hashtable.h

Go to the documentation of this file.

#pragma once
 
#include <cx/cx.h>
#include <cx/debug/assert.h>
 
 
 
typedef struct hashtable_ref {
    void* _is_hashtable;
} hashtable_ref;
 
typedef struct hashtable_ref* hashtable;
typedef struct HTChunkInfo HTChunkInfo;
 
// Internal structure - do not access directly
// Use htSize(), htKeyType(), htValType() macros instead
typedef struct HashTableHeader {
    // extended header, present only if HT_Extended is set
    STypeOps keytypeops;
    STypeOps valtypeops;
 
    // hashtable header begins here
    uint32 idxsz;      // index size
    uint32 idxused;    // number of used index entries (including deleted)
    uint32 storsz;     // number of chunks in storage array
    uint32 storused;   // number of used storage slots (including deleted)
    uint32 valid;      // number of valid items in the hash table
 
    stype keytype;
    stype valtype;
    uint32 flags;
 
    HTChunkInfo* chunks;
    void** keystorage;
    void** valstorage;
    uint32 index[1];
} HashTableHeader;
 
// Element handle - represents a slot in the hash table
// Value of 0 is reserved for "null" / not found
// Can be used to retrieve key/value pointers without a second lookup
typedef uint32 htelem;
 
// Hash table iterator state
typedef struct htiter {
    HashTableHeader* hdr;
    uint32 slot;
} htiter;
 
// Storage allocation constants
// HT_SLOTS_PER_CHUNK MUST BE A POWER OF TWO!
#ifdef _64BIT
#define HT_CHUNK_SHIFT 6
#else
#define HT_CHUNK_SHIFT 5
#endif
#define HT_SLOTS_PER_CHUNK (1 << HT_CHUNK_SHIFT)
#define HT_CHUNK_MASK      (HT_SLOTS_PER_CHUNK - 1)
#define HT_QUARTER_CHUNK   (HT_SLOTS_PER_CHUNK >> 2)
#define HT_QCHUNK_MASK     (HT_QUARTER_CHUNK - 1)
 
// Internal macros for header access - do not use directly
#define HTABLE_HDRSIZE  (offsetof(HashTableHeader, index))
#define HTABLE_HDR(ref) ((HashTableHeader*)(((uintptr)(&((ref)->_is_hashtable))) - HTABLE_HDRSIZE))
 
// Internal function - use htSize(), htKeyType(), htValType() macros instead
_Ret_valid_ _meta_inline HashTableHeader* _htHdr(_In_ hashtable ref)
{
    return HTABLE_HDR(ref);
}
 
#define htSize(ref) ((ref) ? _htHdr((ref))->valid : 0)
 
#define htKeyType(ref) ((ref) ? _htHdr((ref))->keytype : 0)
 
#define htValType(ref) ((ref) ? _htHdr((ref))->valtype : 0)
 
#define hteKeyPtrHdr(hdr, type, elem) ((stStorageType(type)*)_hteElemKeyPtr(hdr, elem))
 
#define hteValPtrHdr(hdr, type, elem) ((stStorageType(type)*)_hteElemValPtr(hdr, elem))
 
#define hteKeyPtr(ref, type, elem) hteKeyPtrHdr(_htHdr(ref), type, elem)
 
#define hteValPtr(ref, type, elem) hteValPtrHdr(_htHdr(ref), type, elem)
 
#define hteKey(ref, type, elem) (*hteKeyPtr(ref, type, elem))
 
#define hteVal(ref, type, elem) (*hteValPtr(ref, type, elem))
 
#define htiKeyPtr(type, iter) (hteKeyPtrHdr((iter).hdr, type, (iter).slot))
 
#define htiValPtr(type, iter) (hteValPtrHdr((iter).hdr, type, (iter).slot))
 
#define htiKey(type, iter) (*htiKeyPtr(type, iter))
 
#define htiVal(type, iter) (*htiValPtr(type, iter))
 
 
 
enum HASHTABLE_FLAGS_ENUM {
    HT_CaseInsensitive = 0x0001,
 
    HT_RefKeys = 0x0002,
 
    HT_Ref = 0x0004,
 
    HT_InsertOpt = 0x0008,
 
    HT_Compact = 0x0010,
 
    // Internal use only - do not set manually
    HTINT_Metadata  = 0x1000,   // metadata area (for hash fragments) is present after index
    HTINT_Quadratic = 0x2000,   // use quadratic probing rather than linear
    HTINT_Pow2      = 0x4000,   // size forced to power of 2 to avoid division
    HTINT_Extended  = 0x8000,   // extended header is present
};
 
