From 8b03ee1d5a310f82718281362d105ff09e30148f Mon Sep 17 00:00:00 2001 From: David Bremner Date: Sun, 12 Jun 2016 22:05:49 -0300 Subject: [PATCH] lib: private string map (associative array) API The choice of array implementation is deliberate, for future iterator support --- lib/Makefile.local | 1 + lib/notmuch-private.h | 11 +++ lib/string-map.c | 153 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 165 insertions(+) create mode 100644 lib/string-map.c diff --git a/lib/Makefile.local b/lib/Makefile.local index beb96358..b13513a2 100644 --- a/lib/Makefile.local +++ b/lib/Makefile.local @@ -40,6 +40,7 @@ libnotmuch_c_srcs = \ $(dir)/messages.c \ $(dir)/sha1.c \ $(dir)/built-with.c \ + $(dir)/string-map.c \ $(dir)/tags.c libnotmuch_cxx_srcs = \ diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h index 682b03d8..77011063 100644 --- a/lib/notmuch-private.h +++ b/lib/notmuch-private.h @@ -544,6 +544,17 @@ _notmuch_string_list_sort (notmuch_string_list_t *list); /* string-map.c */ typedef struct _notmuch_string_map notmuch_string_map_t; +notmuch_string_map_t * +_notmuch_string_map_create (const void *ctx); + +void +_notmuch_string_map_append (notmuch_string_map_t *map, + const char *key, + const char *value); + +const char * +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key); + /* tags.c */ notmuch_tags_t * diff --git a/lib/string-map.c b/lib/string-map.c new file mode 100644 index 00000000..0491a10b --- /dev/null +++ b/lib/string-map.c @@ -0,0 +1,153 @@ +/* string-map.c - associative arrays of strings + * + * + * Copyright © 2016 David Bremner + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see http://www.gnu.org/licenses/ . + * + * Author: David Bremner + */ + +#include "notmuch-private.h" + +/* Create a new notmuch_string_map_t object, with 'ctx' as its + * talloc owner. + * + * This function can return NULL in case of out-of-memory. + */ + +typedef struct _notmuch_string_pair_t { + char *key; + char *value; +} notmuch_string_pair_t; + +struct _notmuch_string_map { + notmuch_bool_t sorted; + size_t length; + notmuch_string_pair_t *pairs; +}; + +notmuch_string_map_t * +_notmuch_string_map_create (const void *ctx) +{ + notmuch_string_map_t *map; + + map = talloc (ctx, notmuch_string_map_t); + if (unlikely (map == NULL)) + return NULL; + + map->length = 0; + map->pairs = NULL; + map->sorted = TRUE; + + return map; +} + +void +_notmuch_string_map_append (notmuch_string_map_t *map, + const char *key, + const char *value) +{ + + map->length++; + map->sorted = FALSE; + + if (map->pairs) + map->pairs = talloc_realloc (map, map->pairs, notmuch_string_pair_t, map->length + 1); + else + map->pairs = talloc_array (map, notmuch_string_pair_t, map->length + 1); + + map->pairs[map->length - 1].key = talloc_strdup (map, key); + map->pairs[map->length - 1].value = talloc_strdup (map, value); + + /* Add sentinel */ + map->pairs[map->length].key = NULL; + map->pairs[map->length].value = NULL; + +} + +static int +cmppair (const void *pa, const void *pb) +{ + notmuch_string_pair_t *a = (notmuch_string_pair_t *) pa; + notmuch_string_pair_t *b = (notmuch_string_pair_t *) pb; + + return strcmp (a->key, b->key); +} + +static void +_notmuch_string_map_sort (notmuch_string_map_t *map) +{ + if (map->length == 0) + return; + + if (map->sorted) + return; + + qsort (map->pairs, map->length, sizeof (notmuch_string_pair_t), cmppair); + + map->sorted = TRUE; +} + +static notmuch_bool_t +string_cmp (const char *a, const char *b, notmuch_bool_t exact) +{ + if (exact) + return (strcmp (a, b)); + else + return (strncmp (a, b, strlen (a))); +} + +static notmuch_string_pair_t * +bsearch_first (notmuch_string_pair_t *array, size_t len, const char *key, notmuch_bool_t exact) +{ + size_t first = 0; + size_t last = len - 1; + size_t mid; + + if (len <= 0) + return NULL; + + while (last > first) { + mid = (first + last) / 2; + int sign = string_cmp (key, array[mid].key, exact); + + if (sign <= 0) + last = mid; + else + first = mid + 1; + } + + + if (string_cmp (key, array[first].key, exact) == 0) + return array + first; + else + return NULL; + +} + +const char * +_notmuch_string_map_get (notmuch_string_map_t *map, const char *key) +{ + notmuch_string_pair_t *pair; + + /* this means that calling append invalidates iterators */ + _notmuch_string_map_sort (map); + + pair = bsearch_first (map->pairs, map->length, key, TRUE); + if (! pair) + return NULL; + + return pair->value; +} -- 2.26.2