libs/basekit/source/PHash.h

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 docDescription("""
   6     PHash - 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 PHASH_DEFINED
  13 #define PHASH_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 } PHashRecord;
  29
  30
  31 typedef struct
  32 {
  33     PHashRecord *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     PHashRecord nullRecord;             // for lookup misses
  41     unsigned int balance;               // to balance tables
  42 } PHash;
  43
  44 //#define PHash_mask(self) (self->tableSize-1)
  45 #define PHash_maxLoops(self) (self->tableSize)
  46 #define PHash_maxKeys(self) (self->tableSize)
  47
  48 BASEKIT_API void PHash_print(PHash *self); // to debug
  49
  50 BASEKIT_API PHash *PHash_new(void);
  51 BASEKIT_API void PHash_free(PHash *self);
  52 BASEKIT_API PHash *PHash_clone(PHash *self);
  53 BASEKIT_API void PHash_copy_(PHash *self, PHash *other);
  54
  55 BASEKIT_API PHashRecord* PHash_cuckoo_(PHash *self, PHashRecord* record);
  56 BASEKIT_API void PHash_grow(PHash *self);
  57 BASEKIT_API void PHash_growWithRecord(PHash *self, PHashRecord* record);
  58
  59 BASEKIT_API size_t PHash_memorySize(PHash *self);
  60 BASEKIT_API void PHash_compact(PHash *self);
  61
  62 BASEKIT_API unsigned int PHash_count(PHash *self);
  63 BASEKIT_API unsigned int PHash_countRecords_size_(unsigned char *records, unsigned int size);
  64
  65 BASEKIT_API void *PHash_firstKeyForValue_(PHash *self, void *v);
  66
  67 // --- perform --------------------------------------------------
  68
  69 BASEKIT_API void PHash_removeValue_(PHash *self, void *value);
  70
  71 #include "PHash_inline.h"
  72
  73 #ifdef __cplusplus
  74 }
  75 #endif
  76 #endif
  77