]>
git.proxmox.com Git - ovs.git/blob - lib/heap.h
2 * Copyright (c) 2012, 2013 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
24 /* A heap node, to be embedded inside the data structure in the 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. */
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
*);
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
*);
52 static inline struct heap_node
*heap_max(const struct heap
*);
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
*);
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.
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
69 #define HEAP_FOR_EACH(NODE, MEMBER, HEAP) \
71 ? INIT_CONTAINER(NODE, (HEAP)->array[1], MEMBER) \
72 : ((NODE) = NULL, (void) 0)); \
74 ((NODE)->MEMBER.idx < (HEAP)->n \
75 ? ASSIGN_CONTAINER(NODE, \
76 (HEAP)->array[(NODE)->MEMBER.idx + 1], \
78 : ((NODE) = NULL, (void) 0)))
80 /* Returns the index of the node that is the parent of the node with the given
81 * 'idx' within a heap. */
83 heap_parent__(size_t idx
)
88 /* Returns the index of the node that is the left child of the node with the
89 * given 'idx' within a heap. */
91 heap_left__(size_t idx
)
96 /* Returns the index of the node that is the right child of the node with the
97 * given 'idx' within a heap. */
99 heap_right__(size_t idx
)
104 /* Returns true if 'idx' is the index of a leaf node in 'heap', false
107 heap_is_leaf__(const struct heap
*heap
, size_t idx
)
109 return heap_left__(idx
) > heap
->n
;
112 /* Returns the number of elements in 'heap'. */
114 heap_count(const struct heap
*heap
)
119 /* Returns true if 'heap' is empty, false if it contains at least one
122 heap_is_empty(const struct heap
*heap
)
127 /* Returns the largest element in 'heap'.
129 * The caller must ensure that 'heap' contains at least one element.
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
134 static inline struct heap_node
*
135 heap_max(const struct heap
*heap
)
137 return heap
->array
[1];
140 /* Removes an arbitrary node from 'heap', in O(1), maintaining the heap
141 * invariant. Returns the node removed.
143 * The caller must ensure that 'heap' contains at least one element. */
144 static inline struct heap_node
*
145 heap_pop(struct heap
*heap
)
147 return heap
->array
[heap
->n
--];
150 /* Changes the priority of 'node' (which must be in 'heap') to 'priority'.
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).
156 * This takes time O(1). */
158 heap_raw_change(struct heap_node
*node
, uint64_t priority
)
160 node
->priority
= priority
;