share/man/man3/arb.3

   1 .\"     $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $
   2 .\"
   3 .\" Copyright 2002 Niels Provos <provos@citi.umich.edu>
   4 .\" Copyright 2018-2019 Netflix, Inc.
   5 .\" All rights reserved.
   6 .\"
   7 .\" Redistribution and use in source and binary forms, with or without
   8 .\" modification, are permitted provided that the following conditions
   9 .\" are met:
  10 .\" 1. Redistributions of source code must retain the above copyright
  11 .\"    notice, this list of conditions and the following disclaimer.
  12 .\" 2. Redistributions in binary form must reproduce the above copyright
  13 .\"    notice, this list of conditions and the following disclaimer in the
  14 .\"    documentation and/or other materials provided with the distribution.
  15 .\" 3. All advertising materials mentioning features or use of this software
  16 .\"    must display the following acknowledgement:
  17 .\"      This product includes software developed by Niels Provos.
  18 .\" 4. The name of the author may not be used to endorse or promote products
  19 .\"    derived from this software without specific prior written permission.
  20 .\"
  21 .\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  22 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  23 .\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  24 .\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  25 .\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  26 .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27 .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28 .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29 .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  30 .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31 .\"
  32 .Dd October 14, 2019
  33 .Dt ARB 3
  34 .Os
  35 .Sh NAME
  36 .Nm ARB_PROTOTYPE ,
  37 .Nm ARB_PROTOTYPE_STATIC ,
  38 .Nm ARB_PROTOTYPE_INSERT ,
  39 .Nm ARB_PROTOTYPE_INSERT_COLOR ,
  40 .Nm ARB_PROTOTYPE_REMOVE ,
  41 .Nm ARB_PROTOTYPE_REMOVE_COLOR ,
  42 .Nm ARB_PROTOTYPE_FIND ,
  43 .Nm ARB_PROTOTYPE_NFIND ,
  44 .Nm ARB_PROTOTYPE_NEXT ,
  45 .Nm ARB_PROTOTYPE_PREV ,
  46 .Nm ARB_PROTOTYPE_MINMAX ,
  47 .Nm ARB_PROTOTYPE_REINSERT ,
  48 .Nm ARB_GENERATE ,
  49 .Nm ARB_GENERATE_STATIC ,
  50 .Nm ARB_GENERATE_INSERT ,
  51 .Nm ARB_GENERATE_INSERT_COLOR ,
  52 .Nm ARB_GENERATE_REMOVE ,
  53 .Nm ARB_GENERATE_REMOVE_COLOR ,
  54 .Nm ARB_GENERATE_FIND ,
  55 .Nm ARB_GENERATE_NFIND ,
  56 .Nm ARB_GENERATE_NEXT ,
  57 .Nm ARB_GENERATE_PREV ,
  58 .Nm ARB_GENERATE_MINMAX ,
  59 .Nm ARB_GENERATE_REINSERT ,
  60 .Nm ARB8_ENTRY ,
  61 .Nm ARB16_ENTRY ,
  62 .Nm ARB32_ENTRY ,
  63 .Nm ARB8_HEAD ,
  64 .Nm ARB16_HEAD ,
  65 .Nm ARB32_HEAD ,
  66 .Nm ARB_ALLOCSIZE ,
  67 .Nm ARB_INITIALIZER ,
  68 .Nm ARB_ROOT ,
  69 .Nm ARB_EMPTY ,
  70 .Nm ARB_FULL ,
  71 .Nm ARB_CURNODES ,
  72 .Nm ARB_MAXNODES ,
  73 .Nm ARB_NEXT ,
  74 .Nm ARB_PREV ,
  75 .Nm ARB_MIN ,
  76 .Nm ARB_MAX ,
  77 .Nm ARB_FIND ,
  78 .Nm ARB_NFIND ,
  79 .Nm ARB_LEFT ,
  80 .Nm ARB_LEFTIDX ,
  81 .Nm ARB_RIGHT ,
  82 .Nm ARB_RIGHTIDX ,
  83 .Nm ARB_PARENT ,
  84 .Nm ARB_PARENTIDX ,
  85 .Nm ARB_GETFREE ,
  86 .Nm ARB_FREEIDX ,
  87 .Nm ARB_FOREACH ,
  88 .Nm ARB_FOREACH_FROM ,
  89 .Nm ARB_FOREACH_SAFE ,
  90 .Nm ARB_FOREACH_REVERSE ,
  91 .Nm ARB_FOREACH_REVERSE_FROM ,
  92 .Nm ARB_FOREACH_REVERSE_SAFE ,
  93 .Nm ARB_INIT ,
  94 .Nm ARB_INSERT ,
  95 .Nm ARB_REMOVE ,
  96 .Nm ARB_REINSERT ,
  97 .Nm ARB_RESET_TREE
  98 .Nd "array-based red-black trees"
  99 .Sh SYNOPSIS
 100 .In sys/arb.h
 101 .Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
 102 .Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
 103 .Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
 104 .Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
 105 .Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
 106 .Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
 107 .Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
 108 .Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
 109 .Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
 110 .Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
 111 .Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
 112 .Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
 113 .Fn ARB_GENERATE NAME TYPE FIELD CMP
 114 .Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
 115 .Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
 116 .Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
 117 .Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
 118 .Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
 119 .Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
 120 .Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
 121 .Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
 122 .Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
 123 .Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
 124 .Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
 125 .Fn ARB<8|16|32>_ENTRY
 126 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
 127 .Ft "size_t"
 128 .Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
 129 .Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
 130 .Ft "struct TYPE *"
 131 .Fn ARB_ROOT "ARB_HEAD *head"
 132 .Ft "bool"
 133 .Fn ARB_EMPTY "ARB_HEAD *head"
 134 .Ft "bool"
 135 .Fn ARB_FULL "ARB_HEAD *head"
 136 .Ft "int<8|16|32>_t"
 137 .Fn ARB_CURNODES "ARB_HEAD *head"
 138 .Ft "int<8|16|32>_t"
 139 .Fn ARB_MAXNODES "ARB_HEAD *head"
 140 .Ft "struct TYPE *"
 141 .Fn ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm"
 142 .Ft "struct TYPE *"
 143 .Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm"
 144 .Ft "struct TYPE *"
 145 .Fn ARB_MIN NAME "ARB_HEAD *head"
 146 .Ft "struct TYPE *"
 147 .Fn ARB_MAX NAME "ARB_HEAD *head"
 148 .Ft "struct TYPE *"
 149 .Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm"
 150 .Ft "struct TYPE *"
 151 .Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm"
 152 .Ft "struct TYPE *"
 153 .Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME"
 154 .Ft "int<8|16|32>_t"
 155 .Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
 156 .Ft "struct TYPE *"
 157 .Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME"
 158 .Ft "int<8|16|32>_t"
 159 .Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
 160 .Ft "struct TYPE *"
 161 .Fn ARB_PARENT "struct TYPE *elm" "ARB_ENTRY NAME"
 162 .Ft "int<8|16|32>_t"
 163 .Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
 164 .Ft "struct TYPE *"
 165 .Fn ARB_GETFREE "ARB_HEAD *head" "FIELD"
 166 .Ft "int<8|16|32>_t"
 167 .Fn ARB_FREEIDX "ARB_HEAD *head"
 168 .Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head"
 169 .Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
 170 .Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
 171 .Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head"
 172 .Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
 173 .Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
 174 .Ft void
 175 .Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
 176 .Ft "struct TYPE *"
 177 .Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
 178 .Ft "struct TYPE *"
 179 .Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
 180 .Ft "struct TYPE *"
 181 .Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
 182 .Ft void
 183 .Fn ARB_RESET_TREE "ARB_HEAD *head" NAME "int<8|16|32>_t maxnodes"
 184 .Sh DESCRIPTION
 185 These macros define data structures for and array-based red-black trees.
 186 They use a single, continuous chunk of memory, and are useful
 187 e.g., when the tree needs to be transferred between userspace and kernel.
 188 .Pp
 189 In the macro definitions,
 190 .Fa TYPE
 191 is the name tag of a user defined structure that must contain a field of type
 192 .Vt ARB_ENTRY ,
 193 named
 194 .Fa ENTRYNAME .
 195 The argument
 196 .Fa HEADNAME
 197 is the name tag of a user defined structure that must be declared
 198 using the
 199 .Fn ARB_HEAD
 200 macro.
 201 The argument
 202 .Fa NAME
 203 has to be a unique name prefix for every tree that is defined.
 204 .Pp
 205 The function prototypes are declared with
 206 .Fn ARB_PROTOTYPE ,
 207 or
 208 .Fn ARB_PROTOTYPE_STATIC .
 209 The function bodies are generated with
 210 .Fn ARB_GENERATE ,
 211 or
 212 .Fn ARB_GENERATE_STATIC .
 213 See the examples below for further explanation of how these macros are used.
 214 .Pp
 215 A red-black tree is a binary search tree with the node color as an
 216 extra attribute.
 217 It fulfills a set of conditions:
 218 .Bl -enum -offset indent
 219 .It
 220 Every search path from the root to a leaf consists of the same number of
 221 black nodes.
 222 .It
 223 Each red node (except for the root) has a black parent.
 224 .It
 225 Each leaf node is black.
 226 .El
 227 .Pp
 228 Every operation on a red-black tree is bounded as
 229 .Fn O "lg n" .
 230 The maximum height of a red-black tree is
 231 .Fn 2lg "n + 1" .
 232 .Pp
 233 .Fn ARB_*
 234 trees require entries to be allocated as an array, and uses array
 235 indices to link entries together.
 236 The maximum number of
 237 .Fn ARB_*
 238 tree entries is therefore constrained by the minimum of array size and choice of
 239 signed integer data type used to store array indices.
 240 Use
 241 .Fn ARB_ALLOCSIZE
 242 to compute the size of memory chunk to allocate.
 243 .Pp
 244 A red-black tree is headed by a structure defined by the
 245 .Fn ARB_HEAD
 246 macro.
 247 A
 248 structure is declared with either of the following:
 249 .Bd -ragged -offset indent
 250 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
 251 .Va head ;
 252 .Ed
 253 .Pp
 254 where
 255 .Fa HEADNAME
 256 is the name of the structure to be defined, and struct
 257 .Fa TYPE
 258 is the type of the elements to be inserted into the tree.
 259 .Pp
 260 The
 261 .Fn ARB_HEAD
 262 variant includes a suffix denoting the signed integer data type size
 263 .Pq in bits
 264 used to store array indices.
 265 For example,
 266 .Fn ARB_HEAD8
 267 creates a red-black tree head strucutre with 8-bit signed array indices capable
 268 of indexing up to 128 entries.
 269 .Pp
 270 The
 271 .Fn ARB_ENTRY
 272 macro declares a structure that allows elements to be connected in the tree.
 273 Similarly to the
 274 .Fn ARB<8|16|32>_HEAD
 275 macro, the
 276 .Fn ARB_ENTRY
 277 variant includes a suffix denoting the signed integer data type size
 278 .Pq in bits
 279 used to store array indices.
 280 Entries should use the same number of bits as the tree head structure they will
 281 be linked into.
 282 .Pp
 283 In order to use the functions that manipulate the tree structure,
 284 their prototypes need to be declared with the
 285 .Fn ARB_PROTOTYPE
 286 or
 287 .Fn ARB_PROTOTYPE_STATIC
 288 macro,
 289 where
 290 .Fa NAME
 291 is a unique identifier for this particular tree.
 292 The
 293 .Fa TYPE
 294 argument is the type of the structure that is being managed
 295 by the tree.
 296 The
 297 .Fa FIELD
 298 argument is the name of the element defined by
 299 .Fn ARB_ENTRY .
 300 Individual prototypes can be declared with
 301 .Fn ARB_PROTOTYPE_INSERT ,
 302 .Fn ARB_PROTOTYPE_INSERT_COLOR ,
 303 .Fn ARB_PROTOTYPE_REMOVE ,
 304 .Fn ARB_PROTOTYPE_REMOVE_COLOR ,
 305 .Fn ARB_PROTOTYPE_FIND ,
 306 .Fn ARB_PROTOTYPE_NFIND ,
 307 .Fn ARB_PROTOTYPE_NEXT ,
 308 .Fn ARB_PROTOTYPE_PREV ,
 309 .Fn ARB_PROTOTYPE_MINMAX ,
 310 and
 311 .Fn ARB_PROTOTYPE_REINSERT
 312 in case not all functions are required.
 313 The individual prototype macros expect
 314 .Fa NAME ,
 315 .Fa TYPE ,
 316 and
 317 .Fa ATTR
 318 arguments.
 319 The
 320 .Fa ATTR
 321 argument must be empty for global functions or
 322 .Fa static
 323 for static functions.
 324 .Pp
 325 The function bodies are generated with the
 326 .Fn ARB_GENERATE
 327 or
 328 .Fn ARB_GENERATE_STATIC
 329 macro.
 330 These macros take the same arguments as the
 331 .Fn ARB_PROTOTYPE
 332 and
 333 .Fn ARB_PROTOTYPE_STATIC
 334 macros, but should be used only once.
 335 As an alternative individual function bodies are generated with the
 336 .Fn ARB_GENERATE_INSERT ,
 337 .Fn ARB_GENERATE_INSERT_COLOR ,
 338 .Fn ARB_GENERATE_REMOVE ,
 339 .Fn ARB_GENERATE_REMOVE_COLOR ,
 340 .Fn ARB_GENERATE_FIND ,
 341 .Fn ARB_GENERATE_NFIND ,
 342 .Fn ARB_GENERATE_NEXT ,
 343 .Fn ARB_GENERATE_PREV ,
 344 .Fn ARB_GENERATE_MINMAX ,
 345 and
 346 .Fn ARB_GENERATE_REINSERT
 347 macros.
 348 .Pp
 349 Finally,
 350 the
 351 .Fa CMP
 352 argument is the name of a function used to compare tree nodes
 353 with each other.
 354 The function takes two arguments of type
 355 .Vt "struct TYPE *" .
 356 If the first argument is smaller than the second, the function returns a
 357 value smaller than zero.
 358 If they are equal, the function returns zero.
 359 Otherwise, it should return a value greater than zero.
 360 The compare
 361 function defines the order of the tree elements.
 362 .Pp
 363 The
 364 .Fn ARB_INIT
 365 macro initializes the tree referenced by
 366 .Fa head ,
 367 with the array length of
 368 .Fa maxnodes .
 369 .Pp
 370 The red-black tree can also be initialized statically by using the
 371 .Fn ARB_INITIALIZER
 372 macro:
 373 .Bd -ragged -offset indent
 374 .Fn ARB<8|16|32>_HEAD HEADNAME TYPE
 375 .Va head
 376 =
 377 .Fn ARB_INITIALIZER &head maxnodes ;
 378 .Ed
 379 .Pp
 380 The
 381 .Fn ARB_INSERT
 382 macro inserts the new element
 383 .Fa elm
 384 into the tree.
 385 .Pp
 386 The
 387 .Fn ARB_REMOVE
 388 macro removes the element
 389 .Fa elm
 390 from the tree pointed by
 391 .Fa head .
 392 .Pp
 393 The
 394 .Fn ARB_FIND
 395 and
 396 .Fn ARB_NFIND
 397 macros can be used to find a particular element in the tree.
 398 .Bd -literal -offset indent
 399 struct TYPE find, *res;
 400 find.key = 30;
 401 res = ARB_FIND(NAME, head, &find);
 402 .Ed
 403 .Pp
 404 The
 405 .Fn ARB_ROOT ,
 406 .Fn ARB_MIN ,
 407 .Fn ARB_MAX ,
 408 .Fn ARB_NEXT ,
 409 and
 410 .Fn ARB_PREV
 411 macros can be used to traverse the tree:
 412 .Pp
 413 .Dl "for (np = ARB_MIN(NAME, &head); np != NULL; np = ARB_NEXT(NAME, &head, np))"
 414 .Pp
 415 Or, for simplicity, one can use the
 416 .Fn ARB_FOREACH
 417 or
 418 .Fn ARB_FOREACH_REVERSE
 419 macro:
 420 .Bd -ragged -offset indent
 421 .Fn ARB_FOREACH np NAME head
 422 .Ed
 423 .Pp
 424 The macros
 425 .Fn ARB_FOREACH_SAFE
 426 and
 427 .Fn ARB_FOREACH_REVERSE_SAFE
 428 traverse the tree referenced by head
 429 in a forward or reverse direction respectively,
 430 assigning each element in turn to np.
 431 However, unlike their unsafe counterparts,
 432 they permit both the removal of np
 433 as well as freeing it from within the loop safely
 434 without interfering with the traversal.
 435 .Pp
 436 Both
 437 .Fn ARB_FOREACH_FROM
 438 and
 439 .Fn ARB_FOREACH_REVERSE_FROM
 440 may be used to continue an interrupted traversal
 441 in a forward or reverse direction respectively.
 442 The head pointer is not required.
 443 The pointer to the node from where to resume the traversal
 444 should be passed as their last argument,
 445 and will be overwritten to provide safe traversal.
 446 .Pp
 447 The
 448 .Fn ARB_EMPTY
 449 macro should be used to check whether a red-black tree is empty.
 450 .Pp
 451 Given that ARB trees have an intrinsic upper bound on the number of entries,
 452 some ARB-specific additional macros are defined.
 453 The
 454 .Fn ARB_FULL
 455 macro returns a boolean indicating whether the current number of tree entries
 456 equals the tree's maximum.
 457 The
 458 .Fn ARB_CURNODES
 459 and
 460 .Fn ARB_MAXNODES
 461 macros return the current and maximum number of entries respectively.
 462 The
 463 .Fn ARB_GETFREE
 464 macro returns a pointer to the next free entry in the array of entries, ready to
 465 be linked into the tree.
 466 The
 467 .Fn ARB_INSERT
 468 returns
 469 .Dv NULL
 470 if the element was inserted in the tree successfully, otherwise they
 471 return a pointer to the element with the colliding key.
 472 .Pp
 473 Accordingly,
 474 .Fn ARB_REMOVE
 475 returns the pointer to the removed element otherwise they return
 476 .Dv NULL
 477 to indicate an error.
 478 .Pp
 479 The
 480 .Fn ARB_REINSERT
 481 macro updates the position of the element
 482 .Fa elm
 483 in the tree.
 484 This must be called if a member of a
 485 .Nm tree
 486 is modified in a way that affects comparison, such as by modifying
 487 a node's key.
 488 This is a lower overhead alternative to removing the element
 489 and reinserting it again.
 490 .Pp
 491 The
 492 .Fn ARB_RESET_TREE
 493 macro discards the tree topology.
 494 It does not modify embedded object values or the free list.
 495 .Sh SEE ALSO
 496 .Xr queue 3 ,
 497 .Xr tree 3
 498 .Sh HISTORY
 499 The
 500 .Nm ARB
 501 macros first appeared in
 502 .Fx 13.0 .
 503 .Sh AUTHORS
 504 The
 505 .Nm ARB
 506 macros were implemented by
 507 .An Lawrence Stewart Aq Mt lstewart@FreeBSD.org ,
 508 based on
 509 .Xr tree 3
 510 macros written by
 511 .An Niels Provos .