Annotation of embedaddon/mpd/src/contrib/libpdel/util/gtree.h, revision 1.1.1.1
1.1 misho 1:
2: /*
3: * Copyright (c) 2001-2002 Packet Design, LLC.
4: * All rights reserved.
5: *
6: * Subject to the following obligations and disclaimer of warranty,
7: * use and redistribution of this software, in source or object code
8: * forms, with or without modifications are expressly permitted by
9: * Packet Design; provided, however, that:
10: *
11: * (i) Any and all reproductions of the source or object code
12: * must include the copyright notice above and the following
13: * disclaimer of warranties; and
14: * (ii) No rights are granted, in any manner or form, to use
15: * Packet Design trademarks, including the mark "PACKET DESIGN"
16: * on advertising, endorsements, or otherwise except as such
17: * appears in the above copyright notice or in the software.
18: *
19: * THIS SOFTWARE IS BEING PROVIDED BY PACKET DESIGN "AS IS", AND
20: * TO THE MAXIMUM EXTENT PERMITTED BY LAW, PACKET DESIGN MAKES NO
21: * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING
22: * THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED
23: * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
24: * OR NON-INFRINGEMENT. PACKET DESIGN DOES NOT WARRANT, GUARANTEE,
25: * OR MAKE ANY REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS
26: * OF THE USE OF THIS SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY,
27: * RELIABILITY OR OTHERWISE. IN NO EVENT SHALL PACKET DESIGN BE
28: * LIABLE FOR ANY DAMAGES RESULTING FROM OR ARISING OUT OF ANY USE
29: * OF THIS SOFTWARE, INCLUDING WITHOUT LIMITATION, ANY DIRECT,
30: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, PUNITIVE, OR CONSEQUENTIAL
31: * DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, LOSS OF
32: * USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY THEORY OF
33: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
35: * THE USE OF THIS SOFTWARE, EVEN IF PACKET DESIGN IS ADVISED OF
36: * THE POSSIBILITY OF SUCH DAMAGE.
37: *
38: * Author: Archie Cobbs <archie@freebsd.org>
39: */
40:
41: #ifndef _PDEL_UTIL_GTREE_H_
42: #define _PDEL_UTIL_GTREE_H_
43:
44: /*
45: * General purpose balanced trees.
46: */
47:
48: /**********************************************************************
49: TREE FUNCTION TYPES
50: **********************************************************************/
51:
52: struct gtree;
53:
54: /*
55: * How to compare two items. Should return -, 0, or + if item1
56: * is less than, equal to, or greater than item2.
57: *
58: * If this function is not specified, then "item1 - item2" is used.
59: */
60: typedef int gtree_cmp_t(struct gtree *g,
61: const void *item1, const void *item2);
62:
63: /*
64: * Notification that an item is being added to the table.
65: *
66: * Supplying this function is optional.
67: */
68: typedef void gtree_add_t(struct gtree *g, void *item);
69:
70: /*
71: * Notification that an item is being removed from the table.
72: *
73: * Supplying this function is optional.
74: */
75: typedef void gtree_del_t(struct gtree *g, void *item);
76:
77: /*
78: * Return a string description of a node in a static buffer.
79: * This is for tracing.
80: *
81: * Supplying this function is optional.
82: */
83: typedef const char *gtree_print_t(struct gtree *g, const void *item);
84:
85: /**********************************************************************
86: TREE METHODS
87: **********************************************************************/
88:
89: __BEGIN_DECLS
90:
91: /*
92: * Create a new hash table.
93: */
94: extern struct gtree *gtree_create(void *arg, const char *mtype,
95: gtree_cmp_t *cmp, gtree_add_t *add,
96: gtree_del_t *del, gtree_print_t *print);
97:
98: /*
99: * Destroy a hash table.
100: *
101: * Any items remaining in the table will be removed first.
102: */
103: extern void gtree_destroy(struct gtree **gp);
104:
105: /*
106: * Get the argument supplied to gtree_create().
107: */
108: extern void *gtree_arg(struct gtree *g);
109:
110: /*
111: * Get an item.
112: *
113: * Returns the item, or NULL if the item does not exist.
114: */
115: extern void *gtree_get(struct gtree *g, const void *item);
116:
117: /*
118: * Put an item.
119: *
120: * Returns 0 if the item is new, 1 if it replaces an existing
121: * item, and -1 if there was an error.
122: *
123: * Note: NULL is an invalid item because gtree_get() returns
124: * NULL to indicate that the item was not found.
125: */
126: extern int gtree_put(struct gtree *g, const void *item);
127:
128: /*
129: * Same as gtree_put() but caller supplies a pre-allocated
130: * node structure which must be allocated with the 'memtype'
131: * supplied to gtree_new() and have size gtree_node_size().
132: * gtree_put_prealloc() assumes responsibility for freeing
133: * this memory. gtree_put_prealloc() never returns -1.
134: */
135: extern int gtree_put_prealloc(struct gtree *g,
136: const void *item, void *node);
137:
138: /*
139: * Remove an item.
140: *
141: * Returns 1 if the item was found and removed, 0 if not found.
142: */
143: extern int gtree_remove(struct gtree *g, const void *item);
144:
145: /*
146: * Traverse the tree in order.
147: *
148: * The handler should return -1 to cancel the traverse.
149: * Returns -1 if the traverse was stopped, otherwise zero.
150: *
151: * No modifications to the tree are allowed by the handler.
152: */
153: extern int gtree_traverse(struct gtree *g,
154: int (*handler)(struct gtree *g, void *item));
155:
156: /*
157: * Get the size of the table.
158: */
159: extern u_int gtree_size(struct gtree *g);
160:
161: /*
162: * Get the size of a node.
163: */
164: extern u_int gtree_node_size(void);
165:
166: /*
167: * Get the first item.
168: *
169: * Returns the item, or NULL if the tree is empty.
170: */
171: extern void *gtree_first(struct gtree *g);
172:
173: /*
174: * Get the next item after 'item'.
175: *
176: * Returns the next item, or NULL if item was the last item
177: * or item does not exist in the tree.
178: */
179: extern void *gtree_next(struct gtree *g, const void *item);
180:
181: /*
182: * Get the previous item before 'item'.
183: *
184: * Returns the previous item, or NULL if item was the first item
185: * or item does not exist in the tree.
186: */
187: extern void *gtree_prev(struct gtree *g, const void *item);
188:
189: /*
190: * Get the last item.
191: *
192: * Returns the item, or NULL if the tree is empty.
193: */
194: extern void *gtree_last(struct gtree *g);
195:
196: /*
197: * Get a sorted array of items.
198: *
199: * Returns number of items in the list, or -1 if error.
200: * Caller must free the list.
201: */
202: extern int gtree_dump(struct gtree *g, void ***listp, const char *mtype);
203:
204: #ifndef _KERNEL
205: /*
206: * Print out a tree
207: */
208: extern void gtree_print(struct gtree *g, FILE *fp);
209: #endif
210:
211: __END_DECLS
212:
213: #endif /* _PDEL_UTIL_GTREE_H_ */
214:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gtree.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util