From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by arlo.cworth.org (Postfix) with ESMTP id 130B16DE0939 for ; Sun, 12 Jun 2016 18:06:40 -0700 (PDT) X-Virus-Scanned: Debian amavisd-new at cworth.org X-Spam-Flag: NO X-Spam-Score: -0.011 X-Spam-Level: X-Spam-Status: No, score=-0.011 tagged_above=-999 required=5 tests=[AWL=-0.000, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01] autolearn=disabled Received: from arlo.cworth.org ([127.0.0.1]) by localhost (arlo.cworth.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Twp6gmUCHUyi for ; Sun, 12 Jun 2016 18:06:32 -0700 (PDT) Received: from fethera.tethera.net (fethera.tethera.net [198.245.60.197]) by arlo.cworth.org (Postfix) with ESMTPS id 972AE6DE02B0 for ; Sun, 12 Jun 2016 18:06:12 -0700 (PDT) Received: from remotemail by fethera.tethera.net with local (Exim 4.84) (envelope-from ) id 1bCGKE-0003xW-F8; Sun, 12 Jun 2016 21:05:58 -0400 Received: (nullmailer pid 5668 invoked by uid 1000); Mon, 13 Jun 2016 01:06:04 -0000 From: David Bremner To: notmuch@notmuchmail.org Subject: [PATCH 2/8] lib: private string map (associative array) API Date: Sun, 12 Jun 2016 22:05:49 -0300 Message-Id: <1465779955-5539-3-git-send-email-david@tethera.net> X-Mailer: git-send-email 2.8.1 In-Reply-To: <1465779955-5539-1-git-send-email-david@tethera.net> References: <1465779955-5539-1-git-send-email-david@tethera.net> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: notmuch@notmuchmail.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: "Use and development of the notmuch mail system." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 13 Jun 2016 01:06:40 -0000 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 beb9635..9280880 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 df63905..5abde88 100644 --- a/lib/notmuch-private.h +++ b/lib/notmuch-private.h @@ -540,6 +540,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 0000000..0491a10 --- /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.8.1