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