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

[PATCH v3 09/17] oidtree: add ability to store data

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

The oidtree data structure is currently only used to store object IDs, without any associated data. So consequently, it can only really be used to track which object IDs exist, and we can use the tree structure to efficiently operate on OID prefixes.

But there are valid use cases where we want to both:
  - Store object IDs in a sorted order.
  - Associated arbitrary data with them.

Refactor the oidtree interface so that it allows us to store arbitrary payloads within the respective nodes. This will be used in the next commit.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 loose.c                  |  2 +-
 object-file.c            |  3 ++-
 oidtree.c                | 37 ++++++++++++++++++++++++++++++++-----
 oidtree.h                | 12 ++++++++++--
 t/unit-tests/u-oidtree.c | 26 +++++++++++++++++++++++---
 5 files changed, 68 insertions(+), 12 deletions(-)
diff --git a/loose.c b/loose.c
index 07333be696..f7a3dd1a72 100644
--- a/loose.c
+++ b/loose.c
@@ -57,7 +57,7 @@ static int insert_loose_map(struct odb_source *source,
 	inserted |= insert_oid_pair(map->to_compat, oid, compat_oid);
 	inserted |= insert_oid_pair(map->to_storage, compat_oid, oid);
 	if (inserted)
-		oidtree_insert(files->loose->cache, compat_oid);
+		oidtree_insert(files->loose->cache, compat_oid, NULL);
 
 	return inserted;
 }
diff --git a/object-file.c b/object-file.c
index 3e70e5d668..d04ab57253 100644
--- a/object-file.c
+++ b/object-file.c
@@ -1857,6 +1857,7 @@ static int for_each_object_wrapper_cb(const struct object_id *oid,
 }
 
 static int for_each_prefixed_object_wrapper_cb(const struct object_id *oid,
+					       void *node_data UNUSED,
 					       void *cb_data)
 {
 	struct for_each_object_wrapper_data *data = cb_data;
@@ -2002,7 +2003,7 @@ static int append_loose_object(const struct object_id *oid,
 			       const char *path UNUSED,
 			       void *data)
 {
-	oidtree_insert(data, oid);
+	oidtree_insert(data, oid, NULL);
 	return 0;
 }
 
diff --git a/oidtree.c b/oidtree.c
index 117649753f..e43f18026e 100644
--- a/oidtree.c
+++ b/oidtree.c
@@ -9,6 +9,7 @@
 struct oidtree_node {
 	struct cb_node base;
 	struct object_id key;
+	void *data;
 };
 
 void oidtree_init(struct oidtree *ot)
@@ -25,15 +26,22 @@ void oidtree_clear(struct oidtree *ot)
 	}
 }
 
