Annotation of embedaddon/libpdel/util/gtree.3, revision 1.1
1.1 ! misho 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.9 2004/06/02 17:24:38 archie 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
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gtree.3 CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libpdel / util