X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fpdeq.c;h=642fd355803725759bcbe13c582e52fe6def5e90;hb=d6a6c024a4742e89a95deffaa5e95ca93c9d8c08;hp=9fab93ab158c68dd52b441ab45a9c6c9a9496933;hpb=efbeaff549fcc6015da255ed4d453a95937ff0fd;p=libfirm diff --git a/ir/adt/pdeq.c b/ir/adt/pdeq.c index 9fab93ab1..642fd3558 100644 --- a/ir/adt/pdeq.c +++ b/ir/adt/pdeq.c @@ -1,173 +1,206 @@ -/* Pdeq --- double ended queue of generic pointers. - Copyright (C) 1995, 1996 Christian von Roques */ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief double ended queue of generic pointers. + * @author Christian von Roques + * @date 1999 by getting from fiasco + * @version $Id$ + */ +#include "config.h" -#ifdef HAVE_CONFIG_H -# include -#endif - -#include #include #include -# ifdef HAVE_STRING_H -# include -# endif -#include "tune.h" -#include "cookies.h" -#include "debug.h" -#include "malloc.h" +#include +#include + +#include "fourcc.h" #include "pdeq.h" +#include "xmalloc.h" +#include "align.h" + +/* Pointer Double Ended Queue */ +#define PDEQ_MAGIC1 FOURCC('P','D','E','1') +#define PDEQ_MAGIC2 FOURCC('P','D','E','2') + +/** 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 # define VRFY(dq) ((void)0) #else -# define VRFY(dq) \ - (d_(df_vrfy_level,1) ? _pdeq_vrfy ((dq)) : assert ((dq) && ((dq)->cookie == PDEQ_COOKIE1))) +# define VRFY(dq) assert((dq) && ((dq)->magic == PDEQ_MAGIC1)) #endif - +/** + * A pointer double ended queue. + * This structure is used as a list chunk either. + */ struct pdeq { #ifndef NDEBUG - unsigned cookie; + unsigned magic; /**< debug magic */ #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 queue */ + pdeq *l, *r; /**< left and right neighbor */ + 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 */ -pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1]; -unsigned pdeqs_cached; /* # pdeqs in pdeq_store */ +/** + * cache of unused, pdeq blocks to speed up new_pdeq and del_pdeq. + * +1 for compilers that can't grok empty arrays + */ +static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1]; +/** + * Number of pdeqs in pdeq_store. + */ +static 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; + p->magic = 0xbadf00d1; #endif if (pdeqs_cached < TUNE_NSAVED_PDEQS) { - if (d_ (df_pdeq, 2)) printf ("[%p ==> pdeq_block_cache] ", p); pdeq_block_cache[pdeqs_cached++] = p; } else { - if (d_ (df_pdeq, 2)) printf ("[%p ==> free] ", p); xfree (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) { p = pdeq_block_cache[--pdeqs_cached]; - if (d_ (df_pdeq, 2)) printf ("[pdeq_block_cache ==> %p] ", p); } else { - p = xmalloc (PREF_MALLOC_SIZE); - if (d_ (df_pdeq, 2)) printf ("[malloc ==> %p] ", p); + p = xmalloc(PREF_MALLOC_SIZE); } return p; } #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; - if (d_ (df_pdeq, 5)) printf ("[pdeq_vrfy %p] ", dq); - assert ( dq - && (dq->cookie == PDEQ_COOKIE1) + && (dq->magic == PDEQ_MAGIC1) && (dq->l_end && dq->r_end)); 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)) + assert ( ((q == dq) || (q->magic == PDEQ_MAGIC2)) + && ((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; dq = alloc_pdeq_block(); #ifndef NDEBUG - dq->cookie = PDEQ_COOKIE1; + dq->magic = PDEQ_MAGIC1; #endif dq->l_end = dq->r_end = dq; 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); 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); } - -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); return dq->l_end->n == 0; } - -int -pdeq_len (pdeq *dq) +/* Returns the length 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; @@ -176,19 +209,16 @@ pdeq_len (pdeq *dq) q = q->r; } while (q); - 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; - VRFY (dq); + VRFY(dq); rdq = dq->r_end; if (rdq->n >= NDATA) { /* tailblock full */ @@ -197,10 +227,9 @@ 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(); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -217,20 +246,17 @@ 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); 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; - VRFY (dq); + VRFY(dq); ldq = dq->l_end; if (ldq->n >= NDATA) { /* headblock full */ @@ -239,10 +265,9 @@ 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(); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -261,26 +286,23 @@ 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); 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; - 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) { @@ -292,27 +314,23 @@ 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); } } - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getr %p ==> %p)\n", dq, x); + VRFY(dq); 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; - VRFY (dq); - assert (dq->l_end->n); + VRFY(dq); + assert(dq->l_end->n); ldq = dq->l_end; p = ldq->p; @@ -329,23 +347,23 @@ 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); } } - VRFY (dq); - if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getl %p ==> %p)\n", dq, x); + VRFY(dq); 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 { @@ -354,32 +372,35 @@ pdeq_contains (pdeq *dq, const void *x) p = q->p; ep = p + q->n; if (ep > NDATA) { - do if (q->data[p] == x) goto found; while (++p < NDATA); + do { + if (q->data[p] == x) return 1; + } while (++p < NDATA); p = 0; ep -= NDATA; } - while (p < ep) if (q->data[p++] == x) goto found; + while (p < ep) { + if (q->data[p++] == x) return 1; + } q = q->r; } while (q); - 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); - 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 { @@ -388,33 +409,33 @@ pdeq_search (pdeq *dq, cmp_fun cmp, const void *key) p = q->p; ep = p + q->n; if (ep > NDATA) { - do if (!cmp (q->data[p], key)) goto found; while (++p < NDATA); + do { + if (!cmp (q->data[p], key)) return (void *)q->data[p-1]; + } while (++p < NDATA); p = 0; ep -= NDATA; } - while (p < ep) if (!cmp (q->data[p++], key)) goto found; + while (p < ep) { + if (!cmp (q->data[p++], key)) return (void *)q->data[p-1]; + } q = q->r; } while (q); - 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]); - 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) { @@ -424,27 +445,28 @@ 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((void *) d, &q->data[p], nn * sizeof(void *)); d += nn; p = 0; n -= nn; } - memcpy (d, &q->data[p], n * sizeof (void *)); d += n; + memcpy((void *) 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); 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) { @@ -462,6 +484,5 @@ 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); return (void **)dst; }