2
\$\begingroup\$

I implemented an immutable hash map in C, as described in this paper. First, my design goals:

  • plug-and-playable: compile with gcc -O3 -std=c11 champ.c, #include "champ.h", ready to use
  • #define Key and value types to suit your needs: see Using it as a "champ<string,int>" below
  • Provide reference counting as the default heap policy, but make it easy enough to modify the source to use your own strategy
  • thread safety: persistent collections really start to take off in a multithreaded environment, which is where I intend to use this
  • cache locality: The abovementioned paper puts a lot of focus on improving cache locality, so I wanted to at least match that

Further below you can see what I have so far. It does what it's supposed to, i'm pretty confident that it's correct and stable, I have written extensive tests (84% coverage, up to 98% planned), valgrind comes up clean. However, I still have some big question marks/insecurities:

  • Is the interface well designed?
  • Is my use of const sensible?
    • In particular: what about taking keys/values params as const, which really only has any significance when they are actually pointers.
  • Is there any value in hiding the struct champ implementation if I intend to distribute it as source code anyway?
  • How can I test the implementation (a fairly critical aspect of library development) without subverting/undermining the interface?
  • Is my strategy for dealing with memory management requirements sensible? (making the source accessible and easy to hack)
  • Should I use more typedef's? Maybe instead of CHAMP_VALUE_T?

Of course, any feedback is desired. I really only have a grasp of C semantics, but little experience in developing large scale projects.

Lastly, a short breakdown of the biggest "gotchas":

  • This is a hash trie with a branching factor of 32. It takes a key-value-pair, computes the key's hash (uint32_t), and looks at the five least significant bits, interpreting them as the index in the root node of the trie (2^5 == 32).
  • If the node already contains an entry at that index, but with an unequal key, the current entry and the new key-value-pair are "pushed down". Their hashes are shifted to the right by 5 bits, and the five next least significant bits are used to determine the entries' index in the next level, and the process starts again.
  • This is a persistent data structure, so instead of modifying a node, a copy of that node gets created and modified, which in turn is then inserted into a copy of it's parent node, and so on, until a new root node gets created and inserted into a new hash map.
  • There's 7 "levels" of nodes (32 / 5 = 6.4, the last layer only hash 2 bits of variance). In case of a hash collision - which only happens if the entire hash is equal, so it should happen less often than with conventional hash tables - an 8th layer is created. At that level only a special kind of node gets created (struct collision_node), and that special kind of node only gets created at that level. Therefore I'm using shift >= HASH_TOTAL_WIDTH to determine whether I'm dealing with a regular or a collision node, so I don't have to implement some sort of dynamic dispatch polymorphism.

champ.h:

/*
 * MIT License
 *
 * Copyright (c) 2020 Samuel Vogelsanger <vogelsangersamuel@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef CHAMP_CHAMP_H
#define CHAMP_CHAMP_H

#include <stdint.h>
#include <stddef.h>

#ifndef DEBUG_PRINT
#ifdef DEBUG
#define DBG 1
#else
#define DBG 0
#endif
#define DEBUG_PRINT(fmt, ...) \
            do { if (DBG) fprintf(stderr, "DEBUG: champ: " fmt, __VA_ARGS__); } while (0)
#endif

#ifndef CHAMP_KEY_T
#define CHAMP_KEY_T void*
#endif

#ifndef CHAMP_VALUE_T
#define CHAMP_VALUE_T void*
#endif

/**
 * These are mostly for convenience
 */

#define CHAMP_HASHFN_T(name) uint32_t (*name)(const CHAMP_KEY_T)
#define CHAMP_EQUALSFN_T(name) int (*name)(const CHAMP_KEY_T left, const CHAMP_KEY_T right)
#define CHAMP_ASSOCFN_T(name) CHAMP_VALUE_T (*name)(const CHAMP_KEY_T key, const CHAMP_VALUE_T old_value, void *user_data)
#define CHAMP_VALUE_EQUALSFN_T(name) int (*name)(const CHAMP_VALUE_T left, const CHAMP_VALUE_T right)


/**
 * These macros help with defining the various callbacks. Use them like so:
 * @code{c}
 * CHAMP_MAKE_EQUALSFN(equals_int, left, right)
 * {
 *     return left == right;
 * }
 * @endcode
 */

#define CHAMP_MAKE_HASHFN(name, arg_1) uint32_t name(const CHAMP_KEY_T arg_1)
#define CHAMP_MAKE_EQUALSFN(name, arg_l, arg_r) int name(const CHAMP_KEY_T arg_l, const CHAMP_KEY_T arg_r)
#define CHAMP_MAKE_ASSOCFN(name, key_arg, value_arg, user_data_arg) CHAMP_VALUE_T name(const CHAMP_KEY_T key_arg, const CHAMP_VALUE_T value_arg, void *user_data_arg)
#define CHAMP_MAKE_VALUE_EQUALSFN(name, arg_l, arg_r) int name(const CHAMP_VALUE_T arg_l, const CHAMP_VALUE_T arg_r)

// todo: replace with something like: "typedef struct champ champ;" to hide implementation details.
struct champ {
    volatile uint32_t ref_count;
    unsigned length;
    struct node *root;

    CHAMP_HASHFN_T(hash);
    CHAMP_EQUALSFN_T(equals);
};

/**
 * Creates a new map with the given hash and equals functions. This implementation is based on the assumption that if
 * two keys are equal, their hashes must be equal as well. This is commonly known as the Java Hashcode contract.
 *
 * The reference count of a new map is zero.
 *
 * @param hash
 * @param equals
 * @return
 */
struct champ *champ_new(CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals));

/**
 * Destroys a champ. Doesn't clean up the stored key-value-pairs.
 *
 * @param old
 */
void champ_destroy(struct champ **champ);

/**
 * Atomically increases the reference count of a map.
 *
 * @param champ
 * @return
 */
struct champ *champ_acquire(const struct champ *champ);

/**
 * Atomically decreases the reference count of a map and calls champ_destroy if it caused the count to drop to zero.
 *
 * In either case then sets the reference to NULL.
 *
 * @param champ
 */
void champ_release(struct champ **champ);

/**
 * Returns the number of entries in champ.
 *
 * @param champ
 * @return the number of entries
 */
unsigned champ_length(const struct champ *champ);

/**
 * Looks up key and sets *value_receiver to the associated value. Doesn't change value_receiver if key is not set.
 *
 * @param champ
 * @param key
 * @param found is set to 0 if key is not set
 * @return
 */
