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