]>
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 | } |