52 #define MIN_CAPACITY 16 73 char tmp[heap->
el_sz];
85 void **pp = (
void**) heap->
data;
99 if (el_sz ==
sizeof(
void*))
120 if (heap->
alloc >= capacity)
123 int newcap = heap->
alloc;
125 while (newcap < capacity) {
134 heap->
values = realloc(heap->
values, newcap *
sizeof(
float));
136 heap->
alloc = newcap;
142 assert (isfinite(v) &&
"zmaxheap_add: Trying to add non-finite number to heap. NaN's prohibited, could allow INF with testing");
145 int idx = heap->
size;
154 int parent = (idx - 1) / 2;
157 if (heap->
values[parent] >= v)
161 heap->
swap(heap, idx, parent);
168 assert(heap != NULL);
170 assert(heap->
el_sz ==
sizeof(
void*));
172 for (
int idx = 0; idx < heap->
size; idx++) {
176 printf(
"Warning: zmaxheap_vmap item %d is NULL\n", idx);
188 if (idx >= heap->
size)
201 if (idx == heap->
size)
213 float parent_score = heap->
values[idx];
216 while (parent < heap->
size) {
218 int left = 2*parent + 1;
219 int right = left + 1;
223 float left_score = (left < heap->
size) ? heap->
values[left] : -INFINITY;
224 float right_score = (right < heap->size) ? heap->
values[right] : -INFINITY;
229 if (parent_score >= left_score && parent_score >= right_score)
233 if (left_score >= right_score) {
234 assert(left < heap->size);
235 heap->
swap(heap, parent, left);
239 assert(right < heap->size);
240 heap->
swap(heap, parent, right);
271 if (it->
in != it->
out) {
291 if (it->
in != it->
out) {
308 int left = 2*parent + 1;
309 int right = 2*parent + 2;
311 int betterchild = parent;
318 if (betterchild != parent) {
319 heap->
swap(heap, parent, betterchild);
324 #if 0 //won't compile if defined but not used 328 for (
int parent = 0; parent < heap->
size; parent++) {
329 int left = 2*parent + 1;
330 int right = 2*parent + 2;
332 if (left < heap->
size) {
336 if (right < heap->size) {
345 if (it->
in == it->
out)
353 for (
int i = heap->
size/2 - 1; i >= 0; i--)
361 int32_t *vals = calloc(
sizeof(int32_t), cap);
368 for (
int iter = 0; iter < 5000000; iter++) {
369 assert(sz == heap->
size);
371 if ((random() & 1) == 0 && sz < cap) {
373 int32_t v = (int32_t) (random() / 1000);
384 int maxv = -1, maxi = -1;
386 for (
int i = 0; i < sz; i++) {
387 if (vals[i] > maxv) {
401 assert(outv == outfv);
402 assert(maxv == outv);
405 vals[maxi] = vals[sz - 1];
413 if (maxsz > 0 && sz == 0)
417 printf(
"max size: %d, zcount %d\n", maxsz, zcnt);
void zmaxheap_iterator_init(zmaxheap_t *heap, zmaxheap_iterator_t *it)
void zmaxheap_iterator_remove(zmaxheap_iterator_t *it)
void zmaxheap_destroy(zmaxheap_t *heap)
void zmaxheap_vmap(zmaxheap_t *heap, void(*f)())
int zmaxheap_remove_index(zmaxheap_t *heap, int idx, void *p, float *v)
void(* swap)(zmaxheap_t *heap, int a, int b)
static void swap_default(zmaxheap_t *heap, int a, int b)
int zmaxheap_size(zmaxheap_t *heap)
zmaxheap_t * zmaxheap_create(size_t el_sz)
static void swap_pointer(zmaxheap_t *heap, int a, int b)
void zmaxheap_iterator_finish(zmaxheap_iterator_t *it)
int zmaxheap_iterator_next(zmaxheap_iterator_t *it, void *p, float *v)
static void maxheapify(zmaxheap_t *heap, int parent)
void zmaxheap_add(zmaxheap_t *heap, void *p, float v)
int zmaxheap_iterator_next_volatile(zmaxheap_iterator_t *it, void *p, float *v)
void zmaxheap_ensure_capacity(zmaxheap_t *heap, int capacity)
int zmaxheap_remove_max(zmaxheap_t *heap, void *p, float *v)