CHAMP_VALUE_T champ_get(const struct champ *champ, const CHAMP_KEY_T key, int *found);

/**
 * Returns a new map derived from champ but with key set to value.
 * If replaced is not NULL, sets it to indicate if the key is present in champ.
 *
 * Reference count of the new map is zero.
 *
 * @param champ
 * @param key
 * @param value
 * @param replaced
 * @return a new champ
 */
struct champ *champ_set(const struct champ *champ, const CHAMP_KEY_T key, const CHAMP_VALUE_T value, int *replaced);

/**
 * Returns a new map derived from champ but without a mapping for key.
 *
 * Reference count of the new map is zero.
 *
 * @param champ
 * @param key
 * @param modified
 * @return
 */
struct champ *champ_del(const struct champ *champ, const CHAMP_KEY_T key, int *modified);

/**
 * Creates a new champ with the given hash and equals functions, and inserts the given keys and values.
 * Only the first 'length' elements from keys and values are inserted.
 *
 * Reference count of the new map is zero.
 *
 * @param hash
 * @param equals
 * @param keys
 * @param values
 * @param length
 * @return
 */
struct champ *champ_of(CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals), CHAMP_KEY_T *keys, CHAMP_VALUE_T *values, size_t length);

/**
 * Returns a new map derived from champ, but with key set to the return value of fn.
 * fn is passed the key, the current value for key, and user_data.
 * If key is not present in champ, NULL is passed in place of the key and current value.
 *
 * Reference count of the new map is zero.
 *
 * @param champ
 * @param key
 * @param fn
 * @param user_data
 * @return
 */
struct champ *champ_assoc(const struct champ *champ, const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn), const void *user_data);

/**
 * Compares two maps for equality. A lot of short-circuiting is done on the assumption that unequal hashes
 * (for both keys and values) imply inequality. This is commonly known as the Java Hashcode contract: If two values
 * are equal, their hashes must be equal as well.
 *
 * @param left
 * @param right
 * @return
 */
int champ_equals(const struct champ *left, const struct champ *right, CHAMP_VALUE_EQUALSFN_T(value_equals));

/**
 * An iterator for champ. Meant to be put on the stack.
 */
struct champ_iter {
    int stack_level;
    unsigned element_cursor;
    unsigned element_arity;
    unsigned branch_cursor_stack[8];
    unsigned branch_arity_stack[8];
    const void *node_stack[8];
};

/**
 * Initializes an iterator with a champ.
 *
 * Example:
 * @code{.c}
 * struct champ_iter iter;
 * CHAMP_KEY_T key;
 * CHAMP_VAL_T val;
 *
 * champ_iter_init(&iter, champ);
 * while(champ_iter_next(&iter, &key, &val)) {
 *     // do something with key and value
 * }
 * @endcode
 *
 * @param iter
 * @param champ
 */
void champ_iter_init(struct champ_iter *iter, const struct champ *champ);

/**
 * Advances iter and points key_receiver and value_receiver to the next pair.
 *
 * @param iter
 * @param key_receiver
 * @param value_receiver
 * @return 0 if the end of the champ has been reached
 */
int champ_iter_next(struct champ_iter *iter, CHAMP_KEY_T *key_receiver, CHAMP_VALUE_T *value_receiver);

#endif //CHAMP_CHAMP_H

champ.c

/*
 * MIT License
 *
 * Copyright (c) 2020 Samuel Vogelsanger <vogelsangersamuel@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/*
 * All the ref-counting specific code was marked with a "//reference counting" comment. If you need to modify this to
 * work with your own memory policy, it is recommended to start looking at those places to understand when and where
 * memory is allocated and freed.
 */

#include <malloc.h>
#include <stdint.h>
#include <stdio.h>
#include <stdatomic.h> // reference counting
#include <string.h>

#include "champ.h"

#define champ_node_debug_fmt "node{element_arity=%u, element_map=%08x, branch_arity=%u, branch_map=%08x, ref_count=%u}"
#define champ_node_debug_args(node) node->element_arity, node->element_map, node->branch_arity, node->branch_map, node->ref_count

#define HASH_PARTITION_WIDTH 5u
#define HASH_TOTAL_WIDTH (8 * sizeof(uint32_t))

/*
 * Helper functions
 */

