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

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