/*
- * 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.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
* @brief double ended queue of generic pointers.
* @author Christian von Roques
* @date 1999 by getting from fiasco
- * @version $Id$
*/
#include "config.h"
/**
* Maximal number of data items in a pdeq chunk.
*/
-#define NDATA ((int)((PREF_MALLOC_SIZE - offsetof (pdeq, data)) / sizeof (void *)))
+#define NDATA ((PREF_MALLOC_SIZE - offsetof(pdeq, data)) / sizeof(void *))
#ifdef NDEBUG
# define VRFY(dq) ((void)0)
#endif
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 */
+ size_t n; /**< number of elements in the current chunk */
+ size_t 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
*/
-static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1];
+static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS];
/**
* Number of pdeqs in pdeq_store.
static inline pdeq *alloc_pdeq_block (void)
{
pdeq *p;
- if (TUNE_NSAVED_PDEQS && pdeqs_cached) {
+ if (pdeqs_cached > 0) {
p = pdeq_block_cache[--pdeqs_cached];
} else {
- p = xmalloc(PREF_MALLOC_SIZE);
+ p = (pdeq*) xmalloc(PREF_MALLOC_SIZE);
}
return p;
}
-
-#ifndef NDEBUG
-/**
- * Verify a double ended list, assert if failure.
- *
- * @param dq The list to verify.
- */
-void _pdeq_vrfy(pdeq *dq)
-{
- pdeq *q;
-
- assert ( dq
- && (dq->magic == PDEQ_MAGIC1)
- && (dq->l_end && dq->r_end));
- q = dq->l_end;
- while (q) {
- 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 == dq->l_end) || (q == dq->r_end) || (q->n == NDATA))
- && ((q->p >= 0) && (q->p < NDATA)));
- q = q->r;
- }
-}
-#endif
-
/* Creates a new double ended pointer list. */
pdeq *new_pdeq(void)
{
qq = q->r;
free_pdeq_block(q);
} while ((q = qq));
-
}
/* Checks if a list is empty. */
}
/* Returns the length of a double ended pointer list. */
-int pdeq_len(pdeq *dq)
+size_t pdeq_len(pdeq *dq)
{
- int n;
+ size_t n;
pdeq *q;
VRFY(dq);
pdeq *pdeq_putr(pdeq *dq, const void *x)
{
pdeq *rdq;
- int n;
+ size_t n;
VRFY(dq);
pdeq *pdeq_putl(pdeq *dq, const void *x)
{
pdeq *ldq;
- int p;
+ size_t p;
VRFY(dq);
}
ldq->n++;
- p = ldq->p - 1;
- if (p < 0) p += NDATA;
+ if (ldq->p == 0)
+ p = NDATA;
+ else
+ p = ldq->p - 1;
ldq->p = p;
ldq->data[p] = x;
{
pdeq *rdq;
const void *x;
- int n;
+ size_t n;
VRFY(dq);
assert(dq->l_end->n);
{
pdeq *ldq;
const void *x;
- int p;
+ size_t p;
VRFY(dq);
assert(dq->l_end->n);
q = dq->l_end;
do {
- int p, ep;
+ size_t p, ep;
p = q->p; ep = p + q->n;
void *pdeq_search(pdeq *dq, cmp_fun cmp, const void *key)
{
pdeq *q;
- int p;
+ size_t p;
VRFY(dq);
q = dq->l_end;
do {
- int ep;
+ size_t ep;
p = q->p; ep = p + q->n;
if (ep > NDATA) {
do {
- if (!cmp (q->data[p], key)) return (void *)q->data[p-1];
+ 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)) return (void *)q->data[p-1];
+ if (!cmp(q->data[p++], key)) return (void *)q->data[p-1];
}
q = q->r;
q = dq->l_end;
while (q) {
- int p, n;
+ size_t p, n;
p = q->p; n = q->n;
if (n + p > NDATA) {
- int nn = NDATA - p;
+ /* p is always < NDATA */
+ size_t nn = NDATA - p;
memcpy((void *) d, &q->data[p], nn * sizeof(void *)); d += nn;
p = 0; n -= nn;
}
q = dq->r_end;
while (q) {
- int p, i;
+ size_t p, i;
p = q->p; i = q->n + p - 1;
if (i >= NDATA) {
i -= NDATA;
- do *d++ = q->data[i]; while (--i >= 0);
+ for (;; --i) {
+ *d++ = q->data[i];
+ if (i == 0)
+ break;
+ }
i = NDATA - 1;
}
- do *d++ = q->data[i]; while (--i >= p);
+ for (;; --i) {
+ *d++ = q->data[i];
+ if (i <= p)
+ break;
+ }
q = q->l;
}