4 * Time-stamp: <01.11.2004 19:45:58h 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>
25 static __inline__ int sortable_compare (const void *pa, const void *pb)
27 const int a = * (unsigned int*) pa;
28 const int b = * (unsigned int*) pb;
34 return ((a < b) ? -1 : +1);
38 Allocate a list of sortables of the given length.
40 static sortable_t *alloc_list (const int len)
42 sortable_t *values = (sortable_t*) malloc (len * sizeof (sortable_t));
44 memset (values, 0x00, len * sizeof (sortable_t));
51 Create a list of sortables of the given length.
53 static sortable_t *gen_list (const int len)
56 sortable_t *values = alloc_list (len);
58 for (i = 0; i < len; i ++) {
59 values [i] = rand () >> 16;
64 # endif /* defined UNSINN */
67 Helper to q_test --- return the index of val in values, or -1
69 static int _q_test (sortable_t *values,
71 const int lo, const int hi)
75 /* fprintf (stdout, "%s for %d [%i:%i]\n", __FUNCTION__, val, lo, hi); */
78 if (EQUAL (val, values [lo])) {
85 if (COMPARE (val, values [lo])) {
90 if (COMPARE (values [hi], val)) {
97 if (EQUAL (val, values [mid])) {
101 if (COMPARE (val, values [mid])) {
102 return (_q_test (values, val, lo, mid));
104 return (_q_test (values, val, mid+1, hi));
111 static void _q_sort (sortable_t *values, const int lo, const int hi)
117 /* handle base case: */
123 if (COMPARE (values [hi], values [lo])) {
124 sortable_t tmp = values [lo];
125 values [lo] = values [hi];
137 while (p_lo <= p_hi) {
138 if (COMPARE (values [p_lo], pivot)) {
139 values [p_lo-1] = values [p_lo];
143 sortable_t tmp = values [p_lo];
145 values [p_lo] = values [p_hi];
152 values [p_lo-1] = pivot;
154 _q_sort (values, lo, p_lo-1);
155 _q_sort (values, p_lo, hi);
160 Little test harness for q_sort and friends.
162 static void test_qsort (const int n_runs, const int max_elems, const int incr)
167 fprintf (stdout, "# n_elems: q_sort time : libc qsort time\n");
169 while (n_elems <= max_elems) {
173 for (i = 0; i < n_runs; i ++) {
174 sortable_t *list = gen_list (n_elems);
176 timing_t *timing = start_timing ();
177 q_sort (list, n_elems);
178 total += end_timing (timing);
180 q_check (list, n_elems);
185 for (i = 0; i < n_runs; i ++) {
186 sortable_t *list = gen_list (n_elems);
188 timing_t *timing = start_timing ();
189 qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
190 qtotal += end_timing (timing);
192 q_check (list, n_elems);
197 fprintf (stdout, "%d %d %d\n", n_elems, total/n_runs, qtotal/n_runs);
203 fprintf (stdout, "\n");
207 Little test harness for the qset implementation
209 static void test_qset (const int n_entries)
214 qset_t *q1 = qset_new (n_entries);
215 qset_t *q2 = qset_new (n_entries);
218 sortable_t *values = gen_list (n_entries);
220 for (i = 0; i < n_entries; i ++) {
221 qset_insert (q1, values [i]);
222 qset_insert (q2, values [i]);
225 fprintf (stdout, "q1: \t\t");
226 qset_print (q1, stdout);
231 q2->is_sorted = FALSE;
234 fprintf (stdout, "q1 (sorted):\t");
235 qset_print (q1, stdout);
237 assert (qset_compare (q1, q2));
239 q = qset_union (q1, q2);
240 fprintf (stdout, "qq (union):\t");
241 qset_print (q, stdout);
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);
257 assert (qset_compare (q1, q2));
258 assert (qset_compare (q2, q));
259 assert (qset_compare (q, q1));
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]));
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);
277 assert (qset_compare (q1, q2));
278 assert (qset_compare (q2, q));
279 assert (qset_compare (q, q1));
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]));
291 # endif /* defned UNSINN */
293 /* PRIVATE QSET IMPLEMENTATION */
295 Resize a qset to (at least) the given size.
297 static void qset_resize (qset_t *qset, const int n_slots)
300 sortable_t *values = NULL;
302 if (qset->n_slots >= n_slots) {
306 new_size = qset->n_slots;
308 while (new_size < n_slots) {
312 values = alloc_list (new_size);
314 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
315 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
318 qset->values = values;
319 qset->n_slots = new_size;
322 /* PUBLIC INTERFACE */
325 Print a list of sortables.
327 void q_print (sortable_t *values, const int n_values, FILE *stream)
331 fprintf (stream, "{");
333 for (i = 0; i < n_values; i ++) {
334 if (0 == values [i]) {
335 fprintf (stream, "_");
337 fprintf (stream, "%d", (int) values [i]);
340 if (i + 1 != n_values) {
341 fprintf (stream, ", ");
345 fprintf (stream, "}\n");
349 Check whether the given list of sortables is sorted.
351 void q_check (sortable_t *values, const int n_values)
355 for (i = 1; i < n_values; i ++) {
356 assert (COMPARE (values [i-1], values [i]) ||
357 EQUAL (values [i-1], values [i]));
360 for (i = 1; i < n_values; i ++) {
361 assert (-1 != q_test (values, values [i], n_values));
366 Test whether the given val is among values. Return the lowest index of val
369 int q_test (sortable_t *values, const sortable_t val, const int n_elems)
371 int idx = _q_test (values, val, 0, n_elems-1);
373 while ((0 <= idx-1) && EQUAL (values [idx], val)) {
381 Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
383 void q_sort (sortable_t *values, const int n_elems)
385 _q_sort (values, 0, n_elems-1);
389 Merge two sorted lists. Keep duplicates (if present)
391 sortable_t *q_merge (sortable_t *list1, const int n1_elems,
392 sortable_t *list2, const int n2_elems)
394 const int n_elems = n1_elems + n2_elems;
395 sortable_t *res = alloc_list (n_elems);
401 while ((i < n_elems) && (i1 < n1_elems) && (i2 < n2_elems)) {
402 if (COMPARE (list1 [i1], list2 [i2])) {
403 res [i ++] = list1 [i1 ++];
405 res [i ++] = list2 [i2 ++];
409 while (i1 < n1_elems) {
410 res [i ++] = list1 [i1 ++];
413 while (i2 < n2_elems) {
414 res [i ++] = list2 [i2 ++];
421 Allocate a new qset with initial space for up to n_elems.
423 qset_t *qset_new (const int n_elems)
425 qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
427 qset->values = alloc_list (n_elems);
428 memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
430 qset->n_slots = n_elems;
432 qset->is_sorted = FALSE;
438 Sort the entries of the given qset.
440 void qset_sort (qset_t *qset)
445 if (qset->is_sorted) {
449 q_sort (qset->values, qset->n_elems);
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];
460 if (qset->n_elems != occ) {
461 fprintf (stdout, "removed %i duplicates\n", qset->n_elems - occ);
466 qset->is_sorted = TRUE;
470 Compact a qset to take up no more space than required.
472 void qset_compact (qset_t *qset)
474 sortable_t *values = (sortable_t*) malloc (qset->n_elems * sizeof (sortable_t));
475 memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
477 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
480 qset->values = values;
481 qset->n_slots = qset->n_elems;
485 Free the memory associated with the given qset
487 void qset_delete (qset_t *qset)
489 memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
492 memset (qset, 0x00, sizeof (qset_t));
498 Test wether the given qset contains the given value.
500 int qset_contains (qset_t *qset, sortable_t val)
504 return (-1 != q_test (qset->values, val, qset->n_elems));
508 Delete the given value from the given qset (if it exists)
510 void qset_remove (qset_t *qset, sortable_t val)
518 idx = q_test (qset->values, val, qset->n_elems);
524 while (EQUAL (qset->values [idx + occ], val)) {
528 for (i = idx; i < qset->n_elems - occ; i ++) {
529 qset->values [i] = qset->values [i+occ];
532 qset->n_elems -= occ;
536 Insert the given elem into the given qset.
538 void qset_insert (qset_t *qset, sortable_t val)
540 /* TODO: sort, find */
541 /* or check for duplicates */
542 qset_resize (qset, qset->n_elems+1);
544 qset->values [qset->n_elems++] = val;
545 qset->is_sorted = FALSE;
549 Insert all elems of qset2 into qset1. qset2 is *not* deleted.
551 void qset_insert_all (qset_t *qset1, qset_t *qset2)
553 sortable_t *values = qset1->values;
554 const int n_elems = qset1->n_slots;
559 qset1->values = q_merge (qset1->values, qset1->n_elems,
560 qset2->values, qset2->n_elems);
562 qset1->n_elems = qset1->n_elems + qset2->n_elems;
563 qset1->n_slots = qset1->n_elems;
567 memset (values, 0x00, n_elems * sizeof (sortable_t));
574 int qset_compare (qset_t *qset1, qset_t *qset2)
577 const int n_elems = qset1->n_elems;
582 if (qset1->n_elems != qset2->n_elems) {
586 for (i = 0; i < n_elems; i ++) {
587 if (qset1->values [i] != qset2->values [i]) {
596 Returns the union of two qsets.
598 qset_t *qset_union (qset_t *qset1, qset_t *qset2)
600 qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
601 const int n_elems = qset1->n_elems + qset2->n_elems;
603 qset->values = alloc_list (n_elems);
605 memcpy (qset->values, qset1->values,
606 qset1->n_elems * sizeof (sortable_t));
608 memcpy (qset->values+qset1->n_elems,
609 qset2->values, qset2->n_elems * sizeof (sortable_t));
611 qset->n_elems = n_elems;
612 qset->n_slots = qset->n_elems;
620 Report the size of the given qset.
622 int qset_size (qset_t *qset)
624 return (qset->n_elems);
628 Print the given qset to the given stream.
630 void qset_print (qset_t *qset, FILE *stream)
632 q_print (qset->values, qset->n_elems, stream);
636 Initialise a new iteration over a qset
638 sortable_t *qset_start (qset_t *qset)
642 return (qset_next (qset)); /* works for empty sets, too */
646 Step to the next element
648 sortable_t *qset_next (qset_t *qset)
650 if (qset->n_elems == qset->cursor) {
654 return (qset->values [qset->cursor++]);
659 int qset_test_main (int argc, char **argv)
664 if (-1 == gettimeofday (&tp, NULL)) {
665 perror ("gettimeofday");
669 seed = (unsigned int) tp.tv_usec;
672 /* test_qsort (20, 1000000, 100000); */
674 test_qset (atoi (argv [1]));
678 # endif /* defined UNSINN */
682 Revision 1.1 2004/11/04 14:55:13 liekweg