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

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