lib: private string map (associative array) API
[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 http://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     notmuch_bool_t sorted;
37     size_t length;
38     notmuch_string_pair_t *pairs;
39 };
40
41 notmuch_string_map_t *
42 _notmuch_string_map_create (const void *ctx)
43 {
44     notmuch_string_map_t *map;
45
46     map = talloc (ctx, notmuch_string_map_t);
47     if (unlikely (map == NULL))
48         return NULL;
49
50     map->length = 0;
51     map->pairs = NULL;
52     map->sorted = TRUE;
53
54     return map;
55 }
56
57 void
58 _notmuch_string_map_append (notmuch_string_map_t *map,
59                             const char *key,
60                             const char *value)
61 {
62
63     map->length++;
64     map->sorted = FALSE;
65
66     if (map->pairs)
67         map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1);
68     else
69         map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1);
70
71     map->pairs[map->length - 1].key = talloc_strdup (map, key);
72     map->pairs[map->length - 1].value = talloc_strdup (map, value);
73
74     /* Add sentinel */
75     map->pairs[map->length].key = NULL;
76     map->pairs[map->length].value = NULL;
77
78 }
79
80 static int
81 cmppair (const void *pa, const void *pb)
82 {
83     notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa;
84     notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb;
85
86     return strcmp (a->key, b->key);
87 }
88
89 static void
90 _notmuch_string_map_sort (notmuch_string_map_t *map)
91 {
92     if (map->length == 0)
93         return;
94
95     if (map->sorted)
96         return;
97
98     qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair);
99
100     map->sorted = TRUE;
101 }
102
103 static notmuch_bool_t
104 string_cmp (const char *a, const char *b, notmuch_bool_t exact)
105 {
106     if (exact)
107         return (strcmp (a, b));
108     else
109         return (strncmp (a, b, strlen (a)));
110 }
111
112 static notmuch_string_pair_t *
113 bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, notmuch_bool_t exact)
114 {
115     size_t first = 0;
116     size_t last = len - 1;
117     size_t mid;
118
119     if (len <= 0)
120         return NULL;
121
122     while (last > first) {
123         mid = (first + last) / 2;
124         int sign = string_cmp (key, array[mid].key, exact);
125
126         if (sign <= 0)
127             last = mid;
128         else
129             first = mid + 1;
130     }
131
132
133     if (string_cmp (key, array[first].key, exact) == 0)
134         return array + first;
135     else
136         return NULL;
137
138 }
139
140 const char *
141 _notmuch_string_map_get (notmuch_string_map_t *map, const char *key)
142 {
143     notmuch_string_pair_t *pair;
144
145     /* this means that calling append invalidates iterators */
146     _notmuch_string_map_sort (map);
147
148     pair = bsearch_first (map->pairs, map->length, key, TRUE);
149     if (! pair)
150         return NULL;
151
152     return pair->value;
153 }