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