summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--fsck-objects.c5
-rw-r--r--object-refs.c142
-rw-r--r--object.c70
-rw-r--r--object.h4
5 files changed, 149 insertions, 74 deletions
diff --git a/Makefile b/Makefile
index 28517f4c3f..5598f48ba3 100644
--- a/Makefile
+++ b/Makefile
@@ -212,7 +212,7 @@ LIB_OBJS = \
blob.o commit.o connect.o csum-file.o cache-tree.o base85.o \
date.o diff-delta.o entry.o exec_cmd.o ident.o lockfile.o \
object.o pack-check.o patch-delta.o path.o pkt-line.o \
- quote.o read-cache.o refs.o run-command.o dir.o \
+ quote.o read-cache.o refs.o run-command.o dir.o object-refs.o \
server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
diff --git a/fsck-objects.c b/fsck-objects.c
index 2b1aab488f..769bb2a6a7 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -64,6 +64,7 @@ static void check_connectivity(void)
/* Look up all the requirements, warn about missing objects.. */
for (i = 0; i < obj_allocs; i++) {
+ const struct object_refs *refs;
struct object *obj = objs[i];
if (!obj)
@@ -78,8 +79,8 @@ static void check_connectivity(void)
continue;
}
- if (obj->refs) {
- const struct object_refs *refs = obj->refs;
+ refs = lookup_object_refs(obj);
+ if (refs) {
unsigned j;
for (j = 0; j < refs->count; j++) {
struct object *ref = refs->ref[j];
diff --git a/object-refs.c b/object-refs.c
new file mode 100644
index 0000000000..8afa2276fb
--- /dev/null
+++ b/object-refs.c
@@ -0,0 +1,142 @@
+#include "cache.h"
+#include "object.h"
+
+int track_object_refs = 0;
+
+static unsigned int refs_hash_size, nr_object_refs;
+static struct object_refs **refs_hash;
+
+static unsigned int hash_obj(struct object *obj, unsigned int n)
+{
+ unsigned int hash = *(unsigned int *)obj->sha1;
+ return hash % n;
+}
+
+static void grow_refs_hash(void)
+{
+ int i;
+ int new_hash_size = (refs_hash_size + 1000) * 3 / 2;
+ struct object_refs **new_hash;
+
+ new_hash = calloc(new_hash_size, sizeof(struct object_refs *));
+ for (i = 0; i < refs_hash_size; i++) {
+ int j;
+ struct object_refs *ref = refs_hash[i];
+ if (!ref)
+ continue;
+ j = hash_obj(ref->base, new_hash_size);
+ new_hash[j] = ref;
+ }
+ free(refs_hash);
+ refs_hash = new_hash;
+ refs_hash_size = new_hash_size;
+}
+
+static void insert_ref_hash(struct object_refs *ref)
+{
+ int j = hash_obj(ref->base, refs_hash_size);
+
+ while (refs_hash[j]) {
+ j++;
+ if (j >= refs_hash_size)
+ j = 0;
+ }
+ refs_hash[j] = ref;
+}
+
+static void add_object_refs(struct object *obj, struct object_refs *ref)
+{
+ int nr = nr_object_refs + 1;
+
+ if (nr > refs_hash_size * 2 / 3)
+ grow_refs_hash();
+ ref->base = obj;
+ insert_ref_hash(ref);
+ nr_object_refs = nr;
+}
+
+struct object_refs *lookup_object_refs(struct object *obj)
+{
+ int j = hash_obj(obj, refs_hash_size);
+ struct object_refs *ref;
+
+ while ((ref = refs_hash[j]) != NULL) {
+ if (ref->base == obj)
+ break;
+ j++;
+ if (j >= refs_hash_size)
+ j = 0;
+ }
+ return ref;
+}
+
+struct object_refs *alloc_object_refs(unsigned count)
+{
+ 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;
+ }
+
+ /* 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;
+ add_object_refs(obj, refs);
+}
+
+void mark_reachable(struct object *obj, unsigned int mask)
+{
+ const struct object_refs *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;
+ refs = lookup_object_refs(obj);
+ if (refs) {
+ unsigned i;
+ for (i = 0; i < refs->count; i++)
+ mark_reachable(refs->ref[i], mask);
+ }
+}
+
+
diff --git a/object.c b/object.c
index 0f70890a45..e26e319ccd 100644
--- a/object.c
+++ b/object.c
@@ -13,8 +13,6 @@ 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;
@@ -55,7 +53,6 @@ void created_object(const unsigned char *sha1, struct object *obj)
obj->parsed = 0;
memcpy(obj->sha1, sha1, 20);
obj->type = TYPE_NONE;
- obj->refs = NULL;
obj->used = 0;
if (obj_allocs - 1 <= nr_objs * 2) {
@@ -84,73 +81,6 @@ void created_object(const unsigned char *sha1, struct object *obj)
nr_objs++;
}
-struct object_refs *alloc_object_refs(unsigned count)
-{
- 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;
- }
-
- /* 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)
-{
- 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;
- 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);
- }
-}
-
struct object *lookup_object_type(const unsigned char *sha1, const char *type)
{
if (!type) {
diff --git a/object.h b/object.h
index f4ee2e55ba..c537b4b72a 100644
--- a/object.h
+++ b/object.h
@@ -9,6 +9,7 @@ struct object_list {
struct object_refs {
unsigned count;
+ struct object *base;
struct object *ref[FLEX_ARRAY]; /* more */
};
@@ -28,7 +29,6 @@ struct object {
unsigned type : TYPE_BITS;
unsigned flags : FLAG_BITS;
unsigned char sha1[20];
- struct object_refs *refs;
};
extern int track_object_refs;
@@ -41,6 +41,8 @@ static inline const char *typename(unsigned int type)
return type_names[type > TYPE_TAG ? TYPE_BAD : type];
}
+extern struct object_refs *lookup_object_refs(struct object *);
+
/** Internal only **/
struct object *lookup_object(const unsigned char *sha1);