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

[PATCH v2 01/14] oidtree: modernize the code a bit

From
Patrick Steinhardt <ps@pks.im>
Date
Mar 20, 2026, 07:07 UTC
Message-ID
<20260320-b4-pks-odb-source-abbrev-v2-1-fe65dcd8c735@pks.im>
In-Reply-To
<20260320-b4-pks-odb-source-abbrev-v2-0-fe65dcd8c735@pks.im>

The "oidtree.c" subsystem is rather small and self-contained and tends to just work. It thus doesn't typically receive a lot of attention, which has as a consequence that it's coding style is somewhat dated nowadays.

Modernize the style of this subsystem a bit:
  - Rename the `oidtree_iter()` function to `oidtree_each_cb()`.
  - Rename `struct oidtree_iter_data` to `struct oidtree_each_data` to
    match the renamed callback function type.
  - Rename parameters and variables to clarify their intent.
  - Add comments that explain what some of the functions do.
  - Adapt the return value of `oidtree_contains()` to be a boolean.

This prepares for some changes to the subsystem that'll happen in the next commit.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 oidtree.c                | 61 ++++++++++++++++++++++++------------------------
 oidtree.h                | 42 +++++++++++++++++++++++++++------
 t/unit-tests/u-oidtree.c | 14 +++++------
 3 files changed, 73 insertions(+), 44 deletions(-)
diff --git a/oidtree.c b/oidtree.c
index 324de94934..a4d10cd429 100644
--- a/oidtree.c
+++ b/oidtree.c
@@ -6,14 +6,6 @@
 #include "oidtree.h"
 #include "hash.h"
 
-struct oidtree_iter_data {
-	oidtree_iter fn;
-	void *arg;
-	size_t *last_nibble_at;
-	uint32_t algo;
-	uint8_t last_byte;
-};
-
 void oidtree_init(struct oidtree *ot)
 {
 	cb_init(&ot->tree);
@@ -54,8 +46,7 @@ void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
 	cb_insert(&ot->tree, on, sizeof(*oid));
 }
 
-
-int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
+bool oidtree_contains(struct oidtree *ot, const struct object_id *oid)
 {
 	struct object_id k;
 	size_t klen = sizeof(k);
@@ -69,41 +60,51 @@ int 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) ? 1 : 0;
+	return !!cb_lookup(&ot->tree, (const uint8_t *)&k, klen);
 }
 
