qLibc

Functions
qtreetbl.c File Reference

Tree Table container that implements the Left-Leaning Red-Black BST algorithm. More...

Go to the source code of this file.

## Functions
qtreetbl_t * | qtreetbl (int options)
| Initialize a tree table.
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.
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.
bool | qtreetbl_putstr (qtreetbl_t *tbl, const char *name, const char *str)
| qtreetbl->putstr(): Put a string into this table.
bool | qtreetbl_putstrf (qtreetbl_t *tbl, const char *name, const char *format,...)
| qtreetbl->putstrf(): Put a formatted string into this table.
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.
void * | qtreetbl_get (qtreetbl_t *tbl, const char *name, size_t *datasize, bool newmem)
| qtreetbl->get(): Get an object from this table.
char * | qtreetbl_getstr (qtreetbl_t *tbl, const char *name, const bool newmem)
| qtreetbl->getstr(): Finds an object and returns it as string type.
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.
bool | qtreetbl_remove (qtreetbl_t *tbl, const char *name)
| qtreetbl->remove(): Remove an object from this table.
bool | qtreetbl_removeobj (qtreetbl_t *tbl, const void *name, size_t namesize)
| qtreetbl->remove(): Remove an object from this table with an object name.
bool | qtreetbl_getnext (qtreetbl_t *tbl, qtreetbl_obj_t *obj, const bool newmem)
| qtreetbl->getnext(): Get next element.
void * | qtreetbl_find_min (qtreetbl_t *tbl, size_t *namesize)
| qtreetbl->find_min(): Find the name of the leftmost object.
void * | qtreetbl_find_max (qtreetbl_t *tbl, size_t *namesize)
| qtreetbl->find_max(): Find the name of the rightmost object.
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.
size_t | qtreetbl_size (qtreetbl_t *tbl)
| qtreetbl->size(): Returns the number of keys in the table.
void | qtreetbl_clear (qtreetbl_t *tbl)
| qtreetbl->clear(): Clears the table so that it contains no keys.
void | qtreetbl_lock (qtreetbl_t *tbl)
| qtreetbl->lock(): Enter critical section.
void | qtreetbl_unlock (qtreetbl_t *tbl)
| qtreetbl->unlock(): Leave critical section.
void | qtreetbl_free (qtreetbl_t *tbl)
| qtreetbl->free(): De-allocate the table.
int | qtreetbl_byte_cmp (const void *name1, size_t namesize1, const void *name2, size_t namesize2)
bool | qtreetbl_debug (qtreetbl_t *tbl, FILE *out)
| qtreetbl->debug(): Print the internal tree structure in text.
int | node_check_root (qtreetbl_t *tbl)
| Verifies that root property of the red-black tree is satisfied.
int | node_check_red (qtreetbl_t *tbl, qtreetbl_obj_t *obj)
| Verifies that red property of the red-black tree is satisfied.
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.
int | node_check_llrb (qtreetbl_t *tbl, qtreetbl_obj_t *obj)
| Verifies that LLRB property of the left-leaning red-black tree is satisfied.
int | qtreetbl_check (qtreetbl_t *tbl)
| Verifies that the invariants of the red-black tree are satisfied.

## Detailed Description

Tree Table container that implements the Left-Leaning Red-Black BST algorithm.

qtreetbl implements a binary search tree that allows efficient in-order traversal with O(log n) search time.

The algorithm qtreetbl specifically implements is the left-leaning red-black tree algorithm invented in 2008 by Robert Sedgewick. A left-leaning red–black tree is a type of self-balancing binary search tree and it is a variant of the red–black tree which was invented in 1972 by Rudolf Bayer.

References:

