This is an interface for map and set functions, based on using
red-black binary search trees. Because these trees are sorted,
they are O(nlogn) to build. They allow logn insertion, find
and deletion of elements.
Both the map and set are ordered by key value, with unique keys.
For the map, the elements are key/value pairs.
For the set we only store unique, ordered keys, and the value
(set to 0 in the implementation) is ignored.
The keys for the map and set can be any of the three types in the
l_rbtree_keytype enum. The values stored can be any of the four
types in the rb_type union.
In-order forward and reverse iterators are provided for maps and sets.
To forward iterate over the map for any type of key (in this example,
uint32), extracting integer values:
L_AMAP *m = l_amapCreate(L_UINT_TYPE);
[add elements to the map ...]
L_AMAP_NODE *n = l_amapGetFirst(m);
while (n) {
l_int32 val = n->value.itype;
// do something ...
n = l_amapGetNext(n);
}
If the nodes are deleted during the iteration:
L_AMAP *m = l_amapCreate(L_UINT_TYPE);
[add elements to the map ...]
L_AMAP_NODE *n = l_amapGetFirst(m);
L_AMAP_NODE *nn;
while (n) {
nn = l_amapGetNext(n);
l_int32 val = n->value.itype;
l_uint32 key = n->key.utype;
// do something ...
l_amapDelete(m, n->key);
n = nn;
}
See prog/maptest.c and prog/settest.c for more examples of usage.
Interface to (a) map using a general key and storing general values
L_AMAP *l_amapCreate()
RB_TYPE *l_amapFind()
void l_amapInsert()
void l_amapDelete()
void l_amapDestroy()
L_AMAP_NODE *l_amapGetFirst()
L_AMAP_NODE *l_amapGetNext()
L_AMAP_NODE *l_amapGetLast()
L_AMAP_NODE *l_amapGetPrev()
l_int32 l_amapSize()
Interface to (a) set using a general key
L_ASET *l_asetCreate()
RB_TYPE *l_asetFind()
void l_asetInsert()
void l_asetDelete()
void l_asetDestroy()
L_ASET_NODE *l_asetGetFirst()
L_ASET_NODE *l_asetGetNext()
L_ASET_NODE *l_asetGetLast()
L_ASET_NODE *l_asetGetPrev()
l_int32 l_asetSize()
Definition in file map.c.
1.9.3