nsz Git - libfirm/blob - ir/ana2/qset.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Copyrigth (C) 1995-2007 University of Karlsruhe.  All right reserved.
   5  *
   6  * This file is part of libFirm.
   7  *
   8  * This file may be distributed and/or modified under the terms of the
   9  * GNU General Public License version 2 as published by the Free Software
  10  * Foundation and appearing in the file LICENSE.GPL included in the
  11  * packaging of this file.
  12  *
  13  * Licensees holding valid libFirm Professional Edition licenses may use
  14  * this file in accordance with the libFirm Commercial License.
  15  * Agreement provided with the Software.
  16  *
  17  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  18  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE.
  20  */
  21
  22 /**
  23  * @file
  24  * @brief   yet another set implementation
  25  * @author  Florian
  26  * @date    Mon 18 Oct 2004
  27  * @version $Id$
  28  */
  29 #ifdef HAVE_CONFIG_H
  30 # include "config.h"
  31 #endif
  32
  33 # include <stdio.h>
  34 # include <stdlib.h>
  35 # include <assert.h>
  36 # include <string.h>
  37
  38 # include "obst.h"
  39 # include "timing.h"
  40 # include "qset.h"
  41
  42 /* local globals */
  43 int qset_id = 0;
  44
  45 /* local protos */
  46
  47 # ifdef UNSINN
  48 /* Check whether the given list of sortables is sorted. */
  49 static void q_check (sortable_t*, const int);
  50 # endif /* defined UNSINN */
  51
  52 /* Test whether the given val is among values.  Return the index of
  53    val in values, or -1. */
  54 static int q_test (sortable_t*, const sortable_t, const int);
  55
  56 /* Sort n_elems entries  in 'values' */
  57 static void q_sort (sortable_t*, const int);
  58
  59 /* Compare funktion, meant to be qsort(3)-compatible */
  60 static INLINE int sortable_compare (const void *pa, const void *pb)
  61 {
  62   const int a = * (unsigned int*) pa;
  63   const int b = * (unsigned int*) pb;
  64
  65   if (a==b) {
  66     return (0);
  67   }
  68
  69   return ((a < b) ? -1 : +1);
  70 }
  71
  72 /*
  73    Wrapper for mixed allocation
  74 */
  75 static void *mix_malloc (struct obstack *obst, size_t size)
  76 {
  77   if (NULL != obst) {
  78     return (obstack_alloc (obst, size));
  79   } else {
  80     return (xmalloc (size));
  81   }
  82 }
  83
  84 /*
  85   Allocate a list of sortables of the given length.
  86 */
  87 static sortable_t *alloc_list (const int len, struct obstack *obst)
  88 {
  89   sortable_t *values = (sortable_t*) mix_malloc (obst, len * sizeof (sortable_t));
  90
  91   memset (values, 0x00, len * sizeof (sortable_t));
  92
  93   return (values);
  94 }
  95
  96 # ifdef UNSINN
  97 /*
  98   Create a list of sortables of the given length.
  99 */
 100 static sortable_t *gen_list (const int len, struct obstack *obst)
 101 {
 102   int i;
 103   sortable_t *values = alloc_list (len, obst);
 104
 105   for (i = 0; i < len; i ++) {
 106     values [i] = rand () >> 16;
 107   }
 108
 109   return (values);
 110 }
 111 # endif /* defined UNSINN */
 112
 113 /*
 114   Helper to q_test --- return the index of val in values, or -1
 115 */
 116 static int _q_test (sortable_t *values,
 117                     const sortable_t val,
 118                     const int lo, const int hi)
 119 {
 120   int mid;
 121
 122   /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
 123
 124   if (lo == hi) {
 125     if (EQUAL (val, values [lo])) {
 126       return (lo);
 127     } else {
 128       return (-1);
 129     }
 130   }
 131
 132   if (COMPARE (val, values [lo])) {
 133     /* too low */
 134     return (-1);
 135   }
 136
 137   if (COMPARE (values [hi], val)) {
 138     /* too high */
 139     return (-1);
 140   }
 141
 142   mid = (hi + lo) / 2;
 143
 144   if (EQUAL (val, values [mid])) {
 145     return (mid);
 146   }
 147
 148   if (COMPARE (val, values [mid])) {
 149     return (_q_test (values, val, lo, mid));
 150   } else {
 151     return (_q_test (values, val, mid+1, hi));
 152   }
 153 }
 154
 155 /*
 156   Helper to q_sort
 157 */
 158 static void _q_sort (sortable_t *values, const int lo, const int hi)
 159 {
 160   sortable_t pivot;
 161   int p_lo;
 162   int p_hi;
 163
 164   /* handle base case: */
 165   if (lo >= hi) {
 166     return;
 167   }
 168
 169   if (1 == hi - lo) {
 170     if (COMPARE (values [hi], values [lo])) {
 171       sortable_t tmp = values [lo];
 172       values [lo] = values [hi];
 173       values [hi] = tmp;
 174     }
 175
 176     return;
 177   }
 178
 179   pivot = values [lo];
 180
 181   p_lo = lo+1;
 182   p_hi = hi;
 183
 184   while (p_lo <= p_hi) {
 185     if (COMPARE (values [p_lo], pivot)) {
 186       values [p_lo-1] = values [p_lo];
 187
 188       p_lo ++;
 189     } else {
 190       sortable_t tmp = values [p_lo];
 191
 192       values [p_lo] = values [p_hi];
 193       values [p_hi] = tmp;
 194
 195       p_hi --;
 196     }
 197   }
 198
 199   values [p_lo-1] = pivot;
 200
 201   _q_sort (values, lo, p_lo-1);
 202   _q_sort (values, p_lo, hi);
 203 }
 204
 205 # ifdef UNSINN
 206 /*
 207   Little test harness for q_sort and friends.
 208 */
 209 static void test_qsort (const int n_runs, const int max_elems, const int incr)
 210 {
 211   int n_elems = 0;
 212   int i;
 213
 214   fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
 215
 216   while (n_elems <= max_elems) {
 217     int total = 0;
 218     int qtotal = 0;
 219
 220     for (i = 0; i < n_runs; i ++) {
 221       sortable_t *list = gen_list (n_elems, NULL);
 222
 223       timing_t *timing = start_timing ();
 224       q_sort (list, n_elems);
 225       total += end_timing (timing);
 226
 227       q_check (list, n_elems);
 228
 229       free (list);
 230     }
 231
 232     for (i = 0; i < n_runs; i ++) {
 233       sortable_t *list = gen_list (n_elems, NULL);
 234
 235       timing_t *timing = start_timing ();
 236       qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
 237       qtotal += end_timing (timing);
 238
 239       q_check (list, n_elems);
 240
 241       free (list);
 242     }
 243
 244     fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
 245     fflush (stdout);
 246     n_elems += incr;
 247   }
 248
 249
 250   fprintf (stdout, "\n");
 251 }
 252
 253 /*
 254   Little test harness for the qset implementation
 255 */
 256 static void test_qset (const int n_entries)
 257 {
 258   int i;
 259   int n1, n2, n;
 260
 261   qset_t *q1 = qset_new (n_entries, NULL);
 262   qset_t *q2 = qset_new (n_entries, NULL);
 263   qset_t *q = NULL;
 264
 265   sortable_t *values = gen_list (n_entries, NULL);
 266
 267   for (i = 0; i < n_entries; i ++) {
 268     qset_insert (q1, values [i]);
 269     qset_insert (q2, values [i]);
 270   }
 271
 272   fprintf (stdout, "q1: \t\t");
 273   qset_print (q1, stdout);
 274   qset_sort (q1);
 275   qset_sort (q2);
 276
 277   /* TEST */
 278   q2->is_sorted = FALSE;
 279   qset_sort (q2);
 280
 281   fprintf (stdout, "q1 (sorted):\t");
 282   qset_print (q1, stdout);
 283
 284   assert (qset_compare (q1, q2));
 285
 286   q = qset_union (q1, q2);
 287   fprintf (stdout, "qq (union):\t");
 288   qset_print (q, stdout);
 289
 290   n1 = qset_size (q1);
 291   n2 = qset_size (q2);
 292   n = qset_size (q);
 293
 294   fprintf (stdout, "q1.size = %i\n", n1);
 295   fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
 296   fprintf (stdout, "q2.size = %i\n", n2);
 297   fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
 298   fprintf (stdout, "q.size  = %i\n", n);
 299   fprintf (stdout, "q.slots  = %i\n", q->n_slots);
 300
 301   assert (n1 == n2);
 302   assert (n2 == n);
 303
 304   assert (qset_compare (q1, q2));
 305   assert (qset_compare (q2, q));
 306   assert (qset_compare (q, q1));
 307
 308   for (i = 0; i < n_entries; i ++) {
 309     assert (qset_contains (q1, values [i]));
 310     assert (qset_contains (q2, values [i]));
 311     assert (qset_contains (q, values [i]));
 312   }
 313
 314   qset_compact (q1);
 315   qset_compact (q);
 316
 317   fprintf (stdout, "q1.size = %i\n", n1);
 318   fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
 319   fprintf (stdout, "q2.size = %i\n", n2);
 320   fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
 321   fprintf (stdout, "q.size  = %i\n", n);
 322   fprintf (stdout, "q.slots  = %i\n", q->n_slots);
 323
 324   assert (qset_compare (q1, q2));
 325   assert (qset_compare (q2, q));
 326   assert (qset_compare (q, q1));
 327
 328   for (i = 0; i < n_entries; i ++) {
 329     assert (qset_contains (q1, values [i]));
 330     assert (qset_contains (q2, values [i]));
 331     assert (qset_contains (q, values [i]));
 332   }
 333
 334   qset_delete (q);
 335   qset_delete (q1);
 336   qset_delete (q2);
 337 }
 338 # endif /* defned UNSINN */
 339
 340 /* PRIVATE QSET IMPLEMENTATION */
 341 /*
 342    Resize a qset to (at least) the given size.
 343 */
 344 static void qset_resize (qset_t *qset, const int n_slots)
 345 {
 346   int new_size;
 347   sortable_t *values = NULL;
 348
 349   if (qset->n_slots >= n_slots) {
 350     return;
 351   }
 352
 353   new_size = qset->n_slots;
 354
 355   while (new_size < n_slots) {
 356     new_size *= 2;
 357   }
 358
 359   values = alloc_list (new_size, qset->obst);
 360
 361   memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
 362   memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
 363
 364   if (NULL == qset->obst) {
 365     free (qset->values);
 366   }
 367
 368   qset->values = values;
 369   qset->n_slots = new_size;
 370 }
 371
 372 /*
 373    Print a list of sortables.
 374 */
 375 static void q_print (sortable_t *values, const int n_values, FILE *stream)
 376 {
 377   int i;
 378
 379   fprintf (stream, "{");
 380
 381   for (i = 0; i < n_values; i ++) {
 382     if (0 == values [i]) {
 383       fprintf (stream, "_");
 384     } else {
 385       fprintf (stream, "0x08%x", (int) values [i]);
 386     }
 387
 388     if (i + 1 != n_values) {
 389       fprintf (stream, ", ");
 390     }
 391   }
 392
 393   fprintf (stream, "}\n");
 394 }
 395
 396 # ifdef UNSINN
 397 /*
 398   Check whether the given list of sortables is sorted.
 399 */
 400 static void q_check (sortable_t *values, const int n_values)
 401 {
 402   int i;
 403
 404   for (i = 1; i < n_values; i ++) {
 405     assert (COMPARE (values [i-1], values [i]) ||
 406             EQUAL   (values [i-1], values [i]));
 407   }
 408
 409   for (i = 1; i < n_values; i ++) {
 410     assert (-1 != q_test (values, values [i], n_values));
 411   }
 412 }
 413 # endif /* defined UNSINN */
 414
 415 /*
 416   Test whether the given val is among values.  Return the lowest index of val
 417   in values, or -1.
 418 */
 419 static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
 420 {
 421   int idx = _q_test (values, val, 0, n_elems-1);
 422
 423   while ((0 <= idx-1) && EQUAL (values [idx], val)) {
 424     idx --;
 425   }
 426
 427   return (idx);
 428 }
 429
 430 /*
 431   Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
 432 */
 433 static void q_sort (sortable_t *values, const int n_elems)
 434 {
 435   _q_sort (values, 0, n_elems-1);
 436 }
 437
 438 /* PUBLIC INTERFACE */
 439
 440 /*
 441   Allocate a new qset with initial space for up to n_elems.
 442   If a non-NULL obstack is given, it is used for all allocations of this qset
 443   and must be initialised and deleted by the user of the qset.
 444 */
 445 qset_t *qset_new (const int n_elems, struct obstack *obst)
 446 {
 447   qset_t *qset = (qset_t*) mix_malloc (obst, sizeof (qset_t));
 448
 449   qset->obst = obst;
 450   qset->values = alloc_list (n_elems, obst);
 451   memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
 452
 453   qset->n_slots = n_elems;
 454   qset->n_elems = 0;
 455   qset->is_sorted = FALSE;
 456   qset->id = qset_id ++;
 457
 458   return (qset);
 459 }
 460
 461 /*
 462   Sort the entries of the given qset.
 463 */
 464 void qset_sort (qset_t *qset)
 465 {
 466   int occ = 0;
 467   int i;
 468
 469   if (qset->is_sorted) {
 470     return;
 471   }
 472
 473   q_sort (qset->values, qset->n_elems);
 474
 475   for (i = 1; i < qset->n_elems; i ++) {
 476     if (! EQUAL (qset->values [i], qset->values [occ])) {
 477       qset->values [++ occ] = qset->values [i];
 478     }
 479   }
 480
 481   occ ++;
 482
 483   /*
 484   if (qset->n_elems != occ) {
 485     fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
 486     }*/
 487
 488   qset->n_elems = occ;
 489
 490   qset->is_sorted = TRUE;
 491 }
 492
 493 /*
 494   Compact a qset to take up no more space than required.
 495 */
 496 void qset_compact (qset_t *qset)
 497 {
 498   if (NULL == qset->obst) {
 499     sortable_t *values = (sortable_t*) mix_malloc (qset->obst,
 500                                                    qset->n_elems * sizeof (sortable_t));
 501     memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
 502
 503     memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
 504
 505     free (qset->values);
 506
 507     qset->values = values;
 508     qset->n_slots = qset->n_elems;
 509   }
 510 }
 511
 512 /*
 513   Free the memory associated with the given qset
 514 */
 515 void qset_delete (qset_t *qset)
 516 {
 517   memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
 518
 519   if (NULL == qset->obst) {
 520     free (qset->values);
 521   }
 522
 523   memset (qset, 0x00, sizeof (qset_t));
 524
 525   if (NULL == qset->obst) {
 526     free (qset);
 527   }
 528 }
 529
 530 /*
 531   Test whether the given qset contains the given value.
 532 */
 533 int qset_contains (qset_t *qset, sortable_t val)
 534 {
 535   qset_sort (qset);
 536
 537   return (-1 != q_test (qset->values, val, qset->n_elems));
 538 }
 539
 540 /*
 541   Delete the given value from the given qset (if it exists)
 542 */
 543 void qset_remove (qset_t *qset, sortable_t val)
 544 {
 545   int idx;
 546   int occ = 0;
 547   int i;
 548
 549   qset_sort (qset);
 550
 551   idx = q_test (qset->values, val, qset->n_elems);
 552
 553   if (-1 == idx) {
 554     return;
 555   }
 556
 557   while (EQUAL (qset->values [idx + occ], val)) {
 558     occ ++;
 559   }
 560
 561   for (i = idx; i < qset->n_elems - occ; i ++) {
 562     qset->values [i] = qset->values [i+occ];
 563   }
 564
 565   qset->n_elems -= occ;
 566 }
 567
 568 /*
 569   Insert the given elem into the given qset; return nonzero iff any
 570   involved values change.
 571 */
 572 int qset_insert (qset_t *qset, sortable_t val)
 573 {
 574   int i;
 575   const int n_elems = qset->n_elems;
 576
 577   /* todo: sort, find */
 578   assert (0 != val);
 579
 580   for (i = 0; i < n_elems; i ++) {
 581     if (EQUAL (val, qset->values [i])) {
 582       return (FALSE);
 583     }
 584   }
 585
 586   qset_resize (qset, qset->n_elems+1);
 587
 588   /* qset_print (qset, stdout); */
 589   /* fprintf (stdout, "%s: must insert 0x%08x\n", __FUNCTION__, (void*) val); */
 590
 591   qset->values [qset->n_elems++] = val;
 592   qset->is_sorted = FALSE;
 593
 594   return (TRUE);
 595 }
 596
 597 /*
 598   Insert all elems of qset2 into qset1; return nonzero iff any
 599   involved values change. qset2 is *not* deleted.
 600 */
 601 int qset_insert_all (qset_t *qset1, qset_t *qset2)
 602 {
 603   int change = FALSE;
 604   sortable_t val = qset_start (qset2);
 605
 606   while (0 != val) {
 607     change |= qset_insert (qset1, val);
 608
 609     val = qset_next (qset2);
 610   }
 611
 612   qset_sort (qset1);
 613
 614   return (change);
 615 }
 616
 617 /*
 618   Compare two qsets.
 619 */
 620 int qset_compare (qset_t *qset1, qset_t *qset2)
 621 {
 622   int i;
 623   const int n_elems = qset1->n_elems;
 624
 625   qset_sort (qset1);
 626   qset_sort (qset2);
 627
 628   if (qset1->n_elems != qset2->n_elems) {
 629     return (FALSE);
 630   }
 631
 632   for (i = 0; i < n_elems; i ++) {
 633     if (qset1->values [i] != qset2->values [i]) {
 634       return (FALSE);
 635     }
 636   }
 637
 638   return (TRUE);
 639 }
 640
 641 /*
 642   Returns the union of two qsets.
 643 */
 644 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
 645 {
 646   qset_t *qset = (qset_t*) mix_malloc (qset1->obst, sizeof (qset_t));
 647   const int n_elems = qset1->n_elems + qset2->n_elems;
 648
 649   qset->values = alloc_list (n_elems, qset1->obst);
 650
 651   memcpy (qset->values, qset1->values,
 652           qset1->n_elems * sizeof (sortable_t));
 653
 654   memcpy (qset->values+qset1->n_elems,
 655           qset2->values, qset2->n_elems * sizeof (sortable_t));
 656
 657   qset->obst = qset1->obst;
 658   qset->n_elems = n_elems;
 659   qset->n_slots = qset->n_elems;
 660
 661   qset_sort (qset);
 662
 663   return (qset);
 664 }
 665
 666 /*
 667   Report the size of the given qset.
 668 */
 669 int qset_size (qset_t *qset)
 670 {
 671   return (qset->n_elems);
 672 }
 673
 674 /*
 675   Print the given qset to the given stream.
 676 */
 677 void qset_print (qset_t *qset, FILE *stream)
 678 {
 679   q_print (qset->values, qset->n_elems, stream);
 680 }
 681
 682 /*
 683    Check wether the given qset is empty
 684 */
 685 int qset_is_empty (qset_t *qset)
 686 {
 687   return (0 == qset->n_elems);
 688 }
 689
 690 /*
 691   Initialise a new iteration over a qset
 692 */
 693 sortable_t *qset_start (qset_t *qset)
 694 {
 695   sortable_t *start;
 696
 697   qset->cursor = 0;
 698
 699   start = qset_next (qset);
 700
 701   return (start);    /* works for empty sets, too */
 702 }
 703
 704 /*
 705   Step to the next element
 706 */
 707 sortable_t *qset_next (qset_t *qset)
 708 {
 709   if (qset->n_elems == qset->cursor) {
 710     return (NULL);
 711   }
 712
 713   /* quick fix to skip NULL entries */
 714   while ((qset->cursor < qset->n_elems) &&
 715          (NULL == qset->values [qset->cursor])) {
 716     qset->cursor ++;
 717   }
 718
 719   return (qset->values [qset->cursor++]);
 720 }
 721
 722
 723 # ifdef UNSINN
 724 int qset_test_main (int argc, char **argv)
 725 {
 726   struct timeval tp;
 727   unsigned int seed;
 728
 729   if (-1 == gettimeofday (&tp, NULL)) {
 730     perror ("gettimeofday");
 731     exit (EXIT_FAILURE);
 732   }
 733
 734   seed = (unsigned int) tp.tv_usec;
 735   srand (seed);
 736
 737   /* test_qsort (20, 1000000, 100000); */
 738
 739   test_qset (atoi (argv [1]));
 740
 741   exit (EXIT_SUCCESS);
 742 }
 743 # endif /* defined UNSINN */
 744
 745 /*
 746   $Log$
 747   Revision 1.12  2006/06/06 12:06:27  beck
 748   use xmalloc instead of malloc
 749
 750   Revision 1.11  2005/06/22 09:34:11  beck
 751   typo fixed
 752
 753   Revision 1.10  2004/12/21 15:37:31  beck
 754   added config.h include
 755   removed unused sys/times.h
 756   removed C99 constructs
 757
 758   Revision 1.9  2004/12/20 17:34:35  liekweg
 759   fix recursion handling
 760
 761   Revision 1.8  2004/12/06 12:49:26  liekweg
 762   virtually no change
 763
 764   Revision 1.7  2004/11/30 14:47:11  liekweg
 765   insert report changes
 766
 767   Revision 1.6  2004/11/26 15:58:30  liekweg
 768   don't free inside obstacks (thx, michael)
 769
 770   Revision 1.5  2004/11/24 14:53:56  liekweg
 771   Bugfixes
 772
 773   Revision 1.4  2004/11/18 16:35:45  liekweg
 774   Added unique ids for debugging
 775
 776   Revision 1.3  2004/11/09 16:45:36  liekweg
 777   print pointers
 778
 779   Revision 1.2  2004/11/08 12:32:00  liekweg
 780   Moved q_* methods into private section
 781
 782   Revision 1.1  2004/11/04 14:55:13  liekweg
 783   added qset
 784
 785
 786  */