|
Packit Service |
20376f |
/*
|
|
Packit Service |
20376f |
* Copyright (C) the libgit2 contributors. All rights reserved.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* This file is part of libgit2, distributed under the GNU GPL v2 with
|
|
Packit Service |
20376f |
* a Linking Exception. For full terms see the included COPYING file.
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#include "common.h"
|
|
Packit Service |
20376f |
#include "git2/oid.h"
|
|
Packit Service |
20376f |
#include "repository.h"
|
|
Packit Service |
20376f |
#include "global.h"
|
|
Packit Service |
20376f |
#include <string.h>
|
|
Packit Service |
20376f |
#include <limits.h>
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static char to_hex[] = "0123456789abcdef";
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int oid_error_invalid(const char *msg)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
giterr_set(GITERR_INVALID, "unable to parse OID - %s", msg);
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_fromstrn(git_oid *out, const char *str, size_t length)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
size_t p;
|
|
Packit Service |
20376f |
int v;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
assert(out && str);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (!length)
|
|
Packit Service |
20376f |
return oid_error_invalid("too short");
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (length > GIT_OID_HEXSZ)
|
|
Packit Service |
20376f |
return oid_error_invalid("too long");
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
memset(out->id, 0, GIT_OID_RAWSZ);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (p = 0; p < length; p++) {
|
|
Packit Service |
20376f |
v = git__fromhex(str[p]);
|
|
Packit Service |
20376f |
if (v < 0)
|
|
Packit Service |
20376f |
return oid_error_invalid("contains invalid characters");
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
out->id[p / 2] |= (unsigned char)(v << (p % 2 ? 0 : 4));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_fromstrp(git_oid *out, const char *str)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return git_oid_fromstrn(out, str, strlen(str));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_fromstr(git_oid *out, const char *str)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return git_oid_fromstrn(out, str, GIT_OID_HEXSZ);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
GIT_INLINE(char) *fmt_one(char *str, unsigned int val)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
*str++ = to_hex[val >> 4];
|
|
Packit Service |
20376f |
*str++ = to_hex[val & 0xf];
|
|
Packit Service |
20376f |
return str;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_nfmt(char *str, size_t n, const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
size_t i, max_i;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (!oid) {
|
|
Packit Service |
20376f |
memset(str, 0, n);
|
|
Packit Service |
20376f |
return;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
if (n > GIT_OID_HEXSZ) {
|
|
Packit Service |
20376f |
memset(&str[GIT_OID_HEXSZ], 0, n - GIT_OID_HEXSZ);
|
|
Packit Service |
20376f |
n = GIT_OID_HEXSZ;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
max_i = n / 2;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (i = 0; i < max_i; i++)
|
|
Packit Service |
20376f |
str = fmt_one(str, oid->id[i]);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (n & 1)
|
|
Packit Service |
20376f |
*str++ = to_hex[oid->id[i] >> 4];
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_fmt(char *str, const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
git_oid_nfmt(str, GIT_OID_HEXSZ, oid);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_pathfmt(char *str, const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
size_t i;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
str = fmt_one(str, oid->id[0]);
|
|
Packit Service |
20376f |
*str++ = '/';
|
|
Packit Service |
20376f |
for (i = 1; i < sizeof(oid->id); i++)
|
|
Packit Service |
20376f |
str = fmt_one(str, oid->id[i]);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
char *git_oid_tostr_s(const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
char *str = GIT_GLOBAL->oid_fmt;
|
|
Packit Service |
20376f |
git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid);
|
|
Packit Service |
20376f |
return str;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
char *git_oid_allocfmt(const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
char *str = git__malloc(GIT_OID_HEXSZ + 1);
|
|
Packit Service |
20376f |
if (!str)
|
|
Packit Service |
20376f |
return NULL;
|
|
Packit Service |
20376f |
git_oid_nfmt(str, GIT_OID_HEXSZ + 1, oid);
|
|
Packit Service |
20376f |
return str;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
char *git_oid_tostr(char *out, size_t n, const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
if (!out || n == 0)
|
|
Packit Service |
20376f |
return "";
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (n > GIT_OID_HEXSZ + 1)
|
|
Packit Service |
20376f |
n = GIT_OID_HEXSZ + 1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
git_oid_nfmt(out, n - 1, oid); /* allow room for terminating NUL */
|
|
Packit Service |
20376f |
out[n - 1] = '\0';
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return out;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid__parse(
|
|
Packit Service |
20376f |
git_oid *oid, const char **buffer_out,
|
|
Packit Service |
20376f |
const char *buffer_end, const char *header)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
const size_t sha_len = GIT_OID_HEXSZ;
|
|
Packit Service |
20376f |
const size_t header_len = strlen(header);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
const char *buffer = *buffer_out;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (buffer + (header_len + sha_len + 1) > buffer_end)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (memcmp(buffer, header, header_len) != 0)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (buffer[header_len + sha_len] != '\n')
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (git_oid_fromstr(oid, buffer + header_len) < 0)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
*buffer_out = buffer + (header_len + sha_len + 1);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid__writebuf(git_buf *buf, const char *header, const git_oid *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
char hex_oid[GIT_OID_HEXSZ];
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
git_oid_fmt(hex_oid, oid);
|
|
Packit Service |
20376f |
git_buf_puts(buf, header);
|
|
Packit Service |
20376f |
git_buf_put(buf, hex_oid, GIT_OID_HEXSZ);
|
|
Packit Service |
20376f |
git_buf_putc(buf, '\n');
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_fromraw(git_oid *out, const unsigned char *raw)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
memcpy(out->id, raw, sizeof(out->id));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_cpy(git_oid *out, const git_oid *src)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
memcpy(out->id, src->id, sizeof(out->id));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_cmp(const git_oid *a, const git_oid *b)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return git_oid__cmp(a, b);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_equal(const git_oid *a, const git_oid *b)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return (git_oid__cmp(a, b) == 0);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_ncmp(const git_oid *oid_a, const git_oid *oid_b, size_t len)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
const unsigned char *a = oid_a->id;
|
|
Packit Service |
20376f |
const unsigned char *b = oid_b->id;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (len > GIT_OID_HEXSZ)
|
|
Packit Service |
20376f |
len = GIT_OID_HEXSZ;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
while (len > 1) {
|
|
Packit Service |
20376f |
if (*a != *b)
|
|
Packit Service |
20376f |
return 1;
|
|
Packit Service |
20376f |
a++;
|
|
Packit Service |
20376f |
b++;
|
|
Packit Service |
20376f |
len -= 2;
|
|
Packit Service |
20376f |
};
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (len)
|
|
Packit Service |
20376f |
if ((*a ^ *b) & 0xf0)
|
|
Packit Service |
20376f |
return 1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_strcmp(const git_oid *oid_a, const char *str)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
const unsigned char *a;
|
|
Packit Service |
20376f |
unsigned char strval;
|
|
Packit Service |
20376f |
int hexval;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (a = oid_a->id; *str && (a - oid_a->id) < GIT_OID_RAWSZ; ++a) {
|
|
Packit Service |
20376f |
if ((hexval = git__fromhex(*str++)) < 0)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
strval = (unsigned char)(hexval << 4);
|
|
Packit Service |
20376f |
if (*str) {
|
|
Packit Service |
20376f |
if ((hexval = git__fromhex(*str++)) < 0)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
strval |= hexval;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
if (*a != strval)
|
|
Packit Service |
20376f |
return (*a - strval);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_streq(const git_oid *oid_a, const char *str)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return git_oid_strcmp(oid_a, str) == 0 ? 0 : -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
int git_oid_iszero(const git_oid *oid_a)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
const unsigned char *a = oid_a->id;
|
|
Packit Service |
20376f |
unsigned int i;
|
|
Packit Service |
20376f |
for (i = 0; i < GIT_OID_RAWSZ; ++i, ++a)
|
|
Packit Service |
20376f |
if (*a != 0)
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
return 1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
typedef short node_index;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
typedef union {
|
|
Packit Service |
20376f |
const char *tail;
|
|
Packit Service |
20376f |
node_index children[16];
|
|
Packit Service |
20376f |
} trie_node;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
struct git_oid_shorten {
|
|
Packit Service |
20376f |
trie_node *nodes;
|
|
Packit Service |
20376f |
size_t node_count, size;
|
|
Packit Service |
20376f |
int min_length, full;
|
|
Packit Service |
20376f |
};
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int resize_trie(git_oid_shorten *self, size_t new_size)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
self->nodes = git__reallocarray(self->nodes, new_size, sizeof(trie_node));
|
|
Packit Service |
20376f |
GITERR_CHECK_ALLOC(self->nodes);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (new_size > self->size) {
|
|
Packit Service |
20376f |
memset(&self->nodes[self->size], 0x0, (new_size - self->size) * sizeof(trie_node));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
self->size = new_size;
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static trie_node *push_leaf(git_oid_shorten *os, node_index idx, int push_at, const char *oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
trie_node *node, *leaf;
|
|
Packit Service |
20376f |
node_index idx_leaf;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (os->node_count >= os->size) {
|
|
Packit Service |
20376f |
if (resize_trie(os, os->size * 2) < 0)
|
|
Packit Service |
20376f |
return NULL;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
idx_leaf = (node_index)os->node_count++;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (os->node_count == SHRT_MAX) {
|
|
Packit Service |
20376f |
os->full = 1;
|
|
Packit Service |
20376f |
return NULL;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
node = &os->nodes[idx];
|
|
Packit Service |
20376f |
node->children[push_at] = -idx_leaf;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
leaf = &os->nodes[idx_leaf];
|
|
Packit Service |
20376f |
leaf->tail = oid;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return node;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
git_oid_shorten *git_oid_shorten_new(size_t min_length)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
git_oid_shorten *os;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
assert((size_t)((int)min_length) == min_length);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
os = git__calloc(1, sizeof(git_oid_shorten));
|
|
Packit Service |
20376f |
if (os == NULL)
|
|
Packit Service |
20376f |
return NULL;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (resize_trie(os, 16) < 0) {
|
|
Packit Service |
20376f |
git__free(os);
|
|
Packit Service |
20376f |
return NULL;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
os->node_count = 1;
|
|
Packit Service |
20376f |
os->min_length = (int)min_length;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return os;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git_oid_shorten_free(git_oid_shorten *os)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
if (os == NULL)
|
|
Packit Service |
20376f |
return;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
git__free(os->nodes);
|
|
Packit Service |
20376f |
git__free(os);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/*
|
|
Packit Service |
20376f |
* What wizardry is this?
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* This is just a memory-optimized trie: basically a very fancy
|
|
Packit Service |
20376f |
* 16-ary tree, which is used to store the prefixes of the OID
|
|
Packit Service |
20376f |
* strings.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* Read more: http://en.wikipedia.org/wiki/Trie
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* Magic that happens in this method:
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* - Each node in the trie is an union, so it can work both as
|
|
Packit Service |
20376f |
* a normal node, or as a leaf.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* - Each normal node points to 16 children (one for each possible
|
|
Packit Service |
20376f |
* character in the oid). This is *not* stored in an array of
|
|
Packit Service |
20376f |
* pointers, because in a 64-bit arch this would be sucking
|
|
Packit Service |
20376f |
* 16*sizeof(void*) = 128 bytes of memory per node, which is
|
|
Packit Service |
20376f |
* insane. What we do is store Node Indexes, and use these indexes
|
|
Packit Service |
20376f |
* to look up each node in the om->index array. These indexes are
|
|
Packit Service |
20376f |
* signed shorts, so this limits the amount of unique OIDs that
|
|
Packit Service |
20376f |
* fit in the structure to about 20000 (assuming a more or less uniform
|
|
Packit Service |
20376f |
* distribution).
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* - All the nodes in om->index array are stored contiguously in
|
|
Packit Service |
20376f |
* memory, and each of them is 32 bytes, so we fit 2x nodes per
|
|
Packit Service |
20376f |
* cache line. Convenient for speed.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* - To differentiate the leafs from the normal nodes, we store all
|
|
Packit Service |
20376f |
* the indexes towards a leaf as a negative index (indexes to normal
|
|
Packit Service |
20376f |
* nodes are positives). When we find that one of the children for
|
|
Packit Service |
20376f |
* a node has a negative value, that means it's going to be a leaf.
|
|
Packit Service |
20376f |
* This reduces the amount of indexes we have by two, but also reduces
|
|
Packit Service |
20376f |
* the size of each node by 1-4 bytes (the amount we would need to
|
|
Packit Service |
20376f |
* add a `is_leaf` field): this is good because it allows the nodes
|
|
Packit Service |
20376f |
* to fit cleanly in cache lines.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* - Once we reach an empty children, instead of continuing to insert
|
|
Packit Service |
20376f |
* new nodes for each remaining character of the OID, we store a pointer
|
|
Packit Service |
20376f |
* to the tail in the leaf; if the leaf is reached again, we turn it
|
|
Packit Service |
20376f |
* into a normal node and use the tail to create a new leaf.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* This is a pretty good balance between performance and memory usage.
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
int git_oid_shorten_add(git_oid_shorten *os, const char *text_oid)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
int i;
|
|
Packit Service |
20376f |
bool is_leaf;
|
|
Packit Service |
20376f |
node_index idx;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (os->full) {
|
|
Packit Service |
20376f |
giterr_set(GITERR_INVALID, "unable to shorten OID - OID set full");
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (text_oid == NULL)
|
|
Packit Service |
20376f |
return os->min_length;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
idx = 0;
|
|
Packit Service |
20376f |
is_leaf = false;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (i = 0; i < GIT_OID_HEXSZ; ++i) {
|
|
Packit Service |
20376f |
int c = git__fromhex(text_oid[i]);
|
|
Packit Service |
20376f |
trie_node *node;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (c == -1) {
|
|
Packit Service |
20376f |
giterr_set(GITERR_INVALID, "unable to shorten OID - invalid hex value");
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
node = &os->nodes[idx];
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (is_leaf) {
|
|
Packit Service |
20376f |
const char *tail;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
tail = node->tail;
|
|
Packit Service |
20376f |
node->tail = NULL;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
node = push_leaf(os, idx, git__fromhex(tail[0]), &tail[1]);
|
|
Packit Service |
20376f |
if (node == NULL) {
|
|
Packit Service |
20376f |
if (os->full)
|
|
Packit Service |
20376f |
giterr_set(GITERR_INVALID, "unable to shorten OID - OID set full");
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (node->children[c] == 0) {
|
|
Packit Service |
20376f |
if (push_leaf(os, idx, c, &text_oid[i + 1]) == NULL) {
|
|
Packit Service |
20376f |
if (os->full)
|
|
Packit Service |
20376f |
giterr_set(GITERR_INVALID, "unable to shorten OID - OID set full");
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
idx = node->children[c];
|
|
Packit Service |
20376f |
is_leaf = false;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (idx < 0) {
|
|
Packit Service |
20376f |
node->children[c] = idx = -idx;
|
|
Packit Service |
20376f |
is_leaf = true;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (++i > os->min_length)
|
|
Packit Service |
20376f |
os->min_length = i;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return os->min_length;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|