1=pod 2 3=head1 NAME 4 5OSSL_RBT_PROTOTYPE, OSSL_RBT_GENERATE, OSSL_RBT_ENTRY, OSSL_RBT_HEAD, 6OSSL_RBT_INITIALIZER, OSSL_RBT_ROOT, OSSL_RBT_EMPTY, OSSL_RBT_NEXT, 7OSSL_RBT_PREV, OSSL_RBT_MIN, OSSL_RBT_MAX, OSSL_RBT_FIND, OSSL_RBT_NFIND, 8OSSL_RBT_LEFT, OSSL_RBT_RIGHT, OSSL_RBT_PARENT, OSSL_RBT_SET_LEFT, 9OSSL_RBT_SET_RIGHT, OSSL_RBT_SET_PARENT, OSSL_RBT_FOREACH, 10OSSL_RBT_FOREACH_SAFE, OSSL_RBT_FOREACH_REVERSE, OSSL_RBT_FOREACH_REVERSE_SAFE, 11OSSL_RBT_INIT, OSSL_RBT_INSERT, OSSL_RBT_REMOVE, 12ossl_rbtree - implementation of red-black tree 13 14=head1 SYNOPSIS 15 16 #include "internal/ossl_rbtree.h" 17 18 /* int (*CMP)(const NODE_TYPE *, const NODE_TYPE *); */ 19 20 OSSL_RBT_PROTOTYPE(NAME, NODE_TYPE, FIELD, CMP) 21 22 OSSL_RBT_GENERATE(NAME, NODE_TYPE, FIELD, CMP); 23 24 OSSL_RBT_ENTRY(NODE_TYPE) 25 26 OSSL_RBT_HEAD(HEADNAME, NODE_TYPE) 27 28 OSSL_RBT_INITIALIZER(OSSL_RBT_HEAD *head); 29 30 struct NODE_TYPE * OSSL_RBT_ROOT(NAME, OSSL_RBT_HEAD *head); 31 32 int OSSL_RBT_EMPTY(NAME, OSSL_RBT_HEAD *head); 33 34 struct NODE_TYPE * OSSL_RBT_NEXT(NAME, struct NODE_TYPE *elm); 35 36 struct NODE_TYPE * OSSL_RBT_PREV(NAME, struct NODE_TYPE *elm); 37 38 struct NODE_TYPE * OSSL_RBT_MIN(NAME, OSSL_RBT_HEAD *head); 39 40 struct NODE_TYPE * OSSL_RBT_MAX(NAME, OSSL_RBT_HEAD *head); 41 42 struct NODE_TYPE * OSSL_RBT_FIND(NAME, OSSL_RBT_HEAD *head, struct NODE_TYPE *elm); 43 44 struct NODE_TYPE * OSSL_RBT_NFIND(NAME, OSSL_RBT_HEAD *head, struct NODE_TYPE *elm); 45 46 struct NODE_TYPE * OSSL_RBT_LEFT(NAME, struct NODE_TYPE *elm); 47 48 struct NODE_TYPE * OSSL_RBT_RIGHT(NAME, struct NODE_TYPE *elm); 49 50 struct NODE_TYPE * OSSL_RBT_PARENT(NAME, struct NODE_TYPE *elm); 51 52 void OSSL_RBT_SET_LEFT(NAME, struct NODE_TYPE *elm, struct NODE_TYPE *left); 53 54 void OSSL_RBT_SET_RIGHT(NAME, struct NODE_TYPE *elm, struct NODE_TYPE *right); 55 56 void OSSL_RBT_SET_PARENT(NAME, struct NODE_TYPE *elm, struct NODE_TYPE *parent); 57 58 OSSL_RBT_FOREACH(VARNAME, NAME, OSSL_RBT_HEAD *head); 59 60 OSSL_RBT_FOREACH_SAFE(VARNAME, NAME, OSSL_RBT_HEAD *head, TEMP_VARNAME); 61 62 OSSL_RBT_FOREACH_REVERSE(VARNAME, NAME, OSSL_RBT_HEAD *head); 63 64 OSSL_RBT_FOREACH_REVERSE_SAFE(VARNAME, NAME, OSSL_RBT_HEAD *head, TEMP_VARNAME); 65 66 void OSSL_RBT_INIT(NAME, OSSL_RBT_HEAD *head); 67 68 struct NODE_TYPE * OSSL_RBT_INSERT(NAME, OSSL_RBT_HEAD *head, struct NODE_TYPE *elm); 69 70 struct NODE_TYPE * OSSL_RBT_REMOVE(NAME, OSSL_RBT_HEAD *head, struct NODE_TYPE *elm); 71 72=head1 DESCRIPTION 73 74These macros define data structures for a red-black tree. 75Every operation on a red-black tree is bounded as O(lg n). The maximum 76height of a red-black tree is 2lg (n+1). 77 78In the macro definitions, B<NODE_TYPE> is the name tag of a user defined 79structure that must contain a field named B<FIELD>, of type B<OSSL_RBT_ENTRY>. 80The argument B<HEADNAME> is the name tag of a user defined 81structure that must be declared using the macro OSSL_RBT_HEAD(). 82The argument B<NAME> has to be a unique name prefix for every 83tree that is defined. 84 85The function prototypes are declared with B<OSSL_RBT_PROTOTYPE>, 86B<OSSL_RBT_GENERATE>. See the examples below for further 87explanation of how these macros are used. 88 89A red-black tree is a binary search tree with the node color as an extra 90attribute. It fulfills a set of conditions: 91 92=over 4 93 94=item 1. 95every search path from the root to a leaf consists of the same 96number of black nodes, 97 98=item 2. 99each red node (except for the root) has a black parent, 100 101=item 3. 102each leaf node is black. 103 104=back 105 106A red-black tree is headed by a structure defined by the OSSL_RBT_HEAD macro. 107An OSSL_RBT_HEAD structure is declared as follows: 108 109 OSSL_RBT_HEAD(HEADNAME, NODE_TYPE) head; 110 111where B<HEADNAME> is the name of the structure to be defined, and B<struct 112NODE_TYPE> is the type of the elements to be inserted into the tree. 113 114The OSSL_RBT_ENTRY macro declares a structure that allows elements to be 115connected in the tree. 116 117In order to use the functions that manipulate the tree structure, their 118prototypes need to be declared with the OSSL_RBT_PROTOTYPE() macro, 119where B<NAME> is a unique identifier for this 120particular tree. The B<NODE_TYPE> argument is the type of the structure that is 121being managed by the tree. The B<FIELD> argument is the name of the element 122defined by OSSL_RBT_ENTRY(). 123 124The function bodies are generated with the OSSL_RBT_GENERATE() macro. 125These macros take the same arguments as the 126OSSL_RBT_PROTOTYPE() macro, but should be used only once. 127 128Finally, the B<CMP> argument is the name of a function used to compare 129trees' nodes with each other. The function takes two arguments of type 130B<const struct NODE_TYPE *>. If the first argument is smaller than the second, 131the function returns a value smaller than zero. If they are equal, the 132function returns zero. Otherwise, it should return a value greater than 133zero. The compare function defines the order of the tree elements. 134 135The OSSL_RBT_INIT() macro initializes the tree referenced by B<head>. 136 137The red-black tree can also be initialized statically by using the 138OSSL_RBT_INITIALIZER() macro like this: 139 140 OSSL_RBT_HEAD(HEADNAME, NODE_TYPE) head = OSSL_RBT_INITIALIZER(&head); 141 142The OSSL_RBT_INSERT() macro inserts the new element B<elm> into the tree pointed by B<head>. 143Upon success, NULL is returned. If a matching element already exists in the 144tree, the insertion is aborted, and a pointer to the existing element is 145returned. 146 147The OSSL_RBT_REMOVE() macro removes the element B<elm> from the tree pointed by 148B<head>. OSSL_RBT_REMOVE() returns B<elm>. 149 150The OSSL_RBT_LEFT() macro returns a pointer to the left child element of B<elm> 151in a red-black tree of type B<NAME>. 152 153The OSSL_RBT_RIGHT() macro returns a pointer to the right child element 154of B<elm> in a red-black tree of type B<NAME>. 155 156The OSSL_RBT_PARENT() macro returns a pointer to the parent element of B<elm> 157in a red-black tree of type B<NAME>. 158 159The OSSL_RBT_SET_LEFT() macro sets the left child pointer of element B<elm> 160to B<left> in a red-black tree of type B<NAME>. 161 162The OSSL_RBT_SET_RIGHT() macro sets the right child pointer of element B<elm> 163to B<right> in a red-black tree of type B<NAME>. 164 165The OSSL_RBT_SET_PARENT() macro sets the parent pointer of element B<elm> 166to B<parent> in a red-black tree of type B<NAME>. 167 168The OSSL_RBT_FIND() and OSSL_RBT_NFIND() macros can be used to find a particular 169element in the tree. OSSL_RBT_FIND() finds the node with the same key as B<elm>. 170OSSL_RBT_NFIND() finds the first node greater than or equal to the search key. 171 172 struct NODE_TYPE find, *res; 173 find.key = 30; 174 res = OSSL_RBT_FIND(NAME, &head, &find); 175 176The OSSL_RBT_ROOT(), OSSL_RBT_MIN(), OSSL_RBT_MAX(), OSSL_RBT_NEXT(), and 177OSSL_RBT_PREV() macros can be used to traverse the tree: 178 179 for (np = OSSL_RBT_MIN(NAME, &head); np != NULL; np = OSSL_RBT_NEXT(NAME, &head, np)) 180 181Or, for simplicity, one can use the OSSL_RBT_FOREACH() or OSSL_RBT_FOREACH_REVERSE() 182macros: 183 184 OSSL_RBT_FOREACH(np, NAME, &head) 185 186The macros OSSL_RBT_FOREACH_SAFE() and OSSL_RBT_FOREACH_REVERSE_SAFE() traverse the 187tree referenced by head in a forward or reverse direction respectively, 188assigning each element in turn to B<VARNAME>. However, unlike their unsafe 189counterparts, they permit both the removal of B<VARNAME> as well as freeing it 190from within the loop safely without interfering with the traversal. 191 192The OSSL_RBT_EMPTY() macro should be used to check whether a red-black tree is 193empty. 194 195=head1 EXAMPLES 196 197The following example demonstrates how to declare a red-black tree 198holding integers. Values are inserted into it and the contents of the 199tree are printed in order. Lastly, the internal structure of the tree 200is printed. 201 202 #include <err.h> 203 #include <stdio.h> 204 #include <stdlib.h> 205 206 #include "internal/nelem.h" 207 #include "internal/ossl_rbtree.h" 208 209 struct node { 210 OSSL_RBT_ENTRY(node) entry; 211 int i; 212 }; 213 214 static int intcmp(const struct node *, const struct node *); 215 216 OSSL_RBT_HEAD(inttree, node) head = OSSL_RBT_INITIALIZER(&head); 217 OSSL_RBT_PROTOTYPE(inttree, node, entry, intcmp) 218 OSSL_RBT_GENERATE(inttree, node, entry, intcmp); 219 220 static const int testdata[] = { 221 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 222 10, 19, 5, 9, 12, 15, 18, 7, 11, 14 223 }; 224 225 static int intcmp(const struct node *e1, const struct node *e2) 226 { 227 return e1->i < e2->i ? -1 : e1->i > e2->i; 228 } 229 230 static void print_tree(struct node *n) 231 { 232 struct node *left, *right; 233 234 if (n == NULL) { 235 printf("nil"); 236 return; 237 } 238 239 left = OSSL_RBT_LEFT(inttree, n); 240 right = OSSL_RBT_RIGHT(inttree, n); 241 242 if (left == NULL && right == NULL) { 243 printf("%d", n->i); 244 } else { 245 printf("%d(", n->i); 246 print_tree(left); 247 printf(","); 248 print_tree(right); 249 printf(")"); 250 } 251 } 252 253 int main(void) 254 { 255 size_t i; 256 struct node *n; 257 258 for (i = 0; i < OSSL_NELEM(testdata); i++) { 259 if ((n = OPENSSL_malloc(sizeof(struct node))) == NULL) 260 err(1, NULL); 261 n->i = testdata[i]; 262 OSSL_RBT_INSERT(inttree, &head, n); 263 } 264 265 OSSL_RBT_FOREACH (n, inttree, &head) { 266 printf("%d\n", n->i); 267 } 268 269 print_tree(OSSL_RBT_ROOT(inttree, &head)); 270 printf("\n"); 271 272 return 0; 273 } 274 275=head1 HISTORY 276 277The red-black tree implementation comes from David Gwynne. It can be found 278here: L<https://github.com/dgwynne/data-structures>. OpenSSL project 279obtained a permission from David Gwynne to license his work under 280Apache License 2.0 281 282Apart from B<OSSL_RBT_> prefix, the API is compatible with implementation 283done by Neils Provos for OpenBSD. 284 285The text in this manual page comes from C<tree(3)> in OpenBSD, the text was 286authored by Neils Provos (according to the commit history) 287 288The red-black tree implementation was added in OpenSSL 4.1. 289 290=head1 COPYRIGHT 291 292Copyright 2002 Niels Provos <provos@citi.umich.edu> 293All rights reserved. 294 295Copyright 2026 The OpenSSL Project Authors. All Rights Reserved. 296 297 298Licensed under the Apache License 2.0 (the "License"). You may not use 299this file except in compliance with the License. You can obtain a copy 300in the file LICENSE in the source distribution or at 301L<https://www.openssl.org/source/license.html>. 302 303=cut 304