Return to gtree.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libpdel / util

libpdel

    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: