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

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