X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fpdeq.c;h=642fd355803725759bcbe13c582e52fe6def5e90;hb=f82f9c6ffbe60d0c1988c7687b5bca29429a7c57;hp=493e2e6b7338ac3d3c64b0241addda65a7fba487;hpb=bdef3c48e38136efb131f4cb9966de7b6d07b24d;p=libfirm diff --git a/ir/adt/pdeq.c b/ir/adt/pdeq.c index 493e2e6b7..642fd3558 100644 --- a/ir/adt/pdeq.c +++ b/ir/adt/pdeq.c @@ -1,32 +1,44 @@ /* - * Project: libFIRM - * File name: ir/adt/pdeq.c - * Purpose: Pdeq --- double ended queue of generic pointers. - * Author: Christian von Roques - * Modified by: - * Created: 1999 by getting from fiasco - * CVS-ID: $Id$ - * Copyright: (c) 1995, 1996 Christian von Roques - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * 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 +#include -#include "cookies.h" -#include "debug.h" +#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 @@ -39,8 +51,7 @@ #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 /** @@ -49,13 +60,13 @@ */ struct pdeq { #ifndef NDEBUG - unsigned cookie; /**< debug 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; /**< number of elements in the current chunk */ - int p; /**< the read/write pointer */ - const void *data[1]; /**< storage for elements */ + 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 */ }; @@ -63,28 +74,26 @@ struct pdeq { * 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]; +static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1]; /** * Number of pdeqs in pdeq_store. */ -unsigned pdeqs_cached; +static unsigned pdeqs_cached; /** * Free a pdeq chunk, put in into the cache if possible. * * @param p The pdeq chunk. */ -static INLINE void free_pdeq_block (pdeq *p) +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); } } @@ -94,15 +103,13 @@ static INLINE void free_pdeq_block (pdeq *p) * * @return A new pdeq chunk. */ -static INLINE pdeq *alloc_pdeq_block (void) +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; } @@ -118,14 +125,12 @@ 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)) + 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)) @@ -145,14 +150,13 @@ pdeq *new_pdeq(void) 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); return dq; } @@ -181,18 +185,16 @@ void del_pdeq(pdeq *dq) free_pdeq_block(q); } while ((q = qq)); - if (d_(df_pdeq, 1)) printf("(del_pdeq %p)\n", 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); return dq->l_end->n == 0; } -/* Returns the lenght of a double ended pointer list. */ +/* Returns the length of a double ended pointer list. */ int pdeq_len(pdeq *dq) { int n; @@ -207,16 +209,14 @@ int pdeq_len(pdeq *dq) q = q->r; } while (q); - if (d_(df_pdeq, 4)) printf("(pdeq_len %p ==> %d)\n", dq, n); return n; } /* Add a pointer to the right site of a double ended pointer list. */ -pdeq * pdeq_putr(pdeq *dq, const void *x) +pdeq *pdeq_putr(pdeq *dq, const void *x) { pdeq *rdq; int n; - int pr = 0; VRFY(dq); @@ -228,9 +228,8 @@ pdeq * pdeq_putr(pdeq *dq, const void *x) if (dq->n) { /* ... if trunk used */ /* allocate and init new block */ ndq = alloc_pdeq_block(); - pr = d_(df_pdeq, 2); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -248,7 +247,6 @@ pdeq * 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); return dq; } @@ -257,7 +255,6 @@ pdeq *pdeq_putl(pdeq *dq, const void *x) { pdeq *ldq; int p; - int pr = 0; VRFY(dq); @@ -269,9 +266,8 @@ pdeq *pdeq_putl(pdeq *dq, const void *x) if (dq->n) { /* ... if trunk used */ /* allocate and init new block */ ndq = alloc_pdeq_block(); - pr = d_(df_pdeq, 2); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -291,7 +287,6 @@ pdeq *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); return dq; } @@ -301,7 +296,6 @@ void *pdeq_getr(pdeq *dq) pdeq *rdq; const void *x; int n; - int pr = 0; VRFY(dq); assert(dq->l_end->n); @@ -321,12 +315,10 @@ void *pdeq_getr(pdeq *dq) } if (dq != rdq) { 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); return (void *)x; } @@ -336,7 +328,6 @@ void *pdeq_getl(pdeq *dq) pdeq *ldq; const void *x; int p; - int pr = 0; VRFY(dq); assert(dq->l_end->n); @@ -357,12 +348,10 @@ void *pdeq_getl(pdeq *dq) } if (dq != ldq) { 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); return (void *)x; } @@ -383,22 +372,21 @@ int 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; } /* @@ -421,23 +409,21 @@ void *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]; } /* @@ -459,16 +445,15 @@ void **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; } @@ -499,6 +484,5 @@ void **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; }