Mercurial > libjeffpc

changeset 464:b1e4c7607050

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
val: introduce VT_NVL This replaces the previous implementation of nvlists. Unfortunately, there is no cbor packing test for VT_NVL because it is complicated to differentiate between a list and an assoc sexpr. However, there are tests for the nvl_pack API, and so the code isn't completely untested. Signed-off-by: Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
author Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
date Sat, 31 Mar 2018 17:34:16 -0400
parents 8f455913bfd0
children c4ac06c3ee4a
files CMakeLists.txt fmt_cbor.c include/jeffpc/cbor.h include/jeffpc/nvl.h include/jeffpc/val.h jeffpc.mapfile-vers nvl.c nvl_convert.c nvl_dump.c nvl_fmt_cbor.c nvl_fmt_json.c nvl_impl.h nvl_pack.c scgisvc.c sexpr.c sexpr_dump.c sexpr_eval.c tests/test_cbor_pack.c tests/test_nvl.c tests/test_nvl_pack.c tests/test_qstring.c val.c val_impl.h val_nvl.c
diffstat 24 files changed, 461 insertions(+), 666 deletions(-) [+]
line wrap: on
line diff
--- a/CMakeLists.txt	Sat Mar 31 19:05:41 2018 -0400
+++ b/CMakeLists.txt	Sat Mar 31 17:34:16 2018 -0400
@@ -99,7 +99,6 @@
 	mem_array.c
 	nvl.c
 	nvl_convert.c
-	nvl_dump.c
 	nvl_fmt_cbor.c
 	nvl_fmt_json.c
 	nvl_pack.c
@@ -122,6 +121,7 @@
 	uuid.c
 	val.c
 	val_array.c
+	val_nvl.c
 	version.c
 	${UMEM_EXTRA_SOURCE}
 )
--- a/fmt_cbor.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/fmt_cbor.c	Sat Mar 31 17:34:16 2018 -0400
@@ -21,6 +21,7 @@
  */
 
 #include <jeffpc/cbor.h>
+#include <jeffpc/nvl.h>
 
 enum major_type {
 	CMT_UINT  = 0,
@@ -231,6 +232,35 @@
 	return cbor_pack_break(buffer);
 }
 
+int cbor_pack_map_val(struct buffer *buffer, struct val *val)
+{
+	struct bst_tree *tree = &val->_set_nvl.values;
+	struct nvpair *cur;
+	size_t npairs;
+	int ret;
+
+	if (val->type != VT_NVL)
+		return -EINVAL;
+
+	npairs = bst_numnodes(tree);
+
+	ret = cbor_pack_map_start(buffer, npairs);
+	if (ret)
+		return ret;
+
+	bst_for_each(tree, cur) {
+		ret = cbor_pack_str(buffer, cur->name);
+		if (ret)
+			return ret;
+
+		ret = cbor_pack_val(buffer, cur->value);
+		if (ret)
+			return ret;
+	}
+
+	return cbor_pack_map_end(buffer, npairs);
+}
+
 int cbor_pack_val(struct buffer *buffer, struct val *val)
 {
 	switch (val->type) {
@@ -258,6 +288,8 @@
 			 */
 			return cbor_pack_array_vals(buffer, val->_set_array.vals,
 						    val->array.nelem);
+		case VT_NVL:
+			return cbor_pack_map_val(buffer, val);
 	}
 
 	return -ENOTSUP;
--- a/include/jeffpc/cbor.h	Sat Mar 31 19:05:41 2018 -0400
+++ b/include/jeffpc/cbor.h	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -49,6 +49,7 @@
 extern int cbor_pack_map_start(struct buffer *buffer, size_t npairs);
 extern int cbor_pack_map_end(struct buffer *buffer, size_t npairs);
 extern int cbor_pack_val(struct buffer *buffer, struct val *val);
+extern int cbor_pack_map_val(struct buffer *buffer, struct val *val);
 
 static inline int cbor_pack_cstr(struct buffer *buffer, const char *str)
 {
--- a/include/jeffpc/nvl.h	Sat Mar 31 19:05:41 2018 -0400
+++ b/include/jeffpc/nvl.h	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -25,24 +25,11 @@
 
 #include <stdbool.h>
 
-#include <jeffpc/list.h>
 #include <jeffpc/val.h>
-#include <jeffpc/refcnt.h>
 #include <jeffpc/buffer.h>
 
 struct nvlist {
-	struct list values;
-	refcnt_t refcnt;
-};
-
-enum nvtype {
-	NVT_ARRAY,
-	NVT_BLOB,
-	NVT_BOOL,
-	NVT_INT,
-	NVT_NULL,
-	NVT_NVL,
-	NVT_STR,
+	struct val val;
 };
 
 /* serialization formats */
@@ -53,26 +40,10 @@
 
 /* do not access these directly */
 struct nvpair {
-	struct list_node node;
+	struct bst_node node;
 
-	const char *name;
-	struct nvval {
-		enum nvtype type;
-		union {
-			struct {
-				struct nvval *vals;
-				size_t nelem;
-			} array;
-			struct {
-				void *ptr;
-				size_t size;
-			} blob;
-			bool b;
-			uint64_t i;
-			struct nvlist *nvl;
-			struct str *str;
-		};
-	} value;
+	struct str *name;
+	struct val *value;
 };
 
 enum nvcvtcond {
@@ -82,14 +53,45 @@
 
 struct nvl_convert_info {
 	const char *name;
-	enum nvtype tgt_type;
+	enum val_type tgt_type;
 	enum nvcvtcond cond;
 };
 
-extern struct nvlist *nvl_alloc(void);
-extern void nvl_free(struct nvlist *nvl);
+#define nvl_alloc()	((struct nvlist *) val_alloc_nvl())
+
+/*
+ * struct val reference counting & casting to struct nvl
+ */
+
+static inline struct nvlist *val_cast_to_nvl(struct val *val)
+{
+	ASSERT(!val || (val->type == VT_NVL));
+
+	return container_of(val, struct nvlist, val);
+}
+
+#define val_getref_nvl(v)	val_cast_to_nvl(val_getref(v))
+
+/*
+ * struct nvl reference counting & casting to struct val
+ */
+
+#define nvl_getref(nvl)		((struct nvlist *) val_getref(nvl_cast_to_val(nvl)))
+
+#define nvl_putref(nvl)		val_putref(nvl_cast_to_val(nvl))
+
+#define nvl_getref_val(nvl)	val_getref(nvl_cast_to_val(nvl))
+
+static inline struct val *nvl_cast_to_val(struct nvlist *nvl)
+{
+	return &nvl->val;
+}
+
+/*
+ * Misc functions
+ */
+
 extern int nvl_merge(struct nvlist *dest, struct nvlist *src);
-extern void nvl_dump_file(FILE *out, struct nvlist *nvl);
 
 /*
  * If convert_all is true, then all errors except -ENOTSUP encountered
@@ -105,14 +107,10 @@
 				 enum nvformat format);
 
 /* iteration */
+extern const struct nvpair *nvl_iter_start(struct nvlist *nvl);
 extern const struct nvpair *nvl_iter_next(struct nvlist *nvl,
 					  const struct nvpair *prev);
 
-static inline const struct nvpair *nvl_iter_start(struct nvlist *nvl)
-{
-	return nvl_iter_next(nvl, NULL);
-}
-
 #define nvl_for_each(pair, nvl)			\
 	for (pair = nvl_iter_start(nvl);	\
 	     pair != NULL;			\
@@ -129,7 +127,7 @@
  * -ERANGE = wrong type (e.g., looking up an int, but stored value is a string)
  */
 extern int nvl_lookup_array(struct nvlist *nvl, const char *name,
-			    const struct nvval **vals, size_t *nelem);
+			    struct val ***vals, size_t *nelem);
 extern int nvl_lookup_blob(struct nvlist *nvl, const char *name,
 			   const void **ptr, size_t *size);
 extern int nvl_lookup_bool(struct nvlist *nvl, const char *name, bool *out);
@@ -147,11 +145,11 @@
  *
  * -ENOMEM = out of memory
  */
-extern int nvl_set(struct nvlist *nvl, const char *name, struct nvval *val);
+extern int nvl_set(struct nvlist *nvl, const char *name, struct val *val);
 extern int nvl_set_array(struct nvlist *nvl, const char *name,
-			 struct nvval *vals, size_t nelem);
+			 struct val **vals, size_t nelem);
 extern int nvl_set_array_copy(struct nvlist *nvl, const char *name,
-			      const struct nvval *vals, size_t nelem);
+			      struct val **vals, size_t nelem);
 extern int nvl_set_blob(struct nvlist *nvl, const char *name, void *ptr,
 			size_t size);
 extern int nvl_set_blob_copy(struct nvlist *nvl, const char *name,
@@ -171,7 +169,7 @@
  * -ERANGE = existing item's type doesn't match requested type
  */
 extern int nvl_unset(struct nvlist *nvl, const char *name);
-extern int nvl_unset_type(struct nvlist *nvl, const char *name, enum nvtype type);
+extern int nvl_unset_type(struct nvlist *nvl, const char *name, enum val_type type);
 
 /*
  * Check existence of a specific key, or key-valuetype pair from the list.
@@ -187,7 +185,7 @@
  */
 extern bool nvl_exists(struct nvlist *nvl, const char *name);
 extern int nvl_exists_type(struct nvlist *nvl, const char *name,
-			   enum nvtype type);
+			   enum val_type type);
 
 /*
  * nvpair related functions
@@ -195,12 +193,12 @@
 
 static inline const char *nvpair_name(const struct nvpair *pair)
 {
-	return pair->name;
+	return str_cstr(pair->name);
 }
 
-static inline enum nvtype nvpair_type(const struct nvpair *pair)
+static inline enum val_type nvpair_type(const struct nvpair *pair)
 {
-	return pair->value.type;
+	return pair->value->type;
 }
 
 /*
@@ -208,7 +206,7 @@
  * integer.  The meaning of the return values is the same as well.
  */
 extern int nvpair_value_array(const struct nvpair *pair,
-			      const struct nvval **vals, size_t *nelem);
+			      struct val ***vals, size_t *nelem);
 extern int nvpair_value_blob(const struct nvpair *pair,
 			     const void **ptr, size_t *size);
 extern int nvpair_value_bool(const struct nvpair *pair, bool *out);
