d1/cb3dae46f699d89717140289cdc700321b1666

   1 Return-Path: <bremner@tesseract.cs.unb.ca>\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 D1C466DE00B8\r
   6  for <notmuch@notmuchmail.org>; Tue,  2 Aug 2016 21:40:39 -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.005\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.005 tagged_above=-999 required=5\r
  12  tests=[AWL=-0.006, HEADER_FROM_DIFFERENT_DOMAINS=0.001]\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 pNAI9-Byhq3I for <notmuch@notmuchmail.org>;\r
  17  Tue,  2 Aug 2016 21:40:31 -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 DA7566DE092A\r
  20  for <notmuch@notmuchmail.org>; Tue,  2 Aug 2016 21:39:07 -0700 (PDT)\r
  21 Received: from remotemail by fethera.tethera.net with local (Exim 4.84_2)\r
  22  (envelope-from <bremner@tesseract.cs.unb.ca>)\r
  23  id 1bUnxk-0000Hw-3h; Wed, 03 Aug 2016 00:39:24 -0400\r
  24 Received: (nullmailer pid 12781 invoked by uid 1000);\r
  25  Wed, 03 Aug 2016 00:30:32 -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: Wed,  3 Aug 2016 09:30:22 +0900\r
  30 Message-Id: <1470184228-12517-3-git-send-email-david@tethera.net>\r
  31 X-Mailer: git-send-email 2.8.1\r
  32 In-Reply-To: <1470184228-12517-1-git-send-email-david@tethera.net>\r
  33 References: <1470184228-12517-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: Wed, 03 Aug 2016 04:40:39 -0000\r
  50 \r
  51 The choice of array implementation is deliberate, for future iterator support\r
  52 ---\r
  53  lib/Makefile.local    |   2 +\r
  54  lib/notmuch-private.h |  11 ++++\r
  55  lib/string-map.c      | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++\r
  56  3 files changed, 166 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..c012ed1 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 @@ -48,6 +49,7 @@ libnotmuch_cxx_srcs =         \\r
  72         $(dir)/directory.cc     \\r
  73         $(dir)/index.cc         \\r
  74         $(dir)/message.cc       \\r
  75 +       $(dir)/message-property.cc \\r
  76         $(dir)/query.cc         \\r
  77         $(dir)/query-fp.cc      \\r
  78         $(dir)/config.cc        \\r
  79 diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h\r
  80 index df63905..5abde88 100644\r
  81 --- a/lib/notmuch-private.h\r
  82 +++ b/lib/notmuch-private.h\r
  83 @@ -540,6 +540,17 @@ _notmuch_string_list_sort (notmuch_string_list_t *list);\r
  84  /* string-map.c */\r
  85  typedef struct _notmuch_string_map  notmuch_string_map_t;\r
  86  \r
  87 +notmuch_string_map_t *\r
  88 +_notmuch_string_map_create (const void *ctx);\r
  89 +\r
  90 +void\r
  91 +_notmuch_string_map_append (notmuch_string_map_t *map,\r
  92 +                           const char *key,\r
  93 +                           const char *value);\r
  94 +\r
  95 +const char *\r
  96 +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key);\r
  97 +\r
  98  /* tags.c */\r
  99  \r
 100  notmuch_tags_t *\r
 101 diff --git a/lib/string-map.c b/lib/string-map.c\r
 102 new file mode 100644\r
 103 index 0000000..0491a10\r
 104 --- /dev/null\r
 105 +++ b/lib/string-map.c\r
 106 @@ -0,0 +1,153 @@\r
 107 +/* string-map.c - associative arrays of strings\r
 108 + *\r
 109 + *\r
 110 + * Copyright © 2016 David Bremner\r
 111 + *\r
 112 + * This program is free software: you can redistribute it and/or modify\r
 113 + * it under the terms of the GNU General Public License as published by\r
 114 + * the Free Software Foundation, either version 3 of the License, or\r
 115 + * (at your option) any later version.\r
 116 + *\r
 117 + * This program is distributed in the hope that it will be useful,\r
 118 + * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
 119 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
 120 + * GNU General Public License for more details.\r
 121 + *\r
 122 + * You should have received a copy of the GNU General Public License\r
 123 + * along with this program.  If not, see http://www.gnu.org/licenses/ .\r
 124 + *\r
 125 + * Author: David Bremner <david@tethera.net>\r
 126 + */\r
 127 +\r
 128 +#include "notmuch-private.h"\r
 129 +\r
 130 +/* Create a new notmuch_string_map_t object, with 'ctx' as its\r
 131 + * talloc owner.\r
 132 + *\r
 133 + * This function can return NULL in case of out-of-memory.\r
 134 + */\r
 135 +\r
 136 +typedef struct _notmuch_string_pair_t {\r
 137 +    char *key;\r
 138 +    char *value;\r
 139 +} notmuch_string_pair_t;\r
 140 +\r
 141 +struct _notmuch_string_map {\r
 142 +    notmuch_bool_t sorted;\r
 143 +    size_t length;\r
 144 +    notmuch_string_pair_t *pairs;\r
 145 +};\r
 146 +\r
 147 +notmuch_string_map_t *\r
 148 +_notmuch_string_map_create (const void *ctx)\r
 149 +{\r
 150 +    notmuch_string_map_t *map;\r
 151 +\r
 152 +    map = talloc (ctx, notmuch_string_map_t);\r
 153 +    if (unlikely (map == NULL))\r
 154 +       return NULL;\r
 155 +\r
 156 +    map->length = 0;\r
 157 +    map->pairs = NULL;\r
 158 +    map->sorted = TRUE;\r
 159 +\r
 160 +    return map;\r
 161 +}\r
 162 +\r
 163 +void\r
 164 +_notmuch_string_map_append (notmuch_string_map_t *map,\r
 165 +                           const char *key,\r
 166 +                           const char *value)\r
 167 +{\r
 168 +\r
 169 +    map->length++;\r
 170 +    map->sorted = FALSE;\r
 171 +\r
 172 +    if (map->pairs)\r
 173 +       map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1);\r
 174 +    else\r
 175 +       map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1);\r
 176 +\r
 177 +    map->pairs[map->length - 1].key = talloc_strdup (map, key);\r
 178 +    map->pairs[map->length - 1].value = talloc_strdup (map, value);\r
 179 +\r
 180 +    /* Add sentinel */\r
 181 +    map->pairs[map->length].key = NULL;\r
 182 +    map->pairs[map->length].value = NULL;\r
 183 +\r
 184 +}\r
 185 +\r
 186 +static int\r
 187 +cmppair (const void *pa, const void *pb)\r
 188 +{\r
 189 +    notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;\r
 190 +    notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;\r
 191 +\r
 192 +    return strcmp (a->key, b->key);\r
 193 +}\r
 194 +\r
 195 +static void\r
 196 +_notmuch_string_map_sort (notmuch_string_map_t *map)\r
 197 +{\r
 198 +    if (map->length == 0)\r
 199 +       return;\r
 200 +\r
 201 +    if (map->sorted)\r
 202 +       return;\r
 203 +\r
 204 +    qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);\r
 205 +\r
 206 +    map->sorted = TRUE;\r
 207 +}\r
 208 +\r
 209 +static notmuch_bool_t\r
 210 +string_cmp (const char *a, const char *b, notmuch_bool_t exact)\r
 211 +{\r
 212 +    if (exact)\r
 213 +       return (strcmp (a, b));\r
 214 +    else\r
 215 +       return (strncmp (a, b, strlen (a)));\r
 216 +}\r
 217 +\r
 218 +static notmuch_string_pair_t *\r
 219 +bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, notmuch_bool_t exact)\r
 220 +{\r
 221 +    size_t first = 0;\r
 222 +    size_t last = len - 1;\r
 223 +    size_t mid;\r
 224 +\r
 225 +    if (len <= 0)\r
 226 +       return NULL;\r
 227 +\r
 228 +    while (last > first) {\r
 229 +       mid = (first + last) / 2;\r
 230 +       int sign = string_cmp (key, array[mid].key, exact);\r
 231 +\r
 232 +       if (sign <= 0)\r
 233 +           last = mid;\r
 234 +       else\r
 235 +           first = mid + 1;\r
 236 +    }\r
 237 +\r
 238 +\r
 239 +    if (string_cmp (key, array[first].key, exact) == 0)\r
 240 +       return array + first;\r
 241 +    else\r
 242 +       return NULL;\r
 243 +\r
 244 +}\r
 245 +\r
 246 +const char *\r
 247 +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key)\r
 248 +{\r
 249 +    notmuch_string_pair_t *pair;\r
 250 +\r
 251 +    /* this means that calling append invalidates iterators */\r
 252 +    _notmuch_string_map_sort (map);\r
 253 +\r
 254 +    pair = bsearch_first (map->pairs, map->length, key, TRUE);\r
 255 +    if (! pair)\r
 256 +       return NULL;\r
 257 +\r
 258 +    return pair->value;\r
 259 +}\r
 260 -- \r
 261 2.8.1\r
 262 \r