sat-math: Introduce macro version of SAT_MUL.
[openvswitch] / 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, uint32_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, uint32_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, uint32_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