Return to gtree.h CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / mpd / src / contrib / libpdel / util |
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: */ 1.1.1.2 ! misho 115: extern void *gtree_get(struct gtree *g, void *item); 1.1 misho 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: */ 1.1.1.2 ! misho 126: extern int gtree_put(struct gtree *g, void *item); 1.1 misho 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, 1.1.1.2 ! misho 136: void *item, void *node); 1.1 misho 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: