ref: d347f48f5ee550b901d0cdba4779f2ebd11b0c73
parent: 4b95f4f4f1f3caae8e09e16f9bcd4af303a33a8b
author: kemal <[email protected]>
date: Fri Jul 2 14:45:08 EDT 2021
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);