3d/1c1119659ef0dfbbfa6ef64848ffaed4a00309

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