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 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
  27static 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
  45static 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
  56struct 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
  71struct 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
  81static 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
  93void 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
 122void 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