]>
Commit | Line | Data |
---|---|---|
c15648cb | 1 | /* |
5e0de328 | 2 | * Copyright (C) 2009-2012 the libgit2 contributors |
c15648cb | 3 | * |
bb742ede VM |
4 | * This file is part of libgit2, distributed under the GNU GPL v2 with |
5 | * a Linking Exception. For full terms see the included COPYING file. | |
c15648cb SP |
6 | */ |
7 | ||
b3be0fc7 | 8 | #include "common.h" |
44908fe7 | 9 | #include "git2/oid.h" |
58519018 | 10 | #include "repository.h" |
c15648cb | 11 | #include <string.h> |
26022f07 | 12 | #include <limits.h> |
c15648cb | 13 | |
af795e49 | 14 | static char to_hex[] = "0123456789abcdef"; |
c15648cb | 15 | |
7c7ff7d1 RB |
16 | static int oid_error_invalid(const char *msg) |
17 | { | |
18 | giterr_set(GITERR_INVALID, "Unable to parse OID - %s", msg); | |
19 | return -1; | |
20 | } | |
21 | ||
d5afc039 | 22 | int git_oid_fromstrn(git_oid *out, const char *str, size_t length) |
c15648cb | 23 | { |
0ef9d2aa | 24 | size_t p; |
e724b058 | 25 | int v; |
d5afc039 VM |
26 | |
27 | if (length > GIT_OID_HEXSZ) | |
28 | length = GIT_OID_HEXSZ; | |
29 | ||
e724b058 | 30 | for (p = 0; p < length - 1; p += 2) { |
eb8de747 | 31 | v = (git__fromhex(str[p + 0]) << 4) |
32 | | git__fromhex(str[p + 1]); | |
d5afc039 | 33 | |
c15648cb | 34 | if (v < 0) |
7c7ff7d1 | 35 | return oid_error_invalid("contains invalid characters"); |
d5afc039 VM |
36 | |
37 | out->id[p / 2] = (unsigned char)v; | |
c15648cb | 38 | } |
d5afc039 | 39 | |
e724b058 | 40 | if (length % 2) { |
eb8de747 | 41 | v = (git__fromhex(str[p + 0]) << 4); |
0e058e78 | 42 | if (v < 0) |
7c7ff7d1 | 43 | return oid_error_invalid("contains invalid characters"); |
0e058e78 | 44 | |
e724b058 DI |
45 | out->id[p / 2] = (unsigned char)v; |
46 | p += 2; | |
47 | } | |
48 | ||
6d8d3f19 | 49 | memset(out->id + p / 2, 0, (GIT_OID_HEXSZ - p) / 2); |
d5afc039 | 50 | |
7c7ff7d1 | 51 | return 0; |
c15648cb | 52 | } |
af795e49 | 53 | |
d5afc039 VM |
54 | int git_oid_fromstr(git_oid *out, const char *str) |
55 | { | |
56 | return git_oid_fromstrn(out, str, GIT_OID_HEXSZ); | |
57 | } | |
58 | ||
213e720c | 59 | GIT_INLINE(char) *fmt_one(char *str, unsigned int val) |
af795e49 SP |
60 | { |
61 | *str++ = to_hex[val >> 4]; | |
62 | *str++ = to_hex[val & 0xf]; | |
63 | return str; | |
64 | } | |
65 | ||
66 | void git_oid_fmt(char *str, const git_oid *oid) | |
67 | { | |
0ef9d2aa | 68 | size_t i; |
af795e49 SP |
69 | |
70 | for (i = 0; i < sizeof(oid->id); i++) | |
71 | str = fmt_one(str, oid->id[i]); | |
72 | } | |
73 | ||
74 | void git_oid_pathfmt(char *str, const git_oid *oid) | |
75 | { | |
0ef9d2aa | 76 | size_t i; |
af795e49 SP |
77 | |
78 | str = fmt_one(str, oid->id[0]); | |
79 | *str++ = '/'; | |
80 | for (i = 1; i < sizeof(oid->id); i++) | |
81 | str = fmt_one(str, oid->id[i]); | |
82 | } | |
83 | ||
84 | char *git_oid_allocfmt(const git_oid *oid) | |
85 | { | |
64a47c01 | 86 | char *str = git__malloc(GIT_OID_HEXSZ + 1); |
af795e49 SP |
87 | if (!str) |
88 | return NULL; | |
89 | git_oid_fmt(str, oid); | |
90 | str[GIT_OID_HEXSZ] = '\0'; | |
91 | return str; | |
92 | } | |
960ca1d7 | 93 | |
5621d809 | 94 | char *git_oid_tostr(char *out, size_t n, const git_oid *oid) |
960ca1d7 RJ |
95 | { |
96 | char str[GIT_OID_HEXSZ]; | |
97 | ||
98 | if (!out || n == 0 || !oid) | |
99 | return ""; | |
100 | ||
87d9869f | 101 | n--; /* allow room for terminating NUL */ |
960ca1d7 RJ |
102 | |
103 | if (n > 0) { | |
104 | git_oid_fmt(str, oid); | |
552e23ba RJ |
105 | if (n > GIT_OID_HEXSZ) |
106 | n = GIT_OID_HEXSZ; | |
107 | memcpy(out, str, n); | |
960ca1d7 RJ |
108 | } |
109 | ||
110 | out[n] = '\0'; | |
111 | ||
112 | return out; | |
113 | } | |
114 | ||
7c7ff7d1 RB |
115 | int git_oid__parse( |
116 | git_oid *oid, const char **buffer_out, | |
117 | const char *buffer_end, const char *header) | |
58519018 VM |
118 | { |
119 | const size_t sha_len = GIT_OID_HEXSZ; | |
120 | const size_t header_len = strlen(header); | |
121 | ||
720d5472 | 122 | const char *buffer = *buffer_out; |
58519018 VM |
123 | |
124 | if (buffer + (header_len + sha_len + 1) > buffer_end) | |
73fe6a8e | 125 | return -1; |
58519018 VM |
126 | |
127 | if (memcmp(buffer, header, header_len) != 0) | |
73fe6a8e | 128 | return -1; |
58519018 VM |
129 | |
130 | if (buffer[header_len + sha_len] != '\n') | |
73fe6a8e | 131 | return -1; |
58519018 | 132 | |
7c7ff7d1 RB |
133 | if (git_oid_fromstr(oid, buffer + header_len) < 0) |
134 | return -1; | |
58519018 VM |
135 | |
136 | *buffer_out = buffer + (header_len + sha_len + 1); | |
137 | ||
7c7ff7d1 | 138 | return 0; |
58519018 VM |
139 | } |
140 | ||
afeecf4f VM |
141 | void git_oid__writebuf(git_buf *buf, const char *header, const git_oid *oid) |
142 | { | |
143 | char hex_oid[GIT_OID_HEXSZ]; | |
144 | ||
145 | git_oid_fmt(hex_oid, oid); | |
146 | git_buf_puts(buf, header); | |
147 | git_buf_put(buf, hex_oid, GIT_OID_HEXSZ); | |
148 | git_buf_putc(buf, '\n'); | |
149 | } | |
150 | ||
fa48608e | 151 | void git_oid_fromraw(git_oid *out, const unsigned char *raw) |
d12299fe VM |
152 | { |
153 | memcpy(out->id, raw, sizeof(out->id)); | |
154 | } | |
155 | ||
156 | void git_oid_cpy(git_oid *out, const git_oid *src) | |
157 | { | |
158 | memcpy(out->id, src->id, sizeof(out->id)); | |
159 | } | |
160 | ||
b8457baa | 161 | int git_oid_ncmp(const git_oid *oid_a, const git_oid *oid_b, size_t len) |
53c0bd81 | 162 | { |
f1d01851 VM |
163 | const unsigned char *a = oid_a->id; |
164 | const unsigned char *b = oid_b->id; | |
165 | ||
166 | do { | |
167 | if (*a != *b) | |
168 | return 1; | |
169 | a++; | |
170 | b++; | |
171 | len -= 2; | |
172 | } while (len > 1); | |
173 | ||
174 | if (len) | |
175 | if ((*a ^ *b) & 0xf0) | |
176 | return 1; | |
177 | ||
178 | return 0; | |
53c0bd81 MP |
179 | } |
180 | ||
34aff010 | 181 | int git_oid_streq(const git_oid *a, const char *str) |
182 | { | |
183 | git_oid id; | |
34aff010 | 184 | |
7c7ff7d1 RB |
185 | if (git_oid_fromstr(&id, str) < 0) |
186 | return -1; | |
34aff010 | 187 | |
7c7ff7d1 | 188 | return git_oid_cmp(a, &id) == 0 ? 0 : -1; |
34aff010 | 189 | } |
190 | ||
74fa4bfa RB |
191 | int git_oid_iszero(const git_oid *oid_a) |
192 | { | |
193 | const unsigned char *a = oid_a->id; | |
194 | unsigned int i; | |
195 | for (i = 0; i < GIT_OID_RAWSZ; ++i, ++a) | |
196 | if (*a != 0) | |
197 | return 0; | |
198 | return 1; | |
199 | } | |
200 | ||
26022f07 VM |
201 | typedef short node_index; |
202 | ||
203 | typedef union { | |
204 | const char *tail; | |
205 | node_index children[16]; | |
206 | } trie_node; | |
207 | ||
208 | struct git_oid_shorten { | |
209 | trie_node *nodes; | |
210 | size_t node_count, size; | |
211 | int min_length, full; | |
212 | }; | |
213 | ||
214 | static int resize_trie(git_oid_shorten *self, size_t new_size) | |
215 | { | |
3286c408 | 216 | self->nodes = git__realloc(self->nodes, new_size * sizeof(trie_node)); |
7c7ff7d1 | 217 | GITERR_CHECK_ALLOC(self->nodes); |
26022f07 VM |
218 | |
219 | if (new_size > self->size) { | |
220 | memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(trie_node)); | |
221 | } | |
222 | ||
223 | self->size = new_size; | |
7c7ff7d1 | 224 | return 0; |
26022f07 VM |
225 | } |
226 | ||
227 | static trie_node *push_leaf(git_oid_shorten *os, node_index idx, int push_at, const char *oid) | |
228 | { | |
229 | trie_node *node, *leaf; | |
230 | node_index idx_leaf; | |
231 | ||
232 | if (os->node_count >= os->size) { | |
7c7ff7d1 | 233 | if (resize_trie(os, os->size * 2) < 0) |
26022f07 VM |
234 | return NULL; |
235 | } | |
236 | ||
237 | idx_leaf = (node_index)os->node_count++; | |
238 | ||
239 | if (os->node_count == SHRT_MAX) | |
240 | os->full = 1; | |
241 | ||
242 | node = &os->nodes[idx]; | |
243 | node->children[push_at] = -idx_leaf; | |
244 | ||
245 | leaf = &os->nodes[idx_leaf]; | |
246 | leaf->tail = oid; | |
247 | ||
248 | return node; | |
249 | } | |
250 | ||
251 | git_oid_shorten *git_oid_shorten_new(size_t min_length) | |
252 | { | |
253 | git_oid_shorten *os; | |
254 | ||
44ef8b1b RB |
255 | assert((size_t)((int)min_length) == min_length); |
256 | ||
7c7ff7d1 | 257 | os = git__calloc(1, sizeof(git_oid_shorten)); |
26022f07 VM |
258 | if (os == NULL) |
259 | return NULL; | |
260 | ||
7c7ff7d1 | 261 | if (resize_trie(os, 16) < 0) { |
3286c408 | 262 | git__free(os); |
26022f07 VM |
263 | return NULL; |
264 | } | |
265 | ||
266 | os->node_count = 1; | |
44ef8b1b | 267 | os->min_length = (int)min_length; |
26022f07 VM |
268 | |
269 | return os; | |
270 | } | |
271 | ||
272 | void git_oid_shorten_free(git_oid_shorten *os) | |
273 | { | |
3286c408 VM |
274 | git__free(os->nodes); |
275 | git__free(os); | |
26022f07 VM |
276 | } |
277 | ||
278 | ||
279 | /* | |
280 | * What wizardry is this? | |
281 | * | |
282 | * This is just a memory-optimized trie: basically a very fancy | |
283 | * 16-ary tree, which is used to store the prefixes of the OID | |
284 | * strings. | |
285 | * | |
286 | * Read more: http://en.wikipedia.org/wiki/Trie | |
287 | * | |
288 | * Magic that happens in this method: | |
289 | * | |
290 | * - Each node in the trie is an union, so it can work both as | |
291 | * a normal node, or as a leaf. | |
292 | * | |
293 | * - Each normal node points to 16 children (one for each possible | |
294 | * character in the oid). This is *not* stored in an array of | |
932d1baf | 295 | * pointers, because in a 64-bit arch this would be sucking |
26022f07 VM |
296 | * 16*sizeof(void*) = 128 bytes of memory per node, which is fucking |
297 | * insane. What we do is store Node Indexes, and use these indexes | |
298 | * to look up each node in the om->index array. These indexes are | |
299 | * signed shorts, so this limits the amount of unique OIDs that | |
300 | * fit in the structure to about 20000 (assuming a more or less uniform | |
301 | * distribution). | |
302 | * | |
303 | * - All the nodes in om->index array are stored contiguously in | |
304 | * memory, and each of them is 32 bytes, so we fit 2x nodes per | |
305 | * cache line. Convenient for speed. | |
306 | * | |
307 | * - To differentiate the leafs from the normal nodes, we store all | |
308 | * the indexes towards a leaf as a negative index (indexes to normal | |
309 | * nodes are positives). When we find that one of the children for | |
310 | * a node has a negative value, that means it's going to be a leaf. | |
311 | * This reduces the amount of indexes we have by two, but also reduces | |
312 | * the size of each node by 1-4 bytes (the amount we would need to | |
313 | * add a `is_leaf` field): this is good because it allows the nodes | |
314 | * to fit cleanly in cache lines. | |
315 | * | |
316 | * - Once we reach an empty children, instead of continuing to insert | |
317 | * new nodes for each remaining character of the OID, we store a pointer | |
318 | * to the tail in the leaf; if the leaf is reached again, we turn it | |
319 | * into a normal node and use the tail to create a new leaf. | |
320 | * | |
321 | * This is a pretty good balance between performance and memory usage. | |
322 | */ | |
323 | int git_oid_shorten_add(git_oid_shorten *os, const char *text_oid) | |
324 | { | |
44ef8b1b RB |
325 | int i; |
326 | bool is_leaf; | |
26022f07 VM |
327 | node_index idx; |
328 | ||
329 | if (os->full) | |
7c7ff7d1 | 330 | return -1; |
26022f07 | 331 | |
f0ab9fda VM |
332 | if (text_oid == NULL) |
333 | return os->min_length; | |
334 | ||
26022f07 | 335 | idx = 0; |
44ef8b1b | 336 | is_leaf = false; |
26022f07 VM |
337 | |
338 | for (i = 0; i < GIT_OID_HEXSZ; ++i) { | |
eb8de747 | 339 | int c = git__fromhex(text_oid[i]); |
26022f07 VM |
340 | trie_node *node; |
341 | ||
7c7ff7d1 RB |
342 | if (c == -1) { |
343 | giterr_set(GITERR_INVALID, "Unable to shorten OID - invalid hex value"); | |
344 | return -1; | |
345 | } | |
26022f07 VM |
346 | |
347 | node = &os->nodes[idx]; | |
348 | ||
349 | if (is_leaf) { | |
350 | const char *tail; | |
351 | ||
352 | tail = node->tail; | |
353 | node->tail = NULL; | |
354 | ||
eb8de747 | 355 | node = push_leaf(os, idx, git__fromhex(tail[0]), &tail[1]); |
7c7ff7d1 | 356 | GITERR_CHECK_ALLOC(node); |
26022f07 VM |
357 | } |
358 | ||
359 | if (node->children[c] == 0) { | |
360 | if (push_leaf(os, idx, c, &text_oid[i + 1]) == NULL) | |
7c7ff7d1 | 361 | return -1; |
26022f07 VM |
362 | break; |
363 | } | |
364 | ||
365 | idx = node->children[c]; | |
44ef8b1b | 366 | is_leaf = false; |
26022f07 VM |
367 | |
368 | if (idx < 0) { | |
369 | node->children[c] = idx = -idx; | |
44ef8b1b | 370 | is_leaf = true; |
26022f07 VM |
371 | } |
372 | } | |
373 | ||
374 | if (++i > os->min_length) | |
375 | os->min_length = i; | |
376 | ||
377 | return os->min_length; | |
378 | } | |
379 |