1  /* Barebones heap implementation supporting only insert and pop.
       2  
       3     Copyright (C) 2010-2023 Free Software Foundation, Inc.
       4  
       5     This program is free software: you can redistribute it and/or modify
       6     it under the terms of the GNU General Public License as published by
       7     the Free Software Foundation; either version 3 of the License, or
       8     (at your option) any later version.
       9  
      10     This program is distributed in the hope that it will be useful,
      11     but WITHOUT ANY WARRANTY; without even the implied warranty of
      12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      13     GNU General Public License for more details.
      14  
      15     You should have received a copy of the GNU General Public License
      16     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
      17  
      18  /* Full implementation: GDSL (http://gna.org/projects/gdsl/) by Nicolas
      19     Darnis <ndarnis@free.fr>. */
      20  
      21  #include <config.h>
      22  
      23  #include "heap.h"
      24  #include "stdlib--.h"
      25  #include "xalloc.h"
      26  
      27  static int heap_default_compare (void const *, void const *);
      28  static size_t heapify_down (void **, size_t, size_t,
      29                              int (*) (void const *, void const *));
      30  static void heapify_up (void **, size_t,
      31                          int (*) (void const *, void const *));
      32  
      33  struct heap
      34  {
      35    void **array;     /* array[0] is not used */
      36    size_t capacity;  /* Array size */
      37    size_t count;     /* Used as index to last element. Also is num of items. */
      38    int (*compare) (void const *, void const *);
      39  };
      40  
      41  /* Allocate memory for the heap. */
      42  
      43  struct heap *
      44  heap_alloc (int (*compare) (void const *, void const *), size_t n_reserve)
      45  {
      46    struct heap *heap = xmalloc (sizeof *heap);
      47  
      48    if (n_reserve == 0)
      49      n_reserve = 1;
      50  
      51    heap->array = xnmalloc (n_reserve, sizeof *(heap->array));
      52  
      53    heap->array[0] = nullptr;
      54    heap->capacity = n_reserve;
      55    heap->count = 0;
      56    heap->compare = compare ? compare : heap_default_compare;
      57  
      58    return heap;
      59  }
      60  
      61  
      62  static int
      63  heap_default_compare (void const *a, void const *b)
      64  {
      65    return 0;
      66  }
      67  
      68  
      69  void
      70  heap_free (struct heap *heap)
      71  {
      72    free (heap->array);
      73    free (heap);
      74  }
      75  
      76  /* Insert element into heap. */
      77  
      78  int
      79  heap_insert (struct heap *heap, void *item)
      80  {
      81    if (heap->capacity - 1 <= heap->count)
      82      heap->array = x2nrealloc (heap->array, &heap->capacity,
      83                                sizeof *(heap->array));
      84  
      85    heap->array[++heap->count] = item;
      86    heapify_up (heap->array, heap->count, heap->compare);
      87  
      88    return 0;
      89  }
      90  
      91  /* Pop top element off heap. */
      92  
      93  void *
      94  heap_remove_top (struct heap *heap)
      95  {
      96    void *top;
      97  
      98    if (heap->count == 0)
      99      return nullptr;
     100  
     101    top = heap->array[1];
     102    heap->array[1] = heap->array[heap->count--];
     103    heapify_down (heap->array, heap->count, 1, heap->compare);
     104  
     105    return top;
     106  }
     107  
     108  /* Move element down into appropriate position in heap. */
     109  
     110  static size_t
     111  heapify_down (void **array, size_t count, size_t initial,
     112                int (*compare) (void const *, void const *))
     113  {
     114    void *element = array[initial];
     115  
     116    size_t parent = initial;
     117    while (parent <= count / 2)
     118      {
     119        size_t child = 2 * parent;
     120  
     121        if (child < count && compare (array[child], array[child + 1]) < 0)
     122          child++;
     123  
     124        if (compare (array[child], element) <= 0)
     125          break;
     126  
     127        array[parent] = array[child];
     128        parent = child;
     129      }
     130  
     131    array[parent] = element;
     132    return parent;
     133  }
     134  
     135  /* Move element up into appropriate position in heap. */
     136  
     137  static void
     138  heapify_up (void **array, size_t count,
     139              int (*compare) (void const *, void const *))
     140  {
     141    size_t k = count;
     142    void *new_element = array[k];
     143  
     144    while (k != 1 && compare (array[k / 2], new_element) <= 0)
     145      {
     146        array[k] = array[k / 2];
     147        k /= 2;
     148      }
     149  
     150    array[k] = new_element;
     151  }