contrib/bind9/lib/isc/include/isc/heap.h

   1 /*
   2  * Copyright (C) 2004-2007, 2009, 2012  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1997-2001  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or 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.26 2009/01/17 23:47:43 tbox Exp $ */
  19
  20 #ifndef ISC_HEAP_H
  21 #define ISC_HEAP_H 1
  22
  23 /*! \file isc/heap.h */
  24
  25 #include <isc/lang.h>
  26 #include <isc/types.h>
  27
  28 ISC_LANG_BEGINDECLS
  29
  30 /*%
  31  * The comparison 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  * Heap elements are indexed from 1.
  64  *
  65  * Requires:
  66  *\li   "mctx" is valid.
  67  *\li   "compare" is a function which takes two void * arguments and
  68  *      returns ISC_TRUE if the first argument has a higher priority than
  69  *      the second, and ISC_FALSE otherwise.
  70  *\li   "index" is a function which takes a void *, and an unsigned int
  71  *      argument.  This function will be called whenever an element's
  72  *      index value changes, so it may continue to delete itself from the
  73  *      heap.  This option may be NULL if this functionality is unneeded.
  74  *\li   "size_increment" is a hint about how large the heap should grow
  75  *      when resizing is needed.  If this is 0, a default size will be
  76  *      used, which is currently 1024, allowing space for an additional 1024
  77  *      heap elements to be inserted before adding more space.
  78  *\li   "heapp" is not NULL, and "*heap" is NULL.
  79  *
  80  * Returns:
  81  *\li   ISC_R_SUCCESS           - success
  82  *\li   ISC_R_NOMEMORY          - insufficient memory
  83  */
  84
  85 void
  86 isc_heap_destroy(isc_heap_t **heapp);
  87 /*!<
  88  * \brief Destroys a heap.
  89  *
  90  * Requires:
  91  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
  92  */
  93
  94 isc_result_t
  95 isc_heap_insert(isc_heap_t *heap, void *elt);
  96 /*!<
  97  * \brief Inserts a new element into a heap.
  98  *
  99  * Requires:
 100  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 101  */
 102
 103 void
 104 isc_heap_delete(isc_heap_t *heap, unsigned int index);
 105 /*!<
 106  * \brief Deletes an element from a heap, by element index.
 107  *
 108  * Requires:
 109  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 110  *\li   "index" is a valid element index, as provided by the "index" callback
 111  *      provided during heap creation.
 112  */
 113
 114 void
 115 isc_heap_increased(isc_heap_t *heap, unsigned int index);
 116 /*!<
 117  * \brief Indicates to the heap that an element's priority has increased.
 118  * This function MUST be called whenever an element has increased in priority.
 119  *
 120  * Requires:
 121  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 122  *\li   "index" is a valid element index, as provided by the "index" callback
 123  *      provided during heap creation.
 124  */
 125
 126 void
 127 isc_heap_decreased(isc_heap_t *heap, unsigned int index);
 128 /*!<
 129  * \brief Indicates to the heap that an element's priority has decreased.
 130  * This function MUST be called whenever an element has decreased in priority.
 131  *
 132  * Requires:
 133  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 134  *\li   "index" is a valid element index, as provided by the "index" callback
 135  *      provided during heap creation.
 136  */
 137
 138 void *
 139 isc_heap_element(isc_heap_t *heap, unsigned int index);
 140 /*!<
 141  * \brief Returns the element for a specific element index.
 142  *
 143  * Requires:
 144  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 145  *\li   "index" is a valid element index, as provided by the "index" callback
 146  *      provided during heap creation.
 147  *
 148  * Returns:
 149  *\li   A pointer to the element for the element index.
 150  */
 151
 152 void
 153 isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap);
 154 /*!<
 155  * \brief Iterate over the heap, calling an action for each element.  The
 156  * order of iteration is not sorted.
 157  *
 158  * Requires:
 159  *\li   "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
 160  *\li   "action" is not NULL, and is a function which takes two arguments.
 161  *      The first is a void *, representing the element, and the second is
 162  *      "uap" as provided to isc_heap_foreach.
 163  *\li   "uap" is a caller-provided argument, and may be NULL.
 164  *
 165  * Note:
 166  *\li   The heap structure CANNOT be modified during this iteration.  The only
 167  *      safe function to call while iterating the heap is isc_heap_element().
 168  */
 169
 170 ISC_LANG_ENDDECLS
 171
 172 #endif /* ISC_HEAP_H */