static unsigned bitcount(uint32_t value)
{
    // taken from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    value = value - ((value >> 1u) & 0x55555555u);                    // reuse input as temporary
    value = (value & 0x33333333u) + ((value >> 2u) & 0x33333333u);     // temp
    return (((value + (value >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u;  // count
}

static uint32_t champ_mask(uint32_t hash, unsigned shift)
{
    return (hash >> shift) & ((1u << HASH_PARTITION_WIDTH) - 1);
}

static unsigned champ_index(uint32_t bitmap, uint32_t bitpos)
{
    return bitcount(bitmap & (bitpos - 1));
}

/*
 * Data structure definitions
 */

struct kv {
    CHAMP_KEY_T key;
    CHAMP_VALUE_T val;
};

#define CHAMP_NODE_ELEMENT_T struct kv
#define CHAMP_NODE_BRANCH_T struct node *

struct node {
    uint8_t element_arity;
    uint8_t branch_arity;
    volatile uint16_t ref_count; // reference counting
    uint32_t element_map;
    uint32_t branch_map;
    CHAMP_NODE_ELEMENT_T content[];
};

struct collision_node {
    uint8_t element_arity; // MUST SHARE LAYOUT WITH struct node
    uint8_t branch_arity; // MUST SHARE LAYOUT WITH struct node
    volatile uint16_t ref_count; // MUST SHARE LAYOUT WITH struct node // reference counting
    CHAMP_NODE_ELEMENT_T content[];
};

static const struct node empty_node = {
    .branch_arity = 0,
    .element_arity = 0,
    .ref_count = 1,
    .branch_map = 0,
    .element_map = 0,
};

#define CHAMP_NODE_ELEMENTS(node) (node)->content
#define CHAMP_NODE_BRANCHES(node) ((CHAMP_NODE_BRANCH_T const *)&(node)->content[(node)->element_arity])

#define CHAMP_NODE_ELEMENTS_SIZE(length) (sizeof(CHAMP_NODE_ELEMENT_T) * (length))
#define CHAMP_NODE_BRANCHES_SIZE(length) (sizeof(CHAMP_NODE_BRANCH_T) * (length))

#define CHAMP_NODE_ELEMENT_AT(node, bitpos) CHAMP_NODE_ELEMENTS(node)[champ_index(node->element_map, bitpos)]
#define CHAMP_NODE_BRANCH_AT(node, bitpos) CHAMP_NODE_BRANCHES(node)[champ_index(node->branch_map, bitpos)]

/*
 * static function declarations
 */

// node constructor
static struct node *node_new(uint32_t element_map, uint32_t branch_map, CHAMP_NODE_ELEMENT_T const *elements,
                 uint8_t element_arity, CHAMP_NODE_BRANCH_T const *branches, uint8_t branch_arity);

// collision node variant
static struct collision_node *collision_node_new(const CHAMP_NODE_ELEMENT_T *values, uint8_t element_arity);

// destructor
static void node_destroy(struct node *node);

// reference counting
static inline struct node *champ_node_acquire(const struct node *node);

// reference counting
static inline void champ_node_release(const struct node *node);


// top-level functions
static CHAMP_VALUE_T node_get(const struct node *node, CHAMP_EQUALSFN_T(equals), const CHAMP_KEY_T key, uint32_t hash,
                  unsigned shift, int *found);

static struct node *node_update(const struct node *node, CHAMP_HASHFN_T(hashfn), CHAMP_EQUALSFN_T(equals),
                const CHAMP_KEY_T key, const CHAMP_VALUE_T value, uint32_t hash, unsigned shift,
                int *found);

static struct node *node_assoc(const struct node *node, CHAMP_HASHFN_T(hashfn), CHAMP_EQUALSFN_T(equals),
                   const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn), const void *user_data, uint32_t hash,
                   unsigned shift, int *found);

static struct node *node_del(const struct node *node, CHAMP_EQUALSFN_T(equals), const CHAMP_KEY_T key, uint32_t hash,
                 unsigned shift, int *modified);

// collision node variants
static CHAMP_VALUE_T collision_node_get(const struct collision_node *node, CHAMP_EQUALSFN_T(equals),
                    const CHAMP_KEY_T key, int *found);

static struct collision_node *collision_node_update(const struct collision_node *node, CHAMP_EQUALSFN_T(equals),
                            const CHAMP_KEY_T key, const CHAMP_VALUE_T value, int *found);

static struct collision_node *collision_node_assoc(const struct collision_node *node, CHAMP_EQUALSFN_T(equals),
                           const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn), const void *user_data,
                           int *found);

static struct collision_node *collision_node_del(const struct collision_node *node, CHAMP_EQUALSFN_T(equals),
                         const CHAMP_KEY_T key, int *modified);


// helper functions for creation of modified nodes
static struct node *node_merge(uint32_t hash_l, const CHAMP_KEY_T key_l, const CHAMP_VALUE_T value_l, uint32_t hash_r,
                   const CHAMP_KEY_T key_r, const CHAMP_VALUE_T value_r, unsigned shift);

static struct node *node_clone_pullup(const struct node *node, uint32_t bitpos, const struct kv element);

static struct node *node_clone_update_branch(const struct node *node, uint32_t bitpos, struct node *branch);

static struct node *node_clone_pushdown(const struct node *node, uint32_t bitpos, struct node *branch);

static struct node *node_clone_insert_element(const struct node *node, uint32_t bitpos, const CHAMP_KEY_T key,
                          const CHAMP_VALUE_T value);

static struct node *node_clone_update_element(const struct node *node, uint32_t bitpos, const CHAMP_VALUE_T value);

static struct node *node_clone_remove_element(const struct node *node, uint32_t bitpos);

// collision node variants
static struct collision_node *collision_node_clone_insert_element(const struct collision_node *node,
                                  const CHAMP_KEY_T key, const CHAMP_VALUE_T value);

static struct collision_node *collision_node_clone_update_element(const struct collision_node *node, unsigned index,
                                  const CHAMP_VALUE_T value);

static struct collision_node *collision_node_clone_remove_element(const struct collision_node *node, unsigned index);


// equality
static int node_equals(const struct node *left, const struct node *right, CHAMP_EQUALSFN_T(key_equals),
               CHAMP_VALUE_EQUALSFN_T(value_equals), unsigned shift);

static int collision_node_equals(const struct collision_node *left, const struct collision_node *right,
                 CHAMP_EQUALSFN_T(key_equals), CHAMP_VALUE_EQUALSFN_T(value_equals));


// champ private constructor
static struct champ *champ_from(struct node *root, unsigned length, CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals));


// iterator helper functions
static void iter_push(struct champ_iter *iterator, const struct node *node);

static void iter_pop(struct champ_iter *iterator);


/*
 * definitions
 */

static void node_destroy(struct node *node)
{
    DEBUG_PRINT("    destroying " champ_node_debug_fmt "@%p\n", champ_node_debug_args(node), (void *)node);

    // reference counting
    CHAMP_NODE_BRANCH_T *branches = (CHAMP_NODE_BRANCH_T *)CHAMP_NODE_BRANCHES(node);
    for (int i = 0; i < node->branch_arity; ++i) {
        champ_node_release(branches[i]);
    }

    free(node);
}

// reference counting
static inline struct node *champ_node_acquire(const struct node *node)
{
    if (node == &empty_node)
        return (struct node *)node;
    atomic_fetch_add((uint16_t *)&node->ref_count, 1u);
    return (struct node *)node;
}

// reference counting
static inline void champ_node_release(const struct node *node)
{
    if (node == &empty_node)
        return;
    if (atomic_fetch_sub((uint16_t *)&node->ref_count, 1u) == 1)
        node_destroy((struct node *)node);
}

/**
 * WARNING: all branches in <code>branches</code> are "acquired", i.e. their reference count is incremented.
 * Do not pass an "almost correct" list of branches.
 */
static struct node *node_new(uint32_t element_map, uint32_t branch_map,
                 CHAMP_NODE_ELEMENT_T const *elements, uint8_t element_arity,
                 CHAMP_NODE_BRANCH_T const *branches, uint8_t branch_arity)
{
    const size_t content_size = CHAMP_NODE_ELEMENTS_SIZE(element_arity) + CHAMP_NODE_BRANCHES_SIZE(branch_arity);
    struct node *result = malloc(sizeof(*result) + content_size);

    result->element_arity = element_arity;
    result->branch_arity = branch_arity;
    result->ref_count = 0;
    result->element_map = element_map;
    result->branch_map = branch_map;

    memcpy(CHAMP_NODE_ELEMENTS(result), elements, CHAMP_NODE_ELEMENTS_SIZE(element_arity));

    CHAMP_NODE_BRANCH_T *branches_dest = (CHAMP_NODE_BRANCH_T *)CHAMP_NODE_BRANCHES(result);
    // reference counting
    for (int i = 0; i < branch_arity; ++i) {
        branches_dest[i] = champ_node_acquire(branches[i]);
    }

    return result;
}

static CHAMP_VALUE_T collision_node_get(const struct collision_node *node, CHAMP_EQUALSFN_T(equals),
                    const CHAMP_KEY_T key, int *found)
{
    for (unsigned i = 0; i < node->element_arity; ++i) {
        struct kv kv = node->content[i];
        if (equals(kv.key, key)) {
            *found = 1;
            return kv.val;
        }
    }

    *found = 0;
    return (CHAMP_VALUE_T)0;
}

static CHAMP_VALUE_T node_get(const struct node *node, CHAMP_EQUALSFN_T(equals),
                  const CHAMP_KEY_T key, uint32_t hash, unsigned shift, int *found)
{
    if (shift >= HASH_TOTAL_WIDTH)
        return collision_node_get((const struct collision_node *)node, equals, key, found);

    const uint32_t bitpos = 1u << champ_mask(hash, shift);

    if (node->branch_map & bitpos) {
        return node_get(CHAMP_NODE_BRANCH_AT(node, bitpos), equals, key, hash, shift + HASH_PARTITION_WIDTH, found);

    } else if (node->element_map & bitpos) {
        CHAMP_NODE_ELEMENT_T kv = CHAMP_NODE_ELEMENT_AT(node, bitpos);
        if (equals(kv.key, key)) {
            *found = 1;
            return kv.val;
        }
    }


    *found = 0;
    return (CHAMP_VALUE_T)0;
}

static struct node *node_clone_insert_element(const struct node *node, uint32_t bitpos,
                          const CHAMP_KEY_T key, const CHAMP_VALUE_T value)
{
    CHAMP_NODE_ELEMENT_T elements[1u << HASH_PARTITION_WIDTH];
    const unsigned index = champ_index(node->element_map, bitpos);

    // copy <branch_arity> chunks in total
    memcpy(elements, CHAMP_NODE_ELEMENTS(node), CHAMP_NODE_ELEMENTS_SIZE(index)); // copy first <index> chunks
    elements[index].key = (CHAMP_KEY_T)key;
    elements[index].val = (CHAMP_VALUE_T)value;
    memcpy(
        &elements[index + 1], // start copying into one-past-<index>
        &CHAMP_NODE_ELEMENTS(node)[index], // start copying from <index>
        CHAMP_NODE_ELEMENTS_SIZE(node->element_arity - index) // <index> chunks already copied, <branch_arity> - <index> remaining
    );

    return node_new(
        node->element_map | bitpos, node->branch_map, elements,
        node->element_arity + 1, CHAMP_NODE_BRANCHES(node), node->branch_arity);
}

static struct node *node_clone_update_element(const struct node *node,
                          uint32_t bitpos, const CHAMP_VALUE_T value)
{
    CHAMP_NODE_ELEMENT_T elements[1u << HASH_PARTITION_WIDTH];
    const unsigned index = champ_index(node->element_map, bitpos);

    memcpy(elements, CHAMP_NODE_ELEMENTS(node), CHAMP_NODE_ELEMENTS_SIZE(node->element_arity));
    elements[index].val = (CHAMP_VALUE_T)value;
    return node_new(node->element_map, node->branch_map, elements, node->element_arity, CHAMP_NODE_BRANCHES(node), node->branch_arity);
}

static struct node *node_clone_update_branch(const struct node *node,
                         uint32_t bitpos, struct node *branch)
{
    CHAMP_NODE_BRANCH_T branches[1u << HASH_PARTITION_WIDTH];
    const unsigned index = champ_index(node->branch_map, bitpos);

    memcpy(branches, CHAMP_NODE_BRANCHES(node), CHAMP_NODE_BRANCHES_SIZE(node->branch_arity));
    branches[index] = branch;
    return node_new(node->element_map, node->branch_map, CHAMP_NODE_ELEMENTS(node), node->element_arity, branches, node->branch_arity);
}

static struct node *node_clone_pushdown(const struct node *node,
                    uint32_t bitpos, struct node *branch)
{
    CHAMP_NODE_ELEMENT_T elements[1u << HASH_PARTITION_WIDTH];
    CHAMP_NODE_BRANCH_T branches[1u << HASH_PARTITION_WIDTH];
    const unsigned element_index = champ_index(node->element_map, bitpos);
    const unsigned branch_index = champ_index(node->branch_map, bitpos);

    memcpy(elements, CHAMP_NODE_ELEMENTS(node), CHAMP_NODE_ELEMENTS_SIZE(element_index));
    memcpy(
        &elements[element_index],
        &CHAMP_NODE_ELEMENTS(node)[element_index + 1],
        CHAMP_NODE_ELEMENTS_SIZE(node->element_arity - (element_index + 1))
    );

    memcpy(branches, CHAMP_NODE_BRANCHES(node), CHAMP_NODE_BRANCHES_SIZE(branch_index));
    memcpy(
        &branches[branch_index + 1],
        &CHAMP_NODE_BRANCHES(node)[branch_index],
        CHAMP_NODE_BRANCHES_SIZE(node->branch_arity - branch_index)
    );
    branches[branch_index] = branch;

    return node_new(
        node->element_map & ~bitpos,
        node->branch_map | bitpos, elements, node->element_arity - 1, branches, node->branch_arity + 1);
}

static struct collision_node *collision_node_new(const CHAMP_NODE_ELEMENT_T *values, uint8_t element_arity)
{
    size_t content_size = sizeof(CHAMP_NODE_ELEMENT_T) * element_arity;
    struct collision_node *result = malloc(sizeof(*result) + content_size);

    result->element_arity = element_arity;
    result->branch_arity = 0;
    result->ref_count = 0;

    memcpy(result->content, values, CHAMP_NODE_ELEMENTS_SIZE(element_arity));

    return result;
}

static struct node *node_merge(uint32_t hash_l, const CHAMP_KEY_T key_l, const CHAMP_VALUE_T value_l,
                   uint32_t hash_r, const CHAMP_KEY_T key_r, const CHAMP_VALUE_T value_r,
                   unsigned shift)
{
    uint32_t bitpos_l = 1u << champ_mask(hash_l, shift);
    uint32_t bitpos_r = 1u << champ_mask(hash_r, shift);

    if (shift >= HASH_TOTAL_WIDTH) {
        CHAMP_NODE_ELEMENT_T elements[2];
        elements[0].key = (CHAMP_KEY_T)key_l;
        elements[0].val = (CHAMP_VALUE_T)value_l;
        elements[1].key = (CHAMP_KEY_T)key_r;
        elements[1].val = (CHAMP_VALUE_T)value_r;

        return (struct node *)collision_node_new(elements, 2);

    } else if (bitpos_l != bitpos_r) {
        CHAMP_NODE_ELEMENT_T elements[2];

        if (bitpos_l <= bitpos_r) {
            elements[0].key = (CHAMP_KEY_T)key_l;
            elements[0].val = (CHAMP_VALUE_T)value_l;
            elements[1].key = (CHAMP_KEY_T)key_r;
            elements[1].val = (CHAMP_VALUE_T)value_r;
        } else {
            elements[0].key = (CHAMP_KEY_T)key_r;
            elements[0].val = (CHAMP_VALUE_T)value_r;
            elements[1].key = (CHAMP_KEY_T)key_l;
            elements[1].val = (CHAMP_VALUE_T)value_l;
        }

        return node_new(bitpos_l | bitpos_r, 0u, elements, 2, NULL, 0);

    } else {
        struct node *sub_node = node_merge(
            hash_l,
            key_l,
            value_l,
            hash_r,
            key_r,
            value_r,
            shift + HASH_PARTITION_WIDTH
        );

        return node_new(0, bitpos_l, NULL, 0, &sub_node, 1);
    }
}

static struct collision_node *collision_node_clone_update_element(const struct collision_node *node,
                                  unsigned index, const CHAMP_VALUE_T value)
{
    CHAMP_NODE_ELEMENT_T elements[node->element_arity];

    memcpy(elements, node->content, CHAMP_NODE_ELEMENTS_SIZE(node->element_arity));
    elements[index].val = (CHAMP_VALUE_T)value;

    return collision_node_new(elements, node->element_arity);
}

static struct collision_node *collision_node_clone_insert_element(const struct collision_node *node,
                                  const CHAMP_KEY_T key,
                                  const CHAMP_VALUE_T value)
{
    CHAMP_NODE_ELEMENT_T elements[node->element_arity + 1];

    memcpy(elements, node->content, CHAMP_NODE_ELEMENTS_SIZE(node->element_arity));
    elements[node->element_arity].key = (CHAMP_KEY_T)key;
    elements[node->element_arity].val = (CHAMP_VALUE_T)value;

    return collision_node_new(elements, node->element_arity + 1);
}

static struct collision_node *collision_node_update(const struct collision_node *node,
                            CHAMP_EQUALSFN_T(equals),
                            const CHAMP_KEY_T key, const CHAMP_VALUE_T value,
                            int *found)
{
    for (unsigned i = 0; i < node->element_arity; ++i) {
        struct kv kv = node->content[i];
        if (equals(kv.key, key)) {
            *found = 1;

            return collision_node_clone_update_element(node, i, value);
        }
    }

    return collision_node_clone_insert_element(node, key, value);
}

static struct node *node_update(const struct node *node, CHAMP_HASHFN_T(hashfn), CHAMP_EQUALSFN_T(equals),
                const CHAMP_KEY_T key, const CHAMP_VALUE_T value, uint32_t hash, unsigned shift,
                int *found)
{
    if (shift >= HASH_TOTAL_WIDTH)
        return (struct node *)collision_node_update((const struct collision_node *)node, equals, key, value, found);

    const uint32_t bitpos = 1u << champ_mask(hash, shift);

    if (node->branch_map & bitpos) {
        const struct node *sub_node = CHAMP_NODE_BRANCH_AT(node, bitpos);
        struct node *new_sub_node = node_update(sub_node, hashfn, equals, key, value, hash,
            shift + HASH_PARTITION_WIDTH, found);
        return node_clone_update_branch(node, bitpos, new_sub_node);

    } else if (node->element_map & bitpos) {
        const CHAMP_KEY_T current_key = CHAMP_NODE_ELEMENT_AT(node, bitpos).key;

        if (equals(current_key, key)) {
            *found = 1;
            return node_clone_update_element(node, bitpos, value);

        } else {
            const CHAMP_VALUE_T current_value = CHAMP_NODE_ELEMENT_AT(node, bitpos).val;
            struct node *sub_node = node_merge(
                hashfn(current_key),
                current_key,
                current_value,
                hashfn(key),
                key,
                value,
                shift + HASH_PARTITION_WIDTH
            );
            return node_clone_pushdown(node, bitpos, sub_node);
        }

    } else {
        return node_clone_insert_element(node, bitpos, key, value);
    }
}

static struct node *node_clone_remove_element(const struct node *node, uint32_t bitpos)
{
    DEBUG_PRINT("removing element with bit position 0x%x\n", bitpos);

    CHAMP_NODE_ELEMENT_T elements[1u << HASH_PARTITION_WIDTH];
    const unsigned index = champ_index(node->element_map, bitpos);

    memcpy(elements, CHAMP_NODE_ELEMENTS(node), CHAMP_NODE_ELEMENTS_SIZE(index));
    memcpy(
        &elements[index],
        &CHAMP_NODE_ELEMENTS(node)[index + 1],
        CHAMP_NODE_ELEMENTS_SIZE(node->element_arity - (index + 1))
    );

    return node_new(
        node->element_map & ~bitpos, node->branch_map, elements,
        node->element_arity - 1, CHAMP_NODE_BRANCHES(node), node->branch_arity);
}

/*
 * 'Pullup' is the inverse of pushdown.
 * It's the process of 'pulling an entry up' from a branch, inlining it as an element instead.
 */
static struct node *node_clone_pullup(const struct node *node, uint32_t bitpos,
                      const struct kv element)
{
    CHAMP_NODE_BRANCH_T branches[1u << HASH_PARTITION_WIDTH];
    CHAMP_NODE_ELEMENT_T elements[1u << HASH_PARTITION_WIDTH];
    const unsigned branch_index = champ_index(node->branch_map, bitpos);
    const unsigned element_index = champ_index(node->element_map, bitpos);

    memcpy(branches, CHAMP_NODE_BRANCHES(node), CHAMP_NODE_BRANCHES_SIZE(branch_index));
    memcpy(
        &branches[branch_index],
        &CHAMP_NODE_BRANCHES(node)[branch_index + 1],
        CHAMP_NODE_BRANCHES_SIZE(node->branch_arity - (branch_index + 1))
    );

    memcpy(elements, CHAMP_NODE_ELEMENTS(node), CHAMP_NODE_ELEMENTS_SIZE(element_index));
    elements[element_index] = element;
    memcpy(
        &elements[element_index + 1],
        &CHAMP_NODE_ELEMENTS(node)[element_index],
        CHAMP_NODE_ELEMENTS_SIZE(node->element_arity - element_index)
    );

    return node_new(
        node->element_map | bitpos,
        node->branch_map & ~bitpos, elements, node->element_arity + 1, branches, node->branch_arity - 1);
}

static struct collision_node *collision_node_clone_remove_element(const struct collision_node *node,
                                  unsigned index)
{
    CHAMP_NODE_ELEMENT_T elements[node->element_arity - 1];

    memcpy(elements, node->content, CHAMP_NODE_ELEMENTS_SIZE(index));
    memcpy(elements, &node->content[index + 1], CHAMP_NODE_ELEMENTS_SIZE(node->element_arity - (index + 1)));

    return collision_node_new(elements, node->element_arity - 1);
}

/**
 * If only one element remains, the returned node will be passed up the tree - to where knowledge of hash collision
 * nodes is inappropriate. In that case, this will return a normal <code>struct node *</code> instead.
 *
 * Consider the only(!) place where this is called: at the start of node_del, if the hash is exhausted. The returned
 * value is then immediately returned to the previous call of node_del, where it is evaluated as new_sub_node of
 * type struct node, and its members branch_arity and element_arity are evaluated. this requires us to have those
 * members be at the exact same place in both struct node and struct collision_node.
 *
 * @return
 */
static struct collision_node *collision_node_del(const struct collision_node *node,
                         CHAMP_EQUALSFN_T(equals), const CHAMP_KEY_T key,
                         int *modified)
{
    for (unsigned i = 0; i < node->element_arity; ++i) {
        struct kv kv = node->content[i];
        if (equals(kv.key, key)) {
            *modified = 1;
            if (node->element_arity == 2) {
                CHAMP_NODE_ELEMENT_T elements[1] = {node->content[i ? 0 : 1]};
                return (struct collision_node *)node_new(0, 0, elements, 1, NULL, 0);

            } else {
                return collision_node_clone_remove_element(node, i);
            }
        }
    }

    return NULL;
}

static struct node *node_del(const struct node *node, CHAMP_EQUALSFN_T(equals),
                 const CHAMP_KEY_T key, uint32_t hash, unsigned shift, int *modified)
{
    if (shift >= HASH_TOTAL_WIDTH)
        return (struct node *)collision_node_del((const struct collision_node *)node, equals, key, modified);

    const uint32_t bitpos = 1u << champ_mask(hash, shift);

    if (node->element_map & bitpos) {
        if (equals(CHAMP_NODE_ELEMENT_AT(node, bitpos).key, key)) {
            *modified = 1;
            if (node->element_arity + node->branch_arity == 1) // only possible for the root node
                return (struct node *)&empty_node;
            else
                return node_clone_remove_element(node, bitpos);
        } else {
            return NULL; // returning from node_del with *modified == 0 means abort immediately
        }

    } else if (node->branch_map & bitpos) {
        struct node *sub_node = CHAMP_NODE_BRANCH_AT(node, bitpos);
        struct node *new_sub_node = node_del(sub_node, equals, key, hash,
            shift + HASH_PARTITION_WIDTH, modified);

        if (!*modified)
            return NULL; // returning from node_del with *modified == 0 means abort immediately

        if (node->branch_arity + node->element_arity == 1) { // node is a 'passthrough'
            if (new_sub_node->branch_arity * 2 + new_sub_node->element_arity == 1) { // new_sub_node is non-canonical, propagate for inlining
                new_sub_node->element_map = bitpos;
                return new_sub_node;
            } else { // canonical, bubble modified trie to the top
                return node_clone_update_branch(node, bitpos, new_sub_node);
            }

        } else if (new_sub_node->branch_arity * 2 + new_sub_node->element_arity == 1) { // new_sub_node is non-canonical
            const struct kv remaining_element = CHAMP_NODE_ELEMENTS(new_sub_node)[0];
            node_destroy(new_sub_node);
            return node_clone_pullup(node, bitpos, remaining_element);

        } else { // both node and new_sub_node are canonical
            return node_clone_update_branch(node, bitpos, new_sub_node);
        }

    } else {
        return NULL;
    }
}

static struct collision_node *collision_node_assoc(const struct collision_node *node,
                           CHAMP_EQUALSFN_T(equals),
                           const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn),
                           const void *user_data,
                           int *found)
{
    CHAMP_VALUE_T new_value;
    for (unsigned i = 0; i < node->element_arity; ++i) {
        struct kv kv = node->content[i];
        if (equals(kv.key, key)) {
            *found = 1;
            CHAMP_VALUE_T old_value = kv.val;
            new_value = fn(key, old_value, (void *)user_data);
            return collision_node_clone_update_element(node, i, new_value);
        }
    }

    new_value = fn((CHAMP_KEY_T)0, (CHAMP_VALUE_T)0, (void *)user_data);
    return collision_node_clone_insert_element(node, key, new_value);
}

