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

[FFT/PATCH 12/11] object.c: make object hash implementation more opaque

From
Junio C Hamano <gitster@pobox.com>
Date
Aug 11, 2011, 23:33 UTC
Message-ID
<7vd3gbplpf.fsf@alter.siamese.dyndns.org>
In-Reply-To
<1313085196-13249-1-git-send-email-gitster@pobox.com>

There are only a handful of callers that want to enumerate all the objects known to the process. Unfortunately they at least know that the object hash can be iterated over with an integer index.

Introduce an opaque "struct object_cursor" type to hide the implementation detail, so that later we may be able to switch to an implementation that is not a based on a flat and sparse array that is used as a hash table.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 * This is not necessary for the purpose of the earlier "cuckoo" update,
   as that still is an implementation based on a single flat sparse array,
   but I am throwing it out as a food-for-thought.
   - The function "object_cursor_max()" returns obj_hash_size, but it only
     is used by fsck to give an overestimate of the number of objects to
     check. We could change it to return nr_obj to give a more precise
     number, but I kept the behaviour bug-for-bug compatible for now.
   - Later if we need to libify the in-core object store, we would wrap
     obj_hash, nr_obj and obj_hash_size into a single "struct obj_ctx"
     (the context of a series of git operations that access the object
     store), and have a pointer to it in the "struct object_cursor".
     get_object_cursor() API function may get a new variant that takes a
     pointer to "struct obj_ctx" to switch between contexts, etc.
   This patch is designed to apply before all the others, outside the main
   series. If this "more opaque" approach is going in a desirable
   direction, the "cuckoo" series should be rebased on top of this.
 builtin/fsck.c       |   17 ++++++++---------
 builtin/index-pack.c |   10 ++++++----
 builtin/name-rev.c   |   12 +++++-------
 object.c             |   34 ++++++++++++++++++++++++++++++----
 object.h             |    7 +++++--
 5 files changed, 54 insertions(+), 26 deletions(-)
