From 1eb0c69cf759f535b1a926e667ae3f3aed486c9f Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 23 May 2011 16:09:15 -0400 Subject: [PATCH] Add MIT-licensed priority heap, based on CLRS, chap. 6 Signed-off-by: Mathieu Desnoyers --- Makefile.am | 2 +- configure.ac | 1 + include/babeltrace/prio_heap.h | 106 ++++++++++++++++++ lib/Makefile.am | 5 + lib/prio_heap.c | 194 +++++++++++++++++++++++++++++++++ 5 files changed, 307 insertions(+), 1 deletion(-) create mode 100644 include/babeltrace/prio_heap.h create mode 100644 lib/Makefile.am create mode 100644 lib/prio_heap.c diff --git a/Makefile.am b/Makefile.am index 073dfc6d..67485eda 100644 --- a/Makefile.am +++ b/Makefile.am @@ -2,4 +2,4 @@ AM_CFLAGS = $(PACKAGE_CFLAGS) -I$(top_srcdir)/include ACLOCAL_AMFLAGS = -I m4 -SUBDIRS = types formats converter tests +SUBDIRS = types formats converter lib tests diff --git a/configure.ac b/configure.ac index e4ce4e09..b6e8d650 100644 --- a/configure.ac +++ b/configure.ac @@ -58,6 +58,7 @@ AC_CONFIG_FILES([ formats/ctf-text/types/Makefile formats/ctf/metadata/Makefile converter/Makefile + lib/Makefile tests/Makefile ]) AC_OUTPUT diff --git a/include/babeltrace/prio_heap.h b/include/babeltrace/prio_heap.h new file mode 100644 index 00000000..51cdac56 --- /dev/null +++ b/include/babeltrace/prio_heap.h @@ -0,0 +1,106 @@ +#ifndef _BABELTRACE_PRIO_HEAP_H +#define _BABELTRACE_PRIO_HEAP_H + +/* + * prio_heap.h + * + * Static-sized priority heap containing pointers. Based on CLRS, + * chapter 6. + * + * Copyright 2011 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + */ + +#include + +struct ptr_heap { + size_t len, alloc_len; + void **ptrs; + int (*gt)(void *a, void *b); +}; + +/** + * heap_maximum - return the largest element in the heap + * @heap: the heap to be operated on + * + * Returns the largest element in the heap, without performing any modification + * to the heap structure. Returns NULL if the heap is empty. + */ +static inline void *heap_maximum(const struct ptr_heap *heap) +{ + return heap->len ? heap->ptrs[0] : NULL; +} + +/** + * heap_init - initialize the heap + * @heap: the heap to initialize + * @alloc_len: number of elements initially allocated + * @gt: function to compare the elements + * + * Returns -ENOMEM if out of memory. + */ +extern int heap_init(struct ptr_heap *heap, + size_t alloc_len, + int gt(void *a, void *b)); + +/** + * heap_free - free the heap + * @heap: the heap to free + */ +extern void heap_free(struct ptr_heap *heap); + +/** + * heap_insert - insert an element into the heap + * @heap: the heap to be operated on + * @p: the element to add + * + * Insert an element into the heap. + * + * Returns -ENOMEM if out of memory. + */ +extern int heap_insert(struct ptr_heap *heap, void *p); + +/** + * heap_remove - remove the largest element from the heap + * @heap: the heap to be operated on + * + * Returns the largest element in the heap. It removes this element from the + * heap. Returns NULL if the heap is empty. + */ +extern void *heap_remove(struct ptr_heap *heap); + +/** + * heap_cherrypick - remove a given element from the heap + * @heap: the heap to be operated on + * @p: the element + * + * Remove the given element from the heap. Return the element if present, else + * return NULL. This algorithm has a complexity of O(n), which is higher than + * O(log(n)) provided by the rest of this API. + */ +extern void *heap_cherrypick(struct ptr_heap *heap, void *p); + +/** + * heap_replace_max - replace the the largest element from the heap + * @heap: the heap to be operated on + * @p: the pointer to be inserted as topmost element replacement + * + * Returns the largest element in the heap. It removes this element from the + * heap. The heap is rebalanced only once after the insertion. Returns NULL if + * the heap is empty. + * + * This is the equivalent of calling heap_remove() and then heap_insert(), but + * it only rebalances the heap once. It never allocates memory. + */ +extern void *heap_replace_max(struct ptr_heap *heap, void *p); + +#endif /* _BABELTRACE_PRIO_HEAP_H */ diff --git a/lib/Makefile.am b/lib/Makefile.am new file mode 100644 index 00000000..95613054 --- /dev/null +++ b/lib/Makefile.am @@ -0,0 +1,5 @@ +AM_CFLAGS = $(PACKAGE_CFLAGS) -I$(top_srcdir)/include + +lib_LTLIBRARIES = libprio_heap.la + +libprio_heap_la_SOURCES = prio_heap.c diff --git a/lib/prio_heap.c b/lib/prio_heap.c new file mode 100644 index 00000000..0a99a3d6 --- /dev/null +++ b/lib/prio_heap.c @@ -0,0 +1,194 @@ +/* + * prio_heap.c + * + * Static-sized priority heap containing pointers. Based on CLRS, + * chapter 6. + * + * Copyright 2011 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + */ + +#include +#include +#include +#include + +#ifndef max_t +#define max_t(type, a, b) \ + ((type) (a) > (type) (b) ? (type) (a) : (type) (b)) +#endif + +static __attribute__((unused)) +size_t parent(size_t i) +{ + return i >> 1; +} + +static +size_t left(size_t i) +{ + return i << 1; +} + +static +size_t right(size_t i) +{ + return (i << 1) + 1; +} + +static +int heap_grow(struct ptr_heap *heap, size_t new_len) +{ + void **new_ptrs; + + if (heap->alloc_len >= new_len) + return 0; + + heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1); + new_ptrs = calloc(heap->alloc_len, sizeof(void *)); + if (!new_ptrs) + return -ENOMEM; + if (heap->ptrs) + memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *)); + free(heap->ptrs); + heap->ptrs = new_ptrs; + return 0; +} + +static +int heap_set_len(struct ptr_heap *heap, size_t new_len) +{ + int ret; + + ret = heap_grow(heap, new_len); + if (ret) + return ret; + heap->len = new_len; + return 0; +} + +int heap_init(struct ptr_heap *heap, size_t alloc_len, + int gt(void *a, void *b)) +{ + heap->ptrs = NULL; + heap->len = 0; + heap->alloc_len = 0; + heap->gt = gt; + /* + * Minimum size allocated is 1 entry to ensure memory allocation + * never fails within heap_replace_max. + */ + return heap_grow(heap, max_t(size_t, 1, alloc_len)); +} + +void heap_free(struct ptr_heap *heap) +{ + free(heap->ptrs); +} + +static void heapify(struct ptr_heap *heap, size_t i) +{ + void **ptrs = heap->ptrs; + size_t l, r, largest; + + for (;;) { + l = left(i); + r = right(i); + if (l <= heap->len && ptrs[l] > ptrs[i]) + largest = l; + else + largest = i; + if (r <= heap->len && ptrs[r] > ptrs[largest]) + largest = r; + if (largest != i) { + void *tmp; + + tmp = ptrs[i]; + ptrs[i] = ptrs[largest]; + ptrs[largest] = tmp; + i = largest; + continue; + } else { + break; + } + } +} + +void *heap_replace_max(struct ptr_heap *heap, void *p) +{ + void *res; + void **ptrs = heap->ptrs; + + if (!heap->len) { + (void) heap_set_len(heap, 1); + ptrs[0] = p; + return NULL; + } + + /* Replace the current max and heapify */ + res = ptrs[0]; + ptrs[0] = p; + heapify(heap, 0); + return res; +} + +int heap_insert(struct ptr_heap *heap, void *p) +{ + void **ptrs = heap->ptrs; + int ret; + + ret = heap_set_len(heap, heap->len + 1); + if (ret) + return ret; + /* Add the element to the end */ + ptrs[heap->len - 1] = p; + /* rebalance */ + heapify(heap, 0); + return 0; +} + +void *heap_remove(struct ptr_heap *heap) +{ + void **ptrs = heap->ptrs; + + switch (heap->len) { + case 0: + return NULL; + case 1: + (void) heap_set_len(heap, 0); + return ptrs[0]; + } + /* Shrink, replace the current max by previous last entry and heapify */ + heap_set_len(heap, heap->len - 1); + return heap_replace_max(heap, ptrs[heap->len - 1]); +} + +void *heap_cherrypick(struct ptr_heap *heap, void *p) +{ + void **ptrs = heap->ptrs; + size_t pos, len = heap->len; + + for (pos = 0; pos < len; pos++) + if (ptrs[pos] == p) + goto found; + return NULL; +found: + if (heap->len == 1) { + (void) heap_set_len(heap, 0); + return ptrs[0]; + } + /* Replace p with previous last entry and heapify. */ + heap_set_len(heap, heap->len - 1); + ptrs[pos] = ptrs[heap->len - 1]; + heapify(heap, pos); + return p; +} -- 2.34.1