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

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