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 <ps@pks.im>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

2 files changed, 65 insertions, 6 deletions

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"