Skip to content

Commit c569642

Browse files
Vicent Martiageric
Vicent Marti
authored and
ageric
committed
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>
1 parent 36b7cdb commit c569642

5 files changed

Lines changed: 216 additions & 11 deletions

File tree

‎src/commit.c‎

Lines changed: 6 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@
3232

3333
const git_oid *git_commit_id(git_commit *c)
3434
{
35-
return &c->id;
35+
return &c->object.id;
3636
}
3737

3838
void git_commit__mark_uninteresting(git_commit *commit)
@@ -75,10 +75,7 @@ int git_commit_parse_existing(git_commit *commit)
7575
if (commit->parsed)
7676
return 0;
7777

78-
if (commit->pool == NULL || commit->pool->db == NULL)
79-
return -1;
80-
81-
if (git_odb_read(&commit_obj, commit->pool->db, &commit->id) < 0)
78+
if (git_odb_read(&commit_obj, commit->object.pool->db, &commit->object.id) < 0)
8279
return -1;
8380

8481
if (commit_obj.type != GIT_OBJ_COMMIT)
@@ -110,8 +107,9 @@ git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id)
110107

111108
memset(commit, 0x0, sizeof(git_commit));
112109

113-
git_oid_cpy(&commit->id, id);
114-
commit->pool = pool;
110+
// Initialize parent object
111+
git_oid_cpy(&commit->object.id, id);
112+
commit->object.pool = pool;
115113

116114
return commit;
117115
}
@@ -182,7 +180,7 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len)
182180
while (git_commit__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) {
183181
git_commit *parent;
184182

185-
if ((parent = git_commit_lookup(commit->pool, &oid)) == NULL)
183+
if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL)
186184
return -1;
187185

188186
// Inherit uninteresting flag

‎src/commit.h‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
#define INCLUDE_commit_h__
33

44
#include "git/commit.h"
5+
#include "revobject.h"
56

67
#include <time.h>
78

@@ -22,9 +23,9 @@ typedef struct git_commit_list git_commit_list;
2223
typedef struct git_commit_node git_commit_node;
2324

