2 * Sparse matrix storage with linked lists for rows and cols.
3 * I did not need floats, so this is all integer.
15 #include "sp_matrix.h"
18 typedef enum _iter_direction_t {
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 */
29 /* These specify the dimensions of the matrix.
30 * They equal the largest values ever used in matrix_set */
32 /* These are the dimensions of allocated arrays below.
33 * rowc >= maxrow and colc >= maxcol hold. */
35 /* arrays of list_head* as entry-points to rows and cols */
36 struct list_head **rows, **cols;
39 struct list_head *first, *last; /* first is to remember start-point; last was returned just before */
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)
50 * Returns the new size for an array of size old_size,
51 * which must at least store an entry at position min.
53 static INLINE int _m_new_size(int old_size, int min) {
55 assert(min>=old_size);
60 assert(bits < sizeof(min)*8-1);
65 * Allocates space for @p count entries in the rows array and
66 * intitializes all entries from @p start to the end.
68 static INLINE void _m_alloc_row(sp_matrix_t *m, int start, int count) {
71 m->rows = realloc(m->rows, m->rowc * sizeof(*m->rows));
73 for (p=start; p<m->rowc; ++p) {
74 m->rows[p] = malloc(sizeof(*m->rows[p]));
76 INIT_LIST_HEAD(m->rows[p]);
81 * Allocates space for @p count entries in the cols array and
82 * intitializes all entries from @p start to the end.
84 static INLINE void _m_alloc_col(sp_matrix_t *m, int start, int count) {
87 m->cols = realloc(m->cols, m->colc * sizeof(*m->cols));
89 for (p=start; p<m->colc; ++p) {
90 m->cols[p] = malloc(sizeof(*m->cols[p]));
92 INIT_LIST_HEAD(m->cols[p]);
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.
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)
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.
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)
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);
139 void del_matrix(sp_matrix_t *m) {
143 for (i=0; i<m->rowc; ++i) {
144 list_for_each_entry(entry_t, e, m->rows[i], row_chain)
148 for (i=0; i<m->colc; ++i)
155 void matrix_set(sp_matrix_t *m, int row, int col, int val) {
156 matrix_elem_t *me = NULL;
158 struct list_head *leftof, *above;
160 /* if necessary enlarge the matrix */
164 _m_alloc_row(m, m->rowc, _m_new_size(m->rowc, row));
169 _m_alloc_col(m, m->colc, _m_new_size(m->colc, col));
172 /* search for existing entry */
173 if (m->maxrow < m->maxcol)
174 me = _m_search_in_col(m, row, col, &above);
176 me = _m_search_in_row(m, row, col, &leftof);
178 /* if it exists, set the value and return */
183 entr = __container_of(me, entry_t, e);
184 list_del(&entr->row_chain);
185 list_del(&entr->col_chain);
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);
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 */
198 /* insert new entry */
199 entr = malloc(sizeof(*entr));
203 list_add(&entr->row_chain, leftof);
204 list_add(&entr->col_chain, above);
207 int matrix_get(const sp_matrix_t *m, int row, int col) {
208 struct list_head *dummy;
211 if (is_empty_row(row) || is_empty_col(col))
214 if (m->maxrow < m->maxcol)
215 me = _m_search_in_col(m, row, col, &dummy);
217 me = _m_search_in_row(m, row, col, &dummy);
220 assert(me->col == col && me->row == row);
225 int matrix_get_rowcount(const sp_matrix_t *m) {
229 int matrix_get_colcount(const sp_matrix_t *m) {
233 matrix_elem_t *matrix_row_first(sp_matrix_t *m, int row) {
234 if (is_empty_row(row))
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;
243 matrix_elem_t *matrix_col_first(sp_matrix_t *m, int col) {
244 if (is_empty_col(col))
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;
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)
257 m->last = m->last->next;
259 return &list_entry(m->last, entry_t, row_chain)->e;
261 return &list_entry(m->last, entry_t, col_chain)->e;
264 void matrix_dump(sp_matrix_t *m, FILE *out, int factor) {
268 for (i=0; i <= m->maxrow; ++i) {
270 matrix_foreach_in_row(m, i, e) {
271 for (o=last_idx+1; o<e->col; ++o)
273 fprintf(out, "%d", factor*e->val);
276 for (o=last_idx+1; o<=m->maxcol; ++o)
282 void matrix_self_test(int d) {
285 sp_matrix_t *m = new_matrix(10, 10);
289 matrix_set(m, i, o, i*o);
293 assert(matrix_get(m, i, o) == i*o);
296 matrix_foreach_in_row(m,1,e) {
300 assert(!matrix_next(m)); /*iter must finish */
303 matrix_foreach_in_col(m,d-1,e) {
307 assert(!matrix_next(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);
314 matrix_set(m, 1,3,6);
315 matrix_set(m, 1,2,5);
316 matrix_set(m, 1,1,4);
318 matrix_foreach_in_row(m, 1, e) {
319 assert(e->row == 1 && e->col == i && e->val == i+3);