lib/heap.c

   1 /*
   2  * Copyright (c) 2012 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 #include <config.h>
  18 #include "heap.h"
  19 #include <stdlib.h>
  20 #include "util.h"
  21
  22 static void put_node(struct heap *, struct heap_node *, size_t i);
  23 static void swap_nodes(struct heap *, size_t i, size_t j);
  24 static bool float_up(struct heap *, size_t i);
  25 static void float_down(struct heap *, size_t i);
  26 static void float_up_or_down(struct heap *, size_t i);
  27 \f
  28 /* Initializes 'heap' as an empty heap. */
  29 void
  30 heap_init(struct heap *heap)
  31 {
  32     heap->array = NULL;
  33     heap->n = 0;
  34     heap->allocated = 0;
  35 }
  36
  37 /* Frees memory owned internally by 'heap'.  The caller is responsible for
  38  * freeing 'heap' itself, if necessary. */
  39 void
  40 heap_destroy(struct heap *heap)
  41 {
  42     if (heap) {
  43         free(heap->array);
  44     }
  45 }
  46
  47 /* Removes all of the elements from 'heap', without freeing any allocated
  48  * memory. */
  49 void
  50 heap_clear(struct heap *heap)
  51 {
  52     heap->n = 0;
  53 }
  54
  55 /* Exchanges the contents of 'a' and 'b'. */
  56 void
  57 heap_swap(struct heap *a, struct heap *b)
  58 {
  59     struct heap tmp = *a;
  60     *a = *b;
  61     *b = tmp;
  62 }
  63
  64 /* Inserts 'node' into 'heap' with the specified 'priority'.
  65  *
  66  * This takes time O(lg n). */
  67 void
  68 heap_insert(struct heap *heap, struct heap_node *node, uint64_t priority)
  69 {
  70     heap_raw_insert(heap, node, priority);
  71     float_up(heap, node->idx);
  72 }
  73
  74 /* Removes 'node' from 'heap'.
  75  *
  76  * This takes time O(lg n). */
  77 void
  78 heap_remove(struct heap *heap, struct heap_node *node)
  79 {
  80     size_t i = node->idx;
  81
  82     heap_raw_remove(heap, node);
  83     if (i <= heap->n) {
  84         float_up_or_down(heap, i);
  85     }
  86 }
  87
  88 /* Changes the priority of 'node' (which must be in 'heap') to 'priority'.
  89  *
  90  * This takes time O(lg n). */
  91 void
  92 heap_change(struct heap *heap, struct heap_node *node, uint64_t priority)
  93 {
  94     heap_raw_change(node, priority);
  95     float_up_or_down(heap, node->idx);
  96 }
  97
  98 /* Inserts 'node' into 'heap' with the specified 'priority', without
  99  * maintaining the heap invariant.
 100  *
 101  * After this call, heap_max() will no longer necessarily return the maximum
 102  * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in
 103  * heap level order, until the next call to heap_rebuild(heap).
 104  *
 105  * This takes time O(1). */
 106 void
 107 heap_raw_insert(struct heap *heap, struct heap_node *node, uint64_t priority)
 108 {
 109     if (heap->n >= heap->allocated) {
 110         heap->allocated = heap->n == 0 ? 1 : 2 * heap->n;
 111         heap->array = xrealloc(heap->array,
 112                                (heap->allocated + 1) * sizeof *heap->array);
 113     }
 114
 115     put_node(heap, node, ++heap->n);
 116     node->priority = priority;
 117 }
 118
 119 /* Removes 'node' from 'heap', without maintaining the heap invariant.
 120  *
 121  * After this call, heap_max() will no longer necessarily return the maximum
 122  * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in
 123  * heap level order, until the next call to heap_rebuild(heap).
 124  *
 125  * This takes time O(1). */
 126 void
 127 heap_raw_remove(struct heap *heap, struct heap_node *node)
 128 {
 129     size_t i = node->idx;
 130     if (i < heap->n) {
 131         put_node(heap, heap->array[heap->n], i);
 132     }
 133     heap->n--;
 134 }
 135
 136 /* Rebuilds 'heap' to restore the heap invariant following a series of one or
 137  * more calls to heap_raw_*() functions.  (Otherwise this function need not be
 138  * called.)
 139  *
 140  * This takes time O(n) in the current size of the heap. */
 141 void
 142 heap_rebuild(struct heap *heap)
 143 {
 144     size_t i;
 145
 146     for (i = heap->n / 2; i >= 1; i--) {
 147         float_down(heap, i);
 148     }
 149 }
 150 \f
 151 static void
 152 put_node(struct heap *heap, struct heap_node *node, size_t i)
 153 {
 154     heap->array[i] = node;
 155     node->idx = i;
 156 }
 157
 158 static void
 159 swap_nodes(struct heap *heap, size_t i, size_t j)
 160 {
 161     struct heap_node *old_i = heap->array[i];
 162     struct heap_node *old_j = heap->array[j];
 163
 164     put_node(heap, old_j, i);
 165     put_node(heap, old_i, j);
 166 }
 167
 168 static bool
 169 float_up(struct heap *heap, size_t i)
 170 {
 171     bool moved = false;
 172     size_t parent;
 173
 174     for (; i > 1; i = parent) {
 175         parent = heap_parent__(i);
 176         if (heap->array[parent]->priority >= heap->array[i]->priority) {
 177             break;
 178         }
 179         swap_nodes(heap, parent, i);
 180         moved = true;
 181     }
 182     return moved;
 183 }
 184
 185 static void
 186 float_down(struct heap *heap, size_t i)
 187 {
 188     while (!heap_is_leaf__(heap, i)) {
 189         size_t left = heap_left__(i);
 190         size_t right = heap_right__(i);
 191         size_t max = i;
 192
 193         if (heap->array[left]->priority > heap->array[max]->priority) {
 194             max = left;
 195         }
 196         if (right <= heap->n
 197             && heap->array[right]->priority > heap->array[max]->priority) {
 198             max = right;
 199         }
 200         if (max == i) {
 201             break;
 202         }
 203
 204         swap_nodes(heap, max, i);
 205         i = max;
 206     }
 207 }
 208
 209 static void
 210 float_up_or_down(struct heap *heap, size_t i)
 211 {
 212     if (!float_up(heap, i)) {
 213         float_down(heap, i);
 214     }
 215 }
 216