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 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
  35 static 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
  47 static 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
  58 struct 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
  73 struct 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
  83 static 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
  95 void 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
 124 void 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