share/man/man3/tree.3

   1 .\"     $NetBSD: tree.3,v 1.3 2004/04/14 11:05:19 pooka Exp $
   2 .\"     $OpenBSD: tree.3,v 1.9 2003/05/20 09:13:38 jmc Exp $
   3 .\" $DragonFly: src/share/man/man3/tree.3,v 1.1 2004/08/19 20:38:33 joerg Exp $
   4 .\"/*
   5 .\" * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   6 .\" * All rights reserved.
   7 .\" *
   8 .\" * Redistribution and use in source and binary forms, with or without
   9 .\" * modification, are permitted provided that the following conditions
  10 .\" * are met:
  11 .\" * 1. Redistributions of source code must retain the above copyright
  12 .\" *    notice, this list of conditions and the following disclaimer.
  13 .\" * 2. Redistributions in binary form must reproduce the above copyright
  14 .\" *    notice, this list of conditions and the following disclaimer in the
  15 .\" *    documentation and/or other materials provided with the distribution.
  16 .\" * 3. All advertising materials mentioning features or use of this software
  17 .\" *    must display the following acknowledgement:
  18 .\" *      This product includes software developed by Niels Provos.
  19 .\" * 4. The name of the author may not be used to endorse or promote products
  20 .\" *    derived from this software without specific prior written permission.
  21 .\" *
  22 .\" * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23 .\" * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24 .\" * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25 .\" * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  26 .\" * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27 .\" * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28 .\" * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29 .\" * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30 .\" * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31 .\" * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 .\" */
  33 .Dd February 24, 2002
  34 .Dt TREE 3
  35 .Os
  36 .Sh NAME
  37 .Nm SPLAY_PROTOTYPE ,
  38 .Nm SPLAY_GENERATE ,
  39 .Nm SPLAY_ENTRY ,
  40 .Nm SPLAY_HEAD ,
  41 .Nm SPLAY_INITIALIZER ,
  42 .Nm SPLAY_ROOT ,
  43 .Nm SPLAY_EMPTY ,
  44 .Nm SPLAY_NEXT ,
  45 .Nm SPLAY_MIN ,
  46 .Nm SPLAY_MAX ,
  47 .Nm SPLAY_FIND ,
  48 .Nm SPLAY_LEFT ,
  49 .Nm SPLAY_RIGHT ,
  50 .Nm SPLAY_FOREACH ,
  51 .Nm SPLAY_INIT ,
  52 .Nm SPLAY_INSERT ,
  53 .Nm SPLAY_REMOVE ,
  54 .Nm RB_PROTOTYPE ,
  55 .Nm RB_GENERATE ,
  56 .Nm RB_ENTRY ,
  57 .Nm RB_HEAD ,
  58 .Nm RB_INITIALIZER ,
  59 .Nm RB_ROOT ,
  60 .Nm RB_EMPTY ,
  61 .Nm RB_NEXT ,
  62 .Nm RB_MIN ,
  63 .Nm RB_MAX ,
  64 .Nm RB_FIND ,
  65 .Nm RB_LEFT ,
  66 .Nm RB_RIGHT ,
  67 .Nm RB_PARENT ,
  68 .Nm RB_FOREACH ,
  69 .Nm RB_INIT ,
  70 .Nm RB_INSERT ,
  71 .Nm RB_REMOVE
  72 .Nd implementations of splay and red-black trees
  73 .Sh SYNOPSIS
  74 .In sys/tree.h
  75 .Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
  76 .Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP"
  77 .Fn SPLAY_ENTRY "TYPE"
  78 .Fn SPLAY_HEAD "HEADNAME" "TYPE"
  79 .Ft "struct TYPE *"
  80 .Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
  81 .Fn SPLAY_ROOT "SPLAY_HEAD *head"
  82 .Ft "bool"
  83 .Fn SPLAY_EMPTY "SPLAY_HEAD *head"
  84 .Ft "struct TYPE *"
  85 .Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
  86 .Ft "struct TYPE *"
  87 .Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
  88 .Ft "struct TYPE *"
  89 .Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
  90 .Ft "struct TYPE *"
  91 .Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
  92 .Ft "struct TYPE *"
  93 .Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
  94 .Ft "struct TYPE *"
  95 .Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
  96 .Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
  97 .Ft void
  98 .Fn SPLAY_INIT "SPLAY_HEAD *head"
  99 .Ft "struct TYPE *"
 100 .Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
 101 .Ft "struct TYPE *"
 102 .Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
 103 .Pp
 104 .Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
 105 .Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
 106 .Fn RB_ENTRY "TYPE"
 107 .Fn RB_HEAD "HEADNAME" "TYPE"
 108 .Fn RB_INITIALIZER "RB_HEAD *head"
 109 .Ft "struct TYPE *"
 110 .Fn RB_ROOT "RB_HEAD *head"
 111 .Ft "bool"
 112 .Fn RB_EMPTY "RB_HEAD *head"
 113 .Ft "struct TYPE *"
 114 .Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
 115 .Ft "struct TYPE *"
 116 .Fn RB_MIN "NAME" "RB_HEAD *head"
 117 .Ft "struct TYPE *"
 118 .Fn RB_MAX "NAME" "RB_HEAD *head"
 119 .Ft "struct TYPE *"
 120 .Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
 121 .Ft "struct TYPE *"
 122 .Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
 123 .Ft "struct TYPE *"
 124 .Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
 125 .Ft "struct TYPE *"
 126 .Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
 127 .Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head"
 128 .Ft void
 129 .Fn RB_INIT "RB_HEAD *head"
 130 .Ft "struct TYPE *"
 131 .Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
 132 .Ft "struct TYPE *"
 133 .Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
 134 .Sh DESCRIPTION
 135 These macros define data structures for different types of trees:
 136 splay trees and red-black trees.
 137 .Pp
 138 In the macro definitions,
 139 .Fa TYPE
 140 is the name tag of a user defined structure that must contain a field of type
 141 .Li SPLAY_ENTRY ,
 142 or
 143 .Li RB_ENTRY ,
 144 named
 145 .Fa ENTRYNAME .
 146 The argument
 147 .Fa HEADNAME
 148 is the name tag of a user defined structure that must be declared
 149 using the macros
 150 .Fn SPLAY_HEAD
 151 or
 152 .Fn RB_HEAD .
 153 The argument
 154 .Fa NAME
 155 has to be a unique name prefix for every tree that is defined.
 156 .Pp
 157 The function prototypes are declared with either
 158 .Li SPLAY_PROTOTYPE
 159 or
 160 .Li RB_PROTOTYPE .
 161 The function bodies are generated with either
 162 .Li SPLAY_GENERATE
 163 or
 164 .Li RB_GENERATE .
 165 See the examples below for further explanation of how these macros are used.
 166 .Sh SPLAY TREES
 167 A splay tree is a self-organizing data structure.
 168 Every operation on the tree causes a splay to happen.
 169 The splay moves the requested node to the root of the tree and partly
 170 rebalances it.
 171 .Pp
 172 This has the benefit that request locality causes faster lookups as
 173 the requested nodes move to the top of the tree.
 174 On the other hand, every lookup causes memory writes.
 175 .Pp
 176 The Balance Theorem bounds the total access time for m operations
 177 and n inserts on an initially empty tree as O((m + n)lg n).
 178 The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
 179 .Pp
 180 A splay tree is headed by a structure defined by the
 181 .Fn SPLAY_HEAD
 182 macro.
 183 A
 184 .Fa SPLAY_HEAD
 185 structure is declared as follows:
 186 .Bd -literal -offset indent
 187 SPLAY_HEAD(HEADNAME, TYPE) head;
 188 .Ed
 189 .Pp
 190 where
 191 .Fa HEADNAME
 192 is the name of the structure to be defined, and struct
 193 .Fa TYPE
 194 is the type of the elements to be inserted into the tree.
 195 .Pp
 196 The
 197 .Fn SPLAY_ENTRY
 198 macro declares a structure that allows elements to be connected in the tree.
 199 .Pp
 200 In order to use the functions that manipulate the tree structure,
 201 their prototypes need to be declared with the
 202 .Fn SPLAY_PROTOTYPE
 203 macro,
 204 where
 205 .Fa NAME
 206 is a unique identifier for this particular tree.
 207 The
 208 .Fa TYPE
 209 argument is the type of the structure that is being managed
 210 by the tree.
 211 The
 212 .Fa FIELD
 213 argument is the name of the element defined by
 214 .Fn SPLAY_ENTRY .
 215 .Pp
 216 The function bodies are generated with the
 217 .Fn SPLAY_GENERATE
 218 macro.
 219 It takes the same arguments as the
 220 .Fn SPLAY_PROTOTYPE
 221 macro, but should be used only once.
 222 .Pp
 223 Finally,
 224 the
 225 .Fa CMP
 226 argument is the name of a function used to compare trees noded
 227 with each other.
 228 The function takes two arguments of type
 229 .Fa "struct TYPE *" .
 230 If the first argument is smaller than the second, the function returns a
 231 value smaller than zero.
 232 If they are equal, the function returns zero.
 233 Otherwise, it should return a value greater than zero.
 234 The compare function defines the order of the tree elements.
 235 .Pp
 236 The
 237 .Fn SPLAY_INIT
 238 macro initializes the tree referenced by
 239 .Fa head .
 240 .Pp
 241 The splay tree can also be initialized statically by using the
 242 .Fn SPLAY_INITIALIZER
 243 macro like this:
 244 .Bd -literal -offset indent
 245 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(\*[Am]head);
 246 .Ed
 247 .Pp
 248 The
 249 .Fn SPLAY_INSERT
 250 macro inserts the new element
 251 .Fa elm
 252 into the tree.
 253 .Pp
 254 The
 255 .Fn SPLAY_REMOVE
 256 macro removes the element
 257 .Fa elm
 258 from the tree pointed by
 259 .Fa head .
 260 .Pp
 261 The
 262 .Fn SPLAY_FIND
 263 macro can be used to find a particular element in the tree.
 264 .Bd -literal -offset indent
 265 struct TYPE find, *res;
 266 find.key = 30;
 267 res = SPLAY_FIND(NAME, head, \*[Am]find);
 268 .Ed
 269 .Pp
 270 The
 271 .Fn SPLAY_ROOT ,
 272 .Fn SPLAY_MIN ,
 273 .Fn SPLAY_MAX ,
 274 and
 275 .Fn SPLAY_NEXT
 276 macros can be used to traverse the tree:
 277 .Bd -literal -offset indent
 278 for (np = SPLAY_MIN(NAME, \*[Am]head); np != NULL; np = SPLAY_NEXT(NAME, \*[Am]head, np))
 279 .Ed
 280 .Pp
 281 Or, for simplicity, one can use the
 282 .Fn SPLAY_FOREACH
 283 macro:
 284 .Bd -literal -offset indent
 285 SPLAY_FOREACH(np, NAME, head)
 286 .Ed
 287 .Pp
 288 The
 289 .Fn SPLAY_EMPTY
 290 macro should be used to check whether a splay tree is empty.
 291 .Sh RED-BLACK TREES
 292 A red-black tree is a binary search tree with the node color as an
 293 extra attribute.
 294 It fulfills a set of conditions:
 295 .Bl -enum -compact -offset indent
 296 .It
 297 every search path from the root to a leaf consists of the same number of
 298 black nodes,
 299 .It
 300 each red node (except for the root) has a black parent,
 301 .It
 302 each leaf node is black.
 303 .El
 304 .Pp
 305 Every operation on a red-black tree is bounded as O(lg n).
 306 The maximum height of a red-black tree is 2lg (n+1).
 307 .Pp
 308 A red-black tree is headed by a structure defined by the
 309 .Fn RB_HEAD
 310 macro.
 311 A
 312 .Fa RB_HEAD
 313 structure is declared as follows:
 314 .Bd -literal -offset indent
 315 RB_HEAD(HEADNAME, TYPE) head;
 316 .Ed
 317 .Pp
 318 where
 319 .Fa HEADNAME
 320 is the name of the structure to be defined, and struct
 321 .Fa TYPE
 322 is the type of the elements to be inserted into the tree.
 323 .Pp
 324 The
 325 .Fn RB_ENTRY
 326 macro declares a structure that allows elements to be connected in the tree.
 327 .Pp
 328 In order to use the functions that manipulate the tree structure,
 329 their prototypes need to be declared with the
 330 .Fn RB_PROTOTYPE
 331 macro,
 332 where
 333 .Fa NAME
 334 is a unique identifier for this particular tree.
 335 The
 336 .Fa TYPE
 337 argument is the type of the structure that is being managed
 338 by the tree.
 339 The
 340 .Fa FIELD
 341 argument is the name of the element defined by
 342 .Fn RB_ENTRY .
 343 .Pp
 344 The function bodies are generated with the
 345 .Fn RB_GENERATE
 346 macro.
 347 It takes the same arguments as the
 348 .Fn RB_PROTOTYPE
 349 macro, but should be used only once.
 350 .Pp
 351 Finally,
 352 the
 353 .Fa CMP
 354 argument is the name of a function used to compare trees noded
 355 with each other.
 356 The function takes two arguments of type
 357 .Fa "struct TYPE *" .
 358 If the first argument is smaller than the second, the function returns a
 359 value smaller than zero.
 360 If they are equal, the function returns zero.
 361 Otherwise, it should return a value greater than zero.
 362 The compare function defines the order of the tree elements.
 363 .Pp
 364 The
 365 .Fn RB_INIT
 366 macro initializes the tree referenced by
 367 .Fa head .
 368 .Pp
 369 The redblack tree can also be initialized statically by using the
 370 .Fn RB_INITIALIZER
 371 macro like this:
 372 .Bd -literal -offset indent
 373 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(\*[Am]head);
 374 .Ed
 375 .Pp
 376 The
 377 .Fn RB_INSERT
 378 macro inserts the new element
 379 .Fa elm
 380 into the tree.
 381 .Pp
 382 The
 383 .Fn RB_REMOVE
 384 macro removes the element
 385 .Fa elm
 386 from the tree pointed by
 387 .Fa head .
 388 .Pp
 389 The
 390 .Fn RB_FIND
 391 macro can be used to find a particular element in the tree.
 392 .Bd -literal -offset indent
 393 struct TYPE find, *res;
 394 find.key = 30;
 395 res = RB_FIND(NAME, head, \*[Am]find);
 396 .Ed
 397 .Pp
 398 The
 399 .Fn RB_ROOT ,
 400 .Fn RB_MIN ,
 401 .Fn RB_MAX ,
 402 and
 403 .Fn RB_NEXT
 404 macros can be used to traverse the tree:
 405 .Bd -literal -offset indent
 406 for (np = RB_MIN(NAME, \*[Am]head); np != NULL; np = RB_NEXT(NAME, \*[Am]head, np))
 407 .Ed
 408 .Pp
 409 Or, for simplicity, one can use the
 410 .Fn RB_FOREACH
 411 macro:
 412 .Bd -literal -offset indent
 413 RB_FOREACH(np, NAME, head)
 414 .Ed
 415 .Pp
 416 The
 417 .Fn RB_EMPTY
 418 macro should be used to check whether a red-black tree is empty.
 419 .Sh NOTES
 420 Trying to free a tree in the following way is a common error:
 421 .Bd -literal -offset indent
 422 SPLAY_FOREACH(var, NAME, head) {
 423         SPLAY_REMOVE(NAME, head, var);
 424         free(var);
 425 }
 426 free(head);
 427 .Ed
 428 .Pp
 429 Since
 430 .Va var
 431 is free'd, the
 432 .Fn FOREACH
 433 macro refers to a pointer that may have been reallocated already.
 434 Proper code needs a second variable.
 435 .Bd -literal -offset indent
 436 for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
 437         nxt = SPLAY_NEXT(NAME, head, var);
 438         SPLAY_REMOVE(NAME, head, var);
 439         free(var);
 440 }
 441 .Ed
 442 .Pp
 443 Both
 444 .Fn RB_INSERT
 445 and
 446 .Fn SPLAY_INSERT
 447 return
 448 .Dv NULL
 449 if the element was inserted in the tree successfully, otherwise they
 450 return a pointer to the element with the colliding key.
 451 .Pp
 452 Accordingly,
 453 .Fn RB_REMOVE
 454 and
 455 .Fn SPLAY_REMOVE
 456 return the pointer to the removed element, otherwise they return
 457 .Dv NULL
 458 to indicate an error.
 459 .Sh AUTHORS
 460 The author of the tree macros is
 461 .An Niels Provos .