@@ -217,18 +215,4 @@
 extern struct nvlist *nvpair_value_nvl(const struct nvpair *pair);
 extern struct str *nvpair_value_str(const struct nvpair *pair);
 
-/*
- * nvval related functions
- */
-
-extern void nvval_release_array(struct nvval *vals, size_t nelem);
-
-static inline void nvval_release(struct nvval *val)
-{
-	if (val)
-		nvval_release_array(val, 1);
-}
-
-REFCNT_INLINE_FXNS(struct nvlist, nvl, refcnt, nvl_free, NULL)
-
 #endif
--- a/include/jeffpc/val.h	Sat Mar 31 19:05:41 2018 -0400
+++ b/include/jeffpc/val.h	Sat Mar 31 17:34:16 2018 -0400
@@ -30,6 +30,8 @@
 #include <jeffpc/refcnt.h>
 #include <jeffpc/error.h>
 #include <jeffpc/types.h>
+#include <jeffpc/list.h>
+#include <jeffpc/bst.h>
 
 /*
  * A typed value structure.
@@ -54,6 +56,7 @@
 	VT_CHAR,	/* a single (unicode) character */
 	VT_BLOB,	/* a byte string */
 	VT_ARRAY,	/* an array of values */
+	VT_NVL,		/* an nvlist */
 };
 
 #define STR_INLINE_LEN	15
@@ -81,6 +84,15 @@
 			struct val **vals;
 			size_t nelem;
 		} array;
+		const struct {
+			/*
+			 * TODO: Using an unbalanced binary search tree is
+			 * not great, but it will do for now.  Once we have
+			 * a balanced binary search tree implementation, we
+			 * should switch to it.
+			 */
+			struct bst_tree values;
+		} nvl;
 
 		/*
 		 * We want to keep the normal members const to catch
@@ -109,6 +121,9 @@
 			struct val **vals;
 			size_t nelem;
 		} _set_array;
+		struct {
+			struct bst_tree values;
+		} _set_nvl;
 	};
 };
 
@@ -133,6 +148,7 @@
 extern struct val *val_alloc_char(uint64_t v);
 extern struct val *val_alloc_int(uint64_t v);
 extern struct val *val_alloc_null(void);
+extern struct val *val_alloc_nvl(void);
 
 /* val_alloc_cons always consume the passed in references */
 extern struct val *val_alloc_cons(struct val *head, struct val *tail);
@@ -362,6 +378,7 @@
 #define VAL_ALLOC_BOOL(v)	val_alloc_bool(v) /* never fails */
 #define VAL_ALLOC_NULL()	val_alloc_null() /* never fails */
 #define VAL_ALLOC_CONS(h, t)	_VAL_ALLOC(struct val, val_alloc_cons((h), (t)))
+#define VAL_ALLOC_NVL()		_VAL_ALLOC(struct val, val_alloc_nvl())
 
 #define VAL_ALLOC_ARRAY(v, l)		_VAL_ALLOC(struct val, val_alloc_array((v), (l)))
 #define VAL_ALLOC_ARRAY_DUP(v, l)	_VAL_ALLOC(struct val, val_alloc_array_dup((v), (l)))
--- a/jeffpc.mapfile-vers	Sat Mar 31 19:05:41 2018 -0400
+++ b/jeffpc.mapfile-vers	Sat Mar 31 17:34:16 2018 -0400
@@ -55,6 +55,7 @@
 		cbor_pack_int;
 		cbor_pack_map_end;
 		cbor_pack_map_start;
+		cbor_pack_map_val;
 		cbor_pack_nint;
 		cbor_pack_null;
 		cbor_pack_str;
@@ -104,13 +105,11 @@
 		mem_recallocarray;
 
 		# nvlist
-		nvl_alloc;
 		nvl_convert;
-		nvl_dump_file;
 		nvl_exists;
 		nvl_exists_type;
-		nvl_free;
 		nvl_iter_next;
+		nvl_iter_start;
 		nvl_lookup;
 		nvl_lookup_array;
 		nvl_lookup_blob;
@@ -143,7 +142,6 @@
 		nvpair_value_null;
 		nvpair_value_nvl;
 		nvpair_value_str;
-		nvval_release_array;
 
 		# padding
 		check_padding;
@@ -251,6 +249,7 @@
 		val_alloc_cons;
 		val_alloc_int;
 		val_alloc_null;
+		val_alloc_nvl;
 		val_empty_cons;
 
 		# urldecode
--- a/nvl.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl.c	Sat Mar 31 17:34:16 2018 -0400
@@ -24,225 +24,16 @@
 #include <jeffpc/mem.h>
 #include <jeffpc/nvl.h>
 
