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

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