]>
Commit | Line | Data |
---|---|---|
95974447 | 1 | /* |
33e191a0 | 2 | * Copyright (c) 2012, 2013 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 | #ifndef HEAP_H | |
18 | #define HEAP_H 1 | |
19 | ||
20 | #include <stdbool.h> | |
21 | #include <stddef.h> | |
22 | #include <stdint.h> | |
23 | ||
24 | /* A heap node, to be embedded inside the data structure in the heap. */ | |
25 | struct heap_node { | |
26 | size_t idx; | |
1a29a798 | 27 | uint64_t priority; |
95974447 BP |
28 | }; |
29 | ||
30 | /* A max-heap. */ | |
31 | struct heap { | |
32 | struct heap_node **array; /* Data in elements 1...n, element 0 unused. */ | |
33 | size_t n; /* Number of nodes currently in the heap. */ | |
34 | size_t allocated; /* Max 'n' before 'array' must be enlarged. */ | |
35 | }; | |
36 | ||
37 | /* Initialization. */ | |
38 | void heap_init(struct heap *); | |
39 | void heap_destroy(struct heap *); | |
40 | void heap_clear(struct heap *); | |
41 | void heap_swap(struct heap *a, struct heap *b); | |
42 | static inline size_t heap_count(const struct heap *); | |
43 | static inline bool heap_is_empty(const struct heap *); | |
44 | ||
45 | /* Insertion and deletion. */ | |
1a29a798 AW |
46 | void heap_insert(struct heap *, struct heap_node *, uint64_t priority); |
47 | void heap_change(struct heap *, struct heap_node *, uint64_t priority); | |
95974447 BP |
48 | void heap_remove(struct heap *, struct heap_node *); |
49 | static inline struct heap_node *heap_pop(struct heap *); | |
50 | ||
51 | /* Maximum. */ | |
52 | static inline struct heap_node *heap_max(const struct heap *); | |
53 | ||
54 | /* The "raw" functions below do not preserve the heap invariants. After you | |
55 | * call them, heap_max() will not necessarily return the right value until you | |
56 | * subsequently call heap_rebuild(). */ | |
1a29a798 AW |
57 | void heap_raw_insert(struct heap *, struct heap_node *, uint64_t priority); |
58 | static inline void heap_raw_change(struct heap_node *, uint64_t priority); | |
95974447 BP |
59 | void heap_raw_remove(struct heap *, struct heap_node *); |
60 | void heap_rebuild(struct heap *); | |
61 | ||
62 | /* Iterates through each NODE in HEAP, where NODE->MEMBER must be a "struct | |
63 | * heap_node". Iterates in heap level order, which in particular means that | |
64 | * the first node visited is the maximum value in the heap. | |
65 | * | |
66 | * If a heap_raw_*() function has been called without a later call to | |
67 | * heap_rebuild(), then the first node visited may not be the maximum | |
68 | * element. */ | |
69 | #define HEAP_FOR_EACH(NODE, MEMBER, HEAP) \ | |
70 | for (((HEAP)->n > 0 \ | |
f17e8ad6 | 71 | ? INIT_CONTAINER(NODE, (HEAP)->array[1], MEMBER) \ |
33e191a0 | 72 | : ((NODE) = NULL, (void) 0)); \ |
95974447 BP |
73 | (NODE) != NULL; \ |
74 | ((NODE)->MEMBER.idx < (HEAP)->n \ | |
75 | ? ASSIGN_CONTAINER(NODE, \ | |
76 | (HEAP)->array[(NODE)->MEMBER.idx + 1], \ | |
77 | MEMBER) \ | |
33e191a0 | 78 | : ((NODE) = NULL, (void) 0))) |
95974447 BP |
79 | \f |
80 | /* Returns the index of the node that is the parent of the node with the given | |
81 | * 'idx' within a heap. */ | |
82 | static inline size_t | |
83 | heap_parent__(size_t idx) | |
84 | { | |
85 | return idx / 2; | |
86 | } | |
87 | ||
88 | /* Returns the index of the node that is the left child of the node with the | |
89 | * given 'idx' within a heap. */ | |
90 | static inline size_t | |
91 | heap_left__(size_t idx) | |
92 | { | |
93 | return idx * 2; | |
94 | } | |
95 | ||
96 | /* Returns the index of the node that is the right child of the node with the | |
97 | * given 'idx' within a heap. */ | |
98 | static inline size_t | |
99 | heap_right__(size_t idx) | |
100 | { | |
101 | return idx * 2 + 1; | |
102 | } | |
103 | ||
104 | /* Returns true if 'idx' is the index of a leaf node in 'heap', false | |
105 | * otherwise. */ | |
106 | static inline bool | |
107 | heap_is_leaf__(const struct heap *heap, size_t idx) | |
108 | { | |
109 | return heap_left__(idx) > heap->n; | |
110 | } | |
111 | ||
112 | /* Returns the number of elements in 'heap'. */ | |
113 | static inline size_t | |
114 | heap_count(const struct heap *heap) | |
115 | { | |
116 | return heap->n; | |
117 | } | |
118 | ||
119 | /* Returns true if 'heap' is empty, false if it contains at least one | |
120 | * element. */ | |
121 | static inline bool | |
122 | heap_is_empty(const struct heap *heap) | |
123 | { | |
124 | return heap->n == 0; | |
125 | } | |
126 | ||
127 | /* Returns the largest element in 'heap'. | |
128 | * | |
129 | * The caller must ensure that 'heap' contains at least one element. | |
130 | * | |
131 | * The return value may be wrong (i.e. not the maximum element but some other | |
132 | * element) if a heap_raw_*() function has been called without a later call to | |
133 | * heap_rebuild(). */ | |
134 | static inline struct heap_node * | |
135 | heap_max(const struct heap *heap) | |
136 | { | |
137 | return heap->array[1]; | |
138 | } | |
139 | ||
140 | /* Removes an arbitrary node from 'heap', in O(1), maintaining the heap | |
141 | * invariant. Returns the node removed. | |
142 | * | |
143 | * The caller must ensure that 'heap' contains at least one element. */ | |
144 | static inline struct heap_node * | |
145 | heap_pop(struct heap *heap) | |
146 | { | |
147 | return heap->array[heap->n--]; | |
148 | } | |
149 | ||
150 | /* Changes the priority of 'node' (which must be in 'heap') to 'priority'. | |
151 | * | |
152 | * After this call, heap_max() will no longer necessarily return the maximum | |
153 | * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in | |
154 | * heap level order, until the next call to heap_rebuild(heap). | |
155 | * | |
156 | * This takes time O(1). */ | |
157 | static inline void | |
1a29a798 | 158 | heap_raw_change(struct heap_node *node, uint64_t priority) |
95974447 BP |
159 | { |
160 | node->priority = priority; | |
161 | } | |
162 | ||
163 | #endif /* heap.h */ |