4 * Time-stamp: <17.12.2004 20:26:51h 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.
34 /* Check whether the given list of sortables is sorted. */
35 static void q_check (sortable_t*, const int);
36 # endif /* defined UNSINN */
38 /* Test whether the given val is among values. Return the index of
39 val in values, or -1. */
40 static int q_test (sortable_t*, const sortable_t, const int);
42 /* Sort n_elems entries in 'values' */
43 static void q_sort (sortable_t*, const int);
45 /* Compare funktion, meant to be qsort(3)-compatible */
46 static INLINE int sortable_compare (const void *pa, const void *pb)
48 const int a = * (unsigned int*) pa;
49 const int b = * (unsigned int*) pb;
55 return ((a < b) ? -1 : +1);
59 Wrapper for mixed allocation
61 static void *mix_malloc (struct obstack *obst, size_t size)
64 return (obstack_alloc (obst, size));
66 return (malloc (size));
71 Allocate a list of sortables of the given length.
73 static sortable_t *alloc_list (const int len, struct obstack *obst)
75 sortable_t *values = (sortable_t*) mix_malloc (obst, len * sizeof (sortable_t));
77 memset (values, 0x00, len * sizeof (sortable_t));
84 Create a list of sortables of the given length.
86 static sortable_t *gen_list (const int len, struct obstack *obst)
89 sortable_t *values = alloc_list (len, obst);
91 for (i = 0; i < len; i ++) {
92 values [i] = rand () >> 16;
97 # endif /* defined UNSINN */
100 Helper to q_test --- return the index of val in values, or -1
102 static int _q_test (sortable_t *values,
103 const sortable_t val,
104 const int lo, const int hi)
108 /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
111 if (EQUAL (val, values [lo])) {
118 if (COMPARE (val, values [lo])) {
123 if (COMPARE (values [hi], val)) {
130 if (EQUAL (val, values [mid])) {
134 if (COMPARE (val, values [mid])) {
135 return (_q_test (values, val, lo, mid));
137 return (_q_test (values, val, mid+1, hi));
144 static void _q_sort (sortable_t *values, const int lo, const int hi)
150 /* handle base case: */
156 if (COMPARE (values [hi], values [lo])) {
157 sortable_t tmp = values [lo];
158 values [lo] = values [hi];
170 while (p_lo <= p_hi) {
171 if (COMPARE (values [p_lo], pivot)) {
172 values [p_lo-1] = values [p_lo];
176 sortable_t tmp = values [p_lo];
178 values [p_lo] = values [p_hi];
185 values [p_lo-1] = pivot;
187 _q_sort (values, lo, p_lo-1);
188 _q_sort (values, p_lo, hi);
193 Little test harness for q_sort and friends.
195 static void test_qsort (const int n_runs, const int max_elems, const int incr)
200 fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
202 while (n_elems <= max_elems) {
206 for (i = 0; i < n_runs; i ++) {
207 sortable_t *list = gen_list (n_elems, NULL);
209 timing_t *timing = start_timing ();
210 q_sort (list, n_elems);
211 total += end_timing (timing);
213 q_check (list, n_elems);
218 for (i = 0; i < n_runs; i ++) {
219 sortable_t *list = gen_list (n_elems, NULL);
221 timing_t *timing = start_timing ();
222 qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
223 qtotal += end_timing (timing);
225 q_check (list, n_elems);
230 fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
236 fprintf (stdout, "\n");
240 Little test harness for the qset implementation
242 static void test_qset (const int n_entries)
247 qset_t *q1 = qset_new (n_entries, NULL);
248 qset_t *q2 = qset_new (n_entries, NULL);
251 sortable_t *values = gen_list (n_entries, NULL);
253 for (i = 0; i < n_entries; i ++) {
254 qset_insert (q1, values [i]);
255 qset_insert (q2, values [i]);
258 fprintf (stdout, "q1: \t\t");
259 qset_print (q1, stdout);
264 q2->is_sorted = FALSE;
267 fprintf (stdout, "q1 (sorted):\t");
268 qset_print (q1, stdout);
270 assert (qset_compare (q1, q2));
272 q = qset_union (q1, q2);
273 fprintf (stdout, "qq (union):\t");
274 qset_print (q, stdout);
280 fprintf (stdout, "q1.size = %i\n", n1);
281 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
282 fprintf (stdout, "q2.size = %i\n", n2);
283 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
284 fprintf (stdout, "q.size = %i\n", n);
285 fprintf (stdout, "q.slots = %i\n", q->n_slots);
290 assert (qset_compare (q1, q2));
291 assert (qset_compare (q2, q));
292 assert (qset_compare (q, q1));
294 for (i = 0; i < n_entries; i ++) {
295 assert (qset_contains (q1, values [i]));
296 assert (qset_contains (q2, values [i]));
297 assert (qset_contains (q, values [i]));
303 fprintf (stdout, "q1.size = %i\n", n1);
304 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
305 fprintf (stdout, "q2.size = %i\n", n2);
306 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
307 fprintf (stdout, "q.size = %i\n", n);
308 fprintf (stdout, "q.slots = %i\n", q->n_slots);
310 assert (qset_compare (q1, q2));
311 assert (qset_compare (q2, q));
312 assert (qset_compare (q, q1));
314 for (i = 0; i < n_entries; i ++) {
315 assert (qset_contains (q1, values [i]));
316 assert (qset_contains (q2, values [i]));
317 assert (qset_contains (q, values [i]));
324 # endif /* defned UNSINN */
326 /* PRIVATE QSET IMPLEMENTATION */
328 Resize a qset to (at least) the given size.
330 static void qset_resize (qset_t *qset, const int n_slots)
333 sortable_t *values = NULL;
335 if (qset->n_slots >= n_slots) {
339 new_size = qset->n_slots;
341 while (new_size < n_slots) {
345 values = alloc_list (new_size, qset->obst);
347 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
348 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
350 if (NULL == qset->obst) {
354 qset->values = values;
355 qset->n_slots = new_size;
359 Print a list of sortables.
361 static void q_print (sortable_t *values, const int n_values, FILE *stream)
365 fprintf (stream, "{");
367 for (i = 0; i < n_values; i ++) {
368 if (0 == values [i]) {
369 fprintf (stream, "_");
371 fprintf (stream, "0x08%x", (int) values [i]);
374 if (i + 1 != n_values) {
375 fprintf (stream, ", ");
379 fprintf (stream, "}\n");
384 Check whether the given list of sortables is sorted.
386 static void q_check (sortable_t *values, const int n_values)
390 for (i = 1; i < n_values; i ++) {
391 assert (COMPARE (values [i-1], values [i]) ||
392 EQUAL (values [i-1], values [i]));
395 for (i = 1; i < n_values; i ++) {
396 assert (-1 != q_test (values, values [i], n_values));
399 # endif /* defined UNSINN */
402 Test whether the given val is among values. Return the lowest index of val
405 static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
407 int idx = _q_test (values, val, 0, n_elems-1);
409 while ((0 <= idx-1) && EQUAL (values [idx], val)) {
417 Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
419 static void q_sort (sortable_t *values, const int n_elems)
421 _q_sort (values, 0, n_elems-1);
424 /* PUBLIC INTERFACE */
427 Allocate a new qset with initial space for up to n_elems.
428 If a non-NULL obstack is given, it is used for all allocations of this qset
429 and must be initialised and deleted by the user of the qset.
431 qset_t *qset_new (const int n_elems, struct obstack *obst)
433 qset_t *qset = (qset_t*) mix_malloc (obst, sizeof (qset_t));
436 qset->values = alloc_list (n_elems, obst);
437 memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
439 qset->n_slots = n_elems;
441 qset->is_sorted = FALSE;
442 qset->id = qset_id ++;
448 Sort the entries of the given qset.
450 void qset_sort (qset_t *qset)
455 if (qset->is_sorted) {
459 q_sort (qset->values, qset->n_elems);
461 for (i = 1; i < qset->n_elems; i ++) {
462 if (! EQUAL (qset->values [i], qset->values [occ])) {
463 qset->values [++ occ] = qset->values [i];
470 if (qset->n_elems != occ) {
471 fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
476 qset->is_sorted = TRUE;
480 Compact a qset to take up no more space than required.
482 void qset_compact (qset_t *qset)
484 if (NULL == qset->obst) {
485 sortable_t *values = (sortable_t*) mix_malloc (qset->obst,
486 qset->n_elems * sizeof (sortable_t));
487 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
489 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
493 qset->values = values;
494 qset->n_slots = qset->n_elems;
499 Free the memory associated with the given qset
501 void qset_delete (qset_t *qset)
503 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
505 if (NULL == qset->obst) {
509 memset (qset, 0x00, sizeof (qset_t));
511 if (NULL == qset->obst) {
517 Test wether the given qset contains the given value.
519 int qset_contains (qset_t *qset, sortable_t val)
523 return (-1 != q_test (qset->values, val, qset->n_elems));
527 Delete the given value from the given qset (if it exists)
529 void qset_remove (qset_t *qset, sortable_t val)
537 idx = q_test (qset->values, val, qset->n_elems);
543 while (EQUAL (qset->values [idx + occ], val)) {
547 for (i = idx; i < qset->n_elems - occ; i ++) {
548 qset->values [i] = qset->values [i+occ];
551 qset->n_elems -= occ;
555 Insert the given elem into the given qset; return nonzero iff any
556 involved values change.
558 int qset_insert (qset_t *qset, sortable_t val)
561 const int n_elems = qset->n_elems;
563 /* todo: sort, find */
566 for (i = 0; i < n_elems; i ++) {
567 if (EQUAL (val, qset->values [i])) {
572 qset_resize (qset, qset->n_elems+1);
574 /* qset_print (qset, stdout); */
575 /* fprintf (stdout, "%s: must insert 0x%08x\n", __FUNCTION__, (void*) val); */
577 qset->values [qset->n_elems++] = val;
578 qset->is_sorted = FALSE;
584 Insert all elems of qset2 into qset1; return nonzero iff any
585 involved values change. qset2 is *not* deleted.
587 int qset_insert_all (qset_t *qset1, qset_t *qset2)
590 sortable_t val = qset_start (qset2);
593 change |= qset_insert (qset1, val);
595 val = qset_next (qset2);
606 int qset_compare (qset_t *qset1, qset_t *qset2)
609 const int n_elems = qset1->n_elems;
614 if (qset1->n_elems != qset2->n_elems) {
618 for (i = 0; i < n_elems; i ++) {
619 if (qset1->values [i] != qset2->values [i]) {
628 Returns the union of two qsets.
630 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
632 qset_t *qset = (qset_t*) mix_malloc (qset1->obst, sizeof (qset_t));
633 const int n_elems = qset1->n_elems + qset2->n_elems;
635 qset->values = alloc_list (n_elems, qset1->obst);
637 memcpy (qset->values, qset1->values,
638 qset1->n_elems * sizeof (sortable_t));
640 memcpy (qset->values+qset1->n_elems,
641 qset2->values, qset2->n_elems * sizeof (sortable_t));
643 qset->obst = qset1->obst;
644 qset->n_elems = n_elems;
645 qset->n_slots = qset->n_elems;
653 Report the size of the given qset.
655 int qset_size (qset_t *qset)
657 return (qset->n_elems);
661 Print the given qset to the given stream.
663 void qset_print (qset_t *qset, FILE *stream)
665 q_print (qset->values, qset->n_elems, stream);
669 Check wether the given qset is empty
671 int qset_is_empty (qset_t *qset)
673 return (0 == qset->n_elems);
677 Initialise a new iteration over a qset
679 sortable_t *qset_start (qset_t *qset)
685 start = qset_next (qset);
687 return (start); /* works for empty sets, too */
691 Step to the next element
693 sortable_t *qset_next (qset_t *qset)
695 if (qset->n_elems == qset->cursor) {
699 /* quick fix to skip NULL entries */
700 while ((qset->cursor < qset->n_elems) &&
701 (NULL == qset->values [qset->cursor])) {
705 return (qset->values [qset->cursor++]);
710 int qset_test_main (int argc, char **argv)
715 if (-1 == gettimeofday (&tp, NULL)) {
716 perror ("gettimeofday");
720 seed = (unsigned int) tp.tv_usec;
723 /* test_qsort (20, 1000000, 100000); */
725 test_qset (atoi (argv [1]));
729 # endif /* defined UNSINN */
733 Revision 1.10 2004/12/21 15:37:31 beck
734 added config.h include
735 removed unused sys/times.h
736 removed C99 constructs
738 Revision 1.9 2004/12/20 17:34:35 liekweg
739 fix recursion handling
741 Revision 1.8 2004/12/06 12:49:26 liekweg
744 Revision 1.7 2004/11/30 14:47:11 liekweg
745 insert report changes
747 Revision 1.6 2004/11/26 15:58:30 liekweg
748 don't free inside obstacks (thx, michael)
750 Revision 1.5 2004/11/24 14:53:56 liekweg
753 Revision 1.4 2004/11/18 16:35:45 liekweg
754 Added unique ids for debugging
756 Revision 1.3 2004/11/09 16:45:36 liekweg
759 Revision 1.2 2004/11/08 12:32:00 liekweg
760 Moved q_* methods into private section
762 Revision 1.1 2004/11/04 14:55:13 liekweg