8 static struct object
**obj_hash
;
9 static int nr_objs
, obj_hash_size
;
11 unsigned int get_max_object_index(void)
16 struct object
*get_indexed_object(unsigned int idx
)
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 */
29 const char *typename(unsigned int type
)
31 if (type
>= ARRAY_SIZE(object_type_strings
))
33 return object_type_strings
[type
];
36 int type_from_string(const char *str
)
40 for (i
= 1; i
< ARRAY_SIZE(object_type_strings
); i
++)
41 if (!strcmp(str
, object_type_strings
[i
]))
43 die("invalid object type \"%s\"", str
);
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.
51 static unsigned int hash_obj(const unsigned char *sha1
, unsigned int n
)
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.
63 memcpy(&hash
, sha1
, sizeof(unsigned int));
64 return hash
& (n
- 1);
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
72 static void insert_obj_hash(struct object
*obj
, struct object
**hash
, unsigned int size
)
74 unsigned int j
= hash_obj(obj
->sha1
, size
);
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.
88 struct object
*lookup_object(const unsigned char *sha1
)
90 unsigned int i
, first
;
96 first
= i
= hash_obj(sha1
, obj_hash_size
);
97 while ((obj
= obj_hash
[i
]) != NULL
) {
98 if (!hashcmp(sha1
, obj
->sha1
))
101 if (i
== obj_hash_size
)
104 if (obj
&& i
!= first
) {
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.
110 struct object
*tmp
= obj_hash
[i
];
111 obj_hash
[i
] = obj_hash
[first
];
112 obj_hash
[first
] = tmp
;
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
122 static void grow_object_hash(void)
126 * Note that this size must always be power-of-2 to match hash_obj
129 int new_hash_size
= obj_hash_size
< 32 ? 32 : 2 * obj_hash_size
;
130 struct object
**new_hash
;
132 new_hash
= xcalloc(new_hash_size
, sizeof(struct object
*));
133 for (i
= 0; i
< obj_hash_size
; i
++) {
134 struct object
*obj
= obj_hash
[i
];
137 insert_obj_hash(obj
, new_hash
, new_hash_size
);
141 obj_hash_size
= new_hash_size
;
144 void *create_object(const unsigned char *sha1
, void *o
)
146 struct object
*obj
= o
;
151 hashcpy(obj
->sha1
, sha1
);
153 if (obj_hash_size
- 1 <= nr_objs
* 2)
156 insert_obj_hash(obj
, obj_hash
, obj_hash_size
);
161 struct object
*lookup_unknown_object(const unsigned char *sha1
)
163 struct object
*obj
= lookup_object(sha1
);
165 obj
= create_object(sha1
, alloc_object_node());
169 struct object
*parse_object_buffer(const unsigned char *sha1
, enum object_type type
, unsigned long size
, void *buffer
, int *eaten_p
)
175 if (type
== OBJ_BLOB
) {
176 struct blob
*blob
= lookup_blob(sha1
);
178 if (parse_blob_buffer(blob
, buffer
, size
))
182 } else if (type
== OBJ_TREE
) {
183 struct tree
*tree
= lookup_tree(sha1
);
187 tree
->object
.parsed
= 0;
188 if (!tree
->object
.parsed
) {
189 if (parse_tree_buffer(tree
, buffer
, size
))
194 } else if (type
== OBJ_COMMIT
) {
195 struct commit
*commit
= lookup_commit(sha1
);
197 if (parse_commit_buffer(commit
, buffer
, size
))
199 if (!get_cached_commit_buffer(commit
, NULL
)) {
200 set_commit_buffer(commit
, buffer
, size
);
203 obj
= &commit
->object
;
205 } else if (type
== OBJ_TAG
) {
206 struct tag
*tag
= lookup_tag(sha1
);
208 if (parse_tag_buffer(tag
, buffer
, size
))
213 warning("object %s has unknown type id %d", sha1_to_hex(sha1
), type
);
216 if (obj
&& obj
->type
== OBJ_NONE
)
221 struct object
*parse_object_or_die(const unsigned char *sha1
,
224 struct object
*o
= parse_object(sha1
);
228 die(_("unable to parse object: %s"), name
? name
: sha1_to_hex(sha1
));
231 struct object
*parse_object(const unsigned char *sha1
)
234 enum object_type type
;
236 const unsigned char *repl
= lookup_replace_object(sha1
);
240 obj
= lookup_object(sha1
);
241 if (obj
&& obj
->parsed
)
244 if ((obj
&& obj
->type
== OBJ_BLOB
) ||
245 (!obj
&& has_sha1_file(sha1
) &&
246 sha1_object_info(sha1
, NULL
) == OBJ_BLOB
)) {
247 if (check_sha1_signature(repl
, NULL
, 0, NULL
) < 0) {
248 error("sha1 mismatch %s", sha1_to_hex(repl
));
251 parse_blob_buffer(lookup_blob(sha1
), NULL
, 0);
252 return lookup_object(sha1
);
255 buffer
= read_sha1_file(sha1
, &type
, &size
);
257 if (check_sha1_signature(repl
, buffer
, size
, typename(type
)) < 0) {
259 error("sha1 mismatch %s", sha1_to_hex(repl
));
263 obj
= parse_object_buffer(sha1
, type
, size
, buffer
, &eaten
);
271 struct object_list
*object_list_insert(struct object
*item
,
272 struct object_list
**list_p
)
274 struct object_list
*new_list
= xmalloc(sizeof(struct object_list
));
275 new_list
->item
= item
;
276 new_list
->next
= *list_p
;
281 int object_list_contains(struct object_list
*list
, struct object
*obj
)
284 if (list
->item
== obj
)
292 * A zero-length string to which object_array_entry::name can be
293 * initialized without requiring a malloc/free.
295 static char object_array_slopbuf
[1];
297 static void add_object_array_with_mode_context(struct object
*obj
, const char *name
,
298 struct object_array
*array
,
300 struct object_context
*context
)
302 unsigned nr
= array
->nr
;
303 unsigned alloc
= array
->alloc
;
304 struct object_array_entry
*objects
= array
->objects
;
305 struct object_array_entry
*entry
;
308 alloc
= (alloc
+ 32) * 2;
309 objects
= xrealloc(objects
, alloc
* sizeof(*objects
));
310 array
->alloc
= alloc
;
311 array
->objects
= objects
;
313 entry
= &objects
[nr
];
318 /* Use our own empty string instead of allocating one: */
319 entry
->name
= object_array_slopbuf
;
321 entry
->name
= xstrdup(name
);
323 entry
->context
= context
;
327 void add_object_array(struct object
*obj
, const char *name
, struct object_array
*array
)
329 add_object_array_with_mode(obj
, name
, array
, S_IFINVALID
);
332 void add_object_array_with_mode(struct object
*obj
, const char *name
, struct object_array
*array
, unsigned mode
)
334 add_object_array_with_mode_context(obj
, name
, array
, mode
, NULL
);
337 void add_object_array_with_context(struct object
*obj
, const char *name
, struct object_array
*array
, struct object_context
*context
)
340 add_object_array_with_mode_context(obj
, name
, array
, context
->mode
, context
);
342 add_object_array_with_mode_context(obj
, name
, array
, S_IFINVALID
, context
);
345 void object_array_filter(struct object_array
*array
,
346 object_array_each_func_t want
, void *cb_data
)
348 unsigned nr
= array
->nr
, src
, dst
;
349 struct object_array_entry
*objects
= array
->objects
;
351 for (src
= dst
= 0; src
< nr
; src
++) {
352 if (want(&objects
[src
], cb_data
)) {
354 objects
[dst
] = objects
[src
];
357 if (objects
[src
].name
!= object_array_slopbuf
)
358 free(objects
[src
].name
);
365 * Return true iff array already contains an entry with name.
367 static int contains_name(struct object_array
*array
, const char *name
)
369 unsigned nr
= array
->nr
, i
;
370 struct object_array_entry
*object
= array
->objects
;
372 for (i
= 0; i
< nr
; i
++, object
++)
373 if (!strcmp(object
->name
, name
))
378 void object_array_remove_duplicates(struct object_array
*array
)
380 unsigned nr
= array
->nr
, src
;
381 struct object_array_entry
*objects
= array
->objects
;
384 for (src
= 0; src
< nr
; src
++) {
385 if (!contains_name(array
, objects
[src
].name
)) {
386 if (src
!= array
->nr
)
387 objects
[array
->nr
] = objects
[src
];
390 if (objects
[src
].name
!= object_array_slopbuf
)
391 free(objects
[src
].name
);
396 void clear_object_flags(unsigned flags
)
400 for (i
=0; i
< obj_hash_size
; i
++) {
401 struct object
*obj
= obj_hash
[i
];
403 obj
->flags
&= ~flags
;