vl_hashtable.h

Go to the documentation of this file.

 
#ifndef VL_HASHTABLE_H
#define VL_HASHTABLE_H
 
#include "vl_arena.h"
#include "vl_hash.h"
 
#define VL_HASHTABLE_ITER_INVALID 0
 
#ifndef VL_HASHTABLE_RESIZE_FACTOR
#define VL_HASHTABLE_RESIZE_FACTOR 0.8
#endif
 
#ifndef VL_HASHTABLE_DEFAULT_SIZE
#define VL_HASHTABLE_DEFAULT_SIZE 128
#endif
 
#define VL_HASHTABLE_FOREACH(table, trackVar)                                                                          \
    for (vl_hash_iter trackVar = vlHashTableFront(table); trackVar != VL_HASHTABLE_ITER_INVALID;                       \
         trackVar = vlHashTableNext(table, trackVar))
 
typedef vl_arena_ptr vl_hash_iter;
 
typedef struct
{
    vl_memory* table; // holds mapping from hash values to collision list heads
                      // in the arena
    vl_arena data; // holds the node key/value data
    vl_hash_function hashFunc; // hash function; hashes keys
 
    vl_dsidx_t totalElements; // total number of mapped elements
} vl_hashtable;
 
typedef struct
{
    vl_uint16_t keySize;
    vl_uint16_t valSize;
    vl_hash keyHash;
    vl_arena_ptr next;
} vl_hashtable_header;
 
VL_API void vlHashTableInit(vl_hashtable* table, vl_hash_function hashFunc);
 
VL_API void vlHashTableFree(vl_hashtable* table);
 
VL_API vl_hashtable* vlHashTableNew(vl_hash_function func);
 
VL_API void vlHashTableDelete(vl_hashtable* table);
 
VL_API vl_hash_iter vlHashTableInsert(vl_hashtable* table, const void* key, vl_memsize_t keySize,
                                      vl_memsize_t dataSize);
 
VL_API void vlHashTableRemoveKey(vl_hashtable* table, const void* key, vl_memsize_t keyLen);
 
VL_API void vlHashTableRemoveIter(vl_hashtable* table, vl_hash_iter iter);
 
VL_API void vlHashTableClear(vl_hashtable* table);
 
VL_API vl_hashtable* vlHashTableClone(const vl_hashtable* table, vl_hashtable* dest);
 
VL_API vl_hash_iter vlHashTableCopyElement(vl_hashtable* src, vl_hash_iter iter, vl_hashtable* dest);
 
VL_API int vlHashTableCopy(vl_hashtable* src, vl_hashtable* dest);
 
VL_API void vlHashTableReserve(vl_hashtable* table, vl_memsize_t buckets, vl_memsize_t heapSize);
 
VL_API vl_hash_iter vlHashTableFind(vl_hashtable* table, const void* key, vl_memsize_t keySize);
 
VL_API const vl_transient* vlHashTableSampleKey(vl_hashtable* table, vl_hash_iter iter,
                                                /*out*/ vl_memsize_t* size);
 
VL_API vl_transient* vlHashTableSampleValue(vl_hashtable* table, vl_hash_iter iter,
                                            /*out*/ vl_memsize_t* size);
 
VL_API vl_hash_iter vlHashTableFront(vl_hashtable* table);
 
VL_API vl_hash_iter vlHashTableNext(vl_hashtable* table, vl_hash_iter iter);
 
// notice "back" and "prev" functions are omitted here.
// considering there is no well-defined order that should be expected from this
// structure, it shouldn't make much difference to iterate forward or backward,
// so long as all elements are encompassed in the iteration.
 
// that said, it can often be observed that iteration occurs in the reverse
// order of insertion *up until* the first resize of the table. this is due to
// how the underlying arena behaves, slicing memory off the end of the first
// free block of memory.
 
#endif // VL_HASHTABLE_H