From 1382e54a9c9e5f98271a943af9c10299c6ba934b Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Fri, 20 Mar 2026 08:07:27 +0100 Subject: oidtree: modernize the code a bit 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 Signed-off-by: Junio C Hamano --- oidtree.c | 61 +++++++++++++++++++++++++++++++------------------------------ 1 file changed, 31 insertions(+), 30 deletions(-) (limited to 'oidtree.c') 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); } -- cgit v1.3 From fe446b01aeaab307adcbfb39d4aaa72c37afbcda Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Fri, 20 Mar 2026 08:07:28 +0100 Subject: oidtree: extend iteration to allow for arbitrary return codes 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 Signed-off-by: Junio C Hamano --- cbtree.c | 21 ++++++++++++--------- cbtree.h | 17 +++++++++-------- object-name.c | 4 ++-- oidtree.c | 12 ++++++------ oidtree.h | 18 ++++++++++++------ t/unit-tests/u-oidtree.c | 4 ++-- 6 files changed, 43 insertions(+), 33 deletions(-) (limited to 'oidtree.c') 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..c374b1b3db 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,15 @@ 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); +/* + * Callback invoked by `cb_each()` for each node in the critbit tree. A return + * value of 0 will cause the iteration to continue, a non-zero return code will + * cause iteration to abort. The error code will be relayed back from + * `cb_each()` in that case. + */ +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 -- cgit v1.3