#include <freeradius-devel/ident.h>
RCSID("$Id$")
#include <freeradius-devel/libradius.h>
#include <freeradius-devel/heap.h>
struct fr_heap_t {
int size;
int num_elements;
size_t offset;
fr_heap_cmp_t cmp;
void **p;
};
#define HEAP_PARENT(x) ( ( (x) - 1 ) / 2 )
#define HEAP_LEFT(x) ( 2*(x) + 1 )
#define HEAP_RIGHT(x) ( 2*(x) + 2 )
#define HEAP_SWAP(a, b) { void *_tmp = a; a = b; b = _tmp; }
static int fr_heap_bubble(fr_heap_t *hp, int child);
void fr_heap_delete(fr_heap_t *hp)
{
if (!hp) return;
free(hp->p);
free(hp);
}
fr_heap_t *fr_heap_create(fr_heap_cmp_t cmp, size_t offset)
{
fr_heap_t *fh;
if (!cmp) return NULL;
fh = malloc(sizeof(*fh));
if (!fh) return NULL;
memset(fh, 0, sizeof(*fh));
fh->size = 2048;
fh->p = malloc(sizeof(*(fh->p)) * fh->size);
if (!fh->p) {
free(fh);
return NULL;
}
fh->cmp = cmp;
fh->offset = offset;
return fh;
}
#define SET_OFFSET(heap, node) \
if (heap->offset) \
*((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = node
#define RESET_OFFSET(heap, node) \
if (heap->offset) \
*((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = -1
int fr_heap_insert(fr_heap_t *hp, void *data)
{
int child = hp->num_elements;
if (child == hp->size) {
void **p;
p = malloc(2 * hp->size * sizeof(*p));
if (!p) return 0;
memcpy(p, hp->p, sizeof(*p) * hp->size);
free(hp->p);
hp->p = p;
hp->size *= 2;
}
hp->p[child] = data;
hp->num_elements++;
return fr_heap_bubble(hp, child);
}
static int fr_heap_bubble(fr_heap_t *hp, int child)
{
while (child > 0) {
int parent = HEAP_PARENT(child);
if (hp->cmp(hp->p[parent], hp->p[child]) < 0) break;
HEAP_SWAP(hp->p[child], hp->p[parent]);
SET_OFFSET(hp, child);
child = parent;
}
SET_OFFSET(hp, child);
return 1;
}
int fr_heap_extract(fr_heap_t *hp, void *data)
{
int child, parent;
int max;
if (!hp || (hp->num_elements == 0)) return 0;
max = hp->num_elements - 1;
if (!data) {
parent = 0;
} else {
if (!hp->offset) return 0;
parent = *((int *)(((uint8_t *)data) + hp->offset));
if (parent < 0 || parent >= hp->num_elements) return 0;
}
RESET_OFFSET(hp, parent);
child = HEAP_LEFT(parent);
while (child <= max) {
if ((child != max) &&
(hp->cmp(hp->p[child + 1], hp->p[child]) < 0)) {
child = child + 1;
}
hp->p[parent] = hp->p[child];
SET_OFFSET(hp, parent);
parent = child;
child = HEAP_LEFT(child);
}
hp->num_elements--;
if (parent != max) {
hp->p[parent] = hp->p[max];
return fr_heap_bubble(hp, parent);
}
return 1;
}
void *fr_heap_peek(fr_heap_t *hp)
{
if (!hp || (hp->num_elements == 0)) return NULL;
return hp->p[0];
}
int fr_heap_num_elements(fr_heap_t *hp)
{
if (!hp) return 0;
return hp->num_elements;
}
#ifdef TESTING
#include <stdio.h>
#include <stdlib.h>
static int heap_cmp(const void *a, const void *b)
{
return *(int *)a - *(int *) b;
}
int main(int argc, char **arg)
{
fr_heap_t *hp;
int i, array[1024];
hp = fr_heap_create(heap_cmp, 0);
if (!hp) {
fprintf(stderr, "Failed creating heap!\n");
exit(1);
}
for (i = 0; i < 1024; i++) {
array[i] = (i * 257) % 65537;
if (!fr_heap_insert(hp, &array[i])) {
fprintf(stderr, "Failed inserting %d\n", i);
exit(1);
}
}
for (i = 0; i < 1024; i++) {
int *p = fr_heap_peek(hp);
if (!p) {
fprintf(stderr, "Failed peeking %d\n", i);
exit(1);
}
printf("%d\t%d\n", i, *p);
if (!fr_heap_extract(hp, NULL)) {
fprintf(stderr, "Failed extracting %d\n", i);
exit(1);
}
}
fr_heap_delete(hp);
return 0;
}
#endif