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

[PATCH 02/14] oidtree: extend iteration to allow for arbitrary return codes

From
Patrick Steinhardt <ps@pks.im>
Date
Mar 19, 2026, 06:53 UTC
Message-ID
<20260319-b4-pks-odb-source-abbrev-v1-2-5ddebad292b0@pks.im>
In-Reply-To
<20260319-b4-pks-odb-source-abbrev-v1-0-5ddebad292b0@pks.im>

The interface `cb_each()` iterates through a crit-bit tree and calls a specific callback function for each of the contained items. The callback function is expected to return either:

  - `CB_CONTINUE` in case iteration shall continue.
  - `CB_BREAK` to abort iteration.

This is needlessly restrictive though, as callers may want to return arbitrary values and have them be bubbled up to the `cb_each()` call site. In fact, this is a rather common pattern we have: whenever such a callback function returns a non-zero error code, we abort iteration and bubble up the code as-is.

Refactor both the crit-bit tree and oidtree subsystems to behave accordingly.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 cbtree.c                 | 21 ++++++++++++---------
 cbtree.h                 | 11 +++--------
 object-name.c            |  4 ++--
 oidtree.c                | 12 ++++++------
 oidtree.h                | 18 ++++++++++++------
 t/unit-tests/u-oidtree.c |  4 ++--
 6 files changed, 37 insertions(+), 33 deletions(-)
diff --git a/cbtree.c b/cbtree.c
index cf8cf75b89..4ab794bddc 100644
--- a/cbtree.c
+++ b/cbtree.c
@@ -96,26 +96,28 @@ struct cb_node *cb_lookup(struct cb_tree *t, const uint8_t *k, size_t klen)
 	return p && !memcmp(p->k, k, klen) ? p : NULL;
 }
 
-static enum cb_next cb_descend(struct cb_node *p, cb_iter fn, void *arg)
+static int cb_descend(struct cb_node *p, cb_iter fn, void *arg)
 {
 	if (1 & (uintptr_t)p) {
 		struct cb_node *q = cb_node_of(p);
-		enum cb_next n = cb_descend(q->child[0], fn, arg);
-
-		return n == CB_BREAK ? n : cb_descend(q->child[1], fn, arg);
+		int ret = cb_descend(q->child[0], fn, arg);
+		if (ret)
+			return ret;
+		return cb_descend(q->child[1], fn, arg);
 	} else {
 		return fn(p, arg);
 	}
 }
 
