Man Linux: Main Page and Category List

NAME

       gg-tree,    GG_SPLAY_PROTOTYPE,    GG_SPLAY_GENERATE,   GG_SPLAY_ENTRY,
       GG_SPLAY_HEAD,  GG_SPLAY_INITIALIZER,  GG_SPLAY_ROOT,   GG_SPLAY_EMPTY,
       GG_SPLAY_NEXT,      GG_SPLAY_MIN,      GG_SPLAY_MAX,     GG_SPLAY_FIND,
       GG_SPLAY_LEFT,   GG_SPLAY_RIGHT,    GG_SPLAY_FOREACH,    GG_SPLAY_INIT,
       GG_SPLAY_INSERT,   GG_SPLAY_REMOVE,   GG_RB_PROTOTYPE,  GG_RB_GENERATE,
       GG_RB_ENTRY, GG_RB_HEAD,  GG_RB_INITIALIZER,  GG_RB_ROOT,  GG_RB_EMPTY,
       GG_RB_NEXT,  GG_RB_MIN, GG_RB_MAX, GG_RB_FIND, GG_RB_LEFT, GG_RB_RIGHT,
       GG_RB_PARENT, GG_RB_FOREACH, GG_RB_INIT, GG_RB_INSERT,  GG_RB_REMOVE  -
       implementations of splay and red-black trees

