projects / thirdparty / git.git / blame
| Commit | Line | Data |
|---|---|---|
| 2834bc27 VM |
1 | #include "cache.h" |
| 2 | #include "object.h" | |
| 3 | #include "pack.h" | |
| 4 | #include "pack-objects.h" | |
| 5 | ||
| 6 | static 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 | ||
| 30 | static 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 | ||
| 41 | static 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 | ||
| fb799474 RS |
50 | free(pdata->index); |
| 51 | pdata->index = xcalloc(pdata->index_size, sizeof(*pdata->index)); | |
| 2834bc27 VM |
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 | ||
| 67 | struct 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 | ||
| 88 | struct 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 | } |