/**
 * @file
 * Hash table library for standard C99.
 */
#ifndef INCLUDED_HT_HT_H
#define INCLUDED_HT_HT_H

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

#ifdef __cplusplus
extern "C" {
#endif

/**
 * Structure holding memory allocation functions as well as extra data to pass
 * to the functions when allocating.
 */
typedef struct HTAllocator {
    /**
     * Analogous to the standard library function of the same name. The
     * user_data field of the allocator is passed as the second argument. This
     * should return NULL or exit the program if allocation fails. If it
     * attempts to longjmp, it might cause memory leaks (unless allocated memory
     * is tracked separately).
     */
    void *(*malloc)(size_t size, void *user_data);
    /**
     * Analogous to the standard library function of the same name. The
     * user_data field of the allocator is passed as the second argument. This
     * should be able to accept a ptr of NULL.
     */
    void (*free)(void *ptr, void *user_data);
    /**
     * Extra data to pass to the allocation functions.
     */
    void *user_data;
} HTAllocator;

/**
 * Values used to determine when to grow and shrink the hash table.
 */
typedef struct HTThreshold {
    /**
     * Initial size of the table. Cannot be 0.
     */
    size_t initial_size;
    /**
     * How much to grow the table by. A value of 2, for example, means to double
     * the table size every time it is expanded.
     */
    float growth_factor;
    /**
     * Once at least this percentage of the table is filled, the table will be
     * grown. Should be a value in the range (0, 1].
     */
    float growth_threshold;
    /**
     * Once less than this percentage of the table is filled, the table will be
     * shrunk. Should be a value in the range (0, 1].
     */
    float shrink_threshold;
} HTThreshold;

typedef struct HTTable HTTable;

/**
 * Stuff an integer into a pointer. This just casts n to a uintptr_t and then to
 * a void *.
 */
#define HT_STUFF(n) ((void *) (uintptr_t) (n))
/**
 * Undo HT_STUFF and retrieve the value as an intptr_t.
 */
#define HT_UNSTUFF(n) ((intptr_t) (void *) (n))
/**
 * Undo HT_STUFF and retrieve the value as a uintptr_t.
 */
#define HT_UUNSTUFF(n) ((uintptr_t) (void *) (n))

/**
 * Hash function for the hash table.
 */
typedef uint64_t (*ht_hash_callback_t)(const void *key, void *user_data);
/**
 * Equality function for the hash table. If key1\ ==\ key2, then
 * hash(key1)\ ==\ hash(key2). However, the reverse is not true. That is, things
 * that are equal have the same hash, but things with the same hash are not
 * necessarily equal.
 */
typedef bool (*ht_equal_callback_t)(const void *key1, const void *key2,
                                    void *user_data);
/**
 * Function to free a hash table key or value.
 */
typedef void (*ht_destroy_callback_t)(void *ptr, void *user_data);
/**
 * The set of functions used by a hash table. Each function will have the
 * user_data member passed as its last argument.
 */
typedef struct HTTableFunctions {
    /**
     * Hash function.
     */
    ht_hash_callback_t hash;
    /**
     * Equality predicate function.
     */
    ht_equal_callback_t equal;
    /**
     * Function to call to cleanup keys when they are removed from the
     * table. This can be NULL. In that case, no cleanup is performed.
     */
    ht_destroy_callback_t destroy_key;
    /**
     * Function to call to cleanup values when they are removed from the
     * table. This can be NULL. In that case, no cleanup is performed.
     */
    ht_destroy_callback_t destroy_value;

    /**
     * This will be passed as a final argument to each other function.
     */
    void *user_data;
} HTTableFunctions;

/**
 * Call back used to copy values.
 * @see ht_copy
 */
typedef void *(*ht_copy_callback_t)(const void *original, void *user_data);
/**
 * Callback used for looping functions. The meaning of the return value depends
 * on the function used.
 * @see ht_foreach
 * @see ht_foreach_remove
 * @see ht_foreach_steal
 */
typedef bool (*ht_foreach_callback_t)(void *key, void *value, void *user_data);

HTTable *ht_new(const HTTableFunctions *fns, const HTAllocator *alloc,
                const HTThreshold *thresh);

HTTable *ht_copy(const HTTable *ht, ht_copy_callback_t copy_key_callback,
                 ht_copy_callback_t copy_value_callback, void *user_data);

void ht_free(HTTable *ht);

size_t ht_count(const HTTable *ht);

bool ht_equal(const HTTable *ht1, const HTTable *ht2);

bool ht_insert(HTTable *ht, void *key, void *value);

bool ht_clear(HTTable *ht);

bool ht_remove(HTTable *ht, const void *key);

bool ht_steal(HTTable *ht, const void *key, void **stolen_key,
              void **stolen_value);

bool ht_steal_all(HTTable *ht, void ***keys, void ***values);

void *ht_get_extended(const HTTable *ht, const void *key, void **found_key);

/**
 * Lookup a value in a hash table from its key.
 * @param ht The hash table
 * @param key The key
 * @return The value associated with the key, or NULL if the key is absent
 */
static inline void *ht_get(const HTTable *ht, const void *key) {
    return ht_get_extended(ht, key, NULL);
}

bool ht_has_extended(const HTTable *ht, const void *key, void **found_key);

/**
 * Test for the presence of a key in a hash table.
 * @param ht The hash table
 * @param key The key
 * @return Whether the table contained a mapping for the key
 */
static inline bool ht_has(const HTTable *ht, const void *key) {
    return ht_has_extended(ht, key, NULL);
}

void ht_foreach(const HTTable *ht, ht_foreach_callback_t callback,
                void *user_data);

bool ht_foreach_remove(HTTable *ht, ht_foreach_callback_t callback,
                       void *user_data);

bool ht_foreach_steal(HTTable *ht, ht_foreach_callback_t callback,
                      void *user_data);

bool ht_find(HTTable *ht, ht_foreach_callback_t callback, void *user_data,
             void **key, void **value);

bool ht_steal_from(HTTable *ht, HTTable *src);

bool ht_get_keys_and_values(const HTTable *ht, void ***keys, void ***values);

void **ht_get_keys(const HTTable *ht);

void **ht_get_values(const HTTable *ht);

uint64_t ht_string_hash_callback(const void *str, void *user_data);
bool ht_string_equal_callback(const void *str1, const void *str2,
                              void *user_data);

uint64_t ht_intptr_hash_callback(const void *num, void *user_data);
bool ht_intptr_equal_callback(const void *n1, const void *n2, void *user_data);

#ifdef __cplusplus
}
#endif

#endif