libs/basekit/source/SHash.h

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