|
4
|
1
|
|
|
2 // written in the D programming language
|
|
|
3
|
|
|
4 module chipmunkd.cpHashSet;
|
|
|
5
|
|
|
6 import chipmunkd.chipmunk;
|
|
|
7 import chipmunkd.chipmunk_types_h;
|
|
|
8 import chipmunkd.cpArray;
|
|
|
9 import chipmunkd.prime;
|
|
|
10
|
|
|
11 // cpHashSet uses a chained hashtable implementation.
|
|
|
12 // Other than the transformation functions, there is nothing fancy going on.
|
|
|
13
|
|
|
14 // cpHashSetBin's form the linked lists in the chained hash table.
|
|
|
15 struct cpHashSetBin {
|
|
|
16 // Pointer to the element.
|
|
|
17 void *elt;
|
|
|
18 // Hash value of the element.
|
|
|
19 cpHashValue hash;
|
|
|
20 // Next element in the chain.
|
|
|
21 cpHashSetBin *next;
|
|
|
22 }
|
|
|
23
|
|
|
24 // Equality function. Returns true if ptr is equal to elt.
|
|
|
25 alias cpBool function(void *ptr, void *elt) cpHashSetEqlFunc;
|
|
|
26 // Used by cpHashSetInsert(). Called to transform the ptr into an element.
|
|
|
27 alias void* function(void *ptr, void *data) cpHashSetTransFunc;
|
|
|
28
|
|
|
29 struct cpHashSet {
|
|
|
30 // Number of elements stored in the table.
|
|
|
31 int entries;
|
|
|
32 // Number of cells in the table.
|
|
|
33 int size;
|
|
|
34
|
|
|
35 cpHashSetEqlFunc eql;
|
|
|
36 cpHashSetTransFunc trans;
|
|
|
37
|
|
|
38 // Default value returned by cpHashSetFind() when no element is found.
|
|
|
39 // Defaults to null.
|
|
|
40 void *default_value;
|
|
|
41
|
|
|
42 // The table and recycled bins
|
|
|
43 cpHashSetBin **table;
|
|
|
44 cpHashSetBin *pooledBins;
|
|
|
45
|
|
|
46 cpArray *allocatedBuffers;
|
|
|
47 }
|
|
|
48
|
|
|
49 alias void function(void *elt, void *data) cpHashSetIterFunc;
|
|
|
50 alias cpBool function(void *elt, void *data) cpHashSetFilterFunc;
|
|
|
51
|
|
|
52 static void freeWrap(void *ptr, void *unused){cpfree(ptr);}
|
|
|
53
|
|
|
54 void
|
|
|
55 cpHashSetDestroy(cpHashSet *set)
|
|
|
56 {
|
|
|
57 // Free the table.
|
|
|
58 cpfree(set.table);
|
|
|
59
|
|
|
60 cpArrayEach(set.allocatedBuffers, &freeWrap, null);
|
|
|
61 cpArrayFree(set.allocatedBuffers);
|
|
|
62 }
|
|
|
63
|
|
|
64 void
|
|
|
65 cpHashSetFree(cpHashSet *set)
|
|
|
66 {
|
|
|
67 if(set){
|
|
|
68 cpHashSetDestroy(set);
|
|
|
69 cpfree(set);
|
|
|
70 }
|
|
|
71 }
|
|
|
72
|
|
|
73 cpHashSet *
|
|
|
74 cpHashSetAlloc()
|
|
|
75 {
|
|
|
76 return cast(cpHashSet *)cpcalloc(1, cpHashSet.sizeof);
|
|
|
77 }
|
|
|
78
|
|
|
79 cpHashSet *
|
|
|
80 cpHashSetInit(cpHashSet *set, int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans)
|
|
|
81 {
|
|
|
82 set.size = next_prime(size);
|
|
|
83 set.entries = 0;
|
|
|
84
|
|
|
85 set.eql = eqlFunc;
|
|
|
86 set.trans = trans;
|
|
|
87
|
|
|
88 set.default_value = null;
|
|
|
89
|
|
|
90 set.table = cast(cpHashSetBin **)cpcalloc(set.size, (cpHashSetBin *).sizeof);
|
|
|
91 set.pooledBins = null;
|
|
|
92
|
|
|
93 set.allocatedBuffers = cpArrayNew(0);
|
|
|
94
|
|
|
95 return set;
|
|
|
96 }
|
|
|
97
|
|
|
98 cpHashSet *
|
|
|
99 cpHashSetNew(int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans)
|
|
|
100 {
|
|
|
101 return cpHashSetInit(cpHashSetAlloc(), size, eqlFunc, trans);
|
|
|
102 }
|
|
|
103
|
|
|
104 static int
|
|
|
105 setIsFull(cpHashSet *set)
|
|
|
106 {
|
|
|
107 return (set.entries >= set.size);
|
|
|
108 }
|
|
|
109
|
|
|
110 static void
|
|
|
111 cpHashSetResize(cpHashSet *set)
|
|
|
112 {
|
|
|
113 // Get the next approximate doubled prime.
|
|
|
114 int newSize = next_prime(set.size + 1);
|
|
|
115 // Allocate a new table.
|
|
|
116 cpHashSetBin **newTable = cast(cpHashSetBin **)cpcalloc(newSize, (cpHashSetBin *).sizeof);
|
|
|
117
|
|
|
118 // Iterate over the chains.
|
|
|
119 for(int i=0; i<set.size; i++){
|
|
|
120 // Rehash the bins into the new table.
|
|
|
121 cpHashSetBin *bin = set.table[i];
|
|
|
122 while(bin){
|
|
|
123 cpHashSetBin *next = bin.next;
|
|
|
124
|
|
|
125 int idx = bin.hash%newSize;
|
|
|
126 bin.next = newTable[idx];
|
|
|
127 newTable[idx] = bin;
|
|
|
128
|
|
|
129 bin = next;
|
|
|
130 }
|
|
|
131 }
|
|
|
132
|
|
|
133 cpfree(set.table);
|
|
|
134
|
|
|
135 set.table = newTable;
|
|
|
136 set.size = newSize;
|
|
|
137 }
|
|
|
138
|
|
|
139 static void
|
|
|
140 recycleBin(cpHashSet *set, cpHashSetBin *bin)
|
|
|
141 {
|
|
|
142 bin.next = set.pooledBins;
|
|
|
143 set.pooledBins = bin;
|
|
|
144 bin.elt = null;
|
|
|
145 }
|
|
|
146
|
|
|
147 static cpHashSetBin *
|
|
|
148 getUnusedBin(cpHashSet *set)
|
|
|
149 {
|
|
|
150 cpHashSetBin *bin = set.pooledBins;
|
|
|
151
|
|
|
152 if(bin){
|
|
|
153 set.pooledBins = bin.next;
|
|
|
154 return bin;
|
|
|
155 } else {
|
|
|
156 // Pool is exhausted, make more
|
|
|
157 int count = CP_BUFFER_BYTES/cpHashSetBin.sizeof;
|
|
|
158 assert(count!=0, "Buffer size is too small.");
|
|
|
159
|
|
|
160 cpHashSetBin *buffer = cast(cpHashSetBin *)cpmalloc(CP_BUFFER_BYTES);
|
|
|
161 cpArrayPush(set.allocatedBuffers, buffer);
|
|
|
162
|
|
|
163 // push all but the first one, return the first instead
|
|
|
164 for(int i=1; i<count; i++) recycleBin(set, buffer + i);
|
|
|
165 return buffer;
|
|
|
166 }
|
|
|
167 }
|
|
|
168
|
|
|
169 void *
|
|
|
170 cpHashSetInsert(cpHashSet *set, cpHashValue hash, void *ptr, void *data)
|
|
|
171 {
|
|
|
172 int idx = hash%set.size;
|
|
|
173
|
|
|
174 // Find the bin with the matching element.
|
|
|
175 cpHashSetBin *bin = set.table[idx];
|
|
|
176 while(bin && !set.eql(ptr, bin.elt))
|
|
|
177 bin = bin.next;
|
|
|
178
|
|
|
179 // Create it necessary.
|
|
|
180 if(!bin){
|
|
|
181 bin = getUnusedBin(set);
|
|
|
182 bin.hash = hash;
|
|
|
183 bin.elt = set.trans(ptr, data); // Transform the pointer.
|
|
|
184
|
|
|
185 bin.next = set.table[idx];
|
|
|
186 set.table[idx] = bin;
|
|
|
187
|
|
|
188 set.entries++;
|
|
|
189
|
|
|
190 // Resize the set if it's full.
|
|
|
191 if(setIsFull(set))
|
|
|
192 cpHashSetResize(set);
|
|
|
193 }
|
|
|
194
|
|
|
195 return bin.elt;
|
|
|
196 }
|
|
|
197
|
|
|
198 void *
|
|
|
199 cpHashSetRemove(cpHashSet *set, cpHashValue hash, void *ptr)
|
|
|
200 {
|
|
|
201 int idx = hash%set.size;
|
|
|
202
|
|
|
203 // Pointer to the previous bin pointer.
|
|
|
204 cpHashSetBin **prev_ptr = &set.table[idx];
|
|
|
205 // Pointer the the current bin.
|
|
|
206 cpHashSetBin *bin = set.table[idx];
|
|
|
207
|
|
|
208 // Find the bin
|
|
|
209 while(bin && !set.eql(ptr, bin.elt)){
|
|
|
210 prev_ptr = &bin.next;
|
|
|
211 bin = bin.next;
|
|
|
212 }
|
|
|
213
|
|
|
214 // Remove it if it exists.
|
|
|
215 if(bin){
|
|
|
216 // Update the previous bin pointer to point to the next bin.
|
|
|
217 (*prev_ptr) = bin.next;
|
|
|
218 set.entries--;
|
|
|
219
|
|
|
220 void *return_value = bin.elt;
|
|
|
221
|
|
|
222 recycleBin(set, bin);
|
|
|
223
|
|
|
224 return return_value;
|
|
|
225 }
|
|
|
226
|
|
|
227 return null;
|
|
|
228 }
|
|
|
229
|
|
|
230 void *
|
|
|
231 cpHashSetFind(cpHashSet *set, cpHashValue hash, void *ptr)
|
|
|
232 {
|
|
|
233 int idx = hash%set.size;
|
|
|
234 cpHashSetBin *bin = set.table[idx];
|
|
|
235 while(bin && !set.eql(ptr, bin.elt))
|
|
|
236 bin = bin.next;
|
|
|
237
|
|
|
238 return (bin ? bin.elt : set.default_value);
|
|
|
239 }
|
|
|
240
|
|
|
241 void
|
|
|
242 cpHashSetEach(cpHashSet *set, cpHashSetIterFunc func, void *data)
|
|
|
243 {
|
|
|
244 for(int i=0; i<set.size; i++){
|
|
|
245 cpHashSetBin *bin = set.table[i];
|
|
|
246 while(bin){
|
|
|
247 cpHashSetBin *next = bin.next;
|
|
|
248 func(bin.elt, data);
|
|
|
249 bin = next;
|
|
|
250 }
|
|
|
251 }
|
|
|
252 }
|
|
|
253
|
|
|
254 void
|
|
|
255 cpHashSetFilter(cpHashSet *set, cpHashSetFilterFunc func, void *data)
|
|
|
256 {
|
|
|
257 // Iterate over all the chains.
|
|
|
258 for(int i=0; i<set.size; i++){
|
|
|
259 // The rest works similarly to cpHashSetRemove() above.
|
|
|
260 cpHashSetBin **prev_ptr = &set.table[i];
|
|
|
261 cpHashSetBin *bin = set.table[i];
|
|
|
262 while(bin){
|
|
|
263 cpHashSetBin *next = bin.next;
|
|
|
264
|
|
|
265 if(func(bin.elt, data)){
|
|
|
266 prev_ptr = &bin.next;
|
|
|
267 } else {
|
|
|
268 (*prev_ptr) = next;
|
|
|
269
|
|
|
270 set.entries--;
|
|
|
271 recycleBin(set, bin);
|
|
|
272 }
|
|
|
273
|
|
|
274 bin = next;
|
|
|
275 }
|
|
|
276 }
|
|
|
277 }
|
