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.c1423
1 files changed, 0 insertions, 1423 deletions
diff --git a/libraries/eina/src/lib/eina_matrixsparse.c b/libraries/eina/src/lib/eina_matrixsparse.c
deleted file mode 100644
index 59cd66b..0000000
--- a/libraries/eina/src/lib/eina_matrixsparse.c
+++ /dev/null
@@ -1,1423 +0,0 @@
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 if ((update_last_used_row) && (m->last_used == r_aux))
1082 m->last_used = r;
1083 }
1084 else
1085 {
1086 if (c != r->last_col)
1087 {
1088 c->next = NULL;
1089 r->last_col = c;
1090 }
1091
1092 if (update_last_used_col)
1093 r->last_used = r->last_col;
1094
1095 r = r->next;
1096 }
1097 }
1098
1099 update_last_used_row = 0;
1100 if (m->last_used)
1101 {
1102 if (m->last_row)
1103 update_last_used_row = m->last_used->row > m->last_row->row;
1104 else
1105 update_last_used_row = 1;
1106 }
1107
1108 if (update_last_used_row)
1109 m->last_used = m->last_row;
1110
1111 m->size.rows = rows;
1112 m->size.cols = cols;
1113 return 1;
1114}
1115
1116EAPI Eina_Bool
1117eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m,
1118 unsigned long row,
1119 unsigned long col,
1120 Eina_Matrixsparse_Cell **cell)
1121{
1122 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1123 EINA_SAFETY_ON_NULL_RETURN_VAL(cell, 0);
1124 *cell = NULL;
1125 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1126 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1127 *cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1128 return 1;
1129}
1130
1131EAPI void *
1132eina_matrixsparse_cell_data_get(const Eina_Matrixsparse_Cell *cell)
1133{
1134 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, NULL);
1135 return cell->data;
1136}
1137
1138EAPI void *
1139eina_matrixsparse_data_idx_get(const Eina_Matrixsparse *m,
1140 unsigned long row,
1141 unsigned long col)
1142{
1143 Eina_Matrixsparse_Cell *c;
1144 EINA_MAGIC_CHECK_MATRIXSPARSE(m, NULL);
1145 c = _eina_matrixsparse_cell_idx_get(m, row, col);
1146 if (c)
1147 return c->data;
1148 else
1149 return NULL;
1150}
1151
1152EAPI Eina_Bool
1153eina_matrixsparse_cell_position_get(const Eina_Matrixsparse_Cell *cell,
1154 unsigned long *row,
1155 unsigned long *col)
1156{
1157 if (row)
1158 *row = 0;
1159
1160 if (col)
1161 *col = 0;
1162
1163 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1164 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1165 if (row)
1166 *row = cell->parent->row;
1167
1168 if (col)
1169 *col = cell->col;
1170
1171 return 1;
1172}
1173
1174EAPI Eina_Bool
1175eina_matrixsparse_cell_data_replace(Eina_Matrixsparse_Cell *cell,
1176 const void *data,
1177 void **p_old)
1178{
1179 if (p_old)
1180 *p_old = NULL;
1181
1182 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1183
1184 if (p_old)
1185 *p_old = cell->data;
1186
1187 cell->data = (void *)data;
1188 return 1;
1189}
1190
1191EAPI Eina_Bool
1192eina_matrixsparse_cell_data_set(Eina_Matrixsparse_Cell *cell, const void *data)
1193{
1194 Eina_Matrixsparse *m;
1195
1196 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1197 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1198 EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0);
1199
1200 m = cell->parent->parent;
1201
1202 if (m->free.func)
1203 m->free.func(m->free.user_data, cell->data);
1204
1205 cell->data = (void *)data;
1206 return 1;
1207}
1208
1209EAPI Eina_Bool
1210eina_matrixsparse_data_idx_replace(Eina_Matrixsparse *m,
1211 unsigned long row,
1212 unsigned long col,
1213 const void *data,
1214 void **p_old)
1215{
1216 Eina_Matrixsparse_Cell *cell;
1217
1218 if (p_old)
1219 *p_old = NULL;
1220
1221 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1222 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1223 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1224
1225 cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1226 if (cell)
1227 {
1228 if (p_old)
1229 *p_old = cell->data;
1230
1231 cell->data = (void *)data;
1232 return 1;
1233 }
1234
1235 return _eina_matrixsparse_cell_idx_add(m, row, col, data);
1236}
1237
1238EAPI Eina_Bool
1239eina_matrixsparse_data_idx_set(Eina_Matrixsparse *m,
1240 unsigned long row,
1241 unsigned long col,
1242 const void *data)
1243{
1244 Eina_Matrixsparse_Cell *cell;
1245
1246 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1247 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1248 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1249
1250 cell = _eina_matrixsparse_cell_idx_get(m, row, col);
1251 if (cell)
1252 {
1253 if (m->free.func)
1254 m->free.func(m->free.user_data, cell->data);
1255
1256 cell->data = (void *)data;
1257 return 1;
1258 }
1259
1260 return _eina_matrixsparse_cell_idx_add(m, row, col, data);
1261}
1262
1263EAPI Eina_Bool
1264eina_matrixsparse_row_idx_clear(Eina_Matrixsparse *m, unsigned long row)
1265{
1266 Eina_Matrixsparse_Row *r;
1267
1268 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1269 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1270
1271 r = _eina_matrixsparse_row_idx_get(m, row);
1272 if (!r)
1273 return 1;
1274
1275 _eina_matrixsparse_row_unlink(r);
1276 _eina_matrixsparse_row_free(r, m->free.func, m->free.user_data);
1277
1278 return 1;
1279}
1280
1281EAPI Eina_Bool
1282eina_matrixsparse_column_idx_clear(Eina_Matrixsparse *m, unsigned long col)
1283{
1284 Eina_Matrixsparse_Row *r;
1285 void (*free_func)(void *, void *);
1286 void *user_data;
1287
1288 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1289 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1290
1291 free_func = m->free.func;
1292 user_data = m->free.user_data;
1293
1294 for (r = m->rows; r; )
1295 {
1296 Eina_Matrixsparse_Row *r_aux = r;
1297 Eina_Matrixsparse_Cell *c;
1298
1299 c = _eina_matrixsparse_row_cell_idx_get(r, col);
1300 r = r->next;
1301
1302 if (!c)
1303 continue;
1304
1305 if ((r_aux->cols != c) || (r_aux->last_col != c))
1306 {
1307 _eina_matrixsparse_cell_unlink(c);
1308 _eina_matrixsparse_cell_free(c, free_func, user_data);
1309 }
1310 else
1311 {
1312 _eina_matrixsparse_row_unlink(r_aux);
1313 _eina_matrixsparse_row_free(r_aux, free_func, user_data);
1314 }
1315 }
1316
1317 return 1;
1318}
1319
1320EAPI Eina_Bool
1321eina_matrixsparse_cell_idx_clear(Eina_Matrixsparse *m,
1322 unsigned long row,
1323 unsigned long col)
1324{
1325 Eina_Matrixsparse_Cell *c;
1326
1327 EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0);
1328 EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0);
1329 EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0);
1330
1331 c = _eina_matrixsparse_cell_idx_get(m, row, col);
1332 if (!c)
1333 return 1;
1334
1335 _eina_matrixsparse_cell_unlink(c);
1336 _eina_matrixsparse_cell_free(c, m->free.func, m->free.user_data);
1337
1338 return 1;
1339}
1340
1341EAPI Eina_Bool
1342eina_matrixsparse_cell_clear(Eina_Matrixsparse_Cell *cell)
1343{
1344 Eina_Matrixsparse *m;
1345
1346 EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0);
1347 EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0);
1348 EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0);
1349
1350 m = cell->parent->parent;
1351
1352 _eina_matrixsparse_cell_unlink(cell);
1353 _eina_matrixsparse_cell_free(cell, m->free.func, m->free.user_data);
1354 return 1;
1355}
1356
1357EAPI Eina_Iterator *
1358eina_matrixsparse_iterator_new(const Eina_Matrixsparse *m)
1359{
1360 Eina_Matrixsparse_Iterator *it;
1361
1362 it = calloc(1, sizeof(*it));
1363 if (!it)
1364 {
1365 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1366 return NULL;
1367 }
1368
1369 EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR);
1370 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1371
1372 it->m = m;
1373 it->ref.row = m->rows;
1374 it->ref.col = m->rows ? m->rows->cols : NULL;
1375
1376 it->iterator.version = EINA_ITERATOR_VERSION;
1377 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_matrixsparse_iterator_next);
1378 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1379 _eina_matrixsparse_iterator_get_container);
1380 it->iterator.free = FUNC_ITERATOR_FREE(_eina_matrixsparse_iterator_free);
1381 return &it->iterator;
1382}
1383
1384EAPI Eina_Iterator *
1385eina_matrixsparse_iterator_complete_new(const Eina_Matrixsparse *m)
1386{
1387 Eina_Matrixsparse_Iterator_Complete *it;
1388
1389 it = calloc(1, sizeof(*it));
1390 if (!it)
1391 {
1392 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1393 return NULL;
1394 }
1395
1396 EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR);
1397 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1398
1399 it->m = m;
1400 it->idx.row = 0;
1401 it->idx.col = 0;
1402 it->ref.row = m->rows;
1403 it->ref.col = m->rows ? m->rows->cols : NULL;
1404
1405 it->dummy.row.next = it->dummy.row.prev = NULL;
1406 it->dummy.row.cols = it->dummy.row.last_col = it->dummy.row.last_used = NULL;
1407 it->dummy.row.parent = (Eina_Matrixsparse *)m;
1408 EINA_MAGIC_SET(&it->dummy.row, EINA_MAGIC_MATRIXSPARSE_ROW);
1409
1410 it->dummy.col.next = it->dummy.col.prev = NULL;
1411 it->dummy.col.data = NULL;
1412 it->dummy.col.parent = &it->dummy.row;
1413 EINA_MAGIC_SET(&it->dummy.col, EINA_MAGIC_MATRIXSPARSE_CELL);
1414
1415 it->iterator.version = EINA_ITERATOR_VERSION;
1416 it->iterator.next = FUNC_ITERATOR_NEXT(
1417 _eina_matrixsparse_iterator_complete_next);
1418 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1419 _eina_matrixsparse_iterator_complete_get_container);
1420 it->iterator.free = FUNC_ITERATOR_FREE(
1421 _eina_matrixsparse_iterator_complete_free);
1422 return &it->iterator;
1423}
generated by cgit v1.1 at 2024-08-30 17:01:09 +0000