/* -*- c -*- */
/*
- * Time-stamp: <01.11.2004 19:45:58h liekweg>
+ * Time-stamp: <17.12.2004 20:26:51h liekweg>
* Project: libFIRM
* File name: ir/ana2/qset.c
* Purpose: yet another set implementation
* 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 <stdio.h>
# include <stdlib.h>
# include <assert.h>
# include <string.h>
-# include <sys/time.h>
+# include "obst.h"
# include "timing.h"
# include "qset.h"
-static __inline__ int sortable_compare (const void *pa, const void *pb)
+/* local globals */
+int qset_id = 0;
+
+/* local protos */
+
+# ifdef UNSINN
+/* Check whether the given list of sortables is sorted. */
+static void q_check (sortable_t*, const int);
+# endif /* defined UNSINN */
+
+/* Test whether the given val is among values. Return the index of
+ val in values, or -1. */
+static int q_test (sortable_t*, const sortable_t, const int);
+
+/* Sort n_elems entries in 'values' */
+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)
{
const int a = * (unsigned int*) pa;
const int b = * (unsigned int*) pb;
return ((a < b) ? -1 : +1);
}
+/*
+ Wrapper for mixed allocation
+*/
+static void *mix_malloc (struct obstack *obst, size_t size)
+{
+ if (NULL != obst) {
+ return (obstack_alloc (obst, size));
+ } else {
+ return (malloc (size));
+ }
+}
+
/*
Allocate a list of sortables of the given length.
*/
-static sortable_t *alloc_list (const int len)
+static sortable_t *alloc_list (const int len, struct obstack *obst)
{
- sortable_t *values = (sortable_t*) malloc (len * sizeof (sortable_t));
+ sortable_t *values = (sortable_t*) mix_malloc (obst, len * sizeof (sortable_t));
memset (values, 0x00, len * sizeof (sortable_t));
/*
Create a list of sortables of the given length.
*/
-static sortable_t *gen_list (const int len)
+static sortable_t *gen_list (const int len, struct obstack *obst)
{
int i;
- sortable_t *values = alloc_list (len);
+ sortable_t *values = alloc_list (len, obst);
for (i = 0; i < len; i ++) {
values [i] = rand () >> 16;
int qtotal = 0;
for (i = 0; i < n_runs; i ++) {
- sortable_t *list = gen_list (n_elems);
+ sortable_t *list = gen_list (n_elems, NULL);
timing_t *timing = start_timing ();
q_sort (list, n_elems);
}
for (i = 0; i < n_runs; i ++) {
- sortable_t *list = gen_list (n_elems);
+ sortable_t *list = gen_list (n_elems, NULL);
timing_t *timing = start_timing ();
qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
int i;
int n1, n2, n;
- qset_t *q1 = qset_new (n_entries);
- qset_t *q2 = qset_new (n_entries);
+ qset_t *q1 = qset_new (n_entries, NULL);
+ qset_t *q2 = qset_new (n_entries, NULL);
qset_t *q = NULL;
- sortable_t *values = gen_list (n_entries);
+ sortable_t *values = gen_list (n_entries, NULL);
for (i = 0; i < n_entries; i ++) {
qset_insert (q1, values [i]);
new_size *= 2;
}
- values = alloc_list (new_size);
+ values = alloc_list (new_size, qset->obst);
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;
}
-/* PUBLIC INTERFACE */
-
/*
Print a list of sortables.
*/
-void q_print (sortable_t *values, const int n_values, FILE *stream)
+static void q_print (sortable_t *values, const int n_values, FILE *stream)
{
int i;
if (0 == values [i]) {
fprintf (stream, "_");
} else {
- fprintf (stream, "%d", (int) values [i]);
+ fprintf (stream, "0x08%x", (int) values [i]);
}
if (i + 1 != n_values) {
fprintf (stream, "}\n");
}
+# ifdef UNSINN
/*
Check whether the given list of sortables is sorted.
*/
-void q_check (sortable_t *values, const int n_values)
+static void q_check (sortable_t *values, const int n_values)
{
int i;
assert (-1 != q_test (values, values [i], n_values));
}
}
+# endif /* defined UNSINN */
/*
Test whether the given val is among values. Return the lowest index of val
in values, or -1.
*/
-int q_test (sortable_t *values, const sortable_t val, const int n_elems)
+static int q_test (sortable_t *values, const sortable_t val, const int n_elems)
{
int idx = _q_test (values, val, 0, n_elems-1);
/*
Sort entries in 'values' from index 'lo' to 'hi' (inclusive)
*/
-void q_sort (sortable_t *values, const int n_elems)
+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)
-*/
-sortable_t *q_merge (sortable_t *list1, const int n1_elems,
- sortable_t *list2, const int n2_elems)
-{
- const int n_elems = n1_elems + n2_elems;
- sortable_t *res = alloc_list (n_elems);
-
- 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 */
/*
Allocate a new qset with initial space for up to n_elems.
+ If a non-NULL obstack is given, it is used for all allocations of this qset
+ and must be initialised and deleted by the user of the qset.
*/
-qset_t *qset_new (const int n_elems)
+qset_t *qset_new (const int n_elems, struct obstack *obst)
{
- qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
+ qset_t *qset = (qset_t*) mix_malloc (obst, sizeof (qset_t));
- qset->values = alloc_list (n_elems);
+ qset->obst = obst;
+ qset->values = alloc_list (n_elems, obst);
memset (qset->values, 0x00, n_elems * sizeof (sortable_t));
qset->n_slots = n_elems;
qset->n_elems = 0;
qset->is_sorted = FALSE;
+ qset->id = qset_id ++;
return (qset);
}
*/
void qset_compact (qset_t *qset)
{
- sortable_t *values = (sortable_t*) malloc (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;
+ }
}
/*
void qset_delete (qset_t *qset)
{
memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
- free (qset->values);
+
+ if (NULL == qset->obst) {
+ free (qset->values);
+ }
memset (qset, 0x00, sizeof (qset_t));
- free (qset);
+ if (NULL == qset->obst) {
+ free (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)
{
}
/*
- 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)
{
- /* TODO: sort, find */
- /* or check for duplicates */
+ int i;
+ const int n_elems = qset->n_elems;
+
+ /* todo: sort, find */
+ assert (0 != val);
+
+ for (i = 0; i < n_elems; i ++) {
+ if (EQUAL (val, qset->values [i])) {
+ 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->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);
}
/*
*/
qset_t *qset_union (qset_t *qset1, qset_t *qset2)
{
- qset_t *qset = (qset_t*) malloc (sizeof (qset_t));
+ qset_t *qset = (qset_t*) mix_malloc (qset1->obst, sizeof (qset_t));
const int n_elems = qset1->n_elems + qset2->n_elems;
- qset->values = alloc_list (n_elems);
+ qset->values = alloc_list (n_elems, qset1->obst);
memcpy (qset->values, qset1->values,
qset1->n_elems * sizeof (sortable_t));
memcpy (qset->values+qset1->n_elems,
qset2->values, qset2->n_elems * sizeof (sortable_t));
+ qset->obst = qset1->obst;
qset->n_elems = n_elems;
qset->n_slots = qset->n_elems;
q_print (qset->values, qset->n_elems, stream);
}
+/*
+ Check wether the given qset is empty
+*/
+int qset_is_empty (qset_t *qset)
+{
+ return (0 == qset->n_elems);
+}
+
/*
Initialise a new iteration over a 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 */
}
/*
return (NULL);
}
+ /* quick fix to skip NULL entries */
+ while ((qset->cursor < qset->n_elems) &&
+ (NULL == qset->values [qset->cursor])) {
+ qset->cursor ++;
+ }
+
return (qset->values [qset->cursor++]);
}
/*
$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
+
+ Revision 1.4 2004/11/18 16:35:45 liekweg
+ Added unique ids for debugging
+
+ Revision 1.3 2004/11/09 16:45:36 liekweg
+ print pointers
+
+ Revision 1.2 2004/11/08 12:32:00 liekweg
+ Moved q_* methods into private section
+
Revision 1.1 2004/11/04 14:55:13 liekweg
added qset