[RFC] Store subtree entries in the same hash map as the note entries

From

Johan Herland <johan@herland.net>

Date

Aug 13, 2009, 03:00 UTC

Message-ID

<200908130500.51135.johan@herland.net>

In-Reply-To

<200908010436.57480.johan@herland.net>

- Since a null SHA1 is also a valid subtree entry (e.g. the "00/*" subtree
  in a 2/38 fanout scheme), we can no longer use is_null_sha1() to identify
  unused entries in the hash map. Instead, a value of 0 in the new
  commit_sha1_len member indicates that this is entry is null/unused.

  There is one exception to this rule: the root notes tree which is just a
  special case of a subtree entry with 0 "valid" bytes in the commit_sha1
  member. However, this exception is acceptable, as the root entry is never
  stored in the hash map (the hash map is initialized by unpacking this
  root tree entry).

- The second special commit_sha1_len value is 255, and is used to indicate
  a subtree entry that has already been unpacked, and should therefore be
  removed from the hash map. It is expensive and non-trivial to _delete_
  an entry in the hash map, and we therefore use this special value to
  _ignore_ the entry. If/when the hash map is grown/reallocated, we simply
  avoid bringing the unpacked subtree entries into the new hash map.

Signed-off-by: Johan Herland <johan@herland.net>
---

On Wednesday 29 July 2009, Johannes Schindelin wrote:

> I know you want to have something working first and optimize then, but I
> imagined that the hashmap can actually contain the entries of the partial
> hashes, too.  You'll need to extend the data type, of course, to be able
> to say just how many digits of the SHA-1 are valid, and I guess for
> consistency you'll need to pad with 0s.

                    fanout level 0   fanout level 1   fanout level 2
  subtree-in-ll         32.71s            1.88s            0.65s
  all-in-hash-map       24.12s            1.49s            0.95s
  all-in-256-tree       20.39s            1.06s            0.63s

Have fun! :)

...Johan

 notes.c |  155 +++++++++++++++++++++++++--------------------------------------
 1 files changed, 62 insertions(+), 93 deletions(-)

