git.ozlabs.org Git - ccan/blob - ccan/heap/heap.h

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #ifndef CCAN_HEAP_H
   3 #define CCAN_HEAP_H
   4
   5 #include <stdbool.h>
   6 #include <stdlib.h>
   7
   8 typedef bool (*heap_less_func_t)(const void *, const void *);
   9
  10 /**
  11  * struct heap - a simple, generic heap structure
  12  * @data: array of pointers to the heap's entries
  13  * @less: function to compare heap entries
  14  * @cap: capacity of the heap array in @data
  15  * @len: number of valid elements in the heap array
  16  *
  17  * The @less function determines the nature of the heap. If @less is
  18  * something akin to 'return a.foo < b.foo', then the heap will be
  19  * a min heap. Conversely, a '>' predicate will result in a max heap.
  20  *
  21  * Elements in the @data array are allocated as needed, hence the need for
  22  * @cap and @len.
  23  */
  24 struct heap {
  25         void **data;
  26         heap_less_func_t less;
  27         size_t cap;
  28         size_t len;
  29 };
  30
  31 /**
  32  * heap_init - allocate and initialise an empty heap
  33  * @less: function to be used to compare heap entries
  34  *
  35  * Returns a pointer to an initialised heap struct on success, NULL if
  36  * the heap could not be allocated.
  37  *
  38  * See also: HEAP_INIT()
  39  */
  40 struct heap *heap_init(heap_less_func_t less);
  41
  42 /**
  43  * HEAP_INIT - initialiser for an empty heap
  44  * @func: comparison function to be used in the heap
  45  *
  46  * Explicit initialiser for a heap.
  47  *
  48  * See also: heap_init()
  49  */
  50 #define HEAP_INIT(func) { NULL, func, 0, 0 }
  51
  52 /**
  53  * heap_free - free a heap allocated via heap_init()
  54  * @heap: the heap to be freed
  55  *
  56  * Note that this only frees the heap and its internal resources, not
  57  * the entries pointed to by it.
  58  *
  59  * See also: heap_init()
  60  */
  61 void heap_free(struct heap *heap);
  62
  63 /**
  64  * heap_ify - enforce the heap property based on a new comparison function
  65  * @h: heap to be heapified
  66  * @less: new comparison function
  67  *
  68  * Complexity: O(n)
  69  */
  70 void heap_ify(struct heap *h, heap_less_func_t less);
  71
  72 /**
  73  * heap_push - push a new heap entry
  74  * @h: heap to receive the new entry
  75  * @data: pointer to the new entry
  76  *
  77  * Returns 0 on success, -1 on error.
  78  *
  79  * Complexity: O(log n)
  80  *
  81  * See also: heap_pop()
  82  */
  83 int heap_push(struct heap *h, void *data);
  84
  85 /**
  86  * heap_pop - pops the root heap entry
  87  * @h: heap to pop the head from
  88  *
  89  * Returns the root entry of the heap after extracting it, or NULL on error.
  90  *
  91  * Note: Calling heap_pop() on an empty heap is a bug. When in doubt,
  92  * check heap->len. See heap_peek()'s documentation for an example.
  93  *
  94  * Complexity: O(log n)
  95  *
  96  * See also: heap_push(), heap_peek()
  97  */
  98 void *heap_pop(struct heap *h);
  99
 100 /**
 101  * heap_peek - inspect the root entry of a heap
 102  * @h: heap whose root entry is to be inspected
 103  *
 104  * Returns the root entry in the heap, without extracting it from @h.
 105  *
 106  * Note: Calling heap_peek() on an empty heap is a bug; check the heap's
 107  * number of items and act accordingly, as in the example below.
 108  *
 109  * See also: heap_pop()
 110  *
 111  * Example:
 112  *      static inline void *heap_peek_safe(const struct heap *h)
 113  *      {
 114  *              return h->len ? heap_peek(h) : NULL;
 115  *      }
 116  */
 117 static inline void *heap_peek(const struct heap *h)
 118 {
 119         return h->data[0];
 120 }
 121
 122 #endif /* CCAN_HEAP_H */