libs/basekit/source/SHash.h

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 docDescription("""
   6     SHash - Cuckoo Hash
   7     keys and values are references (they are not copied or freed)
   8     key pointers are assumed unique
   9 """)
  10 */
  11
  12 #ifndef SHASH_DEFINED
  13 #define SHASH_DEFINED 1
  14
  15 #include "Common.h"
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include <stddef.h>
  19
  20 #ifdef __cplusplus
  21 extern "C" {
  22 #endif
  23
  24 typedef struct
  25 {
  26     void *key;
  27     void *value;
  28 } SHashRecord;
  29
  30 typedef int (SHashKeysEqualCallback)(void *, void *);
  31 typedef intptr_t (SHashHashforKeyCallback)(void *);
  32
  33 typedef struct
  34 {
  35     SHashRecord *records;               // contains the two tables
  36
  37     unsigned int log2tableSize; // log2(tableSize)
  38     unsigned int tableSize;             // total number of records per table
  39     unsigned int numKeys;               // number of used records
  40
  41     unsigned int mask;              // hash bit mask
  42     SHashRecord nullRecord;             // for lookup misses
  43     unsigned int balance;               // to balance tables
  44     SHashKeysEqualCallback *keysEqual;
  45     SHashHashforKeyCallback *hashForKey;
  46
  47 } SHash;
  48
  49 //#define SHash_mask(self) (self->tableSize-1)
  50 #define SHash_maxLoops(self) (self->tableSize < 20 ? self->tableSize : 20)
  51 #define SHash_maxKeys(self)  (self->tableSize)
  52 #define SHash_setKeysEqualCallback(self, v)  (self->keysEqual = v)
  53 #define SHash_setHashForKeyCallback(self, v)  (self->hashForKey = v)
  54
  55 BASEKIT_API void SHash_print(SHash *self); // to debug
  56
  57 BASEKIT_API SHash *SHash_new(void);
  58 BASEKIT_API void SHash_free(SHash *self);
  59 BASEKIT_API SHash *SHash_clone(SHash *self);
  60 BASEKIT_API void SHash_copy_(SHash *self, SHash *other);
  61
  62 BASEKIT_API SHashRecord* SHash_cuckoo_(SHash *self, SHashRecord* record);
  63 BASEKIT_API void SHash_grow(SHash *self);
  64 BASEKIT_API void SHash_growWithRecord(SHash *self, SHashRecord* record);
  65
  66 BASEKIT_API size_t SHash_memorySize(SHash *self);
  67 BASEKIT_API void SHash_compact(SHash *self);
  68
  69 BASEKIT_API unsigned int SHash_count(SHash *self);
  70 BASEKIT_API unsigned int SHash_countRecords_size_(unsigned char *records, unsigned int size);
  71
  72 BASEKIT_API void *SHash_firstKeyForValue_(SHash *self, void *v);
  73
  74 BASEKIT_API void SHash_removeValue_(SHash *self, void *value);
  75
  76 #include "SHash_inline.h"
  77
  78 #ifdef __cplusplus
  79 }
  80 #endif
  81 #endif
  82