1 RCSID(
"$Id: b43bbccc5bba982cc67cbcc9d4a7a8cf5cfc1e53 $")
3 #include <freeradius-devel/libradius.h>
4 #include <freeradius-devel/heap.h>
29 #define HEAP_PARENT(x) ( ( (x) - 1 ) / 2 )
30 #define HEAP_LEFT(x) ( 2*(x) + 1 )
32 #define HEAP_SWAP(a, b) { void *_tmp = a; a = b; b = _tmp; }
48 if (!cmp)
return NULL;
50 fh = malloc(
sizeof(*fh));
53 memset(fh, 0,
sizeof(*fh));
56 fh->
p = malloc(
sizeof(*(fh->
p)) * fh->
size);
80 #define SET_OFFSET(heap, node) \
82 *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = node
88 #define RESET_OFFSET(heap, node) \
90 *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = -1
99 if (child == hp->
size) {
102 p = malloc(2 * hp->
size *
sizeof(*p));
105 memcpy(p, hp->
p,
sizeof(*p) * hp->
size);
129 if (hp->
cmp(hp->
p[parent], hp->
p[child]) < 0)
break;
149 size_t child, parent;
163 if (!hp->
offset)
return 0;
165 parent = *((
int *)(((uint8_t *)data) + hp->
offset));
175 while (child <= max) {
179 if ((child != max) &&
180 (hp->
cmp(hp->
p[child + 1], hp->
p[child]) < 0)) {
183 hp->
p[parent] = hp->
p[child];
199 hp->
p[parent] = hp->
p[max];
233 if (hp->
p[i] == data) {
241 typedef struct heap_thing {
252 static int heap_cmp(
void const *one,
void const *two)
257 a = (heap_thing
const *) one;
258 b = (heap_thing
const *) two;
260 return a->data - b->data;
264 #define ARRAY_SIZE (1024)
266 int main(
int argc,
char **argv)
270 heap_thing array[ARRAY_SIZE];
275 skip = atoi(argv[1]);
280 fprintf(stderr,
"Failed creating heap!\n");
284 for (i = 0; i < ARRAY_SIZE; i++) {
285 array[i].data = rand() % 65537;
287 fprintf(stderr,
"Failed inserting %d\n", i);
291 if (!fr_heap_check(hp, &array[i])) {
292 fprintf(stderr,
"Inserted but not in heap %d\n", i);
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);
307 printf(
"%d elements to remove\n", ARRAY_SIZE / skip);
309 for (i = 0; i < ARRAY_SIZE / skip; i++) {
313 fprintf(stderr,
"Failed removing %d\n", entry);
316 if (fr_heap_check(hp, &array[entry])) {
317 fprintf(stderr,
"Deleted but still in heap %d\n", entry);
321 if (array[entry].heap != -1) {
322 fprintf(stderr,
"heap offset is wrong %d\n", entry);
329 printf(
"%d elements left in the heap\n", left);
331 for (i = 0; i < left; i++) {
335 fprintf(stderr,
"Failed peeking %d\n", i);
339 printf(
"%d\t%d\n", i, t->data);
342 fprintf(stderr,
"Failed extracting %d\n", i);
fr_heap_t * fr_heap_create(fr_heap_cmp_t cmp, size_t offset)
int fr_heap_extract(fr_heap_t *hp, void *data)
void * fr_heap_peek(fr_heap_t *hp)
void fr_heap_delete(fr_heap_t *hp)
#define RESET_OFFSET(heap, node)
size_t fr_heap_num_elements(fr_heap_t *hp)
int(* fr_heap_cmp_t)(void const *, void const *)
static int fr_heap_bubble(fr_heap_t *hp, size_t child)
#define SET_OFFSET(heap, node)
int fr_heap_insert(fr_heap_t *hp, void *data)
int main(int argc, char *argv[])