From c5696427b6d53a3f79baad35ea33c556884a410a Mon Sep 17 00:00:00 2001 From: Vicent Marti Date: Sat, 22 May 2010 23:21:10 +0200 Subject: [PATCH] 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 Signed-off-by: Andreas Ericsson --- src/commit.c | 14 ++--- src/commit.h | 5 +- src/revobject.c | 167 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/revobject.h | 39 +++++++++++++ src/revwalk.c | 2 +- 5 files changed, 216 insertions(+), 11 deletions(-) create mode 100644 src/revobject.c create mode 100644 src/revobject.h diff --git a/src/commit.c b/src/commit.c index b196a80..226eca4 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 75e6d95..818d98c 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 @@ -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 0000000..7c25137 --- /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 0000000..8ea17a2 --- /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 94b6d09..cbf7144 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) -- 2.11.4.GIT