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 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 }