external/bsd/dhcp/dist/includes/heap.h

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