Concord - C Discord API library
A Discord API wrapper library written in C
chash.h
Go to the documentation of this file.
1/* Copyright 2022 Cogmasters */
2/*
3 * C-Ware License
4 *
5 * Copyright (c) 2022, C-Ware
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright notice, this
12 * list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright notice,
15 * this list of conditions and the following disclaimer in the documentation
16 * and/or other materials provided with the distribution.
17 *
18 * 3. Redistributions of modified source code must append a copyright notice in
19 * the form of 'Copyright <YEAR> <NAME>' to each modified source file's
20 * copyright notice, and the standalone license file if one exists.
21 *
22 * A 'redistribution' can be constituted as any version of the original source
23 * code material that is intended to comprise some other derivative work of
24 * this code. A fork created for the purpose of contributing to any version of
25 * the source does not constitute a truly 'derivative work' and does not require
26 * listing.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
29 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
31 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
34 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
35 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
36 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38*/
39
40/* Modified by Lucas Müller (muller.lucas@hotmail.com), 16 May 2022
41 * - add __chash_init() and __chash_free() as a non-malloc option */
42
43#ifndef CWARE_LIBCHASH_H
44#define CWARE_LIBCHASH_H
45
46#define CWARE_LIBCHASH_VERSION "x.0.0"
47
48/* How big heap-allocated hashtables are by default */
49#ifndef CHASH_INITIAL_SIZE
50#define CHASH_INITIAL_SIZE 10
51#elif CHASH_INITIAL_SIZE <= 0
52 "chash_init: default length must be greater than 0"
53#endif
54
55/* Calculates the next size of the hashtable. */
56#ifndef CHASH_RESIZE
57#define CHASH_RESIZE(size) \
58 ((size) * 1.3)
59#endif
60
61/* The threshold that, when passed, will cause a resize */
62#ifndef CHASH_LOAD_THRESHOLD
63#define CHASH_LOAD_THRESHOLD 0.8
64#endif
65
66/* The type that is used for counters; useful for aligning hashtable
67 * length and capacity fields so type casting warnings do not appear */
68#ifndef CHASH_COUNTER_TYPE
69#define CHASH_COUNTER_TYPE int
70#endif
71
72/* The name of the key field */
73#ifndef CHASH_KEY_FIELD
74#define CHASH_KEY_FIELD key
75#endif
76
77/* The name of the value field */
78#ifndef CHASH_VALUE_FIELD
79#define CHASH_VALUE_FIELD value
80#endif
81
82/* The name of the state field */
83#ifndef CHASH_STATE_FIELD
84#define CHASH_STATE_FIELD state
85#endif
86
87/* The name of the buckets field */
88#ifndef CHASH_BUCKETS_FIELD
89#define CHASH_BUCKETS_FIELD buckets
90#endif
91
92/* The name of the length field */
93#ifndef CHASH_LENGTH_FIELD
94#define CHASH_LENGTH_FIELD length
95#endif
96
97/* The name of the capacity field */
98#ifndef CHASH_CAPACITY_FIELD
99#define CHASH_CAPACITY_FIELD capacity
100#endif
101
102/* State enums */
103#define CHASH_UNFILLED 0
104#define CHASH_FILLED 1
105#define CHASH_TOMBSTONE 2
106
107/* Built-ins */
108
109#define chash_string_hash(key, hash) \
110 5031; \
111 do { \
112 int __CHASH_HINDEX = 0; \
113 \
114 for(__CHASH_HINDEX = 0; (key)[__CHASH_HINDEX] != '\0'; \
115 __CHASH_HINDEX++) { \
116 (hash) = (((hash) << 1) + (hash)) + (key)[__CHASH_HINDEX]; \
117 } \
118 } while(0)
119
120#define chash_string_compare(cmp_a, cmp_b) \
121 (strcmp((cmp_a), (cmp_b)) == 0)
122
123#define chash_default_init(bucket, _key, _value) \
124 (bucket).CHASH_KEY_FIELD = (_key); \
125 (bucket).CHASH_VALUE_FIELD = _value
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146/* utility macros */
147
148#define __chash_abs(x) \
149 ((x) < 0 ? (x) * - 1 : (x))
150
151#define __chash_hash(mod, _key, namespace) \
152 __CHASH_HASH = namespace ## _HASH((_key), __CHASH_HASH); \
153 __CHASH_HASH = __CHASH_HASH % (mod); \
154 __CHASH_HASH = __chash_abs(__CHASH_HASH);
155
156#define __chash_probe(hashtable, _key, namespace) \
157 while(__CHASH_INDEX < (hashtable)->CHASH_CAPACITY_FIELD) { \
158 if((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD == \
159 CHASH_UNFILLED) \
160 break; \
161 \
162 if((namespace ## _COMPARE((_key), \
163 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_KEY_FIELD)) == 1) { \
164 \
165 __CHASH_INDEX = -1; \
166 break; \
167 } \
168 \
169 __CHASH_HASH = (__CHASH_HASH + 1) % (hashtable)->CHASH_CAPACITY_FIELD; \
170 __CHASH_INDEX++; \
171 } \
172
173#define __chash_probe_to_unfilled(mod, _key, buffer, namespace) \
174 while(1) { \
175 if(buffer[__CHASH_HASH].CHASH_STATE_FIELD != CHASH_FILLED) \
176 break; \
177 \
178 if((namespace ## _COMPARE((_key), buffer[__CHASH_HASH].CHASH_KEY_FIELD)) \
179 == 1) \
180 break; \
181 \
182 __CHASH_HASH = (__CHASH_HASH + 1) % mod; \
183 } \
184
185#define __chash_resize(hashtable, namespace) \
186do { \
187 CHASH_COUNTER_TYPE __CHASH_INDEX = 0; \
188 namespace ## _BUCKET *__CHASH_BUCKETS = NULL; \
189 CHASH_COUNTER_TYPE __CHASH_NEXT_SIZE = (CHASH_COUNTER_TYPE) \
190 CHASH_RESIZE((hashtable)->CHASH_CAPACITY_FIELD); \
191 \
192 if((namespace ## _HEAP) == 0) { \
193 if((hashtable)->CHASH_LENGTH_FIELD != \
194 (hashtable)->CHASH_CAPACITY_FIELD) { \
195 break; \
196 } \
197 \
198 fprintf(stderr, "__chash_resize: hashtable is full. could not resize" \
199 " (%s:%i)\n", __FILE__, __LINE__); \
200 abort(); \
201 } \
202 \
203 if((double) (hashtable)->CHASH_LENGTH_FIELD / \
204 (double) (hashtable)->CHASH_CAPACITY_FIELD < CHASH_LOAD_THRESHOLD) \
205 break; \
206 \
207 __CHASH_BUCKETS = malloc((size_t) (__CHASH_NEXT_SIZE \
208 * ((CHASH_COUNTER_TYPE) \
209 sizeof(namespace ## _BUCKET)))); \
210 memset(__CHASH_BUCKETS, 0, ((size_t) (__CHASH_NEXT_SIZE \
211 * ((CHASH_COUNTER_TYPE) \
212 sizeof(namespace ## _BUCKET))))); \
213 \
214 for(__CHASH_INDEX = 0; __CHASH_INDEX < (hashtable)->CHASH_CAPACITY_FIELD; \
215 __CHASH_INDEX++) { \
216 namespace ## _BUCKET __CHASH_NEW_KEY_BUCKET; \
217 memset(&__CHASH_NEW_KEY_BUCKET, 0, sizeof(namespace ## _BUCKET)); \
218 namespace ## _INIT(__CHASH_NEW_KEY_BUCKET, \
219 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_INDEX].CHASH_KEY_FIELD, \
220 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_INDEX].CHASH_VALUE_FIELD); \
221 \
222 if((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_INDEX].CHASH_STATE_FIELD \
223 != CHASH_FILLED) \
224 continue; \
225 \
226 __chash_hash(__CHASH_NEXT_SIZE, __CHASH_NEW_KEY_BUCKET.CHASH_KEY_FIELD, \
227 namespace); \
228 __chash_probe_to_unfilled(__CHASH_NEXT_SIZE, \
229 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_INDEX].CHASH_KEY_FIELD, \
230 __CHASH_BUCKETS, namespace) \
231 \
232 __CHASH_BUCKETS[__CHASH_HASH] = __CHASH_NEW_KEY_BUCKET; \
233 __CHASH_BUCKETS[__CHASH_HASH].CHASH_STATE_FIELD = CHASH_FILLED; \
234 __CHASH_HASH = 0; \
235 } \
236 \
237 free((hashtable)->CHASH_BUCKETS_FIELD); \
238 (hashtable)->CHASH_BUCKETS_FIELD = __CHASH_BUCKETS; \
239 (hashtable)->CHASH_CAPACITY_FIELD = __CHASH_NEXT_SIZE; \
240 __CHASH_HASH = 0; \
241} while(0)
242
243#define __chash_assert_nonnull(func, ptr) \
244do { \
245 if((ptr) == NULL) { \
246 fprintf(stderr, #func ": " #ptr " cannot be null (%s:%i)\n", \
247 __FILE__, __LINE__); \
248 abort(); \
249 } \
250} while(0)
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267/* operations */
268#define __chash_init(hashtable, namespace) \
269 (hashtable)->CHASH_LENGTH_FIELD = 0; \
270 (hashtable)->CHASH_CAPACITY_FIELD = CHASH_INITIAL_SIZE; \
271 (hashtable)->CHASH_BUCKETS_FIELD = malloc(CHASH_INITIAL_SIZE \
272 * sizeof(*((hashtable)->CHASH_BUCKETS_FIELD))); \
273 memset((hashtable)->CHASH_BUCKETS_FIELD, 0, \
274 sizeof(*((hashtable)->CHASH_BUCKETS_FIELD)) * CHASH_INITIAL_SIZE)
275
276#define chash_init(hashtable, namespace) \
277 NULL; \
278 \
279 (hashtable) = malloc(sizeof((*(hashtable)))); \
280 __chash_init(hashtable, namespace)
281
282#define chash_init_stack(hashtable, buffer, _length, namespace) \
283 (*(hashtable)); \
284 \
285 if((_length) <= 0) { \
286 fprintf(stderr, "chash_init_stack: hashtable cannot have a maximum " \
287 "length of 0 or less (%s:%i)\n", __FILE__, __LINE__); \
288 abort(); \
289 } \
290 \
291 __chash_assert_nonnull(chash_init_stack, buffer); \
292 \
293 (hashtable)->CHASH_LENGTH_FIELD = 0; \
294 (hashtable)->CHASH_CAPACITY_FIELD = _length; \
295 (hashtable)->CHASH_BUCKETS_FIELD = buffer
296
297#define chash_assign(hashtable, _key, _value, namespace) \
298do { \
299 long __CHASH_HASH = 0; \
300 namespace ## _BUCKET __CHASH_KEY_BUCKET; \
301 memset(&__CHASH_KEY_BUCKET, 0, sizeof(namespace ## _BUCKET)); \
302 namespace ## _INIT(__CHASH_KEY_BUCKET, _key, _value); \
303 \
304 __chash_assert_nonnull(chash_assign, hashtable); \
305 __chash_assert_nonnull(chash_assign, (hashtable)->CHASH_BUCKETS_FIELD); \
306 __chash_resize(hashtable, namespace); \
307 __chash_hash((hashtable)->CHASH_CAPACITY_FIELD, _key, namespace); \
308 __chash_probe_to_unfilled((hashtable)->CHASH_CAPACITY_FIELD, \
309 (_key), (hashtable)->CHASH_BUCKETS_FIELD, namespace) \
310 \
311 if((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD == \
312 CHASH_FILLED) { \
313 namespace ## _FREE_VALUE( \
314 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_VALUE_FIELD); \
315 } else { \
316 (hashtable)->CHASH_LENGTH_FIELD++; \
317 } \
318 \
319 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH] = __CHASH_KEY_BUCKET; \
320 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD = \
321 CHASH_FILLED; \
322} while(0)
323
324#define chash_lookup(hashtable, _key, storage, namespace) \
325storage; \
326 \
327do { \
328 int __CHASH_INDEX = 0; \
329 long __CHASH_HASH = 0; \
330 namespace ## _BUCKET __CHASH_KEY_BUCKET; \
331 memset(&__CHASH_KEY_BUCKET, 0, sizeof(namespace ## _BUCKET)); \
332 namespace ## _INIT(__CHASH_KEY_BUCKET, _key, \
333 __CHASH_KEY_BUCKET.CHASH_VALUE_FIELD); \
334 \
335 (void) __CHASH_KEY_BUCKET; \
336 \
337 __chash_assert_nonnull(chash_lookup, hashtable); \
338 __chash_assert_nonnull(chash_lookup, (hashtable)->CHASH_BUCKETS_FIELD); \
339 __chash_hash((hashtable)->CHASH_CAPACITY_FIELD, _key, namespace); \
340 __chash_probe(hashtable, _key, namespace) \
341 \
342 if(((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD != \
343 CHASH_FILLED) || __CHASH_INDEX != -1) { \
344 fprintf(stderr, "chash_lookup: failed to find key in hashtable (%s:%i)" \
345 "\n", __FILE__, __LINE__); \
346 abort(); \
347 } \
348 \
349 storage = (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_VALUE_FIELD; \
350} while(0)
351
352#define chash_delete(hashtable, _key, namespace) \
353do { \
354 int __CHASH_INDEX = 0; \
355 long __CHASH_HASH = 0; \
356 \
357 __chash_assert_nonnull(chash_delete, hashtable); \
358 __chash_assert_nonnull(chash_delete, (hashtable)->CHASH_BUCKETS_FIELD); \
359 __chash_hash((hashtable)->CHASH_CAPACITY_FIELD, _key, namespace); \
360 __chash_probe(hashtable, _key, namespace) \
361 \
362 if(((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD != \
363 CHASH_FILLED) || __CHASH_INDEX != -1) { \
364 fprintf(stderr, "chash_delete: failed to find key in hashtable (%s:%i)" \
365 "\n", __FILE__, __LINE__); \
366 abort(); \
367 } \
368 \
369 namespace ## _FREE_KEY((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH] \
370 .CHASH_KEY_FIELD); \
371 namespace ## _FREE_VALUE( \
372 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_VALUE_FIELD); \
373 (hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD = \
374 CHASH_TOMBSTONE; \
375 (hashtable)->CHASH_LENGTH_FIELD--; \
376} while(0)
377
378#define chash_contains(hashtable, _key, storage, namespace) \
3791; \
380 \
381do { \
382 int __CHASH_INDEX = 0; \
383 long __CHASH_HASH = 0; \
384 \
385 __chash_assert_nonnull(chash_contents, hashtable); \
386 __chash_assert_nonnull(chash_contents, (hashtable)->CHASH_BUCKETS_FIELD); \
387 __chash_hash((hashtable)->CHASH_CAPACITY_FIELD, _key, namespace); \
388 __chash_probe(hashtable, _key, namespace) \
389 \
390 if(((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD != \
391 CHASH_FILLED) || __CHASH_INDEX != -1) { \
392 storage = 0; \
393 } \
394} while(0)
395
396#define chash_lookup_bucket(hashtable, _key, storage, namespace) \
397storage; \
398 \
399do { \
400 CHASH_COUNTER_TYPE __CHASH_INDEX = 0; \
401 long __CHASH_HASH = 0; \
402 namespace ## _BUCKET __CHASH_KEY_BUCKET; \
403 memset(&__CHASH_KEY_BUCKET, 0, sizeof(namespace ## _BUCKET)); \
404 namespace ## _INIT(__CHASH_KEY_BUCKET, _key, \
405 __CHASH_KEY_BUCKET.CHASH_VALUE_FIELD); \
406 \
407 (void) __CHASH_KEY_BUCKET; \
408 \
409 __chash_assert_nonnull(chash_lookup_bucket, hashtable); \
410 __chash_assert_nonnull(chash_lookup_bucket, \
411 (hashtable)->CHASH_BUCKETS_FIELD); \
412 __chash_hash((hashtable)->CHASH_CAPACITY_FIELD, _key, namespace); \
413 __chash_probe(hashtable, _key, namespace) \
414 \
415 if(((hashtable)->CHASH_BUCKETS_FIELD[__CHASH_HASH].CHASH_STATE_FIELD != \
416 CHASH_FILLED) || __CHASH_INDEX != -1) { \
417 fprintf(stderr, "chash_lookup_bucket: failed to find key in hashtable" \
418 "(%s:%i) \n", __FILE__, __LINE__); \
419 abort(); \
420 } \
421 \
422 storage = ((hashtable)->CHASH_BUCKETS_FIELD + __CHASH_HASH); \
423} while(0)
424
425#define __chash_free(hashtable, namespace) \
426do { \
427 __chash_assert_nonnull(__chash_free, hashtable); \
428 __chash_assert_nonnull(__chash_free, (hashtable)->CHASH_BUCKETS_FIELD); \
429 (hashtable)->CHASH_CAPACITY_FIELD--; \
430 \
431 while((hashtable)->CHASH_CAPACITY_FIELD != -1) { \
432 if((hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
433 .CHASH_STATE_FIELD != CHASH_FILLED) { \
434 (hashtable)->CHASH_CAPACITY_FIELD--; \
435 continue; \
436 } \
437 \
438 namespace ##_FREE_KEY( \
439 (hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
440 .CHASH_KEY_FIELD); \
441 namespace ##_FREE_VALUE( \
442 (hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
443 .CHASH_VALUE_FIELD); \
444 (hashtable)->CHASH_CAPACITY_FIELD--; \
445 (hashtable)->CHASH_LENGTH_FIELD--; \
446 } \
447 \
448 if((namespace ## _HEAP) == 1) { \
449 free((hashtable)->CHASH_BUCKETS_FIELD); \
450 } \
451} while(0)
452
453#define chash_free(hashtable, namespace) \
454do { \
455 __chash_assert_nonnull(chash_free, hashtable); \
456 __chash_assert_nonnull(chash_free, (hashtable)->CHASH_BUCKETS_FIELD); \
457 (hashtable)->CHASH_CAPACITY_FIELD--; \
458 \
459 while((hashtable)->CHASH_CAPACITY_FIELD != -1) { \
460 if((hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
461 .CHASH_STATE_FIELD != CHASH_FILLED) { \
462 (hashtable)->CHASH_CAPACITY_FIELD--; \
463 continue; \
464 } \
465 \
466 namespace ##_FREE_KEY( \
467 (hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
468 .CHASH_KEY_FIELD); \
469 namespace ##_FREE_VALUE( \
470 (hashtable)->CHASH_BUCKETS_FIELD[(hashtable)->CHASH_CAPACITY_FIELD] \
471 .CHASH_VALUE_FIELD); \
472 (hashtable)->CHASH_CAPACITY_FIELD--; \
473 (hashtable)->CHASH_LENGTH_FIELD--; \
474 } \
475 \
476 if((namespace ## _HEAP) == 1) { \
477 free((hashtable)->CHASH_BUCKETS_FIELD); \
478 free((hashtable)); \
479 } \
480} while(0)
481
482#define chash_is_full(hashtable, namespace) \
483 (((hashtable)->CHASH_LENGTH_FIELD) == ((hashtable)->CHASH_CAPACITY_FIELD))
484
485
486
487
488
489
490
491
492
493/* Iterator logic */
494#define chash_iter(hashtable, index, _key, _value) \
495 for((index) = 0, (_key) = (hashtable)->CHASH_BUCKETS_FIELD[index]. \
496 CHASH_KEY_FIELD, \
497 (_value) = (hashtable)->CHASH_BUCKETS_FIELD[index].CHASH_VALUE_FIELD; \
498 (index) < (hashtable)->CHASH_CAPACITY_FIELD; \
499 (index) = ((index) < (hashtable)->CHASH_CAPACITY_FIELD) \
500 ? ((index) + 1) : index, \
501 (_key) = (hashtable)->CHASH_BUCKETS_FIELD[index].CHASH_KEY_FIELD, \
502 (_value) = (hashtable)->CHASH_BUCKETS_FIELD[index].CHASH_VALUE_FIELD, \
503 (index) = (hashtable)->CHASH_CAPACITY_FIELD)
504
505#define chash_skip(hashtable, index) \
506 if((hashtable)->CHASH_BUCKETS_FIELD[index]. \
507 CHASH_STATE_FIELD != CHASH_FILLED) \
508 continue;
509
510#endif