-static void nvpair_free(struct nvpair *pair);
-
-static struct mem_cache *nvlist_cache;
-static struct mem_cache *nvpair_cache;
-
-static void __attribute__((constructor)) init_nvl_subsys(void)
-{
-	nvlist_cache = mem_cache_create("nvlist-cache", sizeof(struct nvlist),
-					0);
-	ASSERT(!IS_ERR(nvlist_cache));
-	nvpair_cache = mem_cache_create("nvpair-cache", sizeof(struct nvpair),
-					0);
-	ASSERT(!IS_ERR(nvpair_cache));
-}
-
-struct nvlist *nvl_alloc(void)
-{
-	struct nvlist *nvl;
-
-	nvl = mem_cache_alloc(nvlist_cache);
-	if (!nvl)
-		return NULL;
-
-	refcnt_init(&nvl->refcnt, 1);
-	list_create(&nvl->values, sizeof(struct nvpair),
-		    offsetof(struct nvpair, node));
-
-	return nvl;
-}
-
-void nvl_free(struct nvlist *nvl)
-{
-	struct nvpair *cur, *safe;
-
-	ASSERT(nvl);
-	ASSERT3U(refcnt_read(&nvl->refcnt), ==, 0);
-
-	list_for_each_safe(cur, safe, &nvl->values)
-		nvpair_free(cur);
-
-	mem_cache_free(nvlist_cache, nvl);
-}
-
-static void __nvval_release(struct nvval *val)
-{
-	size_t i;
-
-	switch (val->type) {
-		case NVT_ARRAY:
-			for (i = 0; i < val->array.nelem; i++)
-				__nvval_release(&val->array.vals[i]);
-			free(val->array.vals);
-			break;
-		case NVT_BLOB:
-			free(val->blob.ptr);
-			break;
-		case NVT_BOOL:
-		case NVT_INT:
-		case NVT_NULL:
-			break;
-		case NVT_NVL:
-			nvl_putref(val->nvl);
-			break;
-		case NVT_STR:
-			str_putref(val->str);
-			break;
-	}
-}
-
-void nvval_release_array(struct nvval *vals, size_t nelem)
-{
-	size_t i;
-
-	if (!vals && !nelem)
-		return;
-
-	ASSERT(vals);
-	ASSERT(nelem);
-
-	for (i = 0; i < nelem; i++)
-		__nvval_release(&vals[i]);
-}
-
-static struct nvval *val_dup_array(const struct nvval *user_vals, size_t nelem)
-{
-	struct nvval *vals;
-	size_t i;
-
-	vals = mem_reallocarray(NULL, nelem, sizeof(struct nvval));
-	if (!vals)
-		return NULL;
-
-	for (i = 0; i < nelem; i++) {
-		const struct nvval *uval = &user_vals[i];
-
-		vals[i].type = uval->type;
-
-		switch (uval->type) {
-			case NVT_ARRAY: {
-				struct nvval *subvals;
-
-				subvals = val_dup_array(uval->array.vals,
-							uval->array.nelem);
-				if (!subvals)
-					goto err;
-
-				vals[i].array.vals = subvals;
-				vals[i].array.nelem = uval->array.nelem;
-				break;
-			}
-			case NVT_BLOB: {
-				void *tmp;
-
-				tmp = malloc(uval->blob.size);
-				if (!tmp)
-					goto err;
-
-				memcpy(tmp, uval->blob.ptr, uval->blob.size);
-
-				vals[i].blob.ptr = tmp;
-				vals[i].blob.size = uval->blob.size;
-				break;
-			}
-			case NVT_BOOL:
-				vals[i].b = uval->b;
-				break;
-			case NVT_INT:
-				vals[i].i = uval->i;
-				break;
-			case NVT_NULL:
-				break;
-			case NVT_NVL:
-				vals[i].nvl = nvl_getref(uval->nvl);
-				break;
-			case NVT_STR:
-				vals[i].str = str_getref(uval->str);
-				break;
-		}
-	}
-
-	return vals;
-
-err:
-	/* only free the copied elements */
-	nelem = i;
-
-	nvval_release_array(vals, nelem);
-	free(vals);
-
-	return NULL;
-}
-
-static struct nvpair *nvpair_alloc(const char *name)
-{
-	struct nvpair *pair;
-
-	pair = mem_cache_alloc(nvpair_cache);
-	if (!pair)
-		return NULL;
-
-	pair->name = strdup(name);
-	if (!pair->name) {
-		mem_cache_free(nvpair_cache, pair);
-		return NULL;
-	}
-
-	pair->value.type = NVT_INT;
-	pair->value.i = 0;
-
-	return pair;
-}
-
-static void nvpair_free(struct nvpair *pair)
-{
-	__nvval_release(&pair->value);
-
-	free((char *) pair->name);
-
-	mem_cache_free(nvpair_cache, pair);
-}
+#include "val_impl.h"
 
 int nvl_merge(struct nvlist *dest, struct nvlist *src)
 {
 	const struct nvpair *spair;
 
 	nvl_for_each(spair, src) {
-		const struct nvval *val = &spair->value;
 		int ret;
 
-		switch (spair->value.type) {
-			case NVT_ARRAY:
-				ret = nvl_set_array_copy(dest, spair->name,
-							 val->array.vals,
-							 val->array.nelem);
-				break;
-			case NVT_BLOB:
-				ret = nvl_set_blob_copy(dest, spair->name,
-							val->blob.ptr,
-							val->blob.size);
-				break;
-			case NVT_BOOL:
-				ret = nvl_set_bool(dest, spair->name, val->b);
-				break;
-			case NVT_INT:
-				ret = nvl_set_int(dest, spair->name, val->i);
-				break;
-			case NVT_NULL:
-				ret = nvl_set_null(dest, spair->name);
-				break;
-			case NVT_NVL:
-				ret = nvl_set_nvl(dest, spair->name,
-						  nvl_getref(val->nvl));
-				break;
-			case NVT_STR:
-				ret = nvl_set_str(dest, spair->name,
-						  str_getref(val->str));
-				break;
-		}
-
+		ret = nvl_set(dest, str_cstr(spair->name), spair->value);
 		if (ret)
 			return ret;
 	}
@@ -252,23 +43,27 @@
 
 static struct nvpair *find(struct nvlist *nvl, const char *name)
 {
-	struct nvpair *cur;
+	struct str name_str = STR_STATIC_INITIALIZER(name);
+	struct nvpair key = {
+		.name = &name_str,
+	};
 
-	list_for_each(cur, &nvl->values)
-		if (!strcmp(cur->name, name))
-			return cur;
-
-	return NULL;
+	return bst_find(&nvl->val._set_nvl.values, &key, NULL);
 }
 
 /*
  * nvlist iteration
  */
 
+const struct nvpair *nvl_iter_start(struct nvlist *nvl)
+{
+	return bst_first(&nvl->val._set_nvl.values);
+}
+
 const struct nvpair *nvl_iter_next(struct nvlist *nvl,
 				   const struct nvpair *prev)
 {
-	return list_next(&nvl->values, (struct nvpair *) prev);
+	return bst_next(&nvl->val._set_nvl.values, (void *) prev);
 }
 
 /*
@@ -297,7 +92,7 @@
 }
 
 int nvl_lookup_array(struct nvlist *nvl, const char *name,
-		     const struct nvval **vals, size_t *nelem)
+		     struct val ***vals, size_t *nelem)
 {
 	return nvpair_value_array(find(nvl, name), vals, nelem);
 }
@@ -323,165 +118,73 @@
  * nvlist set
  */
 
-static struct nvpair *__nvl_set_prep(struct nvlist *nvl, const char *name)
+int nvl_set(struct nvlist *nvl, const char *name, struct val *val)
 {
 	struct nvpair *pair;
 
 	pair = find(nvl, name);
 	if (!pair) {
 		/* not found - allocate a new pair */
-		pair = nvpair_alloc(name);
-		if (!pair)
-			return NULL;
+		pair = __nvpair_alloc(name);
+		if (!pair) {
+			val_putref(val);
+			return -ENOMEM;
+		}
 
-		list_insert_tail(&nvl->values, pair);
-	} else {
-		/* found & should reuse it */
-		__nvval_release(&pair->value);
-
-		pair->value.type = NVT_INT;
-		pair->value.i = 0;
+		bst_add(&nvl->val._set_nvl.values, pair);
 	}
 
-	return pair;
-}
-
-int nvl_set(struct nvlist *nvl, const char *name, struct nvval *val)
-{
-	struct nvpair *pair;
-
-	pair = __nvl_set_prep(nvl, name);
-	if (!pair)
-		return -ENOMEM;
-
-	pair->value = *val;
-
-	return 0;
-}
-
-#define SET(fxn, ctype, nvtype, nvmember, putref)			\
-int fxn(struct nvlist *nvl, const char *name, ctype val)		\
-{									\
-	struct nvpair *pair;						\
-									\
-	pair = __nvl_set_prep(nvl, name);				\
-	if (!pair) {							\
-		putref(val);						\
-		return -ENOMEM;						\
-	}								\
-									\
-	pair->value.type = nvtype;					\
-	pair->value.nvmember = val;					\
-									\
-	return 0;							\
-}
-
-int nvl_set_array(struct nvlist *nvl, const char *name,
-		  struct nvval *vals, size_t nelem)
-{
-	struct nvpair *pair;
-
-	pair = __nvl_set_prep(nvl, name);
-	if (!pair)
-		return -ENOMEM;
-
-	pair->value.type = NVT_ARRAY;
-	pair->value.array.vals = vals;
-	pair->value.array.nelem = nelem;
+	val_putref(pair->value);
+	pair->value = val;
 
 	return 0;
 }
 
-int nvl_set_array_copy(struct nvlist *nvl, const char *name,
-		       const struct nvval *vals, size_t nelem)
-{
-	struct nvval *tmp;
-	int ret;
-
-	tmp = val_dup_array(vals, nelem);
-	if (!tmp)
-		return -ENOMEM;
-
-	ret = nvl_set_array(nvl, name, tmp, nelem);
-	if (ret) {
-		nvval_release_array(tmp, nelem);
-		free(tmp);
-	}
+#define SET(nvl, name, valalloc)					\
+	do {								\
+		struct val *val;					\
+									\
+		val = valalloc;						\
+		if (IS_ERR(val))					\
+			return PTR_ERR(val);				\
+									\
+		return nvl_set(nvl, name, val);				\
+	} while (0)
 
-	return ret;
-}
-
-int nvl_set_blob(struct nvlist *nvl, const char *name, void *ptr, size_t size)
-{
-	struct nvpair *pair;
-
-	pair = __nvl_set_prep(nvl, name);
-	if (!pair)
-		return -ENOMEM;
-
-	pair->value.type = NVT_BLOB;
-	pair->value.blob.ptr = ptr;
-	pair->value.blob.size = size;
-
-	return 0;
+#define SET_ARG0(fxn, valalloc)						\
+int fxn(struct nvlist *nvl, const char *name)				\
+{									\
+	SET(nvl, name, valalloc());					\
 }
 
-int nvl_set_blob_copy(struct nvlist *nvl, const char *name, const void *ptr,
-		      size_t size)
-{
-	void *tmp;
-	int ret;
-
-	tmp = malloc(size);
-	if (!tmp)
-		return -ENOMEM;
-
-	memcpy(tmp, ptr, size);
-
-	ret = nvl_set_blob(nvl, name, tmp, size);
-	if (ret)
-		free(tmp);
-
-	return ret;
-
+#define SET_ARG1(fxn, ctype, valalloc)					\
+int fxn(struct nvlist *nvl, const char *name, ctype v)			\
+{									\
+	SET(nvl, name, valalloc(v));					\
 }
 
-SET(nvl_set_bool, bool, NVT_BOOL, b, (void));
-
-int nvl_set_cstr_dup(struct nvlist *nvl, const char *name, const char *val)
-{
-	struct str *str;
-
-	str = str_dup(val);
-	if (!str)
-		return -ENOMEM;
-
-	return nvl_set_str(nvl, name, str);
+#define SET_ARG2(fxn, ctype1, ctype2, valalloc)				\
+int fxn(struct nvlist *nvl, const char *name, ctype1 a, ctype2 b)	\
+{									\
+	SET(nvl, name, valalloc(a, b));					\
 }
 
-SET(nvl_set_int, uint64_t, NVT_INT, i, (void));
-
-int nvl_set_null(struct nvlist *nvl, const char *name)
-{
-	struct nvpair *pair;
-
-	pair = __nvl_set_prep(nvl, name);
-	if (!pair)
-		return -ENOMEM;
-
-	pair->value.type = NVT_NULL;
-
-	return 0;
-}
-
-SET(nvl_set_nvl, struct nvlist *, NVT_NVL, nvl, nvl_putref);
-SET(nvl_set_str, struct str *, NVT_STR, str, str_putref);
+SET_ARG2(nvl_set_array, struct val **, size_t, val_alloc_array);
+SET_ARG2(nvl_set_array_copy, struct val **, size_t, val_alloc_array_dup);
+SET_ARG2(nvl_set_blob, void *, size_t, val_alloc_blob);
+SET_ARG2(nvl_set_blob_copy, const void *, size_t, val_alloc_blob_dup);
+SET_ARG1(nvl_set_bool, bool, val_alloc_bool);
+SET_ARG1(nvl_set_cstr_dup, const char *, val_dup_str);
+SET_ARG1(nvl_set_int, uint64_t, val_alloc_int);
+SET_ARG0(nvl_set_null, val_alloc_null);
+SET_ARG1(nvl_set_nvl, struct nvlist *, nvl_cast_to_val);
+SET_ARG1(nvl_set_str, struct str *, str_cast_to_val);
 
 /*
  * nvlist unset
  */
 
-static int unset(struct nvlist *nvl, const char *name, enum nvtype type,
+static int unset(struct nvlist *nvl, const char *name, enum val_type type,
 		 bool matchtype)
 {
 	struct nvpair *pair;
@@ -490,22 +193,22 @@
 	if (!pair)
 		return -ENOENT;
 
-	if (matchtype && (pair->value.type != type))
+	if (matchtype && (pair->value->type != type))
 		return -ERANGE;
 
-	list_remove(&nvl->values, pair);
+	bst_remove(&nvl->val._set_nvl.values, pair);
 
-	nvpair_free(pair);
+	__nvpair_free(pair);
 
 	return 0;
 }
 
 int nvl_unset(struct nvlist *nvl, const char *name)
 {
-	return unset(nvl, name, NVT_NULL, false);
+	return unset(nvl, name, VT_NULL, false);
 }
 
-int nvl_unset_type(struct nvlist *nvl, const char *name, enum nvtype type)
+int nvl_unset_type(struct nvlist *nvl, const char *name, enum val_type type)
 {
 	return unset(nvl, name, type, true);
 }
@@ -518,7 +221,7 @@
 	return find(nvl, name) != NULL;
 }
 
-int nvl_exists_type(struct nvlist *nvl, const char *name, enum nvtype type)
+int nvl_exists_type(struct nvlist *nvl, const char *name, enum val_type type)
 {
 	struct nvpair *pair;
 
@@ -526,7 +229,7 @@
 	if (!pair)
 		return -ENOENT;
 
-	if (pair->value.type != type)
+	if (pair->value->type != type)
 		return -ERANGE;
 
 	return 0;
@@ -536,43 +239,43 @@
  * nvpair value
  */
 
-#define VALUE_INT(fxn, ctype, nvtype, nvmember)				\
+#define VALUE_INT(fxn, ctype, nvtype, valmember)			\
 int fxn(const struct nvpair *pair, ctype *out)				\
 {									\
 	if (!pair)							\
 		return -ENOENT;						\
 									\
-	if (pair->value.type != nvtype)					\
+	if (pair->value->type != nvtype)				\
 		return -ERANGE;						\
 									\
-	*out = pair->value.nvmember;					\
+	*out = pair->value->valmember;					\
 									\
 	return 0;							\
 }
 
-#define VALUE_PTR(fxn, ctype, nvtype, nvmember, getref)			\
+#define VALUE_PTR(fxn, ctype, valtype, getref)				\
 ctype fxn(const struct nvpair *pair)					\
 {									\
 	if (!pair)							\
 		return ERR_PTR(-ENOENT);				\
 									\
-	if (pair->value.type != nvtype)					\
+	if (pair->value->type != valtype)				\
 		return ERR_PTR(-ERANGE);				\
 									\
-	return getref(pair->value.nvmember);				\
+	return getref(pair->value);					\
 }
 
-int nvpair_value_array(const struct nvpair *pair, const struct nvval **vals,
+int nvpair_value_array(const struct nvpair *pair, struct val ***vals,
 		       size_t *nelem)
 {
 	if (!pair)
 		return -ENOENT;
 
-	if (pair->value.type != NVT_ARRAY)
+	if (pair->value->type != VT_ARRAY)
 		return -ERANGE;
 
-	*vals = pair->value.array.vals;
-	*nelem = pair->value.array.nelem;
+	*vals = pair->value->_set_array.vals;
+	*nelem = pair->value->array.nelem;
 
 	return 0;
 }
@@ -582,28 +285,28 @@
 	if (!pair)
 		return -ENOENT;
 
-	if (pair->value.type != NVT_BLOB)
+	if (pair->value->type != VT_BLOB)
 		return -ERANGE;
 
-	*ptr = pair->value.blob.ptr;
-	*size = pair->value.blob.size;
+	*ptr = pair->value->blob.ptr;
+	*size = pair->value->blob.size;
 
 	return 0;
 }
 
-VALUE_INT(nvpair_value_bool, bool, NVT_BOOL, b);
-VALUE_INT(nvpair_value_int, uint64_t, NVT_INT, i);
+VALUE_INT(nvpair_value_bool, bool, VT_BOOL, b);
+VALUE_INT(nvpair_value_int, uint64_t, VT_INT, i);
 
 int nvpair_value_null(const struct nvpair *pair)
 {
 	if (!pair)
 		return -ENOENT;
 
-	if (pair->value.type != NVT_NULL)
+	if (pair->value->type != VT_NULL)
 		return -ERANGE;
 
 	return 0;
 }
 
-VALUE_PTR(nvpair_value_nvl, struct nvlist *, NVT_STR, nvl, nvl_getref);
-VALUE_PTR(nvpair_value_str, struct str *, NVT_STR, str, str_getref);
+VALUE_PTR(nvpair_value_nvl, struct nvlist *, VT_NVL, val_getref_nvl);
+VALUE_PTR(nvpair_value_str, struct str *, VT_STR, val_getref_str);
--- a/nvl_convert.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl_convert.c	Sat Mar 31 17:34:16 2018 -0400
@@ -42,14 +42,14 @@
 }
 
 static int cvt_string(struct nvlist *nvl, const struct nvpair *pair,
-		      enum nvtype tgt, enum nvcvtcond cond)
+		      enum val_type tgt, enum nvcvtcond cond)
 {
 	const char *name = nvpair_name(pair);
 	struct str *str;
 	uint64_t intval;
 	int ret = -ENOTSUP;
 
-	ASSERT3U(nvpair_type(pair), ==, NVT_STR);
+	ASSERT3U(nvpair_type(pair), ==, VT_STR);
 
 	str = nvpair_value_str(pair);
 	if (IS_ERR(str)) {
@@ -66,23 +66,26 @@
 	}
 
 	switch (tgt) {
-		case NVT_ARRAY:
-		case NVT_BLOB:
-		case NVT_BOOL:
+		case VT_ARRAY:
+		case VT_BLOB:
+		case VT_BOOL:
+		case VT_SYM:
+		case VT_CONS:
+		case VT_CHAR:
 			ret = -ENOTSUP;
 			break;
-		case NVT_INT:
+		case VT_INT:
 			ret = str2u64(str_cstr(str), &intval);
 			if (!ret)
 				ret = nvl_set_int(nvl, name, intval);
 			break;
-		case NVT_NULL:
+		case VT_NULL:
 			ret = nvl_set_null(nvl, name);
 			break;
-		case NVT_NVL:
+		case VT_NVL:
 			ret = -ENOTSUP;
 			break;
-		case NVT_STR:
+		case VT_STR:
 			/* nothing to do */
 			ret = 0;
 			break;
@@ -121,14 +124,17 @@
 		}
 
 		switch (nvpair_type(pair)) {
-			case NVT_ARRAY:
-			case NVT_BLOB:
-			case NVT_BOOL:
-			case NVT_INT:
-			case NVT_NULL:
-			case NVT_NVL:
+			case VT_ARRAY:
+			case VT_BLOB:
+			case VT_BOOL:
+			case VT_INT:
+			case VT_NULL:
+			case VT_NVL:
+			case VT_SYM:
+			case VT_CONS:
+			case VT_CHAR:
 				return -ENOTSUP;
-			case NVT_STR:
+			case VT_STR:
 				ret = cvt_string(nvl, pair, table->tgt_type,
 						 table->cond);
 				break;
--- a/nvl_dump.c	Sat Mar 31 19:05:41 2018 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,122 +0,0 @@
-/*
- * Copyright (c) 2014-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-
-#include <jeffpc/error.h>
-#include <jeffpc/nvl.h>
-#include <jeffpc/thread.h>
-
-#define INDENT	4
-
-static void __dump_nvl(FILE *out, struct nvlist *nvl, int indent);
-
-static const char *typename(int type)
-{
-	static const char *typenames[] = {
-		[NVT_ARRAY] = "array",
-		[NVT_BLOB] = "blob",
-		[NVT_BOOL] = "bool",
-		[NVT_INT] = "int",
-		[NVT_NVL] = "nvlist",
-		[NVT_NULL] = "null",
-		[NVT_STR] = "string",
-	};
-
-	static __thread char badname[10];
-
-	if ((type < 0) || (type > NVT_STR))
-		goto bad;
-
-	if (typenames[type] == NULL)
-		goto bad;
-
-	return typenames[type];
-
-bad:
-	snprintf(badname, sizeof(badname), "<%d>", type);
-	return badname;
-}
-
-static inline void doindent(FILE *out, int howmuch)
-{
-	fprintf(out, "%*s", INDENT * howmuch, "");
-}
-
-static void __dump_val(FILE *out, const struct nvval *val, int indent)
-{
-	size_t i;
-
-	fprintf(out, " type=%s", typename(val->type));
-
-	switch (val->type) {
-		case NVT_ARRAY:
-			fprintf(out, " nelem=%zu\n", val->array.nelem);
-			for (i = 0; i < val->array.nelem; i++) {
-				doindent(out, indent);
-				fprintf(out, "[%zu]: ", i);
-				__dump_val(out, &val->array.vals[i],
-					   indent + 1);
-			}
-			break;
-		case NVT_BLOB:
-			fprintf(out, " size=%zu\n", val->blob.size);
-			break;
-		case NVT_BOOL:
-			fprintf(out, "\n");
-			doindent(out, indent);
-			fprintf(out, "value=%s\n", val->b ? "true" : "false");
-			break;
-		case NVT_INT:
-			fprintf(out, "\n");
-			doindent(out, indent);
-			fprintf(out, "value=%"PRIu64"\n", val->i);
-			break;
-		case NVT_NULL:
-			fprintf(out, "\n");
-			break;
-		case NVT_NVL:
-			fprintf(out, "\n");
-			__dump_nvl(out, val->nvl, indent);
-			break;
-		case NVT_STR:
-			fprintf(out, "\n");
-			doindent(out, indent);
-			fprintf(out, "value='%s'\n", str_cstr(val->str));
-			break;
-	}
-}
-
-static void __dump_nvl(FILE *out, struct nvlist *nvl, int indent)
-{
-	const struct nvpair *pair;
-
-	nvl_for_each(pair, nvl) {
-		doindent(out, indent);
-		fprintf(out, "name='%s'", pair->name);
-		__dump_val(out, &pair->value, indent + 1);
-	}
-}
-
-void nvl_dump_file(FILE *out, struct nvlist *nvl)
-{
-	fprintf(out, "nvlist dump @ %p\n", nvl);
-	__dump_nvl(out, nvl, 1);
-}
--- a/nvl_fmt_cbor.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl_fmt_cbor.c	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -39,13 +39,13 @@
 	return cbor_pack_map_end(buffer, CBOR_UNKNOWN_NELEM);
 }
 
-static int cbor_array_prologue(struct buffer *buffer, const struct nvval *vals,
+static int cbor_array_prologue(struct buffer *buffer, struct val *const *vals,
 			       size_t nelem)
 {
 	return cbor_pack_array_start(buffer, nelem);
 }
 
-static int cbor_array_epilogue(struct buffer *buffer, const struct nvval *vals,
+static int cbor_array_epilogue(struct buffer *buffer, struct val *const *vals,
 			       size_t nelem)
 {
 	return cbor_pack_array_end(buffer, nelem);
--- a/nvl_fmt_json.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl_fmt_json.c	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -44,18 +44,18 @@
 	return buffer_append_c(buffer, '}');
 }
 
-static int json_array_prologue(struct buffer *buffer, const struct nvval *vals,
+static int json_array_prologue(struct buffer *buffer, struct val *const *vals,
 			       size_t nelem)
 {
 	return buffer_append_c(buffer, '[');
 }
 
-static int json_array_val_sep(struct buffer *buffer, const struct nvval *val)
+static int json_array_val_sep(struct buffer *buffer, const struct val *val)
 {
 	return buffer_append_c(buffer, ',');
 }
 
-static int json_array_epilogue(struct buffer *buffer, const struct nvval *vals,
+static int json_array_epilogue(struct buffer *buffer, struct val *const *vals,
 			       size_t nelem)
 {
 	return buffer_append_c(buffer, ']');
--- a/nvl_impl.h	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl_impl.h	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -80,10 +80,10 @@
 	 * Required: At least one of prologue or epilogue.
 	 * Optional: The rest.
 	 */
-	int (*array_prologue)(struct buffer *buffer, const struct nvval *vals,
+	int (*array_prologue)(struct buffer *buffer, struct val *const *vals,
 			      size_t nelem);
-	int (*array_val_sep)(struct buffer *buffer, const struct nvval *val);
-	int (*array_epilogue)(struct buffer *buffer, const struct nvval *vals,
+	int (*array_val_sep)(struct buffer *buffer, const struct val *val);
+	int (*array_epilogue)(struct buffer *buffer, struct val *const *vals,
 			      size_t nelem);
 
 	/*
--- a/nvl_pack.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/nvl_pack.c	Sat Mar 31 17:34:16 2018 -0400
@@ -28,10 +28,10 @@
 static int pack_nvl(const struct nvpackops *ops, struct buffer *buffer,
 		    struct nvlist *nvl);
 static int pack_val(const struct nvpackops *ops, struct buffer *buffer,
-		    const struct nvval *val);
+		    struct val *val);
 
 static int pack_array(const struct nvpackops *ops, struct buffer *buffer,
-		      const struct nvval *vals, size_t nelem)
+		      struct val **vals, size_t nelem)
 {
 	bool first = true;
 	size_t i;
@@ -44,7 +44,7 @@
 		return ret;
 
 	for (i = 0; i < nelem; i++) {
-		const struct nvval *val = &vals[i];
+		struct val *val = vals[i];
 
 		if (first) {
 			first = false;
@@ -85,51 +85,54 @@
 	return CALL_OR_FAIL(ops, val_null, (buffer));
 }
 
-static int pack_cstring(const struct nvpackops *ops, struct buffer *buffer,
-			const char *str)
-{
-	return CALL_OR_FAIL(ops, val_str, (buffer, str));
-}
-
 static int pack_string(const struct nvpackops *ops, struct buffer *buffer,
 		       struct str *str)
 {
+	const char *s;
+
 	/*
 	 * Even though we try to avoid NULL pointers to indicate empty
 	 * strings, they can crop up from many places.  So, it is safer to
 	 * do the check here.
 	 */
-	return pack_cstring(ops, buffer, str ? str_cstr(str) : "");
+	s = str ? str_cstr(str) : "";
+
+	return CALL_OR_FAIL(ops, val_str, (buffer, s));
 }
 
 static int pack_val(const struct nvpackops *ops, struct buffer *buffer,
-		    const struct nvval *val)
+		    struct val *val)
 {
 	int ret = -ENOTSUP;
 
 	switch (val->type) {
-		case NVT_ARRAY:
+		case VT_ARRAY:
 			ret = pack_array(ops, buffer, val->array.vals,
 					 val->array.nelem);
 			break;
-		case NVT_BLOB:
+		case VT_BLOB:
 			ret = pack_blob(ops, buffer, val->blob.ptr,
 					val->blob.size);
 			break;
-		case NVT_BOOL:
+		case VT_BOOL:
 			ret = pack_bool(ops, buffer, val->b);
 			break;
-		case NVT_INT:
+		case VT_INT:
 			ret = pack_int(ops, buffer, val->i);
 			break;
-		case NVT_NULL:
+		case VT_NULL:
 			ret = pack_null(ops, buffer);
 			break;
-		case NVT_NVL:
-			ret = pack_nvl(ops, buffer, val->nvl);
+		case VT_NVL:
+			ret = pack_nvl(ops, buffer, val_cast_to_nvl(val));
 			break;
-		case NVT_STR:
-			ret = pack_string(ops, buffer, val->str);
+		case VT_STR:
+			ret = pack_string(ops, buffer, val_cast_to_str(val));
+			break;
+		case VT_SYM:
+		case VT_CONS:
+		case VT_CHAR:
+			/* not supported */
 			break;
 	}
 
@@ -144,13 +147,13 @@
 	if ((ret = CALL(ops, pair_prologue, (buffer, pair))))
 		return ret;
 
-	if ((ret = pack_cstring(ops, buffer, pair->name)))
+	if ((ret = pack_string(ops, buffer, pair->name)))
 		return ret;
 
 	if ((ret = CALL(ops, nvl_name_sep, (buffer, pair))))
 		return ret;
 
-	if ((ret = pack_val(ops, buffer, &pair->value)))
+	if ((ret = pack_val(ops, buffer, pair->value)))
 		return ret;
 
 	if ((ret = CALL(ops, pair_epilogue, (buffer, pair))))
--- a/scgisvc.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/scgisvc.c	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2014-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2014-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -150,10 +150,10 @@
  */
 
 static const struct nvl_convert_info scgi_convert_headers[] = {
-	{ .name = "SCGI",		.tgt_type = NVT_INT, },
-	{ .name = SCGI_CONTENT_LENGTH,	.tgt_type = NVT_INT, },
-	{ .name = SCGI_REMOTE_PORT,	.tgt_type = NVT_INT, },
-	{ .name = SCGI_SERVER_PORT,	.tgt_type = NVT_INT, },
+	{ .name = "SCGI",		.tgt_type = VT_INT, },
+	{ .name = SCGI_CONTENT_LENGTH,	.tgt_type = VT_INT, },
+	{ .name = SCGI_REMOTE_PORT,	.tgt_type = VT_INT, },
+	{ .name = SCGI_SERVER_PORT,	.tgt_type = VT_INT, },
 	{ .name = NULL, },
 };
 
--- a/sexpr.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/sexpr.c	Sat Mar 31 17:34:16 2018 -0400
@@ -343,6 +343,33 @@
 
 			goto out;
 		}
+		case VT_NVL: {
+			struct bst_tree *ltree = &lhs->_set_nvl.values;
+			struct bst_tree *rtree = &rhs->_set_nvl.values;
+			struct nvpair *lcur;
+			struct nvpair *rcur;
+
+			lcur = bst_first(ltree);
+			rcur = bst_first(rtree);
+
+			while (lcur && rcur) {
+				ret = (str_cmp(lcur->name, rcur->name) == 0);
+				if (!ret)
+					goto out;
+
+				ret = sexpr_equal(val_getref(lcur->value),
+						  val_getref(rcur->value));
+				if (!ret)
+					goto out;
+
+				lcur = bst_next(ltree, lcur);
+				rcur = bst_next(rtree, rcur);
+			}
+
+			/* if both sides reached the end, then they are equal */
+			ret = !lcur && !rcur;
+			goto out;
+		}
 	}
 
 	panic("unknown struct val type %u", lhs->type);
--- a/sexpr_dump.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/sexpr_dump.c	Sat Mar 31 17:34:16 2018 -0400
@@ -137,6 +137,7 @@
 			panic("%s: VT_CONS is not an atom", __func__);
 		case VT_BLOB:
 		case VT_ARRAY:
+		case VT_NVL:
 			return ERR_PTR(-ENOTSUP);
 	}
 
@@ -258,6 +259,7 @@
 		case VT_INT:
 		case VT_BLOB:
 		case VT_ARRAY:
+		case VT_NVL:
 			return dump_atom(lv);
 		case VT_CONS:
 			if (raw)
--- a/sexpr_eval.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/sexpr_eval.c	Sat Mar 31 17:34:16 2018 -0400
@@ -198,6 +198,8 @@
 			panic("function name cannot be a VT_BLOB");
 		case VT_ARRAY:
 			panic("function name cannot be a VT_ARRAY");
+		case VT_NVL:
+			panic("function name cannot be a VT_NVL");
 		case VT_SYM:
 			break; /* ok */
 	}
@@ -252,6 +254,7 @@
 		case VT_CHAR:
 		case VT_BLOB:
 		case VT_ARRAY:
+		case VT_NVL:
 			return expr;
 		case VT_SYM:
 			if (!env->symlookup)
--- a/tests/test_cbor_pack.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/tests/test_cbor_pack.c	Sat Mar 31 17:34:16 2018 -0400
@@ -91,24 +91,36 @@
 	if (input->type != VT_CONS)
 		return input;
 
-	len = sexpr_length(val_getref(input));
-	if (len < 0)
-		fail("failed to get length of array");
+	/*
+	 * We are dealing with either a list or an assoc, we need to figure
+	 * out which it is...
+	 * FIXME
+	 */
 
-	arr = mem_reallocarray(NULL, len, sizeof(struct val *));
-	if (!arr)
-		fail("failed to allocate val array");
+	if (0) {
+		/* it is an assoc; turn it into a VT_NVL */
+		fail("not yet implemented");
+	} else {
+		/* it is a list; turn it into a VT_ARRAY */
+		len = sexpr_length(val_getref(input));
+		if (len < 0)
+			fail("failed to get length of array");
 
-	ret = sexpr_list_to_array(input, arr, len);
-	if (ret < 0)
-		fail("failed to construct an array");
+		arr = mem_reallocarray(NULL, len, sizeof(struct val *));
+		if (!arr)
+			fail("failed to allocate val array");
+
+		ret = sexpr_list_to_array(input, arr, len);
+		if (ret < 0)
+			fail("failed to construct an array");
 
-	for (i = 0; i < len; i++)
-		arr[i] = convert_input(arr[i]);
+		for (i = 0; i < len; i++)
+			arr[i] = convert_input(arr[i]);
 
-	val_putref(input);
+		val_putref(input);
 
-	return VAL_ALLOC_ARRAY(arr, len);
+		return VAL_ALLOC_ARRAY(arr, len);
+	}
 }
 
 static void onefile(struct val *input, struct buffer *expected)
@@ -122,7 +134,7 @@
 	if (IS_ERR(got))
 		fail("failed to allocate output buffer");
 
-	/* possibly an VT_ARRAY in sexpr list form */
+	/* possibly an VT_ARRAY or VT_NVL in sexpr list form */
 	if (input->type == VT_CONS)
 		input = convert_input(input);
 
@@ -150,6 +162,10 @@
 						      input->array.nelem),
 				 got, expected, input);
 			break;
