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