+#include "config.h"
+
#include <assert.h>
#include <math.h>
#include <string.h>
#include "xmalloc.h"
#include "gaussseidel.h"
-#include "firm_config.h"
#include "util.h"
-#define MAX(x,y) ((x) > (y) ? (x) : (y))
-#define MIN(x,y) ((x) < (y) ? (x) : (y))
-
/**
* The number of newly allocated rows (realloc)
* when there is no more room. Must be >= 1.
*/
#define COL_INCREASE 2
-typedef struct _col_val_t {
+typedef struct col_val_t {
double v;
int col_idx;
} col_val_t;
-typedef struct _row_col_t {
+typedef struct row_col_t {
int c_cols;
int n_cols;
double diag;
col_val_t *cols;
} row_col_t;
-struct _gs_matrix_t {
+struct gs_matrix_t {
int initial_col_increase;
int c_rows;
int n_zero_entries; ///< Upper bound on number of entries equal to 0.0
row_col_t *rows;
};
-static INLINE void alloc_cols(row_col_t *row, int c_cols) {
+static inline void alloc_cols(row_col_t *row, int c_cols)
+{
assert(c_cols > row->c_cols);
row->c_cols = c_cols;
- row->cols = xrealloc(row->cols, c_cols * sizeof(*row->cols));
+ row->cols = XREALLOC(row->cols, col_val_t, c_cols);
}
-static INLINE void alloc_rows(gs_matrix_t *m, int c_rows, int c_cols, int begin_init) {
+static inline void alloc_rows(gs_matrix_t *m, int c_rows, int c_cols, int begin_init)
+{
int i;
assert(c_rows > m->c_rows);
m->c_rows = c_rows;
- m->rows = xrealloc(m->rows, c_rows * sizeof(*m->rows));
+ m->rows = XREALLOC(m->rows, row_col_t, c_rows);
for (i = begin_init; i < c_rows; ++i) {
m->rows[i].c_cols = 0;
}
}
-gs_matrix_t *gs_new_matrix(int n_init_rows, int n_init_cols) {
- gs_matrix_t *res = xmalloc(sizeof(*res));
- memset(res, 0, sizeof(*res));
+gs_matrix_t *gs_new_matrix(int n_init_rows, int n_init_cols)
+{
+ gs_matrix_t *res = XMALLOCZ(gs_matrix_t);
if (n_init_rows < 16)
n_init_rows = 16;
res->initial_col_increase = n_init_cols;
return res;
}
-void gs_delete_matrix(gs_matrix_t *m) {
+void gs_delete_matrix(gs_matrix_t *m)
+{
int i;
for (i = 0; i < m->c_rows; ++i) {
if (m->rows[i].c_cols)
xfree(m);
}
-unsigned gs_matrix_get_n_entries(const gs_matrix_t *m) {
+unsigned gs_matrix_get_n_entries(const gs_matrix_t *m)
+{
int i;
unsigned n_entries = 0;
return n_entries - m->n_zero_entries;
}
-int gs_matrix_get_sizeof_allocated_memory(const gs_matrix_t *m) {
+int gs_matrix_get_sizeof_allocated_memory(const gs_matrix_t *m)
+{
int i, n_col_val_ts = 0;
for (i = 0; i < m->c_rows; ++i)
n_col_val_ts += m->rows[i].c_cols;
return n_col_val_ts * sizeof(col_val_t) + m->c_rows * sizeof(row_col_t) + sizeof(gs_matrix_t);
}
-void gs_matrix_assure_row_capacity(gs_matrix_t *m, int row, int min_capacity) {
+void gs_matrix_assure_row_capacity(gs_matrix_t *m, int row, int min_capacity)
+{
row_col_t *the_row = &m->rows[row];
if (the_row->c_cols < min_capacity)
alloc_cols(the_row, min_capacity);
}
-void gs_matrix_trim_row_capacities(gs_matrix_t *m) {
+void gs_matrix_trim_row_capacities(gs_matrix_t *m)
+{
int i;
for (i = 0; i < m->c_rows; ++i) {
row_col_t *the_row = &m->rows[i];
if (the_row->c_cols) {
the_row->c_cols = the_row->n_cols;
if (the_row->c_cols)
- the_row->cols = xrealloc(the_row->cols, the_row->c_cols * sizeof(*the_row->cols));
+ the_row->cols = XREALLOC(the_row->cols, col_val_t, the_row->c_cols);
else
xfree(the_row->cols);
}
}
}
-void gs_matrix_delete_zero_entries(gs_matrix_t *m) {
+void gs_matrix_delete_zero_entries(gs_matrix_t *m)
+{
int i, read_pos;
for (i = 0; i < m->c_rows; ++i) {
row_col_t *the_row = &m->rows[i];
m->n_zero_entries = 0;
}
-void gs_matrix_set(gs_matrix_t *m, int row, int col, double val) {
+void gs_matrix_set(gs_matrix_t *m, int row, int col, double val)
+{
row_col_t *the_row;
col_val_t *cols;
int min, max, c, i;
if (row >= m->c_rows) {
- int new_c_rows = ROW_INCREASE_FACTOR * row;
+ int new_c_rows = (int)(ROW_INCREASE_FACTOR * row);
alloc_rows(m, new_c_rows, m->initial_col_increase, m->c_rows);
}
cols = the_row->cols;
min = 0;
max = the_row->n_cols;
- c = (max+min)/2;
+ c = max/2;
while (min < max) {
int idx = cols[c].col_idx;
if (idx < col)
assert(c>=the_row->n_cols-1 || the_row->cols[c].col_idx < the_row->cols[c+1].col_idx);
}
-double gs_matrix_get(const gs_matrix_t *m, int row, int col) {
+double gs_matrix_get(const gs_matrix_t *m, int row, int col)
+{
+ row_col_t *the_row;
int c;
+
if (row >= m->c_rows)
return 0.0;
- row_col_t *the_row = &m->rows[row];
+
+ the_row = &m->rows[row];
if (row == col)
return the_row->diag != 0.0 ? 1.0 / the_row->diag : 0.0;
// Search for correct column
- for (c = 0; c < the_row->n_cols && the_row->cols[c].col_idx < col; ++c);
+ for (c = 0; c < the_row->n_cols && the_row->cols[c].col_idx < col; ++c) {
+ }
if (c >= the_row->n_cols || the_row->cols[c].col_idx > col)
return 0.0;
*
* Note that the diagonal element is stored separately in this matrix implementation.
* */
-double gs_matrix_gauss_seidel(const gs_matrix_t *m, double *x, int n) {
+double gs_matrix_gauss_seidel(const gs_matrix_t *m, double *x, int n)
+{
double res = 0.0;
int r;
}
}
-void gs_matrix_dump(const gs_matrix_t *m, int a, int b, FILE *out) {
+void gs_matrix_dump(const gs_matrix_t *m, int a, int b, FILE *out)
+{
int effective_rows = MIN(a, m->c_rows);
int r, c, i;
- double *elems = xmalloc(b * sizeof(*elems));
+ double *elems = XMALLOCN(double, b);
// The rows which have some content
for (r=0; r < effective_rows; ++r) {
+ row_col_t *row = &m->rows[r];
+
memset(elems, 0, b * sizeof(*elems));
- row_col_t *row = &m->rows[r];
for (c = 0; c < row->n_cols; ++c) {
int col_idx = row->cols[c].col_idx;
elems[col_idx] = row->cols[c].v;
xfree(elems);
}
-
-void gs_matrix_self_test(int d) {
- int i, o;
- gs_matrix_t *m = gs_new_matrix(10, 10);
-
- for (i=0; i<d; ++i)
- for (o=0; o<d; ++o)
- gs_matrix_set(m, i, o, i*o);
-
- for (i=0; i<d; ++i)
- for (o=0; o<d; ++o)
- assert(gs_matrix_get(m, i, o) == i*o);
- gs_delete_matrix(m);
-}
projects / libfirm / blobdiff