1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 #include <libpspp/heap.h>
24 #include <libpspp/pool.h>
25 #include <libpspp/assertion.h>
32 /* Comparison function and auxiliary data. */
33 heap_compare_func *compare;
37 struct heap_node **nodes; /* Element 0 unused, 1...CNT are the heap. */
38 size_t cnt; /* Number of elements in heap. */
39 size_t cap; /* Max CNT without allocating more memory. */
42 static inline void set_node (struct heap *, size_t idx, struct heap_node *);
43 static inline bool less (const struct heap *, size_t a, size_t b);
44 static bool UNUSED is_heap (const struct heap *);
45 static inline void propagate_down (struct heap *, size_t idx);
46 static inline bool propagate_up (struct heap *, size_t idx);
48 /* Creates and return a new min-heap. COMPARE is used as
49 comparison function and passed AUX as auxiliary data.
51 To obtain a max-heap, negate the return value of the
52 comparison function. */
54 heap_create (heap_compare_func *compare, const void *aux)
56 struct heap *h = xmalloc (sizeof *h);
65 /* Destroys H (callback for pool). */
67 destroy_callback (void *h)
72 /* Creates and return a new min-heap and registers for its
73 destruction with POOL. COMPARE is used as comparison function
74 and passed AUX as auxiliary data.
76 To obtain a max-heap, negate the return value of the
77 comparison function. */
79 heap_create_pool (struct pool *pool,
80 heap_compare_func *compare, const void *aux)
82 struct heap *h = heap_create (compare, aux);
83 pool_register (pool, destroy_callback, h);
87 /* Destroys heap H. */
89 heap_destroy (struct heap *h)
98 /* Returns true if H is empty, false if it contains at least one
101 heap_is_empty (const struct heap *h)
106 /* Returns the number of elements in H. */
108 heap_count (const struct heap *h)
113 /* Heap nodes may be moved around in memory as necessary, e.g. as
114 the result of an realloc operation on a block that contains a
115 heap node. Once this is done, call this function passing the
116 NODE that was moved and its heap H before attempting any other
119 heap_moved (struct heap *h, struct heap_node *node)
121 assert (node->idx <= h->cnt);
122 h->nodes[node->idx] = node;
125 /* Returns the node with the minimum value in H, which must not
128 heap_minimum (const struct heap *h)
130 assert (!heap_is_empty (h));
134 /* Inserts the given NODE into H. */
136 heap_insert (struct heap *h, struct heap_node *node)
138 if (h->cnt >= h->cap)
140 h->cap = 2 * (h->cap + 8);
141 h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes);
145 set_node (h, h->cnt, node);
146 propagate_up (h, h->cnt);
148 expensive_assert (is_heap (h));
151 /* Deletes the given NODE from H. */
153 heap_delete (struct heap *h, struct heap_node *node)
155 assert (node->idx <= h->cnt);
156 assert (h->nodes[node->idx] == node);
158 if (node->idx < h->cnt)
160 set_node (h, node->idx, h->nodes[h->cnt--]);
161 heap_changed (h, h->nodes[node->idx]);
167 /* After client code changes the value represented by a heap
168 node, it must use this function to update the heap structure.
169 It is also safe (but not useful) to call this function if
170 NODE's value has not changed.
172 It is not safe to update more than one node's value in the
173 heap, then to call this function for each node. Instead,
174 update a single node's value, call this function, update
175 another node's value, and so on. Alternatively, remove all
176 the nodes from the heap, update their values, then re-insert
179 heap_changed (struct heap *h, struct heap_node *node)
181 assert (node->idx <= h->cnt);
182 assert (h->nodes[node->idx] == node);
184 if (!propagate_up (h, node->idx))
185 propagate_down (h, node->idx);
187 expensive_assert (is_heap (h));
190 static inline size_t lesser_node (const struct heap *, size_t a, size_t b);
191 static inline void swap_nodes (struct heap *, size_t a, size_t b);
193 /* Sets h->nodes[IDX] and updates NODE's 'idx' field
196 set_node (struct heap *h, size_t idx, struct heap_node *node)
198 h->nodes[idx] = node;
199 h->nodes[idx]->idx = idx;
202 /* Moves the node with the given IDX down the heap as necessary
203 to restore the heap property. */
205 propagate_down (struct heap *h, size_t idx)
210 least = lesser_node (h, idx, 2 * idx);
211 least = lesser_node (h, least, 2 * idx + 1);
215 swap_nodes (h, least, idx);
220 /* Moves the node with the given IDX up the heap as necessary
221 to restore the heap property. Returns true if the node was
222 moved, false otherwise.*/
224 propagate_up (struct heap *h, size_t idx)
227 for (; idx > 1 && less (h, idx, idx / 2); idx /= 2)
229 swap_nodes (h, idx, idx / 2);
235 /* Returns true if, in H, the node with index A has value less
236 than the node with index B. */
238 less (const struct heap *h, size_t a, size_t b)
240 return h->compare (h->nodes[a], h->nodes[b], h->aux) < 0;
243 /* Returns A or B according to which is the index of the node
244 with the lesser value. B is allowed to be out of the range of
245 valid node indexes, in which case A is returned. */
247 lesser_node (const struct heap *h, size_t a, size_t b)
249 assert (a <= h->cnt);
250 return b > h->cnt || less (h, a, b) ? a : b;
253 /* Swaps, in H, the nodes with indexes A and B. */
255 swap_nodes (struct heap *h, size_t a, size_t b)
259 assert (a <= h->cnt);
260 assert (b <= h->cnt);
263 set_node (h, a, h->nodes[b]);
267 /* Returns true if H is a valid heap,
270 is_heap (const struct heap *h)
274 for (i = 2; i <= h->cnt; i++)
275 if (less (h, i, i / 2))
278 for (i = 1; i <= h->cnt; i++)
279 if (h->nodes[i]->idx != i)