- http://en.wikipedia.org/wiki/Left-leaning_red-black_tree
- https://sedgewick.io/wp-content/uploads/2022/03/2008-09LLRB.pdf

                               (E)
                  ______________|______________
                 /                             \
                (C)                           (R)
               /   \                         /   \
           (A,B)   (D)                   (I,N)   (S,X)

                  <2-3-4 Tree Data Structure>

                                E
                  ______________|______________
                 /                             \
                C                               R
         _______|_______                 _______|_______
        /               \               /               \
       B                 D             N                 X

  // // // A* I* S*

         <Left-Leaning Red-Black Tree Data Structure>

  Nodes A, I and S are nodes with RED upper link. Others are BLACK

The Red-Black BST algorithm has been one of the popular BST algorithms especially for in-memory operation. The Left-Leaning version of Red-Black especially improves performance and reduces overall complexity.

Since it's relatively new algorithm, there's not many practically functional working codes yet other than proof of concept kinds. Here's one of fully functional codes and I, Seungyoung Kim, would like to dedicate this code to the genius inventor Robert Sedgewick and to all the great qLibc users.

Additional features:

- iterator.
- find nearest key.
- iteration from given key.
- find min/max key.

qtreetbl_t *tbl = qtreetbl(QTREETBL_THREADSAFE);
tbl->put(tbl, "KEY", "DATA", 4); // use putobj() for binary keys.
void *data = tbl->get(tbl, "KEY", false); // use getobj() for binary keys.
tbl->remove(tbl, "KEY"); // use remove_by_key() for binary keys.
// iteration example
qtreetbl_obj_t obj;
memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
tbl->lock(tbl); // for thread safety
while (tbl->getnext(tbl, &obj, false) == true) {
...
}
tbl->unlock(tbl);
// find a nearest key then iterate from there
tbl->lock(tbl);
qtreetbl_obj_t obj = tbl->find_nearest(tbl, "K", sizeof("K"), false);
tbl->lock(tbl); // for thread safety
while (tbl->getnext(tbl, &obj, false) == true) {
...
}
tbl->unlock(tbl);
// find minimum value using custom comparator
tbl->set_compare(tbl, my_compare_func); // default is byte comparator
void *min = tbl->find_min(tbl, &keysize);
// get total number of objects in the table
size_t num = tbl->size(tbl);
tbl->free(tbl);
qtreetbl
qtreetbl_t * qtreetbl(int options)
Initialize a tree table.
Definition qtreetbl.c:182

Definition in file qtreetbl.c.

## Function Documentation

## ◆ qtreetbl()

qtreetbl_t * qtreetbl | ( | int | options | ) |

Initialize a tree table.

Parameters

  options | combination of initialization options.

Returns
  a pointer of malloced qtreetbl_t, otherwise returns NULL.

Return values

  errno | will be set in error condition. ENOMEM : Memory allocation failure.

qtreetbl_t *tbl = qtreetbl(0);

Note
  Available options:
  - QTREETBL_THREADSAFE - make it thread-safe.

Definition at line 182 of file qtreetbl.c.

## ◆ qtreetbl_set_compare()

void qtreetbl_set_compare | ( | qtreetbl_t * | tbl,
|  | int(*)(const void *name1, size_t namesize1, const void *name2, size_t namesize2) | cmp
| ) |  |

qtreetbl->set_compare(): Set user comparator.

Parameters

  tbl | qtreetbl_t container pointer.
  cmp | a pointer to the user comparator function.

Note
  By default, qtreetbl uses byte comparator that works for both binary type key and string type key. Please refer qtreetbl_byte_cmp() for your idea to make your own comparator.

Definition at line 250 of file qtreetbl.c.

## ◆ 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.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  data | data object.
  datasize | size of data object.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Definition at line 269 of file qtreetbl.c.

## ◆ qtreetbl_putstr()

bool qtreetbl_putstr | ( | qtreetbl_t * | tbl,
|  | const char * | name,
|  | const char * | str
| ) |  |

qtreetbl->putstr(): Put a string into this table.

Parameters

  tbl | qtreetbl container pointer.
  name | key name.
  str | string data.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Definition at line 287 of file qtreetbl.c.

