src/libpspp/heap.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   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.
   8
   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.
  13
  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
  17    02110-1301, USA. */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include <config.h>
  21 #endif
  22
  23 #include <libpspp/heap.h>
  24 #include <libpspp/pool.h>
  25 #include <libpspp/assertion.h>
  26
  27 #include "xalloc.h"
  28
  29 /* A heap. */
  30 struct heap
  31   {
  32     /* Comparison function and auxiliary data. */
  33     heap_compare_func *compare;
  34     const void *aux;
  35
  36     /* Contents. */
  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. */
  40   };
  41
  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);
  47
  48 /* Creates and return a new min-heap.  COMPARE is used as
  49    comparison function and passed AUX as auxiliary data.
  50
  51    To obtain a max-heap, negate the return value of the
  52    comparison function. */
  53 struct heap *
  54 heap_create (heap_compare_func *compare, const void *aux)
  55 {
  56   struct heap *h = xmalloc (sizeof *h);
  57   h->compare = compare;
  58   h->aux = aux;
  59   h->nodes = NULL;
  60   h->cap = 0;
  61   h->cnt = 0;
  62   return h;
  63 }
  64
  65 /* Destroys H (callback for pool). */
  66 static void
  67 destroy_callback (void *h)
  68 {
  69   heap_destroy (h);
  70 }
  71
  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.
  75
  76    To obtain a max-heap, negate the return value of the
  77    comparison function. */
  78 struct heap *
  79 heap_create_pool (struct pool *pool,
  80                   heap_compare_func *compare, const void *aux)
  81 {
  82   struct heap *h = heap_create (compare, aux);
  83   pool_register (pool, destroy_callback, h);
  84   return h;
  85 }
  86
  87 /* Destroys heap H. */
  88 void
  89 heap_destroy (struct heap *h)
  90 {
  91   if (h != NULL)
  92     {
  93       free (h->nodes);
  94       free (h);
  95     }
  96 }
  97
  98 /* Returns true if H is empty, false if it contains at least one
  99    element. */
 100 bool
 101 heap_is_empty (const struct heap *h)
 102 {
 103   return h->cnt == 0;
 104 }
 105
 106 /* Returns the number of elements in H. */
 107 size_t
 108 heap_count (const struct heap *h)
 109 {
 110   return h->cnt;
 111 }
 112
 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
 117    operation on H. */
 118 void
 119 heap_moved (struct heap *h, struct heap_node *node)
 120 {
 121   assert (node->idx <= h->cnt);
 122   h->nodes[node->idx] = node;
 123 }
 124
 125 /* Returns the node with the minimum value in H, which must not
 126    be empty. */
 127 struct heap_node *
 128 heap_minimum (const struct heap *h)
 129 {
 130   assert (!heap_is_empty (h));
 131   return h->nodes[1];
 132 }
 133
 134 /* Inserts the given NODE into H. */
 135 void
 136 heap_insert (struct heap *h, struct heap_node *node)
 137 {
 138   if (h->cnt >= h->cap)
 139     {
 140       h->cap = 2 * (h->cap + 8);
 141       h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes);
 142     }
 143
 144   h->cnt++;
 145   set_node (h, h->cnt, node);
 146   propagate_up (h, h->cnt);
 147
 148   expensive_assert (is_heap (h));
 149 }
 150
 151 /* Deletes the given NODE from H. */
 152 void
 153 heap_delete (struct heap *h, struct heap_node *node)
 154 {
 155   assert (node->idx <= h->cnt);
 156   assert (h->nodes[node->idx] == node);
 157
 158   if (node->idx < h->cnt)
 159     {
 160       set_node (h, node->idx, h->nodes[h->cnt--]);
 161       heap_changed (h, h->nodes[node->idx]);
 162     }
 163   else
 164     h->cnt--;
 165 }
 166
 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.
 171
 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
 177    all of them. */
 178 void
 179 heap_changed (struct heap *h, struct heap_node *node)
 180 {
 181   assert (node->idx <= h->cnt);
 182   assert (h->nodes[node->idx] == node);
 183
 184   if (!propagate_up (h, node->idx))
 185     propagate_down (h, node->idx);
 186
 187   expensive_assert (is_heap (h));
 188 }
 189 \f
 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);
 192
 193 /* Sets h->nodes[IDX] and updates NODE's 'idx' field
 194    accordingly. */
 195 static void
 196 set_node (struct heap *h, size_t idx, struct heap_node *node)
 197 {
 198   h->nodes[idx] = node;
 199   h->nodes[idx]->idx = idx;
 200 }
 201
 202 /* Moves the node with the given IDX down the heap as necessary
 203    to restore the heap property. */
 204 static void
 205 propagate_down (struct heap *h, size_t idx)
 206 {
 207   for (;;)
 208     {
 209       size_t least;
 210       least = lesser_node (h, idx, 2 * idx);
 211       least = lesser_node (h, least, 2 * idx + 1);
 212       if (least == idx)
 213         break;
 214
 215       swap_nodes (h, least, idx);
 216       idx = least;
 217     }
 218 }
 219
 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.*/
 223 static bool
 224 propagate_up (struct heap *h, size_t idx)
 225 {
 226   bool moved = false;
 227   for (; idx > 1 && less (h, idx, idx / 2); idx /= 2)
 228     {
 229       swap_nodes (h, idx, idx / 2);
 230       moved = true;
 231     }
 232   return moved;
 233 }
 234
 235 /* Returns true if, in H, the node with index A has value less
 236    than the node with index B.  */
 237 static bool
 238 less (const struct heap *h, size_t a, size_t b)
 239 {
 240   return h->compare (h->nodes[a], h->nodes[b], h->aux) < 0;
 241 }
 242
 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. */
 246 static size_t
 247 lesser_node (const struct heap *h, size_t a, size_t b)
 248 {
 249   assert (a <= h->cnt);
 250   return b > h->cnt || less (h, a, b) ? a : b;
 251 }
 252
 253 /* Swaps, in H, the nodes with indexes A and B. */
 254 static void
 255 swap_nodes (struct heap *h, size_t a, size_t b)
 256 {
 257   struct heap_node *t;
 258
 259   assert (a <= h->cnt);
 260   assert (b <= h->cnt);
 261
 262   t = h->nodes[a];
 263   set_node (h, a, h->nodes[b]);
 264   set_node (h, b, t);
 265 }
 266
 267 /* Returns true if H is a valid heap,
 268    false otherwise. */
 269 static bool UNUSED
 270 is_heap (const struct heap *h)
 271 {
 272   size_t i;
 273
 274   for (i = 2; i <= h->cnt; i++)
 275     if (less (h, i, i / 2))
 276       return false;
 277
 278   for (i = 1; i <= h->cnt; i++)
 279     if (h->nodes[i]->idx != i)
 280       return false;
 281
 282   return true;
 283 }