summaryrefslogtreecommitdiffhomepage
path: root/ir/lpp/sp_matrix.h
blob: 19df44976dcdfc048e66b1e6fc601f322f6b53b2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief   Sparse matrix storage with linked lists for rows and cols.
 * @author  Daniel Grund
 */
#ifndef LPP_SP_MATRIX_H
#define LPP_SP_MATRIX_H

#include <stdio.h>

/**
 * A matrix element.
 */
typedef struct matrix_elem_t {
	int   row;  /* row index */
	int   col;  /* column index */
	float val;  /* the actual value of the entry */
} matrix_elem_t;

typedef struct sp_matrix_t sp_matrix_t;

/**
 * Allocate a new matrix and init internal data for a matrix of size
 * row_init X col_init. Matrix cannot grow beyond these init values.
 * All elements are initially (implicit) set to 0.
 */
sp_matrix_t *new_matrix(int rows, int cols);

/**
 * Free space used by matrix m
 */
void del_matrix(sp_matrix_t *m);

/**
 * Sets m[row, col] to val
 */
void matrix_set(sp_matrix_t *m, int row, int col, double val);

/**
 * Sets m[row, cols[0,...,i]] to val for i in (0, ..., num_cols - 1)
 * Following assumptions are done here:
 * - the current row inserted is the last inserted row so far
 * - cols[] is sorted ascending by col number
 */
void matrix_set_row_bulk(sp_matrix_t *m, int row, int *cols, int num_cols, double val);

/**
 * Returns the value stored in m[row, col].
 */
double matrix_get(const sp_matrix_t *m, int row, int col);

/**
 * Returns the number of (not-0-)entries.
 */
int matrix_get_entries(const sp_matrix_t *m);

/**
 * Returns the number of rows in this matrix; the height; the first dimension
 */
int matrix_get_rowcount(const sp_matrix_t *m);

/**
 * Returns the number of cols in this matrix; the width; the second dimension
 */
int matrix_get_colcount(const sp_matrix_t *m);

/**
 * Start iteration over all matrix elements. Row by row, from top to bottom.
 * @return NULL if the matrix is empty, else the first element.
 */
const matrix_elem_t *matrix_first(sp_matrix_t *m);

/**
 * Start iteration over a row. Elements are returned from left to right.
 * @return NULL if row is empty, else the first element.
 */
const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row);

/**
 * Start iteration over a column. Elements are returned from top to bottom.
 * @return NULL if column is empty, else the first element.
 */
const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col);

/**
 * @return the next element in iteration order or NULL if iteration is done.
 */
const matrix_elem_t *matrix_next(sp_matrix_t *m);

/**
 * @return the size for a single matrix element
 */
unsigned matrix_get_elem_size(void);

/**
 * m    The matrix
 * curr The variable to assign all elements to during iteration
 * Save against removal of curr
 */
#define matrix_foreach(m,curr) \
		for (matrix_elem_t const *curr = matrix_first(m); curr; curr = matrix_next(m))

/**
 * m    The matrix
 * r    The row
 * curr The variable to assign all elements to during iteration
 * Save against removal of curr
 */
#define matrix_foreach_in_row(m,r,curr) \
		for (matrix_elem_t const *curr = matrix_row_first(m, r); curr; curr = matrix_next(m))

/**
 * m    The matrix
 * c    The col
 * curr The variable to assign all elements to during iteration
 * Save against removal of curr
 */
#define matrix_foreach_in_col(m,c,curr) \
		for (matrix_elem_t const *curr = matrix_col_first(m, c); curr; curr = matrix_next(m))

/**
 * Changes the matrix into an equivalent one with maximal number zero-rows.
 * The only equivalence transformation is:
 * Adding a constant to Qij and subtracting it from Qji
 */
void matrix_optimize(sp_matrix_t *m);

/**
 * Dumps the matrix factor*m to the stream @p out.
 * Remark: I dont need spaces between the elements. So feel free to add
 *         char *seperator to the arguments.
 */
void matrix_dump(sp_matrix_t *m, FILE *out, int factor);

/**
 * Perform a self test with a square matrix of dimensions d.
 */
void matrix_self_test(int d);

#endif