2425
struct git_commit {
25-
git_oid id;
26+
git_revpool_object object;
27+
2628
time_t commit_time;
27-
git_revpool *pool;
2829
git_commit_list parents;
2930

3031
unsigned short in_degree;

‎src/revobject.c‎

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
/*
2+
* This file is free software; you can redistribute it and/or modify
3+
* it under the terms of the GNU General Public License, version 2,
4+
* as published by the Free Software Foundation.
5+
*
6+
* In addition to the permissions in the GNU General Public License,
7+
* the authors give you unlimited permission to link the compiled
8+
* version of this file into combinations with other programs,
9+
* and to distribute those combinations without any restriction
10+
* coming from the use of this file. (The General Public License
11+
* restrictions do apply in other respects; for example, they cover
12+
* modification of the file, and distribution when not linked into
13+
* a combined executable.)
14+
*
15+
* This file is distributed in the hope that it will be useful, but
16+
* WITHOUT ANY WARRANTY; without even the implied warranty of
17+
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18+
* General Public License for more details.
19+
*
20+
* You should have received a copy of the GNU General Public License
21+
* along with this program; see the file COPYING. If not, write to
22+
* the Free Software Foundation, 51 Franklin Street, Fifth Floor,
23+
* Boston, MA 02110-1301, USA.
24+
*/
25+
26+
#include "common.h"
27+
#include "revobject.h"
28+
29+
const float max_load_factor = 0.65;
30+
31+
unsigned int git_revpool_table__hash(const git_oid *id)
32+
{
33+
const unsigned int m = 0x5bd1e995;
34+
const int r = 24;
35+
36+
unsigned int h = 0xA8A3D5 ^ (unsigned int)id;
37+
int i;
38+
39+
for (i = 0; i < GIT_OID_RAWSZ / 4; ++i)
40+
{
41+
unsigned int k = ((unsigned int *)id->id)[i];
42+
43+
k *= m;
44+
k ^= k >> r;
45+
k *= m;
46+
h *= m;
47+
h ^= k;
48+
}
49+
50+
h ^= h >> 13;
51+
h *= m;
52+
h ^= h >> 15;
53+
54+
return h;
55+
}
56+
57+
git_revpool_table *git_revpool_table_create(unsigned int min_size)
58+
{
59+
git_revpool_table *table;
60+
61+
table = git__malloc(sizeof(table));
62+
63+
if (table == NULL)
64+
return NULL;
65+
66+
// round up size to closest power of 2
67+
min_size--;
68+
min_size |= min_size >> 1;
69+
min_size |= min_size >> 2;
70+
min_size |= min_size >> 4;
71+
min_size |= min_size >> 8;
72+
min_size |= min_size >> 16;
73+
74+
table->size_mask = min_size;
75+
table->count = 0;
76+
table->max_count = (min_size + 1) * max_load_factor;
77+
78+
table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *));
79+
80+
if (table->nodes == NULL)
81+
{
82+
free(table);
83+
return NULL;
84+
}
85+
86+
memset(table->nodes, 0x0, (min_size + 1) * sizeof(git_revpool_node *));
87+
88+
return table;
89+
}
90+
91+
int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object)
92+
{
93+
git_revpool_node *node;
94+
unsigned int index, hash;
95+
96+
if (table->count + 1 > table->max_count)
97+
git_revpool_table_resize(table);
98+
99+
node = git__malloc(sizeof(git_revpool_node));
100+
if (node == NULL)
101+
return -1;
102+
103+
hash = git_revpool_table__hash(&object->id);
104+
index = (hash & table->size_mask);
105+
106+
node->object = object;
107+
node->hash = hash;
108+
node->next = table->nodes[index];
109+
110+
table->nodes[index] = node;
111+
table->count++;
112+
113+
return 0;
114+
}
115+
116+
git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id)
117+
{
118+
git_revpool_node *node;
119+
unsigned int index, hash;
120+
121+
hash = git_revpool_table__hash(id);
122+
index = (hash & table->size_mask);
123+
node = table->nodes[index];
124+
125+
while (node != NULL)
126+
{
127+
if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0)
128+
return node->object;
129+
130+
node = node->next;
131+
}
132+
133+
return NULL;
134+
}
135+
136+
void git_revpool_table_resize(git_revpool_table *table)
137+
{
138+
git_revpool_node **new_nodes;
139+
unsigned int new_size, i;
140+
141+
new_size = (table->size_mask + 1) * 2;
142+
143+
new_nodes = git__malloc(new_size * sizeof(git_revpool_node *));
144+
if (new_nodes == NULL)
145+
return;
146+
147+
memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *));
148+
149+
for (i = 0; i <= table->size_mask; ++i)
150+
{
151+
git_revpool_node *n;
152+
unsigned int index;
153+
154+
while ((n = table->nodes[i]) != NULL)
155+
{
156+
table->nodes[i] = n->next;
157+
index = n->hash & (new_size - 1);
158+
n->next = new_nodes[index];
159+
new_nodes[index] = n;
160+
}
161+
}
162+
163+
free(table->nodes);
164+
table->nodes = new_nodes;
165+
table->size_mask = (new_size - 1);
166+
table->max_count = new_size * max_load_factor;
167+
}

‎src/revobject.h‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
#ifndef INCLUDE_objecttable_h__
2+
#define INCLUDE_objecttable_h__
3+
4+
#include "git/common.h"
5+
#include "git/oid.h"
6+
7+
struct git_revpool_object
8+
{
9+
git_oid id;
10+
git_revpool *pool;
11+
};
12+
13+
struct git_revpool_node
14+
{
15+
struct git_revpool_object *object;
16+
unsigned int hash;
17+
struct git_revpool_node *next;
18+
};
19+
20+
struct git_revpool_table
21+
{
22+
unsigned int size_mask;
23+
unsigned int count;
24+
unsigned int max_count;
25+
struct git_revpool_node **nodes;
26+
};
27+
28+
29+
typedef struct git_revpool_node git_revpool_node;
30+
typedef struct git_revpool_object git_revpool_object;
31+
typedef struct git_revpool_table git_revpool_table;
32+
33+
git_revpool_table *git_revpool_table_create(unsigned int min_size);
34+
int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object);
35+
git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id);
36+
void git_revpool_table_resize(git_revpool_table *table);
37+
38+
39+
#endif

‎src/revwalk.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ void gitrp_free(git_revpool *walk)
4848

4949
void gitrp_push(git_revpool *pool, git_commit *commit)
5050
{
51-
if (commit->pool != pool)
51+
if (commit->object.pool != pool)
5252
return;
5353

5454
if (commit->seen)

0 commit comments

Comments
 (0)