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