+		case VT_NVL:
+			TEST_ONE(cbor_pack_map_val(got, input), got,
+				 expected, input);
+			break;
 		case VT_SYM:
 		case VT_CONS:
 		case VT_CHAR:
--- a/tests/test_nvl.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/tests/test_nvl.c	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -96,7 +96,7 @@
 static void check_key_not_exists(struct nvlist *nvl, const char *key)
 {
 	const struct nvpair *pair;
-	const struct nvval *vals;
+	struct val **vals;
 	struct nvlist *cnvl;
 	size_t nelem, size;
 	const void *ptr;
@@ -134,10 +134,10 @@
 }
 
 static void check_key_exists(struct nvlist *nvl, const char *key,
-			     enum nvtype type)
+			     enum val_type type)
 {
 	const struct nvpair *pair;
-	const struct nvval *vals;
+	struct val **vals;
 	struct nvlist *cnvl;
 	size_t nelem, size;
 	const void *ptr;
@@ -150,36 +150,36 @@
 	__check_lookup_err(IS_ERR(pair), false, PTR_ERR(pair), 0, "nvl_lookup",
 			   key);
 
-	if (pair->value.type != type)
+	if (pair->value->type != type)
 		fail("nvl_lookup(..., '%s') returned wrong type; got %u, "
-		     "expected %u", key, pair->value.type, type);
+		     "expected %u", key, pair->value->type, type);
 
 	ret = nvl_lookup_array(nvl, key, &vals, &nelem);
