[PATCHv4 08/12] Teach the notes lookup code to parse notes trees with various fanout schemes

From

Johan Herland <johan@herland.net>

Date

Aug 27, 2009, 01:43 UTC

Message-ID

<1251337437-16947-9-git-send-email-johan@herland.net>

In-Reply-To

<1251337437-16947-1-git-send-email-johan@herland.net>

The semantics used when parsing notes trees (with regards to fanout subtrees)
follow Dscho's proposal fairly closely:
- No concatenation/merging of notes is performed. If there are several notes
  objects referencing a given commit, only one of those objects are used.
- If a notes object for a given commit is present in the "root" notes tree,
  no subtrees are consulted; the object in the root tree is used directly.
- If there are more than one subtree that prefix-matches the given commit,
  only the subtree with the longest matching prefix is consulted. This
  means that if the given commit is e.g. "deadbeef", and the notes tree have
  subtrees "de" and "dead", then the following paths in the notes tree are
  searched: "deadbeef", "dead/beef". Note that "de/adbeef" is NOT searched.
- Fanout directories (subtrees) must references a whole number of bytes
  from the SHA1 sum they subdivide. E.g. subtrees "dead" and "de" are
  acceptable; "d" and "dea" are not.
- Multiple levels of fanout are allowed. All the above rules apply
  recursively. E.g. "de/adbeef" is preferred over "de/adbe/ef", etc.

Cc: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Johan Herland <johan@herland.net>
---
 notes.c |  294 +++++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 228 insertions(+), 66 deletions(-)

diff --git a/notes.c b/notes.c
index 9172154..a637056 100644
--- a/notes.c
+++ b/notes.c
@@ -6,103 +6,265 @@
 #include "strbuf.h"
 #include "tree-walk.h"
 
