]>
git.proxmox.com Git - libgit2.git/blob - src/oid.c
8d45e4d7d52c236fc6be221e5a13444391b835f2
2 * Copyright (C) the libgit2 contributors. All rights reserved.
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.
11 #include "repository.h"
16 static char to_hex
[] = "0123456789abcdef";
18 static int oid_error_invalid(const char *msg
)
20 git_error_set(GIT_ERROR_INVALID
, "unable to parse OID - %s", msg
);
24 int git_oid_fromstrn(git_oid
*out
, const char *str
, size_t length
)
32 return oid_error_invalid("too short");
34 if (length
> GIT_OID_HEXSZ
)
35 return oid_error_invalid("too long");
37 memset(out
->id
, 0, GIT_OID_RAWSZ
);
39 for (p
= 0; p
< length
; p
++) {
40 v
= git__fromhex(str
[p
]);
42 return oid_error_invalid("contains invalid characters");
44 out
->id
[p
/ 2] |= (unsigned char)(v
<< (p
% 2 ? 0 : 4));
50 int git_oid_fromstrp(git_oid
*out
, const char *str
)
52 return git_oid_fromstrn(out
, str
, strlen(str
));
55 int git_oid_fromstr(git_oid
*out
, const char *str
)
57 return git_oid_fromstrn(out
, str
, GIT_OID_HEXSZ
);
60 GIT_INLINE(char) *fmt_one(char *str
, unsigned int val
)
62 *str
++ = to_hex
[val
>> 4];
63 *str
++ = to_hex
[val
& 0xf];
67 void git_oid_nfmt(char *str
, size_t n
, const git_oid
*oid
)
75 if (n
> GIT_OID_HEXSZ
) {
76 memset(&str
[GIT_OID_HEXSZ
], 0, n
- GIT_OID_HEXSZ
);
82 for (i
= 0; i
< max_i
; i
++)
83 str
= fmt_one(str
, oid
->id
[i
]);
86 *str
++ = to_hex
[oid
->id
[i
] >> 4];
89 void git_oid_fmt(char *str
, const git_oid
*oid
)
91 git_oid_nfmt(str
, GIT_OID_HEXSZ
, oid
);
94 void git_oid_pathfmt(char *str
, const git_oid
*oid
)
98 str
= fmt_one(str
, oid
->id
[0]);
100 for (i
= 1; i
< sizeof(oid
->id
); i
++)
101 str
= fmt_one(str
, oid
->id
[i
]);
104 char *git_oid_tostr_s(const git_oid
*oid
)
106 char *str
= GIT_GLOBAL
->oid_fmt
;
107 git_oid_nfmt(str
, GIT_OID_HEXSZ
+ 1, oid
);
111 char *git_oid_allocfmt(const git_oid
*oid
)
113 char *str
= git__malloc(GIT_OID_HEXSZ
+ 1);
116 git_oid_nfmt(str
, GIT_OID_HEXSZ
+ 1, oid
);
120 char *git_oid_tostr(char *out
, size_t n
, const git_oid
*oid
)
125 if (n
> GIT_OID_HEXSZ
+ 1)
126 n
= GIT_OID_HEXSZ
+ 1;
128 git_oid_nfmt(out
, n
- 1, oid
); /* allow room for terminating NUL */
135 git_oid
*oid
, const char **buffer_out
,
136 const char *buffer_end
, const char *header
)
138 const size_t sha_len
= GIT_OID_HEXSZ
;
139 const size_t header_len
= strlen(header
);
141 const char *buffer
= *buffer_out
;
143 if (buffer
+ (header_len
+ sha_len
+ 1) > buffer_end
)
146 if (memcmp(buffer
, header
, header_len
) != 0)
149 if (buffer
[header_len
+ sha_len
] != '\n')
152 if (git_oid_fromstr(oid
, buffer
+ header_len
) < 0)
155 *buffer_out
= buffer
+ (header_len
+ sha_len
+ 1);
160 void git_oid__writebuf(git_buf
*buf
, const char *header
, const git_oid
*oid
)
162 char hex_oid
[GIT_OID_HEXSZ
];
164 git_oid_fmt(hex_oid
, oid
);
165 git_buf_puts(buf
, header
);
166 git_buf_put(buf
, hex_oid
, GIT_OID_HEXSZ
);
167 git_buf_putc(buf
, '\n');
170 void git_oid_fromraw(git_oid
*out
, const unsigned char *raw
)
172 memcpy(out
->id
, raw
, sizeof(out
->id
));
175 void git_oid_cpy(git_oid
*out
, const git_oid
*src
)
177 memcpy(out
->id
, src
->id
, sizeof(out
->id
));
180 int git_oid_cmp(const git_oid
*a
, const git_oid
*b
)
182 return git_oid__cmp(a
, b
);
185 int git_oid_equal(const git_oid
*a
, const git_oid
*b
)
187 return (git_oid__cmp(a
, b
) == 0);
190 int git_oid_ncmp(const git_oid
*oid_a
, const git_oid
*oid_b
, size_t len
)
192 const unsigned char *a
= oid_a
->id
;
193 const unsigned char *b
= oid_b
->id
;
195 if (len
> GIT_OID_HEXSZ
)
207 if ((*a
^ *b
) & 0xf0)
213 int git_oid_strcmp(const git_oid
*oid_a
, const char *str
)
215 const unsigned char *a
;
216 unsigned char strval
;
219 for (a
= oid_a
->id
; *str
&& (a
- oid_a
->id
) < GIT_OID_RAWSZ
; ++a
) {
220 if ((hexval
= git__fromhex(*str
++)) < 0)
222 strval
= (unsigned char)(hexval
<< 4);
224 if ((hexval
= git__fromhex(*str
++)) < 0)
229 return (*a
- strval
);
235 int git_oid_streq(const git_oid
*oid_a
, const char *str
)
237 return git_oid_strcmp(oid_a
, str
) == 0 ? 0 : -1;
240 int git_oid_iszero(const git_oid
*oid_a
)
242 const unsigned char *a
= oid_a
->id
;
244 for (i
= 0; i
< GIT_OID_RAWSZ
; ++i
, ++a
)
250 typedef short node_index
;
254 node_index children
[16];
257 struct git_oid_shorten
{
259 size_t node_count
, size
;
260 int min_length
, full
;
263 static int resize_trie(git_oid_shorten
*self
, size_t new_size
)
265 self
->nodes
= git__reallocarray(self
->nodes
, new_size
, sizeof(trie_node
));
266 GIT_ERROR_CHECK_ALLOC(self
->nodes
);
268 if (new_size
> self
->size
) {
269 memset(&self
->nodes
[self
->size
], 0x0, (new_size
- self
->size
) * sizeof(trie_node
));
272 self
->size
= new_size
;
276 static trie_node
*push_leaf(git_oid_shorten
*os
, node_index idx
, int push_at
, const char *oid
)
278 trie_node
*node
, *leaf
;
281 if (os
->node_count
>= os
->size
) {
282 if (resize_trie(os
, os
->size
* 2) < 0)
286 idx_leaf
= (node_index
)os
->node_count
++;
288 if (os
->node_count
== SHRT_MAX
) {
293 node
= &os
->nodes
[idx
];
294 node
->children
[push_at
] = -idx_leaf
;
296 leaf
= &os
->nodes
[idx_leaf
];
302 git_oid_shorten
*git_oid_shorten_new(size_t min_length
)
306 assert((size_t)((int)min_length
) == min_length
);
308 os
= git__calloc(1, sizeof(git_oid_shorten
));
312 if (resize_trie(os
, 16) < 0) {
318 os
->min_length
= (int)min_length
;
323 void git_oid_shorten_free(git_oid_shorten
*os
)
328 git__free(os
->nodes
);
334 * What wizardry is this?
336 * This is just a memory-optimized trie: basically a very fancy
337 * 16-ary tree, which is used to store the prefixes of the OID
340 * Read more: http://en.wikipedia.org/wiki/Trie
342 * Magic that happens in this method:
344 * - Each node in the trie is an union, so it can work both as
345 * a normal node, or as a leaf.
347 * - Each normal node points to 16 children (one for each possible
348 * character in the oid). This is *not* stored in an array of
349 * pointers, because in a 64-bit arch this would be sucking
350 * 16*sizeof(void*) = 128 bytes of memory per node, which is
351 * insane. What we do is store Node Indexes, and use these indexes
352 * to look up each node in the om->index array. These indexes are
353 * signed shorts, so this limits the amount of unique OIDs that
354 * fit in the structure to about 20000 (assuming a more or less uniform
357 * - All the nodes in om->index array are stored contiguously in
358 * memory, and each of them is 32 bytes, so we fit 2x nodes per
359 * cache line. Convenient for speed.
361 * - To differentiate the leafs from the normal nodes, we store all
362 * the indexes towards a leaf as a negative index (indexes to normal
363 * nodes are positives). When we find that one of the children for
364 * a node has a negative value, that means it's going to be a leaf.
365 * This reduces the amount of indexes we have by two, but also reduces
366 * the size of each node by 1-4 bytes (the amount we would need to
367 * add a `is_leaf` field): this is good because it allows the nodes
368 * to fit cleanly in cache lines.
370 * - Once we reach an empty children, instead of continuing to insert
371 * new nodes for each remaining character of the OID, we store a pointer
372 * to the tail in the leaf; if the leaf is reached again, we turn it
373 * into a normal node and use the tail to create a new leaf.
375 * This is a pretty good balance between performance and memory usage.
377 int git_oid_shorten_add(git_oid_shorten
*os
, const char *text_oid
)
384 git_error_set(GIT_ERROR_INVALID
, "unable to shorten OID - OID set full");
388 if (text_oid
== NULL
)
389 return os
->min_length
;
394 for (i
= 0; i
< GIT_OID_HEXSZ
; ++i
) {
395 int c
= git__fromhex(text_oid
[i
]);
399 git_error_set(GIT_ERROR_INVALID
, "unable to shorten OID - invalid hex value");
403 node
= &os
->nodes
[idx
];
411 node
= push_leaf(os
, idx
, git__fromhex(tail
[0]), &tail
[1]);
414 git_error_set(GIT_ERROR_INVALID
, "unable to shorten OID - OID set full");
419 if (node
->children
[c
] == 0) {
420 if (push_leaf(os
, idx
, c
, &text_oid
[i
+ 1]) == NULL
) {
422 git_error_set(GIT_ERROR_INVALID
, "unable to shorten OID - OID set full");
428 idx
= node
->children
[c
];
432 node
->children
[c
] = idx
= -idx
;
437 if (++i
> os
->min_length
)
440 return os
->min_length
;