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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       double ended queue of generic pointers.
  23  * @author      Christian von Roques
  24  * @date        1999 by getting from fiasco
  25  */
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <assert.h>
  32
  33 #include "fourcc.h"
  34 #include "pdeq.h"
  35 #include "xmalloc.h"
  36
  37 /* Pointer Double Ended Queue */
  38 #define PDEQ_MAGIC1 FOURCC('P','D','E','1')
  39 #define PDEQ_MAGIC2 FOURCC('P','D','E','2')
  40
  41 /** Size of pdeq block cache. */
  42 #define TUNE_NSAVED_PDEQS 16
  43
  44 /** A size handled efficiently by malloc(), at least 1K.  */
  45 #define PREF_MALLOC_SIZE 2048
  46
  47 /**
  48  * Maximal number of data items in a pdeq chunk.
  49  */
  50 #define NDATA ((PREF_MALLOC_SIZE - offsetof(pdeq, data)) / sizeof(void *))
  51
  52 #ifdef NDEBUG
  53 # define VRFY(dq) ((void)0)
  54 #else
  55 # define VRFY(dq) assert((dq) && ((dq)->magic == PDEQ_MAGIC1))
  56 #endif
  57
  58 /**
  59  * A pointer double ended queue.
  60  * This structure is used as a list chunk either.
  61  */
  62 struct pdeq {
  63 #ifndef NDEBUG
  64         unsigned magic;       /**< debug magic */
  65 #endif
  66         pdeq *l_end, *r_end;  /**< left and right ends of the queue */
  67         pdeq *l, *r;          /**< left and right neighbor */
  68         size_t n;             /**< number of elements in the current chunk */
  69         size_t p;             /**< the read/write pointer */
  70         const void *data[1];  /**< storage for elements */
  71 };
  72
  73
  74 /**
  75  * cache of unused, pdeq blocks to speed up new_pdeq and del_pdeq.
  76  * +1 for compilers that can't grok empty arrays
  77  */
  78 static pdeq *pdeq_block_cache[TUNE_NSAVED_PDEQS+1];
  79
  80 /**
  81  * Number of pdeqs in pdeq_store.
  82  */
  83 static unsigned pdeqs_cached;
  84
  85 /**
  86  * Free a pdeq chunk, put in into the cache if possible.
  87  *
  88  * @param p   The pdeq chunk.
  89  */
  90 static inline void free_pdeq_block (pdeq *p)
  91 {
  92 #ifndef NDEBUG
  93         p->magic = 0xbadf00d1;
  94 #endif
  95         if (pdeqs_cached < TUNE_NSAVED_PDEQS) {
  96                 pdeq_block_cache[pdeqs_cached++] = p;
  97         } else {
  98                 xfree (p);
  99         }
 100 }
 101
 102 /**
 103  * Allocate a new pdeq chunk, get it from the cache if possible.
 104  *
 105  * @return A new pdeq chunk.
 106  */
 107 static inline pdeq *alloc_pdeq_block (void)
 108 {
 109         pdeq *p;
 110         if (TUNE_NSAVED_PDEQS && pdeqs_cached) {
 111                 p = pdeq_block_cache[--pdeqs_cached];
 112         } else {
 113                 p = (pdeq*) xmalloc(PREF_MALLOC_SIZE);
 114         }
 115         return p;
 116 }
 117
 118 /* Creates a new double ended pointer list. */
 119 pdeq *new_pdeq(void)
 120 {
 121         pdeq *dq;
 122
 123         dq = alloc_pdeq_block();
 124
 125 #ifndef NDEBUG
 126         dq->magic = PDEQ_MAGIC1;
 127 #endif
 128         dq->l_end = dq->r_end = dq;
 129         dq->l = dq->r = NULL;
 130         dq->n = dq->p = 0;
 131
 132         VRFY(dq);
 133         return dq;
 134 }
 135
 136 /* Creates a new double ended pointer list and puts an initial pointer element in. */
 137 pdeq *new_pdeq1(const void *x)
 138 {
 139         return pdeq_putr(new_pdeq(), x);
 140 }
 141
 142 /* Delete a double ended pointer list. */
 143 void 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 }
 162
 163 /* Checks if a list is empty. */
 164 int pdeq_empty(pdeq *dq)
 165 {
 166         VRFY(dq);
 167         return dq->l_end->n == 0;
 168 }
 169
 170 /* Returns the length of a double ended pointer list. */
 171 size_t pdeq_len(pdeq *dq)
 172 {
 173         size_t n;
 174         pdeq *q;
 175
 176         VRFY(dq);
 177
 178         n = 0;
 179         q = dq->l_end;
 180         do {
 181                 n += q->n;
 182                 q = q->r;
 183         }  while (q);
 184
 185         return n;
 186 }
 187
 188 /* Add a pointer to the right site of a double ended pointer list. */
 189 pdeq *pdeq_putr(pdeq *dq, const void *x)
 190 {
 191         pdeq *rdq;
 192         size_t n;
 193
 194         VRFY(dq);
 195
 196         rdq = dq->r_end;
 197         if (rdq->n >= NDATA) {  /* tailblock full */
 198                 pdeq *ndq;
 199
 200                 ndq = dq;           /* try to reuse trunk, but ... */
 201                 if (dq->n) {        /* ... if trunk used */
 202                         /* allocate and init new block */
 203                         ndq = alloc_pdeq_block();
 204 #ifndef NDEBUG
 205                         ndq->magic = PDEQ_MAGIC2;
 206 #endif
 207                         ndq->l_end = ndq->r_end = NULL;
 208                 }
 209
 210                 ndq->r = NULL;
 211                 ndq->l = rdq; rdq->r = ndq;
 212                 ndq->n = 0; ndq->p = 0;
 213                 dq->r_end = ndq;
 214                 rdq = ndq;
 215         }
 216
 217         n = rdq->n++ + rdq->p;
 218         if (n >= NDATA) n -= NDATA;
 219
 220         rdq->data[n] = x;
 221
 222         VRFY(dq);
 223         return dq;
 224 }
 225
 226 /* Add a pointer to the left site of a double ended pointer list. */
 227 pdeq *pdeq_putl(pdeq *dq, const void *x)
 228 {
 229         pdeq *ldq;
 230         size_t p;
 231
 232         VRFY(dq);
 233
 234         ldq = dq->l_end;
 235         if (ldq->n >= NDATA) {  /* headblock full */
 236                 pdeq *ndq;
 237
 238                 ndq = dq;           /* try to reuse trunk, but ... */
 239                 if (dq->n) {        /* ... if trunk used */
 240                         /* allocate and init new block */
 241                         ndq = alloc_pdeq_block();
 242 #ifndef NDEBUG
 243                         ndq->magic = PDEQ_MAGIC2;
 244 #endif
 245                         ndq->l_end = ndq->r_end = NULL;
 246                 }
 247
 248                 ndq->l = NULL;
 249                 ndq->r = ldq; ldq->l = ndq;
 250                 ndq->n = 0; ndq->p = 0;
 251                 dq->l_end = ndq;
 252                 ldq = ndq;
 253         }
 254
 255         ldq->n++;
 256         if (ldq->p == 0)
 257                 p = NDATA;
 258         else
 259                 p = ldq->p - 1;
 260         ldq->p = p;
 261
 262         ldq->data[p] = x;
 263
 264         VRFY(dq);
 265         return dq;
 266 }
 267
 268 /* Retrieve a pointer from the right site of a double ended pointer list. */
 269 void *pdeq_getr(pdeq *dq)
 270 {
 271         pdeq *rdq;
 272         const void *x;
 273         size_t n;
 274
 275         VRFY(dq);
 276         assert(dq->l_end->n);
 277
 278         rdq = dq->r_end;
 279         n = rdq->p + --rdq->n;
 280         if (n >= NDATA) n -= NDATA;
 281         x = rdq->data[n];
 282
 283         if (rdq->n == 0) {
 284                 if (rdq->l) {
 285                         dq->r_end = rdq->l;
 286                         rdq->l->r = NULL;
 287                         rdq->l = NULL;
 288                 } else {
 289                         dq->r_end = dq->l_end = dq;
 290                 }
 291                 if (dq != rdq) {
 292                         free_pdeq_block(rdq);
 293                 }
 294         }
 295
 296         VRFY(dq);
 297         return (void *)x;
 298 }
 299
 300 /* Retrieve a pointer from the left site of a double ended pointer list. */
 301 void *pdeq_getl(pdeq *dq)
 302 {
 303         pdeq *ldq;
 304         const void *x;
 305         size_t p;
 306
 307         VRFY(dq);
 308         assert(dq->l_end->n);
 309
 310         ldq = dq->l_end;
 311         p = ldq->p;
 312         x = ldq->data[p];
 313         if (++p >= NDATA) p = 0;
 314         ldq->p = p;
 315
 316         if (--ldq->n == 0) {
 317                 if (ldq->r) {
 318                         dq->l_end = ldq->r;
 319                         ldq->r->l = NULL;
 320                         ldq->r = NULL;
 321                 } else {
 322                         dq->l_end = dq->r_end = dq;
 323                 }
 324                 if (dq != ldq) {
 325                         free_pdeq_block(ldq);
 326                 }
 327         }
 328
 329         VRFY(dq);
 330         return (void *)x;
 331 }
 332
 333 /*
 334  * Returns non-zero if a double ended pointer list
 335  * contains a pointer x.
 336  */
 337 int pdeq_contains(pdeq *dq, const void *x)
 338 {
 339         pdeq *q;
 340
 341         VRFY(dq);
 342
 343         q = dq->l_end;
 344         do {
 345                 size_t p, ep;
 346
 347                 p = q->p; ep = p + q->n;
 348
 349                 if (ep > NDATA) {
 350                         do {
 351                                 if (q->data[p] == x) return 1;
 352                         } while (++p < NDATA);
 353                         p = 0;
 354                         ep -= NDATA;
 355                 }
 356
 357                 while (p < ep) {
 358                         if (q->data[p++] == x) return 1;
 359                 }
 360
 361                 q = q->r;
 362         } while (q);
 363
 364         return 0;
 365 }
 366
 367 /*
 368  * Search a key in a double ended pointer list, the search
 369  * is controlled by a compare function.
 370  * An element is found, if the compare function returns 0.
 371  * The search is started from the left site of the list.
 372  */
 373 void *pdeq_search(pdeq *dq, cmp_fun cmp, const void *key)
 374 {
 375         pdeq *q;
 376         size_t p;
 377
 378         VRFY(dq);
 379
 380         q = dq->l_end;
 381         do {
 382                 size_t ep;
 383
 384                 p = q->p; ep = p + q->n;
 385
 386                 if (ep > NDATA) {
 387                         do {
 388                                 if (!cmp(q->data[p], key)) return (void *)q->data[p-1];
 389                         } while (++p < NDATA);
 390                         p = 0;
 391                         ep -= NDATA;
 392                 }
 393
 394                 while (p < ep) {
 395                         if (!cmp(q->data[p++], key)) return (void *)q->data[p-1];
 396                 }
 397
 398                 q = q->r;
 399         } while (q);
 400
 401         return NULL;
 402 }
 403
 404 /*
 405  * Convert the double ended pointer list into a linear array beginning from
 406  * left, the first element in the linear array will be the left one.
 407  */
 408 void **pdeq_copyl(pdeq *dq, const void **dst)
 409 {
 410         pdeq *q;
 411         const void **d = dst;
 412
 413         VRFY(dq);
 414
 415         q = dq->l_end;
 416         while (q) {
 417                 size_t p, n;
 418
 419                 p = q->p; n = q->n;
 420
 421                 if (n + p > NDATA) {
 422                         /* p is always < NDATA */
 423                         size_t nn = NDATA - p;
 424                         memcpy((void *) d, &q->data[p], nn * sizeof(void *)); d += nn;
 425                         p = 0; n -= nn;
 426                 }
 427
 428                 memcpy((void *) d, &q->data[p], n * sizeof(void *)); d += n;
 429
 430                 q = q->r;
 431         }
 432
 433         return (void **)dst;
 434 }
 435
 436 /*
 437  * Convert the double ended pointer list into a linear array beginning from
 438  * right, the first element in the linear array will be the right one.
 439  */
 440 void **pdeq_copyr(pdeq *dq, const void **dst)
 441 {
 442         pdeq *q;
 443         const void **d = dst;
 444
 445         VRFY(dq);
 446
 447         q = dq->r_end;
 448         while (q) {
 449                 size_t p, i;
 450
 451                 p = q->p; i = q->n + p - 1;
 452                 if (i >= NDATA) {
 453                         i -= NDATA;
 454                         for (;; --i) {
 455                                 *d++ = q->data[i];
 456                                 if (i == 0)
 457                                         break;
 458                         }
 459                         i = NDATA - 1;
 460                 }
 461
 462                 for (;; --i) {
 463                         *d++ = q->data[i];
 464                         if (i <= p)
 465                                 break;
 466                 }
 467
 468                 q = q->l;
 469         }
 470
 471         return (void **)dst;
 472 }