SYNOPSIS

       #include <ggi/gg-tree.h>

       GG_SPLAY_PROTOTYPE(NAME, TYPE, FIELD, CMP);

       GG_SPLAY_GENERATE(NAME, TYPE, FIELD, CMP);

       GG_SPLAY_ENTRY(TYPE);

       GG_SPLAY_HEAD(HEADNAME, TYPE);

       struct TYPE *
       GG_SPLAY_INITIALIZER(GG_SPLAY_HEAD *head);

       GG_SPLAY_ROOT(GG_SPLAY_HEAD *head);

       bool
       GG_SPLAY_EMPTY(GG_SPLAY_HEAD *head);

       struct TYPE *
       GG_SPLAY_NEXT(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_SPLAY_MIN(NAME, GG_SPLAY_HEAD *head);

       struct TYPE *
       GG_SPLAY_MAX(NAME, GG_SPLAY_HEAD *head);

       struct TYPE *
       GG_SPLAY_FIND(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_SPLAY_LEFT(struct TYPE *elm, GG_SPLAY_ENTRY NAME);

       struct TYPE *
       GG_SPLAY_RIGHT(struct TYPE *elm, GG_SPLAY_ENTRY NAME);

       GG_SPLAY_FOREACH(VARNAME, NAME, GG_SPLAY_HEAD *head);

       void
       GG_SPLAY_INIT(GG_SPLAY_HEAD *head);

       struct TYPE *
       GG_SPLAY_INSERT(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_SPLAY_REMOVE(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);

       GG_RB_PROTOTYPE(NAME, TYPE, FIELD, CMP);

       GG_RB_GENERATE(NAME, TYPE, FIELD, CMP);

       GG_RB_ENTRY(TYPE);

       GG_RB_HEAD(HEADNAME, TYPE);

       GG_RB_INITIALIZER(GG_RB_HEAD *head);

       struct TYPE *
       GG_RB_ROOT(GG_RB_HEAD *head);

       bool
       GG_RB_EMPTY(GG_RB_HEAD *head);

       struct TYPE *
       GG_RB_NEXT(NAME, GG_RB_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_RB_MIN(NAME, GG_RB_HEAD *head);

       struct TYPE *
       GG_RB_MAX(NAME, GG_RB_HEAD *head);

       struct TYPE *
       GG_RB_FIND(NAME, GG_RB_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_RB_LEFT(struct TYPE *elm, GG_RB_ENTRY NAME);

       struct TYPE *
       GG_RB_RIGHT(struct TYPE *elm, GG_RB_ENTRY NAME);

       struct TYPE *
       GG_RB_PARENT(struct TYPE *elm, GG_RB_ENTRY NAME);

       GG_RB_FOREACH(VARNAME, NAME, GG_RB_HEAD *head);

       void
       GG_RB_INIT(GG_RB_HEAD *head);

       struct TYPE *
       GG_RB_INSERT(NAME, GG_RB_HEAD *head, struct TYPE *elm);

       struct TYPE *
       GG_RB_REMOVE(NAME, GG_RB_HEAD *head, struct TYPE *elm);

DESCRIPTION

       These macros define data structures for different types of trees: splay
       trees and red-black trees.

       In the macro definitions, TYPE is  the  name  tag  of  a  user  defined
       structure  that  must  contain  a  field  of  type  GG_SPLAY_ENTRY,  or
       GG_RB_ENTRY, named ENTRYNAME. The argument HEADNAME is the name tag  of
       a  user  defined  structure  that  must  be  declared  using the macros
       GG_SPLAY_HEAD or GG_RB_HEAD. The argument NAME has to be a unique  name
       prefix for every tree that is defined.

       The  function prototypes are declared with either GG_SPLAY_PROTOTYPE or
       GG_RB_PROTOTYPE.  The  function  bodies  are  generated   with   either
       GG_SPLAY_GENERATE or GG_RB_GENERATE. See the examples below for further
       explanation of how these macros are used.

SPLAY TREES

       A splay tree is a self-organizing data structure.  Every  operation  on
       the  tree causes a splay to happen.  The splay moves the requested node
       to the root of the tree and partly rebalances it.

       This has the benefit that request locality causes faster lookups as the
       requested  nodes move to the top of the tree.  On the other hand, every
       lookup causes memory writes.

       The Balance Theorem bounds the total access time for m operations and n
       inserts  on  an  initially empty tree as O((m + n)lg n).  The amortized
       cost for a sequence of m accesses to a splay tree is O(lg n).

       A splay tree is headed by a structure defined by the SPLAY_HEAD  macro.
       A GG_SPLAY_HEAD structure is declared as follows:

       GG_SPLAY_HEAD(HEADNAME, TYPE) head;

       where  HEADNAME  is the name of the structure to be defined, and struct
       TYPE is the type of the elements to be inserted into the tree.

       The GG_SPLAY_ENTRY macro declares a structure that allows  elements  to
       be connected in the tree.

       In order to use the functions that manipulate the tree structure, their
       prototypes need to be declared with the GG_SPLAY_PROTOTYPE macro, where
       NAME  is  a  unique  identifier  for  this  particular  tree.  The TYPE
       argument is the type of the structure that  is  being  managed  by  the
       tree.   The  FIELD  argument  is  the  name  of  the element defined by
       GG_SPLAY_ENTRY.

       The function bodies are generated with the GG_SPLAY_GENERATE macro.  It
       takes the same arguments as the GG_SPLAY_PROTOTYPE macro, but should be
       used only once.

       Finally, the CMP argument is the name of a  function  used  to  compare
       trees  noded with each other.  The function takes two arguments of type
       struct TYPE *.  If the first argument is smaller than the  second,  the
       function  returns  a  value  smaller than zero.  If they are equal, the
       function returns zero.  Otherwise, it should  return  a  value  greater
       than  zero.   The  compare  function  defines  the  order  of  the tree
       elements.

       The GG_SPLAY_INIT macro initializes the tree referenced by head.

       The splay  tree  can  also  be  initialized  statically  by  using  the
       GG_SPLAY_INITIALIZER macro like this:

       GG_SPLAY_HEAD(HEADNAME, TYPE) head = GG_SPLAY_INITIALIZER(&head);

       The GG_SPLAY_INSERT macro inserts the new element elm into the tree.

       The GG_SPLAY_REMOVE macro removes the element elm from the tree pointed
       by head.

       The GG_SPLAY_FIND macro can be used to find a particular element in the
       tree.:

       struct TYPE find, *res;
       find.key = 30;
       res = GG_SPLAY_FIND(NAME, head, &find);

       The GG_SPLAY_ROOT, GG_SPLAY_MIN, GG_SPLAY_MAX, and GG_SPLAY_NEXT macros
       can be used to traverse the tree:

       for (np = GG_SPLAY_MIN(NAME, &head); np != NULL; np = GG_SPLAY_NEXT(NAME, &head, np))

       Or, for simplicity, one can use the GG_SPLAY_FOREACH macro:

       GG_SPLAY_FOREACH(np, NAME, head)

       The GG_SPLAY_EMPTY macro should be used to check whether a  splay  tree
       is empty.

RED-BLACK TREES

       A  red-black  tree  is  a  binary search tree with the node color as an
       extra attribute.  It fulfills a set of conditions:

       1   every search path from the root to a  leaf  consists  of  the  same
           number of black nodes,

       2   each red node (except for the root) has a black parent,

       3   each leaf node is black.

       Every operation on a red-black tree is bounded as O(lg n).  The maximum
       height of a red-black tree is 2lg (n+1).

       A red-black tree is headed by a structure  defined  by  the  GG_RB_HEAD
       macro.  A GG_RB_HEAD structure is declared as follows:

       GG_RB_HEAD(HEADNAME, TYPE) head;

       where  HEADNAME  is the name of the structure to be defined, and struct
       TYPE is the type of the elements to be inserted into the tree.

       The GG_RB_ENTRY macro declares a structure that allows elements  to  be
       connected in the tree.

       In order to use the functions that manipulate the tree structure, their
       prototypes need to be declared with the  GG_RB_PROTOTYPE  macro,  where
       NAME is a unique identifier for this particular tree. The TYPE argument
       is the type of the structure that is being managed by  the  tree.   The
       FIELD argument is the name of the element defined by GG_RB_ENTRY.

       The  function  bodies  are  generated with the GG_RB_GENERATE macro. It
       takes the same arguments as the GG_RB_PROTOTYPE macro,  but  should  be
       used only once.

       Finally,  the  CMP  argument  is the name of a function used to compare
       trees noded with each other.  The function takes two arguments of  type
       struct  TYPE  *.  If the first argument is smaller than the second, the
       function returns a value smaller than zero.  If  they  are  equal,  the
       function  returns  zero.   Otherwise,  it should return a value greater
       than zero.   The  compare  function  defines  the  order  of  the  tree
       elements.

       The GG_RB_INIT macro initializes the tree referenced by head.

       The  redblack  tree  can  also  be  initialized statically by using the
       GG_RB_INITIALIZER macro like this:

       GG_RB_HEAD(HEADNAME, TYPE) head = GG_RB_INITIALIZER(&head);

       The GG_RB_INSERT macro inserts the new element elm into the tree.

       The GG_RB_REMOVE macro removes the element elm from the tree pointed by
       head.

       The  GG_RB_FIND  macro  can be used to find a particular element in the
       tree.:

       struct TYPE find, *res;
       find.key = 30;
       res = GG_RB_FIND(NAME, head, &find);

       The GG_RB_ROOT, GG_RB_MIN, GG_RB_MAX, and GG_RB_NEXT macros can be used
       to traverse the tree:

       for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))

       Or, for simplicity, one can use the RB_FOREACH macro:

       GG_RB_FOREACH(np, NAME, head)

       The  GG_RB_EMPTY macro should be used to check whether a red-black tree
       is empty.

NOTES

       Trying to free a tree in the following way is a common error:

       GG_SPLAY_FOREACH(var, NAME, head) {
               GG_SPLAY_REMOVE(NAME, head, var);
               free(var);
       }
       free(head);

       Since var is free’d, the FOREACH macro refers to  a  pointer  that  may
       have been reallocated already.  Proper code needs a second variable.:

       for (var = GG_SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
               nxt = GG_SPLAY_NEXT(NAME, head, var);
               GG_SPLAY_REMOVE(NAME, head, var);
               free(var);
       }

       Both  GG_RB_INSERT  and  GG_SPLAY_INSERT return NULL if the element was
       inserted in the tree successfully, otherwise they return a  pointer  to
       the element with the colliding key.

       Accordingly, GG_RB_REMOVE and GG_SPLAY_REMOVE return the pointer to the
       removed element, otherwise they return NULL to indicate an error.

SEE ALSO

       gg-queue(3)