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

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