contrib/bind-9.3/lib/isc/include/isc/heap.h

   1 /*
   2  * Copyright (C) 2004-2006  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.16.206.2 2006/04/17 18:27:20 explorer Exp $ */
  19
  20 #ifndef ISC_HEAP_H
  21 #define ISC_HEAP_H 1
  22
  23 /*! \file */
  24
  25 #include <isc/lang.h>
  26 #include <isc/types.h>
  27
  28 ISC_LANG_BEGINDECLS
  29
  30 /*%
  31  * The comparision function returns ISC_TRUE if the first argument has
  32  * higher priority than the second argument, and ISC_FALSE otherwise.
  33  */
  34 typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *);
  35
  36 /*%
  37  * The index function allows the client of the heap to receive a callback
  38  * when an item's index number changes.  This allows it to maintain
  39  * sync with its external state, but still delete itself, since deletions
  40  * from the heap require the index be provided.
  41  */
  42 typedef void (*isc_heapindex_t)(void *, unsigned int);
  43
  44 /*%
  45  * The heapaction function is used when iterating over the heap.
  46  *
  47  * NOTE:  The heap structure CANNOT BE MODIFIED during the call to
  48  * isc_heap_foreach().
  49  */
  50 typedef void (*isc_heapaction_t)(void *, void *);
  51
  52 typedef struct isc_heap isc_heap_t;
  53
  54 isc_result_t
  55 isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare,
  56                 isc_heapindex_t index, unsigned int size_increment,
  57                 isc_heap_t **heapp);
  58 /*!<
  59  * \brief Create a new heap.  The heap is implemented using a space-efficient
  60  * storage method.  When the heap elements are deleted space is not freed
  61  * but will be reused when new elements are inserted.
  62  *
  63  * Requires:
  64  *\li   "mctx" is valid.
  65  *\li   "compare" is a function which takes two void * arguments and
  66  *      returns ISC_TRUE if the first argument has a higher priority than
  67  *      the second, and ISC_FALSE otherwise.
  68  *\li   "index" is a function which takes a void *, and an unsigned int
  69  *      argument.  This function will be called whenever an element's
  70  *      index value changes, so it may continue to delete itself from the
  71  *      heap.  This option may be NULL if this functionality is unneeded.
  72  *\li   "size_increment" is a hint about how large the heap should grow
  73  *      when resizing is needed.  If this is 0, a default size will be
  74  *      used, which is currently 1024, allowing space for an additional 1024
  75  *      heap elements to be inserted before adding more space.
  76  *\li   "heapp" is not NULL, and "*heap" is NULL.
  77  *
  78  * Returns:
  79  *\li   ISC_R_SUCCESS           - success
  80  *\li   ISC_R_NOMEMORY          - insufficient memory
  81  */
  82
  83 void
  84 isc_heap_destroy(isc_heap_t **heapp);
  85 /*!<
  86  * \brief Destroys a heap.
  87  *
  88  * Requires:
  89  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  90  */
  91
  92 isc_result_t
  93 isc_heap_insert(isc_heap_t *heap, void *elt);
  94 /*!<
  95  * \brief Inserts a new element into a heap.
  96  *
  97  * Requires:
  98  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  99  */
 100
 101 void
 102 isc_heap_delete(isc_heap_t *heap, unsigned int index);
 103 /*!<
 104  * \brief Deletes an element from a heap, by element index.
 105  *
 106  * Requires:
 107  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 108  *\li   "index" is a valid element index, as provided by the "index" callback
 109  *      provided during heap creation.
 110  */
 111
 112 void
 113 isc_heap_increased(isc_heap_t *heap, unsigned int index);
 114 /*!<
 115  * \brief Indicates to the heap that an element's priority has increased.
 116  * This function MUST be called whenever an element has increased in priority.
 117  *
 118  * Requires:
 119  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 120  *\li   "index" is a valid element index, as provided by the "index" callback
 121  *      provided during heap creation.
 122  */
 123
 124 void
 125 isc_heap_decreased(isc_heap_t *heap, unsigned int index);
 126 /*!<
 127  * \brief Indicates to the heap that an element's priority has decreased.
 128  * This function MUST be called whenever an element has decreased in priority.
 129  *
 130  * Requires:
 131  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 132  *\li   "index" is a valid element index, as provided by the "index" callback
 133  *      provided during heap creation.
 134  */
 135
 136 void *
 137 isc_heap_element(isc_heap_t *heap, unsigned int index);
 138 /*!<
 139  * \brief Returns the element for a specific element index.
 140  *
 141  * Requires:
 142  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 143  *\li   "index" is a valid element index, as provided by the "index" callback
 144  *      provided during heap creation.
 145  *
 146  * Returns:
 147  *\li   A pointer to the element for the element index.
 148  */
 149
 150 void
 151 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap);
 152 /*!<
 153  * \brief Iterate over the heap, calling an action for each element.  The
 154  * order of iteration is not sorted.
 155  *
 156  * Requires:
 157  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 158  *\li   "action" is not NULL, and is a function which takes two arguments.
 159  *      The first is a void *, representing the element, and the second is
 160  *      "uap" as provided to isc_heap_foreach.
 161  *\li   "uap" is a caller-provided argument, and may be NULL.
 162  *
 163  * Note:
 164  *\li   The heap structure CANNOT be modified during this iteration.  The only
 165  *      safe function to call while iterating the heap is isc_heap_element().
 166  */
 167
 168 ISC_LANG_ENDDECLS
 169
 170 #endif /* ISC_HEAP_H */