{"thread":{"id":"57048","subject":"[PATCH] cbtree: remove broken and unused cb_unlink","startedAt":"2021-12-07T18:38:14Z","lastAt":"2021-12-07T18:38:14Z","messageCount":1,"participants":["Eric Wong"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"443336","messageId":"20211207183810.688481-1-e@80x24.org","threadId":"57048","inReplyTo":null,"subject":"[PATCH] cbtree: remove broken and unused cb_unlink","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2021-12-07T18:38:10Z","receivedAt":"2021-12-07T18:38:14Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"cb_unlink is broken once a node is no longer self-referential\ndue to subsequent insertions.  This is a consequence of an\nintrusive implementation and I'm not sure if it's easily fixable\nwhile retaining our cache-friendly intrusive property (I've\ntried for several hours in another project).\n\nIn any case, we're not using cb_unlink anywhere in our codebase,\njust get rid of it to avoid misleading future readers.\n\nSigned-off-by: Eric Wong <e@80x24.org>\n---\n cbtree.c | 32 --------------------------------\n cbtree.h |  1 -\n 2 files changed, 33 deletions(-)\n\ndiff --git a/cbtree.c b/cbtree.c\nindex b0c65d810f..336e46dbba 100644\n--- a/cbtree.c\n+++ b/cbtree.c\n@@ -95,38 +95,6 @@ struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)\n \treturn p && !memcmp(p->k, k, klen) ? p : NULL;\n }\n \n-struct cb_node *cb_unlink(struct cb_tree *t, const uint8_t *k, size_t klen)\n-{\n-\tstruct cb_node **wherep = &t->root;\n-\tstruct cb_node **whereq = NULL;\n-\tstruct cb_node *q = NULL;\n-\tsize_t direction = 0;\n-\tuint8_t c;\n-\tstruct cb_node *p = t->root;\n-\n-\tif (!p) return NULL;\t/* empty tree, nothing to delete */\n-\n-\t/* traverse to find best match, keeping link to parent */\n-\twhile (1 & (uintptr_t)p) {\n-\t\twhereq = wherep;\n-\t\tq = cb_node_of(p);\n-\t\tc = q->byte < klen ? k[q->byte] : 0;\n-\t\tdirection = (1 + (q->otherbits | c)) >> 8;\n-\t\twherep = q->child + direction;\n-\t\tp = *wherep;\n-\t}\n-\n-\tif (memcmp(p->k, k, klen))\n-\t\treturn NULL;\t\t/* no match, nothing unlinked */\n-\n-\t/* found an exact match */\n-\tif (whereq)\t/* update parent */\n-\t\t*whereq = q->child[1 - direction];\n-\telse\n-\t\tt->root = NULL;\n-\treturn p;\n-}\n-\n static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg)\n {\n \tif (1 & (uintptr_t)p) {\ndiff --git a/cbtree.h b/cbtree.h\nindex dedbb8e2a4..0be14fb7ee 100644\n--- a/cbtree.h\n+++ b/cbtree.h\n@@ -47,7 +47,6 @@ static inline void cb_init(struct cb_tree *t)\n \n struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen);\n struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen);\n-struct cb_node *cb_unlink(struct cb_tree *t, const uint8_t *k, size_t klen);\n \n typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg);\n \n"}]}