timeval: On Linux x86-64 systems refresh time whenever it is requested.
[sliver-openvswitch.git] / lib / heap.h
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 #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     uint32_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 *, uint32_t priority);
47 void heap_change(struct heap *, struct heap_node *, uint32_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 *, uint32_t priority);
58 static inline void heap_raw_change(struct heap_node *, uint32_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           ? ASSIGN_CONTAINER(NODE, (HEAP)->array[1], MEMBER)        \
72           : ((NODE) = NULL, 1));                                    \
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, 1)))
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
158 heap_raw_change(struct heap_node *node, uint32_t priority)
159 {
160     node->priority = priority;
161 }
162
163 #endif /* heap.h */