From bdef3c48e38136efb131f4cb9966de7b6d07b24d Mon Sep 17 00:00:00 2001 From: Michael Beck Date: Mon, 28 Jun 2004 17:20:34 +0000 Subject: [PATCH] Removed useless misc.h Added doxygen comments to pdeq [r3224] --- ir/adt/Makefile.in | 2 +- ir/adt/misc.h | 20 ---- ir/adt/pdeq.c | 248 ++++++++++++++++++++++++--------------------- ir/adt/pdeq.h | 162 +++++++++++++++++++++++++---- ir/adt/set.c | 1 - 5 files changed, 281 insertions(+), 152 deletions(-) delete mode 100644 ir/adt/misc.h diff --git a/ir/adt/Makefile.in b/ir/adt/Makefile.in index 6d14ac7b0..1ba5c6937 100644 --- a/ir/adt/Makefile.in +++ b/ir/adt/Makefile.in @@ -20,7 +20,7 @@ disable_libiberty := @disable_libiberty@ SOURCES = Makefile.in \ array.c array.h cookies.h debug.c debug.h host.h obst.h \ pdeq.c pdeq.h pset.h set.c set.h pmap.h pmap.c eset.h eset.c \ - misc.h xmalloc.h + xmalloc.h ifeq ($(disable_libiberty),no) SOURCES += xmalloc.c diff --git a/ir/adt/misc.h b/ir/adt/misc.h deleted file mode 100644 index 7de7315b7..000000000 --- a/ir/adt/misc.h +++ /dev/null @@ -1,20 +0,0 @@ -/* - * Project: libFIRM - * File name: ir/adt/misc.h - * Purpose: Misc. declarations. - * Author: Markus Armbruster - * Modified by: - * Created: 1999 by getting from fiasco - * CVS-ID: $Id$ - * Copyright: (c) 1995, 1996 Markus Armbruster - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. - */ - -#ifndef _MISC_H_ -#define _MISC_H_ - -/* Miscellaneous */ - -typedef int (*cmp_fun) (const void *, const void *); - -#endif /* _MISC_H_ */ diff --git a/ir/adt/pdeq.c b/ir/adt/pdeq.c index e74d82a39..493e2e6b7 100644 --- a/ir/adt/pdeq.c +++ b/ir/adt/pdeq.c @@ -18,7 +18,6 @@ #include #include #include -#include # ifdef HAVE_STRING_H # include # endif @@ -29,10 +28,12 @@ #include "xmalloc.h" -/** Size of pdeq block cache */ +/** Size of pdeq block cache. */ #define TUNE_NSAVED_PDEQS 16 -/* # of data items in block */ +/** + * Maximal number of data items in a pdeq chunk. + */ #define NDATA ((int)((PREF_MALLOC_SIZE - offsetof (pdeq, data)) / sizeof (void *))) #ifdef NDEBUG @@ -42,26 +43,39 @@ (d_(df_vrfy_level,1) ? _pdeq_vrfy ((dq)) : assert ((dq) && ((dq)->cookie == PDEQ_COOKIE1))) #endif - +/** + * A pointer double ended queue. + * This structure is used as a list chunk either. + */ struct pdeq { #ifndef NDEBUG - unsigned cookie; + unsigned cookie; /**< debug cookie */ #endif - pdeq *l_end, *r_end; /* left and right ends of the deque */ - pdeq *l, *r; /* left and right neighbour */ - int n, p; - const void *data[1]; + pdeq *l_end, *r_end; /**< left and right ends of the deque */ + pdeq *l, *r; /**< left and right neighbour */ + int n; /**< number of elements in the current chunk */ + int p; /**< the read/write pointer */ + const void *data[1]; /**< storage for elements */ }; -/* cache of unused, pdeq blocks to speed up new_pdeq and del_pdeq. */ -/* +1 for compilers that can't grok empty arrays */ +/** + * cache of unused, pdeq blocks to speed up new_pdeq and del_pdeq. + * +1 for compilers that can't grok empty arrays + */ pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1]; -unsigned pdeqs_cached; /* # pdeqs in pdeq_store */ +/** + * Number of pdeqs in pdeq_store. + */ +unsigned pdeqs_cached; -static INLINE void -free_pdeq_block (pdeq *p) +/** + * Free a pdeq chunk, put in into the cache if possible. + * + * @param p The pdeq chunk. + */ +static INLINE void free_pdeq_block (pdeq *p) { #ifndef NDEBUG p->cookie = 0xbadf00d1; @@ -75,9 +89,12 @@ free_pdeq_block (pdeq *p) } } - -static INLINE pdeq * -alloc_pdeq_block (void) +/** + * Allocate a new pdeq chunk, get it from the cache if possible. + * + * @return A new pdeq chunk. + */ +static INLINE pdeq *alloc_pdeq_block (void) { pdeq *p; if (TUNE_NSAVED_PDEQS && pdeqs_cached) { @@ -92,8 +109,12 @@ alloc_pdeq_block (void) #ifndef NDEBUG -void -_pdeq_vrfy (pdeq *dq) +/** + * Verify a double ended list, assert if failure. + * + * @param dq The list to verify. + */ +void _pdeq_vrfy(pdeq *dq) { pdeq *q; @@ -105,20 +126,19 @@ _pdeq_vrfy (pdeq *dq) q = dq->l_end; while (q) { assert ( ((q == dq) || (q->cookie == PDEQ_COOKIE2)) - && ((q == dq->l_end) ^ (q->l!=0)) - && ((q == dq->r_end) ^ (q->r!=0)) + && ((q == dq->l_end) ^ (q->l != NULL)) + && ((q == dq->r_end) ^ (q->r != NULL)) && (!q->l || (q == q->l->r)) - && ((q->n>=0) && (q->n<=NDATA)) + && ((q->n >= 0) && (q->n <= NDATA)) && ((q == dq->l_end) || (q == dq->r_end) || (q->n == NDATA)) - && ((q->p>=0) && (q->pp >= 0) && (q->p < NDATA))); q = q->r; } } #endif - -pdeq * -new_pdeq (void) +/* Creates a new double ended pointer list. */ +pdeq *new_pdeq(void) { pdeq *dq; @@ -131,58 +151,54 @@ new_pdeq (void) dq->l = dq->r = NULL; dq->n = dq->p = 0; - VRFY (dq); - if (d_ (df_pdeq, 1)) printf ("(new_pdeq ==> %p)\n", dq); + VRFY(dq); + if (d_(df_pdeq, 1)) printf("(new_pdeq ==> %p)\n", dq); return dq; } - -pdeq * -new_pdeq1 (const void *x) +/* Creates a new double ended pointer list and puts an initial pointer element in. */ +pdeq *new_pdeq1(const void *x) { - return pdeq_putr (new_pdeq(), x); + return pdeq_putr(new_pdeq(), x); } - -void -del_pdeq (pdeq *dq) +/* Delete a double ended pointer list. */ +void del_pdeq(pdeq *dq) { pdeq *q, *qq; - VRFY (dq); + VRFY(dq); q = dq->l_end; /* left end of chain */ /* pdeq trunk empty, but !pdeq_empty() ==> trunk not in chain */ if (dq->n == 0 && dq->l_end != dq ) { - free_pdeq_block (dq); + free_pdeq_block(dq); } /* Free all blocks in the pdeq chain */ do { qq = q->r; - free_pdeq_block (q); + free_pdeq_block(q); } while ((q = qq)); - if (d_ (df_pdeq, 1)) printf ("(del_pdeq %p)\n", dq); + if (d_(df_pdeq, 1)) printf("(del_pdeq %p)\n", dq); } - -bool -pdeq_empty (pdeq *dq) +/* Checks if a list is empty. */ +int pdeq_empty(pdeq *dq) { - VRFY (dq); - if (d_ (df_pdeq, 4)) printf ("(pdeq_empty %p ==> %d)\n", dq, dq->l_end->n == 0); + VRFY(dq); + if (d_(df_pdeq, 4)) printf("(pdeq_empty %p ==> %d)\n", dq, dq->l_end->n == 0); return dq->l_end->n == 0; } - -int -pdeq_len (pdeq *dq) +/* Returns the lenght of a double ended pointer list. */ +int pdeq_len(pdeq *dq) { int n; pdeq *q; - VRFY (dq); + VRFY(dq); n = 0; q = dq->l_end; @@ -191,19 +207,18 @@ pdeq_len (pdeq *dq) q = q->r; } while (q); - if (d_ (df_pdeq, 4)) printf ("(pdeq_len %p ==> %d)\n", dq, n); + if (d_(df_pdeq, 4)) printf("(pdeq_len %p ==> %d)\n", dq, n); return n; } - -pdeq * -pdeq_putr (pdeq *dq, const void *x) +/* Add a pointer to the right site of a double ended pointer list. */ +pdeq * pdeq_putr(pdeq *dq, const void *x) { pdeq *rdq; int n; - bool pr = 0; + int pr = 0; - VRFY (dq); + VRFY(dq); rdq = dq->r_end; if (rdq->n >= NDATA) { /* tailblock full */ @@ -212,8 +227,8 @@ pdeq_putr (pdeq *dq, const void *x) ndq = dq; /* try to reuse trunk, but ... */ if (dq->n) { /* ... if trunk used */ /* allocate and init new block */ - ndq = alloc_pdeq_block (); - pr = d_ (df_pdeq, 2); + ndq = alloc_pdeq_block(); + pr = d_(df_pdeq, 2); #ifndef NDEBUG ndq->cookie = PDEQ_COOKIE2; #endif @@ -232,20 +247,19 @@ pdeq_putr (pdeq *dq, const void *x) rdq->data[n] = x; - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_putr %p %p)\n", dq, x); + VRFY(dq); + if (d_(df_pdeq, 3) || pr) printf("(pdeq_putr %p %p)\n", dq, x); return dq; } - -pdeq * -pdeq_putl (pdeq *dq, const void *x) +/* Add a pointer to the left site of a double ended pointer list. */ +pdeq *pdeq_putl(pdeq *dq, const void *x) { pdeq *ldq; int p; - bool pr = 0; + int pr = 0; - VRFY (dq); + VRFY(dq); ldq = dq->l_end; if (ldq->n >= NDATA) { /* headblock full */ @@ -254,8 +268,8 @@ pdeq_putl (pdeq *dq, const void *x) ndq = dq; /* try to reuse trunk, but ... */ if (dq->n) { /* ... if trunk used */ /* allocate and init new block */ - ndq = alloc_pdeq_block (); - pr = d_ (df_pdeq, 2); + ndq = alloc_pdeq_block(); + pr = d_(df_pdeq, 2); #ifndef NDEBUG ndq->cookie = PDEQ_COOKIE2; #endif @@ -276,26 +290,25 @@ pdeq_putl (pdeq *dq, const void *x) ldq->data[p] = x; - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_putl %p %p)\n", dq, x); + VRFY(dq); + if (d_(df_pdeq, 3) || pr) printf("(pdeq_putl %p %p)\n", dq, x); return dq; } - -void * -pdeq_getr (pdeq *dq) +/* Retrieve a pointer from the right site of a double ended pointer list. */ +void *pdeq_getr(pdeq *dq) { pdeq *rdq; const void *x; int n; - bool pr = 0; + int pr = 0; - VRFY (dq); - assert (dq->l_end->n); + VRFY(dq); + assert(dq->l_end->n); rdq = dq->r_end; n = rdq->p + --rdq->n; - if (n>=NDATA) n -= NDATA; + if (n >= NDATA) n -= NDATA; x = rdq->data[n]; if (rdq->n == 0) { @@ -307,27 +320,26 @@ pdeq_getr (pdeq *dq) dq->r_end = dq->l_end = dq; } if (dq != rdq) { - free_pdeq_block (rdq); - pr = d_ (df_pdeq, 2); + free_pdeq_block(rdq); + pr = d_(df_pdeq, 2); } } - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getr %p ==> %p)\n", dq, x); + VRFY(dq); + if (d_(df_pdeq, 3) || pr) printf("(pdeq_getr %p ==> %p)\n", dq, x); return (void *)x; } - -void * -pdeq_getl (pdeq *dq) +/* Retrieve a pointer from the left site of a double ended pointer list. */ +void *pdeq_getl(pdeq *dq) { pdeq *ldq; const void *x; int p; - bool pr = 0; + int pr = 0; - VRFY (dq); - assert (dq->l_end->n); + VRFY(dq); + assert(dq->l_end->n); ldq = dq->l_end; p = ldq->p; @@ -344,23 +356,25 @@ pdeq_getl (pdeq *dq) dq->l_end = dq->r_end = dq; } if (dq != ldq) { - free_pdeq_block (ldq); - pr = d_ (df_pdeq, 2); + free_pdeq_block(ldq); + pr = d_(df_pdeq, 2); } } - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getl %p ==> %p)\n", dq, x); + VRFY(dq); + if (d_(df_pdeq, 3) || pr) printf("(pdeq_getl %p ==> %p)\n", dq, x); return (void *)x; } - -bool -pdeq_contains (pdeq *dq, const void *x) +/* + * Returns non-zero if a double ended pointer list + * contains a pointer x. + */ +int pdeq_contains(pdeq *dq, const void *x) { pdeq *q; - VRFY (dq); + VRFY(dq); q = dq->l_end; do { @@ -379,22 +393,26 @@ pdeq_contains (pdeq *dq, const void *x) q = q->r; } while (q); - if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p ==> 0)\n", dq, x); + if (d_(df_pdeq, 3)) printf("(pdeq_contains %p %p ==> 0)\n", dq, x); return 0; found: /* The two gotos can be optimized away, if !DEBUG */ - if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p ==> 1)\n", dq, x); + if (d_(df_pdeq, 3)) printf("(pdeq_contains %p %p ==> 1)\n", dq, x); return 1; } - -void * -pdeq_search (pdeq *dq, cmp_fun cmp, const void *key) +/* + * Search a key in a double ended pointer list, the search + * is controlled by a compare function. + * An element is found, if the compare function returns 0. + * The search is started from the left site of the list. + */ +void *pdeq_search(pdeq *dq, cmp_fun cmp, const void *key) { pdeq *q; int p; - VRFY (dq); + VRFY(dq); q = dq->l_end; do { @@ -413,23 +431,25 @@ pdeq_search (pdeq *dq, cmp_fun cmp, const void *key) q = q->r; } while (q); - if (d_ (df_pdeq, 3)) printf ("(pdeq_search %p %p %p ==> 0)\n", dq, cmp, key); + if (d_(df_pdeq, 3)) printf("(pdeq_search %p %p %p ==> 0)\n", dq, cmp, key); return NULL; found: /* The two gotos can be optimized away, if !DEBUG */ - if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p %p ==> %p)\n", - dq, cmp, key, q->data[p]); + if (d_(df_pdeq, 3)) printf("(pdeq_contains %p %p %p ==> %p)\n", + dq, cmp, key, q->data[p]); return (void *)q->data[p-1]; } - -void ** -pdeq_copyl (pdeq *dq, const void **dst) +/* + * Convert the double ended pointer list into a linear array beginning from + * left, the first element in the linear array will be the left one. + */ +void **pdeq_copyl(pdeq *dq, const void **dst) { pdeq *q; const void **d = dst; - VRFY (dq); + VRFY(dq); q = dq->l_end; while (q) { @@ -439,27 +459,29 @@ pdeq_copyl (pdeq *dq, const void **dst) if (n + p > NDATA) { int nn = NDATA - p; - memcpy (d, &q->data[p], nn * sizeof (void *)); d += nn; + memcpy(d, &q->data[p], nn * sizeof(void *)); d += nn; p = 0; n -= nn; } - memcpy (d, &q->data[p], n * sizeof (void *)); d += n; + memcpy(d, &q->data[p], n * sizeof(void *)); d += n; q = q->r; } - if (d_ (df_pdeq, 3)) printf ("(pdeq_copyl %p %p ==> %p)\n", dq, dst, d); + if (d_(df_pdeq, 3)) printf("(pdeq_copyl %p %p ==> %p)\n", dq, dst, d); return (void **)dst; } - -void ** -pdeq_copyr (pdeq *dq, const void **dst) +/* + * Convert the double ended pointer list into a linear array beginning from + * right, the first element in the linear array will be the right one. + */ +void **pdeq_copyr(pdeq *dq, const void **dst) { pdeq *q; const void **d = dst; - VRFY (dq); + VRFY(dq); q = dq->r_end; while (q) { @@ -477,6 +499,6 @@ pdeq_copyr (pdeq *dq, const void **dst) q = q->l; } - if (d_ (df_pdeq, 3)) printf ("(pdeq_copyr %p %p ==> %p)\n", dq, dst, d); + if (d_(df_pdeq, 3)) printf("(pdeq_copyr %p %p ==> %p)\n", dq, dst, d); return (void **)dst; } diff --git a/ir/adt/pdeq.h b/ir/adt/pdeq.h index 8bbc098d6..0f3d8cf43 100644 --- a/ir/adt/pdeq.h +++ b/ir/adt/pdeq.h @@ -9,30 +9,158 @@ * Copyright: (c) 1995, 1996 Christian von Roques * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ - - #ifndef _PDEQ_H_ #define _PDEQ_H_ -#include +/** + * @file pdeq.h + * + * Declarations for double ended queue/list of generic pointers. + */ -#include "misc.h" +/** + * The type of the pointer compare function. + * + * @param elem The list element. + * @param key The user supplied key. + * + * @return 0 if the element matches the key, non-zero else. + */ +typedef int (*cmp_fun)(const void *elem, const void *key); +/** + * The pointer double ended queue (list). + */ typedef struct pdeq pdeq; -pdeq *new_pdeq (void); -pdeq *new_pdeq1 (const void *); -void del_pdeq (pdeq *); -int pdeq_len (pdeq *); -bool pdeq_empty (pdeq *); -bool pdeq_contains (pdeq *, const void *); -void *pdeq_search (pdeq *, cmp_fun cmp, const void *key); -void **pdeq_copyl (pdeq *, const void **); -void **pdeq_copyr (pdeq *, const void **); -pdeq *pdeq_putl (pdeq *, const void *); -pdeq *pdeq_putr (pdeq *, const void *); -void *pdeq_getl (pdeq *); -void *pdeq_getr (pdeq *); +/** + * Creates a new double ended pointer list. + * + * @return A new list. + */ +pdeq *new_pdeq(void); + +/** + * Creates a new double ended pointer list and puts an initial pointer element in. + * + * @param x The pointer element to put in. + * + * @return The new list. + */ +pdeq *new_pdeq1(const void *x); + +/** + * Delete a double ended pointer list. + * + * @param dq The list to be deleted. + */ +void del_pdeq(pdeq *dq); + +/** + * Returns the lenght of a double ended pointer list. + * + * @param dq The list. + */ +int pdeq_len(pdeq *dq); + +/** + * Checks if a list is empty. + * + * @param dq The list. + * + * @return non-zero if the list is empty. + */ +int pdeq_empty(pdeq *dq); + +/** + * Returns non-zero if a double ended pointer list + * contains a pointer x. + * + * @param dp The list. + * @param x The pointer to be searched for. + */ +int pdeq_contains(pdeq *dq, const void *x); + +/** + * Search a key in a double ended pointer list, the search + * is controlled by a compare function. + * An element is found, if the compare function returns 0. + * The search is started from the left site of the list. + * + * @param qp The list. + * @param cmp The compare function. + * @param key The search key. + * + * @return The address of the element entry if the key was found, + * NULL else. + */ +void *pdeq_search(pdeq *qp, cmp_fun cmp, const void *key); + +/** + * Convert the double ended pointer list into a linear array beginning from + * left, the first element in the linear array will be the left one. + * + * @param dq The list. + * @param dst A pointer to a pointer array with must be at least + * pdeq_len(dq) * sizeof(void *) + * + * @return dst + */ +void **pdeq_copyl(pdeq *qp, const void **dst); + +/** + * Convert the double ended pointer list into a linear array beginning from + * right, the first element in the linear array will be the right one. + * + * @param dq The list. + * @param dst A pointer to a pointer array with must be at least + * pdeq_len(dq) * sizeof(void *) + * + * @return dst + */ +void **pdeq_copyr(pdeq *qp, const void **dst); + +/** + * Add a pointer to the left site of a double ended pointer list. + * + * @param dq The list to add a pointer to. + * @param x The pointer element to be added + * + * @return The list. + */ +pdeq *pdeq_putl(pdeq *dq, const void *x); + +/** + * Add a pointer to the right site of a double ended pointer list. + * + * @param dq The list to add a pointer to. + * @param x The pointer element to be added + * + * @return The list. + */ +pdeq *pdeq_putr(pdeq *dq, const void *x); + +/** + * Retrieve a pointer from the left site of a double ended pointer list. + * + * @param dq The list + * + * @return The pointer element. + * + * @remark This function will fail if the list is empty. + */ +void *pdeq_getl(pdeq *dq); + +/** + * Retrieve a pointer from the right site of a double ended pointer list. + * + * @param dq The list + * + * @return The pointer element. + * + * @remark This function will fail if the list is empty. + */ +void *pdeq_getr(pdeq *dq); #ifdef NDEBUG #define PDEQ_VRFY(deq) ((void)0) diff --git a/ir/adt/set.c b/ir/adt/set.c index bb8cab483..f495bd146 100644 --- a/ir/adt/set.c +++ b/ir/adt/set.c @@ -59,7 +59,6 @@ #include #include #include -#include "misc.h" #include "xmalloc.h" #ifdef PSET # include "pset.h" -- 2.20.1