Use a hashtable for objects instead of a sorted list
[git/git.git] / object.c
CommitLineData
8f1d2e6f 1#include "cache.h"
175785e5 2#include "object.h"
e9eefa67
DB
3#include "blob.h"
4#include "tree.h"
5#include "commit.h"
e9eefa67 6#include "tag.h"
175785e5
DB
7
8struct object **objs;
070879ca
JS
9static int nr_objs;
10int obj_allocs;
175785e5 11
8805ccac
LT
12int track_object_refs = 1;
13
070879ca
JS
14static int hashtable_index(const unsigned char *sha1)
15{
16 unsigned int i = *(unsigned int *)sha1;
17 return (int)(i % obj_allocs);
18}
19
5d6ccf5c 20static int find_object(const unsigned char *sha1)
175785e5 21{
070879ca 22 int i = hashtable_index(sha1);
175785e5 23
070879ca
JS
24 if (!objs)
25 return -1;
175785e5 26
070879ca
JS
27 while (objs[i]) {
28 if (memcmp(sha1, objs[i]->sha1, 20) == 0)
29 return i;
30 i++;
31 if (i == obj_allocs)
32 i = 0;
33 }
34 return -1 - i;
175785e5
DB
35}
36
5d6ccf5c 37struct object *lookup_object(const unsigned char *sha1)
175785e5
DB
38{
39 int pos = find_object(sha1);
40 if (pos >= 0)
41 return objs[pos];
42 return NULL;
43}
44
5d6ccf5c 45void created_object(const unsigned char *sha1, struct object *obj)
175785e5 46{
070879ca 47 int pos;
175785e5
DB
48
49 obj->parsed = 0;
50 memcpy(obj->sha1, sha1, 20);
51 obj->type = NULL;
52 obj->refs = NULL;
53 obj->used = 0;
54
070879ca
JS
55 if (obj_allocs - 1 <= nr_objs * 2) {
56 int i, count = obj_allocs;
57 obj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs);
812666c8 58 objs = xrealloc(objs, obj_allocs * sizeof(struct object *));
070879ca
JS
59 memset(objs + count, 0, (obj_allocs - count)
60 * sizeof(struct object *));
61 for (i = 0; i < count; i++)
62 if (objs[i]) {
63 int j = find_object(objs[i]->sha1);
64 if (j != i) {
65 j = -1 - j;
66 objs[j] = objs[i];
67 objs[i] = NULL;
68 }
69 }
175785e5
DB
70 }
71
070879ca
JS
72 pos = find_object(sha1);
73 if (pos >= 0)
74 die("Inserting %s twice\n", sha1_to_hex(sha1));
75 pos = -pos-1;
175785e5
DB
76
77 objs[pos] = obj;
78 nr_objs++;
79}
80
4a4e6fd7 81struct object_refs *alloc_object_refs(unsigned count)
175785e5 82{
4a4e6fd7
SV
83 struct object_refs *refs;
84 size_t size = sizeof(*refs) + count*sizeof(struct object *);
8805ccac 85
4a4e6fd7
SV
86 refs = xmalloc(size);
87 memset(refs, 0, size);
88 refs->count = count;
89 return refs;
90}
91
92static int compare_object_pointers(const void *a, const void *b)
93{
94 const struct object * const *pa = a;
95 const struct object * const *pb = b;
e23eff8b
JH
96 if (*pa == *pb)
97 return 0;
98 else if (*pa < *pb)
99 return -1;
100 else
101 return 1;
4a4e6fd7
SV
102}
103
104void set_object_refs(struct object *obj, struct object_refs *refs)
105{
106 unsigned int i, j;
107
108 /* Do not install empty list of references */
109 if (refs->count < 1) {
110 free(refs);
8805ccac 111 return;
4a4e6fd7 112 }
8805ccac 113
4a4e6fd7
SV
114 /* Sort the list and filter out duplicates */
115 qsort(refs->ref, refs->count, sizeof(refs->ref[0]),
116 compare_object_pointers);
117 for (i = j = 1; i < refs->count; i++) {
118 if (refs->ref[i] != refs->ref[i - 1])
119 refs->ref[j++] = refs->ref[i];
120 }
121 if (j < refs->count) {
122 /* Duplicates were found - reallocate list */
123 size_t size = sizeof(*refs) + j*sizeof(struct object *);
124 refs->count = j;
125 refs = xrealloc(refs, size);
175785e5
DB
126 }
127
4a4e6fd7
SV
128 for (i = 0; i < refs->count; i++)
129 refs->ref[i]->used = 1;
130 obj->refs = refs;
175785e5
DB
131}
132
133void mark_reachable(struct object *obj, unsigned int mask)
134{
8805ccac
LT
135 if (!track_object_refs)
136 die("cannot do reachability with object refs turned off");
175785e5
DB
137 /* If we've been here already, don't bother */
138 if (obj->flags & mask)
139 return;
140 obj->flags |= mask;
4a4e6fd7
SV
141 if (obj->refs) {
142 const struct object_refs *refs = obj->refs;
143 unsigned i;
144 for (i = 0; i < refs->count; i++)
145 mark_reachable(refs->ref[i], mask);
175785e5
DB
146 }
147}
e9eefa67 148
89e4202f
DB
149struct object *lookup_object_type(const unsigned char *sha1, const char *type)
150{
66e481b0
DB
151 if (!type) {
152 return lookup_unknown_object(sha1);
153 } else if (!strcmp(type, blob_type)) {
89e4202f
DB
154 return &lookup_blob(sha1)->object;
155 } else if (!strcmp(type, tree_type)) {
156 return &lookup_tree(sha1)->object;
157 } else if (!strcmp(type, commit_type)) {
158 return &lookup_commit(sha1)->object;
159 } else if (!strcmp(type, tag_type)) {
160 return &lookup_tag(sha1)->object;
161 } else {
162 error("Unknown type %s", type);
163 return NULL;
164 }
165}
166
66e481b0
DB
167union any_object {
168 struct object object;
169 struct commit commit;
170 struct tree tree;
171 struct blob blob;
172 struct tag tag;
173};
174
175struct object *lookup_unknown_object(const unsigned char *sha1)
176{
177 struct object *obj = lookup_object(sha1);
178 if (!obj) {
179 union any_object *ret = xmalloc(sizeof(*ret));
180 memset(ret, 0, sizeof(*ret));
181 created_object(sha1, &ret->object);
182 ret->object.type = NULL;
183 return &ret->object;
184 }
185 return obj;
186}
187
5d6ccf5c 188struct object *parse_object(const unsigned char *sha1)
e9eefa67 189{
c4584ae3
JH
190 unsigned long size;
191 char type[20];
192 void *buffer = read_sha1_file(sha1, type, &size);
193 if (buffer) {
bd2c39f5 194 struct object *obj;
c4584ae3 195 if (check_sha1_signature(sha1, buffer, size, type) < 0)
e9eefa67 196 printf("sha1 mismatch %s\n", sha1_to_hex(sha1));
c4584ae3 197 if (!strcmp(type, "blob")) {
bd2c39f5
NP
198 struct blob *blob = lookup_blob(sha1);
199 parse_blob_buffer(blob, buffer, size);
200 obj = &blob->object;
e9eefa67 201 } else if (!strcmp(type, "tree")) {
bd2c39f5
NP
202 struct tree *tree = lookup_tree(sha1);
203 parse_tree_buffer(tree, buffer, size);
204 obj = &tree->object;
e9eefa67 205 } else if (!strcmp(type, "commit")) {
bd2c39f5
NP
206 struct commit *commit = lookup_commit(sha1);
207 parse_commit_buffer(commit, buffer, size);
bd1e17e2
LT
208 if (!commit->buffer) {
209 commit->buffer = buffer;
210 buffer = NULL;
211 }
bd2c39f5 212 obj = &commit->object;
e9eefa67 213 } else if (!strcmp(type, "tag")) {
bd2c39f5
NP
214 struct tag *tag = lookup_tag(sha1);
215 parse_tag_buffer(tag, buffer, size);
216 obj = &tag->object;
e9eefa67 217 } else {
bd2c39f5 218 obj = NULL;
e9eefa67 219 }
bd2c39f5
NP
220 free(buffer);
221 return obj;
e9eefa67
DB
222 }
223 return NULL;
224}
66e481b0
DB
225
226struct object_list *object_list_insert(struct object *item,
227 struct object_list **list_p)
228{
229 struct object_list *new_list = xmalloc(sizeof(struct object_list));
230 new_list->item = item;
231 new_list->next = *list_p;
232 *list_p = new_list;
233 return new_list;
234}
235
680bab3d
DB
236void object_list_append(struct object *item,
237 struct object_list **list_p)
238{
239 while (*list_p) {
240 list_p = &((*list_p)->next);
241 }
242 *list_p = xmalloc(sizeof(struct object_list));
243 (*list_p)->next = NULL;
244 (*list_p)->item = item;
245}
246
66e481b0
DB
247unsigned object_list_length(struct object_list *list)
248{
249 unsigned ret = 0;
250 while (list) {
251 list = list->next;
252 ret++;
253 }
254 return ret;
255}
256
257int object_list_contains(struct object_list *list, struct object *obj)
258{
259 while (list) {
260 if (list->item == obj)
261 return 1;
262 list = list->next;
263 }
264 return 0;
265}