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 Markus Armbruster
  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
  29
  30 /** Size of pdeq block cache */
  31 #define TUNE_NSAVED_PDEQS 16
  32
  33 #ifndef INLINE
  34 #ifdef USE_GCC_INLINE
  35 #define INLINE inline
  36 #else
  37 #define INLINE
  38 #endif
  39 #endif
  40
  41 /* # of data items in block */
  42 #define NDATA ((int)((PREF_MALLOC_SIZE - offsetof (pdeq, data)) / sizeof (void *)))
  43
  44 #ifdef NDEBUG
  45 # define VRFY(dq) ((void)0)
  46 #else
  47 # define VRFY(dq) \
  48     (d_(df_vrfy_level,1) ? _pdeq_vrfy ((dq)) : assert ((dq) && ((dq)->cookie == PDEQ_COOKIE1)))
  49 #endif
  50
  51
  52 struct pdeq {
  53 #ifndef NDEBUG
  54   unsigned cookie;
  55 #endif
  56   pdeq *l_end, *r_end;          /* left and right ends of the deque */
  57   pdeq *l, *r;                  /*  left and right neighbour */
  58   int n, p;
  59   const void *data[1];
  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 pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1];
  66 unsigned pdeqs_cached;          /* # pdeqs in pdeq_store */
  67
  68
  69 static INLINE void
  70 free_pdeq_block (pdeq *p)
  71 {
  72 #ifndef NDEBUG
  73   p->cookie = 0xbadf00d1;
  74 #endif
  75   if (pdeqs_cached < TUNE_NSAVED_PDEQS) {
  76     if (d_ (df_pdeq, 2)) printf ("[%p ==> pdeq_block_cache] ", p);
  77     pdeq_block_cache[pdeqs_cached++] = p;
  78   } else {
  79     if (d_ (df_pdeq, 2)) printf ("[%p ==> free] ", p);
  80     xfree (p);
  81   }
  82 }
  83
  84
  85 static INLINE pdeq *
  86 alloc_pdeq_block (void)
  87 {
  88   pdeq *p;
  89   if (TUNE_NSAVED_PDEQS && pdeqs_cached) {
  90     p = pdeq_block_cache[--pdeqs_cached];
  91     if (d_ (df_pdeq, 2)) printf ("[pdeq_block_cache ==> %p] ", p);
  92   } else {
  93     p = xmalloc (PREF_MALLOC_SIZE);
  94     if (d_ (df_pdeq, 2)) printf ("[malloc ==> %p] ", p);
  95   }
  96   return p;
  97 }
  98
  99
 100 #ifndef NDEBUG
 101 void
 102 _pdeq_vrfy (pdeq *dq)
 103 {
 104   pdeq *q;
 105
 106   if (d_ (df_pdeq, 5)) printf ("[pdeq_vrfy %p] ", dq);
 107
 108   assert (   dq
 109           && (dq->cookie == PDEQ_COOKIE1)
 110           && (dq->l_end && dq->r_end));
 111   q = dq->l_end;
 112   while (q) {
 113     assert (   ((q == dq) || (q->cookie == PDEQ_COOKIE2))
 114             && ((q == dq->l_end) ^ (q->l!=0))
 115             && ((q == dq->r_end) ^ (q->r!=0))
 116             && (!q->l || (q == q->l->r))
 117             && ((q->n>=0) && (q->n<=NDATA))
 118             && ((q == dq->l_end) || (q == dq->r_end) || (q->n == NDATA))
 119             && ((q->p>=0) && (q->p<NDATA)));
 120     q = q->r;
 121   }
 122 }
 123 #endif
 124
 125
 126 pdeq *
 127 new_pdeq (void)
 128 {
 129   pdeq *dq;
 130
 131   dq = alloc_pdeq_block();
 132
 133 #ifndef NDEBUG
 134   dq->cookie = PDEQ_COOKIE1;
 135 #endif
 136   dq->l_end = dq->r_end = dq;
 137   dq->l = dq->r = NULL;
 138   dq->n = dq->p = 0;
 139
 140   VRFY (dq);
 141   if (d_ (df_pdeq, 1)) printf ("(new_pdeq ==> %p)\n", dq);
 142   return dq;
 143 }
 144
 145
 146 pdeq *
 147 new_pdeq1 (const void *x)
 148 {
 149   return pdeq_putr (new_pdeq(), x);
 150 }
 151
 152
 153 void
 154 del_pdeq (pdeq *dq)
 155 {
 156   pdeq *q, *qq;
 157
 158   VRFY (dq);
 159
 160   q = dq->l_end;                /* left end of chain */
 161   /* pdeq trunk empty, but !pdeq_empty() ==> trunk not in chain */
 162   if (dq->n == 0 && dq->l_end != dq ) {
 163     free_pdeq_block (dq);
 164   }
 165
 166   /* Free all blocks in the pdeq chain */
 167   do {
 168     qq = q->r;
 169     free_pdeq_block (q);
 170   } while ((q = qq));
 171
 172   if (d_ (df_pdeq, 1)) printf ("(del_pdeq %p)\n", dq);
 173 }
 174
 175
 176 bool
 177 pdeq_empty (pdeq *dq)
 178 {
 179   VRFY (dq);
 180   if (d_ (df_pdeq, 4)) printf ("(pdeq_empty %p ==> %d)\n", dq, dq->l_end->n == 0);
 181   return dq->l_end->n == 0;
 182 }
 183
 184
 185 int
 186 pdeq_len (pdeq *dq)
 187 {
 188   int n;
 189   pdeq *q;
 190
 191   VRFY (dq);
 192
 193   n = 0;
 194   q = dq->l_end;
 195   do {
 196     n += q->n;
 197     q = q->r;
 198   }  while (q);
 199
 200   if (d_ (df_pdeq, 4)) printf ("(pdeq_len %p ==> %d)\n", dq, n);
 201   return n;
 202 }
 203
 204
 205 pdeq *
 206 pdeq_putr (pdeq *dq, const void *x)
 207 {
 208   pdeq *rdq;
 209   int n;
 210   bool pr = 0;
 211
 212   VRFY (dq);
 213
 214   rdq = dq->r_end;
 215   if (rdq->n >= NDATA) {        /* tailblock full */
 216     pdeq *ndq;
 217
 218     ndq = dq;                   /* try to reuse trunk, but ... */
 219     if (dq->n) {                /* ... if trunk used */
 220       /* allocate and init new block */
 221       ndq = alloc_pdeq_block ();
 222       pr = d_ (df_pdeq, 2);
 223 #ifndef NDEBUG
 224       ndq->cookie = PDEQ_COOKIE2;
 225 #endif
 226       ndq->l_end = ndq->r_end = NULL;
 227     }
 228
 229     ndq->r = NULL;
 230     ndq->l = rdq; rdq->r = ndq;
 231     ndq->n = 0; ndq->p = 0;
 232     dq->r_end = ndq;
 233     rdq = ndq;
 234   }
 235
 236   n = rdq->n++ + rdq->p;
 237   if (n >= NDATA) n -= NDATA;
 238
 239   rdq->data[n] = x;
 240
 241   VRFY (dq);
 242   if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_putr %p %p)\n", dq, x);
 243   return dq;
 244 }
 245
 246
 247 pdeq *
 248 pdeq_putl (pdeq *dq, const void *x)
 249 {
 250   pdeq *ldq;
 251   int p;
 252   bool pr = 0;
 253
 254   VRFY (dq);
 255
 256   ldq = dq->l_end;
 257   if (ldq->n >= NDATA) {        /* headblock full */
 258     pdeq *ndq;
 259
 260     ndq = dq;                   /* try to reuse trunk, but ... */
 261     if (dq->n) {                /* ... if trunk used */
 262       /* allocate and init new block */
 263       ndq = alloc_pdeq_block ();
 264       pr = d_ (df_pdeq, 2);
 265 #ifndef NDEBUG
 266       ndq->cookie = PDEQ_COOKIE2;
 267 #endif
 268       ndq->l_end = ndq->r_end = NULL;
 269     }
 270
 271     ndq->l = NULL;
 272     ndq->r = ldq; ldq->l = ndq;
 273     ndq->n = 0; ndq->p = 0;
 274     dq->l_end = ndq;
 275     ldq = ndq;
 276   }
 277
 278   ldq->n++;
 279   p = ldq->p - 1;
 280   if (p < 0) p += NDATA;
 281   ldq->p = p;
 282
 283   ldq->data[p] = x;
 284
 285   VRFY (dq);
 286   if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_putl %p %p)\n", dq, x);
 287   return dq;
 288 }
 289
 290
 291 void *
 292 pdeq_getr (pdeq *dq)
 293 {
 294   pdeq *rdq;
 295   const void *x;
 296   int n;
 297   bool pr = 0;
 298
 299   VRFY (dq);
 300   assert (dq->l_end->n);
 301
 302   rdq = dq->r_end;
 303   n = rdq->p + --rdq->n;
 304   if (n>=NDATA) n -= NDATA;
 305   x = rdq->data[n];
 306
 307   if (rdq->n == 0) {
 308     if (rdq->l) {
 309       dq->r_end = rdq->l;
 310       rdq->l->r = NULL;
 311       rdq->l = NULL;
 312     } else {
 313       dq->r_end = dq->l_end = dq;
 314     }
 315     if (dq != rdq) {
 316       free_pdeq_block (rdq);
 317       pr = d_ (df_pdeq, 2);
 318     }
 319   }
 320
 321   VRFY (dq);
 322   if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getr %p ==> %p)\n", dq, x);
 323   return (void *)x;
 324 }
 325
 326
 327 void *
 328 pdeq_getl (pdeq *dq)
 329 {
 330   pdeq *ldq;
 331   const void *x;
 332   int p;
 333   bool pr = 0;
 334
 335   VRFY (dq);
 336   assert (dq->l_end->n);
 337
 338   ldq = dq->l_end;
 339   p = ldq->p;
 340   x = ldq->data[p];
 341   if (++p >= NDATA) p = 0;
 342   ldq->p = p;
 343
 344   if (--ldq->n == 0) {
 345     if (ldq->r) {
 346       dq->l_end = ldq->r;
 347       ldq->r->l = NULL;
 348       ldq->r = NULL;
 349     } else {
 350       dq->l_end = dq->r_end = dq;
 351     }
 352     if (dq != ldq) {
 353       free_pdeq_block (ldq);
 354       pr = d_ (df_pdeq, 2);
 355     }
 356   }
 357
 358   VRFY (dq);
 359   if (d_ (df_pdeq, 3) || pr) printf ("(pdeq_getl %p ==> %p)\n", dq, x);
 360   return (void *)x;
 361 }
 362
 363
 364 bool
 365 pdeq_contains (pdeq *dq, const void *x)
 366 {
 367   pdeq *q;
 368
 369   VRFY (dq);
 370
 371   q = dq->l_end;
 372   do {
 373     int p, ep;
 374
 375     p = q->p; ep = p + q->n;
 376
 377     if (ep > NDATA) {
 378       do if (q->data[p] == x) goto found; while (++p < NDATA);
 379       p = 0;
 380       ep -= NDATA;
 381     }
 382
 383     while (p < ep) if (q->data[p++] == x) goto found;
 384
 385     q = q->r;
 386   } while (q);
 387
 388   if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p ==> 0)\n", dq, x);
 389   return 0;
 390
 391 found:  /* The two gotos can be optimized away, if !DEBUG */
 392   if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p ==> 1)\n", dq, x);
 393   return 1;
 394 }
 395
 396
 397 void *
 398 pdeq_search (pdeq *dq, cmp_fun cmp, const void *key)
 399 {
 400   pdeq *q;
 401   int p;
 402
 403   VRFY (dq);
 404
 405   q = dq->l_end;
 406   do {
 407     int ep;
 408
 409     p = q->p; ep = p + q->n;
 410
 411     if (ep > NDATA) {
 412       do if (!cmp (q->data[p], key)) goto found; while (++p < NDATA);
 413       p = 0;
 414       ep -= NDATA;
 415     }
 416
 417     while (p < ep) if (!cmp (q->data[p++], key)) goto found;
 418
 419     q = q->r;
 420   } while (q);
 421
 422   if (d_ (df_pdeq, 3)) printf ("(pdeq_search %p %p %p ==> 0)\n", dq, cmp, key);
 423   return NULL;
 424
 425 found:  /* The two gotos can be optimized away, if !DEBUG */
 426   if (d_ (df_pdeq, 3)) printf ("(pdeq_contains %p %p %p ==> %p)\n",
 427                                dq, cmp, key, q->data[p]);
 428   return (void *)q->data[p-1];
 429 }
 430
 431
 432 void **
 433 pdeq_copyl (pdeq *dq, const void **dst)
 434 {
 435   pdeq *q;
 436   const void **d = dst;
 437
 438   VRFY (dq);
 439
 440   q = dq->l_end;
 441   while (q) {
 442     int p, n;
 443
 444     p = q->p; n = q->n;
 445
 446     if (n + p > NDATA) {
 447       int nn = NDATA - p;
 448       memcpy (d, &q->data[p], nn * sizeof (void *)); d += nn;
 449       p = 0; n -= nn;
 450     }
 451
 452     memcpy (d, &q->data[p], n * sizeof (void *)); d += n;
 453
 454     q = q->r;
 455   }
 456
 457   if (d_ (df_pdeq, 3)) printf ("(pdeq_copyl %p %p ==> %p)\n", dq, dst, d);
 458   return (void **)dst;
 459 }
 460
 461
 462 void **
 463 pdeq_copyr (pdeq *dq, const void **dst)
 464 {
 465   pdeq *q;
 466   const void **d = dst;
 467
 468   VRFY (dq);
 469
 470   q = dq->r_end;
 471   while (q) {
 472     int p, i;
 473
 474     p = q->p; i = q->n + p - 1;
 475     if (i >= NDATA) {
 476       i -= NDATA;
 477       do *d++ = q->data[i]; while (--i >= 0);
 478       i = NDATA - 1;
 479     }
 480
 481     do *d++ = q->data[i]; while (--i >= p);
 482
 483     q = q->l;
 484   }
 485
 486   if (d_ (df_pdeq, 3)) printf ("(pdeq_copyr %p %p ==> %p)\n", dq, dst, d);
 487   return (void **)dst;
 488 }