[RFC] Use a 16-tree instead of a 256-tree for storing notes

From

Johan Herland <johan@herland.net>

Date

Aug 26, 2009, 10:31 UTC

Message-ID

<200908261231.01616.johan@herland.net>

In-Reply-To

<200908010436.57480.johan@herland.net>

In conclusion, this is faster and smaller than all the previous drafts.

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

Hi,

This patch goes on top of the 256-tree RFC I sent earlier.

Have fun! :)

...Johan

 notes.c |   26 ++++++++++++++------------
 1 files changed, 14 insertions(+), 12 deletions(-)

diff --git a/notes.c b/notes.c
index 9282b16..32b1e01 100644
--- a/notes.c
+++ b/notes.c
@@ -7,9 +7,9 @@
 #include "tree-walk.h"
 
 /*
- * Use a non-balancing simple 256-tree structure with struct int_node as
+ * 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
- * 256-array of pointers to its children
+ * 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 *
@@ -21,18 +21,18 @@
  *
  * To add a leaf_node:
  * 1. Start at the root node, with n = 0
- * 2. Use the nth byte of the key as an index into a:
- *    - If NULL, store the tweaked pointer directly into a[n]
- *    - If an int_node, recurse into that node and increment n
- *    - If a leaf_node:
+ * 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].
  *
  * To find a leaf_node:
  * 1. Start at the root node, with n = 0
- * 2. Use the nth byte of the key as an index into a:
- *    - If an int_node, recurse into that node and increment n
+ * 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.
@@ -42,7 +42,7 @@
  *        subtree entry (and remove it); restart search at the current level.
  */
 struct int_node {
-	void *a[256];
+	void *a[16];
 };
 
 /*
@@ -79,11 +79,13 @@ static int initialized;
 static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 		unsigned int n);
 
+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((n & 0x01) << 2)) & 0x0f)
+
 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 = key_sha1[n];
+	unsigned char i = GET_NIBBLE(n, key_sha1);
 	void *p = tree->a[i];
 
 	switch(GET_PTR_TYPE(p)) {
@@ -138,7 +140,7 @@ static int note_tree_insert(struct int_node *tree, unsigned char n,
 	struct int_node *new_node;
 	const struct leaf_node *l;
 	int ret;
-	unsigned char i = entry->key_sha1[n];
+	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)) {
@@ -211,7 +213,7 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,
 		     sha1_to_hex(subtree->val_sha1));
 
 	prefix_len = subtree->key_sha1[19];
-	assert(prefix_len >= n);
+	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),

-- 
1.6.4.304.g1365c.dirty