All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
heap.c
Go to the documentation of this file.
1 RCSID("$Id: b43bbccc5bba982cc67cbcc9d4a7a8cf5cfc1e53 $")
2 
3 #include <freeradius-devel/libradius.h>
4 #include <freeradius-devel/heap.h>
5 
6 /*
7  * A heap entry is made of a pointer to the object, which
8  * contains the key. The heap itself is an array of pointers.
9  *
10  * Heaps normally support only ordered insert, and extraction
11  * of the minimum element. The heap entry can contain an "int"
12  * field that holds the entries position in the heap. The offset
13  * of the field is held inside of the heap structure.
14  */
15 
16 struct fr_heap_t {
17  size_t size;
18  size_t num_elements;
19  size_t offset;
21  void **p;
22 };
23 
24 /*
25  * First node in a heap is element 0. Children of i are 2i+1 and
26  * 2i+2. These macros wrap the logic, so the code is more
27  * descriptive.
28  */
29 #define HEAP_PARENT(x) ( ( (x) - 1 ) / 2 )
30 #define HEAP_LEFT(x) ( 2*(x) + 1 )
31 /* #define HEAP_RIGHT(x) ( 2*(x) + 2 ) */
32 #define HEAP_SWAP(a, b) { void *_tmp = a; a = b; b = _tmp; }
33 
34 static int fr_heap_bubble(fr_heap_t *hp, size_t child);
35 
37 {
38  if (!hp) return;
39 
40  free(hp->p);
41  free(hp);
42 }
43 
45 {
46  fr_heap_t *fh;
47 
48  if (!cmp) return NULL;
49 
50  fh = malloc(sizeof(*fh));
51  if (!fh) return NULL;
52 
53  memset(fh, 0, sizeof(*fh));
54 
55  fh->size = 2048;
56  fh->p = malloc(sizeof(*(fh->p)) * fh->size);
57  if (!fh->p) {
58  free(fh);
59  return NULL;
60  }
61 
62  fh->cmp = cmp;
63  fh->offset = offset;
64 
65  return fh;
66 }
67 
68 /*
69  * Insert element in heap. Normally, p != NULL, we insert p in a
70  * new position and bubble up. If p == NULL, then the element is
71  * already in place, and key is the position where to start the
72  * bubble-up.
73  *
74  * Returns 1 on failure (cannot allocate new heap entry)
75  *
76  * If offset > 0 the position (index, int) of the element in the
77  * heap is also stored in the element itself at the given offset
78  * in bytes.
79  */
80 #define SET_OFFSET(heap, node) \
81  if (heap->offset) \
82  *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = node
83 
84 /*
85  * RESET_OFFSET is used for sanity checks. It sets offset to an
86  * invalid value.
87  */
88 #define RESET_OFFSET(heap, node) \
89  if (heap->offset) \
90  *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = -1
91 
92 int fr_heap_insert(fr_heap_t *hp, void *data)
93 {
94  size_t child = hp->num_elements;
95 
96  /*
97  * Heap is full. Double it's size.
98  */
99  if (child == hp->size) {
100  void **p;
101 
102  p = malloc(2 * hp->size * sizeof(*p));
103  if (!p) return 0;
104 
105  memcpy(p, hp->p, sizeof(*p) * hp->size);
106  free(hp->p);
107  hp->p = p;
108  hp->size *= 2;
109  }
110 
111  hp->p[child] = data;
112  hp->num_elements++;
113 
114  return fr_heap_bubble(hp, child);
115 }
116 
117 
118 static int fr_heap_bubble(fr_heap_t *hp, size_t child)
119 {
120  /*
121  * Bubble up the element.
122  */
123  while (child > 0) {
124  size_t parent = HEAP_PARENT(child);
125 
126  /*
127  * Parent is smaller than the child. We're done.
128  */
129  if (hp->cmp(hp->p[parent], hp->p[child]) < 0) break;
130 
131  /*
132  * Child is smaller than the parent, repeat.
133  */
134  HEAP_SWAP(hp->p[child], hp->p[parent]);
135  SET_OFFSET(hp, child);
136  child = parent;
137  }
138  SET_OFFSET(hp, child);
139 
140  return 1;
141 }
142 
143 
144 /*
145  * Remove the top element, or object.
146  */
148 {
149  size_t child, parent;
150  size_t max;
151 
152  if (!hp || (hp->num_elements == 0)) return 0;
153 
154  max = hp->num_elements - 1;
155 
156  /*
157  * Extract element. Default is the first one.
158  */
159  if (!data) {
160  parent = 0;
161 
162  } else { /* extract from the middle */
163  if (!hp->offset) return 0;
164 
165  parent = *((int *)(((uint8_t *)data) + hp->offset));
166 
167  /*
168  * Out of bounds.
169  */
170  if (parent >= hp->num_elements) return 0;
171  }
172 
173  RESET_OFFSET(hp, parent);
174  child = HEAP_LEFT(parent);
175  while (child <= max) {
176  /*
177  * Maybe take the right child.
178  */
179  if ((child != max) &&
180  (hp->cmp(hp->p[child + 1], hp->p[child]) < 0)) {
181  child = child + 1;
182  }
183  hp->p[parent] = hp->p[child];
184  SET_OFFSET(hp, parent);
185  parent = child;
186  child = HEAP_LEFT(child);
187  }
188  hp->num_elements--;
189 
190  /*
191  * We didn't end up at the last element in the heap.
192  * This element has to be re-inserted.
193  */
194  if (parent != max) {
195  /*
196  * Fill hole with last entry and bubble up,
197  * reusing the insert code
198  */
199  hp->p[parent] = hp->p[max];
200  return fr_heap_bubble(hp, parent);
201  }
202 
203  return 1;
204 }
205 
206 
208 {
209  if (!hp || (hp->num_elements == 0)) return NULL;
210 
211  /*
212  * If this is NULL, we have a problem.
213  */
214  return hp->p[0];
215 }
216 
218 {
219  if (!hp) return 0;
220 
221  return hp->num_elements;
222 }
223 
224 
225 #ifdef TESTING
226 static bool fr_heap_check(fr_heap_t *hp, void *data)
227 {
228  int i;
229 
230  if (!hp || (hp->num_elements == 0)) return false;
231 
232  for (i = 0; i < hp->num_elements; i++) {
233  if (hp->p[i] == data) {
234  return true;
235  }
236  }
237 
238  return false;
239 }
240 
241 typedef struct heap_thing {
242  int data;
243  int heap; /* for the heap */
244 } heap_thing;
245 
246 
247 /*
248  * cc -g -DTESTING -I .. heap.c -o heap
249  *
250  * ./heap
251  */
252 static int heap_cmp(void const *one, void const *two)
253 {
254  heap_thing const *a;
255  heap_thing const *b;
256 
257  a = (heap_thing const *) one;
258  b = (heap_thing const *) two;
259 
260  return a->data - b->data;
261 
262 }
263 
264 #define ARRAY_SIZE (1024)
265 
266 int main(int argc, char **argv)
267 {
268  fr_heap_t *hp;
269  int i;
270  heap_thing array[ARRAY_SIZE];
271  int skip = 0;
272  int left;
273 
274  if (argc > 1) {
275  skip = atoi(argv[1]);
276  }
277 
278  hp = fr_heap_create(heap_cmp, offsetof(heap_thing, heap));
279  if (!hp) {
280  fprintf(stderr, "Failed creating heap!\n");
281  fr_exit(1);
282  }
283 
284  for (i = 0; i < ARRAY_SIZE; i++) {
285  array[i].data = rand() % 65537;
286  if (!fr_heap_insert(hp, &array[i])) {
287  fprintf(stderr, "Failed inserting %d\n", i);
288  fr_exit(1);
289  }
290 
291  if (!fr_heap_check(hp, &array[i])) {
292  fprintf(stderr, "Inserted but not in heap %d\n", i);
293  fr_exit(1);
294  }
295  }
296 
297 #if 0
298  for (i = 0; i < ARRAY_SIZE; i++) {
299  printf("Array %d has value %d at offset %d\n",
300  i, array[i].data, array[i].heap);
301  }
302 #endif
303 
304  if (skip) {
305  int entry;
306 
307  printf("%d elements to remove\n", ARRAY_SIZE / skip);
308 
309  for (i = 0; i < ARRAY_SIZE / skip; i++) {
310  entry = i * skip;
311 
312  if (!fr_heap_extract(hp, &array[entry])) {
313  fprintf(stderr, "Failed removing %d\n", entry);
314  }
315 
316  if (fr_heap_check(hp, &array[entry])) {
317  fprintf(stderr, "Deleted but still in heap %d\n", entry);
318  fr_exit(1);
319  }
320 
321  if (array[entry].heap != -1) {
322  fprintf(stderr, "heap offset is wrong %d\n", entry);
323  fr_exit(1);
324  }
325  }
326  }
327 
328  left = fr_heap_num_elements(hp);
329  printf("%d elements left in the heap\n", left);
330 
331  for (i = 0; i < left; i++) {
332  heap_thing *t = fr_heap_peek(hp);
333 
334  if (!t) {
335  fprintf(stderr, "Failed peeking %d\n", i);
336  fr_exit(1);
337  }
338 
339  printf("%d\t%d\n", i, t->data);
340 
341  if (!fr_heap_extract(hp, NULL)) {
342  fprintf(stderr, "Failed extracting %d\n", i);
343  fr_exit(1);
344  }
345  }
346 
347  if (fr_heap_num_elements(hp) > 0) {
348  fprintf(stderr, "%d elements left at the end", fr_heap_num_elements(hp));
349  fr_exit(1);
350  }
351 
352  fr_heap_delete(hp);
353 
354  return 0;
355 }
356 #endif
fr_heap_t * fr_heap_create(fr_heap_cmp_t cmp, size_t offset)
Definition: heap.c:44
int fr_heap_extract(fr_heap_t *hp, void *data)
Definition: heap.c:147
void * fr_heap_peek(fr_heap_t *hp)
Definition: heap.c:207
void fr_heap_delete(fr_heap_t *hp)
Definition: heap.c:36
static struct cmp * cmp
Definition: pair.c:45
#define RESET_OFFSET(heap, node)
Definition: heap.c:88
fr_heap_cmp_t cmp
Definition: heap.c:20
#define HEAP_SWAP(a, b)
Definition: heap.c:32
void ** p
Definition: heap.c:21
size_t fr_heap_num_elements(fr_heap_t *hp)
Definition: heap.c:217
int(* fr_heap_cmp_t)(void const *, void const *)
Definition: heap.h:32
size_t size
Definition: heap.c:17
Definition: heap.c:16
static int fr_heap_bubble(fr_heap_t *hp, size_t child)
Definition: heap.c:118
size_t num_elements
Definition: heap.c:18
#define HEAP_LEFT(x)
Definition: heap.c:30
uint8_t data[]
Definition: eap_pwd.h:625
#define SET_OFFSET(heap, node)
Definition: heap.c:80
int fr_heap_insert(fr_heap_t *hp, void *data)
Definition: heap.c:92
size_t offset
Definition: heap.c:19
int main(int argc, char *argv[])
Definition: radattr.c:959
Definition: pair.c:37
#define RCSID(id)
Definition: build.h:135
#define fr_exit(_x)
Definition: libradius.h:508
#define HEAP_PARENT(x)
Definition: heap.c:29