qLibc

qtreetbl.c
Go to the documentation of this file.
1/******************************************************************************
2 * qLibc
3 *
4 * Copyright (c) 2010-2023 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 qtreetbl.c Tree Table container that implements the Left-Leaning
31 * Red-Black BST algorithm.
32 *
33 * qtreetbl implements a binary search tree that allows efficient in-order
34 * traversal with O(log n) search time.
35 *
36 * The algorithm qtreetbl specifically implements is the left-leaning red-black
37 * tree algorithm invented in 2008 by Robert Sedgewick. A left-leaning red–black
38 * tree is a type of self-balancing binary search tree and it is a variant of the
39 * red–black tree which was invented in 1972 by Rudolf Bayer.
40 *
41 * References:
42 * - http://en.wikipedia.org/wiki/Left-leaning_red-black_tree
43 * - https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf
44 *
45 * (E)
46 * ______________|______________
47 * / \
48 * (C) (R)
49 * / \ / \
50 * (A,B) (D) (I,N) (S,X)
51 *
52 * <2-3-4 Tree Data Structure>
53 *
54 * E
55 * ______________|______________
56 * / \
57 * C R
58 * _______|_______ _______|_______
59 * / \ / \
60 * B D N X
61 * // // //
62 * A* I* S*
63 *
64 * <Left-Leaning Red-Black Tree Data Structure>
65 * Nodes A, I and S are nodes with RED upper link. Others are BLACK
66 *
67 *
68 * The Red-Black BST algorithm has been one of the popular BST algorithms
69 * especially for in-memory operation. The Left-Leaning version of Red-Black
70 * especially improves performance and reduces overall complexity.
71 *
72 * Since it's relatively new algorithm, there's not many practically functional
73 * working codes yet other than proof of concept kinds. Here's one of fully
74 * functional codes and I, Seungyoung Kim, would like to dedicate this code to
75 * the genius inventor Robert Sedgewick and to all the great qLibc users.
76 *
77 * Additional features:
78 * - iterator.
79 * - find nearest key.
80 * - iteration from given key.
81 * - find min/max key.
82 *
83 * @code
84 * qtreetbl_t *tbl = qtreetbl(QTREETBL_THREADSAFE);
85 *
86 * tbl->put(tbl, "KEY", "DATA", 4); // use putobj() for binary keys.
87 * void *data = tbl->get(tbl, "KEY", false); // use getobj() for binary keys.
88 * tbl->remove(tbl, "KEY"); // use remove_by_key() for binary keys.
89 *
90 * // iteration example
91 * qtreetbl_obj_t obj;
92 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
93 * tbl->lock(tbl); // for thread safety
94 * while (tbl->getnext(tbl, &obj, false) == true) {
95 * ...
96 * }
97 * tbl->unlock(tbl);
98 *
99 * // find a nearest key then iterate from there
100 * tbl->lock(tbl);
101 * qtreetbl_obj_t obj = tbl->find_nearest(tbl, "K", sizeof("K"), false);
102 * tbl->lock(tbl); // for thread safety
103 * while (tbl->getnext(tbl, &obj, false) == true) {
104 * ...
105 * }
106 * tbl->unlock(tbl);
107 *
108 * // find minimum value using custom comparator
109 * tbl->set_compare(tbl, my_compare_func); // default is byte comparator
110 * void *min = tbl->find_min(tbl, &keysize);
111 *
112 * // get total number of objects in the table
113 * size_t num = tbl->size(tbl);
114 *
115 * tbl->free(tbl);
116 * @endcode
117 */
118
119#include <stdio.h>
120#include <stdlib.h>
121#include <stdbool.h>
122#include <string.h>
123#include <stdarg.h>
124#include <errno.h>
125#include <assert.h>
126#include "qinternal.h"
127#include "utilities/qstring.h"
128#include "containers/qtreetbl.h"
129
130#ifndef _DOXYGEN_SKIP
131
132/* internal functions */
133#define LLRB234 // comment to build 2-3 variant
134 static bool is_red(qtreetbl_obj_t *obj);
135 static qtreetbl_obj_t *flip_color(qtreetbl_obj_t *obj);
136 static qtreetbl_obj_t *rotate_left(qtreetbl_obj_t *obj);
137 static qtreetbl_obj_t *rotate_right(qtreetbl_obj_t *obj);
138 static qtreetbl_obj_t *move_red_left(qtreetbl_obj_t *obj);
139 static qtreetbl_obj_t *move_red_right(qtreetbl_obj_t *obj);
140 static qtreetbl_obj_t *find_min(qtreetbl_obj_t *obj);
141 static qtreetbl_obj_t *find_max(qtreetbl_obj_t *obj);
142 static qtreetbl_obj_t *remove_min(qtreetbl_obj_t *obj);
143 static qtreetbl_obj_t *fix(qtreetbl_obj_t *obj);
144 static qtreetbl_obj_t *find_obj(qtreetbl_t *tbl, const void *name,
145 size_t namesize);
146 static qtreetbl_obj_t *new_obj(bool red, const void *name, size_t namesize,
147 const void *data, size_t datasize);
148 static qtreetbl_obj_t *put_obj(qtreetbl_t *tbl, qtreetbl_obj_t *obj,
149 const void *name, size_t namesize,
150 const void *data, size_t datasize);
151 static qtreetbl_obj_t *remove_obj(qtreetbl_t *tbl, qtreetbl_obj_t *obj,
152 const void *name, size_t namesize);
153 static void free_objs(qtreetbl_obj_t *obj);
154 static uint8_t reset_iterator(qtreetbl_t *tbl);
155
156 struct branch_obj_s {
157 struct branch_obj_s *p;
158 char *s;
159};
160 static void print_branch(struct branch_obj_s *branch, FILE *out);
161 static void print_node(qtreetbl_obj_t *obj, FILE *out, struct branch_obj_s *prev,
162 bool right);
163#endif
164
165/**
166 * Initialize a tree table.
167 *
168 * @param options combination of initialization options.
169 *
170 * @return a pointer of malloced qtreetbl_t, otherwise returns NULL.
171 * @retval errno will be set in error condition.
172 * - ENOMEM : Memory allocation failure.
173 *
174 * @code
175 * qtreetbl_t *tbl = qtreetbl(0);
176 * @endcode
177 *
178 * @note
179 * Available options:
180 * - QTREETBL_THREADSAFE - make it thread-safe.
181 */
182qtreetbl_t *qtreetbl(int options) {
183 qtreetbl_t *tbl = (qtreetbl_t *) calloc(1, sizeof(qtreetbl_t));
184 if (tbl == NULL)
185 goto malloc_failure;
186
187 // handle options.
188 if (options & QTREETBL_THREADSAFE) {
189 Q_MUTEX_NEW(tbl->qmutex, true);
190 if (tbl->qmutex == NULL)
191 goto malloc_failure;
192 }
193
194 // assign methods
195 tbl->set_compare = qtreetbl_set_compare;
196
197 tbl->put = qtreetbl_put;
198 tbl->putstr = qtreetbl_putstr;
199 tbl->putstrf = qtreetbl_putstrf;
200 tbl->putobj = qtreetbl_putobj;
201
202 tbl->get = qtreetbl_get;
203 tbl->getstr = qtreetbl_getstr;
204 tbl->getobj = qtreetbl_getobj;
205
206 tbl->remove = qtreetbl_remove;
207 tbl->removeobj = qtreetbl_removeobj;
208
209 tbl->getnext = qtreetbl_getnext;
210
211 tbl->find_min = qtreetbl_find_min;
212 tbl->find_max = qtreetbl_find_max;
213 tbl->find_nearest = qtreetbl_find_nearest;
214
215 tbl->size = qtreetbl_size;
216 tbl->clear = qtreetbl_clear;
217
218 tbl->lock = qtreetbl_lock;
219 tbl->unlock = qtreetbl_unlock;
220
221 tbl->free = qtreetbl_free;
222 tbl->debug = qtreetbl_debug;
223
224 // Set default comparison function.
225 qtreetbl_set_compare(tbl, qtreetbl_byte_cmp);
226 reset_iterator(tbl);
227
228 return tbl;
229
230 malloc_failure:
231 errno = ENOMEM;
232 if (tbl != NULL) {
233 assert(tbl->qmutex == NULL);
234 qtreetbl_free(tbl);
235 }
236 return NULL;
237}
238
239/**
240 * qtreetbl->set_compare(): Set user comparator.
241 *
242 * @param tbl qtreetbl_t container pointer.
243 * @param cmp a pointer to the user comparator function.
244 *
245 * @note
246 * By default, qtreetbl uses byte comparator that works for
247 * both binary type key and string type key. Please refer
248 * qtreetbl_byte_cmp() for your idea to make your own comparator.
249 */
250 void qtreetbl_set_compare(qtreetbl_t *tbl,
251 int (*cmp)(const void *name1, size_t namesize1,
252 const void *name2, size_t namesize2)) {
253 tbl->compare = cmp;
254}
255
256/**
257 * qtreetbl->put(): Put an object into this table with string type key.
258 *
259 * @param tbl qtreetbl_t container pointer.
260 * @param name key name.
261 * @param data data object.
262 * @param datasize size of data object.
263 *
264 * @return true if successful, otherwise returns false.
265 * @retval errno will be set in error condition.
266 * - EINVAL : Invalid argument.
267 * - ENOMEM : Memory allocation failure.
268 */
269 bool qtreetbl_put(qtreetbl_t *tbl, const char *name, const void *data,
270 size_t datasize) {
271 return qtreetbl_putobj(tbl,
272 name, (name != NULL) ? (strlen(name) + 1) : 0, data, datasize);
273}
274
275/**
276 * qtreetbl->putstr(): Put a string into this table.
277 *
278 * @param tbl qtreetbl container pointer.
279 * @param name key name.
280 * @param str string data.
281 *
282 * @return true if successful, otherwise returns false.
283 * @retval errno will be set in error condition.
284 * - EINVAL : Invalid argument.
285 * - ENOMEM : Memory allocation failure.
286 */
287 bool qtreetbl_putstr(qtreetbl_t *tbl, const char *name, const char *str) {
288 return qtreetbl_putobj(tbl,
289 name, (name != NULL) ? (strlen(name) + 1) : 0,
290 str, (str != NULL) ? (strlen(str) + 1) : 0);
291}
292
293/**
294 * qtreetbl->putstrf(): Put a formatted string into this table.
295 *
296 * @param tbl qtreetbl_t container pointer.
297 * @param name key name.
298 * @param format formatted string data.
299 *
300 * @return true if successful, otherwise returns false.
301 * @retval errno will be set in error condition.
302 * - EINVAL : Invalid argument.
303 * - ENOMEM : Memory allocation failure.
304 */
305 bool qtreetbl_putstrf(qtreetbl_t *tbl, const char *name, const char *format,
306 ...) {
307 char *str;
308 DYNAMIC_VSPRINTF(str, format);
309 if (str == NULL) {
310 errno = ENOMEM;
311 return false;
312 }
313
314 bool ret = qtreetbl_putstr(tbl, name, str);
315 free(str);
316 return ret;
317}
318
319/**
320 * qtreetbl->putobj(): Put an object data into this table with an object key.
321 *
322 * @param tbl qtreetbl_t container pointer.
323 * @param name key name.
324 * @param namesize key size.
325 * @param data data object.
326 * @param datasize size of data object.
327 *
328 * @return true if successful, otherwise returns false.
329 * @retval errno will be set in error condition.
330 * - EINVAL : Invalid argument.
331 * - ENOMEM : Memory allocation failure.
332 *
333 * @note
334 * This is the underlying put function which all other put methods use.
335 */
336 bool qtreetbl_putobj(qtreetbl_t *tbl, const void *name, size_t namesize,
337 const void *data, size_t datasize) {
338 if (name == NULL || namesize == 0) {
339 errno = EINVAL;
340 return false;
341 }
342
343 qtreetbl_lock(tbl);
344 errno = 0;
345 qtreetbl_obj_t *root = put_obj(tbl, tbl->root, name, namesize, data,
346 datasize);
347 if (root == NULL || errno == ENOMEM) {
348 qtreetbl_unlock(tbl);
349 return false;
350 }
351 root->red = false;
352 tbl->root = root;
353 qtreetbl_unlock(tbl);
354
355 return true;
356}
357
358/**
359 * qtreetbl->get(): Get an object from this table.
360 *
361 * @param tbl qtreetbl_t container pointer.
362 * @param name key name.
363 * @param datasize if not NULL, object size will be stored.
364 * @param newmem whether or not to allocate memory for the data.
365 *
366 * @return a pointer of data if the key is found, otherwise returns NULL.
367 * @retval errno will be set in error condition.
368 * - ENOENT : No such key found.
369 * - EINVAL : Invalid argument.
370 * - ENOMEM : Memory allocation failure.
371 *
372 * @code
373 * qtreetbl_t *tbl = qtreetbl(0);
374 * (...codes...)
375 *
376 * // with newmem flag unset
377 * size_t size;
378 * void *data = (struct myobj*)tbl->get(tbl, "key_name", &size, false);
379 *
380 * // with newmem flag set
381 * size_t size;
382 * void *data = (struct myobj*)tbl->get(tbl, "key_name", &size, true);
383 * free(data);
384 * @endcode
385 *
386 * @note
387 * If newmem flag is set, returned data will be malloced and should be
388 * deallocated by user. Otherwise returned pointer will point internal buffer
389 * directly and should not be de-allocated by user. In thread-safe mode,
390 * newmem flag must be set to true always.
391 */
392 void *qtreetbl_get(qtreetbl_t *tbl, const char *name, size_t *datasize,
393 bool newmem) {
394 return qtreetbl_getobj(tbl,
395 name, (name != NULL) ? (strlen(name) + 1) : 0, datasize, newmem);
396}
397
398/**
399 * qtreetbl->getstr(): Finds an object and returns it as string type.
400 *
401 * @param tbl qtreetbl_t container pointer.
402 * @param name key name.
403 * @param newmem whether or not to allocate memory for the data.
404 *
405 * @return a pointer to data if the key is found, otherwise returns NULL.
406 * @retval errno will be set in error condition.
407 * - ENOENT : No such key found.
408 * - EINVAL : Invalid argument.
409 * - ENOMEM : Memory allocation failure.
410 *
411 * @note
412 * If newmem flag is set, returned data will be malloced and should be
413 * deallocated by user. Otherwise returned pointer will point internal buffer
414 * directly and should not be de-allocated by user. In thread-safe mode,
415 * newmem flag must be set to true always.
416 */
417 char *qtreetbl_getstr(qtreetbl_t *tbl, const char *name, const bool newmem) {
418 return qtreetbl_getobj(tbl,
419 name, (name != NULL) ? (strlen(name) + 1) : 0, NULL, newmem);
420}
421
422/**
423 * qtreetbl->getobj(): Get an object from this table with an object name.
424 *
425 * @param tbl qtreetbl_t container pointer.
426 * @param name key name.
427 * @param namesize key size.
428 * @param datasize if not NULL, oject size will be stored.
429 * @param newmem whether or not to allocate memory for the data.
430 *
431 * @return a pointer of data if the key is found, otherwise returns NULL.
432 * @retval errno will be set in error condition.
433 * - ENOENT : No such key found.
434 * - EINVAL : Invalid argument.
435 * - ENOMEM : Memory allocation failure.
436 *
437 * @note
438 * If newmem flag is set, returned data will be malloced and should be
439 * deallocated by user. Otherwise returned pointer will point internal buffer
440 * directly and should not be de-allocated by user. In thread-safe mode,
441 * newmem flag must be set to true always.
442 */
443 void *qtreetbl_getobj(qtreetbl_t *tbl, const void *name, size_t namesize,
444 size_t *datasize, bool newmem) {
445 if (name == NULL || namesize == 0) {
446 errno = EINVAL;
447 return NULL;
448 }
449
450 qtreetbl_lock(tbl);
451 qtreetbl_obj_t *obj = find_obj(tbl, name, namesize);
452 void *data = NULL;
453 if (obj != NULL) {
454 data = (newmem) ? qmemdup(obj->data, obj->datasize) : obj->data;
455 if (datasize != NULL) {
456 *datasize = (data != NULL) ? obj->datasize : 0;
457 }
458 }
459 qtreetbl_unlock(tbl);
460 return data;
461}
462
463/**
464 * qtreetbl->remove(): Remove an object from this table.
465 *
466 * @param tbl qtreetbl_t container pointer.
467 * @param name key name.
468 *
469 * @return true if successful, otherwise(not found) returns false.
470 * @retval errno will be set in error condition.
471 * - ENOENT : No such key found.
472 * - EINVAL : Invalid argument.
473 */
474 bool qtreetbl_remove(qtreetbl_t *tbl, const char *name) {
475 return qtreetbl_removeobj(tbl,
476 name, (name != NULL) ? strlen(name) + 1 : 0);
477}
478
479/**
480 * qtreetbl->remove(): Remove an object from this table with an object name.
481 *
482 * @param tbl qtreetbl_t container pointer.
483 * @param name key name.
484 * @param name key size.
485 *
486 * @return true if successful, otherwise(not found) returns false.
487 * @retval errno will be set in error condition.
488 * - ENOENT : No such key found.
489 * - EINVAL : Invalid argument.
490 */
491 bool qtreetbl_removeobj(qtreetbl_t *tbl, const void *name, size_t namesize) {
492 if (name == NULL) {
493 errno = EINVAL;
494 return false;
495 }
496
497 qtreetbl_lock(tbl);
498 errno = 0;
499 tbl->root = remove_obj(tbl, tbl->root, name, namesize);
500 if (tbl->root != NULL) {
501 tbl->root->red = false;
502 }
503 bool removed = (errno != ENOENT) ? true : false;
504 qtreetbl_unlock(tbl);
505
506 return removed;
507}
508
509/**
510 * qtreetbl->getnext(): Get next element.
511 *
512 * @param tbl qtreetbl_t container pointer.
513 * @param obj found data will be stored in this object.
514 * @param newmem whether or not to allocate memory for the data.
515 *
516 * @return true if found otherwise returns false.
517 * @retval errno will be set in error condition.
518 * - ENOENT : No next element.
519 * - EINVAL : Invalid argument.
520 * - ENOMEM : Memory allocation failure.
521 *
522 * @code
523 * [Iteration example from the beginning]
524 *
525 * qtreetbl_obj_t obj;
526 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
527 * tbl->lock(tbl); // lock it when thread condition is expected
528 * while(tbl->getnext(tbl, &obj, false) == true) {
529 * //
530 * // obj.name : key data
531 * // obj.namesize : key size
532 * // obj.data : data
533 * // obj.datasize : data size
534 * //
535 * // Do free obj.name and obj.data if newmem is set to true;
536 * }
537 * tbl->unlock(tbl);
538 * @endcode
539 *
540 * @code
541 * [Iteration example from given point]
542 *
543 * tbl->lock(tbl); // to guarantee no table update during the run
544 * qtreetbl_obj_t obj = tbl->find_nearest(tbl, "F", sizeof("F"), false);
545 * while (tbl->getnext(tbl, &obj, false) == true) { // newmem is false
546 * // If a tree has 5 objects, A, C, E, G and I.
547 * // The iteration sequence from nearest "F" will be: E->G->I->A->C
548 * }
549 * tbl->unlock(tbl);
550 *
551 * @endcode
552 *
553 * @code
554 * [Removal example in iteration loop]
555 *
556 * qtreetbl_obj_t obj;
557 * memset((void*)&obj, 0, sizeof(obj));
558 * tbl->lock(tbl);
559 * while (tbl->getnext(tbl, &obj, false) == true) {
560 * if (...condition...) {
561 * char *name = qmemdup(obj.name, obj.namesize); // keep the name
562 * size_t namesize = obj.namesize; // for removal argument
563 * tbl->removeobj(tbl, obj.name, obj.namesize); // remove
564 * obj = tbl->find_nearest(tbl, name, namesize, false); // rewind one step back
565 * free(name); // clean up
566 * }
567 * }
568 * tbl->unlock(tbl);
569 * @endcode
570 *
571 * @note
572 * - Data insertion or deletion can be made during the traversal, but in that
573 * case iterator doesn't guarantee full sweep and possibly skip some visits.
574 * When deletion happens in getnext() loop, use find_nearest() to rewind the
575 * iterator one step back.
576 * - Object obj should be initialized with 0 by using memset() before first call.
577 * - If newmem flag is true, user should de-allocate obj.name and obj.data
578 * resources.
579 */
580 bool qtreetbl_getnext(qtreetbl_t *tbl, qtreetbl_obj_t *obj, const bool newmem) {
581 if (obj == NULL) {
582 errno = EINVAL;
583 return NULL;
584 }
585
586 uint8_t tid = obj->tid;
587 if (obj->next == NULL) { // first time call
588 if (tbl->root == NULL) {
589 return false;
590 }
591 // get a new iterator id
592 tid = reset_iterator(tbl);;
593 }
594
595 qtreetbl_obj_t *cursor = ((obj->next != NULL) ? obj->next : tbl->root);
596 while (cursor != NULL) {
597 if (cursor->left != NULL && cursor->left->tid != tid) {
598 cursor->left->next = cursor;
599 cursor = cursor->left;
600 continue;
601 } else if (cursor->tid != tid) {
602 cursor->tid = tid;
603 *obj = *cursor;
604 if (newmem) {
605 obj->name = qmemdup(cursor->name, cursor->namesize);
606 obj->data = qmemdup(cursor->data, cursor->datasize);
607 }
608 obj->next = cursor; // store original address in tree for next iteration
609 return true;
610 } else if (cursor->right != NULL && cursor->right->tid != tid) {
611 cursor->right->next = cursor;
612 cursor = cursor->right;
613 continue;
614 }
615 cursor = cursor->next;
616 }
617
618 // end of travel, reset iterator to allow iteration start over in next call
619 reset_iterator(tbl);
620 return false;
621}
622
623/**
624 * qtreetbl->find_min(): Find the name of the leftmost object.
625 *
626 * @param tbl qtreetbl_t container pointer.
627 * @param namesize if not NULL, the size of key name will be stored.
628 *
629 * @return malloced memory copying the key name.
630 *
631 * @note
632 * It's user's responsibility to free the return.
633 */
634 void *qtreetbl_find_min(qtreetbl_t *tbl, size_t *namesize) {
635 qtreetbl_lock(tbl);
636 qtreetbl_obj_t *obj = find_min(tbl->root);
637 if (obj == NULL) {
638 errno = ENOENT;
639 qtreetbl_unlock(tbl);
640 return NULL;
641 }
642
643 if (namesize != NULL) {
644 *namesize = obj->namesize;
645 }
646 void *name = qmemdup(obj->name, obj->namesize);
647 qtreetbl_unlock(tbl);
648 return name;
649}
650
651/**
652 * qtreetbl->find_max(): Find the name of the rightmost object.
653 *
654 * @param tbl qtreetbl_t container pointer.
655 * @param namesize if not NULL, the size of key name will be stored.
656 *
657 * @return malloced memory copying the key name.
658 *
659 * @note
660 * It's user's responsibility to free the return.
661 */
662 void *qtreetbl_find_max(qtreetbl_t *tbl, size_t *namesize) {
663 qtreetbl_lock(tbl);
664 qtreetbl_obj_t *obj = find_max(tbl->root);
665 if (obj == NULL) {
666 errno = ENOENT;
667 qtreetbl_unlock(tbl);
668 return NULL;
669 }
670
671 if (namesize != NULL) {
672 *namesize = obj->namesize;
673 }
674 void *name = qmemdup(obj->name, obj->namesize);
675 qtreetbl_unlock(tbl);
676 return name;
677}
678
679/**
680 * qtreetbl->find_nearest(): Find an object with matching key or nearest.
681 *
682 * find_nearest() returns matching key or nearest key object. If there's
683 * no keys in the table. It'll return empty qtreetbl_obj_t object
684 * with errno ENOENT.
685 *
686 * @param tbl qtreetbl_t container pointer.
687 * @param name key name.
688 * @param namesize key size.
689 * @param newmem whether or not to allocate memory for the data.
690 *
691 * @return qtreetbl_obj_t object.
692 *
693 * @retval errno will be set in error condition.
694 * - ENOENT : No next element.
695 * - EINVAL : Invalid argument.
696 * - ENOMEM : Memory allocation failure.
697 *
698 * @code
699 * Data Set : A B C D E I N R S X
700 * find_nearest("0") => "A" // no smaller key available, so "A"
701 * find_nearest("C") => "C" // matching key found
702 * find_nearest("F") => "E" // "E" is nearest smaller key from "F"
703 * @endcode
704 *
705 * @note
706 * When there's no matching key it look for closest smaller key
707 * in the neighbors. The only exception when it returns bigger key
708 * than given search key is that when there's no smaller keys available
709 * in the table. In such case, it'll return the nearest bigger key.
710 */
711qtreetbl_obj_t qtreetbl_find_nearest(qtreetbl_t *tbl, const void *name,
712 size_t namesize, bool newmem) {
713 qtreetbl_obj_t retobj;
714 memset((void*) &retobj, 0, sizeof(retobj));
715
716 if (name == NULL || namesize == 0) {
717 errno = EINVAL;
718 return retobj;
719 }
720
721 qtreetbl_lock(tbl);
722 qtreetbl_obj_t *obj, *lastobj;
723 for (obj = lastobj = tbl->root; obj != NULL;) {
724 int cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
725 if (cmp == 0) {
726 break;
727 }
728 lastobj = obj;
729 if (cmp < 0) {
730 if (obj->left != NULL) {
731 obj->left->next = obj;
732 }
733 obj = obj->left;
734 } else {
735 if (obj->right != NULL) {
736 obj->right->next = obj;
737 }
738 obj = obj->right;
739 }
740 }
741
742 if (obj == NULL) {
743 for (obj = lastobj;
744 obj != NULL && (tbl->compare(name, namesize, obj->name, obj->namesize) < 0);
745 obj = obj->next);
746 if (obj == NULL) {
747 obj = lastobj;
748 }
749 }
750
751 if (obj != NULL) {
752 retobj = *obj;
753 if (newmem) {
754 retobj.name = qmemdup(obj->name, obj->namesize);
755 retobj.data = qmemdup(obj->data, obj->datasize);
756 }
757 // set travel info to be used for iteration in getnext()
758 retobj.tid = tbl->tid;
759 retobj.next = obj;
760 } else {
761 errno = ENOENT;
762 }
763
764 qtreetbl_unlock(tbl);
765 return retobj;
766}
767
768/**
769 * qtreetbl->size(): Returns the number of keys in the table.
770 *
771 * @param tbl qtreetbl_t container pointer.
772 *
773 * @return number of elements stored.
774 */
775 size_t qtreetbl_size(qtreetbl_t *tbl) {
776 return tbl->num;
777}
778
779/**
780 * qtreetbl->clear(): Clears the table so that it contains no keys.
781 *
782 * @param tbl qtreetbl_t container pointer.
783 */
784 void qtreetbl_clear(qtreetbl_t *tbl) {
785 qtreetbl_lock(tbl);
786 free_objs(tbl->root);
787 tbl->root = NULL;
788 tbl->num = 0;
789 qtreetbl_unlock(tbl);
790}
791
792/**
793 * qtreetbl->lock(): Enter critical section.
794 *
795 * @param tbl qtreetbl_t container pointer.
796 *
797 * @note
798 * From user side, normally locking operation is only needed when traverse
799 * all elements using qtreetbl->getnext().
800 *
801 * @note
802 * This operation will do nothing if QTREETBL_THREADSAFE option was not
803 * given at the initialization time.
804 */
805 void qtreetbl_lock(qtreetbl_t *tbl) {
806 Q_MUTEX_ENTER(tbl->qmutex);
807}
808
809/**
810 * qtreetbl->unlock(): Leave critical section.
811 *
812 * @param tbl qtreetbl_t container pointer.
813 *
814 * @note
815 * This operation will do nothing if QTREETBL_THREADSAFE option was not
816 * given at the initialization time.
817 */
818 void qtreetbl_unlock(qtreetbl_t *tbl) {
819 Q_MUTEX_LEAVE(tbl->qmutex);
820}
821
822/**
823 * qtreetbl->free(): De-allocate the table.
824 *
825 * @param tbl qtreetbl_t container pointer.
826 */
827 void qtreetbl_free(qtreetbl_t *tbl) {
828 qtreetbl_clear(tbl);
829 Q_MUTEX_DESTROY(tbl->qmutex);
830 free(tbl);
831}
832
833 int qtreetbl_byte_cmp(const void *name1, size_t namesize1, const void *name2,
834 size_t namesize2) {
835 size_t minsize = (namesize1 < namesize2) ? namesize1 : namesize2;
836 int cmp = memcmp(name1, name2, minsize);
837 if (cmp != 0 || namesize1 == namesize2) {
838 return cmp;
839 }
840 return (namesize1 < namesize2) ? -1 : +1;
841}
842
843/**
844 * qtreetbl->debug(): Print the internal tree structure in text.
845 *
846 * @param tbl qtreetbl_t container pointer.
847 * @param out output stream.
848 *
849 * @return true if successful, otherwise returns false.
850 * @retval errno will be set in error condition.
851 * - EIO : Invalid output stream.
852 *
853 * @code
854 * Example output:
855 *
856 * ┌───9
857 * │ └──[8]
858 * ┌───7
859 * │ │ ┌───6
860 * │ └──[5]
861 * │ └───4
862 * 3
863 * │ ┌───2
864 * └───1
865 * └───0
866 * @endcode
867 * @note
868 * Red nodes are wrapped in `[]`.
869 * In this example, 5 and 8 are Red nodes.
870 */
871 bool qtreetbl_debug(qtreetbl_t *tbl, FILE *out) {
872 if (out == NULL) {
873 errno = EIO;
874 return false;
875 }
876
877 qtreetbl_lock(tbl);
878 print_node(tbl->root, out, NULL, false);
879 qtreetbl_unlock(tbl);
880 return true;
881}
882
883/**
884 * Verifies that root property of the red-black tree is satisfied.
885 *
886 * Root property: The root is black.
887 *
888 * @param tbl qtreetbl_t container pointer.
889 */
890 int node_check_root(qtreetbl_t *tbl) {
891 if (tbl == NULL) {
892 return 1;
893 }
894
895 if (is_red(tbl->root)) {
896 return 1;
897 }
898 return 0;
899}
900
901/**
902 * Verifies that red property of the red-black tree is satisfied.
903 *
904 * Red property: If a node is red, then both its children are black.
905 *
906 * @param tbl qtreetbl_t container pointer.
907 * @param obj qtreetbl_obj_t object pointer.
908 */
909 int node_check_red(qtreetbl_t *tbl, qtreetbl_obj_t *obj) {
910 if (obj == NULL) {
911 return 0;
912 }
913
914 if (is_red(obj)) {
915 if (is_red(obj->right) || is_red(obj->left)) {
916 return 1;
917 }
918 }
919
920 if (node_check_red(tbl, obj->right)) {
921 return 1;
922 }
923 if (node_check_red(tbl, obj->left)) {
924 return 1;
925 }
926
927 return 0;
928}
929
930/**
931 * Verifies that black property of the red-black tree is satisfied.
932 *
933 * Black property: For each node, all simple paths from the node to
934 * descendant leaves contain the same number of black nodes.
935 *
936 * @param tbl qtreetbl_t container pointer.
937 * @param obj qtreetbl_obj_t object pointer.
938 * @param path_len black path length.
939 */
940 int node_check_black(qtreetbl_t *tbl, qtreetbl_obj_t *obj, int *path_len) {
941 if (obj == NULL) {
942 *path_len = 1;
943 return 0;
944 }
945
946 int right_path_len;
947 if (node_check_black(tbl, obj->right, &right_path_len)) {
948 return 1;
949 }
950 int left_path_len;
951 if (node_check_black(tbl, obj->left, &left_path_len)) {
952 return 1;
953 }
954
955 if (right_path_len != left_path_len) {
956 return 1;
957 }
958 *path_len = (!is_red(obj)) ? (right_path_len + 1) : right_path_len;
959
960 return 0;
961}
962
963/**
964 * Verifies that LLRB property of the left-leaning red-black tree is satisfied.
965 *
966 * LLRB property: 3-nodes always lean to the left and 4-nodes are balanced.
967 *
968 * @param tbl qtreetbl_t container pointer.
969 * @param obj qtreetbl_obj_t object pointer.
970 */
971 int node_check_llrb(qtreetbl_t *tbl, qtreetbl_obj_t *obj) {
972 if (obj == NULL) {
973 return 0;
974 }
975
976 if (is_red(obj->right) && !is_red(obj->left)) {
977 return 1;
978 }
979
980 if (node_check_llrb(tbl, obj->right)) {
981 return 1;
982 }
983 if (node_check_llrb(tbl, obj->left)) {
984 return 1;
985 }
986
987 return 0;
988}
989
990/**
991 * Verifies that the invariants of the red-black tree are satisfied.
992 *
993 * Root property: The root is black.
994 * Red property: If a node is red, then both its children are black.
995 * Black property: For each node, all simple paths from the node to
996 * descendant leaves contain the same number of black nodes.
997 * LLRB property: 3-nodes always lean to the left and 4-nodes are balanced.
998 *
999 * @param tbl qtreetbl_t container pointer.
1000 */
1001 int qtreetbl_check(qtreetbl_t *tbl) {
1002 if (tbl == NULL) {
1003 return 0;
1004 }
1005
1006 if (node_check_root(tbl)) {
1007 return 1;
1008 }
1009 if (node_check_red(tbl, tbl->root)) {
1010 return 2;
1011 }
1012 int path_len = 0;
1013 if (node_check_black(tbl, tbl->root, &path_len)) {
1014 return 3;
1015 }
1016 if (node_check_llrb(tbl, tbl->root)) {
1017 return 4;
1018 }
1019
1020 return 0;
1021}
1022
1023#ifndef _DOXYGEN_SKIP
1024
1025 static bool is_red(qtreetbl_obj_t *obj) {
1026 return (obj != NULL) ? obj->red : false;
1027}
1028
1029uint32_t _q_treetbl_flip_color_cnt = 0;
1030 static qtreetbl_obj_t *flip_color(qtreetbl_obj_t *obj) {
1031 obj->red = !(obj->red);
1032 obj->left->red = !(obj->left->red);
1033 obj->right->red = !(obj->right->red);
1034 _q_treetbl_flip_color_cnt++;
1035 return obj;
1036}
1037
1038uint32_t _q_treetbl_rotate_left_cnt = 0;
1039 static qtreetbl_obj_t *rotate_left(qtreetbl_obj_t *obj) {
1040 qtreetbl_obj_t *x = obj->right;
1041 obj->right = x->left;
1042 x->left = obj;
1043 x->red = x->left->red;
1044 x->left->red = true;
1045 _q_treetbl_rotate_left_cnt++;
1046 return x;
1047}
1048
1049uint32_t _q_treetbl_rotate_right_cnt = 0;
1050 static qtreetbl_obj_t *rotate_right(qtreetbl_obj_t *obj) {
1051 qtreetbl_obj_t *x = obj->left;
1052 obj->left = x->right;
1053 x->right = obj;
1054 x->red = x->right->red;
1055 x->right->red = true;
1056 _q_treetbl_rotate_right_cnt++;
1057 return x;
1058}
1059
1060 static qtreetbl_obj_t *move_red_left(qtreetbl_obj_t *obj) {
1061 flip_color(obj);
1062 if (is_red(obj->right->left)) {
1063 obj->right = rotate_right(obj->right);
1064 obj = rotate_left(obj);
1065 flip_color(obj);
1066#ifdef LLRB234
1067 // 2-3-4 exclusive
1068 if (is_red(obj->right->right)) {
1069 obj->right = rotate_left(obj->right);
1070 }
1071#endif
1072 }
1073 return obj;
1074}
1075
1076 static qtreetbl_obj_t *move_red_right(qtreetbl_obj_t *obj) {
1077 flip_color(obj);
1078 if (is_red(obj->left->left)) {
1079 obj = rotate_right(obj);
1080 flip_color(obj);
1081 }
1082 return obj;
1083}
1084
1085 static qtreetbl_obj_t *find_min(qtreetbl_obj_t *obj) {
1086 if (obj == NULL) {
1087 errno = ENOENT;
1088 return NULL;
1089 }
1090
1091 for (; obj->left != NULL; obj = obj->left);
1092 return obj;
1093}
1094
1095 static qtreetbl_obj_t *find_max(qtreetbl_obj_t *obj) {
1096 if (obj == NULL) {
1097 errno = ENOENT;
1098 return NULL;
1099 }
1100
1101 for (; obj->right != NULL; obj = obj->right);
1102 return obj;
1103}
1104
1105 static qtreetbl_obj_t *remove_min(qtreetbl_obj_t *obj) {
1106 if (obj->left == NULL) {
1107 // 3-nodes are left-leaning, so this is a leaf.
1108 free(obj->name);
1109 free(obj->data);
1110 return NULL;
1111 }
1112 if (!is_red(obj->left) && !is_red(obj->left->left)) {
1113 obj = move_red_left(obj);
1114 }
1115 obj->left = remove_min(obj->left);
1116 return fix(obj);
1117}
1118
1119 static qtreetbl_obj_t *fix(qtreetbl_obj_t *obj) {
1120 // rotate right red to left
1121 if (is_red(obj->right)) {
1122#ifdef LLRB234
1123 // 2-3-4 exclusive
1124 if (is_red(obj->right->left)) {
1125 obj->right = rotate_right(obj->right);
1126 }
1127#endif
1128 obj = rotate_left(obj);
1129 }
1130 // rotate left red-red to right
1131 if (is_red(obj->left) && is_red(obj->left->left)) {
1132 obj = rotate_right(obj);
1133 }
1134#ifndef LLRB234
1135 // split 4-nodes (2-3 exclusive)
1136 if (is_red(obj->left) && is_red(obj->right)) {
1137 flip_color(obj);
1138 }
1139#endif
1140 return obj;
1141}
1142
1143 static qtreetbl_obj_t *find_obj(qtreetbl_t *tbl, const void *name,
1144 size_t namesize) {
1145 if (name == NULL || namesize == 0) {
1146 errno = EINVAL;
1147 return NULL;
1148 }
1149
1150 qtreetbl_obj_t *obj;
1151 for (obj = tbl->root; obj != NULL;) {
1152 int cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
1153 if (cmp == 0) {
1154 return obj;
1155 }
1156 obj = (cmp < 0) ? obj->left : obj->right;
1157 }
1158
1159 errno = ENOENT;
1160 return NULL;
1161}
1162
1163 static qtreetbl_obj_t *new_obj(bool red, const void *name, size_t namesize,
1164 const void *data, size_t datasize) {
1165 qtreetbl_obj_t *obj = (qtreetbl_obj_t *) calloc(1, sizeof(qtreetbl_obj_t));
1166 void *copyname = qmemdup(name, namesize);
1167 void *copydata = qmemdup(data, datasize);
1168
1169 if (obj == NULL || copyname == NULL) {
1170 errno = ENOMEM;
1171 free(obj);
1172 free(copyname);
1173 free(copydata);
1174 return NULL;
1175 }
1176
1177 obj->red = red;
1178 obj->name = copyname;
1179 obj->namesize = namesize;
1180 obj->data = copydata;
1181 obj->datasize = datasize;
1182
1183 return obj;
1184}
1185
1186 static qtreetbl_obj_t *put_obj(qtreetbl_t *tbl, qtreetbl_obj_t *obj,
1187 const void *name, size_t namesize,
1188 const void *data, size_t datasize) {
1189 if (obj == NULL) {
1190 tbl->num++;
1191 return new_obj(true, name, namesize, data, datasize);
1192 }
1193
1194#ifdef LLRB234
1195 // split 4-nodes on the way down (2-3-4 exclusive)
1196 if (is_red(obj->left) && is_red(obj->right)) {
1197 flip_color(obj);
1198 }
1199#endif
1200
1201 int cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
1202 if (cmp == 0) { // existing key found
1203 void *copydata = qmemdup(data, datasize);
1204 if (copydata != NULL) {
1205 free(obj->data);
1206 obj->data = copydata;
1207 obj->datasize = datasize;
1208 }
1209 } else if (cmp < 0) {
1210 obj->left = put_obj(tbl, obj->left, name, namesize, data, datasize);
1211 } else {
1212 obj->right = put_obj(tbl, obj->right, name, namesize, data, datasize);
1213 }
1214
1215 // fix right-leaning reds on the way up
1216 if (is_red(obj->right) && !is_red(obj->left)) {
1217 obj = rotate_left(obj);
1218 }
1219
1220 // fix two reds in a row on the way up
1221 if (is_red(obj->left) && is_red(obj->left->left)) {
1222 obj = rotate_right(obj);
1223 }
1224
1225#ifndef LLRB234
1226 // split 4-nodes on the way up (2-3 exclusive)
1227 if (is_red(obj->left) && is_red(obj->right)) {
1228 flip_color(obj);
1229 }
1230#endif
1231
1232 // return new root
1233 return obj;
1234}
1235
1236 static qtreetbl_obj_t *remove_obj(qtreetbl_t *tbl, qtreetbl_obj_t *obj,
1237 const void *name, size_t namesize) {
1238 if (obj == NULL) {
1239 errno = ENOENT;
1240 return NULL;
1241 }
1242
1243 int cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
1244 if (cmp < 0) {
1245 // move red left
1246 if (obj->left != NULL
1247 && (!is_red(obj->left) && !is_red(obj->left->left))) {
1248 obj = move_red_left(obj);
1249 }
1250 // keep going down to the left
1251 obj->left = remove_obj(tbl, obj->left, name, namesize);
1252 } else { // right or equal
1253 bool recmp = false; // optimization to reduce duplicated comparisions
1254 if (is_red(obj->left)) {
1255 obj = rotate_right(obj);
1256 recmp = true;
1257 }
1258 // remove if equal at the bottom
1259 if (obj->right == NULL) {
1260 if (recmp) {
1261 cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
1262 recmp = false;
1263 }
1264 if (cmp == 0) {
1265 free(obj->name);
1266 free(obj->data);
1267 free(obj);
1268 tbl->num--;
1269 return NULL;
1270 }
1271 }
1272 // move red right
1273 if (obj->right != NULL
1274 && (!is_red(obj->right) && !is_red(obj->right->left))) {
1275 obj = move_red_right(obj);
1276 recmp = true;
1277 }
1278 // found in the middle
1279 if (recmp) {
1280 cmp = tbl->compare(name, namesize, obj->name, obj->namesize);
1281 }
1282 if (cmp == 0) {
1283 // copy min to this then remove min
1284 qtreetbl_obj_t *minobj = find_min(obj->right);
1285 assert(minobj != NULL);
1286 free(obj->name);
1287 free(obj->data);
1288 obj->name = qmemdup(minobj->name, minobj->namesize);
1289 obj->namesize = minobj->namesize;
1290 obj->data = qmemdup(minobj->data, minobj->datasize);
1291 obj->datasize = minobj->datasize;
1292 obj->right = remove_min(obj->right);
1293 tbl->num--;
1294 } else {
1295 // keep going down to the right
1296 obj->right = remove_obj(tbl, obj->right, name, namesize);
1297 }
1298 }
1299 // fix right-leaning red nodes on the way up
1300 return fix(obj);
1301}
1302
1303 static void free_objs(qtreetbl_obj_t *obj) {
1304 if (obj == NULL) {
1305 return;
1306 }
1307
1308 free_objs(obj->left);
1309 free_objs(obj->right);
1310
1311 free(obj->name);
1312 free(obj->data);
1313 free(obj);
1314}
1315
1316 static uint8_t reset_iterator(qtreetbl_t *tbl) {
1317 if (tbl->root != NULL) {
1318 tbl->root->next = NULL;
1319 }
1320 return (++tbl->tid);
1321}
1322
1323 static void print_branch(struct branch_obj_s *branch, FILE *out) {
1324 if (branch == NULL) {
1325 return;
1326 }
1327 print_branch(branch->p, out);
1328 fprintf(out, "%s", branch->s);
1329}
1330
1331 static void print_node(qtreetbl_obj_t *obj, FILE *out, struct branch_obj_s *prev,
1332 bool right) {
1333 if (obj == NULL) {
1334 return;
1335 }
1336
1337 struct branch_obj_s branch;
1338 branch.p = prev;
1339
1340 branch.s = (prev != NULL) ? (right) ? " " : "│ " : "";
1341 print_node(obj->right, out, &branch, true);
1342
1343 print_branch(prev, out);
1344 if (prev != NULL) {
1345 fprintf(out, "%s%s", (right) ? "┌──" : "└──", (obj->red) ? "[" : "─");
1346 }
1347 if (obj->data == NULL && obj->namesize == sizeof(uint32_t)) {
1348 fprintf(out, "%u", *(uint32_t *)obj->name);
1349 } else {
1350 _q_textout(out, obj->name, obj->namesize, 15);
1351 }
1352 fprintf(out, "%s", (obj->red) ? "]\n" : "\n");
1353
1354 branch.s = (prev != NULL) ? (right) ? "│ " : " " : "";
1355 print_node(obj->left, out, &branch, false);
1356}
1357
1358#endif
qmemdup
void * qmemdup(const void *data, size_t size)
Duplicate a copy of memory data.
Definition qstring.c:413
qtreetbl
qtreetbl_t * qtreetbl(int options)
Initialize a tree table.
Definition qtreetbl.c:182
qtreetbl_get
void * qtreetbl_get(qtreetbl_t *tbl, const char *name, size_t *datasize, bool newmem)
qtreetbl->get(): Get an object from this table.
Definition qtreetbl.c:392
node_check_root
int node_check_root(qtreetbl_t *tbl)
Verifies that root property of the red-black tree is satisfied.
Definition qtreetbl.c:890
qtreetbl_free
void qtreetbl_free(qtreetbl_t *tbl)
qtreetbl->free(): De-allocate the table.
Definition qtreetbl.c:827
qtreetbl_putstr
bool qtreetbl_putstr(qtreetbl_t *tbl, const char *name, const char *str)
qtreetbl->putstr(): Put a string into this table.
Definition qtreetbl.c:287
qtreetbl_remove
bool qtreetbl_remove(qtreetbl_t *tbl, const char *name)
qtreetbl->remove(): Remove an object from this table.
Definition qtreetbl.c:474
qtreetbl_size
size_t qtreetbl_size(qtreetbl_t *tbl)
qtreetbl->size(): Returns the number of keys in the table.
Definition qtreetbl.c:775
qtreetbl_put
bool qtreetbl_put(qtreetbl_t *tbl, const char *name, const void *data, size_t datasize)
qtreetbl->put(): Put an object into this table with string type key.
Definition qtreetbl.c:269
qtreetbl_find_max
void * qtreetbl_find_max(qtreetbl_t *tbl, size_t *namesize)
qtreetbl->find_max(): Find the name of the rightmost object.
Definition qtreetbl.c:662
qtreetbl_lock
void qtreetbl_lock(qtreetbl_t *tbl)
qtreetbl->lock(): Enter critical section.
Definition qtreetbl.c:805
qtreetbl_debug
bool qtreetbl_debug(qtreetbl_t *tbl, FILE *out)
qtreetbl->debug(): Print the internal tree structure in text.
Definition qtreetbl.c:871
qtreetbl_putobj
bool qtreetbl_putobj(qtreetbl_t *tbl, const void *name, size_t namesize, const void *data, size_t datasize)
qtreetbl->putobj(): Put an object data into this table with an object key.
Definition qtreetbl.c:336
qtreetbl_getobj
void * qtreetbl_getobj(qtreetbl_t *tbl, const void *name, size_t namesize, size_t *datasize, bool newmem)
qtreetbl->getobj(): Get an object from this table with an object name.
Definition qtreetbl.c:443
qtreetbl_clear
void qtreetbl_clear(qtreetbl_t *tbl)
qtreetbl->clear(): Clears the table so that it contains no keys.
Definition qtreetbl.c:784
qtreetbl_getstr
char * qtreetbl_getstr(qtreetbl_t *tbl, const char *name, const bool newmem)
qtreetbl->getstr(): Finds an object and returns it as string type.
Definition qtreetbl.c:417
qtreetbl_unlock
void qtreetbl_unlock(qtreetbl_t *tbl)
qtreetbl->unlock(): Leave critical section.
Definition qtreetbl.c:818
node_check_llrb
int node_check_llrb(qtreetbl_t *tbl, qtreetbl_obj_t *obj)
Verifies that LLRB property of the left-leaning red-black tree is satisfied.
Definition qtreetbl.c:971
qtreetbl_find_nearest
qtreetbl_obj_t qtreetbl_find_nearest(qtreetbl_t *tbl, const void *name, size_t namesize, bool newmem)
qtreetbl->find_nearest(): Find an object with matching key or nearest.
Definition qtreetbl.c:711
node_check_black
int node_check_black(qtreetbl_t *tbl, qtreetbl_obj_t *obj, int *path_len)
Verifies that black property of the red-black tree is satisfied.
Definition qtreetbl.c:940
qtreetbl_check
int qtreetbl_check(qtreetbl_t *tbl)
Verifies that the invariants of the red-black tree are satisfied.
Definition qtreetbl.c:1001
qtreetbl_find_min
void * qtreetbl_find_min(qtreetbl_t *tbl, size_t *namesize)
qtreetbl->find_min(): Find the name of the leftmost object.
Definition qtreetbl.c:634
qtreetbl_putstrf
bool qtreetbl_putstrf(qtreetbl_t *tbl, const char *name, const char *format,...)
qtreetbl->putstrf(): Put a formatted string into this table.
Definition qtreetbl.c:305
node_check_red
int node_check_red(qtreetbl_t *tbl, qtreetbl_obj_t *obj)
Verifies that red property of the red-black tree is satisfied.
Definition qtreetbl.c:909
qtreetbl_removeobj
bool qtreetbl_removeobj(qtreetbl_t *tbl, const void *name, size_t namesize)
qtreetbl->remove(): Remove an object from this table with an object name.
Definition qtreetbl.c:491
qtreetbl_getnext
bool qtreetbl_getnext(qtreetbl_t *tbl, qtreetbl_obj_t *obj, const bool newmem)
qtreetbl->getnext(): Get next element.
Definition qtreetbl.c:580
qtreetbl_set_compare
void qtreetbl_set_compare(qtreetbl_t *tbl, int(*cmp)(const void *name1, size_t namesize1, const void *name2, size_t namesize2))
qtreetbl->set_compare(): Set user comparator.
Definition qtreetbl.c:250