qLibc

qlisttbl.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 qlisttbl.c Linked-list-table implementation.
31 *
32 * qlisttbl container is a Linked-List-Table implementation.
33 * Which maps keys to values. Key is a string and value is any non-null object.
34 * These elements are stored sequentially in Doubly-Linked-List data structure.
35 *
36 * Compared to Hash-Table, List-Table is efficient when you need to keep
37 * duplicated keys since Hash-Table only keep unique keys. Of course, qlisttbl
38 * supports both unique keys and key duplication.
39 *
40 * @code
41 * [Conceptional Data Structure Diagram]
42 *
43 * last~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
44 * |
45 * +-----------+ doubly +-----------+ doubly +-v---------+
46 * first~~~|~> 0 <~|~~~~~~~~~~|~> 1 <~|~~~~~~~~~~|~> N |
47 * +--|-----|--+ linked +--|-----|--+ linked +--|-----|--+
48 * | | | | | |
49 * +-----v-+ +-v-------+ | | +-----v-+ +-v-------+
50 * | KEY A | | VALUE A | | | | KEY N | | VALUE N |
51 * +-------+ +---------+ | | +-------+ +---------+
52 * +-----v-+ +-v-------+
53 * | KEY B | | VALUE B |
54 * +-------+ +---------+
55 * @endcode
56 *
57 * @code
58 * // create a list table.
59 * qlisttbl_t *tbl = qlisttbl(QLISTTBL_THREADSAFE);
60 *
61 * // insert elements (key duplication allowed)
62 * tbl->put(tbl, "e1", "a", strlen("e1")+1); // equal to putstr();
63 * tbl->putstr(tbl, "e2", "b");
64 * tbl->putstr(tbl, "e2", "c");
65 * tbl->putstr(tbl, "e3", "d");
66 *
67 * // debug output
68 * tbl->debug(tbl, stdout, true);
69 *
70 * // get element
71 * printf("get('e2') : %s\n", (char*)tbl->get(tbl, "e2", NULL, false));
72 * printf("getstr('e2') : %s\n", tbl->getstr(tbl, "e2", false));
73 *
74 * // get all matching elements
75 * qlisttbl_data_t *objs = tbl->getmulti(tbl, "e2", true, NULL);
76 * for (i = 0; objs[i].data != NULL; i++) {
77 * printf("getmulti('e2')[%d] : %s (size=%d)\n",
78 * i, (char *)objs[i].data, (int)objs[i].size);
79 * }
80 * tbl->freemulti(objs);
81 *
82 * // find every 'e2' elements
83 * qlisttbl_obj_t obj;
84 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
85 * while(tbl->getnext(tbl, &obj, "e2", false) == true) {
86 * printf("NAME=%s, DATA=%s, SIZE=%zu\n",
87 * obj.name, (char*)obj.data, obj.size);
88 * }
89 *
90 * // free object
91 * tbl->free(tbl);
92 * @endcode
93 */
94
95#include <stdio.h>
96#include <stdlib.h>
97#include <stdbool.h>
98#include <stdint.h>
99#include <inttypes.h>
100#include <string.h>
101#include <stdarg.h>
102#include <unistd.h>
103#include <fcntl.h>
104#include <sys/stat.h>
105#include <assert.h>
106#include <errno.h>
107#include "qinternal.h"
108#include "utilities/qencode.h"
109#include "utilities/qfile.h"
110#include "utilities/qhash.h"
111#include "utilities/qio.h"
112#include "utilities/qstring.h"
113#include "utilities/qtime.h"
114#include "containers/qlisttbl.h"
115
116#ifndef _DOXYGEN_SKIP
117
118 static qlisttbl_obj_t *newobj(const char *name, const void *data, size_t size);
119 static bool insertobj(qlisttbl_t *tbl, qlisttbl_obj_t *obj);
120 static qlisttbl_obj_t *findobj(qlisttbl_t *tbl, const char *name, qlisttbl_obj_t *retobj);
121
122 static bool namematch(qlisttbl_obj_t *obj, const char *name, uint32_t hash);
123 static bool namecasematch(qlisttbl_obj_t *obj, const char *name, uint32_t hash);
124
125#endif
126
127/**
128 * Create a new Q_LIST linked-list container
129 *
130 * @param options combination of initialization options.
131 *
132 * @return a pointer of malloced qlisttbl_t structure in case of successful,
133 * otherwise returns NULL.
134 * @retval errno will be set in error condition.
135 * - ENOMEM : Memory allocation failure.
136 *
137 * @code
138 * qlisttbl_t *tbl = qlisttbl(0);
139 * qlisttbl_t *threadsafe_tbl = qlisttbl(QLISTTBL_THREADSAFE);
140 * @endcode
141 *
142 * @note
143 * Available options:
144 * - QLISTTBL_THREADSAFE - make it thread-safe.
145 * - QLISTTBL_UNIQUE - keys are all unique. replace same key
146 * - QLISTTBL_CASEINSENSITIVE - key is case insensitive
147 * - QLISTTBL_INSERTTOP - insert new key at the top
148 * - QLISTTBL_LOOKUPFORWARD - find key from the top
149 */
150qlisttbl_t *qlisttbl(int options)
151{
152 qlisttbl_t *tbl = (qlisttbl_t *)calloc(1, sizeof(qlisttbl_t));
153 if (tbl == NULL) {
154 errno = ENOMEM;
155 return NULL;
156 }
157
158 // assign member methods.
159 tbl->put = qlisttbl_put;
160 tbl->putstr = qlisttbl_putstr;
161 tbl->putstrf = qlisttbl_putstrf;
162 tbl->putint = qlisttbl_putint;
163
164 tbl->get = qlisttbl_get;
165 tbl->getstr = qlisttbl_getstr;
166 tbl->getint = qlisttbl_getint;
167
168 tbl->getmulti = qlisttbl_getmulti;
169 tbl->freemulti = qlisttbl_freemulti;
170
171 tbl->remove = qlisttbl_remove;
172 tbl->removeobj = qlisttbl_removeobj;
173
174 tbl->getnext = qlisttbl_getnext;
175
176 tbl->size = qlisttbl_size;
177 tbl->sort = qlisttbl_sort;
178 tbl->clear = qlisttbl_clear;
179 tbl->save = qlisttbl_save;
180 tbl->load = qlisttbl_load;
181
182 tbl->debug = qlisttbl_debug;
183
184 tbl->lock = qlisttbl_lock;
185 tbl->unlock = qlisttbl_unlock;
186
187 tbl->free = qlisttbl_free;
188
189 // assign private methods.
190 tbl->namematch = namematch;
191 tbl->namecmp = strcmp;
192
193 // handle options.
194 if (options & QLISTTBL_THREADSAFE) {
195 Q_MUTEX_NEW(tbl->qmutex, true);
196 if (tbl->qmutex == NULL) {
197 errno = ENOMEM;
198 free(tbl);
199 return NULL;
200 }
201 }
202 if (options & QLISTTBL_UNIQUE) {
203 tbl->unique = true;
204 }
205 if (options & QLISTTBL_CASEINSENSITIVE) {
206 tbl->namematch = namecasematch;
207 tbl->namecmp = strcasecmp;
208 }
209 if (options & QLISTTBL_INSERTTOP) {
210 tbl->inserttop = true;
211 }
212 if (options & QLISTTBL_LOOKUPFORWARD) {
213 tbl->lookupforward = true;
214 }
215
216 return tbl;
217}
218
219/**
220 * qlisttbl->put(): Put an element to this table.
221 *
222 * @param tbl qlisttbl container pointer.
223 * @param name element name.
224 * @param data a pointer which points data memory.
225 * @param size size of the data.
226 *
227 * @return true if successful, otherwise returns false.
228 * @retval errno will be set in error condition.
229 * - ENOMEM : Memory allocation failure.
230 * - EINVAL : Invalid argument.
231 *
232 * @code
233 * struct my_obj {
234 * int a, b, c;
235 * };
236 *
237 * // create a sample object.
238 * struct my_obj obj;
239 *
240 * // create a table and add a sample object.
241 * qlisttbl_t *tbl = qlisttbl();
242 * tbl->put(tbl, "obj1", &obj, sizeof(struct my_obj));
243 * @endcode
244 *
245 * @note
246 * The default behavior is adding an object at the end of this table
247 * unless QLISTTBL_INSERTTOP option was given.
248 */
249 bool qlisttbl_put(qlisttbl_t *tbl, const char *name, const void *data, size_t size)
250{
251 // make new object table
252 qlisttbl_obj_t *obj = newobj(name, data, size);
253 if (obj == NULL) {
254 return false;
255 }
256
257 // lock table
258 qlisttbl_lock(tbl);
259
260 // if unique flag is set, remove same key
261 if (tbl->unique == true) qlisttbl_remove(tbl, name);
262
263 // insert into table
264 if (tbl->num == 0) {
265 obj->prev = NULL;
266 obj->next = NULL;
267 } else {
268 if (tbl->inserttop == false) {
269 obj->prev = tbl->last;
270 obj->next = NULL;
271 } else {
272 obj->prev = NULL;
273 obj->next = tbl->first;
274 }
275 }
276 insertobj(tbl, obj);
277
278 // unlock table
279 qlisttbl_unlock(tbl);
280
281 return true;
282}
283
284/**
285 * qlisttbl->putstr(): Put a string into this table.
286 *
287 * @param tbl qlisttbl container pointer.
288 * @param name element name.
289 * @param str string data.
290 *
291 * @return true if successful, otherwise returns false.
292 * @retval errno will be set in error condition.
293 * - ENOMEM : Memory allocation failure.
294 * - EINVAL : Invalid argument.
295 */
296 bool qlisttbl_putstr(qlisttbl_t *tbl, const char *name, const char *str)
297{
298 size_t size = (str) ? (strlen(str) + 1) : 0;
299 return qlisttbl_put(tbl, name, (const void *)str, size);
300}
301
302/**
303 * qlisttbl->putstrf(): Put a formatted string into this table.
304 *
305 * @param tbl qlisttbl container pointer.
306 * @param name element name.
307 * @param format formatted value string.
308 *
309 * @return true if successful, otherwise returns false.
310 * @retval errno will be set in error condition.
311 * - ENOMEM : Memory allocation failure.
312 * - EINVAL : Invalid argument.
313 */
314 bool qlisttbl_putstrf(qlisttbl_t *tbl, const char *name, const char *format, ...)
315{
316 char *str;
317 DYNAMIC_VSPRINTF(str, format);
318 if (str == NULL) {
319 errno = ENOMEM;
320 return false;
321 }
322
323 bool ret = qlisttbl_putstr(tbl, name, str);
324 free(str);
325
326 return ret;
327}
328
329/**
330 * qlisttbl->putInt(): Put an integer into this table as string type.
331 *
332 * @param tbl qlisttbl container pointer.
333 * @param name element name.
334 * @param num number data.
335 *
336 * @return true if successful, otherwise returns false.
337 * @retval errno will be set in error condition.
338 * - ENOMEM : Memory allocation failure.
339 * - EINVAL : Invalid argument.
340 *
341 * @note
342 * The integer will be converted to a string object and stored as a string
343 * object.
344 */
345 bool qlisttbl_putint(qlisttbl_t *tbl, const char *name, int64_t num)
346{
347 char str[20+1];
348 snprintf(str, sizeof(str), "%"PRId64, num);
349 return qlisttbl_putstr(tbl, name, str);
350}
351
352/**
353 * qlisttbl->get(): Finds an object with given name.
354 *
355 * If there are duplicate keys in the table, this will return the first matched
356 * one from the bottom (or the top if QLISTTBL_LOOKUPFORWARD option was given).
357 * So if there are duplicated keys, it'll return recently inserted one.
358 *
359 * @param tbl qlisttbl container pointer.
360 * @param name element name.
361 * @param size if size is not NULL, data size will be stored.
362 * @param newmem whether or not to allocate memory for the data.
363 *
364 * @return a pointer of data if key is found, otherwise returns NULL.
365 * @retval errno will be set in error condition.
366 * - ENOENT : No such key found.
367 * - EINVAL : Invalid argument.
368 * - ENOMEM : Memory allocation failure.
369 *
370 * @code
371 * qlisttbl_t *tbl = qlisttbl();
372 * (...codes...)
373 *
374 * // with newmem flag unset
375 * size_t size;
376 * void *data = tbl->get(tbl, "key_name", &size, false);
377 *
378 * // with newmem flag set
379 * size_t size;
380 * void *data = tbl->get(tbl, "key_name", &size, true);
381 * (...does something with data...)
382 * if(data != NULL) free(data);
383 * @endcode
384 *
385 * @note
386 * If newmem flag is set, returned data will be malloced and should be
387 * deallocated by user. Otherwise returned pointer will point internal data
388 * buffer directly and should not be de-allocated by user. In thread-safe mode,
389 * always set newmem flag as true to make sure it works in race condition
390 * situation.
391 */
392 void *qlisttbl_get(qlisttbl_t *tbl, const char *name, size_t *size, bool newmem)
393{
394 if (name == NULL) {
395 errno = EINVAL;
396 return NULL;
397 }
398
399 qlisttbl_lock(tbl);
400 void *data = NULL;
401 qlisttbl_obj_t *obj = findobj(tbl, name, NULL);
402 if (obj != NULL) {
403 // get data
404 if (newmem == true) {
405 data = malloc(obj->size);
406 if (data == NULL) {
407 errno = ENOMEM;
408 qlisttbl_unlock(tbl);
409 return NULL;
410 }
411 memcpy(data, obj->data, obj->size);
412 } else {
413 data = obj->data;
414 }
415
416 // set size
417 if (size != NULL) *size = obj->size;
418 }
419 qlisttbl_unlock(tbl);
420
421 if (data == NULL) {
422 errno = ENOENT;
423 }
424
425 return data;
426}
427
428/**
429 * qlisttbl->getstr(): Finds an object with given name and returns as
430 * string type.
431 *
432 * @param tbl qlisttbl container pointer.
433 * @param name element name.
434 * @param newmem whether or not to allocate memory for the data.
435 *
436 * @return a pointer of data if key is found, otherwise returns NULL.
437 * @retval errno will be set in error condition.
438 * - ENOENT : No such key found.
439 * - EINVAL : Invalid argument.
440 * - ENOMEM : Memory allocation failure.
441*/
442 char *qlisttbl_getstr(qlisttbl_t *tbl, const char *name, bool newmem)
443{
444 return (char *)qlisttbl_get(tbl, name, NULL, newmem);
445}
446
447/**
448 * qlisttbl->getint(): Finds an object with given name and returns as
449 * integer type.
450 *
451 * @param tbl qlisttbl container pointer.
452 * @param name element name.
453 *
454 * @return an integer value of the integer object, otherwise returns 0.
455 * @retval errno will be set in error condition.
456 * - ENOENT : No such key found.
457 * - EINVAL : Invalid argument.
458 * - ENOMEM : Memory allocation failure.
459 */
460int64_t qlisttbl_getint(qlisttbl_t *tbl, const char *name)
461{
462 int64_t num = 0;
463 char *str = qlisttbl_getstr(tbl, name, true);
464 if (str != NULL) {
465 num = atoll(str);
466 free(str);
467 }
468 return num;
469}
470
471/**
472 * qlisttbl->getmulti(): Finds all objects with given name and return a array
473 * of objects.
474 *
475 * If there are duplicate keys in the table, this will return all
476 * the matched ones. The order of objects in return depends on setnextdir()
477 * setting. By default, the order is same(forward) as listed in the table.
478 *
479 * @param tbl qlisttbl container pointer.
480 * @param name element name.
481 * @param newmem whether or not to allocate memory for the data.
482 * @param numobjs the nuber of objects returned will be stored. (can be NULL)
483 *
484 * @return a pointer of data if key is found, otherwise returns NULL.
485 * @retval errno will be set in error condition.
486 * - ENOENT : No such key found.
487 * - EINVAL : Invalid argument.
488 * - ENOMEM : Memory allocation failure.
489 *
490 * @note
491 * The returned array of qlisttbl_data_t should be released by freemulti() call
492 * after use. Even you call getmulti() with newmem set false, freemulti() should
493 * be called all the times, so the object array itself can be released.
494 *
495 * @code
496 * size_t numobjs = 0;
497 * qlisttbl_data_t *objs = tbl->getmulti(tbl, "e2", true, &numobjs);
498 * for (i = 0; objs[i].data != NULL; i++) {
499 * printf("DATA=%s, SIZE=%zu\n", i, (char *)objs[i].data, objs[i].size);
500 * }
501 * tbl->freemulti(objs);
502 * @endcode
503 */
504qlisttbl_data_t *qlisttbl_getmulti(qlisttbl_t *tbl, const char *name, bool newmem,
505 size_t *numobjs)
506{
507 qlisttbl_data_t *objs = NULL; // objects container
508 size_t allocobjs = 0; // allocated number of objs
509 size_t numfound = 0; // number of keys found
510
511 qlisttbl_obj_t obj;
512 memset((void *)&obj, 0, sizeof(obj)); // must be cleared before call
513 qlisttbl_lock(tbl);
514 while (tbl->getnext(tbl, &obj, name, newmem) == true) {
515 numfound++;
516
517 // allocate object array.
518 if (numfound >= allocobjs) {
519 if (allocobjs == 0) allocobjs = 10; // start from 10
520 else allocobjs *= 2; // double size
521 objs = (qlisttbl_data_t *)realloc(objs, sizeof(qlisttbl_data_t) * allocobjs);
522 if (objs == NULL) {
523 DEBUG("qlisttbl->getmulti(): Memory reallocation failure.");
524 errno = ENOMEM;
525 break;
526 }
527 }
528
529 // copy reference
530 qlisttbl_data_t *newobj = &objs[numfound - 1];
531 newobj->data = obj.data;
532 newobj->size = obj.size;
533 newobj->type = (newmem == false) ? 1 : 2;
534
535 // release resource
536 if (newmem == true) {
537 if (obj.name != NULL) free(obj.name);
538 }
539
540 // clear next block
541 newobj = &objs[numfound];
542 memset((void *)newobj, '\0', sizeof(qlisttbl_data_t));
543 newobj->type = 0; // mark, end of objects
544 }
545 qlisttbl_unlock(tbl);
546
547 // return found counter
548 if (numobjs != NULL) {
549 *numobjs = numfound;
550 }
551
552 if (numfound == 0) {
553 errno = ENOENT;
554 }
555
556 return objs;
557}
558
559/**
560 * qlisttbl->freemulti(): Deallocate object array returned by getmulti().
561 *
562 * @param objs pointer of array of qlisttbl_data_t.
563 *
564 * @code
565 * qlisttbl_data_t *objs = tbl->getmulti(tbl, "newmem is true", true, &numobjs);
566 * tbl->freemulti(objs); // frees allocated objects and object array itself.
567 *
568 * qlisttbl_data_t *objs = tbl->getmulti(tbl, "even newmem is false", false, &numobjs);
569 * tbl->freemulti(objs); // frees object array itself.
570 *
571 * @endcode
572 */
573 void qlisttbl_freemulti(qlisttbl_data_t *objs)
574{
575 if (objs == NULL) return;
576
577 qlisttbl_data_t *obj;
578 for (obj = &objs[0]; obj->type == 2; obj++) {
579 if (obj->data != NULL) free(obj->data);
580 }
581
582 free(objs);
583}
584
585/**
586 * qlisttbl->remove(): Remove matched objects with given name.
587 *
588 * @param tbl qlisttbl container pointer.
589 * @param name element name.
590 *
591 * @return a number of removed objects.
592 */
593 size_t qlisttbl_remove(qlisttbl_t *tbl, const char *name)
594{
595 if (name == NULL) return false;
596
597 size_t numremoved = 0;
598
599 qlisttbl_obj_t obj;
600 memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
601 qlisttbl_lock(tbl);
602 while (qlisttbl_getnext(tbl, &obj, name, false) == true) {
603 qlisttbl_removeobj(tbl, &obj);
604 numremoved++;
605 }
606 qlisttbl_unlock(tbl);
607
608 return numremoved;
609}
610
611/**
612 * qlisttbl->removeobj(): Remove objects with given object pointer.
613 *
614 * This call is useful when you want to remove an element while traversing a
615 * table using getnext(). So the address pointed by obj maybe different than
616 * the actual object in a table, but it's ok because we'll recalculate the
617 * actual object address by referring it's links.
618 *
619 * @param tbl qlisttbl container pointer.
620 * @param name element name.
621 *
622 * @return true if succeed on deletion, false if failed.
623 * @retval errno will be set in error condition.
624 * - ENOENT : No such key found.
625 *
626 * @code
627 * qlisttbl_obj_t obj;
628 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
629 * tbl->lock(tbl);
630 * while(tbl->getnext(tbl, &obj, NULL, true) == true) {
631 * tbl->removeobj(tbl, &obj); // this will remove all entries in the table
632 * }
633 * tbl->unlock(tbl);
634 * @endcode
635 */
636 bool qlisttbl_removeobj(qlisttbl_t *tbl, const qlisttbl_obj_t *obj)
637{
638 if (obj == NULL) return false;
639
640 qlisttbl_lock(tbl);
641
642 // copy chains
643 qlisttbl_obj_t *prev = obj->prev;
644 qlisttbl_obj_t *next = obj->next;
645
646 // find this object
647 qlisttbl_obj_t *this = NULL;
648 if (prev != NULL) this = prev->next;
649 else if (next != NULL) this = next->prev;
650 else this = tbl->first; // table has only one object.
651
652 // double check
653 if (this == NULL) {
654 qlisttbl_unlock(tbl);
655 DEBUG("qlisttbl->removeobj(): Can't veryfy object.");
656 errno = ENOENT;
657 return false;
658 }
659
660 // adjust chain links
661 if (prev == NULL) tbl->first = next; // if the object is first one
662 else prev->next = next; // not the first one
663
664 if (next == NULL) tbl->last = prev; // if the object is last one
665 else next->prev = prev; // not the first one
666
667 // adjust counter
668 tbl->num--;
669
670 qlisttbl_unlock(tbl);
671
672 // free object
673 free(this->name);
674 free(this->data);
675 free(this);
676
677 return true;
678}
679
680/**
681 * qlisttbl->getnext(): Get next element.
682 *
683 * Default searching direction is backward, from the bottom to top
684 * unless QLISTTBL_LOOKUPFORWARD option was specified.
685 *
686 * @param tbl qlisttbl container pointer.
687 * @param obj found data will be stored in this object
688 * @param name element name., if key name is NULL search every objects in
689 * the table.
690 * @param newmem whether or not to allocate memory for the data.
691 *
692 * @return true if found otherwise returns false
693 * @retval errno will be set in error condition.
694 * - ENOENT : No next element.
695 * - ENOMEM : Memory allocation failure.
696 *
697 * @note
698 * The obj should be initialized with 0 by using memset() before first call.
699 * If newmem flag is true, user should de-allocate obj.name and obj.data
700 * resources.
701 *
702 * @code
703 * qlisttbl_t *tbl = qlisttbl();
704 * (...add data into table...)
705 *
706 * // non-thread usages
707 * qlisttbl_obj_t obj;
708 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
709 * while(tbl->getnext(tbl, &obj, NULL, false) == true) {
710 * printf("NAME=%s, DATA=%s, SIZE=%zu\n",
711 * obj.name, (char*)obj.data, obj.size);
712 * }
713 *
714 * // thread model with particular key search
715 * qlisttbl_obj_t obj;
716 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
717 * tbl->lock(tbl);
718 * while(tbl->getnext(tbl, &obj, "key_name", true) == true) {
719 * printf("NAME=%s, DATA=%s, SIZE=%zu\n",
720 * obj.name, (char*)obj.data, obj.size);
721 * free(obj.name);
722 * free(obj.data);
723 * }
724 * tbl->unlock(tbl);
725 * @endcode
726 */
727 bool qlisttbl_getnext(qlisttbl_t *tbl, qlisttbl_obj_t *obj, const char *name,
728 bool newmem)
729{
730 if (obj == NULL) return NULL;
731
732 qlisttbl_lock(tbl);
733
734 qlisttbl_obj_t *cont = NULL;
735 if (obj->size == 0) { // first time call
736 if (name == NULL) { // full scan
737 cont = (tbl->lookupforward) ? tbl->first : tbl->last;
738 } else { // name search
739 cont = findobj(tbl, name, NULL);
740 }
741 } else { // next call
742 cont = (tbl->lookupforward) ? obj->next : obj->prev;
743 }
744
745 if (cont == NULL) {
746 errno = ENOENT;
747 qlisttbl_unlock(tbl);
748 return false;
749 }
750
751 uint32_t hash = (name != NULL) ? qhashmurmur3_32(name, strlen(name)) : 0;
752
753 bool ret = false;
754 while (cont != NULL) {
755 if (name == NULL || tbl->namematch(cont, name, hash) == true) {
756 if (newmem == true) {
757 obj->name = strdup(cont->name);
758 obj->data = malloc(cont->size);
759 if (obj->name == NULL || obj->data == NULL) {
760 if (obj->name != NULL) free(obj->name);
761 if (obj->data != NULL) free(obj->data);
762 obj->name = NULL;
763 obj->data = NULL;
764 errno = ENOMEM;
765 break;
766 }
767 memcpy(obj->data, cont->data, cont->size);
768 } else {
769 obj->name = cont->name;
770 obj->data = cont->data;
771 }
772 obj->hash = cont->hash;
773 obj->size = cont->size;
774 obj->prev = cont->prev;
775 obj->next = cont->next;
776
777 ret = true;
778 break;
779 }
780
781 cont = (tbl->lookupforward) ? cont->next : cont->prev;
782 }
783 qlisttbl_unlock(tbl);
784
785 if (ret == false) {
786 errno = ENOENT;
787 }
788
789 return ret;
790}
791
792/**
793 * qlisttbl->size(): Returns the number of elements in this table.
794 *
795 * @param tbl qlisttbl container pointer.
796 *
797 * @return the number of elements in this table.
798 */
799 size_t qlisttbl_size(qlisttbl_t *tbl)
800{
801 return tbl->num;
802}
803
804/**
805 * qlisttbl->sort(): Sort keys in this table.
806 *
807 * @param tbl qlisttbl container pointer.
808 *
809 * @note
810 * It will sort the table in ascending manner, if you need descending order somehow,
811 * lookup-backword option will do the job without changing the order in the table.
812 *
813 * @code
814 * The appearence order of duplicated keys will be preserved in a sored table.
815 * See how duplicated key 'b' is ordered in below example
816 *
817 * [Unsorted] [sorted ASC] [sorted DES]
818 * d = 1 a = 2 d = 1
819 * a = 2 b = 3 c = 5
820 * b = 3 b = 4 b = 3
821 * b = 4 b = 6 b = 4
822 * c = 5 c = 5 b = 6
823 * b = 6 d = 1 a = 2
824 * @endcode
825 */
826 void qlisttbl_sort(qlisttbl_t *tbl)
827{
828 // run bubble sort
829 qlisttbl_lock(tbl);
830 qlisttbl_obj_t *obj1, *obj2;
831 qlisttbl_obj_t tmpobj;
832 int n, n2, i;
833 for (n = tbl->num; n > 0;) {
834 n2 = 0;
835 for (i = 0, obj1 = tbl->first; i < (n - 1); i++, obj1 = obj1->next) {
836 obj2 = obj1->next; // this can't be null.
837 if (tbl->namecmp(obj1->name, obj2->name) > 0) {
838 // swapping contents is faster than adjusting links.
839 tmpobj = *obj1;
840 obj1->hash = obj2->hash;
841 obj1->name = obj2->name;
842 obj1->data = obj2->data;
843 obj1->size = obj2->size;
844 obj2->hash = tmpobj.hash;
845 obj2->name = tmpobj.name;
846 obj2->data = tmpobj.data;
847 obj2->size = tmpobj.size;
848
849 n2 = i + 1;
850 }
851 }
852 n = n2; // skip sorted tailing elements
853 }
854 qlisttbl_unlock(tbl);
855}
856
857/**
858 * qlisttbl->clear(): Removes all of the elements from this table.
859 *
860 * @param tbl qlisttbl container pointer.
861 */
862 void qlisttbl_clear(qlisttbl_t *tbl)
863{
864 qlisttbl_lock(tbl);
865 qlisttbl_obj_t *obj;
866 for (obj = tbl->first; obj != NULL;) {
867 qlisttbl_obj_t *next = obj->next;
868 free(obj->name);
869 free(obj->data);
870 free(obj);
871 obj = next;
872 }
873
874 tbl->num = 0;
875 tbl->first = NULL;
876 tbl->last = NULL;
877 qlisttbl_unlock(tbl);
878}
879
880/**
881 * qlisttbl->save(): Save qlisttbl as plain text format
882 * Dumping direction is always forward(from the top to the bottom) to preserve
883 * the order when we load the file again.
884 *
885 * @param tbl qlisttbl container pointer.
886 * @param filepath save file path
887 * @param sepchar separator character between name and value. normally '=' is
888 * used.
889 * @param encode flag for encoding data . false can be used if the all data
890 * are string or integer type and has no new line. otherwise
891 * true must be set.
892 *
893 * @return true if successful, otherwise returns false.
894 */
895 bool qlisttbl_save(qlisttbl_t *tbl, const char *filepath, char sepchar,
896 bool encode)
897{
898 if (filepath == NULL) {
899 errno = EINVAL;
900 return false;
901 }
902
903 int fd;
904 if ((fd = open(filepath, O_CREAT|O_WRONLY|O_TRUNC, (S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH))) < 0) {
905 DEBUG("qlisttbl->save(): Can't open file %s", filepath);
906 return false;
907 }
908
909 char *gmtstr = qtime_gmt_str(0);
910 qio_printf(fd, -1, "# %s %s\n", filepath, gmtstr);
911 free(gmtstr);
912
913 qlisttbl_lock(tbl);
914 qlisttbl_obj_t *obj;
915 for (obj = tbl->first; obj; obj = obj->next) {
916 char *encval;
917 if (encode == true) encval = qurl_encode(obj->data, obj->size);
918 else encval = obj->data;
919 qio_printf(fd, -1, "%s%c%s\n", obj->name, sepchar, encval);
920 if (encode == true) free(encval);
921 }
922 qlisttbl_unlock(tbl);
923
924 close(fd);
925 return true;
926}
927
928/**
929 * qlisttbl->load(): Load and append entries from given filepath
930 * Loading direction is always appending at the bottom of the table to preserve
931 * the order as it was.
932 *
933 * @param tbl qlisttbl container pointer.
934 * @param filepath save file path
935 * @param sepchar separator character between name and value. normally '=' is
936 * used
937 * @param decode flag for decoding data
938 *
939 * @return the number of loaded entries, otherwise returns -1.
940 */
941ssize_t qlisttbl_load(qlisttbl_t *tbl, const char *filepath, char sepchar,
942 bool decode)
943{
944 // load file
945 char *str = qfile_load(filepath, NULL);
946 if (str == NULL) return -1;
947
948 // parse
949 qlisttbl_lock(tbl);
950 char *offset, *buf;
951 int cnt = 0;
952 for (offset = str; *offset != '\0'; ) {
953 // get one line into buf
954 for (buf = offset; *offset != '\n' && *offset != '\0'; offset++);
955 if (*offset != '\0') {
956 *offset = '\0';
957 offset++;
958 }
959 qstrtrim(buf);
960
961 // skip blank or comment line
962 if ((buf[0] == '#') || (buf[0] == '\0')) continue;
963
964 // parse
965 char *data = strdup(buf);
966 char *name = _q_makeword(data, sepchar);
967 qstrtrim(data);
968 qstrtrim(name);
969 if (decode == true) qurl_decode(data);
970
971 // add to the table.
972 qlisttbl_put(tbl, name, data, strlen(data) + 1);
973
974 free(name);
975 free(data);
976 }
977 qlisttbl_unlock(tbl);
978 free(str);
979
980 return cnt;
981}
982
983/**
984 * qlisttbl->debug(): Print out stored elements for debugging purpose.
985 *
986 * @param tbl qlisttbl container pointer.
987 * @param out output stream FILE descriptor such like stdout, stderr.
988 *
989 * @return true if successful, otherwise returns false.
990 * @retval errno will be set in error condition.
991 * - EIO : Invalid output stream.
992 */
993 bool qlisttbl_debug(qlisttbl_t *tbl, FILE *out)
994{
995 if (out == NULL) {
996 errno = EIO;
997 return false;
998 }
999
1000 qlisttbl_lock(tbl);
1001 qlisttbl_obj_t *obj;
1002 for (obj = tbl->first; obj; obj = obj->next) {
1003 fprintf(out, "%s=" , obj->name);
1004 _q_textout(out, obj->data, obj->size, MAX_HUMANOUT);
1005 fprintf(out, " (%zu, %08x)\n" , obj->size, obj->hash);
1006 }
1007 qlisttbl_unlock(tbl);
1008
1009 return true;
1010}
1011
1012/**
1013 * qlisttbl->lock(): Enter critical section.
1014 *
1015 * @param tbl qlisttbl container pointer.
1016 *
1017 * @note
1018 * Normally explicit locking is only needed when traverse all the
1019 * elements with qlisttbl->getnext().
1020 */
1021 void qlisttbl_lock(qlisttbl_t *tbl)
1022{
1023 Q_MUTEX_ENTER(tbl->qmutex);
1024}
1025
1026/**
1027 * qlisttbl->unlock(): Leave critical section.
1028 *
1029 * @param tbl qlisttbl container pointer.
1030 */
1031 void qlisttbl_unlock(qlisttbl_t *tbl)
1032{
1033 Q_MUTEX_LEAVE(tbl->qmutex);
1034}
1035
1036/**
1037 * qlisttbl->free(): Free qlisttbl_t
1038 *
1039 * @param tbl qlisttbl container pointer.
1040 */
1041 void qlisttbl_free(qlisttbl_t *tbl)
1042{
1043 qlisttbl_clear(tbl);
1044 Q_MUTEX_DESTROY(tbl->qmutex);
1045 free(tbl);
1046}
1047
1048#ifndef _DOXYGEN_SKIP
1049
1050// lock must be obtained from caller
1051 static qlisttbl_obj_t *newobj(const char *name, const void *data, size_t size)
1052{
1053 if (name == NULL || data == NULL || size <= 0) {
1054 errno = EINVAL;
1055 return false;
1056 }
1057
1058 // make a new object
1059 char *dup_name = strdup(name);
1060 void *dup_data = malloc(size);
1061 qlisttbl_obj_t *obj = (qlisttbl_obj_t *)malloc(sizeof(qlisttbl_obj_t));
1062 if (dup_name == NULL || dup_data == NULL || obj == NULL) {
1063 if (dup_name != NULL) free(dup_name);
1064 if (dup_data != NULL) free(dup_data);
1065 if (obj != NULL) free(obj);
1066 errno = ENOMEM;
1067 return NULL;
1068 }
1069 memcpy(dup_data, data, size);
1070 memset((void *)obj, '\0', sizeof(qlisttbl_obj_t));
1071
1072 // obj->hash = qhashmurmur3_32(dup_name);
1073 obj->name = dup_name;
1074 obj->data = dup_data;
1075 obj->size = size;
1076
1077 return obj;
1078}
1079
1080// lock must be obtained from caller
1081 static bool insertobj(qlisttbl_t *tbl, qlisttbl_obj_t *obj)
1082{
1083 // update hash
1084 obj->hash = qhashmurmur3_32(obj->name, strlen(obj->name));
1085
1086 qlisttbl_obj_t *prev = obj->prev;
1087 qlisttbl_obj_t *next = obj->next;
1088
1089 if (prev == NULL) tbl->first = obj;
1090 else prev->next = obj;
1091
1092 if (next == NULL) tbl->last = obj;
1093 else next->prev = obj;
1094
1095 // increase counter
1096 tbl->num++;
1097
1098 return true;
1099}
1100
1101// lock must be obtained from caller
1102 static qlisttbl_obj_t *findobj(qlisttbl_t *tbl, const char *name, qlisttbl_obj_t *retobj)
1103{
1104 if (retobj != NULL) {
1105 memset((void *)retobj, '\0', sizeof(qlisttbl_obj_t));
1106 }
1107
1108 if (name == NULL || tbl->num == 0) {
1109 errno = ENOENT;
1110 return NULL;
1111 }
1112
1113 uint32_t hash = qhashmurmur3_32(name, strlen(name));
1114 qlisttbl_obj_t *obj = (tbl->lookupforward) ? tbl->first : tbl->last;
1115 while (obj != NULL) {
1116 // name string will be compared only if the hash matches.
1117 if (tbl->namematch(obj, name, hash) == true) {
1118 if (retobj != NULL) {
1119 *retobj = *obj;
1120 }
1121 return obj;
1122 }
1123 obj = (tbl->lookupforward)? obj->next : obj->prev;
1124 }
1125
1126 // not found, set prev and next chain.
1127 if (retobj != NULL) {
1128 if (tbl->inserttop) {
1129 retobj->prev = NULL;
1130 retobj->next = tbl->first;
1131 } else {
1132 retobj->prev = tbl->last;
1133 retobj->next = NULL;
1134 }
1135 }
1136 errno = ENOENT;
1137
1138 return NULL;
1139}
1140
1141// key comp
1142 static bool namematch(qlisttbl_obj_t *obj, const char *name, uint32_t hash)
1143{
1144 if ((obj->hash == hash) && !strcmp(obj->name, name)) {
1145 return true;
1146 }
1147 return false;
1148}
1149
1150 static bool namecasematch(qlisttbl_obj_t *obj, const char *name, uint32_t hash)
1151{
1152 if (!strcasecmp(obj->name, name)) {
1153 return true;
1154 }
1155 return false;
1156}
1157
1158#endif /* _DOXYGEN_SKIP */
qurl_encode
char * qurl_encode(const void *bin, size_t size)
Encode data using URL encoding(Percent encoding) algorithm.
Definition qencode.c:125
qurl_decode
size_t qurl_decode(char *str)
Decode URL encoded string.
Definition qencode.c:192
qfile_load
void * qfile_load(const char *filepath, size_t *nbytes)
Load file into memory.
Definition qfile.c:159
qhashmurmur3_32
uint32_t qhashmurmur3_32(const void *data, size_t nbytes)
Get 32-bit Murmur3 hash.
Definition qhash.c:263
qio_printf
ssize_t qio_printf(int fd, int timeoutms, const char *format,...)
Formatted output to a file descriptor.
Definition qio.c:325
qlisttbl_getmulti
qlisttbl_data_t * qlisttbl_getmulti(qlisttbl_t *tbl, const char *name, bool newmem, size_t *numobjs)
qlisttbl->getmulti(): Finds all objects with given name and return a array of objects.
Definition qlisttbl.c:504
qlisttbl_put
bool qlisttbl_put(qlisttbl_t *tbl, const char *name, const void *data, size_t size)
qlisttbl->put(): Put an element to this table.
Definition qlisttbl.c:249
qlisttbl
qlisttbl_t * qlisttbl(int options)
Create a new Q_LIST linked-list container.
Definition qlisttbl.c:150
qlisttbl_putstrf
bool qlisttbl_putstrf(qlisttbl_t *tbl, const char *name, const char *format,...)
qlisttbl->putstrf(): Put a formatted string into this table.
Definition qlisttbl.c:314
qlisttbl_sort
void qlisttbl_sort(qlisttbl_t *tbl)
qlisttbl->sort(): Sort keys in this table.
Definition qlisttbl.c:826
qlisttbl_putint
bool qlisttbl_putint(qlisttbl_t *tbl, const char *name, int64_t num)
qlisttbl->putInt(): Put an integer into this table as string type.
Definition qlisttbl.c:345
qlisttbl_freemulti
void qlisttbl_freemulti(qlisttbl_data_t *objs)
qlisttbl->freemulti(): Deallocate object array returned by getmulti().
Definition qlisttbl.c:573
qlisttbl_removeobj
bool qlisttbl_removeobj(qlisttbl_t *tbl, const qlisttbl_obj_t *obj)
qlisttbl->removeobj(): Remove objects with given object pointer.
Definition qlisttbl.c:636
qlisttbl_size
size_t qlisttbl_size(qlisttbl_t *tbl)
qlisttbl->size(): Returns the number of elements in this table.
Definition qlisttbl.c:799
qlisttbl_free
void qlisttbl_free(qlisttbl_t *tbl)
qlisttbl->free(): Free qlisttbl_t
Definition qlisttbl.c:1041
qlisttbl_lock
void qlisttbl_lock(qlisttbl_t *tbl)
qlisttbl->lock(): Enter critical section.
Definition qlisttbl.c:1021
qlisttbl_unlock
void qlisttbl_unlock(qlisttbl_t *tbl)
qlisttbl->unlock(): Leave critical section.
Definition qlisttbl.c:1031
qlisttbl_getstr
char * qlisttbl_getstr(qlisttbl_t *tbl, const char *name, bool newmem)
qlisttbl->getstr(): Finds an object with given name and returns as string type.
Definition qlisttbl.c:442
qlisttbl_putstr
bool qlisttbl_putstr(qlisttbl_t *tbl, const char *name, const char *str)
qlisttbl->putstr(): Put a string into this table.
Definition qlisttbl.c:296
qlisttbl_clear
void qlisttbl_clear(qlisttbl_t *tbl)
qlisttbl->clear(): Removes all of the elements from this table.
Definition qlisttbl.c:862
qlisttbl_save
bool qlisttbl_save(qlisttbl_t *tbl, const char *filepath, char sepchar, bool encode)
qlisttbl->save(): Save qlisttbl as plain text format Dumping direction is always forward(from the top...
Definition qlisttbl.c:895
qlisttbl_debug
bool qlisttbl_debug(qlisttbl_t *tbl, FILE *out)
qlisttbl->debug(): Print out stored elements for debugging purpose.
Definition qlisttbl.c:993
qlisttbl_getnext
bool qlisttbl_getnext(qlisttbl_t *tbl, qlisttbl_obj_t *obj, const char *name, bool newmem)
qlisttbl->getnext(): Get next element.
Definition qlisttbl.c:727
qlisttbl_remove
size_t qlisttbl_remove(qlisttbl_t *tbl, const char *name)
qlisttbl->remove(): Remove matched objects with given name.
Definition qlisttbl.c:593
qlisttbl_get
void * qlisttbl_get(qlisttbl_t *tbl, const char *name, size_t *size, bool newmem)
qlisttbl->get(): Finds an object with given name.
Definition qlisttbl.c:392
qlisttbl_load
ssize_t qlisttbl_load(qlisttbl_t *tbl, const char *filepath, char sepchar, bool decode)
qlisttbl->load(): Load and append entries from given filepath Loading direction is always appending a...
Definition qlisttbl.c:941
qlisttbl_getint
int64_t qlisttbl_getint(qlisttbl_t *tbl, const char *name)
qlisttbl->getint(): Finds an object with given name and returns as integer type.
Definition qlisttbl.c:460
qstrtrim
char * qstrtrim(char *str)
Remove white spaces(including CR, LF) from head and tail of the string.
Definition qstring.c:55
qtime_gmt_str
char * qtime_gmt_str(time_t utctime)
Get GMT time string formatted like 'Wed, 11-Nov-2007 23:19:25 GMT'.
Definition qtime.c:174