4 * Time-stamp: <11.11.2004 16:42:15h 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>
31 /* Check whether the given list of sortables is sorted. */
32 static void q_check (sortable_t*, const int);
33 # endif /* defined UNSINN */
35 /* Test whether the given val is among values. Return the index of
36 val in values, or -1. */
37 static int q_test (sortable_t*, const sortable_t, const int);
39 /* Sort n_elems entries in 'values' */
40 static void q_sort (sortable_t*, const int);
42 /* Compare funktion, meant to be qsort(3)-compatible */
43 static __inline__ int sortable_compare (const void *pa, const void *pb)
45 const int a = * (unsigned int*) pa;
46 const int b = * (unsigned int*) pb;
52 return ((a < b) ? -1 : +1);
56 Allocate a list of sortables of the given length.
58 static sortable_t *alloc_list (const int len)
60 sortable_t *values = (sortable_t*) malloc (len * sizeof (sortable_t));
62 memset (values, 0x00, len * sizeof (sortable_t));
69 Create a list of sortables of the given length.
71 static sortable_t *gen_list (const int len)
74 sortable_t *values = alloc_list (len);
76 for (i = 0; i < len; i ++) {
77 values [i] = rand () >> 16;
82 # endif /* defined UNSINN */
85 Helper to q_test --- return the index of val in values, or -1
87 static int _q_test (sortable_t *values,
89 const int lo, const int hi)
93 /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
96 if (EQUAL (val, values [lo])) {
103 if (COMPARE (val, values [lo])) {
108 if (COMPARE (values [hi], val)) {
115 if (EQUAL (val, values [mid])) {
119 if (COMPARE (val, values [mid])) {
120 return (_q_test (values, val, lo, mid));
122 return (_q_test (values, val, mid+1, hi));
129 static void _q_sort (sortable_t *values, const int lo, const int hi)
135 /* handle base case: */
141 if (COMPARE (values [hi], values [lo])) {
142 sortable_t tmp = values [lo];
143 values [lo] = values [hi];
155 while (p_lo <= p_hi) {
156 if (COMPARE (values [p_lo], pivot)) {
157 values [p_lo-1] = values [p_lo];
161 sortable_t tmp = values [p_lo];
163 values [p_lo] = values [p_hi];
170 values [p_lo-1] = pivot;
172 _q_sort (values, lo, p_lo-1);
173 _q_sort (values, p_lo, hi);
178 Little test harness for q_sort and friends.
180 static void test_qsort (const int n_runs, const int max_elems, const int incr)
185 fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
187 while (n_elems <= max_elems) {
191 for (i = 0; i < n_runs; i ++) {
192 sortable_t *list = gen_list (n_elems);
194 timing_t *timing = start_timing ();
195 q_sort (list, n_elems);
196 total += end_timing (timing);
198 q_check (list, n_elems);
203 for (i = 0; i < n_runs; i ++) {
204 sortable_t *list = gen_list (n_elems);
206 timing_t *timing = start_timing ();
207 qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
208 qtotal += end_timing (timing);
210 q_check (list, n_elems);
215 fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
221 fprintf (stdout, "\n");
225 Little test harness for the qset implementation
227 static void test_qset (const int n_entries)
232 qset_t *q1 = qset_new (n_entries);
233 qset_t *q2 = qset_new (n_entries);
236 sortable_t *values = gen_list (n_entries);
238 for (i = 0; i < n_entries; i ++) {
239 qset_insert (q1, values [i]);
240 qset_insert (q2, values [i]);
243 fprintf (stdout, "q1: \t\t");
244 qset_print (q1, stdout);
249 q2->is_sorted = FALSE;
252 fprintf (stdout, "q1 (sorted):\t");
253 qset_print (q1, stdout);
255 assert (qset_compare (q1, q2));
257 q = qset_union (q1, q2);
258 fprintf (stdout, "qq (union):\t");
259 qset_print (q, stdout);
265 fprintf (stdout, "q1.size = %i\n", n1);
266 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
267 fprintf (stdout, "q2.size = %i\n", n2);
268 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
269 fprintf (stdout, "q.size = %i\n", n);
270 fprintf (stdout, "q.slots = %i\n", q->n_slots);
275 assert (qset_compare (q1, q2));
276 assert (qset_compare (q2, q));
277 assert (qset_compare (q, q1));
279 for (i = 0; i < n_entries; i ++) {
280 assert (qset_contains (q1, values [i]));
281 assert (qset_contains (q2, values [i]));
282 assert (qset_contains (q, values [i]));
288 fprintf (stdout, "q1.size = %i\n", n1);
289 fprintf (stdout, "q1.slots = %i\n", q1->n_slots);
290 fprintf (stdout, "q2.size = %i\n", n2);
291 fprintf (stdout, "q2.slots = %i\n", q2->n_slots);
292 fprintf (stdout, "q.size = %i\n", n);
293 fprintf (stdout, "q.slots = %i\n", q->n_slots);
295 assert (qset_compare (q1, q2));
296 assert (qset_compare (q2, q));
297 assert (qset_compare (q, q1));
299 for (i = 0; i < n_entries; i ++) {
300 assert (qset_contains (q1, values [i]));
301 assert (qset_contains (q2, values [i]));
302 assert (qset_contains (q, values [i]));
309 # endif /* defned UNSINN */
311 /* PRIVATE QSET IMPLEMENTATION */
313 Resize a qset to (at least) the given size.
315 static void qset_resize (qset_t *qset, const int n_slots)
318 sortable_t *values = NULL;
320 if (qset->n_slots >= n_slots) {
324 new_size = qset->n_slots;
326 while (new_size < n_slots) {
330 values = alloc_list (new_size);
332 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
333 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
336 qset->values = values;
337 qset->n_slots = new_size;
341 Print a list of sortables.
343 static void q_print (sortable_t *values, const int n_values, FILE *stream)
347 fprintf (stream, "{");
349 for (i = 0; i < n_values; i ++) {
350 if (0 == values [i]) {
351 fprintf (stream, "_");
353 fprintf (stream, "0x08%x", (int) values [i]);
356 if (i + 1 != n_values) {
357 fprintf (stream, ", ");
361 fprintf (stream, "}\n");
366 Check whether the given list of sortables is sorted.
368 static void q_check (sortable_t *values, const int n_values)
372 for (i = 1; i < n_values; i ++) {
373 assert (COMPARE (values [i-1], values [i]) ||
374 EQUAL (values [i-1], values [i]));
377 for (i = 1; i < n_values; i ++) {
378 assert (-1 != q_test (values, values [i], n_values));
381 # endif /* defined UNSINN */
384 Test whether the given val is among values. Return the lowest index of val
387 static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
389 int idx = _q_test (values, val, 0, n_elems-1);
391 while ((0 <= idx-1) && EQUAL (values [idx], val)) {
399 Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
401 static void q_sort (sortable_t *values, const int n_elems)
403 _q_sort (values, 0, n_elems-1);
407 Merge two sorted lists. Keep duplicates (if present)
409 static sortable_t *q_merge (sortable_t *list1, const int n1_elems,
410 sortable_t *list2, const int n2_elems)
412 const int n_elems = n1_elems + n2_elems;
413 sortable_t *res = alloc_list (n_elems);
419 while ((i < n_elems) && (i1 < n1_elems) && (i2 < n2_elems)) {
420 if (COMPARE (list1 [i1], list2 [i2])) {
421 res [i ++] = list1 [i1 ++];
423 res [i ++] = list2 [i2 ++];
427 while (i1 < n1_elems) {
428 res [i ++] = list1 [i1 ++];
431 while (i2 < n2_elems) {
432 res [i ++] = list2 [i2 ++];
438 /* PUBLIC INTERFACE */
441 Allocate a new qset with initial space for up to n_elems.
443 qset_t *qset_new (const int n_elems)
445 qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
447 qset->values = alloc_list (n_elems);
448 memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
450 qset->n_slots = n_elems;
452 qset->is_sorted = FALSE;
453 qset->id = qset_id ++;
459 Sort the entries of the given qset.
461 void qset_sort (qset_t *qset)
466 if (qset->is_sorted) {
470 q_sort (qset->values, qset->n_elems);
472 for (i = 1; i < qset->n_elems; i ++) {
473 if (! EQUAL (qset->values [i], qset->values [occ])) {
474 qset->values [++ occ] = qset->values [i];
481 if (qset->n_elems != occ) {
482 fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
487 qset->is_sorted = TRUE;
491 Compact a qset to take up no more space than required.
493 void qset_compact (qset_t *qset)
495 sortable_t *values = (sortable_t*) malloc (qset->n_elems * sizeof (sortable_t));
496 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
498 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
501 qset->values = values;
502 qset->n_slots = qset->n_elems;
506 Free the memory associated with the given qset
508 void qset_delete (qset_t *qset)
510 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
513 memset (qset, 0x00, sizeof (qset_t));
519 Test wether the given qset contains the given value.
521 int qset_contains (qset_t *qset, sortable_t val)
525 return (-1 != q_test (qset->values, val, qset->n_elems));
529 Delete the given value from the given qset (if it exists)
531 void qset_remove (qset_t *qset, sortable_t val)
539 idx = q_test (qset->values, val, qset->n_elems);
545 while (EQUAL (qset->values [idx + occ], val)) {
549 for (i = idx; i < qset->n_elems - occ; i ++) {
550 qset->values [i] = qset->values [i+occ];
553 qset->n_elems -= occ;
557 Insert the given elem into the given qset.
559 void qset_insert (qset_t *qset, sortable_t val)
562 const int n_elems = qset->n_elems;
564 /* todo: sort, find */
567 for (i = 0; i < n_elems; i ++) {
568 if (EQUAL (val, qset->values [i])) {
573 qset_resize (qset, qset->n_elems+1);
575 qset->values [qset->n_elems++] = val;
576 qset->is_sorted = FALSE;
580 Insert all elems of qset2 into qset1. qset2 is *not* deleted.
582 void qset_insert_all (qset_t *qset1, qset_t *qset2)
584 sortable_t *values = qset1->values;
585 const int n_elems = qset1->n_slots;
590 qset1->values = q_merge (qset1->values, qset1->n_elems,
591 qset2->values, qset2->n_elems);
593 qset1->n_elems = qset1->n_elems + qset2->n_elems;
594 qset1->n_slots = qset1->n_elems;
598 memset (values, 0x00, n_elems * sizeof (sortable_t));
605 int qset_compare (qset_t *qset1, qset_t *qset2)
608 const int n_elems = qset1->n_elems;
613 if (qset1->n_elems != qset2->n_elems) {
617 for (i = 0; i < n_elems; i ++) {
618 if (qset1->values [i] != qset2->values [i]) {
627 Returns the union of two qsets.
629 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
631 qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
632 const int n_elems = qset1->n_elems + qset2->n_elems;
634 qset->values = alloc_list (n_elems);
636 memcpy (qset->values, qset1->values,
637 qset1->n_elems * sizeof (sortable_t));
639 memcpy (qset->values+qset1->n_elems,
640 qset2->values, qset2->n_elems * sizeof (sortable_t));
642 qset->n_elems = n_elems;
643 qset->n_slots = qset->n_elems;
651 Report the size of the given qset.
653 int qset_size (qset_t *qset)
655 return (qset->n_elems);
659 Print the given qset to the given stream.
661 void qset_print (qset_t *qset, FILE *stream)
663 q_print (qset->values, qset->n_elems, stream);
667 Check wether the given qset is empty
669 int qset_is_empty (qset_t *qset)
671 return (0 == qset->n_elems);
675 Initialise a new iteration over a qset
677 sortable_t *qset_start (qset_t *qset)
681 return (qset_next (qset)); /* works for empty sets, too */
685 Step to the next element
687 sortable_t *qset_next (qset_t *qset)
689 if (qset->n_elems == qset->cursor) {
693 /* quick fix to skip NULL entries */
694 while ((qset->cursor < qset->n_elems) &&
695 (NULL == qset->values [qset->cursor])) {
699 return (qset->values [qset->cursor++]);
704 int qset_test_main (int argc, char **argv)
709 if (-1 == gettimeofday (&tp, NULL)) {
710 perror ("gettimeofday");
714 seed = (unsigned int) tp.tv_usec;
717 /* test_qsort (20, 1000000, 100000); */
719 test_qset (atoi (argv [1]));
723 # endif /* defined UNSINN */
727 Revision 1.4 2004/11/18 16:35:45 liekweg
728 Added unique ids for debugging
730 Revision 1.3 2004/11/09 16:45:36 liekweg
733 Revision 1.2 2004/11/08 12:32:00 liekweg
734 Moved q_* methods into private section
736 Revision 1.1 2004/11/04 14:55:13 liekweg