-struct entry {
-	unsigned char commit_sha1[20];
-	unsigned char notes_sha1[20];
+/*
+ * Use a non-balancing simple 16-tree structure with struct int_node as
+ * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
+ * 16-array of pointers to its children.
+ * The bottom 2 bits of each pointer is used to identify the pointer type
+ * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
+ * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
+ * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
+ * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
+ *
+ * The root node is a statically allocated struct int_node.
+ */
+struct int_node {
+	void *a[16];
 };
 
-struct hash_map {
-	struct entry *entries;
-	off_t count, size;
+/*
+ * Leaf nodes come in two variants, note entries and subtree entries,
+ * distinguished by the LSb of the leaf node pointer (see above).
+ * As a note entry, the key is the SHA1 of the referenced commit, and the
+ * value is the SHA1 of the note object.
+ * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
+ * referenced commit, using the last byte of the key to store the length of
+ * the prefix. The value is the SHA1 of the tree object containing the notes
+ * subtree.
+ */
+struct leaf_node {
+	unsigned char key_sha1[20];
+	unsigned char val_sha1[20];
 };
 
+#define PTR_TYPE_NULL     0
+#define PTR_TYPE_INTERNAL 1
+#define PTR_TYPE_NOTE     2
+#define PTR_TYPE_SUBTREE  3
+
+#define GET_PTR_TYPE(ptr)       ((uintptr_t) (ptr) & 3)
+#define CLR_PTR_TYPE(ptr)       ((void *) ((uintptr_t) (ptr) & ~3))
+#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
+
+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((n & 0x01) << 2)) & 0x0f)
+
+#define MATCHING_SUBTREE(key_sha1, subtree_sha1) \
+	(!memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
+
 static int initialized;
-static struct hash_map hash_map;
 
-static int hash_index(struct hash_map *map, const unsigned char *sha1)
-{
-	int i = ((*(unsigned int *)sha1) % map->size);
+static struct int_node root_node;
 
-	for (;;) {
-		unsigned char *current = map->entries[i].commit_sha1;
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+		unsigned int n);
 
-		if (!hashcmp(sha1, current))
-			return i;
+/*
+ * To find a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ *    - If a[n] is an int_node, recurse into that node and increment n
+ *    - If a leaf_node with matching key, return leaf_node (assert note entry)
+ *    - If a matching subtree entry, unpack that subtree entry (and remove it);
+ *      restart search at the current level.
+ *    - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.
+ *      Backtrack out of the recursion, one level at a time and check a[0]:
+ *      - If a[0] at the current level is a matching subtree entry, unpack that
+ *        subtree entry (and remove it); restart search at the current level.
+ */
+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,
+		const unsigned char *key_sha1)
+{
+	struct leaf_node *l;
+	unsigned char i = GET_NIBBLE(n, key_sha1);
+	void *p = tree->a[i];
 
-		if (is_null_sha1(current))
-			return -1 - i;
+	switch(GET_PTR_TYPE(p)) {
+	case PTR_TYPE_INTERNAL:
+		l = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);
+		if (l)
+			return l;
+		break;
+	case PTR_TYPE_NOTE:
+		l = (struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!hashcmp(key_sha1, l->key_sha1))
+			return l; /* return note object matching given key */
+		break;
+	case PTR_TYPE_SUBTREE:
+		l = (struct leaf_node *) CLR_PTR_TYPE(p);
+		if (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {
+			/* unpack tree and resume search */
+			tree->a[i] = NULL;
+			load_subtree(l, tree, n);
+			free(l);
+			return note_tree_find(tree, n, key_sha1);
+		}
+		break;
+	case PTR_TYPE_NULL:
+	default:
+		assert(!p);
+		break;
+	}
 
-		if (++i == map->size)
-			i = 0;
+	/*
+	 * Did not find key at this (or any lower) level.
+	 * Check if there's a matching subtree entry in tree->a[0].
+	 * If so, unpack tree and resume search.
+	 */
+	p = tree->a[0];
+	if (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)
+		return NULL;
+	l = (struct leaf_node *) CLR_PTR_TYPE(p);
+	if (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {
+		/* unpack tree and resume search */
+		tree->a[0] = NULL;
+		load_subtree(l, tree, n);
+		free(l);
+		return note_tree_find(tree, n, key_sha1);
 	}
+	return NULL;
 }
 
-static void add_entry(const unsigned char *commit_sha1,
-		const unsigned char *notes_sha1)
+/*
+ * To insert a leaf_node:
+ * 1. Start at the root node, with n = 0
+ * 2. Use the nth nibble of the key as an index into a:
+ *    - If a[n] is NULL, store the tweaked pointer directly into a[n]
+ *    - If a[n] is an int_node, recurse into that node and increment n
+ *    - If a[n] is a leaf_node:
+ *      1. Check if they're equal, and handle that (abort? overwrite?)
+ *      2. Create a new int_node, and store both leaf_nodes there
+ *      3. Store the new int_node into a[n].
+ */
+static int note_tree_insert(struct int_node *tree, unsigned char n,
+		const struct leaf_node *entry, unsigned char type)
 {
-	int index;
-
-	if (hash_map.count + 1 > hash_map.size >> 1) {
-		int i, old_size = hash_map.size;
-		struct entry *old = hash_map.entries;
-
-		hash_map.size = old_size ? old_size << 1 : 64;
-		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)) {
-				index = -1 - hash_index(&hash_map,
-						old[i].commit_sha1);
-				memcpy(hash_map.entries + index, old + i,
-					sizeof(struct entry));
-			}
-		free(old);
+	struct int_node *new_node;
+	const struct leaf_node *l;
+	int ret;
+	unsigned char i = GET_NIBBLE(n, entry->key_sha1);
+	void *p = tree->a[i];
+	assert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);
+	switch(GET_PTR_TYPE(p)) {
+	case PTR_TYPE_NULL:
+		assert(!p);
+		tree->a[i] = SET_PTR_TYPE(entry, type);
+		return 0;
+	case PTR_TYPE_INTERNAL:
+		return note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);
+	default:
+		assert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||
+			GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);
+		l = (const struct leaf_node *) CLR_PTR_TYPE(p);
+		if (!hashcmp(entry->key_sha1, l->key_sha1))
+			return -1; /* abort insert on matching key */
+		new_node = (struct int_node *)
+			xcalloc(sizeof(struct int_node), 1);
+		ret = note_tree_insert(new_node, n + 1,
+			CLR_PTR_TYPE(p), GET_PTR_TYPE(p));
+		if (ret) {
+			free(new_node);
+			return -1;
+		}
+		tree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
+		return note_tree_insert(new_node, n + 1, entry, type);
 	}
+}
 