diff --git a/builtin/fsck.c b/builtin/fsck.c
index 5ae0366..a71b36d 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -266,22 +266,21 @@ static void check_object(struct object *obj)
 
 static void check_connectivity(void)
 {
-	int i, max;
+	struct object_cursor *objects;
+	struct object *obj;
 
 	/* Traverse the pending reachable objects */
 	traverse_reachable();
 
 	/* Look up all the requirements, warn about missing objects.. */
-	max = get_max_object_index();
+	objects = get_object_cursor();
 	if (verbose)
-		fprintf(stderr, "Checking connectivity (%d objects)\n", max);
-
-	for (i = 0; i < max; i++) {
-		struct object *obj = get_indexed_object(i);
+		fprintf(stderr, "Checking connectivity (%d objects)\n",
+			object_cursor_max(objects));
 
-		if (obj)
-			check_object(obj);
-	}
+	while ((obj = get_next_object(objects)) != NULL)
+		check_object(obj);
+	free_object_cursor(objects);
 }
 
 static int fsck_sha1(const unsigned char *sha1)
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index e40451f..ca172d5 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -104,11 +104,13 @@ static void check_object(struct object *obj)
 
 static void check_objects(void)
 {
-	unsigned i, max;
+	struct object_cursor *objects;
+	struct object *obj;
 
-	max = get_max_object_index();
-	for (i = 0; i < max; i++)
-		check_object(get_indexed_object(i));
+	objects = get_object_cursor();
+	while ((obj = get_next_object(objects)) != NULL)
+		check_object(obj);
+	free_object_cursor(objects);
 }
 
 
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 31f5c1c..ec6b952 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -284,16 +284,14 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 			name_rev_line(p, &data);
 		}
 	} else if (all) {
-		int i, max;
+		struct object_cursor *objects;
+		struct object *obj;
 
-		max = get_max_object_index();
-		for (i = 0; i < max; i++) {
-			struct object *obj = get_indexed_object(i);
-			if (!obj)
-				continue;
+		objects = get_object_cursor();
+		while ((obj = get_next_object(objects)) != NULL)
 			show_name(obj, NULL,
 				  always, allow_undefined, data.name_only);
-		}
+		free_object_cursor(objects);
 	} else {
 		int i;
 		for (i = 0; i < revs.nr; i++)
diff --git a/object.c b/object.c
index 31976b5..986d243 100644
--- a/object.c
+++ b/object.c
@@ -8,14 +8,40 @@
 static struct object **obj_hash;
 static int nr_objs, obj_hash_size;
 
-unsigned int get_max_object_index(void)
+struct object_cursor {
+	int cursor_at;
+};
+
+struct object_cursor *get_object_cursor(void)
 {
-	return obj_hash_size;
+	struct object_cursor *objects;
+	objects = xmalloc(sizeof(*objects));
+	objects->cursor_at = 0;
+	return objects;
+}
+
+int object_cursor_max(struct object_cursor *objects)
+{
+	return obj_hash_size; /* nr_objs is more precise, though */
+}
+
+struct object *get_next_object(struct object_cursor *objects)
+{
+	int i = objects->cursor_at;
+	while (i < obj_hash_size) {
+		struct object *obj = obj_hash[i++];
+		if (!obj)
+			continue;
+		objects->cursor_at = i;
+		return obj;
+	}
+	objects->cursor_at = i;
+	return NULL;
 }
 
-struct object *get_indexed_object(unsigned int idx)
+void free_object_cursor(struct object_cursor *objects)
 {
-	return obj_hash[idx];
+	free(objects);
 }
 
 static const char *object_type_strings[] = {
diff --git a/object.h b/object.h
index b6618d9..fdd14a1 100644
--- a/object.h
+++ b/object.h
@@ -35,8 +35,11 @@ struct object {
 extern const char *typename(unsigned int type);
 extern int type_from_string(const char *str);
 
-extern unsigned int get_max_object_index(void);
-extern struct object *get_indexed_object(unsigned int);
+struct object_cursor; /* opaque */
+extern struct object_cursor *get_object_cursor(void);
+extern int object_cursor_max(struct object_cursor *);
+extern struct object *get_next_object(struct object_cursor *);
+extern void free_object_cursor(struct object_cursor *);
 
 /*
  * This can be used to see if we have heard of the object before, but
Previous: Junio C HamanoNext: Thomas Rast
Message 13 of 15 in “Micro-optimizing lookup_object()”
  1. 00/11 Micro-optimizing lookup_object()Junio C Hamano, Aug 11, 2011
  2. 01/11 object.c: code movement for readabilityJunio C Hamano, Aug 11, 2011
  3. 02/11 object.c: remove duplicated code for object hashingJunio C Hamano, Aug 11, 2011
  4. 03/11 pack-objects --count-onlyJunio C Hamano, Aug 11, 2011
  5. 04/11 object: next_size() helper for readabilityJunio C Hamano, Aug 11, 2011
  6. 05/11 object hash: we know the table size is a power of twoJunio C Hamano, Aug 11, 2011
  7. 06/11 object: growing the hash-table more aggressively does not help muchJunio C Hamano, Aug 11, 2011
  8. 07/11 object: try naive cuckoo hashingJunio C Hamano, Aug 11, 2011
  9. 08/11 object: try 5-way cuckoo -- use all 20-bytes of SHA-1Junio C Hamano, Aug 11, 2011
  10. 09/11 object: try 4-way cuckooJunio C Hamano, Aug 11, 2011
  11. 10/11 object: try 3-way cuckooJunio C Hamano, Aug 11, 2011
  12. 11/11 object: try 2-way cuckoo againJunio C Hamano, Aug 11, 2011
  13. 12/11 object.c: make object hash implementation more opaqueJunio C Hamano, Aug 11, 2011
  14. git_checkattr() is inefficient when repeated [Re: [PATCH 00/11] Micro-optimizing lookup_object()]Thomas Rast, Aug 12, 2011
  15. Junio C HamanoAug 15, 2011

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.