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

   1 /*
   2  * Copyright (C) 2005-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Sparse matrix storage with linked lists for rows and cols.
  23  * @author  Daniel Grund
  24  */
  25 #ifndef LPP_SP_MATRIX_H
  26 #define LPP_SP_MATRIX_H
  27
  28 #include <stdio.h>
  29
  30 /**
  31  * A matrix element.
  32  */
  33 typedef struct matrix_elem_t {
  34         int   row;  /* row index */
  35         int   col;  /* column index */
  36         float val;  /* the actual value of the entry */
  37 } matrix_elem_t;
  38
  39 typedef struct sp_matrix_t sp_matrix_t;
  40
  41 /**
  42  * Allocate a new matrix and init internal data for a matrix of size
  43  * row_init X col_init. Matrix cannot grow beyond these init values.
  44  * All elements are initially (implicit) set to 0.
  45  */
  46 sp_matrix_t *new_matrix(int rows, int cols);
  47
  48 /**
  49  * Free space used by matrix m
  50  */
  51 void del_matrix(sp_matrix_t *m);
  52
  53 /**
  54  * Sets m[row, col] to val
  55  */
  56 void matrix_set(sp_matrix_t *m, int row, int col, double val);
  57
  58 /**
  59  * Sets m[row, cols[0,...,i]] to val for i in (0, ..., num_cols - 1)
  60  * Following assumptions are done here:
  61  * - the current row inserted is the last inserted row so far
  62  * - cols[] is sorted ascending by col number
  63  */
  64 void matrix_set_row_bulk(sp_matrix_t *m, int row, int *cols, int num_cols, double val);
  65
  66 /**
  67  * Returns the value stored in m[row, col].
  68  */
  69 double matrix_get(const sp_matrix_t *m, int row, int col);
  70
  71 /**
  72  * Returns the number of (not-0-)entries.
  73  */
  74 int matrix_get_entries(const sp_matrix_t *m);
  75
  76 /**
  77  * Returns the number of rows in this matrix; the height; the first dimension
  78  */
  79 int matrix_get_rowcount(const sp_matrix_t *m);
  80
  81 /**
  82  * Returns the number of cols in this matrix; the width; the second dimension
  83  */
  84 int matrix_get_colcount(const sp_matrix_t *m);
  85
  86 /**
  87  * Start iteration over all matrix elements. Row by row, from top to bottom.
  88  * @return NULL if the matrix is empty, else the first element.
  89  */
  90 const matrix_elem_t *matrix_first(sp_matrix_t *m);
  91
  92 /**
  93  * Start iteration over a row. Elements are returned from left to right.
  94  * @return NULL if row is empty, else the first element.
  95  */
  96 const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row);
  97
  98 /**
  99  * Start iteration over a column. Elements are returned from top to bottom.
 100  * @return NULL if column is empty, else the first element.
 101  */
 102 const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col);
 103
 104 /**
 105  * @return the next element in iteration order or NULL if iteration is done.
 106  */
 107 const matrix_elem_t *matrix_next(sp_matrix_t *m);
 108
 109 /**
 110  * @return the size for a single matrix element
 111  */
 112 unsigned matrix_get_elem_size(void);
 113
 114 /**
 115  * m    The matrix
 116  * curr The variable to assign all elements to during iteration
 117  * Save against removal of curr
 118  */
 119 #define matrix_foreach(m,curr) \
 120                 for (matrix_elem_t const *curr = matrix_first(m); curr; curr = matrix_next(m))
 121
 122 /**
 123  * m    The matrix
 124  * r    The row
 125  * curr The variable to assign all elements to during iteration
 126  * Save against removal of curr
 127  */
 128 #define matrix_foreach_in_row(m,r,curr) \
 129                 for (matrix_elem_t const *curr = matrix_row_first(m, r); curr; curr = matrix_next(m))
 130
 131 /**
 132  * m    The matrix
 133  * c    The col
 134  * curr The variable to assign all elements to during iteration
 135  * Save against removal of curr
 136  */
 137 #define matrix_foreach_in_col(m,c,curr) \
 138                 for (matrix_elem_t const *curr = matrix_col_first(m, c); curr; curr = matrix_next(m))
 139
 140 /**
 141  * Changes the matrix into an equivalent one with maximal number zero-rows.
 142  * The only equivalence transformation is:
 143  * Adding a constant to Qij and subtracting it from Qji
 144  */
 145 void matrix_optimize(sp_matrix_t *m);
 146
 147 /**
 148  * Dumps the matrix factor*m to the stream @p out.
 149  * Remark: I dont need spaces between the elements. So feel free to add
 150  *         char *seperator to the arguments.
 151  */
 152 void matrix_dump(sp_matrix_t *m, FILE *out, int factor);
 153
 154 /**
 155  * Perform a self test with a square matrix of dimensions d.
 156  */
 157 void matrix_self_test(int d);
 158
 159 #endif