lib/heap.h

   1 /*
   2  * Copyright (c) 2012, 2013 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef HEAP_H
  18 #define HEAP_H 1
  19
  20 #include <stdbool.h>
  21 #include <stddef.h>
  22 #include <stdint.h>
  23
  24 /* A heap node, to be embedded inside the data structure in the heap. */
  25 struct heap_node {
  26     size_t idx;
  27     uint64_t priority;
  28 };
  29
  30 /* A max-heap. */
  31 struct heap {
  32     struct heap_node **array;   /* Data in elements 1...n, element 0 unused. */
  33     size_t n;                   /* Number of nodes currently in the heap. */
  34     size_t allocated;           /* Max 'n' before 'array' must be enlarged. */
  35 };
  36
  37 /* Initialization. */
  38 void heap_init(struct heap *);
  39 void heap_destroy(struct heap *);
  40 void heap_clear(struct heap *);
  41 void heap_swap(struct heap *a, struct heap *b);
  42 static inline size_t heap_count(const struct heap *);
  43 static inline bool heap_is_empty(const struct heap *);
  44
  45 /* Insertion and deletion. */
  46 void heap_insert(struct heap *, struct heap_node *, uint64_t priority);
  47 void heap_change(struct heap *, struct heap_node *, uint64_t priority);
  48 void heap_remove(struct heap *, struct heap_node *);
  49 static inline struct heap_node *heap_pop(struct heap *);
  50
  51 /* Maximum.  */
  52 static inline struct heap_node *heap_max(const struct heap *);
  53
  54 /* The "raw" functions below do not preserve the heap invariants.  After you
  55  * call them, heap_max() will not necessarily return the right value until you
  56  * subsequently call heap_rebuild(). */
  57 void heap_raw_insert(struct heap *, struct heap_node *, uint64_t priority);
  58 static inline void heap_raw_change(struct heap_node *, uint64_t priority);
  59 void heap_raw_remove(struct heap *, struct heap_node *);
  60 void heap_rebuild(struct heap *);
  61
  62 /* Iterates through each NODE in HEAP, where NODE->MEMBER must be a "struct
  63  * heap_node".  Iterates in heap level order, which in particular means that
  64  * the first node visited is the maximum value in the heap.
  65  *
  66  * If a heap_raw_*() function has been called without a later call to
  67  * heap_rebuild(), then the first node visited may not be the maximum
  68  * element. */
  69 #define HEAP_FOR_EACH(NODE, MEMBER, HEAP)                           \
  70     for (((HEAP)->n > 0                                             \
  71           ? INIT_CONTAINER(NODE, (HEAP)->array[1], MEMBER)          \
  72           : ((NODE) = NULL, (void) 0));                               \
  73          (NODE) != NULL;                                            \
  74          ((NODE)->MEMBER.idx < (HEAP)->n                            \
  75           ? ASSIGN_CONTAINER(NODE,                                  \
  76                              (HEAP)->array[(NODE)->MEMBER.idx + 1], \
  77                              MEMBER)                                \
  78           : ((NODE) = NULL, (void) 0)))
  79 \f
  80 /* Returns the index of the node that is the parent of the node with the given
  81  * 'idx' within a heap. */
  82 static inline size_t
  83 heap_parent__(size_t idx)
  84 {
  85     return idx / 2;
  86 }
  87
  88 /* Returns the index of the node that is the left child of the node with the
  89  * given 'idx' within a heap. */
  90 static inline size_t
  91 heap_left__(size_t idx)
  92 {
  93     return idx * 2;
  94 }
  95
  96 /* Returns the index of the node that is the right child of the node with the
  97  * given 'idx' within a heap. */
  98 static inline size_t
  99 heap_right__(size_t idx)
 100 {
 101     return idx * 2 + 1;
 102 }
 103
 104 /* Returns true if 'idx' is the index of a leaf node in 'heap', false
 105  * otherwise. */
 106 static inline bool
 107 heap_is_leaf__(const struct heap *heap, size_t idx)
 108 {
 109     return heap_left__(idx) > heap->n;
 110 }
 111
 112 /* Returns the number of elements in 'heap'. */
 113 static inline size_t
 114 heap_count(const struct heap *heap)
 115 {
 116     return heap->n;
 117 }
 118
 119 /* Returns true if 'heap' is empty, false if it contains at least one
 120  * element. */
 121 static inline bool
 122 heap_is_empty(const struct heap *heap)
 123 {
 124     return heap->n == 0;
 125 }
 126
 127 /* Returns the largest element in 'heap'.
 128  *
 129  * The caller must ensure that 'heap' contains at least one element.
 130  *
 131  * The return value may be wrong (i.e. not the maximum element but some other
 132  * element) if a heap_raw_*() function has been called without a later call to
 133  * heap_rebuild(). */
 134 static inline struct heap_node *
 135 heap_max(const struct heap *heap)
 136 {
 137     return heap->array[1];
 138 }
 139
 140 /* Removes an arbitrary node from 'heap', in O(1), maintaining the heap
 141  * invariant.  Returns the node removed.
 142  *
 143  * The caller must ensure that 'heap' contains at least one element. */
 144 static inline struct heap_node *
 145 heap_pop(struct heap *heap)
 146 {
 147     return heap->array[heap->n--];
 148 }
 149
 150 /* Changes the priority of 'node' (which must be in 'heap') to 'priority'.
 151  *
 152  * After this call, heap_max() will no longer necessarily return the maximum
 153  * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in
 154  * heap level order, until the next call to heap_rebuild(heap).
 155  *
 156  * This takes time O(1). */
 157 static inline void
 158 heap_raw_change(struct heap_node *node, uint64_t priority)
 159 {
 160     node->priority = priority;
 161 }
 162
 163 #endif /* heap.h */