NOTE:

This implementation is extremely basic and was largely written as a personal exercise. It will eventually be upgraded to the same quality as the other data structures in sti. Red-black trees get little use (if any?) in my projects and as such it has been a low priority. The API will change when this happens.

Hash tables are superior in nearly all cases, except the rare situation where you need an ordered key-value store with good random access performance and good in-order iteration performance.

Overview

RB is a string-keyed red-black tree that stores pointers or pointer-sized data with simple typechecks on some of the arguments.

A red-black tree is declared using the following overloaded macro, where T is the value's type. RB(T) varname; It must be zero-initialized prior to use. There is a helper for this:

void RB_init(RB* o)

O(1)

Sets the internal memory to zero.

Operations

void RB_insert(RB* o, char* key, T* value)

O(log n)

Inserts a value into the tree.

int RB_delete(RB* o, char* key, T** valuep)

O(log n)

Deletes a value from the tree. If valuep is not NULL, it is filled with the old value prior to deletion. Returns 0 if the key was not found in the table and 1 if it was.

T* RB_find(RB* o, char* key, int* found)

O(log n)

Returns a pointer to the value corresponding to key, if it exists. Returns NULL otherwise. If found is not NULL, it is set to 1 if the key was found, otherwise it is not changed.

void RB_trunc(RB* o)

O(n)

Deletes the entire contents of the tree all at once. This frees all related memory and constitutes destruction of the tree without memory leaks.

long (*rb_traverse_fn)(char* key, void* value, void* user_data) void RB_traverse(RB* o, rb_traverse_fn fn, void* user_data)

O(n)

Walks the tree, in order, calling fn with each key/value pair. user_data is passed unchanged to the iteration function. If fn returns a non-zero value, iteration is stopped immediately and that value is returned from RB_traverse()

long (*rb_traverse_fn)(char* key, void* value, void* user_data) void RB_r_traverse(RB* o, rb_traverse_fn fn, void* user_data)

O(n)

Walks the tree, in reverse order, calling fn with each key/value pair. user_data is passed unchanged to the iteration function. If fn returns a non-zero value, iteration is stopped immediately and that value is returned from RB_traverse()

Red-Black Tree

NOTE:

Overview

Operations