8 static const char *object_type_strings[] = {
9 NULL, /* OBJ_NONE = 0 */
10 "commit", /* OBJ_COMMIT = 1 */
11 "tree", /* OBJ_TREE = 2 */
12 "blob", /* OBJ_BLOB = 3 */
13 "tag", /* OBJ_TAG = 4 */
16 const char *typename(unsigned int type)
18 if (type >= ARRAY_SIZE(object_type_strings))
20 return object_type_strings[type];
23 int type_from_string(const char *str)
27 for (i = 1; i < ARRAY_SIZE(object_type_strings); i++)
28 if (!strcmp(str, object_type_strings[i]))
30 die("invalid object type \"%s\"", str);
33 static struct object **obj_hash;
34 static int nr_objs, obj_hash_size;
36 unsigned int get_max_object_index(void)
41 struct object *get_indexed_object(unsigned int idx)
47 /* Choose from 2, 3, 4 or 5 */
48 #define CUCKOO_FACTOR 4
50 #define H(hv,ix) ((hv[ix]) & (obj_hash_size-1))
52 struct object *lookup_object(const unsigned char *sha1)
55 const unsigned int *hashval;
60 hashval = (const unsigned int *)sha1;
61 if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
63 if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
65 #if CUCKOO_FACTOR >= 3
66 if ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))
69 #if CUCKOO_FACTOR >= 4
70 if ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))
73 #if CUCKOO_FACTOR >= 5
74 if ((obj = obj_hash[H(hashval, 4)]) && !hashcmp(sha1, obj->sha1))
80 static void grow_object_hash(void); /* forward */
83 * A naive single-table cuckoo hashing implementation.
84 * Return NULL when "obj" is successfully inserted. Otherwise
85 * return a pointer to the object to be inserted (which may
86 * be different from the original obj). The caller is expected
87 * to grow the hash table and re-insert the returned object.
89 static struct object *insert_obj_hash(struct object *obj)
93 for (loop = obj_hash_size - obj_hash_size / 8; 0 <= loop; loop--) {
94 struct object *tmp_obj;
96 const unsigned int *hashval;
98 hashval = (const unsigned int *)(obj->sha1);
99 i0 = ix = H(hashval, 0);
100 tmp_obj = obj_hash[i0];
110 #if CUCKOO_FACTOR >= 3
117 #if CUCKOO_FACTOR >= 4
124 #if CUCKOO_FACTOR >= 5
137 static int next_size(int sz)
139 return (sz < 32 ? 32 :
140 (sz < 1024 * 1024 ? 8 : 2) * sz);
143 static void grow_object_hash(void)
145 struct object **current_hash;
148 current_hash = obj_hash;
149 current_size = obj_hash_size;
152 obj_hash_size = next_size(obj_hash_size);
153 obj_hash = xcalloc(obj_hash_size, sizeof(struct object *));
155 for (i = 0; i < current_size; i++) {
156 if (!current_hash[i])
158 if (insert_obj_hash(current_hash[i]))
161 if (i < current_size) {
162 /* too small - grow and retry */
171 void *create_object(const unsigned char *sha1, int type, void *o)
173 struct object *obj = o;
174 struct object *to_insert;
180 hashcpy(obj->sha1, sha1);
187 to_insert = insert_obj_hash(to_insert);
196 struct object *lookup_unknown_object(const unsigned char *sha1)
198 struct object *obj = lookup_object(sha1);
200 obj = create_object(sha1, OBJ_NONE, alloc_object_node());
204 struct object *parse_object_buffer(const unsigned char *sha1, enum object_type type, unsigned long size, void *buffer, int *eaten_p)
210 if (type == OBJ_BLOB) {
211 struct blob *blob = lookup_blob(sha1);
213 if (parse_blob_buffer(blob, buffer, size))
217 } else if (type == OBJ_TREE) {
218 struct tree *tree = lookup_tree(sha1);
221 if (!tree->object.parsed) {
222 if (parse_tree_buffer(tree, buffer, size))
227 } else if (type == OBJ_COMMIT) {
228 struct commit *commit = lookup_commit(sha1);
230 if (parse_commit_buffer(commit, buffer, size))
232 if (!commit->buffer) {
233 commit->buffer = buffer;
236 obj = &commit->object;
238 } else if (type == OBJ_TAG) {
239 struct tag *tag = lookup_tag(sha1);
241 if (parse_tag_buffer(tag, buffer, size))
246 warning("object %s has unknown type id %d\n", sha1_to_hex(sha1), type);
249 if (obj && obj->type == OBJ_NONE)
255 struct object *parse_object(const unsigned char *sha1)
258 enum object_type type;
260 const unsigned char *repl = lookup_replace_object(sha1);
261 void *buffer = read_sha1_file(sha1, &type, &size);
265 if (check_sha1_signature(repl, buffer, size, typename(type)) < 0) {
267 error("sha1 mismatch %s\n", sha1_to_hex(repl));
271 obj = parse_object_buffer(sha1, type, size, buffer, &eaten);
279 struct object_list *object_list_insert(struct object *item,
280 struct object_list **list_p)
282 struct object_list *new_list = xmalloc(sizeof(struct object_list));
283 new_list->item = item;
284 new_list->next = *list_p;
289 int object_list_contains(struct object_list *list, struct object *obj)
292 if (list->item == obj)
299 void add_object_array(struct object *obj, const char *name, struct object_array *array)
301 add_object_array_with_mode(obj, name, array, S_IFINVALID);
304 void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode)
306 unsigned nr = array->nr;
307 unsigned alloc = array->alloc;
308 struct object_array_entry *objects = array->objects;
311 alloc = (alloc + 32) * 2;
312 objects = xrealloc(objects, alloc * sizeof(*objects));
313 array->alloc = alloc;
314 array->objects = objects;
316 objects[nr].item = obj;
317 objects[nr].name = name;
318 objects[nr].mode = mode;
322 void object_array_remove_duplicates(struct object_array *array)
324 unsigned int ref, src, dst;
325 struct object_array_entry *objects = array->objects;
327 for (ref = 0; ref + 1 < array->nr; ref++) {
328 for (src = ref + 1, dst = src;
331 if (!strcmp(objects[ref].name, objects[src].name))
334 objects[dst] = objects[src];