nsz Git - libfirm/blob - ir/adt/pdeq.c

   1 /*
   2  * Copyrigth (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       double ended queue of generic pointers.
  23  * @author      Christian von Roques
  24  * @date        1999 by getting from fiasco
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #ifdef HAVE_STDIO_H
  32 # include <stdio.h>
  33 #endif
  34 #ifdef HAVE_STDLIB_H
  35 # include <stdlib.h>
  36 #endif
  37 #ifdef HAVE_STRING_H
  38 # include <string.h>
  39 #endif
  40
  41 #include <assert.h>
  42
  43 #include "fourcc.h"
  44 #include "pdeq.h"
  45 #include "xmalloc.h"
  46 #include "align.h"
  47
  48 /* Pointer Double Ended Queue */
  49 #define PDEQ_MAGIC1     FOURCC('P','D','E','1')
  50 #define PDEQ_MAGIC2     FOURCC('P','D','E','2')
  51
  52 /** Size of pdeq block cache. */
  53 #define TUNE_NSAVED_PDEQS 16
  54
  55 /**
  56  * Maximal number of data items in a pdeq chunk.
  57  */
  58 #define NDATA ((int)((PREF_MALLOC_SIZE - offsetof (pdeq, data)) / sizeof (void *)))
  59
  60 #ifdef NDEBUG
  61 # define VRFY(dq) ((void)0)
  62 #else
  63 # define VRFY(dq) assert((dq) && ((dq)->magic == PDEQ_MAGIC1))
  64 #endif
  65
  66 /**
  67  * A pointer double ended queue.
  68  * This structure is used as a list chunk either.
  69  */
  70 struct pdeq {
  71 #ifndef NDEBUG
  72   unsigned magic;       /**< debug magic */
  73 #endif
  74   pdeq *l_end, *r_end;  /**< left and right ends of the queue */
  75   pdeq *l, *r;          /**< left and right neighbor */
  76   int n;                /**< number of elements in the current chunk */
  77   int p;                /**< the read/write pointer */
  78   const void *data[1];  /**< storage for elements */
  79 };
  80
  81
  82 /**
  83  * cache of unused, pdeq blocks to speed up new_pdeq and del_pdeq.
  84  * +1 for compilers that can't grok empty arrays
  85  */
  86 static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1];
  87
  88 /**
  89  * Number of pdeqs in pdeq_store.
  90  */
  91 static unsigned pdeqs_cached;
  92
  93 /**
  94  * Free a pdeq chunk, put in into the cache if possible.
  95  *
  96  * @param p   The pdeq chunk.
  97  */
  98 static INLINE void free_pdeq_block (pdeq *p)
  99 {
 100 #ifndef NDEBUG
 101   p->magic = 0xbadf00d1;
 102 #endif
 103   if (pdeqs_cached < TUNE_NSAVED_PDEQS) {
 104     pdeq_block_cache[pdeqs_cached++] = p;
 105   } else {
 106     xfree (p);
 107   }
 108 }
 109
 110 /**
 111  * Allocate a new pdeq chunk, get it from the cache if possible.
 112  *
 113  * @return A new pdeq chunk.
 114  */
 115 static INLINE pdeq *alloc_pdeq_block (void)
 116 {
 117   pdeq *p;
 118   if (TUNE_NSAVED_PDEQS && pdeqs_cached) {
 119     p = pdeq_block_cache[--pdeqs_cached];
 120   } else {
 121     p = xmalloc(PREF_MALLOC_SIZE);
 122   }
 123   return p;
 124 }
 125
 126
 127 #ifndef NDEBUG
 128 /**
 129  * Verify a double ended list, assert if failure.
 130  *
 131  * @param dq   The list to verify.
 132  */
 133 void _pdeq_vrfy(pdeq *dq)
 134 {
 135   pdeq *q;
 136
 137   assert (   dq
 138           && (dq->magic == PDEQ_MAGIC1)
 139           && (dq->l_end && dq->r_end));
 140   q = dq->l_end;
 141   while (q) {
 142     assert (   ((q == dq) || (q->magic == PDEQ_MAGIC2))
 143             && ((q == dq->l_end) ^ (q->l != NULL))
 144             && ((q == dq->r_end) ^ (q->r != NULL))
 145             && (!q->l || (q == q->l->r))
 146             && ((q->n >= 0) && (q->n <= NDATA))
 147             && ((q == dq->l_end) || (q == dq->r_end) || (q->n == NDATA))
 148             && ((q->p >= 0) && (q->p < NDATA)));
 149     q = q->r;
 150   }
 151 }
 152 #endif
 153
 154 /* Creates a new double ended pointer list. */
 155 pdeq *new_pdeq(void)
 156 {
 157   pdeq *dq;
 158
 159   dq = alloc_pdeq_block();
 160
 161 #ifndef NDEBUG
 162   dq->magic = PDEQ_MAGIC1;
 163 #endif
 164   dq->l_end = dq->r_end = dq;
 165   dq->l = dq->r = NULL;
 166   dq->n = dq->p = 0;
 167
 168   VRFY(dq);
 169   return dq;
 170 }
 171
 172 /* Creates a new double ended pointer list and puts an initial pointer element in. */
 173 pdeq *new_pdeq1(const void *x)
 174 {
 175   return pdeq_putr(new_pdeq(), x);
 176 }
 177
 178 /* Delete a double ended pointer list. */
 179 void del_pdeq(pdeq *dq)
 180 {
 181   pdeq *q, *qq;
 182
 183   VRFY(dq);
 184
 185   q = dq->l_end;                /* left end of chain */
 186   /* pdeq trunk empty, but !pdeq_empty() ==> trunk not in chain */
 187   if (dq->n == 0 && dq->l_end != dq ) {
 188     free_pdeq_block(dq);
 189   }
 190
 191   /* Free all blocks in the pdeq chain */
 192   do {
 193     qq = q->r;
 194     free_pdeq_block(q);
 195   } while ((q = qq));
 196
 197 }
 198
 199 /* Checks if a list is empty. */
 200 int pdeq_empty(pdeq *dq)
 201 {
 202   VRFY(dq);
 203   return dq->l_end->n == 0;
 204 }
 205
 206 /* Returns the length of a double ended pointer list. */
 207 int pdeq_len(pdeq *dq)
 208 {
 209   int n;
 210   pdeq *q;
 211
 212   VRFY(dq);
 213
 214   n = 0;
 215   q = dq->l_end;
 216   do {
 217     n += q->n;
 218     q = q->r;
 219   }  while (q);
 220
 221   return n;
 222 }
 223
 224 /* Add a pointer to the right site of a double ended pointer list. */
 225 pdeq *pdeq_putr(pdeq *dq, const void *x)
 226 {
 227   pdeq *rdq;
 228   int n;
 229
 230   VRFY(dq);
 231
 232   rdq = dq->r_end;
 233   if (rdq->n >= NDATA) {        /* tailblock full */
 234     pdeq *ndq;
 235
 236     ndq = dq;                   /* try to reuse trunk, but ... */
 237     if (dq->n) {                /* ... if trunk used */
 238       /* allocate and init new block */
 239       ndq = alloc_pdeq_block();
 240 #ifndef NDEBUG
 241       ndq->magic = PDEQ_MAGIC2;
 242 #endif
 243       ndq->l_end = ndq->r_end = NULL;
 244     }
 245
 246     ndq->r = NULL;
 247     ndq->l = rdq; rdq->r = ndq;
 248     ndq->n = 0; ndq->p = 0;
 249     dq->r_end = ndq;
 250     rdq = ndq;
 251   }
 252
 253   n = rdq->n++ + rdq->p;
 254   if (n >= NDATA) n -= NDATA;
 255
 256   rdq->data[n] = x;
 257
 258   VRFY(dq);
 259   return dq;
 260 }
 261
 262 /* Add a pointer to the left site of a double ended pointer list. */
 263 pdeq *pdeq_putl(pdeq *dq, const void *x)
 264 {
 265   pdeq *ldq;
 266   int p;
 267
 268   VRFY(dq);
 269
 270   ldq = dq->l_end;
 271   if (ldq->n >= NDATA) {        /* headblock full */
 272     pdeq *ndq;
 273
 274     ndq = dq;                   /* try to reuse trunk, but ... */
 275     if (dq->n) {                /* ... if trunk used */
 276       /* allocate and init new block */
 277       ndq = alloc_pdeq_block();
 278 #ifndef NDEBUG
 279       ndq->magic = PDEQ_MAGIC2;
 280 #endif
 281       ndq->l_end = ndq->r_end = NULL;
 282     }
 283
 284     ndq->l = NULL;
 285     ndq->r = ldq; ldq->l = ndq;
 286     ndq->n = 0; ndq->p = 0;
 287     dq->l_end = ndq;
 288     ldq = ndq;
 289   }
 290
 291   ldq->n++;
 292   p = ldq->p - 1;
 293   if (p < 0) p += NDATA;
 294   ldq->p = p;
 295
 296   ldq->data[p] = x;
 297
 298   VRFY(dq);
 299   return dq;
 300 }
 301
 302 /* Retrieve a pointer from the right site of a double ended pointer list. */
 303 void *pdeq_getr(pdeq *dq)
 304 {
 305   pdeq *rdq;
 306   const void *x;
 307   int n;
 308
 309   VRFY(dq);
 310   assert(dq->l_end->n);
 311
 312   rdq = dq->r_end;
 313   n = rdq->p + --rdq->n;
 314   if (n >= NDATA) n -= NDATA;
 315   x = rdq->data[n];
 316
 317   if (rdq->n == 0) {
 318     if (rdq->l) {
 319       dq->r_end = rdq->l;
 320       rdq->l->r = NULL;
 321       rdq->l = NULL;
 322     } else {
 323       dq->r_end = dq->l_end = dq;
 324     }
 325     if (dq != rdq) {
 326       free_pdeq_block(rdq);
 327     }
 328   }
 329
 330   VRFY(dq);
 331   return (void *)x;
 332 }
 333
 334 /* Retrieve a pointer from the left site of a double ended pointer list. */
 335 void *pdeq_getl(pdeq *dq)
 336 {
 337   pdeq *ldq;
 338   const void *x;
 339   int p;
 340
 341   VRFY(dq);
 342   assert(dq->l_end->n);
 343
 344   ldq = dq->l_end;
 345   p = ldq->p;
 346   x = ldq->data[p];
 347   if (++p >= NDATA) p = 0;
 348   ldq->p = p;
 349
 350   if (--ldq->n == 0) {
 351     if (ldq->r) {
 352       dq->l_end = ldq->r;
 353       ldq->r->l = NULL;
 354       ldq->r = NULL;
 355     } else {
 356       dq->l_end = dq->r_end = dq;
 357     }
 358     if (dq != ldq) {
 359       free_pdeq_block(ldq);
 360     }
 361   }
 362
 363   VRFY(dq);
 364   return (void *)x;
 365 }
 366
 367 /*
 368  * Returns non-zero if a double ended pointer list
 369  * contains a pointer x.
 370  */
 371 int pdeq_contains(pdeq *dq, const void *x)
 372 {
 373   pdeq *q;
 374
 375   VRFY(dq);
 376
 377   q = dq->l_end;
 378   do {
 379     int p, ep;
 380
 381     p = q->p; ep = p + q->n;
 382
 383     if (ep > NDATA) {
 384       do {
 385         if (q->data[p] == x) return 1;
 386       } while (++p < NDATA);
 387       p = 0;
 388       ep -= NDATA;
 389     }
 390
 391     while (p < ep) {
 392       if (q->data[p++] == x) return 1;
 393     }
 394
 395     q = q->r;
 396   } while (q);
 397
 398   return 0;
 399 }
 400
 401 /*
 402  * Search a key in a double ended pointer list, the search
 403  * is controlled by a compare function.
 404  * An element is found, if the compare function returns 0.
 405  * The search is started from the left site of the list.
 406  */
 407 void *pdeq_search(pdeq *dq, cmp_fun cmp, const void *key)
 408 {
 409   pdeq *q;
 410   int p;
 411
 412   VRFY(dq);
 413
 414   q = dq->l_end;
 415   do {
 416     int ep;
 417
 418     p = q->p; ep = p + q->n;
 419
 420     if (ep > NDATA) {
 421       do {
 422         if (!cmp (q->data[p], key)) return (void *)q->data[p-1];
 423       } while (++p < NDATA);
 424       p = 0;
 425       ep -= NDATA;
 426     }
 427
 428     while (p < ep) {
 429       if (!cmp (q->data[p++], key)) return (void *)q->data[p-1];
 430     }
 431
 432     q = q->r;
 433   } while (q);
 434
 435   return NULL;
 436 }
 437
 438 /*
 439  * Convert the double ended pointer list into a linear array beginning from
 440  * left, the first element in the linear array will be the left one.
 441  */
 442 void **pdeq_copyl(pdeq *dq, const void **dst)
 443 {
 444   pdeq *q;
 445   const void **d = dst;
 446
 447   VRFY(dq);
 448
 449   q = dq->l_end;
 450   while (q) {
 451     int p, n;
 452
 453     p = q->p; n = q->n;
 454
 455     if (n + p > NDATA) {
 456       int nn = NDATA - p;
 457       memcpy((void *) d, &q->data[p], nn * sizeof(void *)); d += nn;
 458       p = 0; n -= nn;
 459     }
 460
 461     memcpy((void *) d, &q->data[p], n * sizeof(void *)); d += n;
 462
 463     q = q->r;
 464   }
 465
 466   return (void **)dst;
 467 }
 468
 469 /*
 470  * Convert the double ended pointer list into a linear array beginning from
 471  * right, the first element in the linear array will be the right one.
 472  */
 473 void **pdeq_copyr(pdeq *dq, const void **dst)
 474 {
 475   pdeq *q;
 476   const void **d = dst;
 477
 478   VRFY(dq);
 479
 480   q = dq->r_end;
 481   while (q) {
 482     int p, i;
 483
 484     p = q->p; i = q->n + p - 1;
 485     if (i >= NDATA) {
 486       i -= NDATA;
 487       do *d++ = q->data[i]; while (--i >= 0);
 488       i = NDATA - 1;
 489     }
 490
 491     do *d++ = q->data[i]; while (--i >= p);
 492
 493     q = q->l;
 494   }
 495
 496   return (void **)dst;
 497 }