From b8956e9ee534c889e1974e368c37bb4c4b9d9911 Mon Sep 17 00:00:00 2001 From: Richard Kettlewell Date: Fri, 21 Sep 2007 23:58:24 +0100 Subject: [PATCH] tidying and docs --- disobedience/choose.c | 3 +- lib/heap.h | 110 +++++++++++++++++++++++++------------------------- lib/vector.h | 36 +++++++++++++++-- 3 files changed, 90 insertions(+), 59 deletions(-) diff --git a/disobedience/choose.c b/disobedience/choose.c index 24aa9f6..f13362a 100644 --- a/disobedience/choose.c +++ b/disobedience/choose.c @@ -48,7 +48,8 @@ struct displaydata { }; /* instantiate the node vector type */ -VECTOR_TYPE(nodevector, struct choosenode *, xrealloc) + +VECTOR_TYPE(nodevector, struct choosenode *, xrealloc); struct choosenode { struct choosenode *parent; /* parent node */ diff --git a/lib/heap.h b/lib/heap.h index 4603942..56821bf 100644 --- a/lib/heap.h +++ b/lib/heap.h @@ -76,61 +76,61 @@ * \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; \ - } \ - \ +#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 diff --git a/lib/vector.h b/lib/vector.h index f40fe38..6cadaf1 100644 --- a/lib/vector.h +++ b/lib/vector.h @@ -17,10 +17,32 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 * USA */ +/** @file lib/vector.h @brief Dynamic array template */ #ifndef VECTOR_H #define VECTOR_H +/** @brief Dynamic array template + * @param NAME type name + * @param ETYPE element type + * @param REALLOC realloc function + * + * Defines @c struct @p NAME as a dynamic array with element type @p + * ETYPE. @p REALLOC should have the same signature as realloc() and + * will be used for all memory allocation. Typically it would be + * xrealloc() for pointer-containing element types and + * xrealloc_noptr() for pointer-free element types. + * + * Clients are inspected to read the @p vec member of the structure, + * which points to the first element, and the @p nvec member, which is + * the number of elements. It is safe to reduce @p nvec. Do not + * touch any other members. + * + * The functions defined are: + * - NAME_init(struct NAME *v) which initializes @p v + * - NAME_append(struct NAME *v, ETYPE value) which appends @p value to @p v + * - NAME_terminate(struct NAME *v) which zeroes out the element beyond the last + */ #define VECTOR_TYPE(NAME,ETYPE,REALLOC) \ \ struct NAME { \ @@ -45,15 +67,23 @@ static inline void NAME##_terminate(struct NAME *v) { \ v->vec = REALLOC(v->vec, ++v->nslots * sizeof(ETYPE)); \ memset(&v->vec[v->nvec], 0, sizeof (ETYPE)); \ } \ + \ +struct vector_swallow_semicolon -VECTOR_TYPE(vector, char *, xrealloc) -VECTOR_TYPE(dynstr, char, xrealloc_noptr) -VECTOR_TYPE(dynstr_ucs4, uint32_t, xrealloc_noptr) +/** @brief A dynamic array of pointers to strings */ +VECTOR_TYPE(vector, char *, xrealloc); +/** @brief A dynamic string */ +VECTOR_TYPE(dynstr, char, xrealloc_noptr); +/** @brief A dynamic unicode string */ +VECTOR_TYPE(dynstr_ucs4, uint32_t, xrealloc_noptr); +/** @brief Append many strings to a @ref vector */ void vector_append_many(struct vector *v, char **vec, int nvec); +/** @brief Append @p n bytes to a @ref dynstr */ void dynstr_append_bytes(struct dynstr *v, const char *ptr, size_t n); +/** @brief Append a string to a @ref dynstr */ static inline void dynstr_append_string(struct dynstr *v, const char *ptr) { dynstr_append_bytes(v, ptr, strlen(ptr)); } -- 2.11.0