projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Bugfixes
[libfirm]
/
ir
/
ana2
/
qset.c
diff --git
a/ir/ana2/qset.c
b/ir/ana2/qset.c
index
03ee5b8
..
8813512
100644
(file)
--- a/
ir/ana2/qset.c
+++ b/
ir/ana2/qset.c
@@
-1,7
+1,7
@@
/* -*- c -*- */
/*
/* -*- c -*- */
/*
- * Time-stamp: <
09.11.2004 11:42:19
h liekweg>
+ * Time-stamp: <
23.11.2004 13:26:21
h liekweg>
* Project: libFIRM
* File name: ir/ana2/qset.c
* Purpose: yet another set implementation
* Project: libFIRM
* File name: ir/ana2/qset.c
* Purpose: yet another set implementation
@@
-18,22
+18,29
@@
# include <assert.h>
# include <string.h>
# include <sys/time.h>
# include <assert.h>
# include <string.h>
# include <sys/time.h>
+# include <obstack.h>
# include "timing.h"
# include "qset.h"
# include "timing.h"
# include "qset.h"
+/* local globals */
+int qset_id = 0;
+
/* local protos */
/* local protos */
-/* Check whether the given list of sortables is sorted. */
# ifdef UNSINN
# ifdef UNSINN
+/* Check whether the given list of sortables is sorted. */
static void q_check (sortable_t*, const int);
# endif /* defined UNSINN */
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);
/* 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);
/* 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;
static __inline__ int sortable_compare (const void *pa, const void *pb)
{
const int a = * (unsigned int*) pa;
@@
-46,12
+53,24
@@
static __inline__ int sortable_compare (const void *pa, const void *pb)
return ((a < b) ? -1 : +1);
}
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.
*/
/*
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*) m
alloc (
len * sizeof (sortable_t));
+ sortable_t *values = (sortable_t*) m
ix_malloc (obst,
len * sizeof (sortable_t));
memset (values, 0x00, len * sizeof (sortable_t));
memset (values, 0x00, len * sizeof (sortable_t));
@@
-62,10
+81,10
@@
static sortable_t *alloc_list (const int len)
/*
Create a list of sortables of the given length.
*/
/*
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;
{
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;
for (i = 0; i < len; i ++) {
values [i] = rand () >> 16;
@@
-183,7
+202,7
@@
static void test_qsort (const int n_runs, const int max_elems, const int incr)
int qtotal = 0;
for (i = 0; i < n_runs; i ++) {
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);
timing_t *timing = start_timing ();
q_sort (list, n_elems);
@@
-195,7
+214,7
@@
static void test_qsort (const int n_runs, const int max_elems, const int incr)
}
for (i = 0; i < n_runs; i ++) {
}
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);
timing_t *timing = start_timing ();
qsort (list, n_elems, sizeof (sortable_t), sortable_compare);
@@
-223,11
+242,11
@@
static void test_qset (const int n_entries)
int i;
int n1, n2, n;
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;
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]);
for (i = 0; i < n_entries; i ++) {
qset_insert (q1, values [i]);
@@
-321,7
+340,7
@@
static void qset_resize (qset_t *qset, const int n_slots)
new_size *= 2;
}
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 */
memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t)); /* debug only */
@@
-401,10
+420,11
@@
static void q_sort (sortable_t *values, const int n_elems)
Merge two sorted lists. Keep duplicates (if present)
*/
static sortable_t *q_merge (sortable_t *list1, const int n1_elems,
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)
+ sortable_t *list2, const int n2_elems,
+ struct obstack *obst)
{
const int n_elems = n1_elems + n2_elems;
{
const int n_elems = n1_elems + n2_elems;
- sortable_t *res = alloc_list (n_elems);
+ sortable_t *res = alloc_list (n_elems
, obst
);
int i1 = 0;
int i2 = 0;
int i1 = 0;
int i2 = 0;
@@
-433,17
+453,21
@@
static sortable_t *q_merge (sortable_t *list1, const int n1_elems,
/*
Allocate a new qset with initial space for up to n_elems.
/*
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*) m
alloc (
sizeof (qset_t));
+ qset_t *qset = (qset_t*) m
ix_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;
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);
}
return (qset);
}
@@
-485,7
+509,8
@@
void qset_sort (qset_t *qset)
*/
void qset_compact (qset_t *qset)
{
*/
void qset_compact (qset_t *qset)
{
- sortable_t *values = (sortable_t*) malloc (qset->n_elems * sizeof (sortable_t));
+ 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));
memcpy (values, qset->values, qset->n_elems * sizeof (sortable_t));
memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
@@
-501,11
+526,16
@@
void qset_compact (qset_t *qset)
void qset_delete (qset_t *qset)
{
memset (qset->values, 0x00, qset->n_elems * sizeof (sortable_t));
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));
memset (qset, 0x00, sizeof (qset_t));
- free (qset);
+ if (NULL == qset->obst) {
+ free (qset);
+ }
}
/*
}
/*
@@
-581,7
+611,8
@@
void qset_insert_all (qset_t *qset1, qset_t *qset2)
qset_sort (qset2);
qset1->values = q_merge (qset1->values, qset1->n_elems,
qset_sort (qset2);
qset1->values = q_merge (qset1->values, qset1->n_elems,
- qset2->values, qset2->n_elems);
+ qset2->values, qset2->n_elems,
+ qset1->obst);
qset1->n_elems = qset1->n_elems + qset2->n_elems;
qset1->n_slots = qset1->n_elems;
qset1->n_elems = qset1->n_elems + qset2->n_elems;
qset1->n_slots = qset1->n_elems;
@@
-621,10
+652,10
@@
int qset_compare (qset_t *qset1, qset_t *qset2)
*/
qset_t *qset_union (qset_t *qset1, qset_t *qset2)
{
*/
qset_t *qset_union (qset_t *qset1, qset_t *qset2)
{
- qset_t *qset = (qset_t*) m
alloc (
sizeof (qset_t));
+ qset_t *qset = (qset_t*) m
ix_malloc (qset1->obst,
sizeof (qset_t));
const int n_elems = qset1->n_elems + qset2->n_elems;
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->values,
qset1->n_elems * sizeof (sortable_t));
@@
-632,6
+663,7
@@
qset_t *qset_union (qset_t *qset1, qset_t *qset2)
memcpy (qset->values+qset1->n_elems,
qset2->values, qset2->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;
qset->n_elems = n_elems;
qset->n_slots = qset->n_elems;
@@
-683,6
+715,12
@@
sortable_t *qset_next (qset_t *qset)
return (NULL);
}
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++]);
}
return (qset->values [qset->cursor++]);
}
@@
-711,6
+749,12
@@
int qset_test_main (int argc, char **argv)
/*
$Log$
/*
$Log$
+ 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.3 2004/11/09 16:45:36 liekweg
print pointers