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

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