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 *
heap_alloc(int (* compare)(void const *,void const *),size_t n_reserve)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
heap_default_compare(void const * a,void const * b)63 heap_default_compare (void const *a, void const *b)
64 {
65 return 0;
66 }
67
68
69 void
heap_free(struct heap * heap)70 heap_free (struct heap *heap)
71 {
72 free (heap->array);
73 free (heap);
74 }
75
76 /* Insert element into heap. */
77
78 int
heap_insert(struct heap * heap,void * item)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 *
heap_remove_top(struct heap * heap)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
heapify_down(void ** array,size_t count,size_t initial,int (* compare)(void const *,void const *))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
heapify_up(void ** array,size_t count,int (* compare)(void const *,void const *))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 }
152