src/libpspp/heap.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2011 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #ifdef HAVE_CONFIG_H
  18 #include <config.h>
  19 #endif
  20
  21 #include "libpspp/heap.h"
  22 #include "libpspp/pool.h"
  23 #include "libpspp/assertion.h"
  24
  25 #include "gl/xalloc.h"
  26
  27 /* A heap. */
  28 struct heap
  29   {
  30     /* Comparison function and auxiliary data. */
  31     heap_compare_func *compare;
  32     const void *aux;
  33
  34     /* Contents. */
  35     struct heap_node **nodes;   /* Element 0 unused, 1...CNT are the heap. */
  36     size_t cnt;                 /* Number of elements in heap. */
  37     size_t cap;                 /* Max CNT without allocating more memory. */
  38   };
  39
  40 static inline void set_node (struct heap *, size_t idx, struct heap_node *);
  41 static inline bool less (const struct heap *, size_t a, size_t b);
  42 static bool UNUSED is_heap (const struct heap *);
  43 static inline void propagate_down (struct heap *, size_t idx);
  44 static inline bool propagate_up (struct heap *, size_t idx);
  45
  46 /* Creates and return a new min-heap.  COMPARE is used as
  47    comparison function and passed AUX as auxiliary data.
  48
  49    To obtain a max-heap, negate the return value of the
  50    comparison function. */
  51 struct heap *
  52 heap_create (heap_compare_func *compare, const void *aux)
  53 {
  54   struct heap *h = xmalloc (sizeof *h);
  55   h->compare = compare;
  56   h->aux = aux;
  57   h->nodes = NULL;
  58   h->cap = 0;
  59   h->cnt = 0;
  60   return h;
  61 }
  62
  63 /* Destroys H (callback for pool). */
  64 static void
  65 destroy_callback (void *h)
  66 {
  67   heap_destroy (h);
  68 }
  69
  70 /* Creates and return a new min-heap and registers for its
  71    destruction with POOL.  COMPARE is used as comparison function
  72    and passed AUX as auxiliary data.
  73
  74    To obtain a max-heap, negate the return value of the
  75    comparison function. */
  76 struct heap *
  77 heap_create_pool (struct pool *pool,
  78                   heap_compare_func *compare, const void *aux)
  79 {
  80   struct heap *h = heap_create (compare, aux);
  81   pool_register (pool, destroy_callback, h);
  82   return h;
  83 }
  84
  85 /* Destroys heap H. */
  86 void
  87 heap_destroy (struct heap *h)
  88 {
  89   if (h != NULL)
  90     {
  91       free (h->nodes);
  92       free (h);
  93     }
  94 }
  95
  96 /* Returns true if H is empty, false if it contains at least one
  97    element. */
  98 bool
  99 heap_is_empty (const struct heap *h)
 100 {
 101   return h->cnt == 0;
 102 }
 103
 104 /* Returns the number of elements in H. */
 105 size_t
 106 heap_count (const struct heap *h)
 107 {
 108   return h->cnt;
 109 }
 110
 111 /* Heap nodes may be moved around in memory as necessary, e.g. as
 112    the result of an realloc operation on a block that contains a
 113    heap node.  Once this is done, call this function passing the
 114    NODE that was moved and its heap H before attempting any other
 115    operation on H. */
 116 void
 117 heap_moved (struct heap *h, struct heap_node *node)
 118 {
 119   assert (node->idx <= h->cnt);
 120   h->nodes[node->idx] = node;
 121 }
 122
 123 /* Returns the node with the minimum value in H, which must not
 124    be empty. */
 125 struct heap_node *
 126 heap_minimum (const struct heap *h)
 127 {
 128   assert (!heap_is_empty (h));
 129   return h->nodes[1];
 130 }
 131
 132 /* Inserts the given NODE into H. */
 133 void
 134 heap_insert (struct heap *h, struct heap_node *node)
 135 {
 136   if (h->cnt >= h->cap)
 137     {
 138       h->cap = 2 * (h->cap + 8);
 139       h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes);
 140     }
 141
 142   h->cnt++;
 143   set_node (h, h->cnt, node);
 144   propagate_up (h, h->cnt);
 145
 146   expensive_assert (is_heap (h));
 147 }
 148
 149 /* Deletes the given NODE from H. */
 150 void
 151 heap_delete (struct heap *h, struct heap_node *node)
 152 {
 153   assert (node->idx <= h->cnt);
 154   assert (h->nodes[node->idx] == node);
 155
 156   if (node->idx < h->cnt)
 157     {
 158       set_node (h, node->idx, h->nodes[h->cnt--]);
 159       heap_changed (h, h->nodes[node->idx]);
 160     }
 161   else
 162     h->cnt--;
 163 }
 164
 165 /* After client code changes the value represented by a heap
 166    node, it must use this function to update the heap structure.
 167    It is also safe (but not useful) to call this function if
 168    NODE's value has not changed.
 169
 170    It is not safe to update more than one node's value in the
 171    heap, then to call this function for each node.  Instead,
 172    update a single node's value, call this function, update
 173    another node's value, and so on.  Alternatively, remove all
 174    the nodes from the heap, update their values, then re-insert
 175    all of them. */
 176 void
 177 heap_changed (struct heap *h, struct heap_node *node)
 178 {
 179   assert (node->idx <= h->cnt);
 180   assert (h->nodes[node->idx] == node);
 181
 182   if (!propagate_up (h, node->idx))
 183     propagate_down (h, node->idx);
 184
 185   expensive_assert (is_heap (h));
 186 }
 187 \f
 188 static inline size_t lesser_node (const struct heap *, size_t a, size_t b);
 189 static inline void swap_nodes (struct heap *, size_t a, size_t b);
 190
 191 /* Sets h->nodes[IDX] and updates NODE's 'idx' field
 192    accordingly. */
 193 static void
 194 set_node (struct heap *h, size_t idx, struct heap_node *node)
 195 {
 196   h->nodes[idx] = node;
 197   h->nodes[idx]->idx = idx;
 198 }
 199
 200 /* Moves the node with the given IDX down the heap as necessary
 201    to restore the heap property. */
 202 static void
 203 propagate_down (struct heap *h, size_t idx)
 204 {
 205   for (;;)
 206     {
 207       size_t least;
 208       least = lesser_node (h, idx, 2 * idx);
 209       least = lesser_node (h, least, 2 * idx + 1);
 210       if (least == idx)
 211         break;
 212
 213       swap_nodes (h, least, idx);
 214       idx = least;
 215     }
 216 }
 217
 218 /* Moves the node with the given IDX up the heap as necessary
 219    to restore the heap property.  Returns true if the node was
 220    moved, false otherwise.*/
 221 static bool
 222 propagate_up (struct heap *h, size_t idx)
 223 {
 224   bool moved = false;
 225   for (; idx > 1 && less (h, idx, idx / 2); idx /= 2)
 226     {
 227       swap_nodes (h, idx, idx / 2);
 228       moved = true;
 229     }
 230   return moved;
 231 }
 232
 233 /* Returns true if, in H, the node with index A has value less
 234    than the node with index B.  */
 235 static bool
 236 less (const struct heap *h, size_t a, size_t b)
 237 {
 238   return h->compare (h->nodes[a], h->nodes[b], h->aux) < 0;
 239 }
 240
 241 /* Returns A or B according to which is the index of the node
 242    with the lesser value.  B is allowed to be out of the range of
 243    valid node indexes, in which case A is returned. */
 244 static size_t
 245 lesser_node (const struct heap *h, size_t a, size_t b)
 246 {
 247   assert (a <= h->cnt);
 248   return b > h->cnt || less (h, a, b) ? a : b;
 249 }
 250
 251 /* Swaps, in H, the nodes with indexes A and B. */
 252 static void
 253 swap_nodes (struct heap *h, size_t a, size_t b)
 254 {
 255   struct heap_node *t;
 256
 257   assert (a <= h->cnt);
 258   assert (b <= h->cnt);
 259
 260   t = h->nodes[a];
 261   set_node (h, a, h->nodes[b]);
 262   set_node (h, b, t);
 263 }
 264
 265 /* Returns true if H is a valid heap,
 266    false otherwise. */
 267 static bool UNUSED
 268 is_heap (const struct heap *h)
 269 {
 270   size_t i;
 271
 272   for (i = 2; i <= h->cnt; i++)
 273     if (less (h, i, i / 2))
 274       return false;
 275
 276   for (i = 1; i <= h->cnt; i++)
 277     if (h->nodes[i]->idx != i)
 278       return false;
 279
 280   return true;
 281 }