Return to gtree.3 CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libpdel / util

libpdel

    1: .\" Copyright (c) 2001-2002 Packet Design, LLC.
    2: .\" All rights reserved.
    3: .\" 
    4: .\" Subject to the following obligations and disclaimer of warranty,
    5: .\" use and redistribution of this software, in source or object code
    6: .\" forms, with or without modifications are expressly permitted by
    7: .\" Packet Design; provided, however, that:
    8: .\" 
    9: .\"    (i)  Any and all reproductions of the source or object code
   10: .\"         must include the copyright notice above and the following
   11: .\"         disclaimer of warranties; and
   12: .\"    (ii) No rights are granted, in any manner or form, to use
   13: .\"         Packet Design trademarks, including the mark "PACKET DESIGN"
   14: .\"         on advertising, endorsements, or otherwise except as such
   15: .\"         appears in the above copyright notice or in the software.
   16: .\" 
   17: .\" THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
   18: .\" TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
   19: .\" REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
   20: .\" THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
   21: .\" WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
   22: .\" OR NON-INFRINGEMENT.  PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
   23: .\" OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
   24: .\" OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
   25: .\" RELIABILITY OR OTHERWISE.  IN NO EVENT SHALL PACKET DESIGN BE
   26: .\" LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
   27: .\" OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
   28: .\" INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
   29: .\" DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
   30: .\" USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
   31: .\" LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   32: .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
   33: .\" THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
   34: .\" THE POSSIBILITY OF SUCH DAMAGE.
   35: .\"
   36: .\" Author: Archie Cobbs <archie@freebsd.org>
   37: .\"
   38: .\" $Id: gtree.3,v 1.1.1.1 2012/02/21 23:25:53 misho Exp $
   39: .\"
   40: .Dd April 22, 2002
   41: .Dt GTREE 3
   42: .Os
   43: .Sh NAME
   44: .Nm gtree
   45: .Nd generic balanced tree library
   46: .Sh LIBRARY
   47: PDEL Library (libpdel, \-lpdel)
   48: .Sh SYNOPSIS
   49: .In sys/types.h
   50: .In stdio.h
   51: .In pdel/util/gtree.h
   52: .Ft "struct gtree *"
   53: .Fn gtree_create "void *arg" "const char *mtype" "gtree_cmp_t *cmp" "gtree_add_t *add" "gtree_del_t *del" "gtree_print_t print"
   54: .Ft void
   55: .Fn gtree_destroy "struct gtree **gp"
   56: .Ft void
   57: .Fn gtree_arg "struct gtree *g"
   58: .Ft "void *"
   59: .Fn gtree_get "struct gtree *g" "const void *item"
   60: .Ft int
   61: .Fn gtree_put "struct gtree *g" "const void *item"
   62: .Ft int
   63: .Fn gtree_put_prealloc "struct gtree *g" "const void *item" "void *node"
   64: .Ft u_int
   65: .Fn gtree_node_size "void"
   66: .Ft int
   67: .Fn gtree_remove "struct gtree *g" "const void *item"
   68: .Ft u_int
   69: .Fn gtree_size "struct gtree *g"
   70: .Ft "void *"
   71: .Fn gtree_first "struct gtree *g"
   72: .Ft "void *"
   73: .Fn gtree_last "struct gtree *g"
   74: .Ft "void *"
   75: .Fn gtree_next "struct gtree *g" "const void *item"
   76: .Ft "void *"
   77: .Fn gtree_prev "struct gtree *g" "const void *item"
   78: .Ft int
   79: .Fn gtree_traverse "struct gtree *g" "int (*handler)(struct gtree *g, void *item)"
   80: .Ft int
   81: .Fn gtree_dump "struct gtree *g" "void ***listp" "const char *mtype"
   82: .Ft void
   83: .Fn gtree_print "struct gtree *g" "FILE *fp"
   84: .Sh DESCRIPTION
   85: The
   86: .Nm gtree
   87: functions implement a generic balanced tree data structure.
   88: A balanced tree stores a sorted set of items of type
   89: .Ft "void *"
   90: and guarantees O(log n) search time.
   91: The user code supplies callback routines for:
   92: .Bl -bullet -offset 3n
   93: .It
   94: Comparing two items
   95: .It
   96: Housekeeping associated with adding and removing an item
   97: .El
   98: .Pp
   99: .Fn gtree_create
  100: creates a new tree.
  101: The
  102: .Fa arg
  103: parameter can be retrieved at any time via
  104: .Fn gtree_arg
  105: and is otherwise ignored.
  106: .Fa mtype
  107: is a typed memory type string (see
  108: .Xr typed_mem 3 )
  109: used when allocating memory for the tree.
  110: .Pp
  111: The
  112: .Fa cmp ,
  113: .Fa add ,
  114: .Fa del ,
  115: and
  116: .Fa print
  117: parameters are pointers to user-supplied callback functions having
  118: the following types:
  119: .Bd -literal -offset 3n
  120: typedef int     gtree_cmp_t(struct gtree *g,
  121:                     const void *item1, const void *item2);
  122: typedef void    gtree_add_t(struct gtree *g, void *item);
  123: typedef void    gtree_del_t(struct gtree *g, void *item);
  124: typedef const   char *gtree_print_t(struct gtree *g, const void *item);
  125: 
  126: .Ed
  127: The
  128: .Fa cmp
  129: function should return an integer that is negative, zero, or positive
  130: if the first item is less than, equal to, or greater than the second.
  131: This function must return values consistent with a total ordering
  132: of the items.
  133: If not specified,
  134: .Dv "item1 - item2"
  135: is used, i.e., the sorting is based on the pointers themselves.
  136: .Pp
  137: The
  138: .Fa add
  139: and
  140: .Fa del
  141: routines, if not
  142: .Dv NULL ,
  143: will be called whenever an item is added to, or removed from, the tree.
  144: For example, if
  145: .Fn gtree_put
  146: causes a new item to replace an old item, there will be a call to the
  147: .Fa del
  148: function for the old item, followed by a call to the
  149: .Fa add
  150: function for the new item.
  151: These callbacks are typically used to increase and decrease reference counts.
  152: .Pp
  153: The
  154: .Fa print
  155: callback (also optional) is used by
  156: .Fn gtree_print
  157: to print an item when dumping the contents of the tree for debugging.
  158: .Pp
  159: .Fn gtree_destroy
  160: destroys a tree and free's all associated memory.
  161: If any items remain in the tree, the
  162: .Fa del
  163: callback will be invoked once for each item.
  164: Note that this function takes a pointer to a pointer to a tree.
  165: Upon return, the pointer to the tree will be set to
  166: .Dv NULL .
  167: If it is already equal to
  168: .Dv NULL ,
  169: .Fn gtree_destroy
  170: does nothing.
  171: .Pp
  172: .Fn gtree_get
  173: retrieves an item previously stored in the tree, or else returns
  174: .Dv NULL
  175: if the item is not found.
  176: .Pp
  177: .Fn gtree_put
  178: adds an item to the tree, replacing any item that is equal to it
  179: (as determined by the
  180: .Fa cmp
  181: callback).
  182: .Dv NULL
  183: is an invalid item and may not be stored in a tree.
  184: .Pp
  185: .Fn gtree_put_prealloc
  186: is equivalent to
  187: .Fn gtree_put
  188: except that the caller pre-allocates the memory necessary to add
  189: the item to the tree, which guarantees a successful operation.
  190: .Fa node
  191: must point to memory allocated with the same
  192: .Xr typed_mem 3
  193: memory type as was passed to
  194: .Fn gtree_new
  195: and the size of this memory block must be at least as large as the
  196: size of an internal node, which is returned by
  197: .Fn gtree_node_size .
  198: .Pp
  199: .Fn gtree_remove
  200: removes an item from the tree.
  201: If the item does not exist, nothing happens.
  202: .Pp
  203: .Fn gtree_size
  204: returns the number of items in the tree.
  205: .Pp
  206: .Fn gtree_first
  207: and
  208: .Fn gtree_last
  209: return the first and last items in the tree, respectively, or
  210: .Dv NULL
  211: if the tree is empty.
  212: .Fn gtree_next
  213: and
  214: .Fn gtree_prev
  215: return the next and previous item in the tree to
  216: .Fa item ,
  217: or
  218: .Dv NULL
  219: if there are no more items in the tree.
  220: Traversing the entire tree via
  221: .Fn gtree_next
  222: and
  223: .Fn gtree_prev
  224: takes O(n log n) time, where n is the number of items in the tree.
  225: .Pp
  226: .Fn gtree_traverse
  227: traverses the items in the tree in order, invoking
  228: .Fa handler
  229: with each item.
  230: If
  231: .Fa handler
  232: returns -1, the traversal stops and
  233: .Fn gtree_traverse
  234: immediately returns -1 to the caller.
  235: Otherwise,
  236: .Fn gtree_traverse
  237: returns 0 after all items have been traversed.
  238: Any attempt to modify the tree before
  239: .Fn gtree_traverse
  240: returns will return an error.
  241: .Pp
  242: .Fn gtree_dump
  243: generates a sorted array of all the items in the tree.
  244: A pointer to the array is stored in
  245: .Fa "*listp" .
  246: The array is allocated with memory type
  247: .Fa mtype .
  248: The caller must eventually free the array, also using
  249: .Fa mtype .
  250: .Pp
  251: .Fn gtree_print
  252: prints out the tree for debugging purposes.
  253: .Sh RETURN VALUES
  254: .Fn gtree_put
  255: and
  256: .Fn gtree_put_prealloc
  257: return 0 if the item is new, or 1 if the item replaced an existing item.
  258: .Pp
  259: .Fn gtree_remove
  260: returns 0 if the item was not found, or 1 if the item was found and removed.
  261: .Pp
  262: .Fn gtree_dump
  263: returns the number of items in the generated array.
  264: .Pp
  265: .Fn gtree_create ,
  266: .Fn gtree_put ,
  267: and
  268: .Fn gtree_dump
  269: return -1 or
  270: .Dv NULL
  271: to indicate an error;
  272: .Va errno
  273: will be set to the appropriate value.
  274: .Sh IMPLEMENTATION NOTES
  275: The
  276: .Nm gtree
  277: library is designed to gracefully handle certain bugs in the user code.
  278: For example, a reentrant call to
  279: .Fn gtree_put
  280: from within the
  281: .Fa add
  282: callback function called as a result of a previous call to
  283: .Fn gtree_put
  284: will return an error with
  285: .Va errno
  286: set to
  287: .Er EBUSY .
  288: .Sh SEE ALSO
  289: .Xr ghash 3 ,
  290: .Xr libpdel 3 ,
  291: .Xr typed_mem 3
  292: .Sh HISTORY
  293: The PDEL library was developed at Packet Design, LLC.
  294: .Dv "http://www.packetdesign.com/"
  295: .Sh AUTHORS
  296: .An Archie Cobbs Aq archie@freebsd.org