38/c2ca71843ea0f0aff440178045db08712f1ab0

   1 Return-Path: <bremner@tethera.net>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5  by arlo.cworth.org (Postfix) with ESMTP id 130B16DE0939\r
   6  for <notmuch@notmuchmail.org>; Sun, 12 Jun 2016 18:06:40 -0700 (PDT)\r
   7 X-Virus-Scanned: Debian amavisd-new at cworth.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.011\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.011 tagged_above=-999 required=5\r
  12  tests=[AWL=-0.000, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01]\r
  13  autolearn=disabled\r
  14 Received: from arlo.cworth.org ([127.0.0.1])\r
  15  by localhost (arlo.cworth.org [127.0.0.1]) (amavisd-new, port 10024)\r
  16  with ESMTP id Twp6gmUCHUyi for <notmuch@notmuchmail.org>;\r
  17  Sun, 12 Jun 2016 18:06:32 -0700 (PDT)\r
  18 Received: from fethera.tethera.net (fethera.tethera.net [198.245.60.197])\r
  19  by arlo.cworth.org (Postfix) with ESMTPS id 972AE6DE02B0\r
  20  for <notmuch@notmuchmail.org>; Sun, 12 Jun 2016 18:06:12 -0700 (PDT)\r
  21 Received: from remotemail by fethera.tethera.net with local (Exim 4.84)\r
  22  (envelope-from <bremner@tethera.net>)\r
  23  id 1bCGKE-0003xW-F8; Sun, 12 Jun 2016 21:05:58 -0400\r
  24 Received: (nullmailer pid 5668 invoked by uid 1000);\r
  25  Mon, 13 Jun 2016 01:06:04 -0000\r
  26 From: David Bremner <david@tethera.net>\r
  27 To: notmuch@notmuchmail.org\r
  28 Subject: [PATCH 2/8] lib: private string map (associative array) API\r
  29 Date: Sun, 12 Jun 2016 22:05:49 -0300\r
  30 Message-Id: <1465779955-5539-3-git-send-email-david@tethera.net>\r
  31 X-Mailer: git-send-email 2.8.1\r
  32 In-Reply-To: <1465779955-5539-1-git-send-email-david@tethera.net>\r
  33 References: <1465779955-5539-1-git-send-email-david@tethera.net>\r
  34 MIME-Version: 1.0\r
  35 Content-Type: text/plain; charset=UTF-8\r
  36 Content-Transfer-Encoding: 8bit\r
  37 X-BeenThere: notmuch@notmuchmail.org\r
  38 X-Mailman-Version: 2.1.20\r
  39 Precedence: list\r
  40 List-Id: "Use and development of the notmuch mail system."\r
  41  <notmuch.notmuchmail.org>\r
  42 List-Unsubscribe: <https://notmuchmail.org/mailman/options/notmuch>,\r
  43  <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  44 List-Archive: <http://notmuchmail.org/pipermail/notmuch/>\r
  45 List-Post: <mailto:notmuch@notmuchmail.org>\r
  46 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  47 List-Subscribe: <https://notmuchmail.org/mailman/listinfo/notmuch>,\r
  48  <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  49 X-List-Received-Date: Mon, 13 Jun 2016 01:06:40 -0000\r
  50 \r
  51 The choice of array implementation is deliberate, for future iterator support\r
  52 ---\r
  53  lib/Makefile.local    |   1 +\r
  54  lib/notmuch-private.h |  11 ++++\r
  55  lib/string-map.c      | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++\r
  56  3 files changed, 165 insertions(+)\r
  57  create mode 100644 lib/string-map.c\r
  58 \r
  59 diff --git a/lib/Makefile.local b/lib/Makefile.local\r
  60 index beb9635..9280880 100644\r
  61 --- a/lib/Makefile.local\r
  62 +++ b/lib/Makefile.local\r
  63 @@ -40,6 +40,7 @@ libnotmuch_c_srcs =           \\r
  64         $(dir)/messages.c       \\r
  65         $(dir)/sha1.c           \\r
  66         $(dir)/built-with.c     \\r
  67 +       $(dir)/string-map.c    \\r
  68         $(dir)/tags.c\r
  69  \r
  70  libnotmuch_cxx_srcs =          \\r
  71 diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h\r
  72 index df63905..5abde88 100644\r
  73 --- a/lib/notmuch-private.h\r
  74 +++ b/lib/notmuch-private.h\r
  75 @@ -540,6 +540,17 @@ _notmuch_string_list_sort (notmuch_string_list_t *list);\r
  76  /* string-map.c */\r
  77  typedef struct _notmuch_string_map  notmuch_string_map_t;\r
  78  \r
  79 +notmuch_string_map_t *\r
  80 +_notmuch_string_map_create (const void *ctx);\r
  81 +\r
  82 +void\r
  83 +_notmuch_string_map_append (notmuch_string_map_t *map,\r
  84 +                           const char *key,\r
  85 +                           const char *value);\r
  86 +\r
  87 +const char *\r
  88 +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key);\r
  89 +\r
  90  /* tags.c */\r
  91  \r
  92  notmuch_tags_t *\r
  93 diff --git a/lib/string-map.c b/lib/string-map.c\r
  94 new file mode 100644\r
  95 index 0000000..0491a10\r
  96 --- /dev/null\r
  97 +++ b/lib/string-map.c\r
  98 @@ -0,0 +1,153 @@\r
  99 +/* string-map.c - associative arrays of strings\r
 100 + *\r
 101 + *\r
 102 + * Copyright © 2016 David Bremner\r
 103 + *\r
 104 + * This program is free software: you can redistribute it and/or modify\r
 105 + * it under the terms of the GNU General Public License as published by\r
 106 + * the Free Software Foundation, either version 3 of the License, or\r
 107 + * (at your option) any later version.\r
 108 + *\r
 109 + * This program is distributed in the hope that it will be useful,\r
 110 + * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
 111 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
 112 + * GNU General Public License for more details.\r
 113 + *\r
 114 + * You should have received a copy of the GNU General Public License\r
 115 + * along with this program.  If not, see http://www.gnu.org/licenses/ .\r
 116 + *\r
 117 + * Author: David Bremner <david@tethera.net>\r
 118 + */\r
 119 +\r
 120 +#include "notmuch-private.h"\r
 121 +\r
 122 +/* Create a new notmuch_string_map_t object, with 'ctx' as its\r
 123 + * talloc owner.\r
 124 + *\r
 125 + * This function can return NULL in case of out-of-memory.\r
 126 + */\r
 127 +\r
 128 +typedef struct _notmuch_string_pair_t {\r
 129 +    char *key;\r
 130 +    char *value;\r
 131 +} notmuch_string_pair_t;\r
 132 +\r
 133 +struct _notmuch_string_map {\r
 134 +    notmuch_bool_t sorted;\r
 135 +    size_t length;\r
 136 +    notmuch_string_pair_t *pairs;\r
 137 +};\r
 138 +\r
 139 +notmuch_string_map_t *\r
 140 +_notmuch_string_map_create (const void *ctx)\r
 141 +{\r
 142 +    notmuch_string_map_t *map;\r
 143 +\r
 144 +    map = talloc (ctx, notmuch_string_map_t);\r
 145 +    if (unlikely (map == NULL))\r
 146 +       return NULL;\r
 147 +\r
 148 +    map->length = 0;\r
 149 +    map->pairs = NULL;\r
 150 +    map->sorted = TRUE;\r
 151 +\r
 152 +    return map;\r
 153 +}\r
 154 +\r
 155 +void\r
 156 +_notmuch_string_map_append (notmuch_string_map_t *map,\r
 157 +                           const char *key,\r
 158 +                           const char *value)\r
 159 +{\r
 160 +\r
 161 +    map->length++;\r
 162 +    map->sorted = FALSE;\r
 163 +\r
 164 +    if (map->pairs)\r
 165 +       map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1);\r
 166 +    else\r
 167 +       map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1);\r
 168 +\r
 169 +    map->pairs[map->length - 1].key = talloc_strdup (map, key);\r
 170 +    map->pairs[map->length - 1].value = talloc_strdup (map, value);\r
 171 +\r
 172 +    /* Add sentinel */\r
 173 +    map->pairs[map->length].key = NULL;\r
 174 +    map->pairs[map->length].value = NULL;\r
 175 +\r
 176 +}\r
 177 +\r
 178 +static int\r
 179 +cmppair (const void *pa, const void *pb)\r
 180 +{\r
 181 +    notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;\r
 182 +    notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;\r
 183 +\r
 184 +    return strcmp (a->key, b->key);\r
 185 +}\r
 186 +\r
 187 +static void\r
 188 +_notmuch_string_map_sort (notmuch_string_map_t *map)\r
 189 +{\r
 190 +    if (map->length == 0)\r
 191 +       return;\r
 192 +\r
 193 +    if (map->sorted)\r
 194 +       return;\r
 195 +\r
 196 +    qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);\r
 197 +\r
 198 +    map->sorted = TRUE;\r
 199 +}\r
 200 +\r
 201 +static notmuch_bool_t\r
 202 +string_cmp (const char *a, const char *b, notmuch_bool_t exact)\r
 203 +{\r
 204 +    if (exact)\r
 205 +       return (strcmp (a, b));\r
 206 +    else\r
 207 +       return (strncmp (a, b, strlen (a)));\r
 208 +}\r
 209 +\r
 210 +static notmuch_string_pair_t *\r
 211 +bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, notmuch_bool_t exact)\r
 212 +{\r
 213 +    size_t first = 0;\r
 214 +    size_t last = len - 1;\r
 215 +    size_t mid;\r
 216 +\r
 217 +    if (len <= 0)\r
 218 +       return NULL;\r
 219 +\r
 220 +    while (last > first) {\r
 221 +       mid = (first + last) / 2;\r
 222 +       int sign = string_cmp (key, array[mid].key, exact);\r
 223 +\r
 224 +       if (sign <= 0)\r
 225 +           last = mid;\r
 226 +       else\r
 227 +           first = mid + 1;\r
 228 +    }\r
 229 +\r
 230 +\r
 231 +    if (string_cmp (key, array[first].key, exact) == 0)\r
 232 +       return array + first;\r
 233 +    else\r
 234 +       return NULL;\r
 235 +\r
 236 +}\r
 237 +\r
 238 +const char *\r
 239 +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key)\r
 240 +{\r
 241 +    notmuch_string_pair_t *pair;\r
 242 +\r
 243 +    /* this means that calling append invalidates iterators */\r
 244 +    _notmuch_string_map_sort (map);\r
 245 +\r
 246 +    pair = bsearch_first (map->pairs, map->length, key, TRUE);\r
 247 +    if (! pair)\r
 248 +       return NULL;\r
 249 +\r
 250 +    return pair->value;\r
 251 +}\r
 252 -- \r
 253 2.8.1\r
 254 \r