SPDX is an international standard for documenting software license
requirements. Remove the existing headers and replace with a brief
SPDX preamble.
See: https://spdx.dev/use/specifications/
The script used to convert the files is added to "tools", and the
file header templates in headers/ are updated.
Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>
Sometimes we want to search for an exact key only, and reject the case
when tree->key < key. Add rb_search_exact() for this purpose, rather
than forcing the caller to perform the comparison in open code.
Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>
Add operations to get the first and last entry in the tree,
respectively. Searching for 0 or ~UINT64_C(0) is not sufficient in the
presence of duplicated keys, and is more inefficient anyway.
rb_first() followed by rb_next() until NULL, or equivalently rb_last()
followed by rb_prev() until NULL, can be used to walk the tree in key
order (ascending or descending), including all duplicate key
entries.
Since this is a *threaded* tree now, this walk can safely free entires
as it goes along, as long as the whole tree is destroyed; once any one
entry has been freed, the tree is no longer valid for anything other
than proceeding with the same tree walk.
Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>
Change the left-leaning red-black (LLRB) trees into left-leaning
threaded red-black trees. Instead of NULL pointers at leaf nodes, use
the otherwise unused field as a pointer to the lexical predecessor
(left) or successor (right). This allows fast previous/next
interator operation without needing to keep track of the root of the
tree at all times.
The additional metadata that needs to be kept can be done for "free"
simply by changing "bool red" into a flag field.
Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>
Make the source code easier to understand and keep track of by
organizing it into subdirectories depending on the function.
Signed-off-by: H. Peter Anvin <hpa@zytor.com>
