2 * Copyright (c) 2012 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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);
28 /* Initializes 'heap' as an empty heap. */
30 heap_init(struct heap *heap)
37 /* Frees memory owned internally by 'heap'. The caller is responsible for
38 * freeing 'heap' itself, if necessary. */
40 heap_destroy(struct heap *heap)
47 /* Removes all of the elements from 'heap', without freeing any allocated
50 heap_clear(struct heap *heap)
55 /* Exchanges the contents of 'a' and 'b'. */
57 heap_swap(struct heap *a, struct heap *b)
64 /* Inserts 'node' into 'heap' with the specified 'priority'.
66 * This takes time O(lg n). */
68 heap_insert(struct heap *heap, struct heap_node *node, uint32_t priority)
70 heap_raw_insert(heap, node, priority);
71 float_up(heap, node->idx);
74 /* Removes 'node' from 'heap'.
76 * This takes time O(lg n). */
78 heap_remove(struct heap *heap, struct heap_node *node)
82 heap_raw_remove(heap, node);
84 float_up_or_down(heap, i);
88 /* Changes the priority of 'node' (which must be in 'heap') to 'priority'.
90 * This takes time O(lg n). */
92 heap_change(struct heap *heap, struct heap_node *node, uint32_t priority)
94 heap_raw_change(node, priority);
95 float_up_or_down(heap, node->idx);
98 /* Inserts 'node' into 'heap' with the specified 'priority', without
99 * maintaining the heap invariant.
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).
105 * This takes time O(1). */
107 heap_raw_insert(struct heap *heap, struct heap_node *node, uint32_t priority)
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);
115 put_node(heap, node, ++heap->n);
116 node->priority = priority;
119 /* Removes 'node' from 'heap', without maintaining the heap invariant.
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).
125 * This takes time O(1). */
127 heap_raw_remove(struct heap *heap, struct heap_node *node)
129 size_t i = node->idx;
131 put_node(heap, heap->array[heap->n], i);
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
140 * This takes time O(n) in the current size of the heap. */
142 heap_rebuild(struct heap *heap)
146 for (i = heap->n / 2; i >= 1; i--) {
152 put_node(struct heap *heap, struct heap_node *node, size_t i)
154 heap->array[i] = node;
159 swap_nodes(struct heap *heap, size_t i, size_t j)
161 struct heap_node *old_i = heap->array[i];
162 struct heap_node *old_j = heap->array[j];
164 put_node(heap, old_j, i);
165 put_node(heap, old_i, j);
169 float_up(struct heap *heap, size_t i)
174 for (; i > 1; i = parent) {
175 parent = heap_parent__(i);
176 if (heap->array[parent]->priority >= heap->array[i]->priority) {
179 swap_nodes(heap, parent, i);
186 float_down(struct heap *heap, size_t i)
188 while (!heap_is_leaf__(heap, i)) {
189 size_t left = heap_left__(i);
190 size_t right = heap_right__(i);
193 if (heap->array[left]->priority > heap->array[max]->priority) {
197 && heap->array[right]->priority > heap->array[max]->priority) {
204 swap_nodes(heap, max, i);
210 float_up_or_down(struct heap *heap, size_t i)
212 if (!float_up(heap, i)) {