-void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
-			cb_iter fn, void *arg)
+int cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
+	    cb_iter fn, void *arg)
 {
 	struct cb_node *p = t->root;
 	struct cb_node *top = p;
 	size_t i = 0;
 
-	if (!p) return; /* empty tree */
+	if (!p)
+		return 0; /* empty tree */
 
 	/* Walk tree, maintaining top pointer */
 	while (1 & (uintptr_t)p) {
@@ -130,7 +132,8 @@ void cb_each(struct cb_tree *t, const uint8_t *kpfx, size_t klen,
 
 	for (i = 0; i < klen; i++) {
 		if (p->k[i] != kpfx[i])
-			return; /* "best" match failed */
+			return 0; /* "best" match failed */
 	}
-	cb_descend(top, fn, arg);
+
+	return cb_descend(top, fn, arg);
 }
diff --git a/cbtree.h b/cbtree.h
index 43193abdda..4f644d6e45 100644
--- a/cbtree.h
+++ b/cbtree.h
@@ -30,11 +30,6 @@ struct cb_tree {
 	struct cb_node *root;
 };
 
-enum cb_next {
-	CB_CONTINUE = 0,
-	CB_BREAK = 1
-};
-
 #define CBTREE_INIT { 0 }
 
 static inline void cb_init(struct cb_tree *t)
@@ -46,9 +41,9 @@ static inline void cb_init(struct cb_tree *t)
 struct cb_node *cb_lookup(struct cb_tree *, const uint8_t *k, size_t klen);
 struct cb_node *cb_insert(struct cb_tree *, struct cb_node *, size_t klen);
 
-typedef enum cb_next (*cb_iter)(struct cb_node *, void *arg);
+typedef int (*cb_iter)(struct cb_node *, void *arg);
 
-void cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen,
-		cb_iter, void *arg);
+int cb_each(struct cb_tree *, const uint8_t *kpfx, size_t klen,
+	    cb_iter, void *arg);
 
 #endif /* CBTREE_H */
diff --git a/object-name.c b/object-name.c
index e5adec4c9d..a24a1b48e1 100644
--- a/object-name.c
+++ b/object-name.c
@@ -103,12 +103,12 @@ static void update_candidates(struct disambiguate_state *ds, const struct object
 
 static int match_hash(unsigned, const unsigned char *, const unsigned char *);
 
-static enum cb_next match_prefix(const struct object_id *oid, void *arg)
+static int match_prefix(const struct object_id *oid, void *arg)
 {
 	struct disambiguate_state *ds = arg;
 	/* no need to call match_hash, oidtree_each did prefix match */
 	update_candidates(ds, oid);
-	return ds->ambiguous ? CB_BREAK : CB_CONTINUE;
+	return ds->ambiguous;
 }
 
 static void find_short_object_filename(struct disambiguate_state *ds)
diff --git a/oidtree.c b/oidtree.c
index a4d10cd429..ab9fe7ec7a 100644
--- a/oidtree.c
+++ b/oidtree.c
@@ -71,7 +71,7 @@ struct oidtree_each_data {
 	uint8_t last_byte;
 };
 
-static enum cb_next iter(struct cb_node *n, void *cb_data)
+static int iter(struct cb_node *n, void *cb_data)
 {
 	struct oidtree_each_data *data = cb_data;
 	struct object_id k;
@@ -80,18 +80,18 @@ static enum cb_next iter(struct cb_node *n, void *cb_data)
 	memcpy(&k, n->k, sizeof(k));
 
 	if (data->algo != GIT_HASH_UNKNOWN && data->algo != k.algo)
-		return CB_CONTINUE;
+		return 0;
 
 	if (data->last_nibble_at) {
 		if ((k.hash[*data->last_nibble_at] ^ data->last_byte) & 0xf0)
-			return CB_CONTINUE;
+			return 0;
 	}
 
 	return data->cb(&k, data->cb_data);
 }
 
-void oidtree_each(struct oidtree *ot, const struct object_id *prefix,
-		  size_t prefix_hex_len, oidtree_each_cb cb, void *cb_data)
+int oidtree_each(struct oidtree *ot, const struct object_id *prefix,
+		 size_t prefix_hex_len, oidtree_each_cb cb, void *cb_data)
 {
 	struct oidtree_each_data data = {
 		.cb = cb,
@@ -106,5 +106,5 @@ void oidtree_each(struct oidtree *ot, const struct object_id *prefix,
 		data.last_nibble_at = &klen;
 	}
 
-	cb_each(&ot->tree, prefix->hash, klen, iter, &data);
+	return cb_each(&ot->tree, prefix->hash, klen, iter, &data);
 }
diff --git a/oidtree.h b/oidtree.h
index 0651401017..2b7bad2e60 100644
--- a/oidtree.h
+++ b/oidtree.h
@@ -35,16 +35,22 @@ 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);
+/*
+ * 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 *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.
+ *
+ * Returns any non-zero exit code from the provided callback function.
  */
-void oidtree_each(struct oidtree *ot,
-		  const struct object_id *prefix, size_t prefix_hex_len,
-		  oidtree_each_cb cb, void *cb_data);
+int 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 def47c6795..d4d05c7dc3 100644
--- a/t/unit-tests/u-oidtree.c
+++ b/t/unit-tests/u-oidtree.c
@@ -38,7 +38,7 @@ struct expected_hex_iter {
 	const char *query;
 };
 
-static enum cb_next check_each_cb(const struct object_id *oid, void *data)
+static int check_each_cb(const struct object_id *oid, void *data)
 {
 	struct expected_hex_iter *hex_iter = data;
 	struct object_id expected;
@@ -49,7 +49,7 @@ static enum cb_next check_each_cb(const struct object_id *oid, void *data)
 			 &expected);
 	cl_assert_equal_s(oid_to_hex(oid), oid_to_hex(&expected));
 	hex_iter->i += 1;
-	return CB_CONTINUE;
+	return 0;
 }
 
 LAST_ARG_MUST_BE_NULL
-- 
2.53.0.1055.ga2ffed1127.dirty
Previous: Patrick SteinhardtNext: Junio C Hamano
Message 7 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.