shithub: snippets

Info  •  Files  •  Log

qp.[ch]: add qpdel

--- a/qp.c

+++ b/qp.c

@@ -108,6 +108,51 @@

 }

 Trie *

+qpdel(Trie *t, char *k, int len, char **pk, void **pv)

+{

+	Trie *p, *twigs;

+	Tbitmap b;

+	uint 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;

--- a/qp.h

+++ b/qp.h

@@ -3,4 +3,5 @@

 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);