-void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
+struct oidtree_data {
+	struct object_id oid;
+};
+
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid,
+		    void *data)
 {
 	struct oidtree_node *on;
+	struct cb_node *node;
 
 	if (!oid->algo)
 		BUG("oidtree_insert requires oid->algo");
 
 	on = mem_pool_alloc(&ot->mem_pool, sizeof(*on));
 	oidcpy(&on->key, oid);
+	on->data = data;
 
 	/*
 	 * n.b. Current callers won't get us duplicates, here.  If a
@@ -41,13 +49,19 @@ 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->base, sizeof(*oid));
+	node = cb_insert(&ot->tree, &on->base, sizeof(*oid));
+	if (node) {
+		struct oidtree_node *preexisting = container_of(node, struct oidtree_node, base);
+		preexisting->data = data;
+	}
 }
 
-bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+static struct oidtree_node *oidtree_lookup(struct oidtree *ot,
+					   const struct object_id *oid)
 {
 	struct object_id k;
 	size_t klen = sizeof(k);
+	struct cb_node *node;
 
 	oidcpy(&k, oid);
 
@@ -58,7 +72,20 @@ bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
 	klen += BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, hash) <
 				offsetof(struct object_id, algo));
 
-	return !!cb_lookup(&ot->tree, (const uint8_t *)&k, klen);
+	node = cb_lookup(&ot->tree, (const uint8_t *)&k, klen);
+	return node ? container_of(node, struct oidtree_node, base) : NULL;
+}
+
+bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+{
+	struct oidtree_node *node = oidtree_lookup(ot, oid);
+	return node ? 1 : 0;
+}
+
+void *oidtree_get(struct oidtree *ot, const struct object_id *oid)
+{
+	struct oidtree_node *node = oidtree_lookup(ot, oid);
+	return node ? node->data : NULL;
 }
 
 struct oidtree_each_data {
@@ -82,7 +109,7 @@ static int iter(struct cb_node *n, void *cb_data)
 			return 0;
 	}
 
-	return data->cb(&node->key, data->cb_data);
+	return data->cb(&node->key, node->data, data->cb_data);
 }
 
 int oidtree_each(struct oidtree *ot, const struct object_id *prefix,
diff --git a/oidtree.h b/oidtree.h
index 2b7bad2e60..baa5a436ea 100644
--- a/oidtree.h
+++ b/oidtree.h
@@ -29,18 +29,26 @@ void oidtree_init(struct oidtree *ot);
  */
 void oidtree_clear(struct oidtree *ot);
 
-/* Insert the object ID into the tree. */
-void oidtree_insert(struct oidtree *ot, const struct object_id *oid);
+/*
+ * Insert the object ID into the tree and store the given pointer alongside
+ * with it. The data pointer of any preexisting entry will be overwritten.
+ */
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid,
+		    void *data);
 
 /* Check whether the tree contains the given object ID. */
 bool oidtree_contains(struct oidtree *ot, const struct object_id *oid);
 
+/* Get the payload stored with the given object ID. */
+void *oidtree_get(struct oidtree *ot, const struct object_id *oid);
+
 /*
  * Callback function used for `oidtree_each()`. Returning a non-zero exit code
  * will cause iteration to stop. The exit code will be propagated to the caller
  * of `oidtree_each()`.
  */
 typedef int (*oidtree_each_cb)(const struct object_id *oid,
+			       void *node_data,
 			       void *cb_data);
 
 /*
diff --git a/t/unit-tests/u-oidtree.c b/t/unit-tests/u-oidtree.c
index d4d05c7dc3..f0d5ebb733 100644
--- a/t/unit-tests/u-oidtree.c
+++ b/t/unit-tests/u-oidtree.c
@@ -19,7 +19,7 @@ static int fill_tree_loc(struct oidtree *ot, const char *hexes[], size_t n)
 	for (size_t i = 0; i < n; i++) {
 		struct object_id oid;
 		cl_parse_any_oid(hexes[i], &oid);
-		oidtree_insert(ot, &oid);
+		oidtree_insert(ot, &oid, NULL);
 	}
 	return 0;
 }
@@ -38,9 +38,9 @@ struct expected_hex_iter {
 	const char *query;
 };
 
-static int check_each_cb(const struct object_id *oid, void *data)
+static int check_each_cb(const struct object_id *oid, void *node_data UNUSED, void *cb_data)
 {
-	struct expected_hex_iter *hex_iter = data;
+	struct expected_hex_iter *hex_iter = cb_data;
 	struct object_id expected;
 
 	cl_assert(hex_iter->i < hex_iter->expected_hexes.nr);
@@ -105,3 +105,23 @@ void test_oidtree__each(void)
 	check_each(&ot, "32100", "321", NULL);
 	check_each(&ot, "32", "320", "321", NULL);
 }
+
+void test_oidtree__insert_overwrites_data(void)
+{
+	struct object_id oid;
+	struct oidtree ot;
+	int a, b;
+
+	cl_parse_any_oid("1", &oid);
+
+	oidtree_init(&ot);
+
+	oidtree_insert(&ot, &oid, NULL);
+	cl_assert_equal_p(oidtree_get(&ot, &oid), NULL);
+	oidtree_insert(&ot, &oid, &a);
+	cl_assert_equal_p(oidtree_get(&ot, &oid), &a);
+	oidtree_insert(&ot, &oid, &b);
+	cl_assert_equal_p(oidtree_get(&ot, &oid), &b);
+
+	oidtree_clear(&ot);
+}
-- 
2.54.0.rc0.707.g0fbf48f4d6.dirty
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 75 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.