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

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