GG_RB_PARENT man page on Cygwin

Man page or keyword search:  
man Server   22533 pages
apropos Keyword Search (all sections)
Output format
Cygwin logo
[printable version]

gg-tree(3)			      GGI			    gg-tree(3)

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 struc‐
       ture  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 argu‐
       ment 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 ele‐
       ments.

       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 num‐
	   ber 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  ele‐
       ments.

       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)

libgg-1.0.x			  2005-08-26			    gg-tree(3)
[top]

List of man pages available for Cygwin

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net