## ◆ qtreetbl_putstrf()

bool qtreetbl_putstrf | ( | qtreetbl_t * | tbl,
|  | const char * | name,
|  | const char * | format,
|  |  | ...
| ) |  |

qtreetbl->putstrf(): Put a formatted string into this table.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  format | formatted string data.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Definition at line 305 of file qtreetbl.c.

## ◆ 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.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  namesize | key size.
  data | data object.
  datasize | size of data object.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Note
  This is the underlying put function which all other put methods use.

Definition at line 336 of file qtreetbl.c.

## ◆ qtreetbl_get()

void * qtreetbl_get | ( | qtreetbl_t * | tbl,
|  | const char * | name,
|  | size_t * | datasize,
|  | bool | newmem
| ) |  |

qtreetbl->get(): Get an object from this table.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  datasize | if not NULL, object size will be stored.
  newmem | whether or not to allocate memory for the data.

Returns
  a pointer of data if the key is found, otherwise returns NULL.

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

qtreetbl_t *tbl = qtreetbl(0);
(...codes...)
// with newmem flag unset
size_t size;
void *data = (struct myobj*)tbl->get(tbl, "key_name", &size, false);
// with newmem flag set
size_t size;
void *data = (struct myobj*)tbl->get(tbl, "key_name", &size, true);
free(data);

Note
  If newmem flag is set, returned data will be malloced and should be deallocated by user. Otherwise returned pointer will point internal buffer directly and should not be de-allocated by user. In thread-safe mode, newmem flag must be set to true always.

Definition at line 392 of file qtreetbl.c.

## ◆ 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.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  newmem | whether or not to allocate memory for the data.

Returns
  a pointer to data if the key is found, otherwise returns NULL.

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Note
  If newmem flag is set, returned data will be malloced and should be deallocated by user. Otherwise returned pointer will point internal buffer directly and should not be de-allocated by user. In thread-safe mode, newmem flag must be set to true always.

Definition at line 417 of file qtreetbl.c.

## ◆ 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.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  namesize | key size.
  datasize | if not NULL, oject size will be stored.
  newmem | whether or not to allocate memory for the data.

Returns
  a pointer of data if the key is found, otherwise returns NULL.

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Note
  If newmem flag is set, returned data will be malloced and should be deallocated by user. Otherwise returned pointer will point internal buffer directly and should not be de-allocated by user. In thread-safe mode, newmem flag must be set to true always.

Definition at line 443 of file qtreetbl.c.

## ◆ qtreetbl_remove()

bool qtreetbl_remove | ( | qtreetbl_t * | tbl,
|  | const char * | name
| ) |  |

qtreetbl->remove(): Remove an object from this table.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.

Returns
  true if successful, otherwise(not found) returns false.

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument.

Definition at line 474 of file qtreetbl.c.

## ◆ 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.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  name | key size.

Returns
  true if successful, otherwise(not found) returns false.

Return values

  errno | will be set in error condition. ENOENT : No such key found. EINVAL : Invalid argument.

Definition at line 491 of file qtreetbl.c.

## ◆ qtreetbl_getnext()

bool qtreetbl_getnext | ( | qtreetbl_t * | tbl,
|  | qtreetbl_obj_t * | obj,
|  | const bool | newmem
| ) |  |

qtreetbl->getnext(): Get next element.

Parameters

  tbl | qtreetbl_t container pointer.
  obj | found data will be stored in this object.
  newmem | whether or not to allocate memory for the data.

Returns
  true if found otherwise returns false.

Return values

  errno | will be set in error condition. ENOENT : No next element. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