static struct node *node_assoc(const struct node *node, CHAMP_HASHFN_T(hashfn), CHAMP_EQUALSFN_T(equals),
                   const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn), const void *user_data, uint32_t hash,
                   unsigned shift, int *found)
{
    if (shift >= HASH_TOTAL_WIDTH)
        return (struct node *)collision_node_assoc((const struct collision_node *)node, equals, key, fn, user_data, found);

    const uint32_t bitpos = 1u << champ_mask(hash, shift);

    if (node->branch_map & bitpos) {
        const struct node *sub_node = CHAMP_NODE_BRANCH_AT(node, bitpos);
        struct node *new_sub_node = node_assoc(sub_node, hashfn, equals, key, fn, user_data, hash,
            shift + HASH_PARTITION_WIDTH, found);
        return node_clone_update_branch(node, bitpos, new_sub_node);

    } else if (node->element_map & bitpos) {
        const CHAMP_KEY_T current_key = CHAMP_NODE_ELEMENT_AT(node, bitpos).key;

        if (equals(current_key, key)) {
            *found = 1;
            const CHAMP_VALUE_T old_value = CHAMP_NODE_ELEMENT_AT(node, bitpos).val;
            CHAMP_VALUE_T new_value = fn(key, old_value, (void *)user_data);
            return node_clone_update_element(node, bitpos, new_value);

        } else {
            const CHAMP_VALUE_T current_value = CHAMP_NODE_ELEMENT_AT(node, bitpos).val;
            const CHAMP_VALUE_T new_value = fn((CHAMP_KEY_T)0, (CHAMP_VALUE_T)0, (void *)user_data);
            struct node *sub_node = node_merge(
                hashfn(current_key),
                current_key,
                current_value,
                hash,
                key,
                new_value,
                shift + HASH_PARTITION_WIDTH
            );
            return node_clone_pushdown(node, bitpos, sub_node);
        }

    } else {
        const CHAMP_VALUE_T value = fn((CHAMP_KEY_T)0, (CHAMP_VALUE_T)0, (void *)user_data);
        return node_clone_insert_element(node, bitpos, key, value);
    }
}

