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

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