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     int cmp = 0;
  90     notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;
  91     notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;
  92
  93     cmp = strcmp (a->key, b->key);
  94     if (cmp == 0)
  95         cmp = strcmp (a->value, b->value);
  96     return cmp;
  97 }
  98
  99 static void
 100 _notmuch_string_map_sort (notmuch_string_map_t *map)
 101 {
 102     if (map->length == 0)
 103         return;
 104
 105     if (map->sorted)
 106         return;
 107
 108     qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);
 109
 110     map->sorted = true;
 111 }
 112
 113 static int
 114 string_cmp (const char *a, const char *b, bool exact)
 115 {
 116     if (exact)
 117         return (strcmp (a, b));
 118     else
 119         return (strncmp (a, b, strlen (a)));
 120 }
 121
 122 static notmuch_string_pair_t *
 123 bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, bool exact)
 124 {
 125     size_t first = 0;
 126     size_t last = len - 1;
 127     size_t mid;
 128
 129     if (len <= 0)
 130         return NULL;
 131
 132     while (last > first) {
 133         mid = (first + last) / 2;
 134         int sign = string_cmp (key, array[mid].key, exact);
 135
 136         if (sign <= 0)
 137             last = mid;
 138         else
 139             first = mid + 1;
 140     }
 141
 142
 143     if (string_cmp (key, array[first].key, exact) == 0)
 144         return array + first;
 145     else
 146         return NULL;
 147
 148 }
 149
 150 void
 151 _notmuch_string_map_set (notmuch_string_map_t *map,
 152                          const char *key,
 153                          const char *val)
 154 {
 155     notmuch_string_pair_t *pair;
 156
 157     /* this means that calling string_map_set invalidates iterators */
 158     _notmuch_string_map_sort (map);
 159     pair = bsearch_first (map->pairs, map->length, key, true);
 160     if (! pair)
 161         _notmuch_string_map_append (map, key, val);
 162     else {
 163         talloc_free (pair->value);
 164         pair->value = talloc_strdup (map->pairs, val);
 165     }
 166 }
 167
 168 const char *
 169 _notmuch_string_map_get (notmuch_string_map_t *map, const char *key)
 170 {
 171     notmuch_string_pair_t *pair;
 172
 173     /* this means that calling append invalidates iterators */
 174     _notmuch_string_map_sort (map);
 175
 176     pair = bsearch_first (map->pairs, map->length, key, true);
 177     if (! pair)
 178         return NULL;
 179
 180     return pair->value;
 181 }
 182
 183 notmuch_string_map_iterator_t *
 184 _notmuch_string_map_iterator_create (notmuch_string_map_t *map, const char *key,
 185                                      bool exact)
 186 {
 187     notmuch_string_map_iterator_t *iter;
 188
 189     _notmuch_string_map_sort (map);
 190
 191     iter = talloc (map, notmuch_string_map_iterator_t);
 192     if (unlikely (iter == NULL))
 193         return NULL;
 194
 195     if (unlikely (talloc_reference (iter, map) == NULL))
 196         return NULL;
 197
 198     iter->key = talloc_strdup (iter, key);
 199     iter->exact = exact;
 200     iter->current = bsearch_first (map->pairs, map->length, key, exact);
 201     return iter;
 202 }
 203
 204 bool
 205 _notmuch_string_map_iterator_valid (notmuch_string_map_iterator_t *iterator)
 206 {
 207     if (iterator->current == NULL)
 208         return false;
 209
 210     /* sentinel */
 211     if (iterator->current->key == NULL)
 212         return false;
 213
 214     return (0 == string_cmp (iterator->key, iterator->current->key, iterator->exact));
 215
 216 }
 217
 218 void
 219 _notmuch_string_map_iterator_move_to_next (notmuch_string_map_iterator_t *iterator)
 220 {
 221
 222     if (! _notmuch_string_map_iterator_valid (iterator))
 223         return;
 224
 225     (iterator->current)++;
 226 }
 227
 228 const char *
 229 _notmuch_string_map_iterator_key (notmuch_string_map_iterator_t *iterator)
 230 {
 231     if (! _notmuch_string_map_iterator_valid (iterator))
 232         return NULL;
 233
 234     return iterator->current->key;
 235 }
 236
 237 const char *
 238 _notmuch_string_map_iterator_value (notmuch_string_map_iterator_t *iterator)
 239 {
 240     if (! _notmuch_string_map_iterator_valid (iterator))
 241         return NULL;
 242
 243     return iterator->current->value;
 244 }
 245
 246 void
 247 _notmuch_string_map_iterator_destroy (notmuch_string_map_iterator_t *iterator)
 248 {
 249     talloc_free (iterator);
 250 }