X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana2%2Fqset.c;h=c21e355f3cffe6b1c238ce7177b38b6747980535;hb=c53a503e81f6e7c0995fbbcc451c2178ad9083bd;hp=8813512aee77a919765ba475b674b832b244a7fe;hpb=d07b7388a477ce7ce7ceb5fcf427b8db040ff55e;p=libfirm diff --git a/ir/ana2/qset.c b/ir/ana2/qset.c index 8813512ae..c21e355f3 100644 --- a/ir/ana2/qset.c +++ b/ir/ana2/qset.c @@ -1,7 +1,7 @@ /* -*- c -*- */ /* - * Time-stamp: <23.11.2004 13:26:21h liekweg> + * Time-stamp: <17.12.2004 20:26:51h liekweg> * Project: libFIRM * File name: ir/ana2/qset.c * Purpose: yet another set implementation @@ -12,14 +12,16 @@ * Copyright: (c) 1999-2004 Universität Karlsruhe * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE. */ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif # include # include # include # include -# include -# include +# include "obst.h" # include "timing.h" # include "qset.h" @@ -41,7 +43,7 @@ static int q_test (sortable_t*, const sortable_t, const int); static void q_sort (sortable_t*, const int); /* Compare funktion, meant to be qsort(3)-compatible */ -static __inline__ int sortable_compare (const void *pa, const void *pb) +static INLINE int sortable_compare (const void *pa, const void *pb) { const int a = * (unsigned int*) pa; const int b = * (unsigned int*) pb; @@ -344,7 +346,10 @@ static void qset_resize (qset_t *qset, const int n_slots) memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t)); memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */ - free (qset->values); + + if (NULL == qset->obst) { + free (qset->values); + } qset->values = values; qset->n_slots = new_size; @@ -416,39 +421,6 @@ static void q_sort (sortable_t *values, const int n_elems) _q_sort (values, 0, n_elems-1); } -/* - Merge two sorted lists. Keep duplicates (if present) -*/ -static sortable_t *q_merge (sortable_t *list1, const int n1_elems, - sortable_t *list2, const int n2_elems, - struct obstack *obst) -{ - const int n_elems = n1_elems + n2_elems; - sortable_t *res = alloc_list (n_elems, obst); - - int i1 = 0; - int i2 = 0; - int i = 0; - - while ((i < n_elems) && (i1 < n1_elems) && (i2 < n2_elems)) { - if (COMPARE (list1 [i1], list2 [i2])) { - res [i ++] = list1 [i1 ++]; - } else { - res [i ++] = list2 [i2 ++]; - } - } - - while (i1 < n1_elems) { - res [i ++] = list1 [i1 ++]; - } - - while (i2 < n2_elems) { - res [i ++] = list2 [i2 ++]; - } - - return (res); -} - /* PUBLIC INTERFACE */ /* @@ -509,15 +481,18 @@ void qset_sort (qset_t *qset) */ void qset_compact (qset_t *qset) { - sortable_t *values = (sortable_t*) mix_malloc (qset->obst, - qset->n_elems * sizeof (sortable_t)); - memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t)); + if (NULL == qset->obst) { + sortable_t *values = (sortable_t*) mix_malloc (qset->obst, + qset->n_elems * sizeof (sortable_t)); + memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t)); - memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); - free (qset->values); + memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); - qset->values = values; - qset->n_slots = qset->n_elems; + free (qset->values); + + qset->values = values; + qset->n_slots = qset->n_elems; + } } /* @@ -539,7 +514,7 @@ void qset_delete (qset_t *qset) } /* - Test wether the given qset contains the given value. + Test whether the given qset contains the given value. */ int qset_contains (qset_t *qset, sortable_t val) { @@ -577,9 +552,10 @@ void qset_remove (qset_t *qset, sortable_t val) } /* - Insert the given elem into the given qset. + Insert the given elem into the given qset; return nonzero iff any + involved values change. */ -void qset_insert (qset_t *qset, sortable_t val) +int qset_insert (qset_t *qset, sortable_t val) { int i; const int n_elems = qset->n_elems; @@ -589,38 +565,39 @@ void qset_insert (qset_t *qset, sortable_t val) for (i = 0; i < n_elems; i ++) { if (EQUAL (val, qset->values [i])) { - return; + return (FALSE); } } qset_resize (qset, qset->n_elems+1); + /* qset_print (qset, stdout); */ + /* fprintf (stdout, "%s: must insert 0x%08x\n", __FUNCTION__, (void*) val); */ + qset->values [qset->n_elems++] = val; qset->is_sorted = FALSE; + + return (TRUE); } /* - Insert all elems of qset2 into qset1. qset2 is *not* deleted. + Insert all elems of qset2 into qset1; return nonzero iff any + involved values change. qset2 is *not* deleted. */ -void qset_insert_all (qset_t *qset1, qset_t *qset2) +int qset_insert_all (qset_t *qset1, qset_t *qset2) { - sortable_t *values = qset1->values; - const int n_elems = qset1->n_slots; + int change = FALSE; + sortable_t val = qset_start (qset2); - qset_sort (qset1); - qset_sort (qset2); + while (0 != val) { + change |= qset_insert (qset1, val); - qset1->values = q_merge (qset1->values, qset1->n_elems, - qset2->values, qset2->n_elems, - qset1->obst); - - qset1->n_elems = qset1->n_elems + qset2->n_elems; - qset1->n_slots = qset1->n_elems; + val = qset_next (qset2); + } qset_sort (qset1); - memset (values, 0x00, n_elems * sizeof (sortable_t)); - free (values); + return (change); } /* @@ -701,9 +678,13 @@ int qset_is_empty (qset_t *qset) */ sortable_t *qset_start (qset_t *qset) { + sortable_t *start; + qset->cursor = 0; - return (qset_next (qset)); /* works for empty sets, too */ + start = qset_next (qset); + + return (start); /* works for empty sets, too */ } /* @@ -749,6 +730,26 @@ int qset_test_main (int argc, char **argv) /* $Log$ + Revision 1.11 2005/06/22 09:34:11 beck + typo fixed + + Revision 1.10 2004/12/21 15:37:31 beck + added config.h include + removed unused sys/times.h + removed C99 constructs + + Revision 1.9 2004/12/20 17:34:35 liekweg + fix recursion handling + + Revision 1.8 2004/12/06 12:49:26 liekweg + virtually no change + + Revision 1.7 2004/11/30 14:47:11 liekweg + insert report changes + + Revision 1.6 2004/11/26 15:58:30 liekweg + don't free inside obstacks (thx, michael) + Revision 1.5 2004/11/24 14:53:56 liekweg Bugfixes