Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2012, 2013 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 : : #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;
27 : : uint64_t priority;
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. */
46 : : void heap_insert(struct heap *, struct heap_node *, uint64_t priority);
47 : : void heap_change(struct heap *, struct heap_node *, uint64_t priority);
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(). */
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);
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 \
71 : : ? INIT_CONTAINER(NODE, (HEAP)->array[1], MEMBER) \
72 : : : ((NODE) = NULL, (void) 0)); \
73 : : (NODE) != NULL; \
74 : : ((NODE)->MEMBER.idx < (HEAP)->n \
75 : : ? ASSIGN_CONTAINER(NODE, \
76 : : (HEAP)->array[(NODE)->MEMBER.idx + 1], \
77 : : MEMBER) \
78 : : : ((NODE) = NULL, (void) 0)))
79 : :
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 : 4109764 : heap_parent__(size_t idx)
84 : : {
85 : 4109764 : 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 : 4393644 : heap_left__(size_t idx)
92 : : {
93 : 4393644 : 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 : 3706803 : heap_right__(size_t idx)
100 : : {
101 : 3706803 : 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 : 686841 : heap_is_leaf__(const struct heap *heap, size_t idx)
108 : : {
109 : 686841 : return heap_left__(idx) > heap->n;
110 : : }
111 : :
112 : : /* Returns the number of elements in 'heap'. */
113 : : static inline size_t
114 : 1067430 : heap_count(const struct heap *heap)
115 : : {
116 : 1067430 : 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 : 1111696 : heap_is_empty(const struct heap *heap)
123 : : {
124 : 1111696 : 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 : 982344 : heap_max(const struct heap *heap)
136 : : {
137 : 982344 : 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 : 10 : heap_pop(struct heap *heap)
146 : : {
147 : 10 : 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
158 : 87709 : heap_raw_change(struct heap_node *node, uint64_t priority)
159 : : {
160 : 87709 : node->priority = priority;
161 : 87709 : }
162 : :
163 : : #endif /* heap.h */
|
