From 033fd4e36c4cceab309b15253194999ab8dddfa2 Mon Sep 17 00:00:00 2001 From: Richard Kettlewell Date: Fri, 21 Sep 2007 23:38:11 +0100 Subject: [PATCH] binary heap macro and a simple test case --- lib/Makefile.am | 6 ++- lib/heap.h | 146 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/test.c | 47 ++++++++++++++++-- 3 files changed, 195 insertions(+), 4 deletions(-) create mode 100644 lib/heap.h diff --git a/lib/Makefile.am b/lib/Makefile.am index 212b1ce..23590e7 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -85,7 +85,11 @@ test_SOURCES=test.c test_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) test_DEPENDENCIES=libdisorder.a -check: test +check: test #test.i ./test +%.i: %.c + $(CPP) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) -c $< > $@.new + mv $@.new $@ + CLEANFILES=definitions.h diff --git a/lib/heap.h b/lib/heap.h new file mode 100644 index 0000000..4603942 --- /dev/null +++ b/lib/heap.h @@ -0,0 +1,146 @@ +/* + * This file is part of DisOrder. + * Copyright (C) 2007 Richard Kettlewell + * + * This program 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. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ +/** @file lib/heap.h @brief Binary heap template */ + +#ifndef HEAP_H +#define HEAP_H + +/** @brief Binary heap template. + * @param NAME name of type to define + * @param ETYPE element type + * @param LT comparison function + * + * Defines a heap type called @c struct @p NAME and a number of functions to + * operate on it. + * + * The element type of the heap will be @p ETYPE. + * + * @p LT will be called with two arguments of type @p ETYPE, and + * implements a less-than comparison. + * + * The functions defined are: + * - NAME_init(h) which initializes an empty heap at @p h + * - NAME_count(h) which returns the number of elements in the heap + * - NAME_insert(h, e) which inserts @p e into @p h + * - NAME_first(g) which returns the least element of @p h + * - NAME_remove(g) which removes and returns the least element of @p h + * + * The heap is implemented as a vector. Element 0 is the root. For any + * element \f$i\f$, its children are elements \f$2i+1\f$ and \f$2i+2\f$ and + * consequently its parent (if it is not the root) is + * \f$\lfloor(i-1)/2\rfloor\f$. + * + * The insert and remove operations maintain two invariants: the @b + * shape property (all levels of the tree are fully filled except the + * deepest, and that is filled from the left), and the @b heap + * property, that every element compares less than or equal to its + * children. + * + * The shape property implies that the array representation has no gaps, which + * is convenient. It is preserved by only adding or removing the final element + * of the array and otherwise only modifying the array by swapping pairs of + * elements. + * + * @b Insertion works by inserting the new element \f$N\f$ at the end and + * bubbling it up the tree until it is in the right order for its branch. + * - If, for its parent \f$P\f$, \f$P \le N\f$ then it is already in the right + * place and the insertion is complete. + * - Otherwise \f$P > N\f$ and so \f$P\f$ and \f$N\f$ are exchanged. If + * \f$P\f$ has a second child, \f$C\f$, then \f$N < P < C\f$ so the heap + * property is now satisfied from \f$P\f$ down. + * + * @b Removal works by first swapping the root with the final element (and then + * removing it) and then bubbling the new root \f$N\f$ down the tree until it + * finds its proper place. At each stage it is compared with its children + * \f$A\f$ and \f$B\f$. + * - If \f$N \le A\f$ and \f$N \le B\f$ then it is in the + * right place already. + * - Otherwise \f$N > A\f$ or \f$N > B\f$ (or both). WLOG \f$A \le B\f$. + * \f$N\f$ and \f$A\f$ are exchanged, so now \f$A\f$ has children \f$N\f$ and + * \f$B\f$. \f$A < N\f$ and \f$A \le B\f$. + */ +#define HEAP_TYPE(NAME, ETYPE, LT) \ + typedef ETYPE NAME##_element; \ + VECTOR_TYPE(NAME, NAME##_element, xrealloc) \ + \ + static inline int NAME##_count(struct NAME *heap) { \ + return heap->nvec; \ + } \ + \ + static inline NAME##_element NAME##_first(struct NAME *heap) { \ + assert(heap->nvec > 0); \ + return heap->vec[0]; \ + } \ + \ + static void NAME##_insert(struct NAME *heap, NAME##_element elt) { \ + int n = heap->nvec; \ + NAME##_append(heap, elt); \ + while(n > 0) { \ + const int p = (n-1)/2; \ + if(!LT(heap->vec[n],heap->vec[p])) \ + break; \ + else { \ + const NAME##_element t = heap->vec[n]; \ + heap->vec[n] = heap->vec[p]; \ + heap->vec[p] = t; \ + n = p; \ + } \ + } \ + } \ + \ + static NAME##_element NAME##_remove(struct NAME *heap) { \ + int n = 0; \ + NAME##_element r; \ + \ + assert(heap->nvec > 0); \ + r = heap->vec[0]; \ + heap->vec[0] = heap->vec[--heap->nvec]; \ + while(2 * n + 1 < heap->nvec) { \ + int a = 2 * n + 1; \ + int b = 2 * n + 2; \ + \ + if(b < heap->nvec && LT(heap->vec[b],heap->vec[a])) { \ + ++a; \ + --b; \ + } \ + if(LT(heap->vec[a], heap->vec[n])) { \ + const NAME##_element t = heap->vec[n]; \ + heap->vec[n] = heap->vec[a]; \ + heap->vec[a] = t; \ + n = a; \ + } else \ + break; \ + } \ + return r; \ + } \ + \ + struct heap_swallow_semicolon + + +#endif /* PQUEUE_H */ + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/test.c b/lib/test.c index 23d6366..ed765e7 100644 --- a/lib/test.c +++ b/lib/test.c @@ -1,6 +1,6 @@ /* * This file is part of DisOrder. - * Copyright (C) 2005 Richard Kettlewell + * Copyright (C) 2005, 2007 Richard Kettlewell * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -17,6 +17,7 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 * USA */ +/** @file lib/test.c @brief Library tests */ #include #include "types.h" @@ -26,6 +27,7 @@ #include #include #include +#include #include "utf8.h" #include "mem.h" @@ -35,11 +37,13 @@ #include "mime.h" #include "hex.h" #include "words.h" +#include "heap.h" static int tests, errors; +/** @brief Checks that @p expr is nonzero */ #define insist(expr) do { \ - if(!expr) { \ + if(!(expr)) { \ ++errors; \ fprintf(stderr, "%s:%d: error checking %s\n", \ __FILE__, __LINE__, #expr); \ @@ -113,6 +117,8 @@ static void test_utf8(void) { insist(!strcmp(u8, CHARS)); \ } while(0) + fprintf(stderr, "test_utf8\n"); + /* empty string */ U8("", ""); @@ -210,6 +216,8 @@ static void test_utf8(void) { static void test_mime(void) { char *t, *n, *v; + fprintf(stderr, "test_mime\n"); + t = n = v = 0; insist(!mime_content_type("text/plain", &t, &n, &v)); insist(!strcmp(t, "text/plain")); @@ -279,6 +287,8 @@ static void test_hex(void) { uint8_t *u; size_t ul; + fprintf(stderr, "test_hex\n"); + for(n = 0; n <= UCHAR_MAX; ++n) { if(!isxdigit(n)) insist(unhexdigitq(n) == -1); @@ -315,15 +325,18 @@ static void test_hex(void) { insist(memcmp(u, h, 4) == 0); u = unhex("", &ul); insist(ul == 0); - fprintf(stderr, "2 ERROR reports expected:\n"); + fprintf(stderr, "2 ERROR reports expected {\n"); insist(unhex("F", 0) == 0); insist(unhex("az", 0) == 0); + fprintf(stderr, "}\n"); } static void test_casefold(void) { uint32_t c, l, u[2]; const char *s, *ls; + fprintf(stderr, "test_casefold\n"); + for(c = 1; c < 256; ++c) { u[0] = c; u[1] = 0; @@ -361,6 +374,32 @@ static void test_casefold(void) { check_string(casefold(""), ""); } +/** @brief Less-than comparison function for integer heap */ +static inline int int_lt(int a, int b) { return a < b; } + +HEAP_TYPE(iheap, int, int_lt); + +/** @brief Tests for @ref heap.h */ +static void test_heap(void) { + struct iheap h[1]; + int n; + int last = -1; + + fprintf(stderr, "test_heap\n"); + + iheap_init(h); + for(n = 0; n < 1000; ++n) + iheap_insert(h, random() % 100); + for(n = 0; n < 1000; ++n) { + const int latest = iheap_remove(h); + if(last > latest) + fprintf(stderr, "should have %d <= %d\n", last, latest); + insist(last <= latest); + last = latest; + } + putchar('\n'); +} + int main(void) { insist('\n' == 0x0A); insist('\r' == 0x0D); @@ -380,6 +419,8 @@ int main(void) { /* configuration.c */ /* event.c */ /* fprintf.c */ + /* heap.c */ + test_heap(); /* hex.c */ test_hex(); /* inputline.c */ -- 2.11.0