[Iteration example from the beginning]
qtreetbl_obj_t obj;
memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
tbl->lock(tbl); // lock it when thread condition is expected
while(tbl->getnext(tbl, &obj, false) == true) {
//
// obj.name : key data
// obj.namesize : key size
// obj.data : data
// obj.datasize : data size
//
// Do free obj.name and obj.data if newmem is set to true;
}
tbl->unlock(tbl);
[Iteration example from given point]
tbl->lock(tbl); // to guarantee no table update during the run
qtreetbl_obj_t obj = tbl->find_nearest(tbl, "F", sizeof("F"), false);
while (tbl->getnext(tbl, &obj, false) == true) { // newmem is false
// If a tree has 5 objects, A, C, E, G and I.
// The iteration sequence from nearest "F" will be: E->G->I->A->C
}
tbl->unlock(tbl);
[Removal example in iteration loop]
qtreetbl_obj_t obj;
memset((void*)&obj, 0, sizeof(obj));
tbl->lock(tbl);
while (tbl->getnext(tbl, &obj, false) == true) {
if (...condition...) {
char *name = qmemdup(obj.name, obj.namesize); // keep the name
size_t namesize = obj.namesize; // for removal argument
tbl->removeobj(tbl, obj.name, obj.namesize); // remove
obj = tbl->find_nearest(tbl, name, namesize, false); // rewind one step back
free(name); // clean up
}
}
tbl->unlock(tbl);
qmemdup
void * qmemdup(const void *data, size_t size)
Duplicate a copy of memory data.
Definition qstring.c:413

Note
  - Data insertion or deletion can be made during the traversal, but in that case iterator doesn't guarantee full sweep and possibly skip some visits. When deletion happens in getnext() loop, use find_nearest() to rewind the iterator one step back.
  - Object obj should be initialized with 0 by using memset() before first call.
  - If newmem flag is true, user should de-allocate obj.name and obj.data resources.

Definition at line 580 of file qtreetbl.c.

## ◆ qtreetbl_find_min()

void * qtreetbl_find_min | ( | qtreetbl_t * | tbl,
|  | size_t * | namesize
| ) |  |

qtreetbl->find_min(): Find the name of the leftmost object.

Parameters

  tbl | qtreetbl_t container pointer.
  namesize | if not NULL, the size of key name will be stored.

Returns
  malloced memory copying the key name.

Note
  It's user's responsibility to free the return.

Definition at line 634 of file qtreetbl.c.

## ◆ qtreetbl_find_max()

void * qtreetbl_find_max | ( | qtreetbl_t * | tbl,
|  | size_t * | namesize
| ) |  |

qtreetbl->find_max(): Find the name of the rightmost object.

Parameters

  tbl | qtreetbl_t container pointer.
  namesize | if not NULL, the size of key name will be stored.

Returns
  malloced memory copying the key name.

Note
  It's user's responsibility to free the return.

Definition at line 662 of file qtreetbl.c.

## ◆ 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.

find_nearest() returns matching key or nearest key object. If there's no keys in the table. It'll return empty qtreetbl_obj_t object with errno ENOENT.

Parameters

  tbl | qtreetbl_t container pointer.
  name | key name.
  namesize | key size.
  newmem | whether or not to allocate memory for the data.

Returns
  qtreetbl_obj_t object.

Return values

  errno | will be set in error condition. ENOENT : No next element. EINVAL : Invalid argument. ENOMEM : Memory allocation failure.

Data Set : A B C D E I N R S X
find_nearest("0") => "A" // no smaller key available, so "A"
find_nearest("C") => "C" // matching key found
find_nearest("F") => "E" // "E" is nearest smaller key from "F"

Note
  When there's no matching key it look for closest smaller key in the neighbors. The only exception when it returns bigger key than given search key is that when there's no smaller keys available in the table. In such case, it'll return the nearest bigger key.

Definition at line 711 of file qtreetbl.c.

## ◆ qtreetbl_size()

size_t qtreetbl_size | ( | qtreetbl_t * | tbl | ) |

qtreetbl->size(): Returns the number of keys in the table.

Parameters

  tbl | qtreetbl_t container pointer.

Returns
  number of elements stored.

Definition at line 775 of file qtreetbl.c.

