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

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