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
);
219 struct object
*parse_object_or_die(const unsigned char *sha1
,
222 struct object
*o
= parse_object(sha1
);
226 die(_("unable to parse object: %s"), name
? name
: sha1_to_hex(sha1
));
229 struct object
*parse_object(const unsigned char *sha1
)
232 enum object_type type
;
234 const unsigned char *repl
= lookup_replace_object(sha1
);
238 obj
= lookup_object(sha1
);
239 if (obj
&& obj
->parsed
)
242 if ((obj
&& obj
->type
== OBJ_BLOB
) ||
243 (!obj
&& has_sha1_file(sha1
) &&
244 sha1_object_info(sha1
, NULL
) == OBJ_BLOB
)) {
245 if (check_sha1_signature(repl
, NULL
, 0, NULL
) < 0) {
246 error("sha1 mismatch %s", sha1_to_hex(repl
));
249 parse_blob_buffer(lookup_blob(sha1
), NULL
, 0);
250 return lookup_object(sha1
);
253 buffer
= read_sha1_file(sha1
, &type
, &size
);
255 if (check_sha1_signature(repl
, buffer
, size
, typename(type
)) < 0) {
257 error("sha1 mismatch %s", sha1_to_hex(repl
));
261 obj
= parse_object_buffer(sha1
, type
, size
, buffer
, &eaten
);
269 struct object_list
*object_list_insert(struct object
*item
,
270 struct object_list
**list_p
)
272 struct object_list
*new_list
= xmalloc(sizeof(struct object_list
));
273 new_list
->item
= item
;
274 new_list
->next
= *list_p
;
279 int object_list_contains(struct object_list
*list
, struct object
*obj
)
282 if (list
->item
== obj
)
290 * A zero-length string to which object_array_entry::name can be
291 * initialized without requiring a malloc/free.
293 static char object_array_slopbuf
[1];
295 static void add_object_array_with_mode_context(struct object
*obj
, const char *name
,
296 struct object_array
*array
,
298 struct object_context
*context
)
300 unsigned nr
= array
->nr
;
301 unsigned alloc
= array
->alloc
;
302 struct object_array_entry
*objects
= array
->objects
;
303 struct object_array_entry
*entry
;
306 alloc
= (alloc
+ 32) * 2;
307 objects
= xrealloc(objects
, alloc
* sizeof(*objects
));
308 array
->alloc
= alloc
;
309 array
->objects
= objects
;
311 entry
= &objects
[nr
];
316 /* Use our own empty string instead of allocating one: */
317 entry
->name
= object_array_slopbuf
;
319 entry
->name
= xstrdup(name
);
321 entry
->context
= context
;
325 void add_object_array(struct object
*obj
, const char *name
, struct object_array
*array
)
327 add_object_array_with_mode(obj
, name
, array
, S_IFINVALID
);
330 void add_object_array_with_mode(struct object
*obj
, const char *name
, struct object_array
*array
, unsigned mode
)
332 add_object_array_with_mode_context(obj
, name
, array
, mode
, NULL
);
335 void add_object_array_with_context(struct object
*obj
, const char *name
, struct object_array
*array
, struct object_context
*context
)
338 add_object_array_with_mode_context(obj
, name
, array
, context
->mode
, context
);
340 add_object_array_with_mode_context(obj
, name
, array
, S_IFINVALID
, context
);
343 void object_array_filter(struct object_array
*array
,
344 object_array_each_func_t want
, void *cb_data
)
346 unsigned nr
= array
->nr
, src
, dst
;
347 struct object_array_entry
*objects
= array
->objects
;
349 for (src
= dst
= 0; src
< nr
; src
++) {
350 if (want(&objects
[src
], cb_data
)) {
352 objects
[dst
] = objects
[src
];
355 if (objects
[src
].name
!= object_array_slopbuf
)
356 free(objects
[src
].name
);
363 * Return true iff array already contains an entry with name.
365 static int contains_name(struct object_array
*array
, const char *name
)
367 unsigned nr
= array
->nr
, i
;
368 struct object_array_entry
*object
= array
->objects
;
370 for (i
= 0; i
< nr
; i
++, object
++)
371 if (!strcmp(object
->name
, name
))
376 void object_array_remove_duplicates(struct object_array
*array
)
378 unsigned nr
= array
->nr
, src
;
379 struct object_array_entry
*objects
= array
->objects
;
382 for (src
= 0; src
< nr
; src
++) {
383 if (!contains_name(array
, objects
[src
].name
)) {
384 if (src
!= array
->nr
)
385 objects
[array
->nr
] = objects
[src
];
388 if (objects
[src
].name
!= object_array_slopbuf
)
389 free(objects
[src
].name
);
394 void clear_object_flags(unsigned flags
)
398 for (i
=0; i
< obj_hash_size
; i
++) {
399 struct object
*obj
= obj_hash
[i
];
401 obj
->flags
&= ~flags
;