]>
Commit | Line | Data |
---|---|---|
95974447 | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2012 Nicira, Inc. |
95974447 BP |
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 | |
1a29a798 | 68 | heap_insert(struct heap *heap, struct heap_node *node, uint64_t priority) |
95974447 BP |
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 | |
1a29a798 | 92 | heap_change(struct heap *heap, struct heap_node *node, uint64_t priority) |
95974447 BP |
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 | |
1a29a798 | 107 | heap_raw_insert(struct heap *heap, struct heap_node *node, uint64_t priority) |
95974447 BP |
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 |