git.notmuchmail.org Git - notmuch/blob - lib/string-map.c

   1 /* string-map.c - associative arrays of strings
   2  *
   3  *
   4  * Copyright © 2016 David Bremner
   5  *
   6  * This program is free software: you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation, either version 3 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program.  If not, see https://www.gnu.org/licenses/ .
  18  *
  19  * Author: David Bremner <david@tethera.net>
  20  */
  21
  22 #include "notmuch-private.h"
  23
  24 /* Create a new notmuch_string_map_t object, with 'ctx' as its
  25  * talloc owner.
  26  *
  27  * This function can return NULL in case of out-of-memory.
  28  */
  29
  30 typedef struct _notmuch_string_pair_t {
  31     char *key;
  32     char *value;
  33 } notmuch_string_pair_t;
  34
  35 struct _notmuch_string_map {
  36     bool sorted;
  37     size_t length;
  38     notmuch_string_pair_t *pairs;
  39 };
  40
  41 struct _notmuch_string_map_iterator {
  42     notmuch_string_pair_t *current;
  43     bool exact;
  44     const char *key;
  45 };
  46
  47 notmuch_string_map_t *
  48 _notmuch_string_map_create (const void *ctx)
  49 {
  50     notmuch_string_map_t *map;
  51
  52     map = talloc (ctx, notmuch_string_map_t);
  53     if (unlikely (map == NULL))
  54         return NULL;
  55
  56     map->length = 0;
  57     map->pairs = NULL;
  58     map->sorted = true;
  59
  60     return map;
  61 }
  62
  63 void
  64 _notmuch_string_map_append (notmuch_string_map_t *map,
  65                             const char *key,
  66                             const char *value)
  67 {
  68
  69     map->length++;
  70     map->sorted = false;
  71
  72     if (map->pairs)
  73         map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1);
  74     else
  75         map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1);
  76
  77     map->pairs[map->length - 1].key = talloc_strdup (map, key);
  78     map->pairs[map->length - 1].value = talloc_strdup (map, value);
  79
  80     /* Add sentinel */
  81     map->pairs[map->length].key = NULL;
  82     map->pairs[map->length].value = NULL;
  83
  84 }
  85
  86 static int
  87 cmppair (const void *pa, const void *pb)
  88 {
  89     notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;
  90     notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;
  91
  92     return strcmp (a->key, b->key);
  93 }
  94
  95 static void
  96 _notmuch_string_map_sort (notmuch_string_map_t *map)
  97 {
  98     if (map->length == 0)
  99         return;
 100
 101     if (map->sorted)
 102         return;
 103
 104     qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);
 105
 106     map->sorted = true;
 107 }
 108
 109 static int
 110 string_cmp (const char *a, const char *b, bool exact)
 111 {
 112     if (exact)
 113         return (strcmp (a, b));
 114     else
 115         return (strncmp (a, b, strlen (a)));
 116 }
 117
 118 static notmuch_string_pair_t *
 119 bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, bool exact)
 120 {
 121     size_t first = 0;
 122     size_t last = len - 1;
 123     size_t mid;
 124
 125     if (len <= 0)
 126         return NULL;
 127
 128     while (last > first) {
 129         mid = (first + last) / 2;
 130         int sign = string_cmp (key, array[mid].key, exact);
 131
 132         if (sign <= 0)
 133             last = mid;
 134         else
 135             first = mid + 1;
 136     }
 137
 138
 139     if (string_cmp (key, array[first].key, exact) == 0)
 140         return array + first;
 141     else
 142         return NULL;
 143
 144 }
 145
 146 void
 147 _notmuch_string_map_set (notmuch_string_map_t *map,
 148                          const char *key,
 149                          const char *val)
 150 {
 151     notmuch_string_pair_t *pair;
 152
 153     /* this means that calling string_map_set invalidates iterators */
 154     _notmuch_string_map_sort (map);
 155     pair = bsearch_first (map->pairs, map->length, key, true);
 156     if (! pair)
 157         _notmuch_string_map_append (map, key, val);
 158     else {
 159         talloc_free (pair->value);
 160         pair->value = talloc_strdup (map->pairs, val);
 161     }
 162 }
 163
 164 const char *
 165 _notmuch_string_map_get (notmuch_string_map_t *map, const char *key)
 166 {
 167     notmuch_string_pair_t *pair;
 168
 169     /* this means that calling append invalidates iterators */
 170     _notmuch_string_map_sort (map);
 171
 172     pair = bsearch_first (map->pairs, map->length, key, true);
 173     if (! pair)
 174         return NULL;
 175
 176     return pair->value;
 177 }
 178
 179 notmuch_string_map_iterator_t *
 180 _notmuch_string_map_iterator_create (notmuch_string_map_t *map, const char *key,
 181                                      bool exact)
 182 {
 183     notmuch_string_map_iterator_t *iter;
 184
 185     _notmuch_string_map_sort (map);
 186
 187     iter = talloc (map, notmuch_string_map_iterator_t);
 188     if (unlikely (iter == NULL))
 189         return NULL;
 190
 191     if (unlikely (talloc_reference (iter, map) == NULL))
 192         return NULL;
 193
 194     iter->key = talloc_strdup (iter, key);
 195     iter->exact = exact;
 196     iter->current = bsearch_first (map->pairs, map->length, key, exact);
 197     return iter;
 198 }
 199
 200 bool
 201 _notmuch_string_map_iterator_valid (notmuch_string_map_iterator_t *iterator)
 202 {
 203     if (iterator->current == NULL)
 204         return false;
 205
 206     /* sentinel */
 207     if (iterator->current->key == NULL)
 208         return false;
 209
 210     return (0 == string_cmp (iterator->key, iterator->current->key, iterator->exact));
 211
 212 }
 213
 214 void
 215 _notmuch_string_map_iterator_move_to_next (notmuch_string_map_iterator_t *iterator)
 216 {
 217
 218     if (! _notmuch_string_map_iterator_valid (iterator))
 219         return;
 220
 221     (iterator->current)++;
 222 }
 223
 224 const char *
 225 _notmuch_string_map_iterator_key (notmuch_string_map_iterator_t *iterator)
 226 {
 227     if (! _notmuch_string_map_iterator_valid (iterator))
 228         return NULL;
 229
 230     return iterator->current->key;
 231 }
 232
 233 const char *
 234 _notmuch_string_map_iterator_value (notmuch_string_map_iterator_t *iterator)
 235 {
 236     if (! _notmuch_string_map_iterator_valid (iterator))
 237         return NULL;
 238
 239     return iterator->current->value;
 240 }
 241
 242 void
 243 _notmuch_string_map_iterator_destroy (notmuch_string_map_iterator_t *iterator)
 244 {
 245     talloc_free (iterator);
 246 }