]>
Commit | Line | Data |
---|---|---|
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 | 7 | |
0556a11a LT |
8 | static struct object **obj_hash; |
9 | static int nr_objs, obj_hash_size; | |
fc046a75 LT |
10 | |
11 | unsigned int get_max_object_index(void) | |
12 | { | |
0556a11a | 13 | return obj_hash_size; |
fc046a75 LT |
14 | } |
15 | ||
16 | struct object *get_indexed_object(unsigned int idx) | |
17 | { | |
0556a11a | 18 | return obj_hash[idx]; |
fc046a75 | 19 | } |
175785e5 | 20 | |
df843662 NP |
21 | static const char *object_type_strings[] = { |
22 | NULL, /* OBJ_NONE = 0 */ | |
23 | "commit", /* OBJ_COMMIT = 1 */ | |
24 | "tree", /* OBJ_TREE = 2 */ | |
25 | "blob", /* OBJ_BLOB = 3 */ | |
26 | "tag", /* OBJ_TAG = 4 */ | |
885a86ab LT |
27 | }; |
28 | ||
df843662 NP |
29 | const char *typename(unsigned int type) |
30 | { | |
31 | if (type >= ARRAY_SIZE(object_type_strings)) | |
32 | return NULL; | |
33 | return object_type_strings[type]; | |
34 | } | |
35 | ||
36 | int type_from_string(const char *str) | |
37 | { | |
38 | int i; | |
39 | ||
40 | for (i = 1; i < ARRAY_SIZE(object_type_strings); i++) | |
41 | if (!strcmp(str, object_type_strings[i])) | |
42 | return i; | |
43 | die("invalid object type \"%s\"", str); | |
44 | } | |
45 | ||
33bef7ea MH |
46 | /* |
47 | * Return a numerical hash value between 0 and n-1 for the object with | |
48 | * the specified sha1. n must be a power of 2. Please note that the | |
49 | * return value is *not* consistent across computer architectures. | |
50 | */ | |
9f36c9b7 | 51 | static unsigned int hash_obj(const unsigned char *sha1, unsigned int n) |
0556a11a | 52 | { |
b867d324 | 53 | unsigned int hash; |
33bef7ea MH |
54 | |
55 | /* | |
56 | * Since the sha1 is essentially random, we just take the | |
57 | * required number of bits directly from the first | |
58 | * sizeof(unsigned int) bytes of sha1. First we have to copy | |
59 | * the bytes into a properly aligned integer. If we cared | |
60 | * about getting consistent results across architectures, we | |
61 | * would have to call ntohl() here, too. | |
62 | */ | |
9f36c9b7 | 63 | memcpy(&hash, sha1, sizeof(unsigned int)); |
9f36c9b7 | 64 | return hash & (n - 1); |
0556a11a LT |
65 | } |
66 | ||
33bef7ea MH |
67 | /* |
68 | * Insert obj into the hash table hash, which has length size (which | |
69 | * must be a power of 2). On collisions, simply overflow to the next | |
70 | * empty bucket. | |
71 | */ | |
0556a11a LT |
72 | static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size) |
73 | { | |
9f36c9b7 | 74 | unsigned int j = hash_obj(obj->sha1, size); |
0556a11a LT |
75 | |
76 | while (hash[j]) { | |
77 | j++; | |
78 | if (j >= size) | |
79 | j = 0; | |
80 | } | |
81 | hash[j] = obj; | |
82 | } | |
83 | ||
33bef7ea MH |
84 | /* |
85 | * Look up the record for the given sha1 in the hash map stored in | |
86 | * obj_hash. Return NULL if it was not found. | |
87 | */ | |
0556a11a | 88 | struct object *lookup_object(const unsigned char *sha1) |
175785e5 | 89 | { |
9a414486 | 90 | unsigned int i, first; |
0556a11a | 91 | struct object *obj; |
175785e5 | 92 | |
0556a11a LT |
93 | if (!obj_hash) |
94 | return NULL; | |
175785e5 | 95 | |
9f36c9b7 | 96 | first = i = hash_obj(sha1, obj_hash_size); |
0556a11a | 97 | while ((obj = obj_hash[i]) != NULL) { |
a89fccd2 | 98 | if (!hashcmp(sha1, obj->sha1)) |
0556a11a | 99 | break; |
070879ca | 100 | i++; |
0556a11a | 101 | if (i == obj_hash_size) |
070879ca JS |
102 | i = 0; |
103 | } | |
9a414486 JK |
104 | if (obj && i != first) { |
105 | /* | |
106 | * Move object to where we started to look for it so | |
107 | * that we do not need to walk the hash table the next | |
108 | * time we look for it. | |
109 | */ | |
110 | struct object *tmp = obj_hash[i]; | |
111 | obj_hash[i] = obj_hash[first]; | |
112 | obj_hash[first] = tmp; | |
113 | } | |
0556a11a | 114 | return obj; |
175785e5 DB |
115 | } |
116 | ||
33bef7ea MH |
117 | /* |
118 | * Increase the size of the hash map stored in obj_hash to the next | |
119 | * power of 2 (but at least 32). Copy the existing values to the new | |
120 | * hash map. | |
121 | */ | |
0556a11a | 122 | static void grow_object_hash(void) |
175785e5 | 123 | { |
0556a11a | 124 | int i; |
9f36c9b7 NP |
125 | /* |
126 | * Note that this size must always be power-of-2 to match hash_obj | |
127 | * above. | |
128 | */ | |
0556a11a LT |
129 | int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size; |
130 | struct object **new_hash; | |
131 | ||
b3c952f8 | 132 | new_hash = xcalloc(new_hash_size, sizeof(struct object *)); |
0556a11a LT |
133 | for (i = 0; i < obj_hash_size; i++) { |
134 | struct object *obj = obj_hash[i]; | |
135 | if (!obj) | |
136 | continue; | |
137 | insert_obj_hash(obj, new_hash, new_hash_size); | |
138 | } | |
139 | free(obj_hash); | |
140 | obj_hash = new_hash; | |
141 | obj_hash_size = new_hash_size; | |
175785e5 DB |
142 | } |
143 | ||
100c5f3b | 144 | void *create_object(const unsigned char *sha1, int type, void *o) |
175785e5 | 145 | { |
100c5f3b LT |
146 | struct object *obj = o; |
147 | ||
175785e5 | 148 | obj->parsed = 0; |
175785e5 | 149 | obj->used = 0; |
100c5f3b | 150 | obj->type = type; |
0556a11a | 151 | obj->flags = 0; |
e702496e | 152 | hashcpy(obj->sha1, sha1); |
175785e5 | 153 | |
0556a11a LT |
154 | if (obj_hash_size - 1 <= nr_objs * 2) |
155 | grow_object_hash(); | |
175785e5 | 156 | |
0556a11a | 157 | insert_obj_hash(obj, obj_hash, obj_hash_size); |
175785e5 | 158 | nr_objs++; |
100c5f3b | 159 | return obj; |
175785e5 DB |
160 | } |
161 | ||
66e481b0 DB |
162 | struct object *lookup_unknown_object(const unsigned char *sha1) |
163 | { | |
164 | struct object *obj = lookup_object(sha1); | |
100c5f3b LT |
165 | if (!obj) |
166 | obj = create_object(sha1, OBJ_NONE, alloc_object_node()); | |
66e481b0 DB |
167 | return obj; |
168 | } | |
169 | ||
21666f1a | 170 | struct object *parse_object_buffer(const unsigned char *sha1, enum object_type type, unsigned long size, void *buffer, int *eaten_p) |
9f613ddd JH |
171 | { |
172 | struct object *obj; | |
8e92e8f2 | 173 | *eaten_p = 0; |
9f613ddd | 174 | |
cc216827 | 175 | obj = NULL; |
21666f1a | 176 | if (type == OBJ_BLOB) { |
9f613ddd | 177 | struct blob *blob = lookup_blob(sha1); |
cc216827 | 178 | if (blob) { |
d0b8c9e5 MK |
179 | if (parse_blob_buffer(blob, buffer, size)) |
180 | return NULL; | |
cc216827 JM |
181 | obj = &blob->object; |
182 | } | |
21666f1a | 183 | } else if (type == OBJ_TREE) { |
9f613ddd | 184 | struct tree *tree = lookup_tree(sha1); |
cc216827 JM |
185 | if (tree) { |
186 | obj = &tree->object; | |
68be2fea JH |
187 | if (!tree->buffer) |
188 | tree->object.parsed = 0; | |
cc216827 | 189 | if (!tree->object.parsed) { |
d0b8c9e5 MK |
190 | if (parse_tree_buffer(tree, buffer, size)) |
191 | return NULL; | |
8e92e8f2 | 192 | *eaten_p = 1; |
cc216827 | 193 | } |
9f613ddd | 194 | } |
21666f1a | 195 | } else if (type == OBJ_COMMIT) { |
9f613ddd | 196 | struct commit *commit = lookup_commit(sha1); |
cc216827 | 197 | if (commit) { |
d0b8c9e5 MK |
198 | if (parse_commit_buffer(commit, buffer, size)) |
199 | return NULL; | |
cc216827 JM |
200 | if (!commit->buffer) { |
201 | commit->buffer = buffer; | |
8e92e8f2 | 202 | *eaten_p = 1; |
cc216827 JM |
203 | } |
204 | obj = &commit->object; | |
9f613ddd | 205 | } |
21666f1a | 206 | } else if (type == OBJ_TAG) { |
9f613ddd | 207 | struct tag *tag = lookup_tag(sha1); |
cc216827 | 208 | if (tag) { |
d0b8c9e5 MK |
209 | if (parse_tag_buffer(tag, buffer, size)) |
210 | return NULL; | |
cc216827 JM |
211 | obj = &tag->object; |
212 | } | |
9f613ddd | 213 | } else { |
82247e9b | 214 | warning("object %s has unknown type id %d", sha1_to_hex(sha1), type); |
9f613ddd JH |
215 | obj = NULL; |
216 | } | |
e2ac7cb5 SV |
217 | if (obj && obj->type == OBJ_NONE) |
218 | obj->type = type; | |
9f613ddd JH |
219 | return obj; |
220 | } | |
221 | ||
75a95490 JK |
222 | struct object *parse_object_or_die(const unsigned char *sha1, |
223 | const char *name) | |
224 | { | |
225 | struct object *o = parse_object(sha1); | |
226 | if (o) | |
227 | return o; | |
228 | ||
229 | die(_("unable to parse object: %s"), name ? name : sha1_to_hex(sha1)); | |
230 | } | |
231 | ||
5d6ccf5c | 232 | struct object *parse_object(const unsigned char *sha1) |
e9eefa67 | 233 | { |
c4584ae3 | 234 | unsigned long size; |
21666f1a | 235 | enum object_type type; |
9f613ddd | 236 | int eaten; |
4bbf5a26 | 237 | const unsigned char *repl = lookup_replace_object(sha1); |
ccdc6037 JK |
238 | void *buffer; |
239 | struct object *obj; | |
240 | ||
241 | obj = lookup_object(sha1); | |
242 | if (obj && obj->parsed) | |
243 | return obj; | |
9f613ddd | 244 | |
090ea126 NTND |
245 | if ((obj && obj->type == OBJ_BLOB) || |
246 | (!obj && has_sha1_file(sha1) && | |
247 | sha1_object_info(sha1, NULL) == OBJ_BLOB)) { | |
248 | if (check_sha1_signature(repl, NULL, 0, NULL) < 0) { | |
82247e9b | 249 | error("sha1 mismatch %s", sha1_to_hex(repl)); |
090ea126 NTND |
250 | return NULL; |
251 | } | |
252 | parse_blob_buffer(lookup_blob(sha1), NULL, 0); | |
253 | return lookup_object(sha1); | |
254 | } | |
255 | ||
ccdc6037 | 256 | buffer = read_sha1_file(sha1, &type, &size); |
c4584ae3 | 257 | if (buffer) { |
0e87c367 | 258 | if (check_sha1_signature(repl, buffer, size, typename(type)) < 0) { |
0b1f1130 | 259 | free(buffer); |
82247e9b | 260 | error("sha1 mismatch %s", sha1_to_hex(repl)); |
acdeec62 LT |
261 | return NULL; |
262 | } | |
9f613ddd | 263 | |
2e3400c0 | 264 | obj = parse_object_buffer(sha1, type, size, buffer, &eaten); |
9f613ddd JH |
265 | if (!eaten) |
266 | free(buffer); | |
bd2c39f5 | 267 | return obj; |
e9eefa67 DB |
268 | } |
269 | return NULL; | |
270 | } | |
66e481b0 DB |
271 | |
272 | struct object_list *object_list_insert(struct object *item, | |
273 | struct object_list **list_p) | |
274 | { | |
275 | struct object_list *new_list = xmalloc(sizeof(struct object_list)); | |
55b4e9e4 JH |
276 | new_list->item = item; |
277 | new_list->next = *list_p; | |
278 | *list_p = new_list; | |
279 | return new_list; | |
66e481b0 DB |
280 | } |
281 | ||
66e481b0 DB |
282 | int object_list_contains(struct object_list *list, struct object *obj) |
283 | { | |
284 | while (list) { | |
285 | if (list->item == obj) | |
286 | return 1; | |
287 | list = list->next; | |
288 | } | |
289 | return 0; | |
290 | } | |
1f1e895f | 291 | |
31faeb20 MH |
292 | /* |
293 | * A zero-length string to which object_array_entry::name can be | |
294 | * initialized without requiring a malloc/free. | |
295 | */ | |
296 | static char object_array_slopbuf[1]; | |
297 | ||
4197361e JH |
298 | static void add_object_array_with_mode_context(struct object *obj, const char *name, |
299 | struct object_array *array, | |
300 | unsigned mode, | |
301 | struct object_context *context) | |
1f1e895f LT |
302 | { |
303 | unsigned nr = array->nr; | |
304 | unsigned alloc = array->alloc; | |
305 | struct object_array_entry *objects = array->objects; | |
31faeb20 | 306 | struct object_array_entry *entry; |
1f1e895f LT |
307 | |
308 | if (nr >= alloc) { | |
309 | alloc = (alloc + 32) * 2; | |
310 | objects = xrealloc(objects, alloc * sizeof(*objects)); | |
311 | array->alloc = alloc; | |
312 | array->objects = objects; | |
313 | } | |
31faeb20 MH |
314 | entry = &objects[nr]; |
315 | entry->item = obj; | |
316 | if (!name) | |
317 | entry->name = NULL; | |
318 | else if (!*name) | |
319 | /* Use our own empty string instead of allocating one: */ | |
320 | entry->name = object_array_slopbuf; | |
321 | else | |
322 | entry->name = xstrdup(name); | |
323 | entry->mode = mode; | |
4197361e | 324 | entry->context = context; |
1f1e895f LT |
325 | array->nr = ++nr; |
326 | } | |
b2a6d1c6 | 327 | |
afa15f3c MG |
328 | void add_object_array(struct object *obj, const char *name, struct object_array *array) |
329 | { | |
330 | add_object_array_with_mode(obj, name, array, S_IFINVALID); | |
331 | } | |
332 | ||
333 | void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode) | |
334 | { | |
335 | add_object_array_with_mode_context(obj, name, array, mode, NULL); | |
336 | } | |
337 | ||
338 | void add_object_array_with_context(struct object *obj, const char *name, struct object_array *array, struct object_context *context) | |
339 | { | |
340 | if (context) | |
341 | add_object_array_with_mode_context(obj, name, array, context->mode, context); | |
342 | else | |
343 | add_object_array_with_mode_context(obj, name, array, S_IFINVALID, context); | |
344 | } | |
345 | ||
aeb4a51e MH |
346 | void object_array_filter(struct object_array *array, |
347 | object_array_each_func_t want, void *cb_data) | |
b2a6d1c6 | 348 | { |
aeb4a51e | 349 | unsigned nr = array->nr, src, dst; |
b2a6d1c6 JH |
350 | struct object_array_entry *objects = array->objects; |
351 | ||
aeb4a51e MH |
352 | for (src = dst = 0; src < nr; src++) { |
353 | if (want(&objects[src], cb_data)) { | |
b2a6d1c6 JH |
354 | if (src != dst) |
355 | objects[dst] = objects[src]; | |
356 | dst++; | |
31faeb20 MH |
357 | } else { |
358 | if (objects[src].name != object_array_slopbuf) | |
359 | free(objects[src].name); | |
aeb4a51e MH |
360 | } |
361 | } | |
362 | array->nr = dst; | |
363 | } | |
364 | ||
1506510c MH |
365 | /* |
366 | * Return true iff array already contains an entry with name. | |
367 | */ | |
368 | static int contains_name(struct object_array *array, const char *name) | |
369 | { | |
370 | unsigned nr = array->nr, i; | |
371 | struct object_array_entry *object = array->objects; | |
372 | ||
373 | for (i = 0; i < nr; i++, object++) | |
374 | if (!strcmp(object->name, name)) | |
375 | return 1; | |
376 | return 0; | |
377 | } | |
378 | ||
b2a6d1c6 JH |
379 | void object_array_remove_duplicates(struct object_array *array) |
380 | { | |
1506510c | 381 | unsigned nr = array->nr, src; |
b2a6d1c6 JH |
382 | struct object_array_entry *objects = array->objects; |
383 | ||
1506510c MH |
384 | array->nr = 0; |
385 | for (src = 0; src < nr; src++) { | |
386 | if (!contains_name(array, objects[src].name)) { | |
387 | if (src != array->nr) | |
388 | objects[array->nr] = objects[src]; | |
389 | array->nr++; | |
31faeb20 MH |
390 | } else { |
391 | if (objects[src].name != object_array_slopbuf) | |
392 | free(objects[src].name); | |
b2a6d1c6 | 393 | } |
b2a6d1c6 JH |
394 | } |
395 | } | |
bcc0a3ea HV |
396 | |
397 | void clear_object_flags(unsigned flags) | |
398 | { | |
399 | int i; | |
400 | ||
401 | for (i=0; i < obj_hash_size; i++) { | |
402 | struct object *obj = obj_hash[i]; | |
403 | if (obj) | |
404 | obj->flags &= ~flags; | |
405 | } | |
406 | } |