4 * Copyrigth (C) 1995-2007 University of Karlsruhe. All right reserved.
6 * This file is part of libFirm.
8 * This file may be distributed and/or modified under the terms of the
9 * GNU General Public License version 2 as published by the Free Software
10 * Foundation and appearing in the file LICENSE.GPL included in the
11 * packaging of this file.
13 * Licensees holding valid libFirm Professional Edition licenses may use
14 * this file in accordance with the libFirm Commercial License.
15 * Agreement provided with the Software.
17 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
18 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * @brief yet another set implementation
26 * @date Mon 18 Oct 2004
48 /* Check whether the given list of sortables is sorted. */
49 static void q_check (sortable_t*, const int);
50 # endif /* defined UNSINN */
52 /* Test whether the given val is among values. Return the index of
53 val in values, or -1. */
54 static int q_test (sortable_t*, const sortable_t, const int);
56 /* Sort n_elems entries in 'values' */
57 static void q_sort (sortable_t*, const int);
59 /* Compare funktion, meant to be qsort(3)-compatible */
60 static INLINE int sortable_compare (const void *pa, const void *pb)
62 const int a = * (unsigned int*) pa;
63 const int b = * (unsigned int*) pb;
69 return ((a < b) ? -1 : +1);
73 Wrapper for mixed allocation
75 static void *mix_malloc (struct obstack *obst, size_t size)
78 return (obstack_alloc (obst, size));
80 return (xmalloc (size));
85 Allocate a list of sortables of the given length.
87 static sortable_t *alloc_list (const int len, struct obstack *obst)
89 sortable_t *values = (sortable_t*) mix_malloc (obst, len * sizeof (sortable_t));
91 memset (values, 0x00, len * sizeof (sortable_t));
98 Create a list of sortables of the given length.
100 static sortable_t *gen_list (const int len, struct obstack *obst)
103 sortable_t *values = alloc_list (len, obst);
105 for (i = 0; i < len; i ++) {
106 values [i] = rand () >> 16;
111 # endif /* defined UNSINN */
114 Helper to q_test --- return the index of val in values, or -1
116 static int _q_test (sortable_t *values,
117 const sortable_t val,
118 const int lo, const int hi)
122 /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
125 if (EQUAL (val, values [lo])) {
132 if (COMPARE (val, values [lo])) {
137 if (COMPARE (values [hi], val)) {
144 if (EQUAL (val, values [mid])) {
148 if (COMPARE (val, values [mid])) {
149 return (_q_test (values, val, lo, mid));
151 return (_q_test (values, val, mid+1, hi));
158 static void _q_sort (sortable_t *values, const int lo, const int hi)
164 /* handle base case: */
170 if (COMPARE (values [hi], values [lo])) {
171 sortable_t tmp = values [lo];
172 values [lo] = values [hi];
184 while (p_lo <= p_hi) {
185 if (COMPARE (values [p_lo], pivot)) {
186 values [p_lo-1] = values [p_lo];
190 sortable_t tmp = values [p_lo];
192 values [p_lo] = values [p_hi];
199 values [p_lo-1] = pivot;
201 _q_sort (values, lo, p_lo-1);
202 _q_sort (values, p_lo, hi);
207 Little test harness for q_sort and friends.
209 static void test_qsort (const int n_runs, const int max_elems, const int incr)
214 fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
216 while (n_elems <= max_elems) {
220 for (i = 0; i < n_runs; i ++) {
221 sortable_t *list = gen_list (n_elems, NULL);
223 timing_t *timing = start_timing ();
224 q_sort (list, n_elems);
225 total += end_timing (timing);
227 q_check (list, n_elems);
232 for (i = 0; i < n_runs; i ++) {
233 sortable_t *list = gen_list (n_elems, NULL);
235 timing_t *timing = start_timing ();
236 qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
237 qtotal += end_timing (timing);
239 q_check (list, n_elems);
244 fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
250 fprintf (stdout, "\n");
254 Little test harness for the qset implementation
256 static void test_qset (const int n_entries)
261 qset_t *q1 = qset_new (n_entries, NULL);
262 qset_t *q2 = qset_new (n_entries, NULL);
265 sortable_t *values = gen_list (n_entries, NULL);
267 for (i = 0; i < n_entries; i ++) {
268 qset_insert (q1, values [i]);
269 qset_insert (q2, values [i]);
272 fprintf (stdout, "q1: \t\t");
273 qset_print (q1, stdout);
278 q2->is_sorted = FALSE;
281 fprintf (stdout, "q1 (sorted):\t");
282 qset_print (q1, stdout);
284 assert (qset_compare (q1, q2));
286 q = qset_union (q1, q2);
287 fprintf (stdout, "qq (union):\t");
288 qset_print (q, stdout);
294 fprintf (stdout, "q1.size = %i\n", n1);
295 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
296 fprintf (stdout, "q2.size = %i\n", n2);
297 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
298 fprintf (stdout, "q.size = %i\n", n);
299 fprintf (stdout, "q.slots = %i\n", q->n_slots);
304 assert (qset_compare (q1, q2));
305 assert (qset_compare (q2, q));
306 assert (qset_compare (q, q1));
308 for (i = 0; i < n_entries; i ++) {
309 assert (qset_contains (q1, values [i]));
310 assert (qset_contains (q2, values [i]));
311 assert (qset_contains (q, values [i]));
317 fprintf (stdout, "q1.size = %i\n", n1);
318 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
319 fprintf (stdout, "q2.size = %i\n", n2);
320 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
321 fprintf (stdout, "q.size = %i\n", n);
322 fprintf (stdout, "q.slots = %i\n", q->n_slots);
324 assert (qset_compare (q1, q2));
325 assert (qset_compare (q2, q));
326 assert (qset_compare (q, q1));
328 for (i = 0; i < n_entries; i ++) {
329 assert (qset_contains (q1, values [i]));
330 assert (qset_contains (q2, values [i]));
331 assert (qset_contains (q, values [i]));
338 # endif /* defned UNSINN */
340 /* PRIVATE QSET IMPLEMENTATION */
342 Resize a qset to (at least) the given size.
344 static void qset_resize (qset_t *qset, const int n_slots)
347 sortable_t *values = NULL;
349 if (qset->n_slots >= n_slots) {
353 new_size = qset->n_slots;
355 while (new_size < n_slots) {
359 values = alloc_list (new_size, qset->obst);
361 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
362 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
364 if (NULL == qset->obst) {
368 qset->values = values;
369 qset->n_slots = new_size;
373 Print a list of sortables.
375 static void q_print (sortable_t *values, const int n_values, FILE *stream)
379 fprintf (stream, "{");
381 for (i = 0; i < n_values; i ++) {
382 if (0 == values [i]) {
383 fprintf (stream, "_");
385 fprintf (stream, "0x08%x", (int) values [i]);
388 if (i + 1 != n_values) {
389 fprintf (stream, ", ");
393 fprintf (stream, "}\n");
398 Check whether the given list of sortables is sorted.
400 static void q_check (sortable_t *values, const int n_values)
404 for (i = 1; i < n_values; i ++) {
405 assert (COMPARE (values [i-1], values [i]) ||
406 EQUAL (values [i-1], values [i]));
409 for (i = 1; i < n_values; i ++) {
410 assert (-1 != q_test (values, values [i], n_values));
413 # endif /* defined UNSINN */
416 Test whether the given val is among values. Return the lowest index of val
419 static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
421 int idx = _q_test (values, val, 0, n_elems-1);
423 while ((0 <= idx-1) && EQUAL (values [idx], val)) {
431 Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
433 static void q_sort (sortable_t *values, const int n_elems)
435 _q_sort (values, 0, n_elems-1);
438 /* PUBLIC INTERFACE */
441 Allocate a new qset with initial space for up to n_elems.
442 If a non-NULL obstack is given, it is used for all allocations of this qset
443 and must be initialised and deleted by the user of the qset.
445 qset_t *qset_new (const int n_elems, struct obstack *obst)
447 qset_t *qset = (qset_t*) mix_malloc (obst, sizeof (qset_t));
450 qset->values = alloc_list (n_elems, obst);
451 memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
453 qset->n_slots = n_elems;
455 qset->is_sorted = FALSE;
456 qset->id = qset_id ++;
462 Sort the entries of the given qset.
464 void qset_sort (qset_t *qset)
469 if (qset->is_sorted) {
473 q_sort (qset->values, qset->n_elems);
475 for (i = 1; i < qset->n_elems; i ++) {
476 if (! EQUAL (qset->values [i], qset->values [occ])) {
477 qset->values [++ occ] = qset->values [i];
484 if (qset->n_elems != occ) {
485 fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
490 qset->is_sorted = TRUE;
494 Compact a qset to take up no more space than required.
496 void qset_compact (qset_t *qset)
498 if (NULL == qset->obst) {
499 sortable_t *values = (sortable_t*) mix_malloc (qset->obst,
500 qset->n_elems * sizeof (sortable_t));
501 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
503 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
507 qset->values = values;
508 qset->n_slots = qset->n_elems;
513 Free the memory associated with the given qset
515 void qset_delete (qset_t *qset)
517 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
519 if (NULL == qset->obst) {
523 memset (qset, 0x00, sizeof (qset_t));
525 if (NULL == qset->obst) {
531 Test whether the given qset contains the given value.
533 int qset_contains (qset_t *qset, sortable_t val)
537 return (-1 != q_test (qset->values, val, qset->n_elems));
541 Delete the given value from the given qset (if it exists)
543 void qset_remove (qset_t *qset, sortable_t val)
551 idx = q_test (qset->values, val, qset->n_elems);
557 while (EQUAL (qset->values [idx + occ], val)) {
561 for (i = idx; i < qset->n_elems - occ; i ++) {
562 qset->values [i] = qset->values [i+occ];
565 qset->n_elems -= occ;
569 Insert the given elem into the given qset; return nonzero iff any
570 involved values change.
572 int qset_insert (qset_t *qset, sortable_t val)
575 const int n_elems = qset->n_elems;
577 /* todo: sort, find */
580 for (i = 0; i < n_elems; i ++) {
581 if (EQUAL (val, qset->values [i])) {
586 qset_resize (qset, qset->n_elems+1);
588 /* qset_print (qset, stdout); */
589 /* fprintf (stdout, "%s: must insert 0x%08x\n", __FUNCTION__, (void*) val); */
591 qset->values [qset->n_elems++] = val;
592 qset->is_sorted = FALSE;
598 Insert all elems of qset2 into qset1; return nonzero iff any
599 involved values change. qset2 is *not* deleted.
601 int qset_insert_all (qset_t *qset1, qset_t *qset2)
604 sortable_t val = qset_start (qset2);
607 change |= qset_insert (qset1, val);
609 val = qset_next (qset2);
620 int qset_compare (qset_t *qset1, qset_t *qset2)
623 const int n_elems = qset1->n_elems;
628 if (qset1->n_elems != qset2->n_elems) {
632 for (i = 0; i < n_elems; i ++) {
633 if (qset1->values [i] != qset2->values [i]) {
642 Returns the union of two qsets.
644 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
646 qset_t *qset = (qset_t*) mix_malloc (qset1->obst, sizeof (qset_t));
647 const int n_elems = qset1->n_elems + qset2->n_elems;
649 qset->values = alloc_list (n_elems, qset1->obst);
651 memcpy (qset->values, qset1->values,
652 qset1->n_elems * sizeof (sortable_t));
654 memcpy (qset->values+qset1->n_elems,
655 qset2->values, qset2->n_elems * sizeof (sortable_t));
657 qset->obst = qset1->obst;
658 qset->n_elems = n_elems;
659 qset->n_slots = qset->n_elems;
667 Report the size of the given qset.
669 int qset_size (qset_t *qset)
671 return (qset->n_elems);
675 Print the given qset to the given stream.
677 void qset_print (qset_t *qset, FILE *stream)
679 q_print (qset->values, qset->n_elems, stream);
683 Check wether the given qset is empty
685 int qset_is_empty (qset_t *qset)
687 return (0 == qset->n_elems);
691 Initialise a new iteration over a qset
693 sortable_t *qset_start (qset_t *qset)
699 start = qset_next (qset);
701 return (start); /* works for empty sets, too */
705 Step to the next element
707 sortable_t *qset_next (qset_t *qset)
709 if (qset->n_elems == qset->cursor) {
713 /* quick fix to skip NULL entries */
714 while ((qset->cursor < qset->n_elems) &&
715 (NULL == qset->values [qset->cursor])) {
719 return (qset->values [qset->cursor++]);
724 int qset_test_main (int argc, char **argv)
729 if (-1 == gettimeofday (&tp, NULL)) {
730 perror ("gettimeofday");
734 seed = (unsigned int) tp.tv_usec;
737 /* test_qsort (20, 1000000, 100000); */
739 test_qset (atoi (argv [1]));
743 # endif /* defined UNSINN */
747 Revision 1.12 2006/06/06 12:06:27 beck
748 use xmalloc instead of malloc
750 Revision 1.11 2005/06/22 09:34:11 beck
753 Revision 1.10 2004/12/21 15:37:31 beck
754 added config.h include
755 removed unused sys/times.h
756 removed C99 constructs
758 Revision 1.9 2004/12/20 17:34:35 liekweg
759 fix recursion handling
761 Revision 1.8 2004/12/06 12:49:26 liekweg
764 Revision 1.7 2004/11/30 14:47:11 liekweg
765 insert report changes
767 Revision 1.6 2004/11/26 15:58:30 liekweg
768 don't free inside obstacks (thx, michael)
770 Revision 1.5 2004/11/24 14:53:56 liekweg
773 Revision 1.4 2004/11/18 16:35:45 liekweg
774 Added unique ids for debugging
776 Revision 1.3 2004/11/09 16:45:36 liekweg
779 Revision 1.2 2004/11/08 12:32:00 liekweg
780 Moved q_* methods into private section
782 Revision 1.1 2004/11/04 14:55:13 liekweg