packages feed

haskoin-store-1.16.0: cbits/haskoin_store_merge.c

/*
 * The merge operators of haskoin-store. See haskoin_store_merge.h for what
 * each function is for and the formats that it reads and writes.
 */

#include "haskoin_store_merge.h"

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* The numbers of a balance. */
#define BALANCE_FIELDS 5

/* The most entries that the byte in front of a group can count. */
#define MOST_SPENDERS 255

/* Say that a merge failed, the way RocksDB's C API wants it said. */
static char *fail(unsigned char *success, size_t *new_value_length)
{
    *success = 0;
    *new_value_length = 0;
    return NULL;
}

/* A number of 64 bits, most significant byte first. */
static uint64_t read_be64(const unsigned char *bytes)
{
    uint64_t number = 0;
    int i;

    for (i = 0; i < 8; i++) {
        number = (number << 8) | bytes[i];
    }
    return number;
}

static void write_be64(unsigned char *bytes, uint64_t number)
{
    int i;

    for (i = 7; i >= 0; i--) {
        bytes[i] = (unsigned char)(number & 0xff);
        number >>= 8;
    }
}

/*
 * Add the five numbers of a balance, or of a merge record, to five sums.
 * Returns zero if it is not of forty bytes.
 */
static int add_balance(uint64_t *sums, const char *bytes, size_t length)
{
    int i;

    if (length != HASKOIN_STORE_BALANCE_SIZE) {
        return 0;
    }
    for (i = 0; i < BALANCE_FIELDS; i++) {
        /* unsigned, so that it wraps around at 2^64 */
        sums[i] += read_be64((const unsigned char *)bytes + 8 * i);
    }
    return 1;
}

/*
 * The sum of a first balance, if there is one, and of some more.
 */
static char *sum_balances(
    const char *first,
    size_t first_length,
    const char *const *list,
    const size_t *lengths,
    int count,
    unsigned char *success,
    size_t *new_value_length)
{
    uint64_t sums[BALANCE_FIELDS] = {0, 0, 0, 0, 0};
    unsigned char *sum;
    int i;

    if (first != NULL && !add_balance(sums, first, first_length)) {
        return fail(success, new_value_length);
    }
    for (i = 0; i < count; i++) {
        if (!add_balance(sums, list[i], lengths[i])) {
            return fail(success, new_value_length);
        }
    }
    sum = malloc(HASKOIN_STORE_BALANCE_SIZE);
    if (sum == NULL) {
        return fail(success, new_value_length);
    }
    for (i = 0; i < BALANCE_FIELDS; i++) {
        write_be64(sum + 8 * i, sums[i]);
    }
    *success = 1;
    *new_value_length = HASKOIN_STORE_BALANCE_SIZE;
    return (char *)sum;
}

char *haskoin_store_balance_full_merge(
    void *state,
    const char *key,
    size_t key_length,
    const char *existing_value,
    size_t existing_value_length,
    const char *const *operands_list,
    const size_t *operands_list_length,
    int num_operands,
    unsigned char *success,
    size_t *new_value_length)
{
    (void)state;
    (void)key;
    (void)key_length;
    return sum_balances(
        existing_value,
        existing_value_length,
        operands_list,
        operands_list_length,
        num_operands,
        success,
        new_value_length);
}

char *haskoin_store_balance_partial_merge(
    void *state,
    const char *key,
    size_t key_length,
    const char *const *operands_list,
    const size_t *operands_list_length,
    int num_operands,
    unsigned char *success,
    size_t *new_value_length)
{
    (void)state;
    (void)key;
    (void)key_length;
    return sum_balances(NULL, 0, operands_list, operands_list_length, num_operands, success, new_value_length);
}

/*
 * The number of entries that a group says it has, or -1 if its length is
 * not that of so many entries after the byte that counts them.
 */
static int spender_count(const char *group, size_t length)
{
    size_t count;

    if (length < 1) {
        return -1;
    }
    count = (unsigned char)group[0];
    if (length != 1 + count * HASKOIN_STORE_SPENDER_SIZE) {
        return -1;
    }
    return (int)count;
}

/*
 * Put the entries of a group into a list of "*used" entries that is in
 * ascending order of output, each where its output belongs, and in place of
 * the entry that the list has for that output if it has one. The list has
 * room for every entry that it will be given.
 *
 * The number of the output is the first four bytes of an entry, most
 * significant first, so the order of the outputs is the order of those
 * bytes.
 */
static void add_spenders(unsigned char *entries, size_t *used, const char *group, int count)
{
    const size_t size = HASKOIN_STORE_SPENDER_SIZE;
    int i;

    for (i = 0; i < count; i++) {
        const char *entry = group + 1 + (size_t)i * size;
        size_t at = 0;
        int order = 1;

        /* groups are of sixteen outputs: a walk is as good as a search */
        while (at < *used) {
            order = memcmp(entry, entries + at * size, 4);
            if (order <= 0) {
                break;
            }
            at += 1;
        }
        if (at == *used || order < 0) {
            /* a new output: make room for it */
            memmove(entries + (at + 1) * size, entries + at * size, (*used - at) * size);
            *used += 1;
        }
        memcpy(entries + at * size, entry, size);
    }
}

/*
 * The union of a first group, if there is one, and of some more, from the
 * oldest to the newest.
 */
static char *join_spenders(
    const char *first,
    size_t first_length,
    const char *const *list,
    const size_t *lengths,
    int count,
    unsigned char *success,
    size_t *new_value_length)
{
    const size_t size = HASKOIN_STORE_SPENDER_SIZE;
    size_t most = 0;
    size_t used = 0;
    unsigned char *joined;
    int entries;
    int i;

    /* every group is checked before anything is read from one */
    if (first != NULL) {
        entries = spender_count(first, first_length);
        if (entries < 0) {
            return fail(success, new_value_length);
        }
        most += (size_t)entries;
    }
    for (i = 0; i < count; i++) {
        entries = spender_count(list[i], lengths[i]);
        if (entries < 0) {
            return fail(success, new_value_length);
        }
        most += (size_t)entries;
    }

    /* the byte that counts, and room for as many entries as there can be */
    joined = malloc(1 + most * size);
    if (joined == NULL) {
        return fail(success, new_value_length);
    }
    if (first != NULL) {
        add_spenders(joined + 1, &used, first, spender_count(first, first_length));
    }
    for (i = 0; i < count; i++) {
        add_spenders(joined + 1, &used, list[i], spender_count(list[i], lengths[i]));
    }
    if (used > MOST_SPENDERS) {
        free(joined);
        return fail(success, new_value_length);
    }
    joined[0] = (unsigned char)used;
    *success = 1;
    *new_value_length = 1 + used * size;
    return (char *)joined;
}

char *haskoin_store_spender_full_merge(
    void *state,
    const char *key,
    size_t key_length,
    const char *existing_value,
    size_t existing_value_length,
    const char *const *operands_list,
    const size_t *operands_list_length,
    int num_operands,
    unsigned char *success,
    size_t *new_value_length)
{
    (void)state;
    (void)key;
    (void)key_length;
    return join_spenders(
        existing_value,
        existing_value_length,
        operands_list,
        operands_list_length,
        num_operands,
        success,
        new_value_length);
}

char *haskoin_store_spender_partial_merge(
    void *state,
    const char *key,
    size_t key_length,
    const char *const *operands_list,
    const size_t *operands_list_length,
    int num_operands,
    unsigned char *success,
    size_t *new_value_length)
{
    (void)state;
    (void)key;
    (void)key_length;
    return join_spenders(NULL, 0, operands_list, operands_list_length, num_operands, success, new_value_length);
}