// Growth rate configuration - controls how much to grow when expanding the table
enum HASHTABLE_GROWBY_ENUM {
    HT_GROW_By100   = 0x00,   // Double size (balanced default)
    HT_GROW_By200   = 0x10,   // Triple size
    HT_GROW_By300   = 0x20,   // Quadruple size (better performance, uses more memory)
    HT_GROW_By50    = 0x40,   // Grow by 50% (worse performance, memory efficient)
    HT_GROW_BY_MASK = 0xf0,
};
 
// Growth threshold configuration - controls when to expand the table
enum HASHTABLE_GROW_ENUM {
    HT_GROW_At75    = 0x00,   // Grow when 75% full (balanced default)
    HT_GROW_At50    = 0x01,   // Grow when 50% full (better performance, uses more memory)
    HT_GROW_At90    = 0x02,   // Grow when 90% full (worse performance, memory efficient)
    HT_GROW_AT_MASK = 0x0f,
 
    // Preset combinations for common use cases
    HT_GROW_MaxSpeed = (uint32)HT_GROW_At50 | (uint32)HT_GROW_By300,   // Maximum performance
    HT_GROW_MinSize  = (uint32)HT_GROW_At90 | (uint32)HT_GROW_By50,    // Minimum memory usage
};
 
enum HASHTABLE_FUNC_FLAGS_ENUM {
    HT_Ignore = 0x00010000,
 
    HT_Borrow = 0x00020000,
 
    // Internal use only - do not use directly
    HTINT_Consume = 0x10000000,
};
 
// Helper macros for growth configuration
 
#define HT_GROW_MASK (0xff000000)
 
#define HT_Grow(flag) (((uint32)HT_GROW_##flag) << 24)
 
// Internal macro - extracts growth settings from flags
#define HT_GET_GROW(flags) ((flags) >> 24)
 
void _htInit(_Outptr_ hashtable* out, stype keytype, _In_opt_ STypeOps* keyops, stype valtype,
             _In_opt_ STypeOps* valops, uint32 initsz, flags_t flags);
 
#define htInit(out, keytype, valtype, initsz, ...) \
    _htInit(out, stFullType(keytype), stFullType(valtype), initsz, opt_flags(__VA_ARGS__))
 
void htDestroy(_Inout_ptr_uninit_ hashtable* htbl);
 
void htClear(_Inout_ptr_ hashtable* htbl);
 
 
 
void htReindex(_Inout_ptr_ hashtable* htbl, uint32 minsz);
 
void htRepack(_Inout_ptr_ hashtable* htbl);
 
void htClone(_Outptr_ hashtable* out, _In_ hashtable ref);
 
// Internal function - do not call directly, use htInsert() or htInsertC() macro instead
htelem _htInsert(_Inout_ptr_ hashtable* htbl, _In_ stgeneric key, _In_ stgeneric val,
                 flags_t flags);
 
// Internal function with type checking
_meta_inline htelem _htInsertChecked(_Inout_ptr_ hashtable* htbl, stype keytype, _In_ stgeneric key,
                                     stype valtype, _In_ stgeneric val, flags_t flags)
{
    devAssert(*htbl);
    devAssert(stEq(htKeyType(*htbl), keytype) && stEq(htValType(*htbl), valtype));
    return _htInsert(htbl, key, val, flags);
}
 
// Internal SAL annotation helper
#define _ht_Consume_Arg_                                       \
    _When_(flags& HTINT_Consume, _Pre_notnull_ _Post_invalid_) \
        _When_(!(flags & HTINT_Consume), _Inout_)
 
// Internal function - do not call directly, use htInsertC() macro instead
htelem _htInsertPtr(_Inout_ptr_ hashtable* htbl, _In_ stgeneric key,
                    _ht_Consume_Arg_ stgeneric* val, flags_t flags);
 
// Internal function with type checking
_meta_inline htelem _htInsertCheckedC(_Inout_ptr_ hashtable* htbl, stype keytype,
                                      _In_ stgeneric key, stype valtype,
                                      _ht_Consume_Arg_ stgeneric* val, flags_t flags)
{
    devAssert(*htbl);
    devAssert(stEq(htKeyType(*htbl), keytype) && stEq(htValType(*htbl), valtype));
    return _htInsertPtr(htbl, key, val, flags);
}
 
#define htInsert(htbl, ktype, key, vtype, val, ...) \
    _htInsertChecked(htbl,                          \
                     stCheckedArg(ktype, key),      \
                     stCheckedArg(vtype, val),      \
                     opt_flags(__VA_ARGS__))
 
