object-refs.c

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