git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 08/17] cbtree: allow using arbitrary wrapper structures for nodes

From
Patrick Steinhardt <ps@pks.im>
Date
Apr 10, 2026, 12:12 UTC
Message-ID
<20260410-b4-pks-odb-source-inmemory-v3-8-22fd0fad58fe@pks.im>
In-Reply-To
<20260410-b4-pks-odb-source-inmemory-v3-0-22fd0fad58fe@pks.im>

The cbtree subsystem allows the user to store arbitrary data in a prefix-free set of strings. This is used by us to store object IDs in a way that we can easily iterate through them in lexicograph order, and so that we can easily perform lookups with shortened object IDs.

In its current form, it is not easily possible to store arbitrary data with the tree nodes. There are a couple of approaches such a caller could try to use, but none of them really work:

  - One may embed the `struct cb_node` in a custom structure. This does
    not work though as `struct cb_node` contains a flex array, and
    embedding such a struct in another struct is forbidden.
  - One may use a `union` over `struct cb_node` and ones own data type,
    which _is_ allowed even if the struct contains a flex array. This
    does not work though, as the compiler may align members of the
    struct so that the node key would not immediately start where the
    flex array starts.
  - One may allocate `struct cb_node` such that it has room for both its
    key and the custom data. This has the downside though that if the
    custom data is itself a pointer to allocated memory, then the leak
    checker will not consider the pointer to be alive anymore.

Refactor the cbtree to drop the flex array and instead take in an explicit offset for where to find the key, which allows the caller to embed `struct cb_node` is a wrapper struct.

Note that this change has the downside that we now have a bit of padding in our structure, which grows the size from 60 to 64 bytes on a 64 bit system. On the other hand though, it allows us to get rid of the memory copies that we previously had to do to ensure proper alignment. This seems like a reasonable tradeoff.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 cbtree.c  | 25 ++++++++++++++++++-------
 cbtree.h  | 17 +++++++++--------
 oidtree.c | 33 ++++++++++++++-------------------
 3 files changed, 41 insertions(+), 34 deletions(-)
diff --git a/cbtree.c b/cbtree.c
index 4ab794bddc..8f5edbb80a 100644
--- a/cbtree.c
+++ b/cbtree.c
@@ -7,6 +7,11 @@
 #include "git-compat-util.h"
 #include "cbtree.h"
 
+static inline uint8_t *cb_node_key(struct cb_tree *t, struct cb_node *node)
+{
+	return (uint8_t *) node + t->key_offset;
+}
+
 static struct cb_node *cb_node_of(const void *p)
 {
 	return (struct cb_node *)((uintptr_t)p - 1);
@@ -33,6 +38,7 @@ struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
 	uint8_t c;
 	int newdirection;
 	struct cb_node **wherep, *p;
+	uint8_t *node_key, *p_key;
 
 	assert(!((uintptr_t)node & 1)); /* allocations must be aligned */
 
@@ -41,23 +47,26 @@ struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
 		return NULL;	/* success */
 	}
 
+	node_key = cb_node_key(t, node);
+
 	/* see if a node already exists */
-	p = cb_internal_best_match(t->root, node->k, klen);
+	p = cb_internal_best_match(t->root, node_key, klen);
+	p_key = cb_node_key(t, p);
 
 	/* find first differing byte */
 	for (newbyte = 0; newbyte < klen; newbyte++) {
-		if (p->k[newbyte] != node->k[newbyte])
+		if (p_key[newbyte] != node_key[newbyte])
 			goto different_byte_found;
 	}
 	return p;	/* element exists, let user deal with it */
 
 different_byte_found:
-	newotherbits = p->k[newbyte] ^ node->k[newbyte];
+	newotherbits = p_key[newbyte] ^ node_key[newbyte];
 	newotherbits |= newotherbits >> 1;
 	newotherbits |= newotherbits >> 2;
 	newotherbits |= newotherbits >> 4;
 	newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;
-	c = p->k[newbyte];
+	c = p_key[newbyte];
 	newdirection = (1 + (newotherbits | c)) >> 8;
 
 	node->byte = newbyte;
@@ -78,7 +87,7 @@ struct cb_node *cb_insert(struct cb_tree *t, struct cb_node *node, size_t klen)
 			break;
 		if (q->byte == newbyte && q->otherbits > newotherbits)
 			break;
-		c = q->byte < klen ? node->k[q->byte] : 0;
+		c = q->byte < klen ? node_key[q->byte] : 0;
 		direction = (1 + (q->otherbits | c)) >> 8;
 		wherep = q->child + direction;
 	}