-static enum cb_next iter(struct cb_node *n, void *arg)
+struct oidtree_each_data {
+	oidtree_each_cb cb;
+	void *cb_data;
+	size_t *last_nibble_at;
+	uint32_t algo;
+	uint8_t last_byte;
+};
+
+static enum cb_next iter(struct cb_node *n, void *cb_data)
 {
-	struct oidtree_iter_data *x = arg;
+	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 (x->algo != GIT_HASH_UNKNOWN && x->algo != k.algo)
+	if (data->algo != GIT_HASH_UNKNOWN && data->algo != k.algo)
 		return CB_CONTINUE;
 
-	if (x->last_nibble_at) {
-		if ((k.hash[*x->last_nibble_at] ^ x->last_byte) & 0xf0)
+	if (data->last_nibble_at) {
+		if ((k.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0)
 			return CB_CONTINUE;
 	}
 
-	return x->fn(&k, x->arg);
+	return data->cb(&k, data->cb_data);
 }
 
-void oidtree_each(struct oidtree *ot, const struct object_id *oid,
-			size_t oidhexsz, oidtree_iter fn, void *arg)
+void oidtree_each(struct oidtree *ot, const struct object_id *prefix,
+		  size_t prefix_hex_len, oidtree_each_cb cb, void *cb_data)
 {
-	size_t klen = oidhexsz / 2;
-	struct oidtree_iter_data x = { 0 };
-	assert(oidhexsz <= GIT_MAX_HEXSZ);
-
-	x.fn = fn;
-	x.arg = arg;
-	x.algo = oid->algo;
-	if (oidhexsz & 1) {
-		x.last_byte = oid->hash[klen];
-		x.last_nibble_at = &klen;
+	struct oidtree_each_data data = {
+		.cb = cb,
+		.cb_data = cb_data,
+		.algo = prefix->algo,
+	};
+	size_t klen = prefix_hex_len / 2;
+	assert(prefix_hex_len <= GIT_MAX_HEXSZ);
+
+	if (prefix_hex_len & 1) {
+		data.last_byte = prefix->hash[klen];
+		data.last_nibble_at = &klen;
 	}
-	cb_each(&ot->tree, (const uint8_t *)oid, klen, iter, &x);
+
+	cb_each(&ot->tree, prefix->hash, klen, iter, &data);
 }
diff --git a/oidtree.h b/oidtree.h
index 77898f510a..0651401017 100644
--- a/oidtree.h
+++ b/oidtree.h
@@ -5,18 +5,46 @@
 #include "hash.h"
 #include "mem-pool.h"
 
+/*
+ * OID trees are an efficient storage for object IDs that use a critbit tree
+ * internally. Common prefixes are duplicated and object IDs are stored in a
+ * way that allow easy iteration over the objects in lexicographic order. As a
+ * consequence, operations that want to enumerate all object IDs that match a
+ * given prefix can be answered efficiently.
+ *
+ * Note that it is not (yet) possible to store data other than the object IDs
+ * themselves in this tree.
+ */
 struct oidtree {
 	struct cb_tree tree;
 	struct mem_pool mem_pool;
 };
 
-void oidtree_init(struct oidtree *);
-void oidtree_clear(struct oidtree *);
-void oidtree_insert(struct oidtree *, const struct object_id *);
-int oidtree_contains(struct oidtree *, const struct object_id *);
+/* Initialize the oidtree so that it is ready for use. */
+void oidtree_init(struct oidtree *ot);
 
-typedef enum cb_next (*oidtree_iter)(const struct object_id *, void *data);
-void oidtree_each(struct oidtree *, const struct object_id *,
-			size_t oidhexsz, oidtree_iter, void *data);
+/*
+ * Release all memory associated with the oidtree and reinitialize it for
+ * subsequent use.
+ */
+void oidtree_clear(struct oidtree *ot);
+
+/* Insert the object ID into the tree. */
+void oidtree_insert(struct oidtree *ot, const struct object_id *oid);
+
+/* Check whether the tree contains the given object ID. */
+bool oidtree_contains(struct oidtree *ot, const struct object_id *oid);
+
+/* Callback function used for `oidtree_each()`. */
+typedef enum cb_next (*oidtree_each_cb)(const struct object_id *oid,
+					void *cb_data);
+
+/*
+ * Iterate through all object IDs in the tree whose prefix matches the given
+ * object ID prefix and invoke the callback function on each of them.
+ */
+void oidtree_each(struct oidtree *ot,
+		  const struct object_id *prefix, size_t prefix_hex_len,
+		  oidtree_each_cb cb, void *cb_data);
 
 #endif /* OIDTREE_H */
diff --git a/t/unit-tests/u-oidtree.c b/t/unit-tests/u-oidtree.c
index e6eede2740..def47c6795 100644
--- a/t/unit-tests/u-oidtree.c
+++ b/t/unit-tests/u-oidtree.c
@@ -24,7 +24,7 @@ static int fill_tree_loc(struct oidtree *ot, const char *hexes[], size_t n)
 	return 0;
 }
 
-static void check_contains(struct oidtree *ot, const char *hex, int expected)
+static void check_contains(struct oidtree *ot, const char *hex, bool expected)
 {
 	struct object_id oid;
 
@@ -88,12 +88,12 @@ void test_oidtree__cleanup(void)
 void test_oidtree__contains(void)
 {
 	FILL_TREE(&ot, "444", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e");
-	check_contains(&ot, "44", 0);
-	check_contains(&ot, "441", 0);
-	check_contains(&ot, "440", 0);
-	check_contains(&ot, "444", 1);
-	check_contains(&ot, "4440", 1);
-	check_contains(&ot, "4444", 0);
+	check_contains(&ot, "44", false);
+	check_contains(&ot, "441", false);
+	check_contains(&ot, "440", false);
+	check_contains(&ot, "444", true);
+	check_contains(&ot, "4440", true);
+	check_contains(&ot, "4444", false);
 }
 
 void test_oidtree__each(void)
-- 
2.53.0.1055.ga2ffed1127.dirty
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 32 of 52 in “odb: generic object name handling”
  1. 00/14 odb: generic object name handlingPatrick Steinhardt, Mar 19, 2026
  2. 01/14 oidtree: modernize the code a bitPatrick Steinhardt, Mar 19, 2026
  3. Junio C HamanoMar 19, 2026
  4. Patrick SteinhardtMar 20, 2026
  5. brian m. carlsonMar 20, 2026
  6. Patrick SteinhardtMar 23, 2026
  7. 02/14 oidtree: extend iteration to allow for arbitrary return codesPatrick Steinhardt, Mar 19, 2026
  8. Junio C HamanoMar 19, 2026
  9. Patrick SteinhardtMar 20, 2026
  10. Karthik NayakMar 19, 2026
  11. 03/14 odb: introduce `struct odb_for_each_object_options`Patrick Steinhardt, Mar 19, 2026
  12. Junio C HamanoMar 19, 2026
  13. Patrick SteinhardtMar 19, 2026
  14. Karthik NayakMar 20, 2026
  15. 04/14 object-name: move logic to iterate through loose prefixed objectsPatrick Steinhardt, Mar 19, 2026
  16. 05/14 object-name: move logic to iterate through packed prefixed objectsPatrick Steinhardt, Mar 19, 2026
  17. 06/14 object-name: extract function to parse object ID prefixesPatrick Steinhardt, Mar 19, 2026
  18. 07/14 object-name: backend-generic `repo_collect_ambiguous()`Patrick Steinhardt, Mar 19, 2026
  19. Junio C HamanoMar 19, 2026
  20. Patrick SteinhardtMar 19, 2026
  21. Karthik NayakMar 20, 2026
  22. 08/14 object-name: backend-generic `get_short_oid()`Patrick Steinhardt, Mar 19, 2026
  23. 09/14 object-name: merge `update_candidates()` and `match_prefix()`Patrick Steinhardt, Mar 19, 2026
  24. 10/14 object-name: abbreviate loose object names without `disambiguate_state`Patrick Steinhardt, Mar 19, 2026
  25. 11/14 object-name: simplify computing common prefixesPatrick Steinhardt, Mar 19, 2026
  26. Karthik NayakMar 20, 2026
  27. Patrick SteinhardtMar 20, 2026
  28. 12/14 object-name: move logic to compute loose abbreviation lengthPatrick Steinhardt, Mar 19, 2026
  29. 13/14 object-file: move logic to compute packed abbreviation lengthPatrick Steinhardt, Mar 19, 2026
  30. 14/14 odb: introduce generic `odb_find_abbrev_len()`Patrick Steinhardt, Mar 19, 2026
  31. 00/14 odb: generic object name handlingPatrick Steinhardt, Mar 20, 2026
  32. 01/14 oidtree: modernize the code a bitPatrick Steinhardt, Mar 20, 2026
  33. 02/14 oidtree: extend iteration to allow for arbitrary return codesPatrick Steinhardt, Mar 20, 2026
  34. 03/14 odb: introduce `struct odb_for_each_object_options`Patrick Steinhardt, Mar 20, 2026
  35. 04/14 object-name: move logic to iterate through loose prefixed objectsPatrick Steinhardt, Mar 20, 2026
  36. 05/14 object-name: move logic to iterate through packed prefixed objectsPatrick Steinhardt, Mar 20, 2026
  37. Toon ClaesMar 30, 2026
  38. 06/14 object-name: extract function to parse object ID prefixesPatrick Steinhardt, Mar 20, 2026
  39. 07/14 object-name: backend-generic `repo_collect_ambiguous()`Patrick Steinhardt, Mar 20, 2026
  40. 08/14 object-name: backend-generic `get_short_oid()`Patrick Steinhardt, Mar 20, 2026
  41. Toon ClaesMar 30, 2026
  42. 09/14 object-name: merge `update_candidates()` and `match_prefix()`Patrick Steinhardt, Mar 20, 2026
  43. 10/14 object-name: abbreviate loose object names without `disambiguate_state`Patrick Steinhardt, Mar 20, 2026
  44. 11/14 object-name: simplify computing common prefixesPatrick Steinhardt, Mar 20, 2026
  45. 12/14 object-name: move logic to compute loose abbreviation lengthPatrick Steinhardt, Mar 20, 2026
  46. 13/14 object-file: move logic to compute packed abbreviation lengthPatrick Steinhardt, Mar 20, 2026
  47. 14/14 odb: introduce generic `odb_find_abbrev_len()`Patrick Steinhardt, Mar 20, 2026
  48. Karthik NayakMar 20, 2026
  49. Patrick SteinhardtMar 20, 2026
  50. Toon ClaesMar 30, 2026
  51. Junio C HamanoMar 30, 2026
  52. Patrick SteinhardtMar 31, 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.