/* heap.c - Abstract heap type
* Copyright 2000-2002 srvx Development Team
*
- * This program is free software; you can redistribute it and/or modify
+ * This file is part of srvx.
+ *
+ * srvx is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version. Important limitations are
- * listed in the COPYING file that accompanies this software.
+ * (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
- * along with this program; if not, email srvx-maintainers@srvx.net.
+ * along with srvx; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
*/
#include "common.h"
last_key = heap->data[index*2];
last_data = heap->data[index*2+1];
while (index > 0) {
- parent = (index - 1) >> 1;
- res = heap->comparator(last_key, heap->data[parent*2]);
- if (res > 0) break;
- heap->data[index*2] = heap->data[parent*2];
- heap->data[index*2+1] = heap->data[parent*2+1];
- index = parent;
+ parent = (index - 1) >> 1;
+ res = heap->comparator(last_key, heap->data[parent*2]);
+ if (res > 0) break;
+ heap->data[index*2] = heap->data[parent*2];
+ heap->data[index*2+1] = heap->data[parent*2+1];
+ index = parent;
}
heap->data[index*2] = last_key;
heap->data[index*2+1] = last_data;
heap_insert(heap_t heap, void *key, void *data)
{
if (heap->data_used == heap->data_alloc) {
- heap->data_alloc *= 2;
- heap->data = realloc(heap->data, 2*heap->data_alloc*sizeof(void*));
+ heap->data_alloc *= 2;
+ heap->data = realloc(heap->data, 2*heap->data_alloc*sizeof(void*));
}
heap->data[heap->data_used*2] = key;
heap->data[heap->data_used*2+1] = data;
last_data = heap->data[pos*2+1];
/* start at left child */
while ((child=pos*2+1) < heap->data_used) {
- /* use right child if it exists and is smaller */
- if (child+1 < heap->data_used) {
- res = heap->comparator(heap->data[(child+1)*2], heap->data[child*2]);
- if (res < 0) child = child+1;
- }
- res = heap->comparator(last_key, heap->data[child*2]);
- if (res <= 0) break;
- heap->data[pos*2] = heap->data[child*2];
- heap->data[pos*2+1] = heap->data[child*2+1];
- pos = child;
+ /* use right child if it exists and is smaller */
+ if (child+1 < heap->data_used) {
+ res = heap->comparator(heap->data[(child+1)*2], heap->data[child*2]);
+ if (res < 0) child = child+1;
+ }
+ res = heap->comparator(last_key, heap->data[child*2]);
+ if (res <= 0) break;
+ heap->data[pos*2] = heap->data[child*2];
+ heap->data[pos*2+1] = heap->data[child*2+1];
+ pos = child;
}
heap->data[pos*2] = last_key;
heap->data[pos*2+1] = last_data;
pos = 1;
}
while (pos < heap->data_used) {
- if (pred(heap->data[pos*2], heap->data[pos*2+1], extra)) {
+ if (pred(heap->data[pos*2], heap->data[pos*2+1], extra)) {
heap_remove(heap, pos);
pos = 0;
} else {