nsz Git - libfirm/blob - ir/be/sp_matrix.h

   1 /**
   2  * Sparse matrix storage with linked lists for rows and cols.
   3  * I did not need floats, so this is all integer.
   4  * @author Daniel Grund
   5  * @date 07.04.2005
   6  */
   7
   8 #ifndef _SP_MATRIX_H
   9 #define _SP_MATRIX_H
  10
  11 #include <stdio.h>
  12
  13 typedef struct _matrix_elem_t {
  14         int row, col, val;
  15 } matrix_elem_t;
  16
  17 typedef struct _sp_matrix_t sp_matrix_t;
  18
  19 /**
  20  * Allocate a new matrix and init internal data for a matrix of size
  21  * row_init X col_init. Matrix cannot grow beyond these init values.
  22  * All elements are initially (implicit) set to 0.
  23  */
  24 sp_matrix_t *new_matrix(int rows, int cols);
  25
  26 /**
  27  * Free space used by matrix m
  28  */
  29 void del_matrix(sp_matrix_t *m);
  30
  31 /**
  32  * Sets m[row, col] to val
  33  */
  34 void matrix_set(sp_matrix_t *m, int row, int col, int val);
  35
  36 /**
  37  * Returns the value stored in m[row, col].
  38  */
  39 int matrix_get(const sp_matrix_t *m, int row, int col);
  40
  41 /**
  42  * Returns the number of (not-0-)entries.
  43  */
  44 int matrix_get_entries(const sp_matrix_t *m);
  45
  46 /**
  47  * Returns the number of rows in this matrix; the height; the first dimension
  48  */
  49 int matrix_get_rowcount(const sp_matrix_t *m);
  50
  51 /**
  52  * Returns the number of cols in this matrix; the width; the second dimension
  53  */
  54 int matrix_get_rowcount(const sp_matrix_t *m);
  55
  56 /**
  57  * Start iteration over all matrix elements. Row by row, from top to bottom.
  58  * @return NULL if the matrix is empty, else the first element.
  59  */
  60 const matrix_elem_t *matrix_first(sp_matrix_t *m);
  61
  62 /**
  63  * Start iteratation over a row. Elements are returned from left to right.
  64  * @return NULL if row is empty, else the first element.
  65  */
  66 const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row);
  67
  68 /**
  69  * Start iteratation over a column. Elements are returned from top to bottom.
  70  * @return NULL if column is empty, else the first element.
  71  */
  72 const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int row);
  73
  74 /**
  75  * @return the next element in iteration order or NULL if iteration is done.
  76  */
  77 const matrix_elem_t *matrix_next(sp_matrix_t *m);
  78
  79 /**
  80  * m    The matrix
  81  * curr The variable to assign all elements to during iteration
  82  * Save against removal of curr
  83  */
  84 #define matrix_foreach(m,curr) \
  85                 for (curr = matrix_first(m); curr; curr = matrix_next(m))
  86
  87 /**
  88  * m    The matrix
  89  * r    The row
  90  * curr The variable to assign all elements to during iteration
  91  * Save against removal of curr
  92  */
  93 #define matrix_foreach_in_row(m,r,curr) \
  94                 for (curr = matrix_row_first(m, r); curr; curr = matrix_next(m))
  95
  96 /**
  97  * m    The matrix
  98  * c    The col
  99  * curr The variable to assign all elements to during iteration
 100  * Save against removal of curr
 101  */
 102 #define matrix_foreach_in_col(m,c,curr) \
 103                 for (curr = matrix_col_first(m, c); curr; curr = matrix_next(m))
 104
 105 /**
 106  * Changes the matrix into an equivalent one with maximal number zero-rows.
 107  * The only equivalence transformation is:
 108  *      Adding a constant to Qij and substracting it from Qji
 109  */
 110 void matrix_optimize(sp_matrix_t *m);
 111
 112 /**
 113  * Dumps the matrix factor*m to the stream @p out.
 114  * Remark: I dont need spaces between the elements. So feel free to add
 115  *         char *seperator to the arguments.
 116  */
 117 void matrix_dump(sp_matrix_t *m, FILE *out, int factor);
 118
 119 /**
 120  * Perform a self test with a sqare matrix of dimensions d.
 121  */
 122 void matrix_self_test(int d);
 123
 124 #endif