static int collision_node_equals(const struct collision_node *left, const struct collision_node *right,
                 CHAMP_EQUALSFN_T(key_equals), CHAMP_VALUE_EQUALSFN_T(value_equals))
{
    if (left == right)
        return 1;
    if (left->element_arity != right->element_arity)
        return 0;


    for (unsigned left_i = 0; left_i < left->element_arity; ++left_i) {
        struct kv left_element = CHAMP_NODE_ELEMENTS(left)[left_i];

        for (unsigned right_i = 0; right_i < right->element_arity; ++right_i) {
            struct kv right_element = CHAMP_NODE_ELEMENTS(right)[right_i];

            if (key_equals(left_element.key, right_element.key) && value_equals(left_element.val, right_element.val))
                goto found_matching_element;
        }
        return 0; // compared left_element to all elements in right node, no match.

        found_matching_element:
        continue;
    }
    return 1; // compared all elements in left node, never had an element without match.
}

static int node_equals(const struct node *left, const struct node *right, CHAMP_EQUALSFN_T(key_equals),
               CHAMP_VALUE_EQUALSFN_T(value_equals), unsigned shift)
{
    if (shift >= HASH_TOTAL_WIDTH)
        return collision_node_equals((struct collision_node *)left, (struct collision_node *)right, key_equals, value_equals);
    if (left == right)
        return 1;
    if (left->element_map != right->element_map)
        return 0;
    if (left->branch_map != right->branch_map)
        return 0;
    for (unsigned i = 0; i < left->element_arity; ++i) {
        struct kv left_element = CHAMP_NODE_ELEMENTS(left)[i];
        struct kv right_element = CHAMP_NODE_ELEMENTS(right)[i];
        if (!key_equals(left_element.key, right_element.key) || !value_equals(left_element.val, right_element.val))
            return 0;
    }
    for (unsigned i = 0; i < left->branch_arity; ++i) {
        struct node *left_branch = CHAMP_NODE_BRANCHES(left)[i];
        struct node *right_branch = CHAMP_NODE_BRANCHES(right)[i];
        if (!node_equals(left_branch, right_branch, key_equals, value_equals, shift + HASH_PARTITION_WIDTH))
            return 0;
    }
    return 1;
}


