1 //metadoc CHash copyright Steve Dekorte 2009
2 //metadoc CHash license BSD revised
3 /*metadoc CHash description
4 CHash - Cuckoo Hash
5 keys and values are references (they are not copied or freed)
6 */
7
8 #ifdef CHASH_C
9 #define IO_IN_C_FILE
10 #endif
11 #include "Common_inline.h"
12 #ifdef IO_DECLARE_INLINES
13
14 #define CRecords_recordAt_(records, pos) (CHashRecord *)(records + (pos * sizeof(CHashRecord)))
15
CHash_record1_(CHash * self,void * k)16 IOINLINE CHashRecord *CHash_record1_(CHash *self, void *k)
17 {
18 // the ~ | 0x1 before the mask ensures an even pos
19 size_t pos = self->hash1(k) & self->mask;
20 //printf("pos1 %i/%i\n", pos, self->size);
21 return CRecords_recordAt_(self->records, pos);
22 }
23
CHash_record2_(CHash * self,void * k)24 IOINLINE CHashRecord *CHash_record2_(CHash *self, void *k)
25 {
26 // the | 0x1 before the mask ensures an odd pos
27 size_t pos = self->hash2(k) & self->mask;
28 //printf("pos2 %i/%i\n", pos, self->size);
29 return CRecords_recordAt_(self->records, pos);
30 }
31
CHash_at_(CHash * self,void * k)32 IOINLINE void *CHash_at_(CHash *self, void *k)
33 {
34 CHashRecord *r;
35
36 r = CHash_record1_(self, k);
37
38 if(r->k && self->equals(k, r->k))
39 {
40 return r->v;
41 }
42
43 r = CHash_record2_(self, k);
44
45 if(r->k && self->equals(k, r->k))
46 {
47 return r->v;
48 }
49
50 return 0x0;
51 }
52
CHash_count(CHash * self)53 IOINLINE size_t CHash_count(CHash *self)
54 {
55 return self->keyCount;
56 }
57
CHashKey_hasKey_(CHash * self,void * key)58 IOINLINE int CHashKey_hasKey_(CHash *self, void *key)
59 {
60 return CHash_at_(self, key) != NULL;
61 }
62
CHash_at_put_(CHash * self,void * k,void * v)63 IOINLINE int CHash_at_put_(CHash *self, void *k, void *v)
64 {
65 CHashRecord *r;
66
67 r = CHash_record1_(self, k);
68
69 if(!r->k)
70 {
71 r->k = k;
72 r->v = v;
73 self->keyCount ++;
74 return 0;
75 }
76
77 if(k == r->k || self->equals(k, r->k))
78 {
79 r->v = v;
80 return 0;
81 }
82
83 r = CHash_record2_(self, k);
84
85 if(!r->k)
86 {
87 r->k = k;
88 r->v = v;
89 self->keyCount ++;
90 return 0;
91 }
92
93 if(k == r->k || self->equals(k, r->k))
94 {
95 r->v = v;
96 return 0;
97 }
98
99
100 {
101 CHashRecord x;
102 x.k = k;
103 x.v = v;
104 return CHash_insert_(self, &x);
105 }
106 }
107
CHash_shrinkIfNeeded(CHash * self)108 IOINLINE void CHash_shrinkIfNeeded(CHash *self)
109 {
110 if(self->keyCount < self->size/5)
111 {
112 CHash_shrink(self);
113 }
114 }
115
CHashRecord_swapWith_(CHashRecord * self,CHashRecord * other)116 IOINLINE void CHashRecord_swapWith_(CHashRecord *self, CHashRecord *other)
117 {
118 CHashRecord tmp = *self;
119 *self = *other;
120 *other = tmp;
121 }
122
CHash_clean(CHash * self)123 IOINLINE void CHash_clean(CHash *self)
124 {
125 memset(self->records, 0, sizeof(CHashRecord) * self->size);
126 self->keyCount = 0;
127 }
128
129 // --- enumeration --------------------------------------------------
130
131 #define CHASH_FOREACH(self, pkey, pvalue, code) \
132 {\
133 CHash *_self = (self);\
134 unsigned char *_records = _self->records;\
135 size_t _i, _size = _self->size;\
136 void *pkey;\
137 void *pvalue;\
138 \
139 for (_i = 0; _i < _size; _i ++)\
140 {\
141 CHashRecord *_record = CRecords_recordAt_(_records, _i);\
142 if (_record->k)\
143 {\
144 pkey = _record->k;\
145 pvalue = _record->v;\
146 code;\
147 }\
148 }\
149 }
150
151 #undef IO_IN_C_FILE
152 #endif
153