-	__check_lookup_err(!!ret, type != NVT_ARRAY, ret, -ERANGE,
+	__check_lookup_err(!!ret, type != VT_ARRAY, ret, -ERANGE,
 			   "nvl_lookup_array", key);
 
 	ret = nvl_lookup_blob(nvl, key, &ptr, &size);
-	__check_lookup_err(!!ret, type != NVT_BLOB, ret, -ERANGE,
+	__check_lookup_err(!!ret, type != VT_BLOB, ret, -ERANGE,
 			   "nvl_lookup_blob", key);
 
 	ret = nvl_lookup_bool(nvl, key, &bool_val);
-	__check_lookup_err(!!ret, type != NVT_BOOL, ret, -ERANGE,
+	__check_lookup_err(!!ret, type != VT_BOOL, ret, -ERANGE,
 			   "nvl_lookup_bool", key);
 
 	ret = nvl_lookup_int(nvl, key, &int_val);
-	__check_lookup_err(!!ret, type != NVT_INT, ret, -ERANGE,
+	__check_lookup_err(!!ret, type != VT_INT, ret, -ERANGE,
 			   "nvl_lookup_int", key);
 
 	ret = nvl_lookup_null(nvl, key);
-	__check_lookup_err(!!ret, type != NVT_NULL, ret, -ERANGE,
+	__check_lookup_err(!!ret, type != VT_NULL, ret, -ERANGE,
 			   "nvl_lookup_null", key);
 
 	cnvl = nvl_lookup_nvl(nvl, key);
-	__check_lookup_err(IS_ERR(cnvl), type != NVT_NVL, PTR_ERR(cnvl),
+	__check_lookup_err(IS_ERR(cnvl), type != VT_NVL, PTR_ERR(cnvl),
 			   -ERANGE, "nvl_lookup_nvl", key);
 
 	str = nvl_lookup_str(nvl, key);
-	__check_lookup_err(IS_ERR(str), type != NVT_STR, PTR_ERR(str),
+	__check_lookup_err(IS_ERR(str), type != VT_STR, PTR_ERR(str),
 			   -ERANGE, "nvl_lookup_str", key);
 }
 
@@ -259,20 +259,20 @@
 	set_int(nvl, "abc", 1);
 
 	check_key_not_exists(nvl, "non-existent");
-	check_key_exists(nvl, "abc", NVT_INT);
+	check_key_exists(nvl, "abc", VT_INT);
 
 	set_bool(nvl, "def", true);
 
 	check_key_not_exists(nvl, "non-existent");
-	check_key_exists(nvl, "abc", NVT_INT);
-	check_key_exists(nvl, "def", NVT_BOOL);
+	check_key_exists(nvl, "abc", VT_INT);
+	check_key_exists(nvl, "def", VT_BOOL);
 
 	set_null(nvl, "ghi");
 
 	check_key_not_exists(nvl, "non-existent");
-	check_key_exists(nvl, "abc", NVT_INT);
-	check_key_exists(nvl, "def", NVT_BOOL);
-	check_key_exists(nvl, "ghi", NVT_NULL);
+	check_key_exists(nvl, "abc", VT_INT);
+	check_key_exists(nvl, "def", VT_BOOL);
+	check_key_exists(nvl, "ghi", VT_NULL);
 
 	nvl_putref(nvl);
 
@@ -295,9 +295,9 @@
 		if ((mask & bit) == 0)
 			check_key_not_exists(nvl, name);
 		else if (imask & bit)
-			check_key_exists(nvl, name, NVT_INT);
+			check_key_exists(nvl, name, VT_INT);
 		else if (bmask & bit)
-			check_key_exists(nvl, name, NVT_BOOL);
+			check_key_exists(nvl, name, VT_BOOL);
 	}
 }
 
--- a/tests/test_nvl_pack.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/tests/test_nvl_pack.c	Sat Mar 31 17:34:16 2018 -0400
@@ -260,11 +260,13 @@
 					break;
 				case VT_BLOB:
 				case VT_ARRAY:
+				case VT_NVL:
 					/*
 					 * We couldn't have possibly read
 					 * this from the input sexpr!
 					 */
-					fail("sexprs don't support blobs/arrays");
+					fail("sexprs don't support "
+					     "blobs/arrays/nvlists");
 					break;
 				case VT_BOOL:
 					set_bool(nvl, var, op[2]->b, 0);
--- a/tests/test_qstring.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/tests/test_qstring.c	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2014-2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2014-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -37,12 +37,14 @@
 		return -ENOMEM;
 
 	ret = qstring_parse_len(vars, ibuf, len);
+#if 0
 	if (!ret)
 		nvl_dump_file(stderr, vars);
+#endif
 
 	nvl_putref(vars);
 
-	return 0;
+	return ret;
 }
 
 static void test(const char *fname)
--- a/val.c	Sat Mar 31 19:05:41 2018 -0400
+++ b/val.c	Sat Mar 31 17:34:16 2018 -0400
@@ -28,6 +28,7 @@
 #include <ctype.h>
 #include <inttypes.h>
 
+#include <jeffpc/val.h>
 #include <jeffpc/jeffpc.h>
 #include <jeffpc/error.h>
 #include <jeffpc/types.h>
@@ -117,6 +118,9 @@
 				free(val->_set_array.vals);
 			break;
 		}
+		case VT_NVL:
+			__val_free_nvl(val);
+			break;
 	}
 
 	mem_cache_free(val_cache, val);
@@ -309,6 +313,10 @@
 					      indent + 2);
 			break;
 		}