static struct champ *champ_from(struct node *root, unsigned length,
                CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals))
{
    struct champ *result = malloc(sizeof(*result));
    result->ref_count = 0;
    result->root = root;
    result->length = length;
    result->hash = hash;
    result->equals = equals;
    return result;
}

void champ_destroy(struct champ **champ)
{
    DEBUG_PRINT("destroying champ@%p\n", (void *)*champ);
    champ_node_release((*champ)->root);
    free(*champ);
    *champ = NULL;
}

struct champ *champ_new(CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals))
{
    return champ_from((struct node *)&empty_node, 0, hash, equals);
}

struct champ *champ_acquire(const struct champ *champ)
{
    atomic_fetch_add((uint32_t *)&champ->ref_count, 1u);
    return (struct champ *)champ;
}

void champ_release(struct champ **champ)
{
    if (atomic_fetch_sub((uint32_t *)&((*champ)->ref_count), 1u) == 1u)
        champ_destroy((struct champ **)champ);
    *champ = NULL;
}

struct champ *champ_of(CHAMP_HASHFN_T(hash), CHAMP_EQUALSFN_T(equals),
               CHAMP_KEY_T*keys, CHAMP_VALUE_T*values, size_t length)
{
    struct champ *result = champ_new(hash, equals);
    while (length--) {
        struct champ *tmp = champ_set(result, keys[length], values[length], NULL);
        champ_destroy(&result);
        result = tmp;
    }
    return result;
}

