1 /* string-map.c - associative arrays of strings
4 * Copyright © 2016 David Bremner
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.
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.
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/ .
19 * Author: David Bremner <david@tethera.net>
22 #include "notmuch-private.h"
24 /* Create a new notmuch_string_map_t object, with 'ctx' as its
27 * This function can return NULL in case of out-of-memory.
30 typedef struct _notmuch_string_pair_t {
33 } notmuch_string_pair_t;
35 struct _notmuch_string_map {
38 notmuch_string_pair_t *pairs;
41 struct _notmuch_string_map_iterator {
42 notmuch_string_pair_t *current;
47 notmuch_string_map_t *
48 _notmuch_string_map_create (const void *ctx)
50 notmuch_string_map_t *map;
52 map = talloc (ctx, notmuch_string_map_t);
53 if (unlikely (map == NULL))
64 _notmuch_string_map_append (notmuch_string_map_t *map,
73 map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1);
75 map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1);
77 map->pairs[map->length - 1].key = talloc_strdup (map, key);
78 map->pairs[map->length - 1].value = talloc_strdup (map, value);
81 map->pairs[map->length].key = NULL;
82 map->pairs[map->length].value = NULL;
87 cmppair (const void *pa, const void *pb)
90 notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;
91 notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;
93 cmp = strcmp (a->key, b->key);
95 cmp = strcmp (a->value, b->value);
100 _notmuch_string_map_sort (notmuch_string_map_t *map)
102 if (map->length == 0)
108 qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);
114 string_cmp (const char *a, const char *b, bool exact)
117 return (strcmp (a, b));
119 return (strncmp (a, b, strlen (a)));
122 static notmuch_string_pair_t *
123 bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, bool exact)
126 size_t last = len - 1;
132 while (last > first) {
133 mid = (first + last) / 2;
134 int sign = string_cmp (key, array[mid].key, exact);
143 if (string_cmp (key, array[first].key, exact) == 0)
144 return array + first;
151 _notmuch_string_map_set (notmuch_string_map_t *map,
155 notmuch_string_pair_t *pair;
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);
161 _notmuch_string_map_append (map, key, val);
163 talloc_free (pair->value);
164 pair->value = talloc_strdup (map->pairs, val);
169 _notmuch_string_map_get (notmuch_string_map_t *map, const char *key)
171 notmuch_string_pair_t *pair;
173 /* this means that calling append invalidates iterators */
174 _notmuch_string_map_sort (map);
176 pair = bsearch_first (map->pairs, map->length, key, true);
183 notmuch_string_map_iterator_t *
184 _notmuch_string_map_iterator_create (notmuch_string_map_t *map, const char *key,
187 notmuch_string_map_iterator_t *iter;
189 _notmuch_string_map_sort (map);
191 iter = talloc (map, notmuch_string_map_iterator_t);
192 if (unlikely (iter == NULL))
195 if (unlikely (talloc_reference (iter, map) == NULL))
198 iter->key = talloc_strdup (iter, key);
200 iter->current = bsearch_first (map->pairs, map->length, key, exact);
205 _notmuch_string_map_iterator_valid (notmuch_string_map_iterator_t *iterator)
207 if (iterator->current == NULL)
211 if (iterator->current->key == NULL)
214 return (0 == string_cmp (iterator->key, iterator->current->key, iterator->exact));
219 _notmuch_string_map_iterator_move_to_next (notmuch_string_map_iterator_t *iterator)
222 if (! _notmuch_string_map_iterator_valid (iterator))
225 (iterator->current)++;
229 _notmuch_string_map_iterator_key (notmuch_string_map_iterator_t *iterator)
231 if (! _notmuch_string_map_iterator_valid (iterator))
234 return iterator->current->key;
238 _notmuch_string_map_iterator_value (notmuch_string_map_iterator_t *iterator)
240 if (! _notmuch_string_map_iterator_valid (iterator))
243 return iterator->current->value;
247 _notmuch_string_map_iterator_destroy (notmuch_string_map_iterator_t *iterator)
249 talloc_free (iterator);