Add 'git_revpool_object' and 'git_revpool_table' structures.

All the objects which will will be eventually transversable from
a revision pool (commits, trees, etc) now inherit from the
'git_revpool_object' structure which identifies them with their
own OID.

Furthermore, the 'git_revpool_table' and related functions have
been added, which allow for constant time lookup (hash table)
of the loaded revpool objects based on their OID.

Signed-off-by: Vicent Marti <tanoku@gmail.com>
Signed-off-by: Andreas Ericsson <ae@op5.se>

5 files changed, 216 insertions, 11 deletions

diff --git a/src/commit.c b/src/commit.c
index b196a807b..226eca421 100644
--- a/src/commit.c
+++ b/src/commit.c
@@ -32,7 +32,7 @@
 
 const git_oid *git_commit_id(git_commit *c)
 {
-	return &c->id;
+	return &c->object.id;
 }
 
 void git_commit__mark_uninteresting(git_commit *commit)
@@ -75,10 +75,7 @@ int git_commit_parse_existing(git_commit *commit)
     if (commit->parsed)
         return 0;
 
-    if (commit->pool == NULL || commit->pool->db == NULL)
-        return -1;
-
-    if (git_odb_read(&commit_obj, commit->pool->db, &commit->id) < 0)
+    if (git_odb_read(&commit_obj, commit->object.pool->db, &commit->object.id) < 0)
         return -1;
 
     if (commit_obj.type != GIT_OBJ_COMMIT)
@@ -110,8 +107,9 @@ git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
 
     memset(commit, 0x0, sizeof(git_commit));
 
-    git_oid_cpy(&commit->id, id);
-    commit->pool = pool;
+    // Initialize parent object
+    git_oid_cpy(&commit->object.id, id);
+    commit->object.pool = pool;
 
     return commit;
 }
