X-Git-Url: https://git.octo.it/?p=git.git;a=blobdiff_plain;f=object.c;h=0f70890a4582fec845fb9399b3dc9f388c6538fc;hp=72f6aa552f79edcd5f4f5c4a647ab62503365b1b;hb=HEAD;hpb=f10e0e0b18c8e2e69535e7380fb3c1f9b097cfda diff --git a/object.c b/object.c index 72f6aa55..0f70890a 100644 --- a/object.c +++ b/object.c @@ -1,33 +1,43 @@ +#include "cache.h" #include "object.h" #include "blob.h" #include "tree.h" #include "commit.h" -#include "cache.h" #include "tag.h" struct object **objs; -int nr_objs; -static int obj_allocs; +static int nr_objs; +int obj_allocs; + +const char *type_names[] = { + "none", "blob", "tree", "commit", "bad" +}; + +int track_object_refs = 0; + +static int hashtable_index(const unsigned char *sha1) +{ + unsigned int i; + memcpy(&i, sha1, sizeof(unsigned int)); + return (int)(i % obj_allocs); +} static int find_object(const unsigned char *sha1) { - int first = 0, last = nr_objs; - - while (first < last) { - int next = (first + last) / 2; - struct object *obj = objs[next]; - int cmp; - - cmp = memcmp(sha1, obj->sha1, 20); - if (!cmp) - return next; - if (cmp < 0) { - last = next; - continue; - } - first = next+1; - } - return -first-1; + int i; + + if (!objs) + return -1; + + i = hashtable_index(sha1); + while (objs[i]) { + if (memcmp(sha1, objs[i]->sha1, 20) == 0) + return i; + i++; + if (i == obj_allocs) + i = 0; + } + return -1 - i; } struct object *lookup_object(const unsigned char *sha1) @@ -40,60 +50,104 @@ struct object *lookup_object(const unsigned char *sha1) void created_object(const unsigned char *sha1, struct object *obj) { - int pos = find_object(sha1); + int pos; obj->parsed = 0; memcpy(obj->sha1, sha1, 20); - obj->type = NULL; + obj->type = TYPE_NONE; obj->refs = NULL; obj->used = 0; - if (pos >= 0) - die("Inserting %s twice\n", sha1_to_hex(sha1)); - pos = -pos-1; - - if (obj_allocs == nr_objs) { - obj_allocs = alloc_nr(obj_allocs); + if (obj_allocs - 1 <= nr_objs * 2) { + int i, count = obj_allocs; + obj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs); objs = xrealloc(objs, obj_allocs * sizeof(struct object *)); + memset(objs + count, 0, (obj_allocs - count) + * sizeof(struct object *)); + for (i = 0; i < obj_allocs; i++) + if (objs[i]) { + int j = find_object(objs[i]->sha1); + if (j != i) { + j = -1 - j; + objs[j] = objs[i]; + objs[i] = NULL; + } + } } - /* Insert it into the right place */ - memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * - sizeof(struct object *)); + pos = find_object(sha1); + if (pos >= 0) + die("Inserting %s twice\n", sha1_to_hex(sha1)); + pos = -pos-1; objs[pos] = obj; nr_objs++; } -void add_ref(struct object *refer, struct object *target) +struct object_refs *alloc_object_refs(unsigned count) { - struct object_list **pp = &refer->refs; - struct object_list *p; - - while ((p = *pp) != NULL) { - if (p->item == target) - return; - pp = &p->next; + struct object_refs *refs; + size_t size = sizeof(*refs) + count*sizeof(struct object *); + + refs = xcalloc(1, size); + refs->count = count; + return refs; +} + +static int compare_object_pointers(const void *a, const void *b) +{ + const struct object * const *pa = a; + const struct object * const *pb = b; + if (*pa == *pb) + return 0; + else if (*pa < *pb) + return -1; + else + return 1; +} + +void set_object_refs(struct object *obj, struct object_refs *refs) +{ + unsigned int i, j; + + /* Do not install empty list of references */ + if (refs->count < 1) { + free(refs); + return; } - target->used = 1; - p = xmalloc(sizeof(*p)); - p->item = target; - p->next = NULL; - *pp = p; + /* Sort the list and filter out duplicates */ + qsort(refs->ref, refs->count, sizeof(refs->ref[0]), + compare_object_pointers); + for (i = j = 1; i < refs->count; i++) { + if (refs->ref[i] != refs->ref[i - 1]) + refs->ref[j++] = refs->ref[i]; + } + if (j < refs->count) { + /* Duplicates were found - reallocate list */ + size_t size = sizeof(*refs) + j*sizeof(struct object *); + refs->count = j; + refs = xrealloc(refs, size); + } + + for (i = 0; i < refs->count; i++) + refs->ref[i]->used = 1; + obj->refs = refs; } void mark_reachable(struct object *obj, unsigned int mask) { - struct object_list *p = obj->refs; - + if (!track_object_refs) + die("cannot do reachability with object refs turned off"); /* If we've been here already, don't bother */ if (obj->flags & mask) return; obj->flags |= mask; - while (p) { - mark_reachable(p->item, mask); - p = p->next; + if (obj->refs) { + const struct object_refs *refs = obj->refs; + unsigned i; + for (i = 0; i < refs->count; i++) + mark_reachable(refs->ref[i], mask); } } @@ -127,10 +181,9 @@ struct object *lookup_unknown_object(const unsigned char *sha1) { struct object *obj = lookup_object(sha1); if (!obj) { - union any_object *ret = xmalloc(sizeof(*ret)); - memset(ret, 0, sizeof(*ret)); + union any_object *ret = xcalloc(1, sizeof(*ret)); created_object(sha1, &ret->object); - ret->object.type = NULL; + ret->object.type = TYPE_NONE; return &ret->object; } return obj; @@ -145,15 +198,18 @@ struct object *parse_object(const unsigned char *sha1) struct object *obj; if (check_sha1_signature(sha1, buffer, size, type) < 0) printf("sha1 mismatch %s\n", sha1_to_hex(sha1)); - if (!strcmp(type, "blob")) { + if (!strcmp(type, blob_type)) { struct blob *blob = lookup_blob(sha1); parse_blob_buffer(blob, buffer, size); obj = &blob->object; - } else if (!strcmp(type, "tree")) { + } else if (!strcmp(type, tree_type)) { struct tree *tree = lookup_tree(sha1); - parse_tree_buffer(tree, buffer, size); obj = &tree->object; - } else if (!strcmp(type, "commit")) { + if (!tree->object.parsed) { + parse_tree_buffer(tree, buffer, size); + buffer = NULL; + } + } else if (!strcmp(type, commit_type)) { struct commit *commit = lookup_commit(sha1); parse_commit_buffer(commit, buffer, size); if (!commit->buffer) { @@ -161,7 +217,7 @@ struct object *parse_object(const unsigned char *sha1) buffer = NULL; } obj = &commit->object; - } else if (!strcmp(type, "tag")) { + } else if (!strcmp(type, tag_type)) { struct tag *tag = lookup_tag(sha1); parse_tag_buffer(tag, buffer, size); obj = &tag->object; @@ -184,6 +240,17 @@ struct object_list *object_list_insert(struct object *item, return new_list; } +void object_list_append(struct object *item, + struct object_list **list_p) +{ + while (*list_p) { + list_p = &((*list_p)->next); + } + *list_p = xmalloc(sizeof(struct object_list)); + (*list_p)->next = NULL; + (*list_p)->item = item; +} + unsigned object_list_length(struct object_list *list) { unsigned ret = 0;