diff --git a/notes.c b/notes.c
index 7e9dc49..34b8892 100644
--- a/notes.c
+++ b/notes.c
@@ -9,6 +9,15 @@
 struct entry {
 	unsigned char commit_sha1[20];
 	unsigned char notes_sha1[20];
+	/*
+	 * The following member can have the following values:
+	 * 0    - This is a NULL/blank entry in the hash_map
+	 *        (Exception: The root_tree entry in initialize_hash_map())
+	 * 1-19 - This is a subtree with the given number of valid prefix bytes
+	 * 20   - This is a note
+	 * 255  - This is a subtree which has been unpacked, please ignore
+	 */
+	unsigned char commit_sha1_len;
 };
 
 struct hash_map {
@@ -16,43 +25,35 @@ struct hash_map {
 	off_t count, size;
 };
 
-struct subtree_entry {
-	/*
-	 * SHA1 prefix is stored in the first 19 bytes (w/trailing NUL bytes);
-	 * length of SHA1 prefix is stored in the last byte
-	 */
-	unsigned char sha1_prefix_w_len[20];
-	unsigned char subtree_sha1[20];
-	struct subtree_entry *next;
-};
-
 static int initialized;
 static struct hash_map hash_map;
-static struct subtree_entry *subtree_list;
 
 static int hash_index(struct hash_map *map, const unsigned char *sha1)
 {
 	int i = ((*(unsigned int *)sha1) % map->size);
 
 	for (;;) {
-		unsigned char *current = map->entries[i].commit_sha1;
+		struct entry *current = &(map->entries[i]);
 
-		if (!hashcmp(sha1, current))
-			return i;
-
-		if (is_null_sha1(current))
+		if (!current->commit_sha1_len)
 			return -1 - i;
 
+		if (!hashcmp(sha1, current->commit_sha1)
+		 && current->commit_sha1_len <= 20)
+			return i;
+
 		if (++i == map->size)
 			i = 0;
 	}
 }
 
 static void add_entry(const unsigned char *commit_sha1,
-		const unsigned char *notes_sha1)
+		const unsigned char *notes_sha1,
+		unsigned char commit_sha1_len)
 {
 	int index;
 
+	assert(commit_sha1_len > 0 && commit_sha1_len <= 20);
 	if (hash_map.count + 1 > hash_map.size >> 1) {
 		int i, old_size = hash_map.size;
 		struct entry *old = hash_map.entries;
@@ -61,13 +62,20 @@ static void add_entry(const unsigned char *commit_sha1,
 		hash_map.entries = (struct entry *)
 			xcalloc(sizeof(struct entry), hash_map.size);
 
-		for (i = 0; i < old_size; i++)
-			if (!is_null_sha1(old[i].commit_sha1)) {
+		for (i = 0; i < old_size; i++) {
+			switch (old[i].commit_sha1_len) {
+			case 255:
+				hash_map.count--;
+				/* fall through */
+			case 0:
+				continue;
+			default:
 				index = -1 - hash_index(&hash_map,
 						old[i].commit_sha1);
 				memcpy(hash_map.entries + index, old + i,
 					sizeof(struct entry));
 			}
+		}
 		free(old);
 	}
 
@@ -79,6 +87,7 @@ static void add_entry(const unsigned char *commit_sha1,
 
 	hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
 	hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+	hash_map.entries[index].commit_sha1_len = commit_sha1_len;
 }
 
 /*
@@ -110,22 +119,26 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
 	return len;
 }
 
-static void load_subtree(struct subtree_entry *se)
+static void load_subtree(struct entry *subtree)
 {
 	unsigned char commit_sha1[20];
 	unsigned int prefix_len;
 	void *buf;
 	struct tree_desc desc;
 	struct name_entry entry;
-	struct subtree_entry *tmp_list = NULL, *tmp_last = NULL;
 
-	buf = fill_tree_descriptor(&desc, se->subtree_sha1);
+	buf = fill_tree_descriptor(&desc, subtree->notes_sha1);
 	if (!buf)
 		die("Could not read %s for notes-index",
-		     sha1_to_hex(se->subtree_sha1));
+		     sha1_to_hex(subtree->notes_sha1));
+
+	prefix_len = subtree->commit_sha1_len;
+	assert(prefix_len < 20);
+	memcpy(commit_sha1, subtree->commit_sha1, prefix_len);
+
+	/* Invalidate this subtree from further consideration */
+	subtree->commit_sha1_len = 255;
 
-	prefix_len = se->sha1_prefix_w_len[19];
-	memcpy(commit_sha1, se->sha1_prefix_w_len, prefix_len);
 	while (tree_entry(&desc, &entry)) {
 		int len = get_sha1_hex_segment(entry.path, strlen(entry.path),
 				commit_sha1 + prefix_len, 20 - prefix_len);
@@ -133,110 +146,66 @@ static void load_subtree(struct subtree_entry *se)
 			continue; /* entry.path is not a SHA1 sum. Skip */
 		len += prefix_len;
 
-		/* If commit SHA1 is complete, assume note object */
-		if (len == 20)
-			add_entry(commit_sha1, entry.sha1);
-		/* If commit SHA1 is incomplete, assume note subtree */
-		else if (len < 20 && entry.mode == S_IFDIR) {
-			struct subtree_entry *n = (struct subtree_entry *)
-				xcalloc(sizeof(struct subtree_entry), 1);
-			hashcpy(n->sha1_prefix_w_len, commit_sha1);
-			n->sha1_prefix_w_len[19] = (unsigned char) len;
-			hashcpy(n->subtree_sha1, entry.sha1);
-
-			if (!tmp_list) {
-				tmp_list = n;
-				tmp_last = n;
-			}
-			else {
-				assert(!tmp_last->next);
-				assert(hashcmp(n->sha1_prefix_w_len,
-					tmp_last->sha1_prefix_w_len) > 0);
-				tmp_last->next = n;
-				tmp_last = n;
-			}
-		}
+		if (len == 20 || (len < 20 && entry.mode == S_IFDIR))
+			add_entry(commit_sha1, entry.sha1, len);
 	}
 	free(buf);
-	if (tmp_list) {
-		/* insert tmp_list immediately after se */
-		assert(hashcmp(tmp_list->sha1_prefix_w_len,
-				se->sha1_prefix_w_len) > 0);
-		if (se->next) {
-			assert(hashcmp(se->next->sha1_prefix_w_len,
-					tmp_last->sha1_prefix_w_len) > 0);
-			tmp_last->next = se->next;
-		}
-		se->next = tmp_list;
-	}
 }
 
 static void initialize_hash_map(const char *notes_ref_name)
 {
 	unsigned char sha1[20], commit_sha1[20];
 	unsigned mode;
-	struct subtree_entry root_tree;
+	struct entry root_tree;
 
 	if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
 	    get_tree_entry(commit_sha1, "", sha1, &mode))
 		return;
 
-	hashclr(root_tree.sha1_prefix_w_len);
-	hashcpy(root_tree.subtree_sha1, sha1);
-	root_tree.next = NULL;
+	hashclr(root_tree.commit_sha1);
+	hashcpy(root_tree.notes_sha1, sha1);
+	root_tree.commit_sha1_len = 0;
 	load_subtree(&root_tree);
-	subtree_list = root_tree.next;
 }
 
-/*
- * Compare the given commit SHA1 against the given subtree entry.
- * Return -1 if the commit SHA1 cannot exist within the given subtree, or any
- * subtree following it.
- * Return 0 if the commit SHA1 _may_ exist within the given subtree.
- * Return 1 if the commit SHA1 cannot exist within the given subtree, but may
- * exist within a subtree following it.
- */
-static int commit_subtree_cmp(const unsigned char *commit_sha1,
-		const struct subtree_entry *entry)
+static struct entry *lookup_subtree(const unsigned char *commit_sha1)
 {
-	unsigned int prefix_len = entry->sha1_prefix_w_len[19];
-	return memcmp(commit_sha1, entry->sha1_prefix_w_len, prefix_len);
-}
+	unsigned char prefix_sha1[20];
+	unsigned char i;
+	int index;
 
-static struct subtree_entry *lookup_subtree(const unsigned char *commit_sha1)
-{
-	struct subtree_entry *found = NULL, *cur = subtree_list;
-	while (cur) {
-		int cmp = commit_subtree_cmp(commit_sha1, cur);
-		if (!cmp)
-			found = cur;
-		if (cmp < 0)
-			break;
-		cur = cur->next;
+	hashcpy(prefix_sha1, commit_sha1);
+	for (i = 19; i; --i) {
+		prefix_sha1[i] = 0;
+		index = hash_index(&hash_map, prefix_sha1);
+		if (index >= 0 && hash_map.entries[index].commit_sha1_len == i)
+			return &(hash_map.entries[index]);
 	}
-	return found;
+	return NULL;
 }
 
 static unsigned char *lookup_notes(const unsigned char *commit_sha1)
 {
 	int index;
-	struct subtree_entry *subtree;
+	struct entry *subtree;
+
+	if (!hash_map.size)
+		return NULL;
 
 	/* First, try to find the commit SHA1 directly in hash map */
-	index = hash_map.size ? hash_index(&hash_map, commit_sha1) : -1;
+	index = hash_index(&hash_map, commit_sha1);
 	if (index >= 0)
 		return hash_map.entries[index].notes_sha1;
 
 	/* Next, try finding a subtree that may contain the commit SHA1 */
 	subtree = lookup_subtree(commit_sha1);
 
-	/* Give up if no subtree found, or if subtree is already loaded */
-	if (!subtree || is_null_sha1(subtree->subtree_sha1))
+	/* Give up if no subtree found */
+	if (!subtree)
 		return NULL;
 
 	/* Load subtree into hash_map, and retry lookup recursively */
 	load_subtree(subtree);
-	hashclr(subtree->subtree_sha1);
 	return lookup_notes(commit_sha1);
 }
 

-- 
1.6.4.rc3.138.ga6b98.dirty