Return to heap.h CVS log

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

Annotation of embedaddon/dhcp/includes/heap.h, revision 1.1.1.1

1.1       misho       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: 
1.1.1.1 ! misho      18: /* $Id: heap.h,v 1.3 2007/05/19 19:16:25 dhankins Exp $ */
1.1       misho      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 */