qLibc

qhasharr.c
Go to the documentation of this file.
1/******************************************************************************
2 * qLibc
3 *
4 * Copyright (c) 2010-2015 Seungyoung Kim.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 *****************************************************************************/
28
29/**
30 * @file qhasharr.c Static(array) hash-table implementation.
31 *
32 * qhasharr implements a hash-table which maps keys to values and stores into
33 * fixed size static memory like shared-memory and memory-mapped file.
34 * The creator qhasharr() initializes static memory to makes small slots in it.
35 * The default slot size factors are defined in Q_HASHARR_NAMESIZE and
36 * Q_HASHARR_DATASIZE. And they are applied at compile time.
37 *
38 * The value part of an element will be stored across several slots if it's size
39 * exceeds the slot size. But the key part of an element will be truncated if
40 * the size exceeds and it's length and more complex MD5 hash value will be
41 * stored with the key. So to look up a particular key, first we find an element
42 * which has same hash value. If the key was not truncated, we just do key
43 * comparison. But if the key was truncated because it's length exceeds, we do
44 * both md5 and key comparison(only stored size) to verify that the key is same.
45 * So please be aware of that, theoretically there is a possibility we pick
46 * wrong element in case a key exceeds the limit, has same length and MD5 hash
47 * with lookup key. But this possibility is very low and almost zero in practice.
48 *
49 * qhasharr hash-table does not provide thread-safe handling intentionally and
50 * let users determine whether to provide locking mechanism or not, depending on
51 * the use cases. When there's race conditions expected, you should provide a
52 * shared resource control using mutex or semaphore to make sure data gets
53 * updated by one instance at a time.
54 *
55 * @code
56 * [Data Structure Diagram]
57 *
58 * +--[Static Flat Memory Area]-----------------------------------------------+
59 * | +-[Header]---------+ +-[Slot 0]---+ +-[Slot 1]---+ +-[Slot N]---+ |
60 * | |Private table data| |KEY A|DATA A| |KEY B|DATA B| .... |KEY N|DATA N| |
61 * | +------------------+ +------------+ +------------+ +------------+ |
62 * +--------------------------------------------------------------------------+
63 *
64 * Below diagram shows how a big value is stored.
65 * +--[Static Flat Memory Area------------------------------------------------+
66 * | +--------+ +-[Slot 0]---+ +-[Slot 1]---+ +-[Slot 2]---+ +-[Slot 3]-----+ |
67 * | |TBL INFO| |KEY A|DATA A| |DATA A cont.| |KEY B|DATA B| |DATA A cont. | |
68 * | +--------+ +------------+ +------------+ +------------+ +--------------+ |
69 * | ^~~link~~^ ^~~~~~~~~~link~~~~~~~~~^ |
70 * +--------------------------------------------------------------------------+
71 * @endcode
72 *
73 * @code
74 * // initialize hash-table.
75 * char memory[1000 * 10];
76 * qhasharr_t *tbl = qhasharr(memory, sizeof(memory));
77 * if(tbl == NULL) return;
78 *
79 * // insert elements (key duplication does not allowed)
80 * tbl->putstr(tbl, "e1", "a");
81 * tbl->putstr(tbl, "e2", "b");
82 * tbl->putstr(tbl, "e3", "c");
83 *
84 * // debug print out
85 * tbl->debug(tbl, stdout);
86 *
87 * char *e2 = tbl->getstr(tbl, "e2");
88 * if(e2 != NULL) {
89 * printf("getstr('e2') : %s\n", e2);
90 * free(e2);
91 * }
92 *
93 * // Release reference object.
94 * tbl->free(tbl);
95 * @endcode
96 *
97 * An example for using hash table over shared memory.
98 *
99 * @code
100 * [CREATOR SIDE]
101 * int maxslots = 1000;
102 * int memsize = qhasharr_calculate_memsize(maxslots);
103 *
104 * // create shared memory
105 * int shmid = qshm_init("/tmp/some_id_file", 'q', memsize, true);
106 * if(shmid < 0) return -1; // creation failed
107 * void *memory = qshm_get(shmid);
108 *
109 * // initialize hash-table
110 * qhasharr_t *tbl = qhasharr(memory, memsize);
111 * if(hasharr == NULL) return -1;
112 *
113 * (...your codes with your own locking mechanism...)
114 *
115 * // Release reference object
116 * tbl->free(tbl);
117 *
118 * // destroy shared memory
119 * qshm_free(shmid);
120 *
121 * [USER SIDE]
122 * int shmid = qshm_getid("/tmp/some_id_file", 'q');
123 *
124 * // get shared memory
125 * void *memory = qshm_get(shmid);
126 *
127 * // map existing memory into table
128 * qhasharr_t *tbl = qhasharr(memory, 0);
129 *
130 * (...your codes with your own locking mechanism...)
131 *
132 * // Release reference object
133 * tbl->free(tbl);
134 * @endcode
135 */
136
137#include <stdio.h>
138#include <stdlib.h>
139#include <stdbool.h>
140#include <stdint.h>
141#include <inttypes.h>
142#include <stdarg.h>
143#include <string.h>
144#include <errno.h>
145#include <assert.h>
146#include "qinternal.h"
147#include "utilities/qhash.h"
148#include "containers/qhasharr.h"
149
150#define COLLISION_MARK (-1)
151#define EXTBLOCK_MARK (-2)
152
153#ifndef _DOXYGEN_SKIP
154
155 static qhasharr_slot_t* get_slots(qhasharr_t *tbl);
156 static int find_avail(qhasharr_t *tbl, int startidx);
157 static int get_idx(qhasharr_t *tbl, const void *name, size_t namesize,
158 uint32_t hash);
159 static void *get_data(qhasharr_t *tbl, int idx, size_t *size);
160 static bool put_data(qhasharr_t *tbl, int idx, uint32_t hash, const void *name,
161 size_t namesize, const void *data, size_t datasize,
162 int count);
163 static bool copy_slot(qhasharr_t *tbl, int idx1, int idx2);
164 static bool remove_slot(qhasharr_t *tbl, int idx);
165 static bool remove_data(qhasharr_t *tbl, int idx);
166
167#endif
168
169/**
170 * Get how much memory is needed for N slots.
171 *
172 * @param max a number of maximum internal slots
173 *
174 * @return memory size needed
175 *
176 * @note
177 * This can be used for calculating minimum memory size for N slots.
178 */
179 size_t qhasharr_calculate_memsize(int max) {
180 size_t memsize = sizeof(qhasharr_data_t)
181 + (sizeof(qhasharr_slot_t) * (max));
182 return memsize;
183}
184
185/**
186 * Initialize static hash table
187 *
188 * @param memory a pointer of data memory.
189 * @param memsize a size of data memory, 0 for using existing data.
190 *
191 * @return qhasharr_t container pointer, otherwise returns NULL.
192 * @retval errno will be set in error condition.
193 * - EINVAL : Assigned memory is too small. It must bigger enough to allocate
194 * at least 1 slot.
195 *
196 * @code
197 * // initialize hash-table with 100 slots.
198 * // A single element can take several slots.
199 * char memory[112 * 100];
200 *
201 * // Initialize new table.
202 * qhasharr_t *tbl = qhasharr(memory, sizeof(memory));
203 *
204 * // Use existing table.
205 * qhasharr_t *tbl2 = qhasharr(memory, 0);
206 * @endcode
207 */
208qhasharr_t *qhasharr(void *memory, size_t memsize) {
209 // Structure memory.
210 qhasharr_data_t *tbldata = (qhasharr_data_t *) memory;
211
212 // Initialize data if memsize is set or use existing data.
213 if (memsize > 0) {
214 // calculate max
215 int maxslots = (memsize - sizeof(qhasharr_data_t))
216 / sizeof(qhasharr_slot_t);
217 if (maxslots < 1 || memsize <= sizeof(qhasharr_t)) {
218 errno = EINVAL;
219 return NULL;
220 }
221
222 // Set memory.
223 memset((void *) tbldata, 0, memsize);
224 tbldata->maxslots = maxslots;
225 tbldata->usedslots = 0;
226 tbldata->num = 0;
227 }
228
229 // Create the table object.
230 qhasharr_t *tbl = (qhasharr_t *) malloc(sizeof(qhasharr_t));
231 if (tbl == NULL) {
232 errno = ENOMEM;
233 return NULL;
234 }
235 memset((void *) tbl, 0, sizeof(qhasharr_t));
236
237 // assign methods
238 tbl->put = qhasharr_put;
239 tbl->putstr = qhasharr_putstr;
240 tbl->putstrf = qhasharr_putstrf;
241 tbl->put_by_obj = qhasharr_put_by_obj;
242
243 tbl->get = qhasharr_get;
244 tbl->getstr = qhasharr_getstr;
245 tbl->get_by_obj = qhasharr_get_by_obj;
246
247 tbl->remove = qhasharr_remove;
248 tbl->remove_by_obj = qhasharr_remove_by_obj;
249 tbl->remove_by_idx = qhasharr_remove_by_idx;
250
251 tbl->getnext = qhasharr_getnext;
252
253 tbl->size = qhasharr_size;
254 tbl->clear = qhasharr_clear;
255 tbl->debug = qhasharr_debug;
256
257 tbl->free = qhasharr_free;
258
259 tbl->data = tbldata;
260
261 return tbl;
262}
263
264/**
265 * qhasharr->put(): Put an object into this table.
266 *
267 * @param tbl qhasharr_t container pointer.
268 * @param key key string
269 * @param value value object data
270 * @param size size of value
271 *
272 * @return true if successful, otherwise returns false
273 * @retval errno will be set in error condition.
274 * - ENOBUFS : Table doesn't have enough space to store the object.
275 * - EINVAL : Invalid argument.
276 * - EFAULT : Unexpected error. Data structure is not constant.
277 */
278 bool qhasharr_put(qhasharr_t *tbl, const char *name, const void *data,
279 size_t datasize) {
280 return qhasharr_put_by_obj(tbl, name, (name) ? strlen(name) + 1 : 0, data,
281 datasize);
282}
283
284/**
285 * qhasharr->putstr(): Put a string into this table
286 *
287 * @param tbl qhasharr_t container pointer.
288 * @param name key string.
289 * @param data value string.
290 *
291 * @return true if successful, otherwise returns false
292 * @retval errno will be set in error condition.
293 * - ENOBUFS : Table doesn't have enough space to store the object.
294 * - EINVAL : Invalid argument.
295 * - EFAULT : Unexpected error. Data structure is not constant.
296 */
297 bool qhasharr_putstr(qhasharr_t *tbl, const char *name, const char *data) {
298 return qhasharr_put_by_obj(tbl, name, (name) ? strlen(name) + 1 : 0,
299 data, (data) ? strlen(data) + 1 : 0);
300}
301
302/**
303 * qhasharr->putstrf(): Put a formatted string into this table.
304 *
305 * @param tbl qhasharr_t container pointer.
306 * @param name key string
307 * @param format formatted string data.
308 *
309 * @return true if successful, otherwise returns false.
310 * @retval errno will be set in error condition.
311 * - ENOBUFS : Table doesn't have enough space to store the object.
312 * - ENOMEM : System memory allocation failure.
313 * - EINVAL : Invalid argument.
314 * - EFAULT : Unexpected error. Data structure is not constant.
315 */
316 bool qhasharr_putstrf(qhasharr_t *tbl, const char *name, const char *format, ...) {
317 char *str;
318 DYNAMIC_VSPRINTF(str, format);
319 if (str == NULL) {
320 errno = ENOMEM;
321 return false;
322 }
323
324 bool ret = qhasharr_putstr(tbl, name, str);
325 free(str);
326 return ret;
327}
328
329/**
330 * qhasharr->put_by_obj(): ut an object into this table by key object.
331 *
332 * @param tbl qhasharr_t container pointer.
333 * @param name key data
334 * @param namesize size of key
335 * @param data data
336 * @param datasize size of data
337 *
338 * @return true if successful, otherwise returns false
339 * @retval errno will be set in error condition.
340 * - ENOBUFS : Table doesn't have enough space to store the object.
341 * - EINVAL : Invalid argument.
342 * - EFAULT : Unexpected error. Data structure is not constant.
343 */
344 bool qhasharr_put_by_obj(qhasharr_t *tbl, const void *name, size_t namesize,
345 const void *data, size_t datasize) {
346 if (tbl == NULL || name == NULL || namesize == 0 || data == NULL
347 || datasize == 0) {
348 errno = EINVAL;
349 return false;
350 }
351
352 qhasharr_data_t *tbldata = tbl->data;
353 qhasharr_slot_t *tblslots = get_slots(tbl);
354
355 // check full
356 if (tbldata->usedslots >= tbldata->maxslots) {
357 errno = ENOBUFS;
358 return false;
359 }
360
361 // get hash integer
362 uint32_t hash = qhashmurmur3_32(name, namesize) % tbldata->maxslots;
363
364 // check, is slot empty
365 if (tblslots[hash].count == 0) { // empty slot
366 // put data
367 if (put_data(tbl, hash, hash, name, namesize, data, datasize,
368 1) == false) {
369 return false;
370 }
371 } else if (tblslots[hash].count > 0) { // same key or hash collision
372 // check same key;
373 int idx = get_idx(tbl, name, namesize, hash);
374 if (idx >= 0) { // same key
375 // remove and recall
376 qhasharr_remove_by_idx(tbl, idx);
377 return qhasharr_put_by_obj(tbl, name, namesize, data, datasize);
378 } else { // no same key but hash collision
379 // find empty slot
380 int idx = find_avail(tbl, hash);
381 if (idx < 0) {
382 errno = ENOBUFS;
383 return false;
384 }
385
386 // put data. -1 is used for collision resolution (idx != hash);
387 if (put_data(tbl, idx, hash, name, namesize, data, datasize,
388 COLLISION_MARK) == false) {
389 return false;
390 }
391
392 // increase counter from leading slot
393 tblslots[hash].count++;
394 }
395 } else {
396 // collision key or extended block
397
398 // find empty slot
399 int idx = find_avail(tbl, hash + 1);
400 if (idx < 0) {
401 errno = ENOBUFS;
402 return false;
403 }
404
405 // move the slot
406 copy_slot(tbl, idx, hash);
407 remove_slot(tbl, hash);
408
409 // adjust the link chain
410 if (tblslots[idx].link != -1) {
411 tblslots[tblslots[idx].link].hash = idx;
412 }
413 if (tblslots[idx].count == EXTBLOCK_MARK) {
414 tblslots[tblslots[idx].hash].link = idx;
415 }
416
417 // store data
418 if (put_data(tbl, hash, hash, name, namesize, data, datasize,
419 1) == false) {
420 return false;
421 }
422 }
423
424 return true;
425}
426
427/**
428 * qhasharr->get(): Get an object from this table
429 *
430 * @param tbl qhasharr_t container pointer.
431 * @param name key string
432 * @param datasize if not NULL, returned object size will be stored
433 *
434 * @return malloced object pointer if successful, otherwise(not found)
435 * returns NULL
436 * @retval errno will be set in error condition.
437 * - ENOENT : No such key found.
438 * - EINVAL : Invalid argument.
439 * - ENOMEM : Memory allocation failed.
440 *
441 * @note
442 * returned object must be freed after done using.
443 */
444 void *qhasharr_get(qhasharr_t *tbl, const char *name, size_t *datasize) {
445 return qhasharr_get_by_obj(tbl, name, (name) ? strlen(name) + 1 : 0, datasize);
446}
447
448/**
449 * qhasharr->getstr(): Finds an object with given name and returns as
450 * string type.
451 *
452 * @param tbl qhasharr_t container pointer.
453 * @param name key string
454 *
455 * @return string pointer if successful, otherwise(not found) returns NULL
456 * @retval errno will be set in error condition.
457 * - ENOENT : No such key found.
458 * - EINVAL : Invalid argument.
459 * - ENOMEM : Memory allocation failed.
460 *
461 * @note
462 * returned object must be freed after done using.
463 */
464 char *qhasharr_getstr(qhasharr_t *tbl, const char *name) {
465 return (char *) qhasharr_get(tbl, name, NULL);
466}
467
468/**
469 * qhasharr->get_by_object(): Get an object from this table by key object
470 *
471 * @param tbl qhasharr_t container pointer.
472 * @param name key data
473 * @param namesize size of key
474 * @param datasize if not NULL, returned object size will be stored
475 *
476 * @return malloced object pointer if successful, otherwise(not found)
477 * returns NULL
478 * @retval errno will be set in error condition.
479 * - ENOENT : No such key found.
480 * - EINVAL : Invalid argument.
481 * - ENOMEM : Memory allocation failed.
482 *
483 * @note
484 * returned object must be freed after done using.
485 */
486 void *qhasharr_get_by_obj(qhasharr_t *tbl, const void *name, size_t namesize,
487 size_t *datasize) {
488 if (tbl == NULL || name == NULL || namesize == 0) {
489 errno = EINVAL;
490 return NULL;
491 }
492
493 qhasharr_data_t *tbldata = tbl->data;
494
495 // get hash integer
496 uint32_t hash = qhashmurmur3_32(name, namesize) % tbldata->maxslots;
497 int idx = get_idx(tbl, name, namesize, hash);
498 if (idx < 0) {
499 errno = ENOENT;
500 return NULL;
501 }
502
503 return get_data(tbl, idx, datasize);
504}
505
506/**
507 * qhasharr->remove(): Remove an object from this table.
508 *
509 * @param tbl qhasharr_t container pointer.
510 * @param name key string
511 *
512 * @return true if successful, otherwise(not found) returns false
513 * @retval errno will be set in error condition.
514 * - ENOENT : No such key found.
515 * - EINVAL : Invald argument.
516 * - EFAULT : Unexpected error. Data structure is not constant.
517 */
518 bool qhasharr_remove(qhasharr_t *tbl, const char *name) {
519 return qhasharr_remove_by_obj(tbl, name, (name) ? strlen(name) + 1 : 0);
520}
521
522/**
523 * qhasharr->remove_by_obj(): Remove an object from this table by key object
524 *
525 * @param tbl qhasharr_t container pointer.
526 * @param name key data
527 * @param namesize size of key
528 *
529 * @return true if successful, otherwise(not found) returns false
530 * @retval errno will be set in error condition.
531 * - ENOENT : No such key found.
532 * - EINVAL : Invald argument.
533 * - EFAULT : Unexpected error. Data structure is not constant.
534 */
535 bool qhasharr_remove_by_obj(qhasharr_t *tbl, const char *name, size_t namesize) {
536 if (tbl == NULL || name == NULL || namesize == 0) {
537 errno = EINVAL;
538 return false;
539 }
540
541 qhasharr_data_t *tbldata = tbl->data;
542
543 // get hash integer
544 uint32_t hash = qhashmurmur3_32(name, namesize) % tbldata->maxslots;
545 int idx = get_idx(tbl, name, namesize, hash);
546 if (idx < 0) {
547 errno = ENOENT;
548 return false;
549 }
550
551 return qhasharr_remove_by_idx(tbl, idx);
552}
553
554/**
555 * qhasharr->remove_by_idx(): Remove an object from this table by index number.
556 *
557 * @param tbl qhasharr_t container pointer.
558 * @param idx slot index number
559 *
560 * @return true if successful, otherwise(not found) returns false
561 * @retval errno will be set in error condition.
562 * - ENOENT : Index is not pointing a valid object.
563 * - EINVAL : Invald argument.
564 * - EFAULT : Unexpected error. Data structure is not constant.
565 *
566 * @code
567 * int idx = 0;
568 * qhasharr_obj_t obj;
569 * while(tbl->getnext(tbl, &obj, &idx) == true) {
570 * if (condition_to_remove) {
571 * idx--; // adjust index by -1
572 * remove_by_idx(idx);
573 * }
574 * free(obj.name);
575 * free(obj.data);
576 * }
577 * @endcode
578 *
579 * @note
580 * This function is to remove an object in getnext() traversal loop without
581 * knowing the object name but index value. When key names are longer than
582 * defined size, the keys are stored with truncation with their fingerprint,
583 * so this method provides a way to remove those keys.
584 * getnext() returns actual index + 1(pointing next slot of current finding),
585 * so you need to adjust it by -1 for the valid index number. And once you
586 * remove object by this method, rewind idx by -1 before calling getnext()
587 * because collision objects can be moved back to removed index again, so
588 * by adjusting index by -1, getnext() can continue search from the removed
589 * slot index again. Please refer an example code.
590 */
591 bool qhasharr_remove_by_idx(qhasharr_t *tbl, int idx) {
592 if (idx < 0) {
593 errno = EINVAL;
594 return false;
595 }
596
597 qhasharr_data_t *tbldata = tbl->data;
598 qhasharr_slot_t *tblslots = get_slots(tbl);
599
600 if (tblslots[idx].count == 1) {
601 // just remove
602 remove_data(tbl, idx);
603 } else if (tblslots[idx].count > 1) { // leading slot and has collision
604 // find the collision key
605 int idx2;
606 for (idx2 = idx + 1;; idx2++) {
607 if (idx2 >= tbldata->maxslots)
608 idx2 = 0;
609 if (idx2 == idx) {
610 errno = EFAULT;
611 return false;
612 }
613 if (tblslots[idx2].count == COLLISION_MARK
614 && tblslots[idx2].hash == tblslots[idx].hash) {
615 break;
616 }
617 }
618
619 // move to leading slot
620 int backupcount = tblslots[idx].count;
621 remove_data(tbl, idx); // remove leading data
622 copy_slot(tbl, idx, idx2); // copy slot
623 remove_slot(tbl, idx2); // remove moved slot
624
625 tblslots[idx].count = backupcount - 1; // adjust collision counter
626 if (tblslots[idx].link != -1) {
627 tblslots[tblslots[idx].link].hash = idx;
628 }
629
630 } else if (tblslots[idx].count == COLLISION_MARK) { // collision key
631 // decrease counter from leading slot
632 if (tblslots[tblslots[idx].hash].count <= 1) {
633 errno = EFAULT;
634 return false;
635 }
636 tblslots[tblslots[idx].hash].count--;
637
638 // remove data
639 remove_data(tbl, idx);
640 } else {
641 errno = ENOENT;
642 return false;
643 }
644
645 return true;
646}
647
648/**
649 * qhasharr->getnext(): Get next element.
650 *
651 * @param tbl qhasharr_t container pointer.
652 * @param idx index pointer
653 *
654 * @return key name string if successful, otherwise(end of table) returns NULL
655 * @retval errno will be set in error condition.
656 * - ENOENT : No next element.
657 * - EINVAL : Invald argument.
658 * - ENOMEM : Memory allocation failed.
659 *
660 * @code
661 * int idx = 0;
662 * qhasharr_obj_t obj;
663 * while(tbl->getnext(tbl, &obj, &idx) == true) {
664 * printf("NAMESIZE=%zu, DATASIZE=%zu\n",
665 * obj.namesize, obj.datasize);
666 * free(obj.name); // key name
667 * free(obj.data); // value data
668 * }
669 * @endcode
670 *
671 * @note
672 * Please be aware a key name will be returned with truncated length
673 * because key name gets truncated if it doesn't fit into slot size,
674 * Q_HASHARR_NAMESIZE.
675 */
676 bool qhasharr_getnext(qhasharr_t *tbl, qhasharr_obj_t *obj, int *idx) {
677 if (tbl == NULL || obj == NULL || idx == NULL) {
678 errno = EINVAL;
679 return NULL;
680 }
681
682 qhasharr_data_t *tbldata = tbl->data;
683 qhasharr_slot_t *tblslots = get_slots(tbl);
684
685 for (; *idx < tbldata->maxslots; (*idx)++) {
686 if (tblslots[*idx].count == 0 || tblslots[*idx].count == EXTBLOCK_MARK) {
687 continue;
688 }
689
690 size_t namesize = tblslots[*idx].data.pair.namesize;
691 if (namesize > Q_HASHARR_NAMESIZE)
692 namesize = Q_HASHARR_NAMESIZE;
693
694 obj->name = malloc(namesize + 1);
695 if (obj->name == NULL) {
696 errno = ENOMEM;
697 return false;
698 }
699 memcpy(obj->name, tblslots[*idx].data.pair.name, namesize);
700 memcpy(obj->name + namesize, "", 1); // for truncated case
701 obj->namesize = namesize;
702
703 obj->data = get_data(tbl, *idx, &obj->datasize);
704 if (obj->data == NULL) {
705 free(obj->name);
706 errno = ENOMEM;
707 return false;
708 }
709
710 *idx += 1;
711 return true;
712 }
713
714 errno = ENOENT;
715 return false;
716}
717
718/**
719 * qhasharr->size(): Returns the number of objects in this table.
720 *
721 * @param tbl qhasharr_t container pointer.
722 * @param maxslots if not NULL, total number of slots will be stored.
723 * @param usedslots if not NULL, total number of used slots will be stored.
724 *
725 * @return a number of elements stored.
726 */
727 int qhasharr_size(qhasharr_t *tbl, int *maxslots, int *usedslots) {
728 if (tbl == NULL) {
729 errno = EINVAL;
730 return -1;
731 }
732
733 qhasharr_data_t *tbldata = tbl->data;
734
735 if (maxslots != NULL)
736 *maxslots = tbldata->maxslots;
737 if (usedslots != NULL)
738 *usedslots = tbldata->usedslots;
739
740 return tbldata->num;
741}
742
743/**
744 * qhasharr->clear(): Clears this table so that it contains no keys.
745 *
746 * @param tbl qhasharr_t container pointer.
747 *
748 * @return true if successful, otherwise returns false.
749 */
750 void qhasharr_clear(qhasharr_t *tbl) {
751 if (tbl == NULL) {
752 errno = EINVAL;
753 return;
754 }
755
756 qhasharr_data_t *tbldata = tbl->data;
757 qhasharr_slot_t *tblslots = get_slots(tbl);
758
759 if (tbldata->usedslots == 0)
760 return;
761
762 tbldata->usedslots = 0;
763 tbldata->num = 0;
764
765 // clear memory
766 memset((void *) tblslots, '\0',
767 (tbldata->maxslots * sizeof(qhasharr_slot_t)));
768}
769
770/**
771 * qhasharr->debug(): Print hash table for debugging purpose
772 *
773 * @param tbl qhasharr_t container pointer.
774 * @param out output stream
775 *
776 * @return true if successful, otherwise returns false
777 * @retval errno will be set in error condition.
778 * - EIO : Invalid output stream.
779 */
780 bool qhasharr_debug(qhasharr_t *tbl, FILE *out) {
781 if (tbl == NULL) {
782 errno = EINVAL;
783 return false;
784 }
785
786 if (out == NULL) {
787 errno = EIO;
788 return false;
789 }
790
791 qhasharr_slot_t *tblslots = get_slots(tbl);
792
793 int idx = 0;
794 qhasharr_obj_t obj;
795 while (tbl->getnext(tbl, &obj, &idx) == true) {
796 uint16_t namesize = tblslots[idx - 1].data.pair.namesize;
797 _q_textout(out, obj.name, obj.namesize, MAX_HUMANOUT);
798 fprintf(out, "%s(%d)=", (namesize > Q_HASHARR_NAMESIZE) ? "..." : "",
799 namesize);
800 _q_textout(out, obj.data, obj.datasize, MAX_HUMANOUT);
801 fprintf(out, " (%zu)\n", obj.datasize);
802
803 free(obj.name);
804 free(obj.data);
805 }
806
807#ifdef BUILD_DEBUG
808 qhasharr_data_t *tbldata = tbl->data;
809 fprintf(out, "%d elements (slot %d used/%d total)\n",
810 tbldata->num, tbldata->usedslots, tbldata->maxslots);
811 for (idx = 0; idx < tbldata->maxslots; idx++) {
812 if (tblslots[idx].count == 0) continue;
813
814 fprintf(out, "slot=%d,type=", idx);
815 if (tblslots[idx].count == EXTBLOCK_MARK) {
816 fprintf(out, "EXTEND");
817 fprintf(out, ",prev=%d", tblslots[idx].hash);
818 fprintf(out, ",next=%d", tblslots[idx].link);
819 fprintf(out, ",datasize=%d", tblslots[idx].datasize);
820 fprintf(out, ",data=");
821 _q_textout(out,
822 tblslots[idx].data.ext.data,
823 tblslots[idx].datasize,
824 MAX_HUMANOUT);
825 } else {
826 fprintf(out, "%s", (tblslots[idx].count == COLLISION_MARK)?"COLISN":"NORMAL");
827 fprintf(out, ",next=%d", tblslots[idx].link);
828 fprintf(out, ",count=%d", tblslots[idx].count);
829 fprintf(out, ",hash=%u", tblslots[idx].hash);
830 fprintf(out, ",namesize=%d", tblslots[idx].data.pair.namesize);
831 fprintf(out, ",datasize=%d", tblslots[idx].datasize);
832 fprintf(out, ",name=");
833 _q_textout(out,
834 tblslots[idx].data.pair.name,
835 (tblslots[idx].data.pair.namesize>Q_HASHARR_NAMESIZE)
836 ? Q_HASHARR_NAMESIZE
837 : tblslots[idx].data.pair.namesize,
838 MAX_HUMANOUT);
839 fprintf(out, ",data=");
840 _q_textout(out,
841 tblslots[idx].data.pair.data,
842 tblslots[idx].datasize,
843 MAX_HUMANOUT);
844 }
845 fprintf(out, "\n");
846 }
847#endif
848
849 return true;
850}
851
852/**
853 * qhasharr->free(): De-allocate table reference object.
854 *
855 * @param tbl qhashtbl_t container pointer.
856 *
857 * @note
858 * This does not de-allocate the data memory but only the memory of
859 * qhasharr struct. User provided data memory must be de-allocated
860 * by user.
861 */
862 void qhasharr_free(qhasharr_t *tbl) {
863 free(tbl);
864}
865
866#ifndef _DOXYGEN_SKIP
867
868 static qhasharr_slot_t* get_slots(qhasharr_t *tbl) {
869 return (qhasharr_slot_t*) ((char*) (tbl->data) + sizeof(qhasharr_data_t));
870}
871
872// find empty slot : return empty slow number, otherwise returns -1.
873 static int find_avail(qhasharr_t *tbl, int startidx) {
874 qhasharr_data_t *tbldata = tbl->data;
875 qhasharr_slot_t *tblslots = get_slots(tbl);
876
877 if (startidx >= tbldata->maxslots)
878 startidx = 0;
879
880 int idx = startidx;
881 while (true) {
882 if (tblslots[idx].count == 0)
883 return idx;
884
885 idx++;
886 if (idx >= tbldata->maxslots)
887 idx = 0;
888 if (idx == startidx)
889 break;
890 }
891
892 return -1;
893}
894
895 static int get_idx(qhasharr_t *tbl, const void *name, size_t namesize,
896 uint32_t hash) {
897 qhasharr_data_t *tbldata = tbl->data;
898 qhasharr_slot_t *tblslots = get_slots(tbl);
899
900 if (tblslots[hash].count > 0) {
901 int count, idx;
902 for (count = 0, idx = hash; count < tblslots[hash].count;) {
903 if (tblslots[idx].hash == hash
904 && (tblslots[idx].count > 0 || tblslots[idx].count == COLLISION_MARK)) {
905 // same hash
906 count++;
907
908 // is same key?
909 // first check key length
910 if (namesize == tblslots[idx].data.pair.namesize) {
911 if (namesize <= Q_HASHARR_NAMESIZE) {
912 // original key is stored
913 if (!memcmp(name, tblslots[idx].data.pair.name,
914 namesize)) {
915 return idx;
916 }
917 } else {
918 // key is truncated, compare MD5 also.
919 unsigned char namemd5[16];
920 qhashmd5(name, namesize, namemd5);
921 if (!memcmp(name, tblslots[idx].data.pair.name,
922 Q_HASHARR_NAMESIZE)
923 && !memcmp(namemd5,
924 tblslots[idx].data.pair.namemd5,
925 16)) {
926 return idx;
927 }
928 }
929 }
930 }
931
932 // increase idx
933 idx++;
934 if (idx >= tbldata->maxslots)
935 idx = 0;
936
937 // check loop
938 if (idx == hash)
939 break;
940
941 continue;
942 }
943 }
944
945 return -1;
946}
947
948 static void *get_data(qhasharr_t *tbl, int idx, size_t *size) {
949 if (idx < 0) {
950 errno = ENOENT;
951 return NULL;
952 }
953
954 qhasharr_slot_t *tblslots = get_slots(tbl);
955
956 int newidx;
957 size_t datasize;
958 for (newidx = idx, datasize = 0;; newidx = tblslots[newidx].link) {
959 datasize += tblslots[newidx].datasize;
960 if (tblslots[newidx].link == -1)
961 break;
962 }
963
964 void *data, *dp;
965 if ((data = malloc(datasize)) == NULL) {
966 errno = ENOMEM;
967 return NULL;
968 }
969
970 for (newidx = idx, dp = data;; newidx = tblslots[newidx].link) {
971 if (tblslots[newidx].count == EXTBLOCK_MARK) {
972 // extended data block
973 memcpy(dp, (void *) tblslots[newidx].data.ext.data,
974 tblslots[newidx].datasize);
975 } else {
976 // key/value pair data block
977 memcpy(dp, (void *) tblslots[newidx].data.pair.data,
978 tblslots[newidx].datasize);
979 }
980
981 dp += tblslots[newidx].datasize;
982 if (tblslots[newidx].link == -1)
983 break;
984 }
985
986 if (size != NULL)
987 *size = datasize;
988 return data;
989}
990
991 static bool put_data(qhasharr_t *tbl, int idx, uint32_t hash, const void *name,
992 size_t namesize, const void *data, size_t datasize,
993 int count) {
994 qhasharr_data_t *tbldata = tbl->data;
995 qhasharr_slot_t *tblslots = get_slots(tbl);
996
997 assert(tblslots[idx].count == 0);
998
999 unsigned char namemd5[16];
1000 qhashmd5(name, namesize, namemd5);
1001
1002 // store name
1003 tblslots[idx].count = count;
1004 tblslots[idx].hash = hash;
1005 memcpy(tblslots[idx].data.pair.name, name,
1006 (namesize < Q_HASHARR_NAMESIZE) ? namesize : Q_HASHARR_NAMESIZE);
1007 memcpy((char *) tblslots[idx].data.pair.namemd5, (char *) namemd5, 16);
1008 tblslots[idx].data.pair.namesize = namesize;
1009 tblslots[idx].link = -1;
1010
1011 // store data
1012 int newidx;
1013 size_t savesize;
1014 for (newidx = idx, savesize = 0; savesize < datasize;) {
1015 if (savesize > 0) { // find next empty slot
1016 int tmpidx = find_avail(tbl, newidx + 1);
1017 if (tmpidx < 0) {
1018 remove_data(tbl, idx);
1019 errno = ENOBUFS;
1020 return false;
1021 }
1022
1023 // clear & set
1024 memset((void *) (&tblslots[tmpidx]), '\0', sizeof(qhasharr_slot_t));
1025
1026 tblslots[tmpidx].count = EXTBLOCK_MARK; // extended data block
1027 tblslots[tmpidx].hash = newidx; // previous link
1028 tblslots[tmpidx].link = -1; // end block mark
1029 tblslots[tmpidx].datasize = 0;
1030 tblslots[newidx].link = tmpidx; // link chain
1031
1032 newidx = tmpidx;
1033 }
1034
1035 // copy data
1036 size_t copysize = datasize - savesize;
1037 if (tblslots[newidx].count == EXTBLOCK_MARK) {
1038 // extended value
1039 if (copysize > sizeof(struct Q_HASHARR_SLOT_EXT)) {
1040 copysize = sizeof(struct Q_HASHARR_SLOT_EXT);
1041 }
1042 memcpy(tblslots[newidx].data.ext.data, data + savesize, copysize);
1043 } else {
1044 // first slot
1045 if (copysize > Q_HASHARR_DATASIZE) {
1046 copysize = Q_HASHARR_DATASIZE;
1047 }
1048 memcpy(tblslots[newidx].data.pair.data, data + savesize, copysize);
1049
1050 // increase stored key counter
1051 tbldata->num++;
1052 }
1053 tblslots[newidx].datasize = copysize;
1054 savesize += copysize;
1055
1056 // increase used slot counter
1057 tbldata->usedslots++;
1058 }
1059
1060 return true;
1061}
1062
1063 static bool copy_slot(qhasharr_t *tbl, int idx1, int idx2) {
1064 qhasharr_slot_t *tblslots = get_slots(tbl);
1065
1066 if (tblslots[idx1].count != 0 || tblslots[idx2].count == 0) {
1067 errno = EFAULT;
1068 return false;
1069 }
1070
1071 memcpy((void *) (&tblslots[idx1]), (void *) (&tblslots[idx2]),
1072 sizeof(qhasharr_slot_t));
1073
1074 return true;
1075}
1076
1077 static bool remove_slot(qhasharr_t *tbl, int idx) {
1078 qhasharr_slot_t *tblslots = get_slots(tbl);
1079 assert(tblslots[idx].count != 0);
1080
1081 tblslots[idx].count = 0;
1082 return true;
1083}
1084
1085 static bool remove_data(qhasharr_t *tbl, int idx) {
1086 qhasharr_data_t *tbldata = tbl->data;
1087 qhasharr_slot_t *tblslots = get_slots(tbl);
1088 assert(tblslots[idx].count != 0);
1089
1090 while (true) {
1091 int link = tblslots[idx].link;
1092 remove_slot(tbl, idx);
1093 tbldata->usedslots--;
1094
1095 if (link == -1)
1096 break;
1097
1098 idx = link;
1099 }
1100
1101 // decrease stored key counter
1102 tbldata->num--;
1103
1104 return true;
1105}
1106
1107#endif /* _DOXYGEN_SKIP */
qhashmd5
bool qhashmd5(const void *data, size_t nbytes, void *retbuf)
Calculate 128-bit(16-bytes) MD5 hash.
Definition qhash.c:67
qhashmurmur3_32
uint32_t qhashmurmur3_32(const void *data, size_t nbytes)
Get 32-bit Murmur3 hash.
Definition qhash.c:263
qhasharr_clear
void qhasharr_clear(qhasharr_t *tbl)
qhasharr->clear(): Clears this table so that it contains no keys.
Definition qhasharr.c:750
qhasharr_size
int qhasharr_size(qhasharr_t *tbl, int *maxslots, int *usedslots)
qhasharr->size(): Returns the number of objects in this table.
Definition qhasharr.c:727
qhasharr_put_by_obj
bool qhasharr_put_by_obj(qhasharr_t *tbl, const void *name, size_t namesize, const void *data, size_t datasize)
qhasharr->put_by_obj(): ut an object into this table by key object.
Definition qhasharr.c:344
qhasharr_remove_by_idx
bool qhasharr_remove_by_idx(qhasharr_t *tbl, int idx)
qhasharr->remove_by_idx(): Remove an object from this table by index number.
Definition qhasharr.c:591
qhasharr_get
void * qhasharr_get(qhasharr_t *tbl, const char *name, size_t *datasize)
qhasharr->get(): Get an object from this table
Definition qhasharr.c:444
qhasharr_debug
bool qhasharr_debug(qhasharr_t *tbl, FILE *out)
qhasharr->debug(): Print hash table for debugging purpose
Definition qhasharr.c:780
qhasharr_put
bool qhasharr_put(qhasharr_t *tbl, const char *name, const void *data, size_t datasize)
qhasharr->put(): Put an object into this table.
Definition qhasharr.c:278
qhasharr
qhasharr_t * qhasharr(void *memory, size_t memsize)
Initialize static hash table.
Definition qhasharr.c:208
qhasharr_calculate_memsize
size_t qhasharr_calculate_memsize(int max)
Get how much memory is needed for N slots.
Definition qhasharr.c:179
qhasharr_getstr
char * qhasharr_getstr(qhasharr_t *tbl, const char *name)
qhasharr->getstr(): Finds an object with given name and returns as string type.
Definition qhasharr.c:464
qhasharr_getnext
bool qhasharr_getnext(qhasharr_t *tbl, qhasharr_obj_t *obj, int *idx)
qhasharr->getnext(): Get next element.
Definition qhasharr.c:676
qhasharr_get_by_obj
void * qhasharr_get_by_obj(qhasharr_t *tbl, const void *name, size_t namesize, size_t *datasize)
qhasharr->get_by_object(): Get an object from this table by key object
Definition qhasharr.c:486
qhasharr_putstrf
bool qhasharr_putstrf(qhasharr_t *tbl, const char *name, const char *format,...)
qhasharr->putstrf(): Put a formatted string into this table.
Definition qhasharr.c:316
qhasharr_free
void qhasharr_free(qhasharr_t *tbl)
qhasharr->free(): De-allocate table reference object.
Definition qhasharr.c:862
qhasharr_remove
bool qhasharr_remove(qhasharr_t *tbl, const char *name)
qhasharr->remove(): Remove an object from this table.
Definition qhasharr.c:518
qhasharr_putstr
bool qhasharr_putstr(qhasharr_t *tbl, const char *name, const char *data)
qhasharr->putstr(): Put a string into this table
Definition qhasharr.c:297
qhasharr_remove_by_obj
bool qhasharr_remove_by_obj(qhasharr_t *tbl, const char *name, size_t namesize)
qhasharr->remove_by_obj(): Remove an object from this table by key object
Definition qhasharr.c:535