Branch data Line data Source code
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 : :
28 : : /* Initializes 'heap' as an empty heap. */
29 : : void
30 : 269580 : heap_init(struct heap *heap)
31 : : {
32 : 269580 : heap->array = NULL;
33 : 269580 : heap->n = 0;
34 : 269580 : heap->allocated = 0;
35 : 269580 : }
36 : :
37 : : /* Frees memory owned internally by 'heap'. The caller is responsible for
38 : : * freeing 'heap' itself, if necessary. */
39 : : void
40 : 109950 : heap_destroy(struct heap *heap)
41 : : {
42 [ + - ]: 109950 : if (heap) {
43 : 109950 : free(heap->array);
44 : : }
45 : 109950 : }
46 : :
47 : : /* Removes all of the elements from 'heap', without freeing any allocated
48 : : * memory. */
49 : : void
50 : 0 : heap_clear(struct heap *heap)
51 : : {
52 : 0 : heap->n = 0;
53 : 0 : }
54 : :
55 : : /* Exchanges the contents of 'a' and 'b'. */
56 : : void
57 : 0 : heap_swap(struct heap *a, struct heap *b)
58 : : {
59 : 0 : struct heap tmp = *a;
60 : 0 : *a = *b;
61 : 0 : *b = tmp;
62 : 0 : }
63 : :
64 : : /* Inserts 'node' into 'heap' with the specified 'priority'.
65 : : *
66 : : * This takes time O(lg n). */
67 : : void
68 : 474284 : heap_insert(struct heap *heap, struct heap_node *node, uint64_t priority)
69 : : {
70 : 474284 : heap_raw_insert(heap, node, priority);
71 : 474284 : float_up(heap, node->idx);
72 : 474284 : }
73 : :
74 : : /* Removes 'node' from 'heap'.
75 : : *
76 : : * This takes time O(lg n). */
77 : : void
78 : 474274 : heap_remove(struct heap *heap, struct heap_node *node)
79 : : {
80 : 474274 : size_t i = node->idx;
81 : :
82 : 474274 : heap_raw_remove(heap, node);
83 [ + + ]: 474274 : if (i <= heap->n) {
84 : 296030 : float_up_or_down(heap, i);
85 : : }
86 : 474274 : }
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 : 87683 : heap_change(struct heap *heap, struct heap_node *node, uint64_t priority)
93 : : {
94 : 87683 : heap_raw_change(node, priority);
95 : 87683 : float_up_or_down(heap, node->idx);
96 : 87683 : }
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 : 525564 : heap_raw_insert(struct heap *heap, struct heap_node *node, uint64_t priority)
108 : : {
109 [ + + ]: 525564 : if (heap->n >= heap->allocated) {
110 [ + + ]: 312683 : heap->allocated = heap->n == 0 ? 1 : 2 * heap->n;
111 : 312683 : heap->array = xrealloc(heap->array,
112 : 312683 : (heap->allocated + 1) * sizeof *heap->array);
113 : : }
114 : :
115 : 525564 : put_node(heap, node, ++heap->n);
116 : 525564 : node->priority = priority;
117 : 525564 : }
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 : 525554 : heap_raw_remove(struct heap *heap, struct heap_node *node)
128 : : {
129 : 525554 : size_t i = node->idx;
130 [ + + ]: 525554 : if (i < heap->n) {
131 : 331422 : put_node(heap, heap->array[heap->n], i);
132 : : }
133 : 525554 : heap->n--;
134 : 525554 : }
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 : 42327 : heap_rebuild(struct heap *heap)
143 : : {
144 : : size_t i;
145 : :
146 [ + + ]: 105819 : for (i = heap->n / 2; i >= 1; i--) {
147 : 63492 : float_down(heap, i);
148 : : }
149 : 42327 : }
150 : :
151 : : static void
152 : 1861962 : put_node(struct heap *heap, struct heap_node *node, size_t i)
153 : : {
154 : 1861962 : heap->array[i] = node;
155 : 1861962 : node->idx = i;
156 : 1861962 : }
157 : :
158 : : static void
159 : 502488 : swap_nodes(struct heap *heap, size_t i, size_t j)
160 : : {
161 : 502488 : struct heap_node *old_i = heap->array[i];
162 : 502488 : struct heap_node *old_j = heap->array[j];
163 : :
164 : 502488 : put_node(heap, old_j, i);
165 : 502488 : put_node(heap, old_i, j);
166 : 502488 : }
167 : :
168 : : static bool
169 : 857997 : float_up(struct heap *heap, size_t i)
170 : : {
171 : 857997 : bool moved = false;
172 : : size_t parent;
173 : :
174 [ + + ]: 1106601 : for (; i > 1; i = parent) {
175 : 790367 : parent = heap_parent__(i);
176 [ + + ]: 790367 : if (heap->array[parent]->priority >= heap->array[i]->priority) {
177 : 541763 : break;
178 : : }
179 : 248604 : swap_nodes(heap, parent, i);
180 : 248604 : moved = true;
181 : : }
182 : 857997 : return moved;
183 : : }
184 : :
185 : : static void
186 : 432957 : float_down(struct heap *heap, size_t i)
187 : : {
188 [ + + ]: 686841 : while (!heap_is_leaf__(heap, i)) {
189 : 387406 : size_t left = heap_left__(i);
190 : 387406 : size_t right = heap_right__(i);
191 : 387406 : size_t max = i;
192 : :
193 [ + + ]: 387406 : if (heap->array[left]->priority > heap->array[max]->priority) {
194 : 229828 : max = left;
195 : : }
196 [ + + ]: 387406 : if (right <= heap->n
197 [ + + ]: 309394 : && heap->array[right]->priority > heap->array[max]->priority) {
198 : 109525 : max = right;
199 : : }
200 [ + + ]: 387406 : if (max == i) {
201 : 133522 : break;
202 : : }
203 : :
204 : 253884 : swap_nodes(heap, max, i);
205 : 253884 : i = max;
206 : : }
207 : 432957 : }
208 : :
209 : : static void
210 : 383713 : float_up_or_down(struct heap *heap, size_t i)
211 : : {
212 [ + + ]: 383713 : if (!float_up(heap, i)) {
213 : 369465 : float_down(heap, i);
214 : : }
215 : 383713 : }
216 : :
|
