diff options
Diffstat (limited to 'src/contrib/ucw/heap.c')
| -rw-r--r-- | src/contrib/ucw/heap.c | 153 |
1 files changed, 153 insertions, 0 deletions
diff --git a/src/contrib/ucw/heap.c b/src/contrib/ucw/heap.c new file mode 100644 index 0000000..7d74aeb --- /dev/null +++ b/src/contrib/ucw/heap.c @@ -0,0 +1,153 @@ +/* + * Binary heap + * + * (c) 2012 Ondrej Filip <feela@network.cz> + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/*** + * Introduction + * ------------ + * + * Binary heap is a simple data structure, which for example supports efficient insertions, deletions + * and access to the minimal inserted item. We define several macros for such operations. + * Note that because of simplicity of heaps, we have decided to define direct macros instead + * of a <<generic:,macro generator>> as for several other data structures in the Libucw. + * + * A heap is represented by a number of elements and by an array of values. Beware that we + * index this array from one, not from zero as do the standard C arrays. + * + * Most macros use these parameters: + * + * - @num - a variable (signed or unsigned integer) with the number of elements + * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused + * + * A valid heap must follow these rules: + * + * - `num >= 0` + * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]` + * + * The first element `heap[1]` is always lower or equal to all other elements. + ***/ + +#include <string.h> +#include <stdlib.h> +#include "contrib/ucw/heap.h" + +static inline void heap_swap(heap_val_t **e1, heap_val_t **e2) +{ + if (e1 == e2) return; /* Stack tmp should be faster than tmpelem. */ + heap_val_t *tmp = *e1; /* Even faster than 2-XOR nowadays. */ + *e1 = *e2; + *e2 = tmp; + int pos = (*e1)->pos; + (*e1)->pos = (*e2)->pos; + (*e2)->pos = pos; +} + +int heap_init(struct heap *h, int (*cmp)(void *, void *), int init_size) +{ + int isize = init_size ? init_size : INITIAL_HEAP_SIZE; + + h->num = 0; + h->max_size = isize; + h->cmp = cmp; + h->data = malloc((isize + 1) * sizeof(heap_val_t*)); /* Temp element unused. */ + + return h->data ? 1 : 0; +} + +void heap_deinit(struct heap *h) +{ + free(h->data); + memset(h, 0, sizeof(*h)); +} + +static inline void _heap_bubble_down(struct heap *h, int e) +{ + int e1; + for (;;) { + e1 = 2 * e; + if (e1 > h->num) break; + if ((h->cmp(*HELEMENT(h, e), *HELEMENT(h, e1)) < 0) && + (e1 == h->num || (h->cmp(*HELEMENT(h, e), *HELEMENT(h, e1 + 1)) < 0))) break; + if ((e1 != h->num) && (h->cmp(*HELEMENT(h, e1 + 1), *HELEMENT(h, e1)) < 0)) e1++; + heap_swap(HELEMENT(h, e), HELEMENT(h, e1)); + e = e1; + } +} + +static inline void _heap_bubble_up(struct heap *h, int e) +{ + int e1; + while (e > 1) { + e1 = e / 2; + if (h->cmp(*HELEMENT(h, e1), *HELEMENT(h, e)) < 0) break; + heap_swap(HELEMENT(h, e), HELEMENT(h, e1)); + e = e1; + } +} + +void heap_replace(struct heap *h, int pos, heap_val_t *e) +{ + *HELEMENT(h, pos) = e; + e->pos = pos; + + if (pos == 1 || h->cmp(*HELEMENT(h, pos / 2), e) < 0) { + _heap_bubble_down(h, pos); + } else { + _heap_bubble_up(h, pos); + } +} + +void heap_delmin(struct heap *h) +{ + if (h->num == 0) return; + if (h->num > 1) { + heap_swap(HHEAD(h), HELEMENT(h, h->num)); + } + (*HELEMENT(h, h->num))->pos = 0; + h->num--; + _heap_bubble_down(h, 1); +} + +int heap_insert(struct heap *h, heap_val_t *e) +{ + if (h->num == h->max_size) { + h->max_size = h->max_size * HEAP_INCREASE_STEP; + h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*)); + if (!h->data) { + return 0; + } + } + + h->num++; + *HELEMENT(h, h->num) = e; + e->pos = h->num; + _heap_bubble_up(h, h->num); + return 1; +} + +int heap_find(struct heap *h, heap_val_t *elm) +{ + return ((struct heap_val *) elm)->pos; +} + +void heap_delete(struct heap *h, int e) +{ + heap_swap(HELEMENT(h, e), HELEMENT(h, h->num)); + (*HELEMENT(h, h->num))->pos = 0; + h->num--; + if (h->cmp(*HELEMENT(h, e), *HELEMENT(h, h->num + 1)) < 0) { + _heap_bubble_up(h, e); + } else { + _heap_bubble_down(h, e); + } + + if ((h->num > INITIAL_HEAP_SIZE) && (h->num < h->max_size / HEAP_DECREASE_THRESHOLD)) { + h->max_size = h->max_size / HEAP_INCREASE_STEP; + h->data = realloc(h->data, (h->max_size + 1) * sizeof(heap_val_t*)); + } +} |