shithub: qk1

Download patch

ref: 0667b932941239bd7a561e4ff17e1f1307ab9acb
parent: 6405b2a349f9ceb8b8678c81535e72843b848b6e
author: Sigrid Solveig Haflínudóttir <sigrid@ftrv.se>
date: Sun Jan 12 19:17:17 EST 2025 

qp: replace with 5-bit qp tries (more portable)


--- a/cmd.c
+++ b/cmd.c
@@ -222,7 +222,7 @@
 }
 
 static void
-Cmd_AliasList(char *name, void *v, void *aux)
+Cmd_AliasList(const char *name, void *v, void *aux)
 {
 	cmd_t *a;
 
--- a/console.c
+++ b/console.c
@@ -1,5 +1,5 @@
 #include "quakedef.h"
-#include "qp.h"
+#include "tbl.h"
 
 static int con_linewidth;
 
@@ -36,31 +36,26 @@
 
 extern void M_Menu_Main_f (cmd_t *c);
 
-static Trie *conobj;
+static Tbl *conobj;
 
 void
 Con_AddObject(char *name, void *obj)
 {
-	conobj = qpset(conobj, name, 0, obj);
+	conobj = Tset(conobj, name, obj);
 }
 
 void *
 Con_FindObject(char *name)
 {
-	char *k;
-	void *v;
-
-	if(qpget(conobj, name, 0, &k, &v) != 0)
-		v = nil;
-	return v;
+	return Tget(conobj, name);
 }
 
 int
-Con_SearchObject(char *prefix, int len0, void (*f)(char *name, void *obj, void *aux), void *aux)
+Con_SearchObject(const char *prefix, int len0, void (*f)(const char *name, void *obj, void *aux), void *aux)
 {
-	char *k;
+	const char *k;
 	void *v;
-	int n, len, c;
+	int n, c, len;
 
 	if(conobj == nil)
 		return 0;
@@ -69,7 +64,7 @@
 	v = nil;
 	len = 0;
 	for(n = 0;;){
-		if(qpnext(conobj, &k, &len, &v) < 0)
+		if(!Tnextl(conobj, &k, &len, &v))
 			break;
 		c = -1;
 		if(len0 == 0 || (len >= len0 && (c = strncmp(k, prefix, len0)) == 0)){
@@ -259,9 +254,9 @@
 static void
 Con_Print(char *txt)
 {
+	static bool cr;
 	int		y;
 	int		c, l;
-	static int	cr;
 	int		mask;
 
 	con_backscroll = 0;
@@ -312,13 +307,10 @@
 
 		switch (c)
 		{
+		case '\r':
+			cr = true;
 		case '\n':
 			con_x = 0;
-			break;
-
-		case '\r':
-			con_x = 0;
-			cr = 1;
 			break;
 
 		default:	// display character and advance
--- a/console.h
+++ b/console.h
@@ -24,4 +24,4 @@
 
 void Con_AddObject(char *name, void *obj);
 void *Con_FindObject(char *name);
-int Con_SearchObject(char *prefix, int len, void (*f)(char *, void *, void *), void *aux);
+int Con_SearchObject(const char *prefix, int len, void (*f)(const char *, void *, void *), void *aux);
--- /dev/null
+++ b/fn.c
@@ -1,0 +1,205 @@
+// fn.c: quintet bit popcount patricia tries, new version
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#include "platform.h"
+#include "tbl.h"
+#include "fn.h"
+
+bool
+Tgetkv(Tbl *t, const char *key, int len, const char **pkey, void **pval)
+{
+	if(t == nil)
+		return false;
+	while(isbranch(t)){
+		Tindex i = t->index;
+		Tbitmap b = twigbit(i, key, len);
+		if(!hastwig(i, b))
+			return false;
+		t = Tbranch_twigs(t) + twigoff(i, b);
+	}
+	if(strcmp(key, Tleaf_key(t)) != 0)
+		return false;
+	*pkey = Tleaf_key(t);
+	*pval = Tleaf_val(t);
+	return true;
+}
+
+static bool
+next_rec(Trie *t, const char **pkey, int *plen, void **pval)
+{
+	Tindex i = t->index;
+	if(Tindex_branch(i)){
+		// Recurse to find either this leaf (*pkey != nil)
+		// or the next one (*pkey == nil).
+		Tbitmap b = twigbit(i, *pkey, *plen);
+		u32int s, m; TWIGOFFMAX(s, m, i, b);
+		for(; s < m; s++){
+			if(next_rec(Tbranch_twigs(t)+s, pkey, plen, pval))
+				return true;
+		}
+		return false;
+	}
+	// We have found the next leaf.
+	if(*pkey == nil){
+		*pkey = Tleaf_key(t);
+		*plen = strlen(*pkey);
+		*pval = Tleaf_val(t);
+		return true;
+	}
+	// We have found this leaf, so start looking for the next one.
+	if(strcmp(*pkey, Tleaf_key(t)) == 0){
+		*pkey = nil;
+		*plen = 0;
+		return false;
+	}
+	// No match.
+	return false;
+}
+
+bool
+Tnextl(Tbl *tbl, const char **pkey, int *plen, void **pval)
+{
+	if(tbl == nil){
+		*pkey = nil;
+		*plen = 0;
+		return false;
+	}
+	return next_rec(tbl, pkey, plen, pval);
+}
+
+Tbl *
+Tdelkv(Tbl *tbl, const char *key, int len, const char **pkey, void **pval)
+{
+	if(tbl == nil)
+		return nil;
+	Trie *t = tbl, *p = nil;
+	Tindex i = 0;
+	Tbitmap b = 0;
+	while(isbranch(t)){
+		i = t->index;
+		b = twigbit(i, key, len);
+		if(!hastwig(i, b))
+			return tbl;
+		p = t; t = Tbranch_twigs(t) + twigoff(i, b);
+	}
+	if(strcmp(key, Tleaf_key(t)) != 0)
+		return tbl;
+	*pkey = Tleaf_key(t);
+	*pval = Tleaf_val(t);
+	if(p == nil){
+		free(tbl);
+		return nil;
+	}
+	Trie *twigs = Tbranch_twigs(p);
+	u32int m = __builtin_popcount(Tindex_bitmap(i));
+	assert(twigs <= t && t < twigs+m);
+	if(m == 2){
+		// Move the other twig to the parent branch.
+		*p = twigs[twigs == t];
+		free(twigs);
+		return tbl;
+	}
+	memmove(t, t+1, ((twigs + m) - (t + 1)) * sizeof(Trie));
+	p->index = Tbitmap_del(i, b);
+	// We have now correctly removed the twig from the trie, so if
+	// realloc() fails we can ignore it and continue to use the
+	// slightly oversized twig array.
+	twigs = realloc(twigs, sizeof(Trie) * (m - 1));
+	if(twigs != nil)
+		Tset_twigs(p, twigs);
+	return tbl;
+}
+
+Tbl *
+Tsetl(Tbl *tbl, const char *key, int len, void *val)
+{
+	assert(!Tindex_branch((Tindex)(uintptr)val) && len <= (int)Tmaxlen);
+	if(val == nil)
+		return Tdell(tbl, key, len);
+	// First leaf in an empty tbl?
+	if(tbl == nil){
+		tbl = malloc(sizeof(*tbl));
+		if(tbl == nil)
+			return nil;
+		Tset_key(tbl, key);
+		Tset_val(tbl, val);
+		return tbl;
+	}
+	Trie *t = tbl;
+	// Find the most similar leaf node in the trie. We will compare
+	// its key with our new key to find the first differing nibble,
+	// which can be at a lower index than the point at which we
+	// detect a difference.
+	while(isbranch(t)){
+		Tindex i = t->index;
+		Tbitmap b = twigbit(i, key, len);
+		// Even if our key is missing from this branch we need to
+		// keep iterating down to a leaf. It doesn't matter which
+		// twig we choose since the keys are all the same up to this
+		// index. Note that blindly using twigoff(t, b) can cause
+		// an out-of-bounds index if it equals twigmax(t).
+		u32int s = hastwig(i, b) ? twigoff(i, b) : 0;
+		t = Tbranch_twigs(t) + s;
+	}
+	// Do the keys differ, and if so, where?
+	u32int off, xor, shf;
+	const char *tkey = Tleaf_key(t);
+	for(off = 0; off <= (u32int)len; off++){
+		xor = (u8int)key[off] ^ (u8int)tkey[off];
+		if(xor != 0)
+			goto newkey;
+	}
+	Tset_val(t, val);
+	return tbl;
+newkey:; // We have the branch's byte index; what is its chunk index?
+	u32int bit = off * 8 + qclz(xor) + 8 - sizeof(u32int) * 8;
+	u32int qo = bit / 5;
+	off = qo * 5 / 8;
+	shf = qo * 5 % 8;
+	// re-index keys with adjusted offset
+	Tbitmap nb = 1U << knybble(key,off,shf);
+	Tbitmap tb = 1U << knybble(tkey,off,shf);
+	// Prepare the new leaf.
+	Trie nt;
+	Tset_key(&nt, key);
+	Tset_val(&nt, val);
+	// Find where to insert a branch or grow an existing branch.
+	t = tbl;
+	Tindex i;
+	while(isbranch(t)){
+		i = t->index;
+		if(off == Tindex_offset(i) && shf == Tindex_shift(i))
+			goto growbranch;
+		if(off == Tindex_offset(i) && shf < Tindex_shift(i))
+			goto newbranch;
+		if(off < Tindex_offset(i))
+			goto newbranch;
+		Tbitmap b = twigbit(i, key, len);
+		assert(hastwig(i, b));
+		t = Tbranch_twigs(t) + twigoff(i, b);
+	}
+newbranch:;
+	Trie *twigs = malloc(sizeof(Trie) * 2);
+	if(twigs == nil)
+		return nil;
+	i = Tindex_new(shf, off, nb | tb);
+	twigs[twigoff(i, nb)] = nt;
+	twigs[twigoff(i, tb)] = *t;
+	Tset_twigs(t, twigs);
+	Tset_index(t, i);
+	return tbl;
+growbranch:
+	assert(!hastwig(i, nb));
+	u32int s, m; TWIGOFFMAX(s, m, i, nb);
+	twigs = realloc(Tbranch_twigs(t), sizeof(Trie) * (m + 1));
+	if(twigs == nil)
+		return nil;
+	memmove(twigs+s+1, twigs+s, sizeof(Trie) * (m - s));
+	memmove(twigs+s, &nt, sizeof(Trie));
+	Tset_twigs(t, twigs);
+	Tset_index(t, Tbitmap_add(i, nb));
+	return tbl;
+}
--- /dev/null
+++ b/fn.h
@@ -1,0 +1,200 @@
+// fn.h: quintet bit popcount patricia tries, new version
+//
+// This version uses somewhat different terminology than older
+// variants. The location of a quintet in the key is now called its
+// "offset", and the whole word containing the offset, bitmap, and tag
+// bit is called the "index word" (by analogy with a database index).
+// The precise quintet location is represented as a byte offset and a
+// shift. Previously a flags field contained the isbranch tag and shift,
+// but these are now separate.
+//
+// Instead of trying to use bit fields, this code uses accessor
+// functions to split up a pair of words into their constituent parts.
+// This should improve portability to machines with varying endianness
+// and/or word size.
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#pragma once
+
+typedef u32int Tbitmap;
+typedef u64int Tindex;
+
+#ifdef __plan9__
+static inline u32int
+__builtin_popcount(Tbitmap w)
+{
+	w -= (w >> 1) & 0x55555555U;
+	w = (w & 0x33333333U) + ((w >> 2) & 0x33333333U);
+	w = (w + (w >> 4)) & 0x0F0F0F0FU;
+	w = (w * 0x01010101U) >> 24;
+	return w;
+}
+#endif
+
+typedef struct Tbl {
+	Tindex index;
+	void *ptr;
+}Trie;
+
+// accessor functions, except for the index word
+
+#define Tset_field(cast, elem, type, field) \
+	static inline void \
+	Tset_##field(Trie *t, type field) \
+	{ \
+		t->elem = cast field; \
+	} \
+	struct dummy
+
+Tset_field((void *),          ptr,   Trie *,       twigs);
+Tset_field((Tindex),          index, Tindex,       index);
+Tset_field((void *)(uintptr), ptr,   const char *, key);
+Tset_field((Tindex)(uintptr), index, void *,       val);
+
+static inline bool Tindex_branch(Tindex i);
+
+static inline bool isbranch(Trie *t)
+{
+	return Tindex_branch(t->index);
+}
+
+#define Tbranch(t) assert(isbranch(t))
+#define Tleaf(t)  assert(!isbranch(t))
+
+#define Tcheck_get(type, tag, field, expr) \
+	static inline type \
+	tag##_##field(Trie *t) \
+	{ \
+		tag(t); \
+		return expr; \
+	} \
+	struct dummy
+
+Tcheck_get(Trie *,       Tbranch, twigs, t->ptr);
+Tcheck_get(const char *, Tleaf,   key,   t->ptr);
+Tcheck_get(void *,       Tleaf,   val,   (void*)(uintptr)t->index);
+
+// index word layout
+
+#define Tix_width_branch 1
+#define Tix_width_shift  3
+#define Tix_width_offset 28
+#define Tix_width_bitmap 32
+
+#define Tix_base_branch 0
+#define Tix_base_shift  (Tix_base_branch + Tix_width_branch)
+#define Tix_base_offset (Tix_base_shift  + Tix_width_shift)
+#define Tix_base_bitmap (Tix_base_offset + Tix_width_offset)
+
+#define Tix_place(field) ((Tindex)(field) << Tix_base_##field)
+
+#define Tix_mask(field) ((1ULL << Tix_width_##field) - 1ULL)
+
+#define Tunmask(field,index) \
+	((u32int)(((index) >> Tix_base_##field) & Tix_mask(field)))
+
+#define Tmaxlen Tix_mask(offset)
+
+// index word accessor functions
+
+#define Tindex_get(type, field) \
+	static inline type \
+	Tindex_##field(Tindex i) \
+	{ \
+		return Tunmask(field, i); \
+	} \
+	struct dummy
+
+Tindex_get(bool, branch);
+Tindex_get(u32int, shift);
+Tindex_get(u32int, offset);
+Tindex_get(Tbitmap, bitmap);
+
+static inline Tindex
+Tindex_new(u32int shift, u32int offset, Tbitmap bitmap)
+{
+	u32int branch = 1;
+	return
+		Tix_place(branch) |
+		Tix_place(shift)  |
+		Tix_place(offset) |
+		Tix_place(bitmap) ;
+}
+
+static inline Tindex
+Tbitmap_add(Tindex i, Tbitmap bitmap)
+{
+	return i | Tix_place(bitmap);
+}
+
+static inline Tindex
+Tbitmap_del(Tindex i, Tbitmap bitmap)
+{
+	return i & ~Tix_place(bitmap);
+}
+
+#if 0
+// sanity checks!
+static_assert(Tix_base_bitmap + Tix_width_bitmap == 64,
+	      "index fields must fill a 64 bit word");
+
+static_assert(Tunmask(bitmap,0x1234567800000000ULL) == 0x12345678,
+	      "extracting the bitmap works");
+
+static_assert(Tunmask(offset,0x0420ULL) == 0x42,
+	      "extracting the offset works");
+
+static_assert(Tunmask(shift,0xFEDCBAULL) == 5,
+	      "extracting the shift works");
+#endif
+
+//  ..key[o%5==0].. ..key[o%5==1].. ..key[o%5==2].. ..key[o%5==3].. ..key[o%5==4]..
+// |               |               |               |               |               |
+//  7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+// |         |         |         |         |         |         |         |         |
+//  shift=0   shift=5   shift=2   shift=7   shift=4   shift=1   shift=6   shift=3
+
+static inline u8int
+knybble(const char *key, u32int off, u32int shift)
+{
+	u32int word = (u8int)key[off]<<8;
+	if(word)
+		word |= key[off+1];
+	u32int right = 16 - 5 - shift;
+	return (word >> right) & 0x1FU;
+}
+
+static inline u8int
+nibble(Tindex i, const char *key, int len)
+{
+	u32int off = Tindex_offset(i);
+	if(off >= (u32int)len)
+		return 0;
+	return knybble(key, off, Tindex_shift(i));
+}
+
+static inline Tbitmap
+twigbit(Tindex i, const char *key, int len)
+{
+	return 1U << nibble(i, key, len);
+}
+
+static inline bool
+hastwig(Tindex i, Tbitmap bit)
+{
+	return Tindex_bitmap(i) & bit;
+}
+
+static inline u32int
+twigoff(Tindex i, Tbitmap bit)
+{
+	return __builtin_popcount(Tindex_bitmap(i) & (bit-1));
+}
+
+#define TWIGOFFMAX(off, max, i, b) do{ \
+		off = twigoff(i, b); \
+		max = __builtin_popcount(Tindex_bitmap(i)); \
+	}while(0)
--- a/fs.c
+++ b/fs.c
@@ -471,7 +471,7 @@
 }
 
 static void
-dumpcvar(char *name, void *o, void *bf)
+dumpcvar(const char *name, void *o, void *bf)
 {
 	cvar_t *c;
 
--- a/keys.c
+++ b/keys.c
@@ -129,7 +129,7 @@
 */
 
 static void
-Key_Complete(char *name, void *o, void *aux)
+Key_Complete(const char *name, void *o, void *aux)
 {
 	static int printed = 0;
 	int n;
--- a/meson.build
+++ b/meson.build
@@ -48,6 +48,7 @@
 	'd_surf.c',
 	'd_vars.c',
 	'draw.c',
+	'fn.c',
 	'fs.c',
 	'host.c',
 	'host_cmd.c',
@@ -73,7 +74,6 @@
 	'pr_edict.c',
 	'pr_exec.c',
 	'protocol.c',
-	'qp.c',
 	'r_aclip.c',
 	'r_alias.c',
 	'r_bsp.c',
@@ -96,6 +96,7 @@
 	'sv_move.c',
 	'sv_phys.c',
 	'sv_user.c',
+	'tbl.c',
 	'view.c',
 	'wav.c',
 	'world.c',
--- a/mkfile
+++ b/mkfile
@@ -31,6 +31,7 @@
 	d_surf.$O\
 	d_vars.$O\
 	draw.$O\
+	fn.$O\
 	fs.$O\
 	host.$O\
 	host_cmd.$O\
@@ -62,7 +63,6 @@
 	pr_edict.$O\
 	pr_exec.$O\
 	protocol.$O\
-	qp.$O\
 	r_aclip.$O\
 	r_alias.$O\
 	r_bsp.$O\
@@ -87,6 +87,7 @@
 	sv_phys.$O\
 	sv_user.$O\
 	sys_plan9.$O\
+	tbl.$O\
 	vid_plan9.$O\
 	view.$O\
 	wav.$O\
@@ -107,6 +108,7 @@
 	d_local.h\
 	dat.h\
 	draw.h\
+	fn.h\
 	fns.h\
 	i_tga.h\
 	i_wad.h\
@@ -122,7 +124,6 @@
 	progdefs.h\
 	progs.h\
 	protocol.h\
-	qp.h\
 	quakedef.h\
 	r_local.h\
 	r_shared.h\
@@ -132,6 +133,7 @@
 	server.h\
 	softfloat.h\
 	spritegn.h\
+	tbl.h\
 	vid.h\
 	view.h\
 	world.h\
@@ -147,3 +149,6 @@
 
 i_resize.$O: i_resize.c
 	$CC $CFLAGS -p i_resize.c
+
+fn.$O: fn.c
+	$CC $CFLAGS -p fn.c
--- a/plan9/platform.h
+++ b/plan9/platform.h
@@ -45,6 +45,7 @@
 static double ln2c;
 #define exp2f(x) (exp((x) * (ln2c ? ln2c : (ln2c = log(2.0)))))
 
+int qclz(unsigned);
 int qctz(unsigned);
 
 float DotProduct(const float v1[3], const float v2[3]);
--- a/posix/platform.h
+++ b/posix/platform.h
@@ -41,6 +41,7 @@
 #define setrealloctag(p, t) do{USED(p); USED(t);}while(0)
 #define isNaNf isnan
 
+#define qclz(x) __builtin_clz(x)
 #define qctz(x) __builtin_ctz(x)
 
 #ifdef HAVE_ENDIAN_H
--- a/qp.c
+++ /dev/null
@@ -1,230 +1,0 @@
-#include "quakedef.h"
-#include "qp.h"
-
-typedef u16int Tbitmap;
-typedef struct Tbranch Tbranch;
-typedef struct Tleaf Tleaf;
-
-struct Tleaf {
-	char *k;
-	void *v;
-};
-
-struct Tbranch {
-	Trie *twigs;
-	u64int x;
-};
-
-union Trie {
-	Tleaf leaf;
-	Tbranch branch;
-};
-
-#define x_flags(x) ((x)>>62)
-#define x_index(x) ((x)>>16 & ((1ULL<<46)-1ULL))
-#define x_bitmap(x) ((x) & 0xffff)
-
-#define isbranch(t) (x_flags((t)->branch.x) != 0)
-#define hastwig(t, b) (x_bitmap((t)->branch.x) & (b))
-#define twigoff(t, b) popcount(x_bitmap((t)->branch.x) & ((b)-1))
-#define twig(t, i) (&(t)->branch.twigs[(i)])
-#define twigoffmax(off, max, t, b) do{ off = twigoff(t, b); max = popcount(x_bitmap((t)->branch.x)); }while(0)
-#define nibbit(k, f) (1 << (((k) & (((f)-2) ^ 0x0f) & 0xff) >> ((2-(f))<<2)))
-#define twigbit(t, k, len) \
-	(x_index((t)->branch.x) >= (u64int)(len) ? \
-	1 : \
-	nibbit((u8int)(k)[x_index((t)->branch.x)], x_flags((t)->branch.x)))
-
-/*
-// need some speed? just say no.
-#define POPCNT	BYTE $0xf3; BYTE $0x0f; BYTE $0xb8
-
-TEXT popcount(SB),$0
-	MOVL b+0(FP), AX
-	POPCNT
-	RET
-*/
-static u16int
-popcount(u16int b)
-{
-	b -= b>>1 & 0x5555;
-	b = (b & 0x3333) + ((b>>2) & 0x3333);
-	b = (b + (b>>4)) & 0x0f0f;
-	b = (b + (b>>8)) & 0x00ff;
-	return b;
-}
-
-int
-qpget(Trie *t, char *k, int len, char **pk, void **pv)
-{
-	Tbitmap b;
-
-	assert(k != nil && pk != nil && pv != nil);
-
-	if(len < 1)
-		len = strlen(k);
-	if(t == nil)
-		return -1;
-	for(; isbranch(t); t = twig(t, twigoff(t, b))){
-		b = twigbit(t, k, len);
-		if(!hastwig(t, b))
-			return -1;
-	}
-	if(strncmp(k, t->leaf.k, len) != 0)
-		return -1;
-	*pk = t->leaf.k;
-	*pv = t->leaf.v;
-
-	return 0;
-}
-
-int
-qpnext(Trie *t, char **pk, int *plen, void **pv)
-{
-	Tbitmap b;
-	unsigned s, m;
-
-	assert(pk != nil && plen != nil && pv != nil);
-
-	if(isbranch(t)){
-		b = twigbit(t, *pk, *plen);
-		twigoffmax(s, m, t, b);
-		for(; s < m; s++){
-			if(qpnext(twig(t, s), pk, plen, pv) == 0)
-				return 0;
-		}
-		return -1;
-	}
-
-	if(*pk == nil){
-		*pk = t->leaf.k;
-		*plen = strlen(*pk);
-		*pv = t->leaf.v;
-		return 0;
-	}
-	if(*pk == t->leaf.k || strcmp(*pk, t->leaf.k) == 0){
-		*pk = nil;
-		*plen = 0;
-		*pv = nil;
-		return -1;
-	}
-
-	return -1;
-}
-
-Trie *
-qpdel(Trie *t, char *k, int len, char **pk, void **pv)
-{
-	Trie *p, *twigs;
-	Tbitmap b;
-	unsigned s, m;
-
-	if(t == nil)
-		return nil;
-	assert(k != nil && pk != nil && pv != nil);
-	if(len < 1)
-		len = strlen(k);
-	assert(len > 0);
-
-	for(b = 0, p = nil; isbranch(t); p = t, t = twig(t, twigoff(t, b))){
-		b = twigbit(t, k, len);
-		if(!hastwig(t, b))
-			return t;
-	}
-	
-	if(strncmp(k, t->leaf.k, len) != 0)
-		return t;
-	*pk = t->leaf.k;
-	*pv = t->leaf.v;
-
-	if(p == nil){
-		free(t);
-		return nil;
-	}
-	t = p;
-
-	twigoffmax(s, m, t, b);
-	if(m == 2){
-		twigs = t->branch.twigs;
-		*t = *twig(t, !s);
-		free(twigs);
-		return t;
-	}
-	memmove(t->branch.twigs+s, t->branch.twigs+s+1, sizeof(*t)*(m-s-1));
-	t->branch.x &= ~(u64int)b;
-
-	t->branch.twigs = realloc(t->branch.twigs, sizeof(*t)*(m-1));
-	return t;
-}
-
-Trie *
-qpset(Trie *t, char *k, int len, void *v)
-{
-	Trie *t0, t1, t2;
-	unsigned i, s, m;
-	u8int f;
-	Tbitmap b, b1, b2;
-	u8int k2;
-
-	assert(k != nil && v != nil);
-	if(len < 1)
-		len = strlen(k);
-	assert(len > 0);
-
-	if(t == nil){
-		t = malloc(sizeof(*t));
-		assert(t != nil);
-		t->leaf.k = k;
-		t->leaf.v = v;
-		return t;
-	}
-
-	t0 = t;
-	for(; isbranch(t); t = twig(t, i)){
-		b = twigbit(t, k, len);
-		i = hastwig(t, b) ? twigoff(t, b) : 0;
-	}
-	for(i = 0; i <= (unsigned)len && k[i] == t->leaf.k[i]; i++);
-	if(i == (unsigned)len+1){
-		t->leaf.v = v;
-		return t0;
-	}
-
-	k2 = (u8int)t->leaf.k[i];
-	f = (((u8int)k[i] ^ k2) & 0xf0) ? 1 : 2;
-	b1 = nibbit(k[i], f);
-	t1.leaf.k = k;
-	t1.leaf.v = v;
-	for(t = t0; isbranch(t); t = twig(t, twigoff(t, b))){
-		if(i == x_index(t->branch.x)){
-			if(f == x_flags(t->branch.x))
-				goto growbranch;
-			if(f < x_flags(t->branch.x))
-				break;
-		}else if(i < x_index(t->branch.x)){
-			break;
-		}
-		b = twigbit(t, k, len);
-		assert(hastwig(t, b));
-	}
-
-	t2 = *t;
-	b2 = nibbit(k2, f);
-	t->branch.twigs = malloc(sizeof(*t)*2);
-	assert(t->branch.twigs != nil);
-	t->branch.x = (u64int)f<<62 | (u64int)i<<16 | b1 | b2;
-	*twig(t, twigoff(t, b1)) = t1;
-	*twig(t, twigoff(t, b2)) = t2;
-
-	return t0;
-
-growbranch:
-	assert(!hastwig(t, b1));
-	twigoffmax(s, m, t, b1);
-	t->branch.twigs = realloc(t->branch.twigs, sizeof(*t)*(m+1));
-	memmove(t->branch.twigs+s+1, t->branch.twigs+s, sizeof(*t)*(m-s));
-	memmove(t->branch.twigs+s, &t1, sizeof(t1));
-	t->branch.x |= b1;
-
-	return t0;
-}
--- a/qp.h
+++ /dev/null
@@ -1,7 +1,0 @@
-typedef union Trie Trie;
-#pragma incomplete Trie
-
-int qpget(Trie *t, char *k, int len, char **pk, void **pv);
-int qpnext(Trie *t, char **pk, int *plen, void **pv);
-Trie *qpdel(Trie *t, char *k, int len, char **pk, void **pv);
-Trie *qpset(Trie *t, char *k, int len, void *v);
--- a/sys_plan9.c
+++ b/sys_plan9.c
@@ -9,6 +9,16 @@
 static int ndisabled;
 
 int
+qclz(unsigned x)
+{
+	unsigned r;
+	if(x == 0)
+		return 32;
+	for(r = 0; (x & (1UL<<31)) == 0; x <<= 1, r++);
+	return r;
+}
+
+int
 qctz(unsigned x)
 {
 	unsigned r;
--- /dev/null
+++ b/tbl.c
@@ -1,0 +1,57 @@
+// tbl.c: simpler wrappers for core table functions
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#include "platform.h"
+#include "tbl.h"
+
+void *
+Tgetl(Tbl *tbl, const char *key, int len)
+{
+	const char *rkey = nil;
+	void *rval = nil;
+	return Tgetkv(tbl, key, len, &rkey, &rval) ? rval : nil;
+}
+
+void *
+Tget(Tbl *tbl, const char *key)
+{
+	return Tgetl(tbl, key, strlen(key));
+}
+
+Tbl *
+Tset(Tbl *tbl, const char *key, void *value)
+{
+	return Tsetl(tbl, key, strlen(key), value);
+}
+
+Tbl *
+Tdell(Tbl *tbl, const char *key, int len)
+{
+	const char *rkey = nil;
+	void *rval = nil;
+	return Tdelkv(tbl, key, len, &rkey, &rval);
+}
+
+Tbl *
+Tdel(Tbl *tbl, const char *key)
+{
+	return Tdell(tbl, key, strlen(key));
+}
+
+bool
+Tnext(Tbl *tbl, const char **pkey, void **pvalue)
+{
+	int len = *pkey == nil ? 0 : strlen(*pkey);
+	return Tnextl(tbl, pkey, &len, pvalue);
+}
+
+const char *
+Tnxt(Tbl *tbl, const char *key)
+{
+	void *value = nil;
+	Tnext(tbl, &key, &value);
+	return key;
+}
--- /dev/null
+++ b/tbl.h
@@ -1,0 +1,56 @@
+// tbl.h: an abstract API for tables with string keys.
+//
+// Written by Tony Finch <dot@dotat.at>
+// You may do anything with this. It has no warranty.
+// <http://creativecommons.org/publicdomain/zero/1.0/>
+
+#pragma once
+
+// A table is represented by a pointer to this incomplete struct type.
+// You initialize an empty table by setting the pointer to NULL.
+//
+typedef struct Tbl Tbl;
+#ifdef __plan9__
+#pragma incomplete Tbl
+#endif
+
+// Get the value associated with a key.
+// Returns NULL if the key is not in the Table.
+//
+void *Tgetl(Tbl *tbl, const char *key, int klen);
+void *Tget(Tbl *tbl, const char *key);
+
+// Returns false if the key is not found, otherwise returns true and
+// sets *rkey and *rval to the table's key and value pointers.
+//
+bool Tgetkv(Tbl *tbl, const char *key, int klen, const char **rkey, void **rval);
+
+// Associate a key with a value in a table. Returns a new pointer to
+// the modified table. If there is an error it sets errno and returns
+// NULL. To delete a key, set its value to NULL. When the last key is
+// deleted, Tset() returns NULL without setting errno. The key and
+// value are borrowed not copied.
+//
+// Errors:
+// EINVAL - value pointer is not word-aligned
+// ENOMEM - allocation failed
+//
+Tbl *Tsetl(Tbl *tbl, const char *key, int klen, void *value);
+Tbl *Tset(Tbl *tbl, const char *key, void *value);
+Tbl *Tdell(Tbl *tbl, const char *key, int klen);
+Tbl *Tdel(Tbl *tbl, const char *key);
+
+// Deletes an entry from the table as above, and sets *rkey and *rval
+// to the removed key and value pointers.
+//
+Tbl *Tdelkv(Tbl *tbl, const char *key, int klen, const char **rkey, void **rval);
+
+// Find the next item in the table. The p... arguments are in/out
+// parameters. To find the first key, pass *pkey=NULL and *pklen=0.
+// For subsequent keys, *pkey must be present in the table and is
+// updated to the lexicographically following key. Returns false or
+// NULL when there are no more keys.
+//
+bool Tnextl(Tbl *tbl, const char **pkey, int *pklen, void **pvalue);
+bool Tnext(Tbl *tbl, const char **pkey, void **pvalue);
+const char *Tnxt(Tbl *tbl, const char *key);