/* -*- c -*- */
/*
- * Time-stamp: <26.11.2004 16:53:35h liekweg>
- * Project: libFIRM
- * File name: ir/ana2/qset.c
- * Purpose: yet another set implementation
- * Author: Florian
- * Modified by:
- * Created: Mon 18 Oct 2004
- * CVS-ID: $Id$
- * Copyright: (c) 1999-2004 Universität Karlsruhe
- * Licence: This file is protected by GPL - GNU GENERAL PUBLIC LICENSE.
+ * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
*/
+/**
+ * @file
+ * @brief yet another set implementation
+ * @author Florian
+ * @date Mon 18 Oct 2004
+ * @version $Id$
+ */
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
# include <string.h>
-# include <sys/time.h>
-# include <obstack.h>
+# include "obst.h"
# include "timing.h"
# include "qset.h"
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;
if (NULL != obst) {
return (obstack_alloc (obst, size));
} else {
- return (malloc (size));
+ return (xmalloc (size));
}
}
_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 */
/*
}
/*
- 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)
{
}
/*
- 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;
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));
-
- if (NULL == qset1->obst) {
- free (values);
- }
+ return (change);
}
/*
*/
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 */
}
/*
/*
$Log$
+ Revision 1.12 2006/06/06 12:06:27 beck
+ use xmalloc instead of malloc
+
+ 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)
projects / libfirm / blobdiff