From 017a923a8536a406b08c2169957a290efd904549 Mon Sep 17 00:00:00 2001 From: David Bremner Date: Wed, 3 Aug 2016 09:30:22 +0900 Subject: [PATCH] [PATCH 2/8] lib: private string map (associative array) API --- d1/cb3dae46f699d89717140289cdc700321b1666 | 262 ++++++++++++++++++++++ 1 file changed, 262 insertions(+) create mode 100644 d1/cb3dae46f699d89717140289cdc700321b1666 diff --git a/d1/cb3dae46f699d89717140289cdc700321b1666 b/d1/cb3dae46f699d89717140289cdc700321b1666 new file mode 100644 index 000000000..f625cecd9 --- /dev/null +++ b/d1/cb3dae46f699d89717140289cdc700321b1666 @@ -0,0 +1,262 @@ +Return-Path: +X-Original-To: notmuch@notmuchmail.org +Delivered-To: notmuch@notmuchmail.org +Received: from localhost (localhost [127.0.0.1]) + by arlo.cworth.org (Postfix) with ESMTP id D1C466DE00B8 + for ; Tue, 2 Aug 2016 21:40:39 -0700 (PDT) +X-Virus-Scanned: Debian amavisd-new at cworth.org +X-Spam-Flag: NO +X-Spam-Score: -0.005 +X-Spam-Level: +X-Spam-Status: No, score=-0.005 tagged_above=-999 required=5 + tests=[AWL=-0.006, HEADER_FROM_DIFFERENT_DOMAINS=0.001] + 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 pNAI9-Byhq3I for ; + Tue, 2 Aug 2016 21:40:31 -0700 (PDT) +Received: from fethera.tethera.net (fethera.tethera.net [198.245.60.197]) + by arlo.cworth.org (Postfix) with ESMTPS id DA7566DE092A + for ; Tue, 2 Aug 2016 21:39:07 -0700 (PDT) +Received: from remotemail by fethera.tethera.net with local (Exim 4.84_2) + (envelope-from ) + id 1bUnxk-0000Hw-3h; Wed, 03 Aug 2016 00:39:24 -0400 +Received: (nullmailer pid 12781 invoked by uid 1000); + Wed, 03 Aug 2016 00:30:32 -0000 +From: David Bremner +To: notmuch@notmuchmail.org +Subject: [PATCH 2/8] lib: private string map (associative array) API +Date: Wed, 3 Aug 2016 09:30:22 +0900 +Message-Id: <1470184228-12517-3-git-send-email-david@tethera.net> +X-Mailer: git-send-email 2.8.1 +In-Reply-To: <1470184228-12517-1-git-send-email-david@tethera.net> +References: <1470184228-12517-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: Wed, 03 Aug 2016 04:40:39 -0000 + +The choice of array implementation is deliberate, for future iterator support +--- + lib/Makefile.local | 2 + + lib/notmuch-private.h | 11 ++++ + lib/string-map.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++ + 3 files changed, 166 insertions(+) + create mode 100644 lib/string-map.c + +diff --git a/lib/Makefile.local b/lib/Makefile.local +index beb9635..c012ed1 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 = \ +@@ -48,6 +49,7 @@ libnotmuch_cxx_srcs = \ + $(dir)/directory.cc \ + $(dir)/index.cc \ + $(dir)/message.cc \ ++ $(dir)/message-property.cc \ + $(dir)/query.cc \ + $(dir)/query-fp.cc \ + $(dir)/config.cc \ +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 + -- 2.26.2