Merge pull request #833 from carlosmn/odb-one

[libgit2.git] / src / oid.c

/*
 * Copyright (C) 2009-2012 the libgit2 contributors
 *
 * 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 < 4)
                return oid_error_invalid("input too short");

        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 || !oid)
                return "";

        n--; /* allow room for terminating NUL */

        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, unsigned int 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 fucking
 *      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;
}