From 3d45483846368796d12f62d7d15daaa59d9d8a5c Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 2 Apr 2025 13:13:42 +0200 Subject: pack-bitmap: allow passing payloads to `show_reachable_fn()` The `show_reachable_fn` callback is used by a couple of functions to present reachable objects to the caller. The function does not provide a way for the caller to pass a payload though, which is functionality that we'll require in a subsequent commit. Change the callback type to accept a payload and adapt all callsites accordingly. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- pack-bitmap.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) (limited to 'pack-bitmap.c') diff --git a/pack-bitmap.c b/pack-bitmap.c index 6f7fd94c36..d192fb87da 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1625,7 +1625,7 @@ static void show_extended_objects(struct bitmap_index *bitmap_git, (obj->type == OBJ_TAG && !revs->tag_objects)) continue; - show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0); + show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0, NULL); } } @@ -1663,7 +1663,8 @@ static void init_type_iterator(struct ewah_or_iterator *it, static void show_objects_for_type( struct bitmap_index *bitmap_git, enum object_type object_type, - show_reachable_fn show_reach) + show_reachable_fn show_reach, + void *payload) { size_t i = 0; uint32_t offset; @@ -1715,7 +1716,7 @@ static void show_objects_for_type( if (bitmap_git->hashes) hash = get_be32(bitmap_git->hashes + index_pos); - show_reach(&oid, object_type, 0, hash, pack, ofs); + show_reach(&oid, object_type, 0, hash, pack, ofs, payload); } } @@ -2518,13 +2519,13 @@ void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git, { assert(bitmap_git->result); - show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable); + show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable, NULL); if (revs->tree_objects) - show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable); + show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable, NULL); if (revs->blob_objects) - show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable); + show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable, NULL); if (revs->tag_objects) - show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable); + show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable, NULL); show_extended_objects(bitmap_git, revs, show_reachable); } -- cgit v1.2.3 From 5420901bde8043a298b8ae5e5b3c3cfc1b67039b Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 2 Apr 2025 13:13:43 +0200 Subject: pack-bitmap: add function to iterate over filtered bitmapped objects Introduce a function that allows the caller to iterate over all bitmapped objects that match a given filter. This mechanism will be used in a subsequent commit to optimize object filters in git-cat-file(1). Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- pack-bitmap.c | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++------ pack-bitmap.h | 12 ++++++++++++ 2 files changed, 65 insertions(+), 6 deletions(-) (limited to 'pack-bitmap.c') diff --git a/pack-bitmap.c b/pack-bitmap.c index d192fb87da..6adb8aaa1c 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -1662,6 +1662,7 @@ static void init_type_iterator(struct ewah_or_iterator *it, static void show_objects_for_type( struct bitmap_index *bitmap_git, + struct bitmap *objects, enum object_type object_type, show_reachable_fn show_reach, void *payload) @@ -1672,8 +1673,6 @@ static void show_objects_for_type( struct ewah_or_iterator it; eword_t filter; - struct bitmap *objects = bitmap_git->result; - init_type_iterator(&it, bitmap_git, object_type); for (i = 0; i < objects->word_alloc && @@ -2025,6 +2024,50 @@ static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git, } } +int for_each_bitmapped_object(struct bitmap_index *bitmap_git, + struct list_objects_filter_options *filter, + show_reachable_fn show_reach, + void *payload) +{ + struct bitmap *filtered_bitmap = NULL; + uint32_t objects_nr; + size_t full_word_count; + int ret; + + if (!can_filter_bitmap(filter)) { + ret = -1; + goto out; + } + + objects_nr = bitmap_num_objects(bitmap_git); + full_word_count = objects_nr / BITS_IN_EWORD; + + /* We start from the all-1 bitmap and then filter down from there. */ + filtered_bitmap = bitmap_word_alloc(full_word_count + !!(objects_nr % BITS_IN_EWORD)); + memset(filtered_bitmap->words, 0xff, full_word_count * sizeof(*filtered_bitmap->words)); + for (size_t i = full_word_count * BITS_IN_EWORD; i < objects_nr; i++) + bitmap_set(filtered_bitmap, i); + + if (filter_bitmap(bitmap_git, NULL, filtered_bitmap, filter) < 0) { + ret = -1; + goto out; + } + + show_objects_for_type(bitmap_git, filtered_bitmap, + OBJ_COMMIT, show_reach, payload); + show_objects_for_type(bitmap_git, filtered_bitmap, + OBJ_TREE, show_reach, payload); + show_objects_for_type(bitmap_git, filtered_bitmap, + OBJ_BLOB, show_reach, payload); + show_objects_for_type(bitmap_git, filtered_bitmap, + OBJ_TAG, show_reach, payload); + + ret = 0; +out: + bitmap_free(filtered_bitmap); + return ret; +} + struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, int filter_provided_objects) { @@ -2519,13 +2562,17 @@ void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git, { assert(bitmap_git->result); - show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable, NULL); + show_objects_for_type(bitmap_git, bitmap_git->result, + OBJ_COMMIT, show_reachable, NULL); if (revs->tree_objects) - show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable, NULL); + show_objects_for_type(bitmap_git, bitmap_git->result, + OBJ_TREE, show_reachable, NULL); if (revs->blob_objects) - show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable, NULL); + show_objects_for_type(bitmap_git, bitmap_git->result, + OBJ_BLOB, show_reachable, NULL); if (revs->tag_objects) - show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable, NULL); + show_objects_for_type(bitmap_git, bitmap_git->result, + OBJ_TAG, show_reachable, NULL); show_extended_objects(bitmap_git, revs, show_reachable); } diff --git a/pack-bitmap.h b/pack-bitmap.h index de6bf534fe..079bae3246 100644 --- a/pack-bitmap.h +++ b/pack-bitmap.h @@ -79,6 +79,18 @@ int test_bitmap_pseudo_merges(struct repository *r); int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n); int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n); +struct list_objects_filter_options; + +/* + * Filter bitmapped objects and iterate through all resulting objects, + * executing `show_reach` for each of them. Returns `-1` in case the filter is + * not supported, `0` otherwise. + */ +int for_each_bitmapped_object(struct bitmap_index *bitmap_git, + struct list_objects_filter_options *filter, + show_reachable_fn show_reach, + void *payload); + #define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \ "GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL" -- cgit v1.2.3 From c9b94a7785b4de4e3e15d0e5b65c97337c206b81 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 2 Apr 2025 13:13:44 +0200 Subject: pack-bitmap: introduce function to check whether a pack is bitmapped Introduce a function that allows us to verify whether a pack is bitmapped or not. This functionality will be used in a subsequent commit. Helped-by: Taylor Blau Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- pack-bitmap.c | 15 +++++++++++++++ pack-bitmap.h | 7 +++++++ 2 files changed, 22 insertions(+) (limited to 'pack-bitmap.c') diff --git a/pack-bitmap.c b/pack-bitmap.c index 6adb8aaa1c..edc8f42122 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -745,6 +745,21 @@ struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx) return NULL; } +int bitmap_index_contains_pack(struct bitmap_index *bitmap, struct packed_git *pack) +{ + for (; bitmap; bitmap = bitmap->base) { + if (bitmap_is_midx(bitmap)) { + for (size_t i = 0; i < bitmap->midx->num_packs; i++) + if (bitmap->midx->packs[i] == pack) + return 1; + } else if (bitmap->pack == pack) { + return 1; + } + } + + return 0; +} + struct include_data { struct bitmap_index *bitmap_git; struct bitmap *base; diff --git a/pack-bitmap.h b/pack-bitmap.h index 079bae3246..55df1b3af5 100644 --- a/pack-bitmap.h +++ b/pack-bitmap.h @@ -67,6 +67,13 @@ struct bitmapped_pack { struct bitmap_index *prepare_bitmap_git(struct repository *r); struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx); + +/* + * Given a bitmap index, determine whether it contains the pack either directly + * or via the multi-pack-index. + */ +int bitmap_index_contains_pack(struct bitmap_index *bitmap, struct packed_git *pack); + void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits, uint32_t *trees, uint32_t *blobs, uint32_t *tags); void traverse_bitmap_commit_list(struct bitmap_index *, -- cgit v1.2.3