## ◆ qtreetbl_clear()

void qtreetbl_clear | ( | qtreetbl_t * | tbl | ) |

qtreetbl->clear(): Clears the table so that it contains no keys.

Parameters

  tbl | qtreetbl_t container pointer.

Definition at line 784 of file qtreetbl.c.

## ◆ qtreetbl_lock()

void qtreetbl_lock | ( | qtreetbl_t * | tbl | ) |

qtreetbl->lock(): Enter critical section.

Parameters

  tbl | qtreetbl_t container pointer.

Note
  From user side, normally locking operation is only needed when traverse all elements using qtreetbl->getnext().
  This operation will do nothing if QTREETBL_THREADSAFE option was not given at the initialization time.

Definition at line 805 of file qtreetbl.c.

## ◆ qtreetbl_unlock()

void qtreetbl_unlock | ( | qtreetbl_t * | tbl | ) |

qtreetbl->unlock(): Leave critical section.

Parameters

  tbl | qtreetbl_t container pointer.

Note
  This operation will do nothing if QTREETBL_THREADSAFE option was not given at the initialization time.

Definition at line 818 of file qtreetbl.c.

## ◆ qtreetbl_free()

void qtreetbl_free | ( | qtreetbl_t * | tbl | ) |

qtreetbl->free(): De-allocate the table.

Parameters

  tbl | qtreetbl_t container pointer.

Definition at line 827 of file qtreetbl.c.

## ◆ qtreetbl_byte_cmp()

int qtreetbl_byte_cmp | ( | const void * | name1,
|  | size_t | namesize1,
|  | const void * | name2,
|  | size_t | namesize2
| ) |  |

Definition at line 833 of file qtreetbl.c.

## ◆ qtreetbl_debug()

bool qtreetbl_debug | ( | qtreetbl_t * | tbl,
|  | FILE * | out
| ) |  |

qtreetbl->debug(): Print the internal tree structure in text.

Parameters

  tbl | qtreetbl_t container pointer.
  out | output stream.

Returns
  true if successful, otherwise returns false.

Return values

  errno | will be set in error condition. EIO : Invalid output stream.

Example output:
┌───9
│ └──[8]
┌───7
│ │ ┌───6
│ └──[5]
│ └───4
3
│ ┌───2
└───1
└───0

Note
  Red nodes are wrapped in `[]`. In this example, 5 and 8 are Red nodes.

Definition at line 871 of file qtreetbl.c.

## ◆ node_check_root()

int node_check_root | ( | qtreetbl_t * | tbl | ) |

Verifies that root property of the red-black tree is satisfied.

Root property: The root is black.

Parameters

  tbl | qtreetbl_t container pointer.

Definition at line 890 of file qtreetbl.c.

## ◆ 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.

Red property: If a node is red, then both its children are black.

Parameters

  tbl | qtreetbl_t container pointer.
  obj | qtreetbl_obj_t object pointer.

Definition at line 909 of file qtreetbl.c.

## ◆ 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.

Black property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Parameters

  tbl | qtreetbl_t container pointer.
  obj | qtreetbl_obj_t object pointer.
  path_len | black path length.

Definition at line 940 of file qtreetbl.c.

## ◆ 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.

LLRB property: 3-nodes always lean to the left and 4-nodes are balanced.

Parameters

  tbl | qtreetbl_t container pointer.
  obj | qtreetbl_obj_t object pointer.

Definition at line 971 of file qtreetbl.c.

## ◆ qtreetbl_check()

int qtreetbl_check | ( | qtreetbl_t * | tbl | ) |

Verifies that the invariants of the red-black tree are satisfied.

Root property: The root is black. Red property: If a node is red, then both its children are black. Black property: For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. LLRB property: 3-nodes always lean to the left and 4-nodes are balanced.

Parameters

  tbl | qtreetbl_t container pointer.

Definition at line 1001 of file qtreetbl.c.