@@ -182,7 +180,7 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
     while (git_commit__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
         git_commit *parent;
 
-        if ((parent = git_commit_lookup(commit->pool, &oid)) == NULL)
+        if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
             return -1;
 
         // Inherit uninteresting flag
diff --git a/src/commit.h b/src/commit.h
index 75e6d95a8..818d98c06 100644
--- a/src/commit.h
+++ b/src/commit.h
@@ -2,6 +2,7 @@
 #define INCLUDE_commit_h__
 
 #include "git/commit.h"
+#include "revobject.h"
 
 #include <time.h>
 
@@ -22,9 +23,9 @@ typedef struct git_commit_list git_commit_list;
 typedef struct git_commit_node git_commit_node;
 
 struct git_commit {
-    git_oid id;
+    git_revpool_object object;
+
     time_t commit_time;
-    git_revpool *pool;
     git_commit_list parents;
 
     unsigned short in_degree;
diff --git a/src/revobject.c b/src/revobject.c
new file mode 100644
index 000000000..7c2513775
--- /dev/null
+++ b/src/revobject.c
@@ -0,0 +1,167 @@
+/*
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License, version 2,
+ * as published by the Free Software Foundation.
+ *
+ * In addition to the permissions in the GNU General Public License,
+ * the authors give you unlimited permission to link the compiled
+ * version of this file into combinations with other programs,
+ * and to distribute those combinations without any restriction
+ * coming from the use of this file.  (The General Public License
+ * restrictions do apply in other respects; for example, they cover
+ * modification of the file, and distribution when not linked into
+ * a combined executable.)
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; see the file COPYING.  If not, write to
+ * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "common.h"
+#include "revobject.h"
+
+const float max_load_factor = 0.65;
+
+unsigned int git_revpool_table__hash(const git_oid *id)
+{
+	const unsigned int m = 0x5bd1e995;
+	const int r = 24;
+
+	unsigned int h = 0xA8A3D5 ^ (unsigned int)id;
+    int i;
+
+    for (i = 0; i < GIT_OID_RAWSZ / 4; ++i)
+    {
+		unsigned int k = ((unsigned int *)id->id)[i];
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+		h *= m;
+		h ^= k;
+    }
+
+	h ^= h >> 13;
+	h *= m;
+	h ^= h >> 15;
+
+	return h;
+}
+
+git_revpool_table *git_revpool_table_create(unsigned int min_size)
+{
+    git_revpool_table *table;
+
+    table = git__malloc(sizeof(table));
+
+    if (table == NULL)
+        return NULL;
+
+    // round up size to closest power of 2
+    min_size--;
+    min_size |= min_size >> 1;
+    min_size |= min_size >> 2;
+    min_size |= min_size >> 4;
+    min_size |= min_size >> 8;
+    min_size |= min_size >> 16;
+
+    table->size_mask = min_size;
+    table->count = 0;
+    table->max_count = (min_size + 1) * max_load_factor;
+
+    table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *));
+
+    if (table->nodes == NULL)
+    {
+        free(table);
+        return NULL;
+    }
+
+    memset(table->nodes, 0x0, (min_size + 1) * sizeof(git_revpool_node *));
+
+    return table;
+}
+
+int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object)
+{
+    git_revpool_node *node;
+    unsigned int index, hash;
+
+    if (table->count + 1 > table->max_count)
+        git_revpool_table_resize(table);
+
+    node = git__malloc(sizeof(git_revpool_node));
+    if (node == NULL)
+        return -1;
+
+    hash = git_revpool_table__hash(&object->id);
+    index = (hash & table->size_mask);
+
+    node->object = object;
+    node->hash = hash;
+    node->next = table->nodes[index];
+
+    table->nodes[index] = node;
+    table->count++;
+
+    return 0;
+}
+
+git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id)
+{
+    git_revpool_node *node;
+    unsigned int index, hash;
+
+    hash = git_revpool_table__hash(id);
+    index = (hash & table->size_mask);
+    node = table->nodes[index];
+
+    while (node != NULL)
+    {
+        if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0)
+            return node->object;
+
+        node = node->next;
+    }
+
+    return NULL;
+}
+
+void git_revpool_table_resize(git_revpool_table *table)
+{
+    git_revpool_node **new_nodes;
+    unsigned int new_size, i;
+
+    new_size = (table->size_mask + 1) * 2;
+
+    new_nodes = git__malloc(new_size * sizeof(git_revpool_node *));
+    if (new_nodes == NULL)
+        return;
+
+    memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *));
+
+    for (i = 0; i <= table->size_mask; ++i)
+    {
+        git_revpool_node *n;
+        unsigned int index;
+
+        while ((n = table->nodes[i]) != NULL)
+        {
+            table->nodes[i] = n->next;
+            index = n->hash & (new_size - 1);
+            n->next = new_nodes[index];
+            new_nodes[index] = n;
+        }
+    }
+
+    free(table->nodes);
+    table->nodes = new_nodes;
+    table->size_mask = (new_size - 1);
+    table->max_count = new_size * max_load_factor;
+}
diff --git a/src/revobject.h b/src/revobject.h
new file mode 100644
index 000000000..8ea17a2c5
--- /dev/null
+++ b/src/revobject.h
@@ -0,0 +1,39 @@
+#ifndef INCLUDE_objecttable_h__
+#define INCLUDE_objecttable_h__
+
+#include "git/common.h"
+#include "git/oid.h"
+
+struct git_revpool_object
+{
+    git_oid id;
+    git_revpool *pool;
+};
+
+struct git_revpool_node
+{
+    struct git_revpool_object *object;
+    unsigned int hash;
+    struct git_revpool_node *next;
+};
+
+struct git_revpool_table
+{
+    unsigned int size_mask;
+    unsigned int count;
+    unsigned int max_count;
+    struct git_revpool_node **nodes;
+};
+
+
+typedef struct git_revpool_node git_revpool_node;
+typedef struct git_revpool_object git_revpool_object;
+typedef struct git_revpool_table git_revpool_table;
+
+git_revpool_table *git_revpool_table_create(unsigned int min_size);
+int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object);
+git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id);
+void git_revpool_table_resize(git_revpool_table *table);
+
+
+#endif
diff --git a/src/revwalk.c b/src/revwalk.c
index 94b6d09da..cbf7144d8 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -48,7 +48,7 @@ void gitrp_free(git_revpool *walk)
 
 void gitrp_push(git_revpool *pool, git_commit *commit)
 {
-    if (commit->pool != pool)
+    if (commit->object.pool != pool)
         return;
 
     if (commit->seen)