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

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