/* -*- c -*- */
/*
- * Time-stamp: <01.11.2004 19:45:58h liekweg>
+ * Time-stamp: <11.11.2004 16:42:15h liekweg>
* Project: libFIRM
* File name: ir/ana2/qset.c
* Purpose: yet another set implementation
# include "timing.h"
# include "qset.h"
+/* 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;
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)
+static 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);
return (res);
}
+/* PUBLIC INTERFACE */
+
/*
Allocate a new qset with initial space for up to n_elems.
*/
qset->n_slots = n_elems;
qset->n_elems = 0;
qset->is_sorted = FALSE;
+ qset->id = qset_id ++;
return (qset);
}
*/
void 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;
+ }
+ }
+
qset_resize (qset, qset->n_elems+1);
qset->values [qset->n_elems++] = val;
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
*/
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.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