Annotation of embedaddon/libpdel/util/gtree.3, revision 1.1.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