+		case VT_NVL:
+			/* TODO: dump the contents of the pairs */
+			fprintf(out, "%*snvlist\n", indent, "");
+			break;
 		default:
 			fprintf(out, "Unknown type %d\n", val->type);
 			break;
--- a/val_impl.h	Sat Mar 31 19:05:41 2018 -0400
+++ b/val_impl.h	Sat Mar 31 17:34:16 2018 -0400
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2017 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ * Copyright (c) 2017-2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
@@ -24,8 +24,13 @@
 #define __VAL_IMPL_H
 
 #include <jeffpc/val.h>
+#include <jeffpc/nvl.h>
 
 extern struct val *__val_alloc(enum val_type type);
+extern void __val_free_nvl(struct val *val);
+
+extern struct nvpair *__nvpair_alloc(const char *name);
+extern void __nvpair_free(struct nvpair *pair);
 
 static inline bool val_is_null_cons(struct val *v)
 {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/val_nvl.c	Sat Mar 31 17:34:16 2018 -0400
@@ -0,0 +1,107 @@
+/*
+ * Copyright (c) 2018 Josef 'Jeff' Sipek <jeffpc@josefsipek.net>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include <jeffpc/mem.h>
+
+#include "val_impl.h"
+
+static struct mem_cache *nvpair_cache;
+
+static void __attribute__((constructor)) init_val_subsys(void)
+{
+	nvpair_cache = mem_cache_create("nvpair-cache", sizeof(struct nvpair),
+					0);
+	ASSERT(!IS_ERR(nvpair_cache));
+}
+
+struct nvpair *__nvpair_alloc(const char *name)
+{
+	struct nvpair *pair;
+
+	pair = mem_cache_alloc(nvpair_cache);
+	if (!pair)
+		return NULL;
+
+	pair->name = str_dup(name);
+	if (IS_ERR(pair->name)) {
+		mem_cache_free(nvpair_cache, pair);
+		return NULL;
+	}
+
+	/*
+	 * Avoid returning with a NULL pointer.  Of all the types, VT_NULL
+	 * is the least out of place.
+	 *
+	 * (We use VAL_ALLOC_NULL here to make it painfully clear that
+	 * ->value is valid later on, even though we could have used
+	 *  val_alloc_null directly as it never fails.)
+	 */
+	pair->value = VAL_ALLOC_NULL();
+
+	return pair;
+}
+
+void __nvpair_free(struct nvpair *pair)
+{
+	str_putref(pair->name);
+	val_putref(pair->value);
+
+	mem_cache_free(nvpair_cache, pair);
+}
+
+static int val_nvl_cmp(const void *va, const void *vb)
+{
+	const struct nvpair *a = va;
+	const struct nvpair *b = vb;
+
+	return str_cmp(a->name, b->name);
+}
+
+struct val *val_alloc_nvl(void)
+{
+	struct val *val;
+
+	val = __val_alloc(VT_NVL);
+	if (IS_ERR(val))
+		return val;
+
+	bst_create(&val->_set_nvl.values, val_nvl_cmp, sizeof(struct nvpair),
+		   offsetof(struct nvpair, node));
+
+	return val;
+}
+
+void __val_free_nvl(struct val *val)
+{
+	struct bst_cookie cookie;
+	struct nvpair *cur;
+
+	ASSERT(val);
+	ASSERT3U(refcnt_read(&val->refcnt), ==, 0);
+	ASSERT3U(val->type, ==, VT_NVL);
+
+	memset(&cookie, 0, sizeof(struct bst_cookie));
+	while ((cur = bst_destroy_nodes(&val->_set_nvl.values, &cookie)))
+		__nvpair_free(cur);
+
+	bst_destroy(&val->_set_nvl.values);
+}