#define htInsertC(htbl, ktype, key, vtype, val, ...) \
    _htInsertCheckedC(htbl,                          \
                      stCheckedArg(ktype, key),      \
                      stCheckedPtrArg(vtype, val),   \
                      opt_flags(__VA_ARGS__) | HTINT_Consume)
 
// Internal function - do not call directly, use htFind() macro instead
_Success_(return != 0)
htelem _htFind(_In_ hashtable htbl, _In_ stgeneric key, _Inout_opt_ stgeneric* val, flags_t flags);
 
// Internal function with type checking
_Success_(return != 0) _meta_inline
htelem _htFindChecked(_In_ hashtable htbl, stype keytype, _In_ stgeneric key, stype valtype,
                      _stCopyDest_Anno_opt_(valtype) stgeneric* val, flags_t flags)
{
    devAssert(htbl);
    devAssert(stEq(htKeyType(htbl), keytype));
    devAssert(stGetId(valtype) == stTypeId(none) || stEq(htValType(htbl), valtype));
    return _htFind(htbl, key, val, flags);
}
 
#define htFind(htbl, ktype, key, vtype, val_copy_out, ...) \
    _htFindChecked(htbl,                                   \
                   stCheckedArg(ktype, key),               \
                   stCheckedPtrArg(vtype, val_copy_out),   \
                   opt_flags(__VA_ARGS__))
 
// Internal function - do not call directly, use htExtract() or htRemove() macro instead
_Success_(return) bool
_htExtract(_Inout_ptr_ hashtable* htbl, _In_ stgeneric key, _Inout_opt_ stgeneric* val);
 
// Internal function with type checking
_Success_(return)
_meta_inline bool _htExtractChecked(_Inout_ptr_ hashtable* htbl, stype keytype, _In_ stgeneric key,
                                    stype valtype, _stCopyDest_Anno_opt_(valtype) stgeneric* val)
{
    devAssert(*htbl);
    devAssert(stEq(htKeyType(*htbl), keytype));
    devAssert(stGetId(valtype) == stTypeId(none) || stEq(htValType(*htbl), valtype));
    return _htExtract(htbl, key, val);
}
 
#define htExtract(htbl, ktype, key, vtype, val_copy_out) \
    _htExtractChecked(htbl, stCheckedArg(ktype, key), stCheckedPtrArg(vtype, val_copy_out))
 
#define htRemove(htbl, ktype, key) \
    _htExtractChecked(htbl, stCheckedArg(ktype, key), stType(none), NULL)
 
// Internal function - do not call directly, use htHasKey() macro instead
bool _htHasKey(_In_ hashtable htbl, _In_ stgeneric key);
 
// Internal function with type checking
_meta_inline bool _htHasKeyChecked(_In_ hashtable htbl, stype keytype, _In_ stgeneric key)
{
    devAssert(htbl);
    devAssert(stEq(htKeyType(htbl), keytype));
    return _htHasKey(htbl, key);
}
 
#define htHasKey(htbl, ktype, key) _htHasKeyChecked(htbl, stCheckedArg(ktype, key))
 
 
// Internal function - gets pointer to key storage for an element
// Do not call directly - use hteKeyPtr() or hteKey() macros instead
_Pre_satisfies_(elem > 0) void* _hteElemKeyPtr(_Inout_ HashTableHeader* hdr, htelem elem);
 
// Internal function - gets pointer to value storage for an element
// Do not call directly - use hteValPtr() or hteVal() macros instead
_Pre_satisfies_(elem > 0) void* _hteElemValPtr(_Inout_ HashTableHeader* hdr, htelem elem);
 
 
// define separately so the the prototype is all on one line and the tooltips in vscode work
// properly...
#define _htiInitAnno                                   \
    _Success_(return) _Post_satisfies_(iter->slot > 0) \
        _On_failure_(_Post_satisfies_(iter->slot == 0))
 
_htiInitAnno bool htiInit(_Out_ htiter* iter, _In_ hashtable htbl);
 
#define _htiNextAnno                                   \
    _Success_(return) _Post_satisfies_(iter->slot > 0) \
        _On_failure_(_Post_satisfies_(iter->slot == 0))
 
_htiNextAnno bool htiNext(_Inout_ htiter* iter);
 
void htiFinish(_Pre_notnull_ _Post_invalid_ htiter* iter);
 
_Post_equal_to_(iter->slot > 0) _meta_inline bool htiValid(_In_ htiter* iter)
{
    return iter->slot > 0;
}