@@ -93,7 +102,7 @@ struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)
 {
 	struct cb_node *p = cb_internal_best_match(t->root, k, klen);
 
-	return p && !memcmp(p->k, k, klen) ? p : NULL;
+	return p && !memcmp(cb_node_key(t, p), k, klen) ? p : NULL;
 }
 
 static int cb_descend(struct cb_node *p, cb_iter fn, void *arg)
@@ -115,6 +124,7 @@ int cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
 	struct cb_node *p = t->root;
 	struct cb_node *top = p;
 	size_t i = 0;
+	uint8_t *p_key;
 
 	if (!p)
 		return 0; /* empty tree */
@@ -130,8 +140,9 @@ int cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
 			top = p;
 	}
 
+	p_key = cb_node_key(t, p);
 	for (i = 0; i < klen; i++) {
-		if (p->k[i] != kpfx[i])
+		if (p_key[i] != kpfx[i])
 			return 0; /* "best" match failed */
 	}
 
diff --git a/cbtree.h b/cbtree.h
index c374b1b3db..4647d4a32f 100644
--- a/cbtree.h
+++ b/cbtree.h
@@ -6,9 +6,9 @@
  *
  * This is adapted to store arbitrary data (not just NUL-terminated C strings
  * and allocates no memory internally.  The user needs to allocate
- * "struct cb_node" and fill cb_node.k[] with arbitrary match data
- * for memcmp.
- * If "klen" is variable, then it should be embedded into "c_node.k[]"
+ * "struct cb_node" and provide `key_offset` to indicate where the key can be
+ * found relative to the `struct cb_node` for memcmp.
+ * If "klen" is variable, then it should be embedded into the key.
  * Recursion is bound by the maximum value of "klen" used.
  */
 #ifndef CBTREE_H
@@ -23,18 +23,19 @@ struct cb_node {
 	 */
 	uint32_t byte;
 	uint8_t otherbits;
-	uint8_t k[FLEX_ARRAY]; /* arbitrary data, unaligned */
 };
 
 struct cb_tree {
 	struct cb_node *root;
+	ptrdiff_t key_offset;
 };
 
-#define CBTREE_INIT { 0 }
-
-static inline void cb_init(struct cb_tree *t)
+static inline void cb_init(struct cb_tree *t,
+			   ptrdiff_t key_offset)
 {
-	struct cb_tree blank = CBTREE_INIT;
+	struct cb_tree blank = {
+		.key_offset = key_offset,
+	};
 	memcpy(t, &blank, sizeof(*t));
 }
 
diff --git a/oidtree.c b/oidtree.c
index ab9fe7ec7a..117649753f 100644
--- a/oidtree.c
+++ b/oidtree.c
@@ -6,9 +6,14 @@
 #include "oidtree.h"
 #include "hash.h"
 
+struct oidtree_node {
+	struct cb_node base;
+	struct object_id key;
+};
+
 void oidtree_init(struct oidtree *ot)
 {
-	cb_init(&ot->tree);
+	cb_init(&ot->tree, offsetof(struct oidtree_node, key));
 	mem_pool_init(&ot->mem_pool, 0);
 }
 
@@ -22,20 +27,13 @@ void oidtree_clear(struct oidtree *ot)
 
 void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
 {
-	struct cb_node *on;
-	struct object_id k;
+	struct oidtree_node *on;
 
 	if (!oid->algo)
 		BUG("oidtree_insert requires oid->algo");
 
-	on = mem_pool_alloc(&ot->mem_pool, sizeof(*on) + sizeof(*oid));
-
-	/*
-	 * Clear the padding and copy the result in separate steps to
-	 * respect the 4-byte alignment needed by struct object_id.
-	 */
-	oidcpy(&k, oid);
-	memcpy(on->k, &k, sizeof(k));
+	on = mem_pool_alloc(&ot->mem_pool, sizeof(*on));
+	oidcpy(&on->key, oid);
 
 	/*
 	 * n.b. Current callers won't get us duplicates, here.  If a
@@ -43,7 +41,7 @@ void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
 	 * that won't be freed until oidtree_clear.  Currently it's not
 	 * worth maintaining a free list
 	 */
-	cb_insert(&ot->tree, on, sizeof(*oid));
+	cb_insert(&ot->tree, &on->base, sizeof(*oid));
 }
 
 bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
@@ -73,21 +71,18 @@ struct oidtree_each_data {
 
 static int iter(struct cb_node *n, void *cb_data)
 {
+	struct oidtree_node *node = container_of(n, struct oidtree_node, base);
 	struct oidtree_each_data *data = cb_data;
-	struct object_id k;
-
-	/* Copy to provide 4-byte alignment needed by struct object_id. */
-	memcpy(&k, n->k, sizeof(k));
 
-	if (data->algo != GIT_HASH_UNKNOWN && data->algo != k.algo)
+	if (data->algo != GIT_HASH_UNKNOWN && data->algo != node->key.algo)
 		return 0;
 
 	if (data->last_nibble_at) {
-		if ((k.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0)
+		if ((node->key.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0)
 			return 0;
 	}
 
-	return data->cb(&k, data->cb_data);
+	return data->cb(&node->key, data->cb_data);
 }
 
 int oidtree_each(struct oidtree *ot, const struct object_id *prefix,
-- 
2.54.0.rc0.707.g0fbf48f4d6.dirty
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 74 of 85 in “odb: introduce "inmemory" source”
  1. 00/16 odb: introduce "inmemory" sourcePatrick Steinhardt, Apr 3, 2026
  2. 01/16 odb: introduce "inmemory" sourcePatrick Steinhardt, Apr 3, 2026
  3. Justin ToblerApr 8, 2026
  4. Patrick SteinhardtApr 9, 2026
  5. 02/16 odb/source-inmemory: implement `free()` callbackPatrick Steinhardt, Apr 3, 2026
  6. Justin ToblerApr 8, 2026
  7. 03/16 odb: fix unnecessary call to `find_cached_object()`Patrick Steinhardt, Apr 3, 2026
  8. Justin ToblerApr 8, 2026
  9. Patrick SteinhardtApr 9, 2026
  10. 04/16 odb/source-inmemory: implement `read_object_info()` callbackPatrick Steinhardt, Apr 3, 2026
  11. 05/16 odb/source-inmemory: implement `read_object_stream()` callbackPatrick Steinhardt, Apr 3, 2026
  12. Justin ToblerApr 8, 2026
  13. Patrick SteinhardtApr 9, 2026
  14. 06/16 odb/source-inmemory: implement `write_object()` callbackPatrick Steinhardt, Apr 3, 2026
  15. 07/16 odb/source-inmemory: implement `write_object_stream()` callbackPatrick Steinhardt, Apr 3, 2026
  16. Junio C HamanoApr 3, 2026
  17. Patrick SteinhardtApr 8, 2026
  18. 08/16 cbtree: allow using arbitrary wrapper structures for nodesPatrick Steinhardt, Apr 3, 2026
  19. 09/16 oidtree: add ability to store dataPatrick Steinhardt, Apr 3, 2026
  20. 10/16 odb/source-inmemory: convert to use oidtreePatrick Steinhardt, Apr 3, 2026
  21. 11/16 odb/source-inmemory: implement `for_each_object()` callbackPatrick Steinhardt, Apr 3, 2026
  22. 12/16 odb/source-inmemory: implement `find_abbrev_len()` callbackPatrick Steinhardt, Apr 3, 2026
  23. 13/16 odb/source-inmemory: implement `count_objects()` callbackPatrick Steinhardt, Apr 3, 2026
  24. 14/16 odb/source-inmemory: implement `freshen_object()` callbackPatrick Steinhardt, Apr 3, 2026
  25. 15/16 odb/source-inmemory: stub out remaining functionsPatrick Steinhardt, Apr 3, 2026
  26. 16/16 odb: generic inmemory sourcePatrick Steinhardt, Apr 3, 2026
  27. Junio C HamanoApr 3, 2026
  28. Patrick SteinhardtApr 8, 2026
  29. Junio C HamanoApr 8, 2026
  30. Patrick SteinhardtApr 9, 2026
  31. Junio C HamanoApr 9, 2026
  32. Patrick SteinhardtApr 10, 2026
  33. 00/17 odb: introduce "in-memory" sourcePatrick Steinhardt, Apr 9, 2026
  34. 01/17 odb: introduce "in-memory" sourcePatrick Steinhardt, Apr 9, 2026
  35. Karthik NayakApr 9, 2026
  36. Patrick SteinhardtApr 9, 2026
  37. 02/17 odb/source-inmemory: implement `free()` callbackPatrick Steinhardt, Apr 9, 2026
  38. 03/17 odb: fix unnecessary call to `find_cached_object()`Patrick Steinhardt, Apr 9, 2026
  39. 04/17 odb/source-inmemory: implement `read_object_info()` callbackPatrick Steinhardt, Apr 9, 2026
  40. Karthik NayakApr 9, 2026
  41. Patrick SteinhardtApr 9, 2026
  42. Karthik NayakApr 9, 2026
  43. 05/17 odb/source-inmemory: implement `read_object_stream()` callbackPatrick Steinhardt, Apr 9, 2026
  44. Karthik NayakApr 9, 2026
  45. Patrick SteinhardtApr 9, 2026
  46. 06/17 odb/source-inmemory: implement `write_object()` callbackPatrick Steinhardt, Apr 9, 2026
  47. 07/17 odb/source-inmemory: implement `write_object()` callbackPatrick Steinhardt, Apr 9, 2026
  48. Karthik NayakApr 9, 2026
  49. Patrick SteinhardtApr 9, 2026
  50. 08/17 odb/source-inmemory: implement `write_object_stream()` callbackPatrick Steinhardt, Apr 9, 2026
  51. 09/17 cbtree: allow using arbitrary wrapper structures for nodesPatrick Steinhardt, Apr 9, 2026
  52. Karthik NayakApr 9, 2026
  53. Patrick SteinhardtApr 9, 2026
  54. 10/17 oidtree: add ability to store dataPatrick Steinhardt, Apr 9, 2026
  55. 11/17 odb/source-inmemory: convert to use oidtreePatrick Steinhardt, Apr 9, 2026
  56. 12/17 odb/source-inmemory: implement `for_each_object()` callbackPatrick Steinhardt, Apr 9, 2026
  57. 13/17 odb/source-inmemory: implement `find_abbrev_len()` callbackPatrick Steinhardt, Apr 9, 2026
  58. 14/17 odb/source-inmemory: implement `count_objects()` callbackPatrick Steinhardt, Apr 9, 2026
  59. 15/17 odb/source-inmemory: implement `freshen_object()` callbackPatrick Steinhardt, Apr 9, 2026
  60. 16/17 odb/source-inmemory: stub out remaining functionsPatrick Steinhardt, Apr 9, 2026
  61. Junio C HamanoApr 9, 2026
  62. Patrick SteinhardtApr 10, 2026
  63. 17/17 odb: generic in-memory sourcePatrick Steinhardt, Apr 9, 2026
  64. Karthik NayakApr 9, 2026
  65. Patrick SteinhardtApr 9, 2026
  66. 00/17 odb: introduce "in-memory" sourcePatrick Steinhardt, Apr 10, 2026
  67. 01/17 odb: introduce "in-memory" sourcePatrick Steinhardt, Apr 10, 2026
  68. 02/17 odb/source-inmemory: implement `free()` callbackPatrick Steinhardt, Apr 10, 2026
  69. 03/17 odb: fix unnecessary call to `find_cached_object()`Patrick Steinhardt, Apr 10, 2026
  70. 04/17 odb/source-inmemory: implement `read_object_info()` callbackPatrick Steinhardt, Apr 10, 2026
  71. 05/17 odb/source-inmemory: implement `read_object_stream()` callbackPatrick Steinhardt, Apr 10, 2026
  72. 06/17 odb/source-inmemory: implement `write_object()` callbackPatrick Steinhardt, Apr 10, 2026
  73. 07/17 odb/source-inmemory: implement `write_object_stream()` callbackPatrick Steinhardt, Apr 10, 2026
  74. 08/17 cbtree: allow using arbitrary wrapper structures for nodesPatrick Steinhardt, Apr 10, 2026
  75. 09/17 oidtree: add ability to store dataPatrick Steinhardt, Apr 10, 2026
  76. 10/17 odb/source-inmemory: convert to use oidtreePatrick Steinhardt, Apr 10, 2026
  77. 11/17 odb/source-inmemory: implement `for_each_object()` callbackPatrick Steinhardt, Apr 10, 2026
  78. 12/17 odb/source-inmemory: implement `find_abbrev_len()` callbackPatrick Steinhardt, Apr 10, 2026
  79. 13/17 odb/source-inmemory: implement `count_objects()` callbackPatrick Steinhardt, Apr 10, 2026
  80. 14/17 odb/source-inmemory: implement `freshen_object()` callbackPatrick Steinhardt, Apr 10, 2026
  81. 15/17 odb/source-inmemory: stub out remaining functionsPatrick Steinhardt, Apr 10, 2026
  82. 16/17 odb: generic in-memory sourcePatrick Steinhardt, Apr 10, 2026
  83. 17/17 t/unit-tests: add tests for the in-memory object sourcePatrick Steinhardt, Apr 10, 2026
  84. Karthik NayakApr 14, 2026
  85. Karthik NayakApr 14, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.