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