4 * Time-stamp: <23.11.2004 13:26:21h liekweg>
6 * File name: ir/ana2/qset.c
7 * Purpose: yet another set implementation
10 * Created: Mon 18 Oct 2004
12 * Copyright: (c) 1999-2004 Universität Karlsruhe
13 * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
20 # include <sys/time.h>
32 /* Check whether the given list of sortables is sorted. */
33 static void q_check (sortable_t*, const int);
34 # endif /* defined UNSINN */
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);
40 /* Sort n_elems entries in 'values' */
41 static void q_sort (sortable_t*, const int);
43 /* Compare funktion, meant to be qsort(3)-compatible */
44 static __inline__ int sortable_compare (const void *pa, const void *pb)
46 const int a = * (unsigned int*) pa;
47 const int b = * (unsigned int*) pb;
53 return ((a < b) ? -1 : +1);
57 Wrapper for mixed allocation
59 static void *mix_malloc (struct obstack *obst, size_t size)
62 return (obstack_alloc (obst, size));
64 return (malloc (size));
69 Allocate a list of sortables of the given length.
71 static sortable_t *alloc_list (const int len, struct obstack *obst)
73 sortable_t *values = (sortable_t*) mix_malloc (obst, len * sizeof (sortable_t));
75 memset (values, 0x00, len * sizeof (sortable_t));
82 Create a list of sortables of the given length.
84 static sortable_t *gen_list (const int len, struct obstack *obst)
87 sortable_t *values = alloc_list (len, obst);
89 for (i = 0; i < len; i ++) {
90 values [i] = rand () >> 16;
95 # endif /* defined UNSINN */
98 Helper to q_test --- return the index of val in values, or -1
100 static int _q_test (sortable_t *values,
101 const sortable_t val,
102 const int lo, const int hi)
106 /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
109 if (EQUAL (val, values [lo])) {
116 if (COMPARE (val, values [lo])) {
121 if (COMPARE (values [hi], val)) {
128 if (EQUAL (val, values [mid])) {
132 if (COMPARE (val, values [mid])) {
133 return (_q_test (values, val, lo, mid));
135 return (_q_test (values, val, mid+1, hi));
142 static void _q_sort (sortable_t *values, const int lo, const int hi)
148 /* handle base case: */
154 if (COMPARE (values [hi], values [lo])) {
155 sortable_t tmp = values [lo];
156 values [lo] = values [hi];
168 while (p_lo <= p_hi) {
169 if (COMPARE (values [p_lo], pivot)) {
170 values [p_lo-1] = values [p_lo];
174 sortable_t tmp = values [p_lo];
176 values [p_lo] = values [p_hi];
183 values [p_lo-1] = pivot;
185 _q_sort (values, lo, p_lo-1);
186 _q_sort (values, p_lo, hi);
191 Little test harness for q_sort and friends.
193 static void test_qsort (const int n_runs, const int max_elems, const int incr)
198 fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
200 while (n_elems <= max_elems) {
204 for (i = 0; i < n_runs; i ++) {
205 sortable_t *list = gen_list (n_elems, NULL);
207 timing_t *timing = start_timing ();
208 q_sort (list, n_elems);
209 total += end_timing (timing);
211 q_check (list, n_elems);
216 for (i = 0; i < n_runs; i ++) {
217 sortable_t *list = gen_list (n_elems, NULL);
219 timing_t *timing = start_timing ();
220 qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
221 qtotal += end_timing (timing);
223 q_check (list, n_elems);
228 fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
234 fprintf (stdout, "\n");
238 Little test harness for the qset implementation
240 static void test_qset (const int n_entries)
245 qset_t *q1 = qset_new (n_entries, NULL);
246 qset_t *q2 = qset_new (n_entries, NULL);
249 sortable_t *values = gen_list (n_entries, NULL);
251 for (i = 0; i < n_entries; i ++) {
252 qset_insert (q1, values [i]);
253 qset_insert (q2, values [i]);
256 fprintf (stdout, "q1: \t\t");
257 qset_print (q1, stdout);
262 q2->is_sorted = FALSE;
265 fprintf (stdout, "q1 (sorted):\t");
266 qset_print (q1, stdout);
268 assert (qset_compare (q1, q2));
270 q = qset_union (q1, q2);
271 fprintf (stdout, "qq (union):\t");
272 qset_print (q, stdout);
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);
288 assert (qset_compare (q1, q2));
289 assert (qset_compare (q2, q));
290 assert (qset_compare (q, q1));
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]));
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);
308 assert (qset_compare (q1, q2));
309 assert (qset_compare (q2, q));
310 assert (qset_compare (q, q1));
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]));
322 # endif /* defned UNSINN */
324 /* PRIVATE QSET IMPLEMENTATION */
326 Resize a qset to (at least) the given size.
328 static void qset_resize (qset_t *qset, const int n_slots)
331 sortable_t *values = NULL;
333 if (qset->n_slots >= n_slots) {
337 new_size = qset->n_slots;
339 while (new_size < n_slots) {
343 values = alloc_list (new_size, qset->obst);
345 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
346 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
349 qset->values = values;
350 qset->n_slots = new_size;
354 Print a list of sortables.
356 static void q_print (sortable_t *values, const int n_values, FILE *stream)
360 fprintf (stream, "{");
362 for (i = 0; i < n_values; i ++) {
363 if (0 == values [i]) {
364 fprintf (stream, "_");
366 fprintf (stream, "0x08%x", (int) values [i]);
369 if (i + 1 != n_values) {
370 fprintf (stream, ", ");
374 fprintf (stream, "}\n");
379 Check whether the given list of sortables is sorted.
381 static void q_check (sortable_t *values, const int n_values)
385 for (i = 1; i < n_values; i ++) {
386 assert (COMPARE (values [i-1], values [i]) ||
387 EQUAL (values [i-1], values [i]));
390 for (i = 1; i < n_values; i ++) {
391 assert (-1 != q_test (values, values [i], n_values));
394 # endif /* defined UNSINN */
397 Test whether the given val is among values. Return the lowest index of val
400 static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
402 int idx = _q_test (values, val, 0, n_elems-1);
404 while ((0 <= idx-1) && EQUAL (values [idx], val)) {
412 Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
414 static void q_sort (sortable_t *values, const int n_elems)
416 _q_sort (values, 0, n_elems-1);
420 Merge two sorted lists. Keep duplicates (if present)
422 static sortable_t *q_merge (sortable_t *list1, const int n1_elems,
423 sortable_t *list2, const int n2_elems,
424 struct obstack *obst)
426 const int n_elems = n1_elems + n2_elems;
427 sortable_t *res = alloc_list (n_elems, obst);
433 while ((i < n_elems) && (i1 < n1_elems) && (i2 < n2_elems)) {
434 if (COMPARE (list1 [i1], list2 [i2])) {
435 res [i ++] = list1 [i1 ++];
437 res [i ++] = list2 [i2 ++];
441 while (i1 < n1_elems) {
442 res [i ++] = list1 [i1 ++];
445 while (i2 < n2_elems) {
446 res [i ++] = list2 [i2 ++];
452 /* PUBLIC INTERFACE */
455 Allocate a new qset with initial space for up to n_elems.
456 If a non-NULL obstack is given, it is used for all allocations of this qset
457 and must be initialised and deleted by the user of the qset.
459 qset_t *qset_new (const int n_elems, struct obstack *obst)
461 qset_t *qset = (qset_t*) mix_malloc (obst, sizeof (qset_t));
464 qset->values = alloc_list (n_elems, obst);
465 memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
467 qset->n_slots = n_elems;
469 qset->is_sorted = FALSE;
470 qset->id = qset_id ++;
476 Sort the entries of the given qset.
478 void qset_sort (qset_t *qset)
483 if (qset->is_sorted) {
487 q_sort (qset->values, qset->n_elems);
489 for (i = 1; i < qset->n_elems; i ++) {
490 if (! EQUAL (qset->values [i], qset->values [occ])) {
491 qset->values [++ occ] = qset->values [i];
498 if (qset->n_elems != occ) {
499 fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
504 qset->is_sorted = TRUE;
508 Compact a qset to take up no more space than required.
510 void qset_compact (qset_t *qset)
512 sortable_t *values = (sortable_t*) mix_malloc (qset->obst,
513 qset->n_elems * sizeof (sortable_t));
514 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
516 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
519 qset->values = values;
520 qset->n_slots = qset->n_elems;
524 Free the memory associated with the given qset
526 void qset_delete (qset_t *qset)
528 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
530 if (NULL == qset->obst) {
534 memset (qset, 0x00, sizeof (qset_t));
536 if (NULL == qset->obst) {
542 Test wether the given qset contains the given value.
544 int qset_contains (qset_t *qset, sortable_t val)
548 return (-1 != q_test (qset->values, val, qset->n_elems));
552 Delete the given value from the given qset (if it exists)
554 void qset_remove (qset_t *qset, sortable_t val)
562 idx = q_test (qset->values, val, qset->n_elems);
568 while (EQUAL (qset->values [idx + occ], val)) {
572 for (i = idx; i < qset->n_elems - occ; i ++) {
573 qset->values [i] = qset->values [i+occ];
576 qset->n_elems -= occ;
580 Insert the given elem into the given qset.
582 void qset_insert (qset_t *qset, sortable_t val)
585 const int n_elems = qset->n_elems;
587 /* todo: sort, find */
590 for (i = 0; i < n_elems; i ++) {
591 if (EQUAL (val, qset->values [i])) {
596 qset_resize (qset, qset->n_elems+1);
598 qset->values [qset->n_elems++] = val;
599 qset->is_sorted = FALSE;
603 Insert all elems of qset2 into qset1. qset2 is *not* deleted.
605 void qset_insert_all (qset_t *qset1, qset_t *qset2)
607 sortable_t *values = qset1->values;
608 const int n_elems = qset1->n_slots;
613 qset1->values = q_merge (qset1->values, qset1->n_elems,
614 qset2->values, qset2->n_elems,
617 qset1->n_elems = qset1->n_elems + qset2->n_elems;
618 qset1->n_slots = qset1->n_elems;
622 memset (values, 0x00, n_elems * sizeof (sortable_t));
629 int qset_compare (qset_t *qset1, qset_t *qset2)
632 const int n_elems = qset1->n_elems;
637 if (qset1->n_elems != qset2->n_elems) {
641 for (i = 0; i < n_elems; i ++) {
642 if (qset1->values [i] != qset2->values [i]) {
651 Returns the union of two qsets.
653 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
655 qset_t *qset = (qset_t*) mix_malloc (qset1->obst, sizeof (qset_t));
656 const int n_elems = qset1->n_elems + qset2->n_elems;
658 qset->values = alloc_list (n_elems, qset1->obst);
660 memcpy (qset->values, qset1->values,
661 qset1->n_elems * sizeof (sortable_t));
663 memcpy (qset->values+qset1->n_elems,
664 qset2->values, qset2->n_elems * sizeof (sortable_t));
666 qset->obst = qset1->obst;
667 qset->n_elems = n_elems;
668 qset->n_slots = qset->n_elems;
676 Report the size of the given qset.
678 int qset_size (qset_t *qset)
680 return (qset->n_elems);
684 Print the given qset to the given stream.
686 void qset_print (qset_t *qset, FILE *stream)
688 q_print (qset->values, qset->n_elems, stream);
692 Check wether the given qset is empty
694 int qset_is_empty (qset_t *qset)
696 return (0 == qset->n_elems);
700 Initialise a new iteration over a qset
702 sortable_t *qset_start (qset_t *qset)
706 return (qset_next (qset)); /* works for empty sets, too */
710 Step to the next element
712 sortable_t *qset_next (qset_t *qset)
714 if (qset->n_elems == qset->cursor) {
718 /* quick fix to skip NULL entries */
719 while ((qset->cursor < qset->n_elems) &&
720 (NULL == qset->values [qset->cursor])) {
724 return (qset->values [qset->cursor++]);
729 int qset_test_main (int argc, char **argv)
734 if (-1 == gettimeofday (&tp, NULL)) {
735 perror ("gettimeofday");
739 seed = (unsigned int) tp.tv_usec;
742 /* test_qsort (20, 1000000, 100000); */
744 test_qset (atoi (argv [1]));
748 # endif /* defined UNSINN */
752 Revision 1.5 2004/11/24 14:53:56 liekweg
755 Revision 1.4 2004/11/18 16:35:45 liekweg
756 Added unique ids for debugging
758 Revision 1.3 2004/11/09 16:45:36 liekweg
761 Revision 1.2 2004/11/08 12:32:00 liekweg
762 Moved q_* methods into private section
764 Revision 1.1 2004/11/04 14:55:13 liekweg