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

   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 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <assert.h>
  15 #include "sp_matrix.h"
  16 #include "list.h"
  17
  18 typedef enum _iter_direction_t {
  19         down, right
  20 } iter_direction_t;
  21
  22 typedef struct _entry_t {
  23         struct list_head col_chain; /**< points to next element in same column */
  24         struct list_head row_chain; /**< points to next element in same row */
  25         matrix_elem_t e;
  26 } entry_t;
  27
  28 struct _sp_matrix_t {
  29         /* These specify the dimensions of the matrix.
  30          * They equal the largest values ever used in matrix_set */
  31         int maxrow, maxcol;
  32         /* These are the dimensions of allocated arrays below.
  33          * rowc >= maxrow and colc >= maxcol hold. */
  34         int rowc, colc;
  35         /* arrays of list_head* as entry-points to rows and cols */
  36         struct list_head **rows, **cols;
  37         /* for iteration */
  38         iter_direction_t dir;
  39         struct list_head *first, *last; /* first is to remember start-point; last was returned just before */
  40 };
  41
  42 #define _offsetof(type,member) ((char *) &(((type *) 0)->member) - (char *) 0)
  43 #define _container_of(ptr,type,member) ((type *) ((char *) (ptr) - _offsetof(type, member)))
  44 #define is_empty_row(row) (row>m->maxrow || list_empty(m->rows[row]))
  45 #define is_empty_col(col) (col>m->maxcol || list_empty(m->cols[col]))
  46 #define list_entry_by_col(h) (&list_entry(h, entry_t, col_chain)->e)
  47 #define list_entry_by_row(h) (&list_entry(h, entry_t, row_chain)->e)
  48
  49 /**
  50  * Returns the new size for an array of size old_size,
  51  *  which must at least store an entry at position min.
  52  */
  53 static INLINE int _m_new_size(int old_size, int min) {
  54         int bits = 0;
  55         assert(min>=old_size);
  56         while (min>0) {
  57                 min >>= 1;
  58                 bits++;
  59         }
  60         assert(bits < sizeof(min)*8-1);
  61         return 1 << bits;
  62 }
  63
  64 /**
  65  * Allocates space for @p count entries in the rows array and
  66  * intitializes all entries from @p start to the end.
  67  */
  68 static INLINE void _m_alloc_row(sp_matrix_t *m, int start, int count) {
  69         int p;
  70         m->rowc = count;
  71         m->rows = realloc(m->rows, m->rowc * sizeof(*m->rows));
  72         assert(m->rows);
  73         for (p=start; p<m->rowc; ++p) {
  74                 m->rows[p] = malloc(sizeof(*m->rows[p]));
  75                 assert(m->rows[p]);
  76                 INIT_LIST_HEAD(m->rows[p]);
  77         }
  78 }
  79
  80 /**
  81  * Allocates space for @p count entries in the cols array and
  82  * intitializes all entries from @p start to the end.
  83  */
  84 static INLINE void _m_alloc_col(sp_matrix_t *m, int start, int count) {
  85         int p;
  86         m->colc = count;
  87         m->cols = realloc(m->cols, m->colc * sizeof(*m->cols));
  88         assert(m->cols);
  89         for (p=start; p<m->colc; ++p) {
  90                 m->cols[p] = malloc(sizeof(*m->cols[p]));
  91                 assert(m->cols[p]);
  92                 INIT_LIST_HEAD(m->cols[p]);
  93         }
  94 }
  95
  96 /**
  97  * Searches in row @p row for the matrix element m[row, col].
  98  * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element.
  99  *         Else: NULL and @p prev points to the list_head after which the element would be inserted.
 100  */
 101 static INLINE matrix_elem_t *_m_search_in_row(const sp_matrix_t *m, int row, int col, struct list_head **prev) {
 102         struct list_head *start;
 103         start = *prev = m->rows[row];
 104         while ((*prev)->next != start && list_entry_by_row((*prev)->next)->col <= col)
 105                 *prev = (*prev)->next;
 106         if (*prev != start) {
 107                 matrix_elem_t *me = list_entry_by_row(*prev);
 108                 if (me->row == row && me->col == col)
 109                         return me;
 110         }
 111         return NULL;
 112 }
 113
 114 /**
 115  * Searches in col @p col for the matrix element m[row, col].
 116  * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element.
 117  *         Else: NULL and @p prev points to the list_head after which the element would be inserted.
 118  */
 119 static INLINE matrix_elem_t *_m_search_in_col(const sp_matrix_t *m, int row, int col, struct list_head **prev) {
 120         struct list_head *start;
 121         start = *prev = m->cols[col];
 122         while ((*prev)->next != start && list_entry_by_col((*prev)->next)->row <= row)
 123                 *prev = (*prev)->next;
 124         if (*prev != start) {
 125                 matrix_elem_t *me = list_entry_by_col(*prev);
 126                 if (me->row == row && me->col == col)
 127                         return me;
 128         }
 129         return NULL;
 130 }
 131
 132 sp_matrix_t *new_matrix(int row_init, int col_init) {
 133         sp_matrix_t *res = calloc(1, sizeof(*res));
 134         _m_alloc_row(res, 0, row_init);
 135         _m_alloc_col(res, 0, col_init);
 136         return res;
 137 }
 138
 139 void del_matrix(sp_matrix_t *m) {
 140         int i;
 141         entry_t *e, *tmp;
 142
 143         for (i=0; i<m->rowc; ++i) {
 144                 list_for_each_entry_safe(entry_t, e, tmp, m->rows[i], row_chain)
 145                         free(e);
 146                 free(m->rows[i]);
 147         }
 148         for (i=0; i<m->colc; ++i)
 149                 free(m->cols[i]);
 150         free(m->rows);
 151         free(m->cols);
 152         free(m);
 153 }
 154
 155 void matrix_set(sp_matrix_t *m, int row, int col, int val) {
 156         matrix_elem_t *me = NULL;
 157         entry_t *entr;
 158         struct list_head *leftof, *above;
 159
 160         /* if necessary enlarge the matrix */
 161         if (row>m->maxrow) {
 162                 m->maxrow = row;
 163                 if (row>=m->rowc)
 164                         _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row));
 165         }
 166         if (col>m->maxcol) {
 167                 m->maxcol = col;
 168                 if (col>=m->colc)
 169                         _m_alloc_col(m, m->colc, _m_new_size(m->colc, col));
 170         }
 171
 172         /* search for existing entry */
 173         if (m->maxrow < m->maxcol)
 174                 me = _m_search_in_col(m, row, col, &above);
 175         else
 176                 me = _m_search_in_row(m, row, col, &leftof);
 177
 178         /* if it exists, set the value and return */
 179         if (me) {
 180                 if (val != 0) {
 181                         me->val = val;
 182                 } else {
 183                         entr = _container_of(me, entry_t, e);
 184                         list_del(&entr->row_chain);
 185                         list_del(&entr->col_chain);
 186                         free(entr);
 187                 }
 188                 return;
 189         }
 190
 191         /* if it does not exist search the other direction */
 192         if (m->maxrow >= m->maxcol)
 193                 _m_search_in_col(m, row, col, &above);
 194         else
 195                 _m_search_in_row(m, row, col, &leftof);
 196         /* now leftof and above are the entry_t's prior the new one in each direction */
 197
 198         /* insert new entry */
 199         entr = malloc(sizeof(*entr));
 200         entr->e.row = row;
 201         entr->e.col = col;
 202         entr->e.val = val;
 203         list_add(&entr->row_chain, leftof);
 204         list_add(&entr->col_chain, above);
 205 }
 206
 207 int matrix_get(const sp_matrix_t *m, int row, int col) {
 208         struct list_head *dummy;
 209         matrix_elem_t *me;
 210
 211         if (is_empty_row(row) || is_empty_col(col))
 212                 return 0;
 213
 214         if (m->maxrow < m->maxcol)
 215                 me = _m_search_in_col(m, row, col, &dummy);
 216         else
 217                 me = _m_search_in_row(m, row, col, &dummy);
 218
 219         if (me)
 220                 assert(me->col == col && me->row == row);
 221
 222         return me?me->val:0;
 223 }
 224
 225 int matrix_get_rowcount(const sp_matrix_t *m) {
 226         return m->maxrow+1;
 227 }
 228
 229 int matrix_get_colcount(const sp_matrix_t *m) {
 230         return m->maxcol+1;
 231 }
 232
 233 matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row) {
 234         if (is_empty_row(row))
 235                 return NULL;
 236         m->dir = right;
 237         m->first = m->rows[row];
 238         m->last = m->rows[row]->next;
 239         assert ( (&list_entry(m->last, entry_t, row_chain)->e)->row == row);
 240         return &list_entry(m->last, entry_t, row_chain)->e;
 241 }
 242
 243 matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col) {
 244         if (is_empty_col(col))
 245                 return NULL;
 246         m->dir = down;
 247         m->first = m->cols[col];
 248         m->last = m->cols[col]->next;
 249         assert ( (&list_entry(m->last, entry_t, col_chain)->e)->col == col);
 250         return &list_entry(m->last, entry_t, col_chain)->e;
 251 }
 252
 253 matrix_elem_t *matrix_next(sp_matrix_t *m) {
 254         assert(m->last && "Start iteration with matrix_???_first, before calling me!");
 255         if (m->last->next == m->first)
 256                 return NULL;
 257         m->last = m->last->next;
 258         if (m->dir == right)
 259                 return &list_entry(m->last, entry_t, row_chain)->e;
 260         else
 261                 return &list_entry(m->last, entry_t, col_chain)->e;
 262 }
 263
 264 void matrix_dump(sp_matrix_t *m, FILE *out, int factor) {
 265         int i, o, last_idx;
 266         matrix_elem_t *e;
 267
 268         for (i=0; i <= m->maxrow; ++i) {
 269                 last_idx = -1;
 270                 matrix_foreach_in_row(m, i, e) {
 271                         for (o=last_idx+1; o<e->col; ++o)
 272                                 fprintf(out, "0");
 273                         fprintf(out, "%d", factor*e->val);
 274                         last_idx = e->col;
 275                 }
 276                 for (o=last_idx+1; o<=m->maxcol; ++o)
 277                         fprintf(out, "0");
 278                 fprintf(out, "\n");
 279         }
 280 }
 281
 282 void matrix_self_test(int d) {
 283         int i, o;
 284         matrix_elem_t *e;
 285         sp_matrix_t *m = new_matrix(10, 10);
 286
 287         for (i=0; i<d; ++i)
 288                 for (o=0; o<d; ++o)
 289                         matrix_set(m, i, o, i*o);
 290
 291         for (i=0; i<d; ++i)
 292                 for (o=0; o<d; ++o)
 293                         assert(matrix_get(m, i, o) == i*o);
 294
 295         i = 0;
 296         matrix_foreach_in_row(m,1,e) {
 297                 assert(e->val == i);
 298                 i++;
 299         }
 300         assert(!matrix_next(m)); /*iter must finish */
 301
 302         i = 0;
 303         matrix_foreach_in_col(m,d-1,e) {
 304                 assert(e->val == i);
 305                 i += d-1;
 306         }
 307         assert(!matrix_next(m));
 308         del_matrix(m);
 309         m = new_matrix(16,16);
 310         matrix_set(m, 1,1,9);
 311         matrix_set(m, 1,2,8);
 312         matrix_set(m, 1,3,7);
 313
 314         matrix_set(m, 1,3,6);
 315         matrix_set(m, 1,2,5);
 316         matrix_set(m, 1,1,4);
 317         i = 1;
 318         matrix_foreach_in_row(m, 1, e) {
 319                 assert(e->row == 1 && e->col == i && e->val == i+3);
 320                 i++;
 321         }
 322         assert(i == 4);
 323         del_matrix(m);
 324 }