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