Andrew's git - gitweb.git/blob

   1#include "cache.h"
   2#include "object.h"
   3#include "pack.h"
   4#include "pack-objects.h"
   5
   6static uint32_t locate_object_entry_hash(struct packing_data *pdata,
   7                                         const unsigned char *sha1,
   8                                         int *found)
   9{
  10        uint32_t i, hash, mask = (pdata->index_size - 1);
  11
  12        memcpy(&hash, sha1, sizeof(uint32_t));
  13        i = hash & mask;
  14
  15        while (pdata->index[i] > 0) {
  16                uint32_t pos = pdata->index[i] - 1;
  17
  18                if (!hashcmp(sha1, pdata->objects[pos].idx.sha1)) {
  19                        *found = 1;
  20                        return i;
  21                }
  22
  23                i = (i + 1) & mask;
  24        }
  25
  26        *found = 0;
  27        return i;
  28}
  29
  30static inline uint32_t closest_pow2(uint32_t v)
  31{
  32        v = v - 1;
  33        v |= v >> 1;
  34        v |= v >> 2;
  35        v |= v >> 4;
  36        v |= v >> 8;
  37        v |= v >> 16;
  38        return v + 1;
  39}
  40
  41static void rehash_objects(struct packing_data *pdata)
  42{
  43        uint32_t i;
  44        struct object_entry *entry;
  45
  46        pdata->index_size = closest_pow2(pdata->nr_objects * 3);
  47        if (pdata->index_size < 1024)
  48                pdata->index_size = 1024;
  49
  50        free(pdata->index);
  51        pdata->index = xcalloc(pdata->index_size, sizeof(*pdata->index));
  52
  53        entry = pdata->objects;
  54
  55        for (i = 0; i < pdata->nr_objects; i++) {
  56                int found;
  57                uint32_t ix = locate_object_entry_hash(pdata, entry->idx.sha1, &found);
  58
  59                if (found)
  60                        die("BUG: Duplicate object in hash");
  61
  62                pdata->index[ix] = i + 1;
  63                entry++;
  64        }
  65}
  66
  67struct object_entry *packlist_find(struct packing_data *pdata,
  68                                   const unsigned char *sha1,
  69                                   uint32_t *index_pos)
  70{
  71        uint32_t i;
  72        int found;
  73
  74        if (!pdata->index_size)
  75                return NULL;
  76
  77        i = locate_object_entry_hash(pdata, sha1, &found);
  78
  79        if (index_pos)
  80                *index_pos = i;
  81
  82        if (!found)
  83                return NULL;
  84
  85        return &pdata->objects[pdata->index[i] - 1];
  86}
  87
  88struct object_entry *packlist_alloc(struct packing_data *pdata,
  89                                    const unsigned char *sha1,
  90                                    uint32_t index_pos)
  91{
  92        struct object_entry *new_entry;
  93
  94        if (pdata->nr_objects >= pdata->nr_alloc) {
  95                pdata->nr_alloc = (pdata->nr_alloc  + 1024) * 3 / 2;
  96                pdata->objects = xrealloc(pdata->objects,
  97                                          pdata->nr_alloc * sizeof(*new_entry));
  98        }
  99
 100        new_entry = pdata->objects + pdata->nr_objects++;
 101
 102        memset(new_entry, 0, sizeof(*new_entry));
 103        hashcpy(new_entry->idx.sha1, sha1);
 104
 105        if (pdata->index_size * 3 <= pdata->nr_objects * 4)
 106                rehash_objects(pdata);
 107        else
 108                pdata->index[index_pos] = pdata->nr_objects;
 109
 110        return new_entry;
 111}