X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fpdeq.c;h=8d596d0f3e574d1e0b3354f38abd185d918712b4;hb=3da5ed2598245b896255bc444aaa1768f6098cfe;hp=9ea9747eb5797f4b19f05a9acd2a073f4f1f27c3;hpb=0613f68c24fea77a4048c6018b5263d9d1d6e6af;p=libfirm diff --git a/ir/adt/pdeq.c b/ir/adt/pdeq.c index 9ea9747eb..8d596d0f3 100644 --- a/ir/adt/pdeq.c +++ b/ir/adt/pdeq.c @@ -1,35 +1,51 @@ /* - * 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 "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 +/** A size handled efficiently by malloc(), at least 1K. */ +#define PREF_MALLOC_SIZE 2048 + /** * Maximal number of data items in a pdeq chunk. */ @@ -38,7 +54,7 @@ #ifdef NDEBUG # define VRFY(dq) ((void)0) #else -# define VRFY(dq) assert((dq) && ((dq)->cookie == PDEQ_COOKIE1)) +# define VRFY(dq) assert((dq) && ((dq)->magic == PDEQ_MAGIC1)) #endif /** @@ -47,13 +63,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 */ }; @@ -61,22 +77,22 @@ 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) { pdeq_block_cache[pdeqs_cached++] = p; @@ -90,13 +106,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]; } else { - p = xmalloc (PREF_MALLOC_SIZE); + p = xmalloc(PREF_MALLOC_SIZE); } return p; } @@ -112,13 +128,12 @@ void _pdeq_vrfy(pdeq *dq) { pdeq *q; - 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)) @@ -138,7 +153,7 @@ 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; @@ -182,7 +197,7 @@ int pdeq_empty(pdeq *dq) 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; @@ -201,7 +216,7 @@ int pdeq_len(pdeq *dq) } /* 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; @@ -217,7 +232,7 @@ pdeq * pdeq_putr(pdeq *dq, const void *x) /* allocate and init new block */ ndq = alloc_pdeq_block(); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -255,7 +270,7 @@ pdeq *pdeq_putl(pdeq *dq, const void *x) /* allocate and init new block */ ndq = alloc_pdeq_block(); #ifndef NDEBUG - ndq->cookie = PDEQ_COOKIE2; + ndq->magic = PDEQ_MAGIC2; #endif ndq->l_end = ndq->r_end = NULL; } @@ -433,11 +448,11 @@ 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; }