Return to heap.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / dhcp / includes

dhcp 4.1 r7

    1: /*
    2:  * Copyright (C) 2004-2007  Internet Systems Consortium, Inc. ("ISC")
    3:  * Copyright (C) 1997-2001  Internet Software Consortium.
    4:  *
    5:  * Permission to use, copy, modify, and distribute this software for any
    6:  * purpose with or without fee is hereby granted, provided that the above
    7:  * copyright notice and this permission notice appear in all copies.
    8:  *
    9:  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
   10:  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
   11:  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
   12:  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
   13:  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
   14:  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
   15:  * PERFORMANCE OF THIS SOFTWARE.
   16:  */
   17: 
   18: /* $Id: heap.h,v 1.1.1.1 2012/10/09 09:06:54 misho Exp $ */
   19: 
   20: #ifndef ISC_HEAP_H
   21: #define ISC_HEAP_H 1
   22: 
   23: /*! \file isc/heap.h */
   24: 
   25: /*%
   26:  * The comparision function returns ISC_TRUE if the first argument has
   27:  * higher priority than the second argument, and ISC_FALSE otherwise.
   28:  */
   29: typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *);
   30: 
   31: /*%
   32:  * The index function allows the client of the heap to receive a callback
   33:  * when an item's index number changes.  This allows it to maintain
   34:  * sync with its external state, but still delete itself, since deletions
   35:  * from the heap require the index be provided.
   36:  */
   37: typedef void (*isc_heapindex_t)(void *, unsigned int);
   38: 
   39: /*%
   40:  * The heapaction function is used when iterating over the heap.
   41:  *
   42:  * NOTE:  The heap structure CANNOT BE MODIFIED during the call to
   43:  * isc_heap_foreach().
   44:  */
   45: typedef void (*isc_heapaction_t)(void *, void *);
   46: 
   47: typedef struct isc_heap isc_heap_t;
   48: 
   49: isc_result_t
   50: isc_heap_create(isc_heapcompare_t compare,
   51: 		isc_heapindex_t index, unsigned int size_increment,
   52: 		isc_heap_t **heapp);
   53: /*!<
   54:  * \brief Create a new heap.  The heap is implemented using a space-efficient
   55:  * storage method.  When the heap elements are deleted space is not freed
   56:  * but will be reused when new elements are inserted.
   57:  *
   58:  * Requires:
   59:  *\li	"mctx" is valid.
   60:  *\li	"compare" is a function which takes two void * arguments and
   61:  *	returns ISC_TRUE if the first argument has a higher priority than
   62:  *	the second, and ISC_FALSE otherwise.
   63:  *\li	"index" is a function which takes a void *, and an unsigned int
   64:  *	argument.  This function will be called whenever an element's
   65:  *	index value changes, so it may continue to delete itself from the
   66:  *	heap.  This option may be NULL if this functionality is unneeded.
   67:  *\li	"size_increment" is a hint about how large the heap should grow
   68:  *	when resizing is needed.  If this is 0, a default size will be
   69:  *	used, which is currently 1024, allowing space for an additional 1024
   70:  *	heap elements to be inserted before adding more space.
   71:  *\li	"heapp" is not NULL, and "*heap" is NULL.
   72:  *
   73:  * Returns:
   74:  *\li	ISC_R_SUCCESS		- success
   75:  *\li	ISC_R_NOMEMORY		- insufficient memory
   76:  */
   77: 
   78: void
   79: isc_heap_destroy(isc_heap_t **heapp);
   80: /*!<
   81:  * \brief Destroys a heap.
   82:  *
   83:  * Requires:
   84:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
   85:  */
   86: 
   87: isc_result_t
   88: isc_heap_insert(isc_heap_t *heap, void *elt);
   89: /*!<
   90:  * \brief Inserts a new element into a heap.
   91:  *
   92:  * Requires:
   93:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
   94:  */
   95: 
   96: void
   97: isc_heap_delete(isc_heap_t *heap, unsigned int index);
   98: /*!<
   99:  * \brief Deletes an element from a heap, by element index.
  100:  *
  101:  * Requires:
  102:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  103:  *\li	"index" is a valid element index, as provided by the "index" callback
  104:  *	provided during heap creation.
  105:  */
  106: 
  107: void
  108: isc_heap_increased(isc_heap_t *heap, unsigned int index);
  109: /*!<
  110:  * \brief Indicates to the heap that an element's priority has increased.
  111:  * This function MUST be called whenever an element has increased in priority.
  112:  *
  113:  * Requires:
  114:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  115:  *\li	"index" is a valid element index, as provided by the "index" callback
  116:  *	provided during heap creation.
  117:  */
  118: 
  119: void
  120: isc_heap_decreased(isc_heap_t *heap, unsigned int index);
  121: /*!<
  122:  * \brief Indicates to the heap that an element's priority has decreased.
  123:  * This function MUST be called whenever an element has decreased in priority.
  124:  *
  125:  * Requires:
  126:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  127:  *\li	"index" is a valid element index, as provided by the "index" callback
  128:  *	provided during heap creation.
  129:  */
  130: 
  131: void *
  132: isc_heap_element(isc_heap_t *heap, unsigned int index);
  133: /*!<
  134:  * \brief Returns the element for a specific element index.
  135:  *
  136:  * Requires:
  137:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  138:  *\li	"index" is a valid element index, as provided by the "index" callback
  139:  *	provided during heap creation.
  140:  *
  141:  * Returns:
  142:  *\li	A pointer to the element for the element index.
  143:  */
  144: 
  145: void
  146: isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap);
  147: /*!<
  148:  * \brief Iterate over the heap, calling an action for each element.  The
  149:  * order of iteration is not sorted.
  150:  *
  151:  * Requires:
  152:  *\li	"heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  153:  *\li	"action" is not NULL, and is a function which takes two arguments.
  154:  *	The first is a void *, representing the element, and the second is
  155:  *	"uap" as provided to isc_heap_foreach.
  156:  *\li	"uap" is a caller-provided argument, and may be NULL.
  157:  *
  158:  * Note:
  159:  *\li	The heap structure CANNOT be modified during this iteration.  The only
  160:  *	safe function to call while iterating the heap is isc_heap_element().
  161:  */
  162: 
  163: #endif /* ISC_HEAP_H */