unsigned champ_length(const struct champ *champ)
{
    return champ->length;
}

struct champ *champ_set(const struct champ *champ,
            const CHAMP_KEY_T key, const CHAMP_VALUE_T value, int *replaced)
{
    const uint32_t hash = champ->hash(key);
    int found = 0;
    int *found_p = replaced ? replaced : &found;
    *found_p = 0;
    struct node *new_root = champ_node_acquire(node_update(champ->root, champ->hash, champ->equals, key, value, hash, 0, found_p));
    return champ_from(new_root, champ->length + (*found_p ? 0 : 1), champ->hash, champ->equals);
}

CHAMP_VALUE_T champ_get(const struct champ *champ, const CHAMP_KEY_T key, int *found)
{
    uint32_t hash = champ->hash(key);
    int tmp = 0;
    return node_get(champ->root, champ->equals, key, hash, 0, found ? found : &tmp);
}

struct champ *champ_del(const struct champ *champ, const CHAMP_KEY_T key, int *modified)
{
    const uint32_t hash = champ->hash(key);
    int found = 0;
    int *found_p = modified ? modified : &found;
    *found_p = 0;
    struct node *new_root = node_del(champ->root, champ->equals, key, hash, 0, found_p);
    if (!*found_p)
        return (struct champ *)champ;
    return champ_from(champ_node_acquire(new_root), champ->length - 1, champ->hash, champ->equals);
}

struct champ *champ_assoc(const struct champ *champ, const CHAMP_KEY_T key, CHAMP_ASSOCFN_T(fn), const void *user_data)
{
    const uint32_t hash = champ->hash(key);
    int found = 0;
    struct node *new_root = champ_node_acquire(node_assoc(champ->root, champ->hash, champ->equals, key, fn, user_data, hash, 0, &found));
    return champ_from(new_root, champ->length + (found ? 0 : 1), champ->hash, champ->equals);
}

