1 /*
2 * Binary heap
3 *
4 * (c) 2012 Ondrej Filip <feela@network.cz>
5 *
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
8 */
9
10 /***
11 * Introduction
12 * ------------
13 *
14 * Binary heap is a simple data structure, which for example supports efficient insertions, deletions
15 * and access to the minimal inserted item. We define several macros for such operations.
16 * Note that because of simplicity of heaps, we have decided to define direct macros instead
17 * of a <<generic:,macro generator>> as for several other data structures in the Libucw.
18 *
19 * A heap is represented by a number of elements and by an array of values. Beware that we
20 * index this array from one, not from zero as do the standard C arrays.
21 *
22 * Most macros use these parameters:
23 *
24 * - @num - a variable (signed or unsigned integer) with the number of elements
25 * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
26 *
27 * A valid heap must follow these rules:
28 *
29 * - `num >= 0`
30 * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
31 *
32 * The first element `heap[1]` is always lower or equal to all other elements.
33 ***/
34
35 #include <string.h>
36 #include <stdlib.h>
37 #include "contrib/ucw/heap.h"
38
heap_swap(heap_val_t ** e1,heap_val_t ** e2)39 static inline void heap_swap(heap_val_t **e1, heap_val_t **e2)
40 {
41 if (e1 == e2) return; /* Stack tmp should be faster than tmpelem. */
42 heap_val_t *tmp = *e1; /* Even faster than 2-XOR nowadays. */
43 *e1 = *e2;
44 *e2 = tmp;
45 int pos = (*e1)->pos;
46 (*e1)->pos = (*e2)->pos;
47 (*e2)->pos = pos;
48 }
49
heap_init(struct heap * h,int (* cmp)(void *,void *),int init_size)50 int heap_init(struct heap *h, int (*cmp)(void *, void *), int init_size)
51 {
52 int isize = init_size ? init_size : INITIAL_HEAP_SIZE;
53
54 h->num = 0;
55 h->max_size = isize;
56 h->cmp = cmp;
57 h->data = malloc((isize + 1) * sizeof(heap_val_t*)); /* Temp element unused. */
58
59 return h->data ? 1 : 0;
60 }
61
heap_deinit(struct heap * h)62 void heap_deinit(struct heap *h)
63 {
64 free(h->data);
65 memset(h, 0, sizeof(*h));
66 }
67
_heap_bubble_down(struct heap * h,int e)68 static inline void _heap_bubble_down(struct heap *h, int e)
69 {
70 int e1;
71 for (;;)
72 {
73 e1 = 2*e;
74 if(e1 > h->num) break;
75 if((h->cmp(*HELEMENT(h, e),*HELEMENT(h,e1)) < 0) && (e1 == h->num || (h->cmp(*HELEMENT(h, e),*HELEMENT(h,e1+1)) < 0))) break;
76 if((e1 != h->num) && (h->cmp(*HELEMENT(h, e1+1), *HELEMENT(h,e1)) < 0)) e1++;
77 heap_swap(HELEMENT(h,e),HELEMENT(h,e1));
78 e = e1;
79 }
80 }
81
_heap_bubble_up(struct heap * h,int e)82 static inline void _heap_bubble_up(struct heap *h, int e)
83 {
84 int e1;
85 while (e > 1)
86 {
87 e1 = e/2;
88 if(h->cmp(*HELEMENT(h, e1),*HELEMENT(h,e)) < 0) break;
89 heap_swap(HELEMENT(h,e),HELEMENT(h,e1));
90 e = e1;
91 }
92
93 }
94
heap_increase(struct heap * h,int pos,heap_val_t * e)95 static void heap_increase(struct heap *h, int pos, heap_val_t *e)
96 {
97 *HELEMENT(h, pos) = e;
98 e->pos = pos;
99 _heap_bubble_down(h, pos);
100 }
101
heap_decrease(struct heap * h,int pos,heap_val_t * e)102 static void heap_decrease(struct heap *h, int pos, heap_val_t *e)
103 {
104 *HELEMENT(h, pos) = e;
105 e->pos = pos;
106 _heap_bubble_up(h, pos);
107 }
108
heap_replace(struct heap * h,int pos,heap_val_t * e)109 void heap_replace(struct heap *h, int pos, heap_val_t *e)
110 {
111 if (h->cmp(*HELEMENT(h, pos),e) < 0) {
112 heap_increase(h, pos, e);
113 } else {
114 heap_decrease(h, pos, e);
115 }
116 }
117
heap_delmin(struct heap * h)118 void heap_delmin(struct heap *h)
119 {
120 if(h->num == 0) return;
121 if(h->num > 1)
122 {
123 heap_swap(HHEAD(h),HELEMENT(h,h->num));
124 }
125 (*HELEMENT(h, h->num))->pos = 0;
126 --h->num;
127 _heap_bubble_down(h, 1);
128 }
129
heap_insert(struct heap * h,heap_val_t * e)130 int heap_insert(struct heap *h, heap_val_t *e)
131 {
132 if(h->num == h->max_size)
133 {
134 h->max_size = h->max_size * HEAP_INCREASE_STEP;
135 h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*));
136 if (!h->data) {
137 return 0;
138 }
139 }
140
141 h->num++;
142 *HELEMENT(h,h->num) = e;
143 e->pos = h->num;
144 _heap_bubble_up(h,h->num);
145 return 1;
146 }
147
heap_find(struct heap * h,heap_val_t * elm)148 int heap_find(struct heap *h, heap_val_t *elm)
149 {
150 return ((struct heap_val *) elm)->pos;
151 }
152
heap_delete(struct heap * h,int e)153 void heap_delete(struct heap *h, int e)
154 {
155 heap_swap(HELEMENT(h, e), HELEMENT(h, h->num));
156 (*HELEMENT(h, h->num))->pos = 0;
157 h->num--;
158 if(h->cmp(*HELEMENT(h, e), *HELEMENT(h, h->num + 1)) < 0) _heap_bubble_up(h, e);
159 else _heap_bubble_down(h, e);
160
161 if ((h->num > INITIAL_HEAP_SIZE) && (h->num < h->max_size / HEAP_DECREASE_THRESHOLD))
162 {
163 h->max_size = h->max_size / HEAP_INCREASE_STEP;
164 h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*));
165 }
166 }
167