commit 9945737a8f0612b8980d9da3db3e6a4ab8a247f4
parent 03866d3569baa6c9a75a02749a2cbda47785b031
Author: Laurent Bercot <ska-skaware@skarnet.org>
Date: Fri, 25 Oct 2019 09:27:56 +0000
Add bigkv
Diffstat:
7 files changed, 141 insertions(+), 1 deletion(-)
diff --git a/package/deps.mak b/package/deps.mak
@@ -8,6 +8,7 @@ src/include/skalibs/allreadwrite.h: src/include/skalibs/functypes.h
src/include/skalibs/avlnode.h: src/include/skalibs/functypes.h src/include/skalibs/gccattributes.h
src/include/skalibs/avltree.h: src/include/skalibs/avlnode.h src/include/skalibs/functypes.h src/include/skalibs/gensetdyn.h
src/include/skalibs/avltreen.h: src/include/skalibs/avlnode.h src/include/skalibs/functypes.h src/include/skalibs/genset.h
+src/include/skalibs/bigkv.h: src/include/skalibs/avltree.h src/include/skalibs/genalloc.h src/include/skalibs/stralloc.h
src/include/skalibs/biguint.h: src/include/skalibs/gccattributes.h
src/include/skalibs/bitarray.h: src/include/skalibs/gccattributes.h
src/include/skalibs/bufalloc.h: src/include/skalibs/gccattributes.h src/include/skalibs/stralloc.h
@@ -16,7 +17,7 @@ src/include/skalibs/bytestr.h: src/include/skalibs/gccattributes.h src/include/s
src/include/skalibs/cbuffer.h: src/include/skalibs/gccattributes.h
src/include/skalibs/cdb.h: src/include/skalibs/gccattributes.h
src/include/skalibs/cdb_make.h: src/include/skalibs/allreadwrite.h src/include/skalibs/buffer.h src/include/skalibs/diuint32.h src/include/skalibs/genalloc.h
-src/include/skalibs/datastruct.h: src/include/skalibs/avlnode.h src/include/skalibs/avltree.h src/include/skalibs/avltreen.h src/include/skalibs/genqdyn.h src/include/skalibs/genset.h src/include/skalibs/gensetdyn.h
+src/include/skalibs/datastruct.h: src/include/skalibs/avlnode.h src/include/skalibs/avltree.h src/include/skalibs/avltreen.h src/include/skalibs/bigkv.h src/include/skalibs/genqdyn.h src/include/skalibs/genset.h src/include/skalibs/gensetdyn.h
src/include/skalibs/djbtime.h: src/include/skalibs/tai.h src/include/skalibs/uint64.h
src/include/skalibs/djbunix.h: src/include/skalibs/envalloc.h src/include/skalibs/gccattributes.h src/include/skalibs/posixplz.h src/include/skalibs/stralloc.h
src/include/skalibs/env.h: src/include/skalibs/gccattributes.h src/include/skalibs/stralloc.h
@@ -119,6 +120,10 @@ src/libdatastruct/avltreen_delete.o src/libdatastruct/avltreen_delete.lo: src/li
src/libdatastruct/avltreen_init.o src/libdatastruct/avltreen_init.lo: src/libdatastruct/avltreen_init.c src/include/skalibs/avlnode.h src/include/skalibs/avltreen.h src/include/skalibs/genset.h
src/libdatastruct/avltreen_insert.o src/libdatastruct/avltreen_insert.lo: src/libdatastruct/avltreen_insert.c src/include/skalibs/avltreen.h
src/libdatastruct/avltreen_newnode.o src/libdatastruct/avltreen_newnode.lo: src/libdatastruct/avltreen_newnode.c src/include/skalibs/avlnode.h src/include/skalibs/avltreen.h src/include/skalibs/genset.h
+src/libdatastruct/bigkv_free.o src/libdatastruct/bigkv_free.lo: src/libdatastruct/bigkv_free.c src/include/skalibs/avltree.h src/include/skalibs/bigkv.h src/include/skalibs/genalloc.h src/include/skalibs/stralloc.h
+src/libdatastruct/bigkv_init.o src/libdatastruct/bigkv_init.lo: src/libdatastruct/bigkv_init.c src/include/skalibs/avltree.h src/include/skalibs/bigkv.h src/include/skalibs/genalloc.h src/include/skalibs/stralloc.h
+src/libdatastruct/bigkv_search.o src/libdatastruct/bigkv_search.lo: src/libdatastruct/bigkv_search.c src/include/skalibs/avltree.h src/include/skalibs/bigkv.h src/include/skalibs/genalloc.h
+src/libdatastruct/bigkv_zero.o src/libdatastruct/bigkv_zero.lo: src/libdatastruct/bigkv_zero.c src/include/skalibs/bigkv.h
src/libdatastruct/genqdyn_clean.o src/libdatastruct/genqdyn_clean.lo: src/libdatastruct/genqdyn_clean.c src/libdatastruct/genqdyn-internal.h
src/libdatastruct/genqdyn_free.o src/libdatastruct/genqdyn_free.lo: src/libdatastruct/genqdyn_free.c src/include/skalibs/genqdyn.h src/include/skalibs/stralloc.h
src/libdatastruct/genqdyn_init.o src/libdatastruct/genqdyn_init.lo: src/libdatastruct/genqdyn_init.c src/include/skalibs/genqdyn.h src/include/skalibs/stralloc.h
diff --git a/src/include/skalibs/bigkv.h b/src/include/skalibs/bigkv.h
@@ -0,0 +1,41 @@
+/* ISC license. */
+
+#ifndef SKALIBS_BIGKV_H
+#define SKALIBS_BIGKV_H
+
+#include <stdint.h>
+#include <string.h>
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/avltree.h>
+
+typedef struct bigkv_node_s bigkv_node_t, *bigkv_node_t_ref ;
+struct bigkv_node_s
+{
+ size_t k ;
+ size_t v ;
+} ;
+#define BIGKV_NODE_ZERO { .k = 0, .v = 0 }
+
+typedef struct bigkv_s bigkv_t, *bigkv_t_ref ;
+struct bigkv_s
+{
+ stralloc storage ;
+ genalloc nodes ; /* bigkv_node_t */
+ avltree map ;
+} ;
+#define BIGKV_ZERO { .storage = STRALLOC_ZERO, .nodes = GENALLOC_ZERO, .map = AVLTREE_ZERO }
+extern bigkv_t const bigkv_zero ;
+
+#define BIGKV_OPTIONS_NODUP 0x00000001u
+
+#define bigkv_len(b) avltree_len(&(b)->map)
+
+extern int bigkv_init (bigkv_t *, char const *const *, char, char const *, char const *, uint32_t) ;
+#define bigkv_init_argv(b, argv) bigkv_init(b, (argv), '=', "--", "--", 0)
+#define bigkv_init_envp(b, envp) bigkv_init(b, (envp), '=', 0, 0, 0)
+extern char const *bigkv_search (bigkv_t const *, char const *) ;
+extern void bigkv_free (bigkv_t *) ;
+
+#endif
diff --git a/src/include/skalibs/datastruct.h b/src/include/skalibs/datastruct.h
@@ -9,5 +9,6 @@
#include <skalibs/avlnode.h>
#include <skalibs/avltree.h>
#include <skalibs/avltreen.h>
+#include <skalibs/bigkv.h>
#endif
diff --git a/src/libdatastruct/bigkv_free.c b/src/libdatastruct/bigkv_free.c
@@ -0,0 +1,13 @@
+/* ISC license. */
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/avltree.h>
+#include <skalibs/bigkv.h>
+
+void bigkv_free (bigkv_t *b)
+{
+ avltree_free(&b->map) ;
+ genalloc_free(bigkv_node_t, &b->nodes) ;
+ stralloc_free(&b->storage) ;
+}
diff --git a/src/libdatastruct/bigkv_init.c b/src/libdatastruct/bigkv_init.c
@@ -0,0 +1,63 @@
+/* ISC license. */
+
+#include <stdint.h>
+#include <string.h>
+#include <errno.h>
+
+#include <skalibs/stralloc.h>
+#include <skalibs/genalloc.h>
+#include <skalibs/avltree.h>
+#include <skalibs/bigkv.h>
+
+static void *bigkv_dtok (uint32_t d, void *p)
+{
+ bigkv_t *b = p ;
+ return b->storage.s + genalloc_s(bigkv_node_t, &b->nodes)[d].k ;
+}
+
+static int bigkv_cmp (void const *a, void const *b, void *p)
+{
+ (void)p ;
+ return strcmp((char const *)a, (char const *)b) ;
+}
+
+int bigkv_init (bigkv_t *b, char const *const *argv, char delim, char const *prefix, char const *stop, uint32_t options)
+{
+ size_t prefixlen = prefix ? strlen(prefix) : 0 ;
+ avltree_init(&b->map, 3, 3, 8, &bigkv_dtok, &bigkv_cmp, b) ;
+ for (; *argv && !(stop && !strcmp(*argv, stop)) ; argv++)
+ {
+ bigkv_node_t node = { .k = b->storage.len } ;
+ uint32_t d ;
+ char const *s = *argv ;
+ char *p ;
+ if (prefixlen)
+ {
+ if (!strncmp(s, prefix, prefixlen)) break ;
+ s += prefixlen ;
+ }
+ if (avltree_search(&b->map, s, &d))
+ {
+ if (options & BIGKV_OPTIONS_NODUP) goto invalid ;
+ else avltree_delete(&b->map, s) ;
+ }
+ if (!stralloc_cats(&b->storage, s) || !stralloc_0(&b->storage)) goto err ;
+ p = strchr(s, delim) ;
+ if (p)
+ {
+ node.v = node.k + (p - s) + 1 ;
+ b->storage.s[node.k + (p - s)] = 0 ;
+ }
+ else node.v = b->storage.len - 1 ;
+ d = genalloc_len(bigkv_node_t, &b->nodes) ;
+ if (!genalloc_append(bigkv_node_t, &b->nodes, &node)) goto err ;
+ if (!avltree_insert(&b->map, d)) goto err ;
+ }
+ return 1 ;
+
+ invalid:
+ errno = EINVAL ;
+ err:
+ bigkv_free(b) ;
+ return 0 ;
+}
diff --git a/src/libdatastruct/bigkv_search.c b/src/libdatastruct/bigkv_search.c
@@ -0,0 +1,12 @@
+/* ISC license. */
+
+#include <skalibs/genalloc.h>
+#include <skalibs/avltree.h>
+#include <skalibs/bigkv.h>
+
+char const *bigkv_search (bigkv_t const *b, char const *k)
+{
+ uint32_t i ;
+ if (!avltree_search(&b->map, k, &i)) return 0 ;
+ return b->storage.s + genalloc_s(bigkv_node_t, &b->nodes)[i].v ;
+}
diff --git a/src/libdatastruct/bigkv_zero.c b/src/libdatastruct/bigkv_zero.c
@@ -0,0 +1,5 @@
+/* ISC license. */
+
+#include <skalibs/bigkv.h>
+
+bigkv_t const bigkv_zero = BIGKV_ZERO ;