Andrew's git - gitweb.git/blob

   1#include "cache.h"
   2#include "object.h"
   3
   4int track_object_refs = 0;
   5
   6static unsigned int refs_hash_size, nr_object_refs;
   7static struct object_refs **refs_hash;
   8
   9static unsigned int hash_obj(struct object *obj, unsigned int n)
  10{
  11        unsigned int hash = *(unsigned int *)obj->sha1;
  12        return hash % n;
  13}
  14
  15static void grow_refs_hash(void)
  16{
  17        int i;
  18        int new_hash_size = (refs_hash_size + 1000) * 3 / 2;
  19        struct object_refs **new_hash;
  20
  21        new_hash = calloc(new_hash_size, sizeof(struct object_refs *));
  22        for (i = 0; i < refs_hash_size; i++) {
  23                int j;
  24                struct object_refs *ref = refs_hash[i];
  25                if (!ref)
  26                        continue;
  27                j = hash_obj(ref->base, new_hash_size);
  28                new_hash[j] = ref;
  29        }
  30        free(refs_hash);
  31        refs_hash = new_hash;
  32        refs_hash_size = new_hash_size;
  33}
  34
  35static void insert_ref_hash(struct object_refs *ref)
  36{
  37        int j = hash_obj(ref->base, refs_hash_size);
  38
  39        while (refs_hash[j]) {
  40                j++;
  41                if (j >= refs_hash_size)
  42                        j = 0;
  43        }
  44        refs_hash[j] = ref;
  45}
  46
  47static void add_object_refs(struct object *obj, struct object_refs *ref)
  48{
  49        int nr = nr_object_refs + 1;
  50
  51        if (nr > refs_hash_size * 2 / 3)
  52                grow_refs_hash();
  53        ref->base = obj;
  54        insert_ref_hash(ref);
  55        nr_object_refs = nr;
  56}
  57
  58struct object_refs *lookup_object_refs(struct object *obj)
  59{
  60        int j = hash_obj(obj, refs_hash_size);
  61        struct object_refs *ref;
  62
  63        while ((ref = refs_hash[j]) != NULL) {
  64                if (ref->base == obj)
  65                        break;
  66                j++;
  67                if (j >= refs_hash_size)
  68                        j = 0;
  69        }
  70        return ref;
  71}
  72
  73struct object_refs *alloc_object_refs(unsigned count)
  74{
  75        struct object_refs *refs;
  76        size_t size = sizeof(*refs) + count*sizeof(struct object *);
  77
  78        refs = xcalloc(1, size);
  79        refs->count = count;
  80        return refs;
  81}
  82
  83static int compare_object_pointers(const void *a, const void *b)
  84{
  85        const struct object * const *pa = a;
  86        const struct object * const *pb = b;
  87        if (*pa == *pb)
  88                return 0;
  89        else if (*pa < *pb)
  90                return -1;
  91        else
  92                return 1;
  93}
  94
  95void set_object_refs(struct object *obj, struct object_refs *refs)
  96{
  97        unsigned int i, j;
  98
  99        /* Do not install empty list of references */
 100        if (refs->count < 1) {
 101                free(refs);
 102                return;
 103        }
 104
 105        /* Sort the list and filter out duplicates */
 106        qsort(refs->ref, refs->count, sizeof(refs->ref[0]),
 107              compare_object_pointers);
 108        for (i = j = 1; i < refs->count; i++) {
 109                if (refs->ref[i] != refs->ref[i - 1])
 110                        refs->ref[j++] = refs->ref[i];
 111        }
 112        if (j < refs->count) {
 113                /* Duplicates were found - reallocate list */
 114                size_t size = sizeof(*refs) + j*sizeof(struct object *);
 115                refs->count = j;
 116                refs = xrealloc(refs, size);
 117        }
 118
 119        for (i = 0; i < refs->count; i++)
 120                refs->ref[i]->used = 1;
 121        add_object_refs(obj, refs);
 122}
 123
 124void mark_reachable(struct object *obj, unsigned int mask)
 125{
 126        const struct object_refs *refs;
 127
 128        if (!track_object_refs)
 129                die("cannot do reachability with object refs turned off");
 130        /* If we've been here already, don't bother */
 131        if (obj->flags & mask)
 132                return;
 133        obj->flags |= mask;
 134        refs = lookup_object_refs(obj);
 135        if (refs) {
 136                unsigned i;
 137                for (i = 0; i < refs->count; i++)
 138                        mark_reachable(refs->ref[i], mask);
 139        }
 140}
 141
 142