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 <alloca.h>
  15 #include <assert.h>
  16 #include "sp_matrix.h"
  17 #include "list.h"
  18 #include "bitset.h"
  19
  20 #define MAX(a,b) ((a<b)?b:a)
  21
  22 typedef enum _iter_direction_t {
  23         down, right, all
  24 } iter_direction_t;
  25
  26 typedef struct _entry_t {
  27         struct list_head col_chain; /**< points to next element in same column */
  28         struct list_head row_chain; /**< points to next element in same row */
  29         matrix_elem_t e;
  30 } entry_t;
  31
  32 struct _sp_matrix_t {
  33         /* These specify the dimensions of the matrix.
  34          * They equal the largest values ever used in matrix_set */
  35         int maxrow, maxcol;
  36         /* These are the dimensions of allocated arrays below.
  37          * rowc >= maxrow and colc >= maxcol hold. */
  38         int rowc, colc;
  39         /* number of entries */
  40         int entries;
  41         /* arrays of list_head* as entry-points to rows and cols */
  42         struct list_head **rows, **cols;
  43         /* for iteration: first is to remember start-point;
  44          *                                last was returned just before
  45          *                                next is used in case last was removed from list */
  46         iter_direction_t dir;
  47         struct list_head *first, *last, *next;
  48         int iter_row; /* used for iteration over all elements */
  49 };
  50
  51 #define _offsetof(type,member) ((char *) &(((type *) 0)->member) - (char *) 0)
  52 #define _container_of(ptr,type,member) ((type *) ((char *) (ptr) - _offsetof(type, member)))
  53 #define is_empty_row(row) (row>m->maxrow || list_empty(m->rows[row]))
  54 #define is_empty_col(col) (col>m->maxcol || list_empty(m->cols[col]))
  55 #define list_entry_by_col(h) (&list_entry(h, entry_t, col_chain)->e)
  56 #define list_entry_by_row(h) (&list_entry(h, entry_t, row_chain)->e)
  57
  58 /**
  59  * Returns the new size for an array of size old_size,
  60  *  which must at least store an entry at position min.
  61  */
  62 static INLINE int _m_new_size(int old_size, int min) {
  63         int bits = 0;
  64         assert(min>=old_size);
  65         while (min>0) {
  66                 min >>= 1;
  67                 bits++;
  68         }
  69         assert(bits < sizeof(min)*8-1);
  70         return 1 << bits;
  71 }
  72
  73 /**
  74  * Allocates space for @p count entries in the rows array and
  75  * intitializes all entries from @p start to the end.
  76  */
  77 static INLINE void _m_alloc_row(sp_matrix_t *m, int start, int count) {
  78         int p;
  79         m->rowc = count;
  80         m->rows = realloc(m->rows, m->rowc * sizeof(*m->rows));
  81         assert(m->rows);
  82         for (p=start; p<m->rowc; ++p) {
  83                 m->rows[p] = malloc(sizeof(*m->rows[p]));
  84                 assert(m->rows[p]);
  85                 INIT_LIST_HEAD(m->rows[p]);
  86         }
  87 }
  88
  89 /**
  90  * Allocates space for @p count entries in the cols array and
  91  * intitializes all entries from @p start to the end.
  92  */
  93 static INLINE void _m_alloc_col(sp_matrix_t *m, int start, int count) {
  94         int p;
  95         m->colc = count;
  96         m->cols = realloc(m->cols, m->colc * sizeof(*m->cols));
  97         assert(m->cols);
  98         for (p=start; p<m->colc; ++p) {
  99                 m->cols[p] = malloc(sizeof(*m->cols[p]));
 100                 assert(m->cols[p]);
 101                 INIT_LIST_HEAD(m->cols[p]);
 102         }
 103 }
 104
 105 /**
 106  * Searches in row @p row for the matrix element m[row, col].
 107  * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element.
 108  *         Else: NULL and @p prev points to the list_head after which the element would be inserted.
 109  */
 110 static INLINE matrix_elem_t *_m_search_in_row(const sp_matrix_t *m, int row, int col, struct list_head **prev) {
 111         struct list_head *start;
 112         start = *prev = m->rows[row];
 113         while ((*prev)->next != start && list_entry_by_row((*prev)->next)->col <= col)
 114                 *prev = (*prev)->next;
 115         if (*prev != start) {
 116                 matrix_elem_t *me = list_entry_by_row(*prev);
 117                 if (me->row == row && me->col == col)
 118                         return me;
 119         }
 120         return NULL;
 121 }
 122
 123 /**
 124  * Searches in col @p col for the matrix element m[row, col].
 125  * @return If the element exists: Element m[row, col] and @p prev points to the list_head in the entry_t holding the element.
 126  *         Else: NULL and @p prev points to the list_head after which the element would be inserted.
 127  */
 128 static INLINE matrix_elem_t *_m_search_in_col(const sp_matrix_t *m, int row, int col, struct list_head **prev) {
 129         struct list_head *start;
 130         start = *prev = m->cols[col];
 131         while ((*prev)->next != start && list_entry_by_col((*prev)->next)->row <= row)
 132                 *prev = (*prev)->next;
 133         if (*prev != start) {
 134                 matrix_elem_t *me = list_entry_by_col(*prev);
 135                 if (me->row == row && me->col == col)
 136                         return me;
 137         }
 138         return NULL;
 139 }
 140
 141 sp_matrix_t *new_matrix(int row_init, int col_init) {
 142         sp_matrix_t *res = calloc(1, sizeof(*res));
 143         res->maxrow = -1;
 144         res->maxcol = -1;
 145         _m_alloc_row(res, 0, MAX(0, row_init));
 146         _m_alloc_col(res, 0, MAX(0, col_init));
 147         return res;
 148 }
 149
 150 void del_matrix(sp_matrix_t *m) {
 151         int i;
 152         entry_t *e, *tmp;
 153
 154         for (i=0; i<m->rowc; ++i) {
 155                 list_for_each_entry_safe(entry_t, e, tmp, m->rows[i], row_chain)
 156                         free(e);
 157                 free(m->rows[i]);
 158         }
 159         for (i=0; i<m->colc; ++i)
 160                 free(m->cols[i]);
 161         free(m->rows);
 162         free(m->cols);
 163         free(m);
 164 }
 165
 166 void matrix_set(sp_matrix_t *m, int row, int col, int val) {
 167         matrix_elem_t *me = NULL;
 168         entry_t *entr;
 169         struct list_head *leftof, *above;
 170
 171         /* if necessary enlarge the matrix */
 172         if (row>m->maxrow) {
 173                 m->maxrow = row;
 174                 if (row>=m->rowc)
 175                         _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row));
 176         }
 177         if (col>m->maxcol) {
 178                 m->maxcol = col;
 179                 if (col>=m->colc)
 180                         _m_alloc_col(m, m->colc, _m_new_size(m->colc, col));
 181         }
 182
 183         /* search for existing entry */
 184         if (m->maxrow < m->maxcol)
 185                 me = _m_search_in_col(m, row, col, &above);
 186         else
 187                 me = _m_search_in_row(m, row, col, &leftof);
 188
 189         /* if it exists, set the value and return */
 190         if (me) {
 191                 if (val != 0) {
 192                         me->val = val;
 193                 } else {
 194                         entr = _container_of(me, entry_t, e);
 195                         list_del(&entr->row_chain);
 196                         list_del(&entr->col_chain);
 197                         free(entr);
 198                         m->entries--;
 199                 }
 200                 return;
 201         }
 202
 203         /* if it does not exist and 0 should be set just quit */
 204         if (val == 0)
 205                 return;
 206
 207         /* if it does not exist and val != 0 search the other direction */
 208         if (m->maxrow >= m->maxcol)
 209                 _m_search_in_col(m, row, col, &above);
 210         else
 211                 _m_search_in_row(m, row, col, &leftof);
 212         /* now leftof and above are the entry_t's prior the new one in each direction */
 213
 214         /* insert new entry */
 215         entr = malloc(sizeof(*entr));
 216         entr->e.row = row;
 217         entr->e.col = col;
 218         entr->e.val = val;
 219         list_add(&entr->row_chain, leftof);
 220         list_add(&entr->col_chain, above);
 221         m->entries++;
 222 }
 223
 224 int matrix_get(const sp_matrix_t *m, int row, int col) {
 225         struct list_head *dummy;
 226         matrix_elem_t *me;
 227
 228         if (is_empty_row(row) || is_empty_col(col))
 229                 return 0;
 230
 231         if (m->maxrow < m->maxcol)
 232                 me = _m_search_in_col(m, row, col, &dummy);
 233         else
 234                 me = _m_search_in_row(m, row, col, &dummy);
 235
 236         if (me)
 237                 assert(me->col == col && me->row == row);
 238
 239         return me?me->val:0;
 240 }
 241
 242 int matrix_get_entries(const sp_matrix_t *m) {
 243         return m->entries;
 244 }
 245
 246 int matrix_get_rowcount(const sp_matrix_t *m) {
 247         return m->maxrow+1;
 248 }
 249
 250 int matrix_get_colcount(const sp_matrix_t *m) {
 251         return m->maxcol+1;
 252 }
 253
 254 const matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row) {
 255         if (is_empty_row(row))
 256                 return NULL;
 257         m->dir = right;
 258         m->first = m->rows[row];
 259         m->last = m->first->next;
 260         m->next = m->last->next;
 261         assert (list_entry_by_row(m->last)->row == row);
 262         return list_entry_by_row(m->last);
 263 }
 264
 265 const matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col) {
 266         if (is_empty_col(col))
 267                 return NULL;
 268         m->dir = down;
 269         m->first = m->cols[col];
 270         m->last = m->first->next;
 271         m->next = m->last->next;
 272         assert (list_entry_by_col(m->last)->col == col);
 273         return list_entry_by_col(m->last);
 274 }
 275
 276 static INLINE const matrix_elem_t *matrix_first_from(sp_matrix_t *m, int startrow) {
 277         const matrix_elem_t *res;
 278         int i;
 279         for (i=startrow; i<=m->maxrow; ++i)
 280                 if ((res = matrix_row_first(m, i))) {
 281                         m->iter_row = i;
 282                         m->dir = all;
 283                         return res;
 284                 }
 285         return NULL;
 286 }
 287
 288 const matrix_elem_t *matrix_first(sp_matrix_t *m) {
 289         return matrix_first_from(m, 0);
 290 }
 291
 292 const matrix_elem_t *matrix_next(sp_matrix_t *m) {
 293         assert(m->last && "Start iteration with matrix_???_first, before calling me!");
 294         if (!m->last->next)
 295                 ;
 296         if (m->next == m->first) {
 297                 if (m->dir == all)
 298                         return matrix_first_from(m, ++m->iter_row);
 299                 else
 300                         return NULL;
 301         }
 302         m->last = m->next;
 303         m->next = m->next->next;
 304         if (m->dir == down)
 305                 return list_entry_by_col(m->last);
 306         else /* right or all */
 307                 return list_entry_by_row(m->last);
 308 }
 309
 310 static int cmp_count(const void *e1, const void *e2) {
 311         return (int *)e2 - (int *)e1;
 312 }
 313
 314 static INLINE void matrix_fill_row(sp_matrix_t *m, int row, bitset_t *fullrow) {
 315         const matrix_elem_t *e;
 316         bitset_set(fullrow, row);
 317         matrix_foreach_in_col(m, row, e)
 318                 if (!bitset_is_set(fullrow, e->row)) {
 319                         assert(0 == matrix_get(m, e->col, e->row));
 320                         matrix_set(m, e->col, e->row, e->val);
 321                         matrix_set(m, e->row, e->col, 0);
 322                 }
 323 }
 324
 325 void matrix_optimize(sp_matrix_t *m) {
 326         int i, size, redo;
 327         int *c;
 328         const matrix_elem_t *e;
 329         bitset_t *fullrow;
 330
 331         size = MAX(m->maxcol, m->maxrow)+1;
 332
 333         /* kill all double-entries (Mij and Mji are set) */
 334         matrix_foreach(m, e) {
 335                 assert(e->row != e->col && "Root has itself as arg. Ok. But the arg (=root) will alwazs have the same color as root");
 336                 int t_val = matrix_get(m, e->col, e->row);
 337                 if (t_val) {
 338                         matrix_set(m, e->col, e->row, 0);
 339                         matrix_set(m, e->row, e->col, e->val + t_val);
 340                 }
 341         }
 342
 343         c = alloca(size * sizeof(*c));
 344         redo = 1;
 345         fullrow = bitset_alloca(size);
 346         /* kill 'all' rows containing only 1 entry */
 347         while (redo) {
 348                 redo = 0;
 349                 /* count elements in rows */
 350                 memset(c, 0, size * sizeof(*c));
 351                 matrix_foreach(m, e)
 352                         c[e->row]++;
 353                 for (i=0; i<size; ++i)
 354                         if (c[i] == 1 && !bitset_is_set(fullrow, i)) {
 355                                 redo = 1;
 356                                 /* if the other row isn't empty move the e in there, else fill e's row */
 357                                 if (e = matrix_row_first(m, i), e) {
 358                                         if (c[e->col] > 0)
 359                                                 matrix_fill_row(m, e->col, fullrow);
 360                                         else
 361                                                 matrix_fill_row(m, e->row, fullrow);
 362                                 }
 363                         }
 364         }
 365
 366
 367         memset(c, 0, size * sizeof(*c));
 368         matrix_foreach(m, e)
 369                 c[e->row]++;
 370         qsort(c, size, sizeof(*c), cmp_count);
 371
 372
 373         for (i=0; i<size; ++i)
 374                 if (!bitset_is_set(fullrow, i))
 375                         matrix_fill_row(m, i, fullrow);
 376 }
 377
 378 void matrix_dump(sp_matrix_t *m, FILE *out, int factor) {
 379         int i, o, last_idx;
 380         const matrix_elem_t *e;
 381
 382         for (i=0; i <= m->maxrow; ++i) {
 383                 last_idx = -1;
 384                 matrix_foreach_in_row(m, i, e) {
 385                         for (o=last_idx+1; o<e->col; ++o)
 386                                 fprintf(out, "0");
 387                         fprintf(out, "%d", factor*e->val);
 388                         last_idx = e->col;
 389                 }
 390                 for (o=last_idx+1; o<=m->maxcol; ++o)
 391                         fprintf(out, "0");
 392                 fprintf(out, "\n");
 393         }
 394 }
 395
 396 void matrix_self_test(int d) {
 397         int i, o;
 398         const matrix_elem_t *e;
 399         sp_matrix_t *m = new_matrix(10, 10);
 400
 401         for (i=0; i<d; ++i)
 402                 for (o=0; o<d; ++o)
 403                         matrix_set(m, i, o, i*o);
 404
 405         for (i=0; i<d; ++i)
 406                 for (o=0; o<d; ++o)
 407                         assert(matrix_get(m, i, o) == i*o);
 408
 409         i = 0;
 410         matrix_foreach_in_row(m,1,e) {
 411                 assert(e->val == i);
 412                 i++;
 413         }
 414         assert(!matrix_next(m)); /*iter must finish */
 415
 416         i = 0;
 417         matrix_foreach_in_col(m,d-1,e) {
 418                 assert(e->val == i);
 419                 i += d-1;
 420         }
 421         assert(!matrix_next(m));
 422         del_matrix(m);
 423         m = new_matrix(16,16);
 424         matrix_set(m, 1,1,9);
 425         matrix_set(m, 1,2,8);
 426         matrix_set(m, 1,3,7);
 427
 428         matrix_set(m, 1,3,6);
 429         matrix_set(m, 1,2,5);
 430         matrix_set(m, 1,1,4);
 431         i = 1;
 432         matrix_foreach_in_row(m, 1, e) {
 433                 assert(e->row == 1 && e->col == i && e->val == i+3);
 434                 i++;
 435         }
 436         assert(i == 4);
 437         del_matrix(m);
 438
 439         m = new_matrix(5,5);
 440         matrix_set(m, 1,1,1);
 441         matrix_set(m, 2,2,2);
 442         matrix_set(m, 3,3,3);
 443         matrix_set(m, 3,5,4);
 444         matrix_set(m, 4,4,5);
 445         matrix_set(m, 5,5,6);
 446         for (i=1, e = matrix_first(m); e; ++i, e=matrix_next(m))
 447                 assert(e->val == i);
 448         assert(i == 7);
 449         matrix_set(m, 1,1,0);
 450         assert(5 == matrix_get_entries(m));
 451         del_matrix(m);
 452 }