try-emacs-mua: Trim `require' advice for Emacs 25
[notmuch] / 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 const char *
147 _notmuch_string_map_get (notmuch_string_map_t *map, const char *key)
148 {
149     notmuch_string_pair_t *pair;
150
151     /* this means that calling append invalidates iterators */
152     _notmuch_string_map_sort (map);
153
154     pair = bsearch_first (map->pairs, map->length, key, true);
155     if (! pair)
156         return NULL;
157
158     return pair->value;
159 }
160
161 notmuch_string_map_iterator_t *
162 _notmuch_string_map_iterator_create (notmuch_string_map_t *map, const char *key,
163                                      bool exact)
164 {
165     notmuch_string_map_iterator_t *iter;
166
167     _notmuch_string_map_sort (map);
168
169     iter = talloc (map, notmuch_string_map_iterator_t);
170     if (unlikely (iter == NULL))
171         return NULL;
172
173     if (unlikely (talloc_reference (iter, map) == NULL))
174         return NULL;
175
176     iter->key = talloc_strdup (iter, key);
177     iter->exact = exact;
178     iter->current = bsearch_first (map->pairs, map->length, key, exact);
179     return iter;
180 }
181
182 bool
183 _notmuch_string_map_iterator_valid (notmuch_string_map_iterator_t *iterator)
184 {
185     if (iterator->current == NULL)
186         return false;
187
188     /* sentinel */
189     if (iterator->current->key == NULL)
190         return false;
191
192     return (0 == string_cmp (iterator->key, iterator->current->key, iterator->exact));
193
194 }
195
196 void
197 _notmuch_string_map_iterator_move_to_next (notmuch_string_map_iterator_t *iterator)
198 {
199
200     if (! _notmuch_string_map_iterator_valid (iterator))
201         return;
202
203     (iterator->current)++;
204 }
205
206 const char *
207 _notmuch_string_map_iterator_key (notmuch_string_map_iterator_t *iterator)
208 {
209     if (! _notmuch_string_map_iterator_valid (iterator))
210         return NULL;
211
212     return iterator->current->key;
213 }
214
215 const char *
216 _notmuch_string_map_iterator_value (notmuch_string_map_iterator_t *iterator)
217 {
218     if (! _notmuch_string_map_iterator_valid (iterator))
219         return NULL;
220
221     return iterator->current->value;
222 }
223
224 void
225 _notmuch_string_map_iterator_destroy (notmuch_string_map_iterator_t *iterator)
226 {
227     talloc_free (iterator);
228 }