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