1 //metadoc PointerHash copyright Steve Dekorte 2002, Marc Fauconneau 2007
2 //metadoc PointerHash license BSD revised
3 /*metadoc PointerHash description
4 PointerHash - Cuckoo Hash
5 keys and values are references (they are not copied or freed)
6 key pointers are assumed unique
7 */
8
9 #ifdef POINTERHASH_C
10 #define IO_IN_C_FILE
11 #endif
12 #include "Common_inline.h"
13 #ifdef IO_DECLARE_INLINES
14
15 #define PointerHashRecords_recordAt_(records, pos) (PointerHashRecord *)(records + (pos * sizeof(PointerHashRecord)))
16
17 /*
18 IOINLINE unsigned int PointerHash_hash(PointerHash *self, void *key)
19 {
20 intptr_t k = (intptr_t)PointerHashKey_value(key);
21 return k^(k>>4);
22 }
23
24 IOINLINE unsigned int PointerHash_hash_more(PointerHash *self, unsigned int hash)
25 {
26 return hash ^ (hash >> self->log2tableSize);
27 }
28 */
29
30 // -----------------------------------
31
PointerHash_record1_(PointerHash * self,void * k)32 IOINLINE PointerHashRecord *PointerHash_record1_(PointerHash *self, void *k)
33 {
34 // the ~| 0x1 before the mask ensures an odd pos
35 intptr_t kk = (intptr_t)k;
36 size_t pos = ((kk^(kk>>4)) | 0x1) & self->mask;
37 return PointerHashRecords_recordAt_(self->records, pos);
38 }
39
PointerHash_record2_(PointerHash * self,void * k)40 IOINLINE PointerHashRecord *PointerHash_record2_(PointerHash *self, void *k)
41 {
42 // the | 0x1 before the mask ensures an even pos
43 intptr_t kk = (intptr_t)k;
44 //size_t pos = (((kk^(kk/33)) << 1)) & self->mask;
45 size_t pos = (kk << 1) & self->mask;
46 return PointerHashRecords_recordAt_(self->records, pos);
47 }
48
PointerHash_at_(PointerHash * self,void * k)49 IOINLINE void *PointerHash_at_(PointerHash *self, void *k)
50 {
51 PointerHashRecord *r;
52
53 r = PointerHash_record1_(self, k);
54 if(k == r->k) return r->v;
55
56 r = PointerHash_record2_(self, k);
57 if(k == r->k) return r->v;
58
59 return 0x0;
60 }
61
PointerHash_count(PointerHash * self)62 IOINLINE size_t PointerHash_count(PointerHash *self)
63 {
64 return self->keyCount;
65 }
66
PointerHashKey_hasKey_(PointerHash * self,void * key)67 IOINLINE int PointerHashKey_hasKey_(PointerHash *self, void *key)
68 {
69 return PointerHash_at_(self, key) != NULL;
70 }
71
PointerHash_at_put_(PointerHash * self,void * k,void * v)72 IOINLINE void PointerHash_at_put_(PointerHash *self, void *k, void *v)
73 {
74 PointerHashRecord *r;
75
76 r = PointerHash_record1_(self, k);
77
78 if(!r->k)
79 {
80 r->k = k;
81 r->v = v;
82 self->keyCount ++;
83 return;
84 }
85
86 if(r->k == k)
87 {
88 r->v = v;
89 return;
90 }
91
92 r = PointerHash_record2_(self, k);
93
94 if(!r->k)
95 {
96 r->k = k;
97 r->v = v;
98 self->keyCount ++;
99 return;
100 }
101
102 if(r->k == k)
103 {
104 r->v = v;
105 return;
106 }
107
108 {
109 PointerHashRecord x;
110 x.k = k;
111 x.v = v;
112 PointerHash_insert_(self, &x);
113 }
114 }
115
PointerHash_shrinkIfNeeded(PointerHash * self)116 IOINLINE void PointerHash_shrinkIfNeeded(PointerHash *self)
117 {
118 if(self->keyCount < self->size/8)
119 {
120 PointerHash_shrink(self);
121 }
122 }
123
PointerHashRecord_swapWith_(PointerHashRecord * self,PointerHashRecord * other)124 IOINLINE void PointerHashRecord_swapWith_(PointerHashRecord *self, PointerHashRecord *other)
125 {
126 PointerHashRecord tmp = *self;
127 *self = *other;
128 *other = tmp;
129 }
130
PointerHash_clean(PointerHash * self)131 IOINLINE void PointerHash_clean(PointerHash *self)
132 {
133 memset(self->records, 0, sizeof(PointerHashRecord) * self->size);
134 self->keyCount = 0;
135 }
136
137 // --- enumeration --------------------------------------------------
138
139 #define POINTERHASH_FOREACH(self, pkey, pvalue, code) \
140 {\
141 PointerHash *_self = (self);\
142 unsigned char *_records = _self->records;\
143 size_t _i, _size = _self->size;\
144 void *pkey;\
145 void *pvalue;\
146 \
147 for (_i = 0; _i < _size; _i ++)\
148 {\
149 PointerHashRecord *_record = PointerHashRecords_recordAt_(_records, _i);\
150 if (_record->k)\
151 {\
152 pkey = _record->k;\
153 pvalue = _record->v;\
154 code;\
155 }\
156 }\
157 }
158
159 #undef IO_IN_C_FILE
160 #endif
161