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

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);

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);

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.

Functions

Detailed Description

Function Documentation

◆ qtreetbl()

◆ qtreetbl_set_compare()

◆ qtreetbl_put()

◆ qtreetbl_putstr()

◆ qtreetbl_putstrf()

◆ qtreetbl_putobj()

◆ qtreetbl_get()

◆ qtreetbl_getstr()

◆ qtreetbl_getobj()

◆ qtreetbl_remove()

◆ qtreetbl_removeobj()

◆ qtreetbl_getnext()

◆ qtreetbl_find_min()

◆ qtreetbl_find_max()

◆ qtreetbl_find_nearest()

◆ qtreetbl_size()

◆ qtreetbl_clear()

◆ qtreetbl_lock()

◆ qtreetbl_unlock()

◆ qtreetbl_free()

◆ qtreetbl_byte_cmp()

◆ qtreetbl_debug()

◆ node_check_root()

◆ node_check_red()

◆ node_check_black()

◆ node_check_llrb()

◆ qtreetbl_check()