aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_matrixsparse.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/lib/eina_matrixsparse.c')
-rw-r--r--libraries/eina/src/lib/eina_matrixsparse.c1421
1 files changed, 1421 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_matrixsparse.c b/libraries/eina/src/lib/eina_matrixsparse.c
new file mode 100644
index 0000000..3ac0439
--- /dev/null
+++ b/libraries/eina/src/lib/eina_matrixsparse.c
@@ -0,0 +1,1421 @@
1/* EINA - EFL data type library
2 * Copyright (C) 2009 Gustavo Sverzut Barbieri
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library;
16 * if not, see <http://www.gnu.org/licenses/>.
17 */
18
19
20/**
21 * @page tutorial_matrixsparse_page Sparse Matrix Tutorial
22 *
23 * to be written...
24 *
25 */
26
27#ifdef HAVE_CONFIG_H
28# include "config.h"
29#endif
30
31#include <stdlib.h>
32#include <stdio.h>
33#include <string.h>
34#include <assert.h>
35
36#ifdef HAVE_EVIL
37# include <Evil.h>
38#endif
39
40#include "eina_config.h"
41#include "eina_private.h"
42#include "eina_error.h"
43#include "eina_log.h"
44#include "eina_magic.h"
45#include "eina_mempool.h"
46
47/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
48#include "eina_safety_checks.h"
49#include "eina_matrixsparse.h"
50
51
52/*============================================================================*
53* Local *
54*============================================================================*/
55
56/**
57 * @cond LOCAL
58 */
59
60static const char EINA_MAGIC_MATRIXSPARSE_STR[] = "Eina Matrixsparse";
61static const char EINA_MAGIC_MATRIXSPARSE_ROW_STR[] = "Eina Matrixsparse Row";
62static const char EINA_MAGIC_MATRIXSPARSE_CELL_STR[] = "Eina Matrixsparse Cell";
63static const char EINA_MAGIC_MATRIXSPARSE_ITERATOR_STR[] =
64 "Eina Matrixsparse Iterator";
65static const char EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR_STR[] =
66 "Eina Matrixsparse Row Accessor";
67static const char EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR_STR[] =
68 "Eina Matrixsparse Row Iterator";
69static const char EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR_STR[] =
70 "Eina Matrixsparse Cell Accessor";
71static const char EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR_STR[] =
72 "Eina Matrixsparse Cell Iterator";
73
74
75#define EINA_MAGIC_CHECK_MATRIXSPARSE(d, ...) \
76 do { \
77 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE)) \
78 { \
79 EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE); \
80 return __VA_ARGS__; \
81 } \
82 } while(0)
83
84#define EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(d, ...) \
85 do { \
86 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_ROW)) \
87 { \
88 EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_ROW); \
89 return __VA_ARGS__; \
90 } \
91 } while(0)
92
93#define EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(d, ...) \
94 do { \
95 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_CELL)) \
96 { \
97 EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_CELL); \
98 return __VA_ARGS__; \
99 } \
100 } while(0)
101
102#define EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(d, ...) \
103 do { \
104 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_ITERATOR)) \
105 { \
106 EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_ITERATOR); \
107 return __VA_ARGS__; \
108 } \
109 } while(0)
110
111struct _Eina_Matrixsparse_Cell
112{
113 Eina_Matrixsparse_Cell *next;
114 Eina_Matrixsparse_Cell *prev;
115
116 void *data;
117 unsigned long col;
118
119 Eina_Matrixsparse_Row *parent;
120
121 EINA_MAGIC
122};
123
124struct _Eina_Matrixsparse_Row
125{
126 Eina_Matrixsparse_Row *next;
127 Eina_Matrixsparse_Row *prev;
128
129 Eina_Matrixsparse_Cell *cols;
130 Eina_Matrixsparse_Cell *last_col;
131 Eina_Matrixsparse_Cell *last_used; /* fast sequential access */
132 unsigned long row;
133
134 Eina_Matrixsparse *parent;
135
136 EINA_MAGIC
137};
138
139struct _Eina_Matrixsparse
140{
141 Eina_Matrixsparse_Row *rows;
142 Eina_Matrixsparse_Row *last_row;
143 Eina_Matrixsparse_Row *last_used; /* fast sequential access */
144
145 struct
146 {
147 unsigned long rows;
148 unsigned long cols;
149 } size;
150
151 struct
152 {
153 void (*func)(void *user_data, void *cell_data);
154 void *user_data;
155 } free;
156
157 EINA_MAGIC
158};
159
160typedef struct _Eina_Matrixsparse_Iterator Eina_Matrixsparse_Iterator;
161typedef struct _Eina_Matrixsparse_Iterator_Complete
162Eina_Matrixsparse_Iterator_Complete;
163
164struct _Eina_Matrixsparse_Iterator
165{
166 Eina_Iterator iterator;
167
168 const Eina_Matrixsparse *m;
169 struct
170 {
171 const Eina_Matrixsparse_Row *row;
172 const Eina_Matrixsparse_Cell *col;
173 } ref;
174
175 EINA_MAGIC
176};
177
178struct _Eina_Matrixsparse_Iterator_Complete
179{
180 Eina_Iterator iterator;
181
182 const Eina_Matrixsparse *m;
183 struct
184 {
185 const Eina_Matrixsparse_Row *row;
186 const Eina_Matrixsparse_Cell *col;
187 } ref;
188
189 struct
190 {
191 unsigned long row, col;
192 } idx;
193
194 struct
195 {
196 Eina_Matrixsparse_Row row;
197 Eina_Matrixsparse_Cell col;
198 } dummy;
199
200 EINA_MAGIC
201};
202
203/**
204 * @todo Eina_Matrixsparse_Row_Iterator: iterator over rows in matrix
205 * @todo Eina_Matrixsparse_Row_Accessor: accessor over rows in matrix
206 * @todo Eina_Matrixsparse_Cell_Iterator: iterator over cells in row
207 * @todo Eina_Matrixsparse_Cell_Accessor: accessor over cells in row
208 */
209
210static int _eina_matrixsparse_log_dom = -1;
211
212#ifdef ERR
213#undef ERR
214#endif
215#define ERR(...) EINA_LOG_DOM_ERR(_eina_matrixsparse_log_dom, __VA_ARGS__)
216
217#ifdef DBG
218#undef DBG
219#endif
220#define DBG(...) EINA_LOG_DOM_DBG(_eina_matrixsparse_log_dom, __VA_ARGS__)
221
222static Eina_Mempool *_eina_matrixsparse_cell_mp = NULL;
223static Eina_Mempool *_eina_matrixsparse_row_mp = NULL;
224
225static inline void
226_eina_matrixsparse_cell_free(Eina_Matrixsparse_Cell *c, void (*free_func)(
227 void *,
228 void *), void *user_data)
229{
230 if (free_func)
231 free_func(user_data, c->data);
232
233 EINA_MAGIC_SET(c, EINA_MAGIC_NONE);
234 eina_mempool_free(_eina_matrixsparse_cell_mp, c);
235}
236
237static inline void
238_eina_matrixsparse_cell_unlink(Eina_Matrixsparse_Cell *c)
239{
240 Eina_Matrixsparse_Row *r = c->parent;
241
242 if (r->last_used == c)
243 {
244 if (c->next)
245 r->last_used = c->next;
246 else
247 r->last_used = c->prev;
248 }
249
250 if (r->last_col == c)
251 r->last_col = c->prev;
252
253 if (r->cols == c)
254 r->cols = c->next;
255
256 if (c->next && c->prev)
257 {
258 c->next->prev = c->prev;
259 c->prev->next = c->next;
260 }
261 else if (c->next)
262 c->next->prev = NULL;
263 else if (c->prev)
264 c->prev->next = NULL;
265}
266
267static inline void
268_eina_matrixsparse_row_cells_free(Eina_Matrixsparse_Row *r, void (*free_func)(
269 void *,
270 void *), void *user_data)
271{
272 Eina_Matrixsparse_Cell *c = r->cols;
273 while (c)
274 {
275 Eina_Matrixsparse_Cell *c_aux = c;
276 c = c->next;
277 _eina_matrixsparse_cell_free(c_aux, free_func, user_data);
278 }
279}
280
281static inline void
282_eina_matrixsparse_row_free(Eina_Matrixsparse_Row *r, void (*free_func)(void *,
283 void *),
284 void *user_data)
285{
286 _eina_matrixsparse_row_cells_free(r, free_func, user_data);
287 EINA_MAGIC_SET(r, EINA_MAGIC_NONE);
288 eina_mempool_free(_eina_matrixsparse_row_mp, r);
289}
290
291static inline void
292_eina_matrixsparse_row_unlink(Eina_Matrixsparse_Row *r)
293{
294 Eina_Matrixsparse *m = r->parent;
295
296 if (m->last_used == r)
297 {
298 if (r->next)
299 m->last_used = r->next;
300 else
301 m->last_used = r->prev;
302 }
303
304 if (m->last_row == r)
305 m->last_row = r->prev;
306
307 if (m->rows == r)
308 m->rows = r->next;
309
310 if (r->next && r->prev)
311 {
312 r->next->prev = r->prev;
313 r->prev->next = r->next;
314 }
315 else if (r->next)
316 r->next->prev = NULL;
317 else if (r->prev)
318 r->prev->next = NULL;
319}
320
321static inline void
322_eina_matrixsparse_row_find_parms_get(const Eina_Matrixsparse *m,
323 unsigned long row,
324 Eina_Matrixsparse_Row **p_r,
325 int *p_dir)
326{
327 Eina_Matrixsparse_Row *r;
328 unsigned long dist;
329 int dir;
330
331 dist = row - m->rows->row;
332 r = m->rows;
333 dir = 1;
334 if (dist > m->last_row->row - row)
335 {
336 dist = m->last_row->row - row;
337 r = m->last_row;
338 dir = -1;
339 }
340
341 if (m->last_used)
342 {
343 if (m->last_used->row < row)
344 {
345 if (dist > row - m->last_used->row)
346 {
347/* dist = row = m->last_used->row; */
348 r = m->last_used;
349 dir = 1;
350 }
351 }
352 else if (dist > m->last_used->row - row)
353 {
354/* dist = m->last_used->row - row; */
355 r = m->last_used;
356 dir = -1;
357 }
358 }
359
360 *p_r = r;
361 *p_dir = dir;
362}
363
364static inline void
365_eina_matrixsparse_row_cell_find_parms_get(const Eina_Matrixsparse_Row *r,
366 unsigned long col,
367 Eina_Matrixsparse_Cell **p_c,
368 int *p_dir)
369{
370 Eina_Matrixsparse_Cell *c;
371 unsigned long dist;
372 int dir;
373
374 dist = col - r->cols->col;
375 c = r->cols;
376 dir = 1;
377 if (dist > r->last_col->col - col)
378 {
379 dist = r->last_col->col - col;
380 c = r->last_col;
381 dir = -1;
382 }
383
384 if (r->last_used)
385 {
386 if (r->last_used->col < col)
387 {
388 if (dist > col - r->last_used->col)
389 {
390/* dist = col = r->last_used->col; */
391 c = r->last_used;
392 dir = 1;
393 }
394 }
395 else if (dist > r->last_used->col - col)
396 {
397/* dist = r->last_used->col - col; */
398 c = r->last_used;
399 dir = -1;
400 }
401 }
402
403 *p_c = c;
404 *p_dir = dir;
405}
406
407static inline Eina_Matrixsparse_Row *
408_eina_matrixsparse_row_idx_get(const Eina_Matrixsparse *m, unsigned long row)
409{
410 Eina_Matrixsparse_Row *r;
411 int dir;
412
413 if (!m->rows)
414 return NULL;
415
416 if (m->rows->row == row)
417 return m->rows;
418 else if (m->rows->row > row)
419 return NULL;
420
421 if (m->last_row->row == row)
422 return m->last_row;
423 else if (m->last_row->row < row)
424 return NULL;
425
426 if ((m->last_used) && (m->last_used->row == row))
427 return m->last_used;
428
429 _eina_matrixsparse_row_find_parms_get(m, row, &r, &dir);
430 assert(dir != 0);
431 if (dir > 0)
432 {
433 for (; r; r = r->next)
434 if (r->row == row)
435 {
436 ((Eina_Matrixsparse *)m)->last_used = r;
437 return r;
438 }
439 else if (r->row > row)
440 return NULL;
441
442 }
443 else if (dir < 0)
444 {
445 for (; r; r = r->prev)
446 if (r->row == row)
447 {
448 ((Eina_Matrixsparse *)m)->last_used = r;
449 return r;
450 }
451 else if (r->row < row)
452 return NULL;
453 }
454
455 return NULL;
456}
457
458static inline Eina_Matrixsparse_Cell *
459_eina_matrixsparse_row_cell_idx_get(const Eina_Matrixsparse_Row *r,
460 unsigned long col)
461{
462 Eina_Matrixsparse_Cell *c;
463 int dir;
464
465 if (!r->cols)
466 return NULL;
467
468 if (r->cols->col == col)
469 return r->cols;
470 else if (r->cols->col > col)
471 return NULL;
472
473 if (r->last_col->col == col)
474 return r->last_col;
475 else if (r->last_col->col < col)
476 return NULL;
477
478 if ((r->last_used) && (r->last_used->col == col))
479 return r->last_used;
480
481 _eina_matrixsparse_row_cell_find_parms_get(r, col, &c, &dir);
482 assert(dir != 0);
483 if (dir > 0)
484 {
485 for (; r; c = c->next)
486 if (c->col == col)
487 {
488 ((Eina_Matrixsparse_Row *)r)->last_used = c;
489 return c;
490 }
491 else if (c->col > col)
492 return NULL;
493
494 }
495 else if (dir < 0)
496 {
497 for (; r; c = c->prev)
498 if (c->col == col)
499 {
500 ((Eina_Matrixsparse_Row *)r)->last_used = c;
501 return c;
502 }
503 else if (c->col < col)
504 return NULL;
505 }
506
507 return NULL;
508}
509
510static inline Eina_Matrixsparse_Cell *
511_eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m,
512 unsigned long row,
513 unsigned long col)
514{
515 Eina_Matrixsparse_Row *r = _eina_matrixsparse_row_idx_get(m, row);
516 if (!r)
517 return NULL;
518
519 return _eina_matrixsparse_row_cell_idx_get(r, col);
520}
521
522static inline void
523_eina_matrixsparse_row_idx_siblings_find(const Eina_Matrixsparse *m,
524 unsigned long row,
525 Eina_Matrixsparse_Row **p_prev,
526 Eina_Matrixsparse_Row **p_next)
527{
528 Eina_Matrixsparse_Row *r;
529 int dir;
530
531 _eina_matrixsparse_row_find_parms_get(m, row, &r, &dir);
532 assert(dir != 0);
533 if (dir > 0)
534 {
535 for (; r; r = r->next)
536 if (r->row > row)
537 break;
538
539 assert(r != NULL);
540 *p_prev = r->prev;
541 *p_next = r;
542 }
543 else if (dir < 0)
544 {
545 for (; r; r = r->prev)
546 if (r->row < row)
547 break;
548
549 assert(r != NULL);
550 *p_prev = r;
551 *p_next = r->next;
552 }
553}
554
555static inline void
556_eina_matrixsparse_row_cell_idx_siblings_find(const Eina_Matrixsparse_Row *r,
557 unsigned long col,
558 Eina_Matrixsparse_Cell **p_prev,
559 Eina_Matrixsparse_Cell **p_next)
560{
561 Eina_Matrixsparse_Cell *c;
562 int dir;
563
564 _eina_matrixsparse_row_cell_find_parms_get(r, col, &c, &dir);
565 assert(dir != 0);
566 if (dir > 0)
567 {
568 for (; c; c = c->next)
569 if (c->col > col)
570 break;
571
572 assert(c != NULL);
573 *p_prev = c->prev;
574 *p_next = c;
575 }
576 else if (dir < 0)
577 {
578 for (; c; c = c->prev)
579 if (c->col < col)
580 break;
581
582 assert(c != NULL);
583 *p_prev = c;
584 *p_next = c->next;
585 }
586}
587
588static inline Eina_Matrixsparse_Row *
589_eina_matrixsparse_row_idx_add(Eina_Matrixsparse *m, unsigned long row)
590{
591 Eina_Matrixsparse_Row *r = eina_mempool_malloc
592 (_eina_matrixsparse_row_mp, sizeof(Eina_Matrixsparse_Row));
593 if (!r)
594 return NULL;
595
596 if (!m->rows)
597 {
598 r->prev = NULL;
599 r->next = NULL;
600 m->rows = r;
601 m->last_row = r;
602 }
603 else if (row < m->rows->row)
604 {
605 r->prev = NULL;
606 r->next = m->rows;
607 m->rows->prev = r;
608 m->rows = r;
609 }
610 else if (row > m->last_row->row)
611 {
612 r->prev = m->last_row;
613 m->last_row->next = r;
614 r->next = NULL;
615 m->last_row = r;
616 }
617 else
618 {
619 Eina_Matrixsparse_Row *prev = NULL, *next = NULL;
620 _eina_matrixsparse_row_idx_siblings_find(m, row, &prev, &next);
621 assert(prev != NULL);
622 assert(next != NULL);
623 r->prev = prev;
624 r->next = next;
625 prev->next = r;
626 next->prev = r;
627 }
628
629 r->cols = NULL;
630 r->last_col = NULL;
631 r->last_used = NULL;
632 r->row = row;
633 r->parent = m;
634 EINA_MAGIC_SET(r, EINA_MAGIC_MATRIXSPARSE_ROW);
635 m->last_used = r;
636 return r;
637}
638
639static inline Eina_Matrixsparse_Cell *
640_eina_matrixsparse_row_cell_idx_add(Eina_Matrixsparse_Row *r,
641 unsigned long col,
642 const void *data)
643{
644 Eina_Matrixsparse_Cell *c = eina_mempool_malloc
645 (_eina_matrixsparse_cell_mp, sizeof(Eina_Matrixsparse_Cell));
646 if (!c)
647 return NULL;
648
649 if (!r->cols)
650 {
651 c->prev = NULL;
652 c->next = NULL;
653 r->cols = c;
654 r->last_col = c;
655 }
656 else if (col < r->cols->col)
657 {
658 c->prev = NULL;
659 c->next = r->cols;
660 r->cols->prev = c;
661 r->cols = c;
662 }
663 else if (col > r->last_col->col)
664 {
665 c->prev = r->last_col;
666 r->last_col->next = c;
667 c->next = NULL;
668 r->last_col = c;
669 }
670 else
671 {
672 Eina_Matrixsparse_Cell *prev = NULL, *next = NULL;
673 _eina_matrixsparse_row_cell_idx_siblings_find(r, col, &prev, &next);
674 assert(prev != NULL);
675 assert(next != NULL);
676 c->prev = prev;
677 c->next = next;
678 prev->next = c;
679 next->prev = c;
680 }
681
682 c->data = (void *)data;
683 c->col = col;
684 c->parent = r;
685 EINA_MAGIC_SET(c, EINA_MAGIC_MATRIXSPARSE_CELL);
686 r->last_used = c;
687 return c;
688}
689
690static inline Eina_Bool
691_eina_matrixsparse_cell_idx_add(Eina_Matrixsparse *m,
692 unsigned long row,
693 unsigned long col,
694 const void *data)
695{
696 Eina_Matrixsparse_Row *r = _eina_matrixsparse_row_idx_get(m, row);
697 if (!r)
698 r = _eina_matrixsparse_row_idx_add(m, row);
699
700 if (!r)
701 return 0;
702
703 if (_eina_matrixsparse_row_cell_idx_add(r, col, data))
704 return 1;
705
706 if (r->cols)
707 return 0;
708
709 _eina_matrixsparse_row_unlink(r);
710 _eina_matrixsparse_row_free(r, m->free.func, m->free.user_data);
711 return 0;
712}
713
714/*============================================================================*
715* Iterators *
716*============================================================================*/
717static Eina_Bool
718_eina_matrixsparse_iterator_next(Eina_Matrixsparse_Iterator *it, void **data)
719{
720 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, EINA_FALSE);
721
722 /* do not touch it->idx */
723
724 if (!it->ref.col)
725 return 0;
726
727 *data = (Eina_Matrixsparse_Cell *)it->ref.col;
728
729 it->ref.col = it->ref.col->next;
730 if (!it->ref.col)
731 {
732 it->ref.row = it->ref.row->next;
733 if (it->ref.row)
734 it->ref.col = it->ref.row->cols;
735 }
736
737 return 1;
738}
739
740static Eina_Matrixsparse *
741_eina_matrixsparse_iterator_get_container(Eina_Matrixsparse_Iterator *it)
742{
743 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, NULL);
744 return (Eina_Matrixsparse *)it->m;
745}
746
747static void
748_eina_matrixsparse_iterator_free(Eina_Matrixsparse_Iterator *it)
749{
750 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it);
751 EINA_MAGIC_SET(it, EINA_MAGIC_NONE);
752 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE);
753 free(it);
754}
755
756static Eina_Bool
757_eina_matrixsparse_iterator_complete_next(
758 Eina_Matrixsparse_Iterator_Complete *it,
759 void **data)
760{
761 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, EINA_FALSE);
762
763 if (it->idx.row >= it->m->size.rows)
764 return 0;
765
766 if (it->dummy.col.data)
767 ERR("Last iterator call changed dummy cell!");
768
769 if ((it->ref.col) &&
770 (it->ref.col->col == it->idx.col) &&
771 (it->ref.row->row == it->idx.row))
772 {
773 *data = (Eina_Matrixsparse_Cell *)it->ref.col;
774 it->ref.col = it->ref.col->next;
775 if (!it->ref.col)
776 {
777 it->ref.row = it->ref.row->next;
778 if (it->ref.row)
779 it->ref.col = it->ref.row->cols;
780 }
781 }
782 else
783 {
784 it->dummy.col.data = NULL;
785 it->dummy.col.col = it->idx.col;
786 it->dummy.row.row = it->idx.row;
787 *data = &it->dummy.col;
788 }
789
790 it->idx.col++;
791 if (it->idx.col == it->m->size.cols)
792 {
793 it->idx.col = 0;
794 it->idx.row++;
795 }
796
797 return 1;
798}
799
800static Eina_Matrixsparse *
801_eina_matrixsparse_iterator_complete_get_container(
802 Eina_Matrixsparse_Iterator_Complete *it)
803{
804 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, NULL);
805 return (Eina_Matrixsparse *)it->m;
806}
807
808static void
809_eina_matrixsparse_iterator_complete_free(
810 Eina_Matrixsparse_Iterator_Complete *it)
811{
812 EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it);
813
814 if (it->dummy.col.data)
815 ERR("Last iterator call changed dummy cell!");
816
817 EINA_MAGIC_SET(it, EINA_MAGIC_NONE);
818 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE);
819 free(it);
820}
821
822
823/**
824 * @endcond
825 */
826
827/*============================================================================*
828* Global *
829*============================================================================*/
830
831/**
832 * @internal
833 * @brief Initialize the matrixsparse module.
834 *
835 * @return #EINA_TRUE on success, #EINA_FALSE on failure.
836 *
837 * This function sets up the matrixsparse module of Eina. It is called by
838 * eina_init().
839 *
840 * This function creates mempool to speed up matrix rows and cells
841 * management, using EINA_MEMPOOL environment variable if it is set to
842 * choose the memory pool type to use.
843 *
844 * @see eina_init()
845 */
846Eina_Bool
847eina_matrixsparse_init(void)
848{
849 const char *choice, *tmp;
850
851 _eina_matrixsparse_log_dom = eina_log_domain_register("eina_matrixsparse",
852 EINA_LOG_COLOR_DEFAULT);
853 if (_eina_matrixsparse_log_dom < 0)
854 {
855 EINA_LOG_ERR("Could not register log domain: eina_matrixsparse");
856 return EINA_FALSE;
857 }
858
859#ifdef EINA_DEFAULT_MEMPOOL
860 choice = "pass_through";
861#else
862 choice = "chained_mempool";
863#endif
864 tmp = getenv("EINA_MEMPOOL");
865 if (tmp && tmp[0])
866 choice = tmp;
867
868 _eina_matrixsparse_cell_mp = eina_mempool_add
869 (choice,
870 "matrixsparse_cell",
871 NULL,
872 sizeof (Eina_Matrixsparse_Cell),
873 120);
874 if (!_eina_matrixsparse_cell_mp)
875 {
876 ERR(
877 "Mempool for matrixsparse_cell cannot be allocated in matrixsparse init.");
878 goto on_init_fail;
879 }
880
881 _eina_matrixsparse_row_mp = eina_mempool_add
882 (choice, "matrixsparse_row", NULL, sizeof (Eina_Matrixsparse_Row), 120);
883 if (!_eina_matrixsparse_row_mp)
884 {
885 ERR(
886 "Mempool for matrixsparse_row cannot be allocated in matrixsparse init.");
887 goto on_init_fail;
888 }
889
890#define EMS(n) eina_magic_string_static_set(n, n ## _STR)
891 EMS(EINA_MAGIC_MATRIXSPARSE);
892 EMS(EINA_MAGIC_MATRIXSPARSE_ROW);
893 EMS(EINA_MAGIC_MATRIXSPARSE_CELL);
894 EMS(EINA_MAGIC_MATRIXSPARSE_ITERATOR);
895 EMS(EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR);
896 EMS(EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR);
897 EMS(EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR);
898 EMS(EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR);
899#undef EMS
900
901 return EINA_TRUE;
902
903on_init_fail:
904 eina_log_domain_unregister(_eina_matrixsparse_log_dom);
905 _eina_matrixsparse_log_dom = -1;
906 return EINA_FALSE;
907}
908
909/**
910 * @internal
911 * @brief Shut down the matrixsparse module.
912 *
913 * @return #EINA_TRUE on success, #EINA_FALSE on failure.
914 *
915 * This function shuts down the matrixsparse module set up by
916 * eina_matrixsparse_init(). It is called by eina_shutdown().
917 *
918 * @see eina_shutdown()
919 */
920Eina_Bool
921eina_matrixsparse_shutdown(void)
922{
923 eina_mempool_del(_eina_matrixsparse_row_mp);
924 eina_mempool_del(_eina_matrixsparse_cell_mp);
925
926 eina_log_domain_unregister(_eina_matrixsparse_log_dom);
927 _eina_matrixsparse_log_dom = -1;
928 return EINA_TRUE;
929}
930
931/*============================================================================*
932* API *
933*============================================================================*/
934
935EAPI Eina_Matrixsparse *
936eina_matrixsparse_new(unsigned long rows, unsigned long cols, void (*free_func)(
937 void *user_data,
938 void *cell_data), const void *user_data)
939{
940 Eina_Matrixsparse *m;
941
942 EINA_SAFETY_ON_FALSE_RETURN_VAL(rows > 0, NULL);
943 EINA_SAFETY_ON_FALSE_RETURN_VAL(cols > 0, NULL);
944
945 m = malloc(sizeof(Eina_Matrixsparse));
946 if (!m)
947 {
948 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
949 return NULL;
950 }
951
952 EINA_MAGIC_SET(m, EINA_MAGIC_MATRIXSPARSE);
953
954 m->rows = NULL;
955 m->last_row = NULL;
956 m->last_used = NULL;
957
958 m->size.rows = rows;
959 m->size.cols = cols;
960 m->free.func = free_func;
961 m->free.user_data = (void *)user_data;
962
963 eina_error_set(0);
964 return m;
965}
966
967EAPI void
968eina_matrixsparse_free(Eina_Matrixsparse *m)
969{
970 void (*free_func)(void *, void *);
971 void *user_data;
972
973 Eina_Matrixsparse_Row *r;
974 EINA_MAGIC_CHECK_MATRIXSPARSE(m);
975
976 free_func = m->free.func;
977 user_data = m->free.user_data;
978
979 r = m->rows;
980 while (r)
981 {
982 Eina_Matrixsparse_Row *r_aux = r;
983 r = r->next;
984 _eina_matrixsparse_row_free(r_aux, free_func, user_data);
985 }
986
987 EINA_MAGIC_SET(m, EINA_MAGIC_NONE);
988 free(m);
989}
990
991EAPI void
992eina_matrixsparse_size_get(const Eina_Matrixsparse *m,
993 unsigned long *rows,
994 unsigned long *cols)
995{
996 if (rows)
997 *rows = 0;
998
999 if (cols)
1000 *cols = 0;
1001
1002 EINA_MAGIC_CHECK_MATRIXSPARSE(m);
1003 if (rows)
1004 *rows = m->size.rows;
1005
1006 if (cols)
1007 *cols = m->size.cols;
1008}
1009
1010EAPI Eina_Bool
1011eina_matrixsparse_size_set(Eina_Matrixsparse *m,
1012 unsigned long rows,
1013 unsigned long cols)
1014{
1015 Eina_Bool update_last_used_row;
1016 Eina_Matrixsparse_Row *r;
1017 void (*free_func)(void *, void *);
1018 void *user_data;
1019
1020 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1021 EINA_SAFETY_ON_FALSE_RETURN_VAL(rows > 0, 0);
1022 EINA_SAFETY_ON_FALSE_RETURN_VAL(cols > 0, 0);
1023
1024 if ((rows == m->size.rows) && (cols == m->size.cols))
1025 return 1;
1026
1027 update_last_used_row = ((m->last_used) && (m->last_used->row >= rows));
1028 free_func = m->free.func;
1029 user_data = m->free.user_data;
1030
1031 r = m->last_row;
1032 while (r && r->row >= rows)
1033 {
1034 Eina_Matrixsparse_Row *r_aux = r;
1035 r = r->prev;
1036 _eina_matrixsparse_row_free(r_aux, free_func, user_data);
1037 }
1038 if (!r)
1039 {
1040 m->last_row = NULL;
1041 m->rows = NULL;
1042 }
1043 else if (r != m->last_row)
1044 {
1045 r->next = NULL;
1046 m->last_row = r;
1047 }
1048
1049 if (update_last_used_row)
1050 m->last_used = m->last_row;
1051
1052 r = m->rows;
1053 while (r)
1054 {
1055 Eina_Matrixsparse_Cell *c = r->last_col;
1056 Eina_Bool update_last_used_col;
1057 update_last_used_col = ((r->last_used) && (r->last_used->col >= cols));
1058 while (c && c->col >= cols)
1059 {
1060 Eina_Matrixsparse_Cell *c_aux = c;
1061 c = c->prev;
1062 _eina_matrixsparse_cell_free(c_aux, free_func, user_data);
1063 }
1064 if (!c)
1065 {
1066 Eina_Matrixsparse_Row *r_aux = r;
1067 r->cols = NULL;
1068 r->last_col = NULL;
1069 if (r->next)
1070 r->next->prev = r->prev;
1071 else
1072 m->last_row = r->prev;
1073
1074 if (r->prev)
1075 r->prev->next = r->next;
1076 else
1077 m->rows = r->next;
1078
1079 r = r->next;
1080 _eina_matrixsparse_row_free(r_aux, free_func, user_data);
1081 }
1082 else
1083 {
1084 if (c != r->last_col)
1085 {
1086 c->next = NULL;
1087 r->last_col = c;
1088 }
1089
1090 if (update_last_used_col)
1091 r->last_used = r->last_col;
1092
1093 r = r->next;
1094 }
1095 }
1096
1097 update_last_used_row = 0;
1098 if (m->last_used)
1099 {
1100 if (m->last_row)
1101 update_last_used_row = m->last_used->row > m->last_row->row;
1102 else
1103 update_last_used_row = 1;
1104 }
1105
1106 if (update_last_used_row)
1107 m->last_used = m->last_row;
1108
1109 m->size.rows = rows;
1110 m->size.cols = cols;
1111 return 1;
1112}
1113
1114EAPI Eina_Bool
1115eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m,
1116 unsigned long row,
1117 unsigned long col,
1118 Eina_Matrixsparse_Cell **cell)
1119{
1120 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1121 EINA_SAFETY_ON_NULL_RETURN_VAL(cell, 0);
1122 *cell = NULL;
1123 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1124 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1125 *cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1126 return 1;
1127}
1128
1129EAPI void *
1130eina_matrixsparse_cell_data_get(const Eina_Matrixsparse_Cell *cell)
1131{
1132 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, NULL);
1133 return cell->data;
1134}
1135
1136EAPI void *
1137eina_matrixsparse_data_idx_get(const Eina_Matrixsparse *m,
1138 unsigned long row,
1139 unsigned long col)
1140{
1141 Eina_Matrixsparse_Cell *c;
1142 EINA_MAGIC_CHECK_MATRIXSPARSE(m, NULL);
1143 c = _eina_matrixsparse_cell_idx_get(m, row, col);
1144 if (c)
1145 return c->data;
1146 else
1147 return NULL;
1148}
1149
1150EAPI Eina_Bool
1151eina_matrixsparse_cell_position_get(const Eina_Matrixsparse_Cell *cell,
1152 unsigned long *row,
1153 unsigned long *col)
1154{
1155 if (row)
1156 *row = 0;
1157
1158 if (col)
1159 *col = 0;
1160
1161 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1162 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1163 if (row)
1164 *row = cell->parent->row;
1165
1166 if (col)
1167 *col = cell->col;
1168
1169 return 1;
1170}
1171
1172EAPI Eina_Bool
1173eina_matrixsparse_cell_data_replace(Eina_Matrixsparse_Cell *cell,
1174 const void *data,
1175 void **p_old)
1176{
1177 if (p_old)
1178 *p_old = NULL;
1179
1180 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1181
1182 if (p_old)
1183 *p_old = cell->data;
1184
1185 cell->data = (void *)data;
1186 return 1;
1187}
1188
1189EAPI Eina_Bool
1190eina_matrixsparse_cell_data_set(Eina_Matrixsparse_Cell *cell, const void *data)
1191{
1192 Eina_Matrixsparse *m;
1193
1194 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1195 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1196 EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0);
1197
1198 m = cell->parent->parent;
1199
1200 if (m->free.func)
1201 m->free.func(m->free.user_data, cell->data);
1202
1203 cell->data = (void *)data;
1204 return 1;
1205}
1206
1207EAPI Eina_Bool
1208eina_matrixsparse_data_idx_replace(Eina_Matrixsparse *m,
1209 unsigned long row,
1210 unsigned long col,
1211 const void *data,
1212 void **p_old)
1213{
1214 Eina_Matrixsparse_Cell *cell;
1215
1216 if (p_old)
1217 *p_old = NULL;
1218
1219 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1220 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1221 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1222
1223 cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1224 if (cell)
1225 {
1226 if (p_old)
1227 *p_old = cell->data;
1228
1229 cell->data = (void *)data;
1230 return 1;
1231 }
1232
1233 return _eina_matrixsparse_cell_idx_add(m, row, col, data);
1234}
1235
1236EAPI Eina_Bool
1237eina_matrixsparse_data_idx_set(Eina_Matrixsparse *m,
1238 unsigned long row,
1239 unsigned long col,
1240 const void *data)
1241{
1242 Eina_Matrixsparse_Cell *cell;
1243
1244 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1245 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1246 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1247
1248 cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1249 if (cell)
1250 {
1251 if (m->free.func)
1252 m->free.func(m->free.user_data, cell->data);
1253
1254 cell->data = (void *)data;
1255 return 1;
1256 }
1257
1258 return _eina_matrixsparse_cell_idx_add(m, row, col, data);
1259}
1260
1261EAPI Eina_Bool
1262eina_matrixsparse_row_idx_clear(Eina_Matrixsparse *m, unsigned long row)
1263{
1264 Eina_Matrixsparse_Row *r;
1265
1266 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1267 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1268
1269 r = _eina_matrixsparse_row_idx_get(m, row);
1270 if (!r)
1271 return 1;
1272
1273 _eina_matrixsparse_row_unlink(r);
1274 _eina_matrixsparse_row_free(r, m->free.func, m->free.user_data);
1275
1276 return 1;
1277}
1278
1279EAPI Eina_Bool
1280eina_matrixsparse_column_idx_clear(Eina_Matrixsparse *m, unsigned long col)
1281{
1282 Eina_Matrixsparse_Row *r;
1283 void (*free_func)(void *, void *);
1284 void *user_data;
1285
1286 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1287 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1288
1289 free_func = m->free.func;
1290 user_data = m->free.user_data;
1291
1292 for (r = m->rows; r; )
1293 {
1294 Eina_Matrixsparse_Row *r_aux = r;
1295 Eina_Matrixsparse_Cell *c;
1296
1297 c = _eina_matrixsparse_row_cell_idx_get(r, col);
1298 r = r->next;
1299
1300 if (!c)
1301 continue;
1302
1303 if ((r_aux->cols != c) || (r_aux->last_col != c))
1304 {
1305 _eina_matrixsparse_cell_unlink(c);
1306 _eina_matrixsparse_cell_free(c, free_func, user_data);
1307 }
1308 else
1309 {
1310 _eina_matrixsparse_row_unlink(r_aux);
1311 _eina_matrixsparse_row_free(r_aux, free_func, user_data);
1312 }
1313 }
1314
1315 return 1;
1316}
1317
1318EAPI Eina_Bool
1319eina_matrixsparse_cell_idx_clear(Eina_Matrixsparse *m,
1320 unsigned long row,
1321 unsigned long col)
1322{
1323 Eina_Matrixsparse_Cell *c;
1324
1325 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1326 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1327 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1328
1329 c = _eina_matrixsparse_cell_idx_get(m, row, col);
1330 if (!c)
1331 return 1;
1332
1333 _eina_matrixsparse_cell_unlink(c);
1334 _eina_matrixsparse_cell_free(c, m->free.func, m->free.user_data);
1335
1336 return 1;
1337}
1338
1339EAPI Eina_Bool
1340eina_matrixsparse_cell_clear(Eina_Matrixsparse_Cell *cell)
1341{
1342 Eina_Matrixsparse *m;
1343
1344 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1345 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1346 EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0);
1347
1348 m = cell->parent->parent;
1349
1350 _eina_matrixsparse_cell_unlink(cell);
1351 _eina_matrixsparse_cell_free(cell, m->free.func, m->free.user_data);
1352 return 1;
1353}
1354
1355EAPI Eina_Iterator *
1356eina_matrixsparse_iterator_new(const Eina_Matrixsparse *m)
1357{
1358 Eina_Matrixsparse_Iterator *it;
1359
1360 it = calloc(1, sizeof(*it));
1361 if (!it)
1362 {
1363 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1364 return NULL;
1365 }
1366
1367 EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR);
1368 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1369
1370 it->m = m;
1371 it->ref.row = m->rows;
1372 it->ref.col = m->rows ? m->rows->cols : NULL;
1373
1374 it->iterator.version = EINA_ITERATOR_VERSION;
1375 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_matrixsparse_iterator_next);
1376 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1377 _eina_matrixsparse_iterator_get_container);
1378 it->iterator.free = FUNC_ITERATOR_FREE(_eina_matrixsparse_iterator_free);
1379 return &it->iterator;
1380}
1381
1382EAPI Eina_Iterator *
1383eina_matrixsparse_iterator_complete_new(const Eina_Matrixsparse *m)
1384{
1385 Eina_Matrixsparse_Iterator_Complete *it;
1386
1387 it = calloc(1, sizeof(*it));
1388 if (!it)
1389 {
1390 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1391 return NULL;
1392 }
1393
1394 EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR);
1395 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1396
1397 it->m = m;
1398 it->idx.row = 0;
1399 it->idx.col = 0;
1400 it->ref.row = m->rows;
1401 it->ref.col = m->rows ? m->rows->cols : NULL;
1402
1403 it->dummy.row.next = it->dummy.row.prev = NULL;
1404 it->dummy.row.cols = it->dummy.row.last_col = it->dummy.row.last_used = NULL;
1405 it->dummy.row.parent = (Eina_Matrixsparse *)m;
1406 EINA_MAGIC_SET(&it->dummy.row, EINA_MAGIC_MATRIXSPARSE_ROW);
1407
1408 it->dummy.col.next = it->dummy.col.prev = NULL;
1409 it->dummy.col.data = NULL;
1410 it->dummy.col.parent = &it->dummy.row;
1411 EINA_MAGIC_SET(&it->dummy.col, EINA_MAGIC_MATRIXSPARSE_CELL);
1412
1413 it->iterator.version = EINA_ITERATOR_VERSION;
1414 it->iterator.next = FUNC_ITERATOR_NEXT(
1415 _eina_matrixsparse_iterator_complete_next);
1416 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1417 _eina_matrixsparse_iterator_complete_get_container);
1418 it->iterator.free = FUNC_ITERATOR_FREE(
1419 _eina_matrixsparse_iterator_complete_free);
1420 return &it->iterator;
1421}
generated by cgit v1.1 at 2024-10-30 02:43:04 +0000