-	index = hash_index(&hash_map, commit_sha1);
-	if (index < 0) {
-		index = -1 - index;
-		hash_map.count++;
+/*
+ * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
+ * - hex      - Partial SHA1 segment in ASCII hex format
+ * - hex_len  - Length of above segment. Must be multiple of 2 between 0 and 40
+ * - sha1     - Partial SHA1 value is written here
+ * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
+ * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format).
+ * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
+ * Pads sha1 with NULs up to sha1_len (not included in returned length).
+ */
+static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
+		unsigned char *sha1, unsigned int sha1_len)
+{
+	unsigned int i, len = hex_len >> 1;
+	if (hex_len % 2 != 0 || len > sha1_len)
+		return -1;
+	for (i = 0; i < len; i++) {
+		unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
+		if (val & ~0xff)
+			return -1;
+		*sha1++ = val;
+		hex += 2;
 	}
+	for (; i < sha1_len; i++)
+		*sha1++ = 0;
+	return len;
+}
+
+static void load_subtree(struct leaf_node *subtree, struct int_node *node,
+		unsigned int n)
+{
+	unsigned char commit_sha1[20];
+	unsigned int prefix_len;
+	int status;
+	void *buf;
+	struct tree_desc desc;
+	struct name_entry entry;
+
+	buf = fill_tree_descriptor(&desc, subtree->val_sha1);
+	if (!buf)
+		die("Could not read %s for notes-index",
+		     sha1_to_hex(subtree->val_sha1));
+
+	prefix_len = subtree->key_sha1[19];
+	assert(prefix_len * 2 >= n);
+	memcpy(commit_sha1, subtree->key_sha1, 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);
+		if (len < 0)
+			continue; /* entry.path is not a SHA1 sum. Skip */
+		len += prefix_len;
 
-	hashcpy(hash_map.entries[index].commit_sha1, commit_sha1);
-	hashcpy(hash_map.entries[index].notes_sha1, notes_sha1);
+		/*
+		 * If commit SHA1 is complete (len == 20), assume note object
+		 * If commit SHA1 is incomplete (len < 20), assume note subtree
+		 */
+		if (len <= 20) {
+			unsigned char type = PTR_TYPE_NOTE;
+			struct leaf_node *l = (struct leaf_node *)
+				xcalloc(sizeof(struct leaf_node), 1);
+			hashcpy(l->key_sha1, commit_sha1);
+			hashcpy(l->val_sha1, entry.sha1);
+			if (len < 20) {
+				l->key_sha1[19] = (unsigned char) len;
+				type = PTR_TYPE_SUBTREE;
+			}
+			status = note_tree_insert(node, n, l, type);
+			assert(!status);
+		}
+	}
+	free(buf);
 }
 
-static void initialize_hash_map(const char *notes_ref_name)
+static void initialize_notes(const char *notes_ref_name)
 {
 	unsigned char sha1[20], commit_sha1[20];
 	unsigned mode;
-	struct tree_desc desc;
-	struct name_entry entry;
-	void *buf;
+	struct leaf_node root_tree;
 
 	if (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||
 	    get_tree_entry(commit_sha1, "", sha1, &mode))
 		return;
 
-	buf = fill_tree_descriptor(&desc, sha1);
-	if (!buf)
-		die("Could not read %s for notes-index", sha1_to_hex(sha1));
-
-	while (tree_entry(&desc, &entry))
-		if (!get_sha1(entry.path, commit_sha1))
-			add_entry(commit_sha1, entry.sha1);
-	free(buf);
+	hashclr(root_tree.key_sha1);
+	hashcpy(root_tree.val_sha1, sha1);
+	load_subtree(&root_tree, &root_node, 0);
 }
 
 static unsigned char *lookup_notes(const unsigned char *commit_sha1)
 {
-	int index;
-
-	if (!hash_map.size)
-		return NULL;
-
-	index = hash_index(&hash_map, commit_sha1);
-	if (index < 0)
-		return NULL;
-	return hash_map.entries[index].notes_sha1;
+	struct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);
+	if (found)
+		return found->val_sha1;
+	return NULL;
 }
 
 void get_commit_notes(const struct commit *commit, struct strbuf *sb,
@@ -120,7 +282,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,
 			notes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);
 		else if (!notes_ref_name)
 			notes_ref_name = GIT_NOTES_DEFAULT_REF;
-		initialize_hash_map(notes_ref_name);
+		initialize_notes(notes_ref_name);
 		initialized = 1;
 	}
 

-- 
1.6.4.304.g1365c.dirty