int champ_equals(const struct champ *left, const struct champ *right, CHAMP_VALUE_EQUALSFN_T(value_equals))
{
    if (left == right)
        return 1;
    else if (champ_length(left) != champ_length(right))
        return 0;
    else
        return node_equals(left->root, right->root, left->equals, value_equals, 0);
}

static const char *indent(unsigned level)
{
    const char *spaces = "                                                                                ";
    return spaces + 4 * (20 - level);
}

#define iprintf(level, fmt, ...) printf("%s" fmt, indent(level), ##__VA_ARGS__)

static char *format_binary(uint32_t value, char *buffer)
{
    for (char *pos = buffer + 31; pos >= buffer; --pos) {
        if (value & 1u) *pos = '1';
        else *pos = '0';
        value = value >> 1u;
    }
    return buffer;
}

static void champ_node_repr(const struct node *node, const char *kp, const char *vp, unsigned shift, unsigned i_level)
{
    if (shift >= HASH_TOTAL_WIDTH) {
        iprintf(i_level, "\"collision node (omitted)\"");
        return;
    }
    char map_buf[33];
    printf("{\n");
    iprintf(i_level, "\"element_map\": 0b%.32s,\n", format_binary(node->element_map, map_buf));
    iprintf(i_level, "\"element_arity\": %u,\n", node->element_arity);
    iprintf(i_level, "\"branch_map\": 0b%.32s,\n", format_binary(node->branch_map, map_buf));
    iprintf(i_level, "\"branch_arity\": %u,\n", node->branch_arity);
    iprintf(i_level, "\"elements\": {\n");
    for (unsigned i = 0; i < node->element_arity; ++i) {
        CHAMP_NODE_ELEMENT_T el = CHAMP_NODE_ELEMENTS(node)[i];
        iprintf(i_level + 1, "\"");
        printf(kp, el.key);
        printf("\": ");
        printf(vp, el.val);
        printf(",\n");
    }
    iprintf(i_level, "},\n");
    iprintf(i_level, "\"nodes\": [\n");
    for (unsigned i = 0; i < node->branch_arity; ++i) {
        CHAMP_NODE_BRANCH_T n = CHAMP_NODE_BRANCHES(node)[i];
        iprintf(i_level + 1, "");
        champ_node_repr(n, kp, vp, shift + HASH_PARTITION_WIDTH, i_level + 2);
        printf(",\n");
    }
    iprintf(i_level, "],\n");
    iprintf(i_level - 1, "}");
}

void champ_repr(const struct champ *champ, const char *key_prefix, const char *value_prefix)
{
    printf("{\n");
    iprintf(1, "\"length\": %d,\n", champ->length);
    iprintf(1, "\"root\": ");
    champ_node_repr(champ->root, key_prefix, value_prefix, 0, 2);
    printf("\n}\n");
}

void champ_iter_init(struct champ_iter *iterator, const struct champ *champ)
{
    iterator->stack_level = 0;
    iterator->element_cursor = 0;
    iterator->element_arity = champ->root->element_arity;
    iterator->branch_cursor_stack[0] = 0;
    iterator->branch_arity_stack[0] = champ->root->branch_arity;
    iterator->node_stack[0] = champ->root;
}

static void iter_push(struct champ_iter *iterator, const struct node *node)
{
    iterator->stack_level += 1;
    iterator->element_cursor = 0;
    iterator->element_arity = node->element_arity;
    iterator->branch_cursor_stack[iterator->stack_level] = 0;
    iterator->branch_arity_stack[iterator->stack_level] = node->branch_arity;
    iterator->node_stack[iterator->stack_level] = node;
}

static void iter_pop(struct champ_iter *iterator)
{
    iterator->stack_level -= 1;
}

int champ_iter_next(struct champ_iter *iterator, CHAMP_KEY_T *key, CHAMP_VALUE_T *value)
{
    if (iterator->stack_level == -1)
        return 0;

    const struct node *current_node = iterator->node_stack[iterator->stack_level];
    unsigned *branch_cursor = iterator->branch_cursor_stack + iterator->stack_level;
    if (*branch_cursor == 0 && iterator->element_cursor < current_node->element_arity) { // todo: write test for this
        *key = CHAMP_NODE_ELEMENTS(current_node)[iterator->element_cursor].key;
        *value = CHAMP_NODE_ELEMENTS(current_node)[iterator->element_cursor].val;
        ++iterator->element_cursor;
        return 1;

    } else {
        if (*branch_cursor < iterator->branch_arity_stack[iterator->stack_level]) {
            iter_push(iterator, CHAMP_NODE_BRANCHES(current_node)[*branch_cursor]);
            ++*branch_cursor;
            return champ_iter_next(iterator, key, value);

        } else {
            iter_pop(iterator);
            return champ_iter_next(iterator, key, value);
        }
    }
}

Using it as a "champ<string,int>"

This is an example of how to use this map with a scalar value type.

Compile with gcc -DDEBUG -O3 -o main main.c str_int_map.c -std=c11

champ_str_int.h

#define CHAMP_KEY_T char*
#define CHAMP_VALUE_T int
#include "champ.h"

champ_str_int.c

#include "str_int_map.h"
#include "champ.c"

main.c

#include <stdio.h>
#include <string.h>
#include "str_int_map.h"
#include "champ_fns.h"

int equals_str(const char *l, const char *r) {
    return !strcmp(l, r);
}

uint32_t hash_str(const char *str) {
    uint32_t hash = 0;
    for (unsigned i = 0; i < strlen(str); i++) {
        hash = 31 * hash + (uint32_t)str[i];
    }
    return hash;
}

int main()
{
    struct champ *map = champ_acquire(champ_new(hash_str, equals_str));
    // note: key is char* and value is int instead of void*, no cast required
    map = champ_set(map, "answer", 42, NULL);
    printf("answer == %d\n", champ_get(map, "answer", NULL));
}
\$\endgroup\$
2
\$\begingroup\$

Without digging into it too deeply, this seems well put-together and it's clear that you know what you're doing. The only minor thing I picked up on first read is that this:

int *found

should be using <stdbool.h> instead of an int; mostly to help your users understand what's happening. The same goes for the return value of equals_str.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! I was trying pretty hard. And yeah, I was under the impression that int is the de-facto bool in C and nobody really uses <stdbool>, but my teachers just might have been a bit quirky. \$\endgroup\$
    – ammut
    Apr 27 '20 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.