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