From f5564ddd503d1146721e0460a5b42fe859298f30 Mon Sep 17 00:00:00 2001 From: barbieri Date: Fri, 4 Sep 2009 13:43:44 +0000 Subject: [PATCH] eina_matrixsparse: welcome sparse matrix implementation and tests. Sparse Matrix was implemented and tested by Rafael Antognolli and myself in order to implement optimized large sparse matrix walk in some products, one of them WebKit-EFL optimizations. We have done extensive tests, with good code coverage. Similar to lists/inlists, we keep pointer to last known element and similar to iterators we keep reference to last accessed row and cell inside rows. This allows fast sequential access (for i... for j... m[i,j]), that is our most common usage case. Rows are kept in a list, with cells inside that row as another list. It's not similar to most book implementations where cells keep reference to their sibling cells in other rows as well, we opted to not do that to save some pointers and make algorithms simpler, still do great for our use case. This code was developed on behalf of our client, that wants to remain unnamed so far. Thanks client ;-) git-svn-id: svn+ssh://svn.enlightenment.org/var/svn/e/trunk/eina@42243 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- configure.ac | 2 +- src/include/Eina.h | 1 + src/include/eina_matrixsparse.h | 116 +++ src/include/eina_private.h | 11 + src/lib/Makefile.am | 1 + src/lib/eina_main.c | 11 + src/lib/eina_matrixsparse.c | 1566 ++++++++++++++++++++++++++++++++++++ src/tests/Makefile.am | 3 +- src/tests/eina_suite.c | 1 + src/tests/eina_suite.h | 1 + src/tests/eina_test_matrixsparse.c | 481 +++++++++++ 11 files changed, 2192 insertions(+), 2 deletions(-) create mode 100644 src/include/eina_matrixsparse.h create mode 100644 src/lib/eina_matrixsparse.c create mode 100644 src/tests/eina_test_matrixsparse.c diff --git a/configure.ac b/configure.ac index 19401b2..03c32a9 100644 --- a/configure.ac +++ b/configure.ac @@ -232,6 +232,7 @@ case "$host_os" in ;; esac +EFL_CHECK_COVERAGE([${enable_tests}], [enable_coverage="yes"], [enable_coverage="no"]) EINA_CFLAGS="${EFL_COVERAGE_CFLAGS}" case "${host_os}" in cegcc*) @@ -348,7 +349,6 @@ EINA_CHECK_MODULE([pass-through], [yes], [pass through]) ### Unit tests, coverage and benchmarking EFL_CHECK_TESTS([enable_tests="yes"], [enable_tests="no"]) -EFL_CHECK_COVERAGE([${enable_tests}], [enable_coverage="yes"], [enable_coverage="no"]) EFL_CHECK_BENCHMARK([enable_benchmark="yes"], [enable_benchmark="no"]) EINA_BENCH_MODULE([evas], [${enable_benchmark}], [evas], [enable_benchmark_evas="yes"], [enable_benchmark_evas="no"]) EINA_BENCH_MODULE([ecore], [${enable_benchmark}], [ecore], [enable_benchmark_ecore="yes"], [enable_benchmark_ecore="no"]) diff --git a/src/include/Eina.h b/src/include/Eina.h index 8a851f0..e87359e 100644 --- a/src/include/Eina.h +++ b/src/include/Eina.h @@ -181,6 +181,7 @@ extern "C" { #include "eina_cpu.h" #include "eina_tiler.h" #include "eina_hamster.h" +#include "eina_matrixsparse.h" #ifdef __cplusplus } diff --git a/src/include/eina_matrixsparse.h b/src/include/eina_matrixsparse.h new file mode 100644 index 0000000..5fe69f3 --- /dev/null +++ b/src/include/eina_matrixsparse.h @@ -0,0 +1,116 @@ +/* EINA - EFL data type library + * Copyright (C) 2009 Gustavo Sverzut Barbieri + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + */ + +#ifndef EINA_MATRIXSPARSE_H_ +#define EINA_MATRIXSPARSE_H_ + +#include + +#include "eina_config.h" + +#include "eina_types.h" +#include "eina_iterator.h" +#include "eina_accessor.h" + +/** + * @addtogroup Eina_Data_Types_Group Data Types + * + * @{ + */ + +/** + * @addtogroup Eina_Containers_Group Containers + * + * @{ + */ + +/** + * @defgroup Eina_Matrixsparse_Group Sparse Matrix + * + * @{ + */ + +/** + * @typedef Eina_Matrixsparse + * Type for a generic sparse matrix. + */ +typedef struct _Eina_Matrixsparse Eina_Matrixsparse; + +/** + * @typedef Eina_Matrixsparse_Row + * Type for a generic sparse matrix row, opaque for users. + */ +typedef struct _Eina_Matrixsparse_Row Eina_Matrixsparse_Row; + +/** + * @typedef Eina_Matrixsparse_Cell + * Type for a generic sparse matrix cell, opaque for users. + */ +typedef struct _Eina_Matrixsparse_Cell Eina_Matrixsparse_Cell; + +typedef struct _Eina_Matrixsparse_Item_Cell Eina_Matrixsparse_Item_Cell; +typedef struct _Eina_Matrixsparse_Item_Row Eina_Matrixsparse_Item_Row; + + +/* init */ +EAPI int eina_matrixsparse_init(void); +EAPI int eina_matrixsparse_shutdown(void); + +/* constructors and destructors */ +EAPI Eina_Matrixsparse *eina_matrixsparse_new(unsigned long rows, unsigned long cols, void (*free_func)(void *user_data, void *cell_data), const void *user_data); +EAPI void eina_matrixsparse_free(Eina_Matrixsparse *m); + +/* size manipulation */ +EAPI void eina_matrixsparse_size_get(const Eina_Matrixsparse *m, unsigned long *rows, unsigned long *cols); +EAPI Eina_Bool eina_matrixsparse_size_set(Eina_Matrixsparse *m, unsigned long rows, unsigned long cols); + +/* data getting */ +EAPI Eina_Bool eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m, unsigned long row, unsigned long col, Eina_Matrixsparse_Cell **cell); +EAPI void *eina_matrixsparse_cell_data_get(const Eina_Matrixsparse_Cell *cell); +EAPI void *eina_matrixsparse_data_idx_get(const Eina_Matrixsparse *m, unsigned long row, unsigned long col); +EAPI Eina_Bool eina_matrixsparse_cell_position_get(const Eina_Matrixsparse_Cell *cell, unsigned long *row, unsigned long *col); + +/* data setting */ +EAPI Eina_Bool eina_matrixsparse_cell_data_replace(Eina_Matrixsparse_Cell *cell, const void *data, void **p_old); +EAPI Eina_Bool eina_matrixsparse_cell_data_set(Eina_Matrixsparse_Cell *cell, const void *data); +EAPI Eina_Bool eina_matrixsparse_data_idx_replace(Eina_Matrixsparse *m, unsigned long row, unsigned long col, const void *data, void **p_old); +EAPI Eina_Bool eina_matrixsparse_data_idx_set(Eina_Matrixsparse *m, unsigned long row, unsigned long col, const void *data); + +/* data deleting */ +EAPI Eina_Bool eina_matrixsparse_row_idx_clear(Eina_Matrixsparse *m, unsigned long row); +EAPI Eina_Bool eina_matrixsparse_column_idx_clear(Eina_Matrixsparse *m, unsigned long col); +EAPI Eina_Bool eina_matrixsparse_cell_idx_clear(Eina_Matrixsparse *m, unsigned long row, unsigned long col); +EAPI Eina_Bool eina_matrixsparse_cell_clear(Eina_Matrixsparse_Cell *cell); + +/* iterators */ +EAPI Eina_Iterator *eina_matrixsparse_iterator_new(const Eina_Matrixsparse *m); +EAPI Eina_Iterator *eina_matrixsparse_iterator_complete_new(const Eina_Matrixsparse *m); + +/** + * @} + */ + +/** + * @} + */ + +/** + * @} + */ + +#endif /* EINA_MATRIXSPARSE_H_ */ diff --git a/src/include/eina_private.h b/src/include/eina_private.h index 191c88f..ba4f018 100644 --- a/src/include/eina_private.h +++ b/src/include/eina_private.h @@ -71,6 +71,17 @@ #define EINA_MAGIC_TILER 0x98761240 #define EINA_MAGIC_TILER_ITERATOR 0x98761241 +#define EINA_MAGIC_MATRIXSPARSE 0x98761242 +#define EINA_MAGIC_MATRIXSPARSE_ROW 0x98761243 +#define EINA_MAGIC_MATRIXSPARSE_CELL 0x98761244 +#define EINA_MAGIC_MATRIXSPARSE_ITERATOR 0x98761245 +#define EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR 0x98761246 +#define EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR 0x98761247 +#define EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR 0x98761248 +#define EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR 0x98761249 + + + /* undef the following, we want out version */ #undef FREE #define FREE(ptr) \ diff --git a/src/lib/Makefile.am b/src/lib/Makefile.am index 809cf2e..bb1e988 100644 --- a/src/lib/Makefile.am +++ b/src/lib/Makefile.am @@ -19,6 +19,7 @@ eina_inlist.c \ eina_file.c \ eina_mempool.c \ eina_list.c \ +eina_matrixsparse.c \ eina_module.c \ eina_value.c \ eina_array.c \ diff --git a/src/lib/eina_main.c b/src/lib/eina_main.c index 98400e6..f26008a 100644 --- a/src/lib/eina_main.c +++ b/src/lib/eina_main.c @@ -31,6 +31,7 @@ #include "eina_hash.h" #include "eina_stringshare.h" #include "eina_list.h" +#include "eina_matrixsparse.h" #include "eina_array.h" #include "eina_counter.h" #include "eina_benchmark.h" @@ -89,6 +90,7 @@ static int _eina_log_dom = -1; * @li eina_hash_init() * @li eina_stringshare_init() * @li eina_list_init() + * @li eina_matrixsparse_init() * @li eina_array_init() * @li eina_counter_init() * @li eina_benchmark_init() @@ -144,6 +146,11 @@ eina_init(void) ERR("Could not initialize eina list module."); goto list_init_error; } + if (!eina_matrixsparse_init()) + { + ERR("Could not initialize eina matrixsparse module."); + goto matrixsparse_init_error; + } if (!eina_array_init()) { ERR("Could not initialize eina array module."); @@ -182,6 +189,8 @@ eina_init(void) counter_init_error: eina_array_shutdown(); array_init_error: + eina_matrixsparse_shutdown(); + matrixsparse_init_error: eina_list_shutdown(); list_init_error: eina_stringshare_shutdown(); @@ -214,6 +223,7 @@ eina_init(void) * @li eina_benchmark_shutdown() * @li eina_counter_shutdown() * @li eina_array_shutdown() + * @li eina_matrixsparse_shutdown() * @li eina_list_shutdown() * @li eina_stringshare_shutdown() * @li eina_hash_shutdown() @@ -235,6 +245,7 @@ eina_shutdown(void) eina_benchmark_shutdown(); eina_counter_shutdown(); eina_array_shutdown(); + eina_matrixsparse_shutdown(); eina_list_shutdown(); eina_stringshare_shutdown(); eina_hash_shutdown(); diff --git a/src/lib/eina_matrixsparse.c b/src/lib/eina_matrixsparse.c new file mode 100644 index 0000000..37c6937 --- /dev/null +++ b/src/lib/eina_matrixsparse.c @@ -0,0 +1,1566 @@ +/* EINA - EFL data type library + * Copyright (C) 2009 Gustavo Sverzut Barbieri + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + */ + + +/** + * @page tutorial_matrixsparse_page Matrix Sparse Tutorial + * + * to be written... + * + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include +#include +#include +#include + +#ifdef HAVE_EVIL +# include +#endif + +#include "eina_config.h" +#include "eina_error.h" +#include "eina_matrixsparse.h" +#include "eina_magic.h" +#include "eina_mempool.h" +#include "eina_private.h" +#include "eina_safety_checks.h" + + +/*============================================================================* + * Local * + *============================================================================*/ +/** + * @cond LOCAL + */ +#define EINA_MAGIC_CHECK_MATRIXSPARSE(d, ...) \ + do { \ + if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE)) \ + { \ + EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE); \ + return __VA_ARGS__; \ + } \ + } while(0); + +#define EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(d, ...) \ + do { \ + if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_ROW)) \ + { \ + EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_ROW); \ + return __VA_ARGS__; \ + } \ + } while(0); + +#define EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(d, ...) \ + do { \ + if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_CELL)) \ + { \ + EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_CELL); \ + return __VA_ARGS__; \ + } \ + } while(0); + +#define EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(d, ...) \ + do { \ + if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_MATRIXSPARSE_ITERATOR)) \ + { \ + EINA_MAGIC_FAIL(d, EINA_MAGIC_MATRIXSPARSE_ITERATOR); \ + return __VA_ARGS__; \ + } \ + } while(0); + +struct _Eina_Matrixsparse_Cell +{ + Eina_Matrixsparse_Cell *next; + Eina_Matrixsparse_Cell *prev; + + void *data; + unsigned long col; + + Eina_Matrixsparse_Row *parent; + + EINA_MAGIC +}; + +struct _Eina_Matrixsparse_Row +{ + Eina_Matrixsparse_Row *next; + Eina_Matrixsparse_Row *prev; + + Eina_Matrixsparse_Cell *cols; + Eina_Matrixsparse_Cell *last_col; + Eina_Matrixsparse_Cell *last_used; /* fast sequential access */ + unsigned long row; + + Eina_Matrixsparse *parent; + + EINA_MAGIC +}; + +struct _Eina_Matrixsparse +{ + Eina_Matrixsparse_Row *rows; + Eina_Matrixsparse_Row *last_row; + Eina_Matrixsparse_Row *last_used; /* fast sequential access */ + + struct + { + unsigned long rows; + unsigned long cols; + } size; + + struct + { + void (*func)(void *user_data, void *cell_data); + void *user_data; + } free; + + EINA_MAGIC +}; + +typedef struct _Eina_Matrixsparse_Iterator Eina_Matrixsparse_Iterator; +typedef struct _Eina_Matrixsparse_Iterator_Complete Eina_Matrixsparse_Iterator_Complete; + +struct _Eina_Matrixsparse_Iterator +{ + Eina_Iterator iterator; + + const Eina_Matrixsparse *m; + struct { + const Eina_Matrixsparse_Row *row; + const Eina_Matrixsparse_Cell *col; + } ref; + + EINA_MAGIC +}; + +struct _Eina_Matrixsparse_Iterator_Complete +{ + Eina_Iterator iterator; + + const Eina_Matrixsparse *m; + struct { + const Eina_Matrixsparse_Row *row; + const Eina_Matrixsparse_Cell *col; + } ref; + + struct { + unsigned long row, col; + } idx; + + struct { + Eina_Matrixsparse_Row row; + Eina_Matrixsparse_Cell col; + } dummy; + + EINA_MAGIC +}; + +/** + * @todo Eina_Matrixsparse_Row_Iterator: iterator over rows in matrix + * @todo Eina_Matrixsparse_Row_Accessor: accessor over rows in matrix + * @todo Eina_Matrixsparse_Cell_Iterator: iterator over cells in row + * @todo Eina_Matrixsparse_Cell_Accessor: accessor over cells in row + */ + +static int _eina_matrixsparse_init_count = 0; +static Eina_Mempool *_eina_matrixsparse_cell_mp = NULL; +static Eina_Mempool *_eina_matrixsparse_row_mp = NULL; + +static inline void +_eina_matrixsparse_cell_free(Eina_Matrixsparse_Cell *c, void (*free_func)(void *, void *), void *user_data) +{ + if (free_func) + free_func(user_data, c->data); + + EINA_MAGIC_SET(c, EINA_MAGIC_NONE); + eina_mempool_free(_eina_matrixsparse_cell_mp, c); +} + +static inline void +_eina_matrixsparse_cell_unlink(Eina_Matrixsparse_Cell *c) +{ + Eina_Matrixsparse_Row *r = c->parent; + long *tmp = c->data; + + if (r->last_used == c) + { + if (c->next) + r->last_used = c->next; + else + r->last_used = c->prev; + } + + if (r->last_col == c) + r->last_col = c->prev; + + if (r->cols == c) + r->cols = c->next; + + if (c->next && c->prev) + { + c->next->prev = c->prev; + c->prev->next = c->next; + } + else if (c->next) + c->next->prev = NULL; + else if (c->prev) + c->prev->next = NULL; +} + +static inline void +_eina_matrixsparse_row_cells_free(Eina_Matrixsparse_Row *r, void (*free_func)(void *, void *), void *user_data) +{ + Eina_Matrixsparse_Cell *c = r->cols; + while (c) + { + Eina_Matrixsparse_Cell *c_aux = c; + c = c->next; + _eina_matrixsparse_cell_free(c_aux, free_func, user_data); + } +} + +static inline void +_eina_matrixsparse_row_free(Eina_Matrixsparse_Row *r, void (*free_func)(void *, void *), void *user_data) +{ + _eina_matrixsparse_row_cells_free(r, free_func, user_data); + EINA_MAGIC_SET(r, EINA_MAGIC_NONE); + eina_mempool_free(_eina_matrixsparse_row_mp, r); +} + +static inline void +_eina_matrixsparse_row_unlink(Eina_Matrixsparse_Row *r) +{ + Eina_Matrixsparse *m = r->parent; + + if (m->last_used == r) + { + if (r->next) + m->last_used = r->next; + else + m->last_used = r->prev; + } + + if (m->last_row == r) + m->last_row = r->prev; + + if (m->rows == r) + m->rows = r->next; + + if (r->next && r->prev) + { + r->next->prev = r->prev; + r->prev->next = r->next; + } + else if (r->next) + r->next->prev = NULL; + else if (r->prev) + r->prev->next = NULL; +} + +static inline void +_eina_matrixsparse_row_find_parms_get(const Eina_Matrixsparse *m, unsigned long row, Eina_Matrixsparse_Row **p_r, int *p_dir) +{ + Eina_Matrixsparse_Row *r; + unsigned long dist; + int dir; + + dist = row - m->rows->row; + r = m->rows; + dir = 1; + if (dist > m->last_row->row - row) + { + dist = m->last_row->row - row; + r = m->last_row; + dir = -1; + } + + if (m->last_used) + { + if (m->last_used->row < row) + { + if (dist > row - m->last_used->row) + { +/* dist = row = m->last_used->row; */ + r = m->last_used; + dir = 1; + } + } + else + { + if (dist > m->last_used->row - row) + { +/* dist = m->last_used->row - row; */ + r = m->last_used; + dir = -1; + } + } + } + + *p_r = r; + *p_dir = dir; +} + +static inline void +_eina_matrixsparse_row_cell_find_parms_get(const Eina_Matrixsparse_Row *r, unsigned long col, Eina_Matrixsparse_Cell **p_c, int *p_dir) +{ + Eina_Matrixsparse_Cell *c; + unsigned long dist; + int dir; + + dist = col - r->cols->col; + c = r->cols; + dir = 1; + if (dist > r->last_col->col - col) + { + dist = r->last_col->col - col; + c = r->last_col; + dir = -1; + } + + if (r->last_used) + { + if (r->last_used->col < col) + { + if (dist > col - r->last_used->col) + { +/* dist = col = r->last_used->col; */ + c = r->last_used; + dir = 1; + } + } + else + { + if (dist > r->last_used->col - col) + { +/* dist = r->last_used->col - col; */ + c = r->last_used; + dir = -1; + } + } + } + + *p_c = c; + *p_dir = dir; +} + +static inline Eina_Matrixsparse_Row * +_eina_matrixsparse_row_idx_get(const Eina_Matrixsparse *m, unsigned long row) +{ + Eina_Matrixsparse_Row *r; + int dir; + + if (!m->rows) return NULL; + + if (m->rows->row == row) return m->rows; + else if (m->rows->row > row) return NULL; + + if (m->last_row->row == row) return m->last_row; + else if (m->last_row->row < row) return NULL; + + if ((m->last_used) && (m->last_used->row == row)) return m->last_used; + + _eina_matrixsparse_row_find_parms_get(m, row, &r, &dir); + assert(dir != 0); + if (dir > 0) + { + for (; r != NULL; r = r->next) + if (r->row == row) + { + ((Eina_Matrixsparse *)m)->last_used = r; + return r; + } + else if (r->row > row) + return NULL; + } + else if (dir < 0) + { + for (; r != NULL; r = r->prev) + if (r->row == row) + { + ((Eina_Matrixsparse *)m)->last_used = r; + return r; + } + else if (r->row < row) + return NULL; + } + + return NULL; +} + +static inline Eina_Matrixsparse_Cell * +_eina_matrixsparse_row_cell_idx_get(const Eina_Matrixsparse_Row *r, unsigned long col) +{ + Eina_Matrixsparse_Cell *c; + int dir; + + if (!r->cols) return NULL; + + if (r->cols->col == col) return r->cols; + else if (r->cols->col > col) return NULL; + + if (r->last_col->col == col) return r->last_col; + else if (r->last_col->col < col) return NULL; + + if ((r->last_used) && (r->last_used->col == col)) return r->last_used; + + + _eina_matrixsparse_row_cell_find_parms_get(r, col, &c, &dir); + assert(dir != 0); + if (dir > 0) + { + for (; r != NULL; c = c->next) + if (c->col == col) + { + ((Eina_Matrixsparse_Row *)r)->last_used = c; + return c; + } + else if (c->col > col) + return NULL; + } + else if (dir < 0) + { + for (; r != NULL; c = c->prev) + if (c->col == col) + { + ((Eina_Matrixsparse_Row *)r)->last_used = c; + return c; + } + else if (c->col < col) + return NULL; + } + + return NULL; +} + +static inline Eina_Matrixsparse_Cell * +_eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m, unsigned long row, unsigned long col) +{ + Eina_Matrixsparse_Row *r = _eina_matrixsparse_row_idx_get(m, row); + if (!r) return NULL; + return _eina_matrixsparse_row_cell_idx_get(r, col); +} + +static inline void +_eina_matrixsparse_row_idx_siblings_find(const Eina_Matrixsparse *m, unsigned long row, Eina_Matrixsparse_Row **p_prev, Eina_Matrixsparse_Row **p_next) +{ + Eina_Matrixsparse_Row *r; + int dir; + + _eina_matrixsparse_row_find_parms_get(m, row, &r, &dir); + assert(dir != 0); + if (dir > 0) + { + for (; r != NULL; r = r->next) + if (r->row > row) + break; + assert(r != NULL); + *p_prev = r->prev; + *p_next = r; + } + else if (dir < 0) + { + for (; r != NULL; r = r->prev) + if (r->row < row) + break; + assert(r != NULL); + *p_prev = r; + *p_next = r->next; + } +} + +static inline void +_eina_matrixsparse_row_cell_idx_siblings_find(const Eina_Matrixsparse_Row *r, unsigned long col, Eina_Matrixsparse_Cell **p_prev, Eina_Matrixsparse_Cell **p_next) +{ + Eina_Matrixsparse_Cell *c; + int dir; + + _eina_matrixsparse_row_cell_find_parms_get(r, col, &c, &dir); + assert(dir != 0); + if (dir > 0) + { + for (; c != NULL; c = c->next) + if (c->col > col) + break; + assert(c != NULL); + *p_prev = c->prev; + *p_next = c; + } + else if (dir < 0) + { + for (; c != NULL; c = c->prev) + if (c->col < col) + break; + assert(c != NULL); + *p_prev = c; + *p_next = c->next; + } +} + +static inline Eina_Matrixsparse_Row * +_eina_matrixsparse_row_idx_add(Eina_Matrixsparse *m, unsigned long row) +{ + Eina_Matrixsparse_Row *r = eina_mempool_malloc + (_eina_matrixsparse_row_mp, sizeof(Eina_Matrixsparse_Row)); + if (!r) return NULL; + + if (!m->rows) + { + r->prev = NULL; + r->next = NULL; + m->rows = r; + m->last_row = r; + } + else if (row < m->rows->row) + { + r->prev = NULL; + r->next = m->rows; + m->rows->prev = r; + m->rows = r; + } + else if (row > m->last_row->row) + { + r->prev = m->last_row; + m->last_row->next = r; + r->next = NULL; + m->last_row = r; + } + else + { + Eina_Matrixsparse_Row *prev = NULL, *next = NULL; + _eina_matrixsparse_row_idx_siblings_find(m, row, &prev, &next); + assert(prev != NULL); + assert(next != NULL); + r->prev = prev; + r->next = next; + prev->next = r; + next->prev = r; + } + + r->cols = NULL; + r->last_col = NULL; + r->last_used = NULL; + r->row = row; + r->parent = m; + EINA_MAGIC_SET(r, EINA_MAGIC_MATRIXSPARSE_ROW); + m->last_used = r; + return r; +} + +static inline Eina_Matrixsparse_Cell * +_eina_matrixsparse_row_cell_idx_add(Eina_Matrixsparse_Row *r, unsigned long col, const void *data) +{ + Eina_Matrixsparse_Cell *c = eina_mempool_malloc + (_eina_matrixsparse_cell_mp, sizeof(Eina_Matrixsparse_Cell)); + if (!c) return NULL; + + if (!r->cols) + { + c->prev = NULL; + c->next = NULL; + r->cols = c; + r->last_col = c; + } + else if (col < r->cols->col) + { + c->prev = NULL; + c->next = r->cols; + r->cols->prev = c; + r->cols = c; + } + else if (col > r->last_col->col) + { + c->prev = r->last_col; + r->last_col->next = c; + c->next = NULL; + r->last_col = c; + } + else + { + Eina_Matrixsparse_Cell *prev = NULL, *next = NULL; + _eina_matrixsparse_row_cell_idx_siblings_find(r, col, &prev, &next); + assert(prev != NULL); + assert(next != NULL); + c->prev = prev; + c->next = next; + prev->next = c; + next->prev = c; + } + + c->data = (void *)data; + c->col = col; + c->parent = r; + EINA_MAGIC_SET(c, EINA_MAGIC_MATRIXSPARSE_CELL); + r->last_used = c; + return c; +} + +static inline Eina_Bool +_eina_matrixsparse_cell_idx_add(Eina_Matrixsparse *m, unsigned long row, unsigned long col, const void *data) +{ + Eina_Matrixsparse_Row *r = _eina_matrixsparse_row_idx_get(m, row); + if (!r) + r = _eina_matrixsparse_row_idx_add(m, row); + if (!r) + return 0; + + if (_eina_matrixsparse_row_cell_idx_add(r, col, data)) + return 1; + + if (r->cols) + return 0; + _eina_matrixsparse_row_unlink(r); + _eina_matrixsparse_row_free(r, m->free.func, m->free.user_data); + return 0; +} + +/*============================================================================* + * Iterators * + *============================================================================*/ +static Eina_Bool +_eina_matrixsparse_iterator_next(Eina_Matrixsparse_Iterator *it, void **data) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, EINA_FALSE); + + /* do not touch it->idx */ + + if (!it->ref.col) return 0; + *data = (Eina_Matrixsparse_Cell *)it->ref.col; + + it->ref.col = it->ref.col->next; + if (!it->ref.col) + { + it->ref.row = it->ref.row->next; + if (it->ref.row) + it->ref.col = it->ref.row->cols; + } + return 1; +} + +static Eina_Matrixsparse * +_eina_matrixsparse_iterator_get_container(Eina_Matrixsparse_Iterator *it) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, NULL); + return (Eina_Matrixsparse *)it->m; +} + +static void +_eina_matrixsparse_iterator_free(Eina_Matrixsparse_Iterator *it) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it); + EINA_MAGIC_SET(it, EINA_MAGIC_NONE); + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE); + free(it); +} + +static Eina_Bool +_eina_matrixsparse_iterator_complete_next(Eina_Matrixsparse_Iterator_Complete *it, void **data) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, EINA_FALSE); + + if (it->idx.row >= it->m->size.rows) + return 0; + + if (it->dummy.col.data != NULL) + EINA_ERROR_PERR("Last iterator call changed dummy cell!\n"); + + if ((it->ref.col) && + (it->ref.col->col == it->idx.col) && + (it->ref.row->row == it->idx.row)) + { + *data = (Eina_Matrixsparse_Cell *)it->ref.col; + it->ref.col = it->ref.col->next; + if (!it->ref.col) + { + it->ref.row = it->ref.row->next; + if (it->ref.row) + it->ref.col = it->ref.row->cols; + } + } + else + { + it->dummy.col.data = NULL; + *data = &it->dummy.col; + } + + it->idx.col++; + if (it->idx.col == it->m->size.cols) + { + it->idx.col = 0; + it->idx.row++; + } + return 1; +} + +static Eina_Matrixsparse * +_eina_matrixsparse_iterator_complete_get_container(Eina_Matrixsparse_Iterator_Complete *it) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it, NULL); + return (Eina_Matrixsparse *)it->m; +} + +static void +_eina_matrixsparse_iterator_complete_free(Eina_Matrixsparse_Iterator_Complete *it) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_ITERATOR(it); + + if (it->dummy.col.data != NULL) + EINA_ERROR_PERR("Last iterator call changed dummy cell!\n"); + + EINA_MAGIC_SET(it, EINA_MAGIC_NONE); + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE); + free(it); +} + + +/** + * @endcond + */ + +/*============================================================================* + * Global * + *============================================================================*/ + +/*============================================================================* + * API * + *============================================================================*/ + +/** + * @addtogroup Eina_Matrixsparse_Group Matrix Sparse + * + * @brief These functions provide matrix sparse management. + * + * For more information, you can look at the @ref tutorial_matrixsparse_page. + * + * @{ + */ +/** + * @brief Initialize the matrixsparse module. + * + * @return 1 or greater on success, 0 on error. + * + * This function sets up the error, magic and mempool modules of + * Eina. It is also called by eina_init(). It returns 0 on failure, + * otherwise it returns the number of times it has already been + * called. If Eina has been configured with the default memory pool, + * then the memory pool used in an Eina matrixsparse will be + * "pass_through". Otherwise, the environment variable EINA_MEMPOOL is + * read and its value is chosen as memory pool ; if EINA_MEMPOOL is + * not defined, then the "chained_mempool" memory pool is chosen. If + * the memory pool is not found, then eina_matrixsparse_init() return @c 0. + * See eina_error_init(), eina_magic_string_init() and + * eina_mempool_init() for the documentation of the initialisation of + * the dependency modules. + * + * When no more Eina matrixsparse are used, call eina_matrixsparse_shutdown() + * to shut down the matrixsparse module. + * + * @see eina_error_init() + * @see eina_magic_string_init() + * @see eina_mempool_init() + */ +EAPI int +eina_matrixsparse_init(void) +{ + const char *choice; + + if (!_eina_matrixsparse_init_count) + { + if (!eina_error_init()) + { + fprintf(stderr, "Could not initialize eina error module\n"); + return 0; + } + + if (!eina_magic_string_init()) + { + EINA_ERROR_PERR("ERROR: Could not initialize eina magic string module.\n"); + goto on_magic_string_fail; + } + + if (!eina_mempool_init()) + { + EINA_ERROR_PERR("ERROR: Could not initialize eina mempool module.\n"); + goto on_mempool_fail; + } + +#ifdef EINA_DEFAULT_MEMPOOL + choice = "pass_through"; +#else + if (!(choice = getenv("EINA_MEMPOOL"))) + choice = "chained_mempool"; +#endif + + _eina_matrixsparse_cell_mp = eina_mempool_add + (choice, "matrixsparse_cell", NULL, sizeof (Eina_Matrixsparse_Cell), 120); + if (!_eina_matrixsparse_cell_mp) + { + EINA_ERROR_PERR("ERROR: Mempool for matrixsparse_cell cannot be allocated in matrixsparse init.\n"); + goto on_init_fail; + } + + _eina_matrixsparse_row_mp = eina_mempool_add + (choice, "matrixsparse_row", NULL, sizeof (Eina_Matrixsparse_Row), 120); + if (!_eina_matrixsparse_row_mp) + { + EINA_ERROR_PERR("ERROR: Mempool for matrixsparse_row cannot be allocated in matrixsparse init.\n"); + goto on_init_fail; + } + + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE, + "Eina Matrixsparse"); + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_ROW, + "Eina Matrixsparse Row"); + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_CELL, + "Eina Matrixsparse Cell"); + + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_ITERATOR, + "Eina Matrixsparse Iterator"); + + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR, + "Eina Matrixsparse Row Accessor"); + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR, + "Eina Matrixsparse Row Iterator"); + + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR, + "Eina Matrixsparse Cell Accessor"); + eina_magic_string_set(EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR, + "Eina Matrixsparse Cell Iterator"); + } + + return ++_eina_matrixsparse_init_count; + + on_init_fail: + eina_mempool_shutdown(); + on_mempool_fail: + eina_magic_string_shutdown(); + on_magic_string_fail: + eina_error_shutdown(); + return 0; +} + +/** + * @brief Shut down the matrixsparse module. + * + * @return 0 when the matrixsparse module is completely shut down, 1 or + * greater otherwise. + * + * This function shuts down the mempool, magic and error modules set + * up by eina_matrixsparse_init(). It is also called by eina_shutdown(). It + * returns 0 when it is called the same number of times than + * eina_matrixsparse_init(). + */ +EAPI int +eina_matrixsparse_shutdown(void) +{ + --_eina_matrixsparse_init_count; + + if (!_eina_matrixsparse_init_count) + { + eina_mempool_del(_eina_matrixsparse_row_mp); + eina_mempool_del(_eina_matrixsparse_cell_mp); + + eina_mempool_shutdown(); + eina_magic_string_shutdown(); + eina_error_shutdown(); + } + + return _eina_matrixsparse_init_count; +} + +/** + * @brief Create a new Sparse Matrix. + * + * @param rows number of rows in matrix. Operations with rows greater than this + * value will fail. + * @param cols number of columns in matrix. Operations with columns greater + * than this value will fail. + * @param free_func used to delete cell data contents, used by + * eina_matrixsparse_free(), eina_matrixsparse_size_set(), + * eina_matrixsparse_row_idx_clear(), + * eina_matrixsparse_column_idx_clear(), + * eina_matrixsparse_cell_idx_clear() and possible others. + * @param user_data given to @a free_func as first parameter. + * + * @return newly allocated matrix or NULL if allocation failed and eina_error + * is set. + */ +EAPI Eina_Matrixsparse * +eina_matrixsparse_new(unsigned long rows, unsigned long cols, void (*free_func)(void *user_data, void *cell_data), const void *user_data) +{ + Eina_Matrixsparse *m; + + EINA_SAFETY_ON_FALSE_RETURN_VAL(rows > 0, NULL); + EINA_SAFETY_ON_FALSE_RETURN_VAL(cols > 0, NULL); + + m = malloc(sizeof(Eina_Matrixsparse)); + if (!m) + { + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + return NULL; + } + + m->rows = NULL; + m->last_row = NULL; + m->last_used = NULL; + + m->size.rows = rows; + m->size.cols = cols; + m->free.func = free_func; + m->free.user_data = (void *)user_data; + + EINA_MAGIC_SET(m, EINA_MAGIC_MATRIXSPARSE); + eina_error_set(0); + return m; +} + +/** + * @brief Free resources allocated to Sparse Matrix. + * + * @param m The Sparse Matrix instance to free, must @b not be @c NULL. + */ +EAPI void +eina_matrixsparse_free(Eina_Matrixsparse *m) +{ + Eina_Matrixsparse_Row *r; + EINA_MAGIC_CHECK_MATRIXSPARSE(m); + void (*free_func)(void *, void *) = m->free.func; + void *user_data = m->free.user_data; + + r = m->rows; + while (r) + { + Eina_Matrixsparse_Row *r_aux = r; + r = r->next; + _eina_matrixsparse_row_free(r_aux, free_func, user_data); + } + + EINA_MAGIC_SET(m, EINA_MAGIC_NONE); + free(m); +} + +/** + * @brief Get the current size of Sparse Matrix. + * + * The given parameters are guaranteed to be set if they're not NULL, + * even if this function fails (ie: @a m is not a valid matrix instance). + * + * @param m the sparse matrix to operate on. + * @param rows returns the number of rows, may be NULL. If @a m is invalid, + * returned value is zero, otherwise it's a positive integer. + * @param cols returns the number of columns, may be NULL. If @a m is + * invalid, returned value is zero, otherwise it's a positive integer. + */ +EAPI void +eina_matrixsparse_size_get(const Eina_Matrixsparse *m, unsigned long *rows, unsigned long *cols) +{ + if (rows) *rows = 0; + if (cols) *cols = 0; + EINA_MAGIC_CHECK_MATRIXSPARSE(m); + if (rows) *rows = m->size.rows; + if (cols) *cols = m->size.cols; +} + +/** + * @brief Resize the Sparse Matrix. + * + * This will resize the sparse matrix, possibly freeing cells on rows + * and columns that will cease to exist. + * + * @param m the sparse matrix to operate on. + * @param rows the new number of rows, must be greater than zero. + * @param cols the new number of columns, must be greater than zero. + * @return 1 on success, 0 on failure. + * + * @warning cells, rows or columns are not reference counted and thus + * after this call any reference might be invalid if instance were + * freed. + */ +EAPI Eina_Bool +eina_matrixsparse_size_set(Eina_Matrixsparse *m, unsigned long rows, unsigned long cols) +{ + Eina_Bool update_last_used_row; + Eina_Matrixsparse_Row *r; + void (*free_func)(void *, void *); + void *user_data; + + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(rows > 0, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(cols > 0, 0); + + if ((rows == m->size.rows) && (cols == m->size.cols)) return 1; + + update_last_used_row = ((m->last_used) && (m->last_used->row >= rows)); + free_func = m->free.func; + user_data = m->free.user_data; + + r = m->last_row; + while (r && r->row >= rows) + { + Eina_Matrixsparse_Row *r_aux = r; + r = r->prev; + _eina_matrixsparse_row_free(r_aux, free_func, user_data); + } + if (!r) + { + m->last_row = NULL; + m->rows = NULL; + } + else if (r != m->last_row) + { + r->next = NULL; + m->last_row = r; + } + + if (update_last_used_row) + m->last_used = m->last_row; + + r = m->rows; + while (r) + { + Eina_Matrixsparse_Cell *c = r->last_col; + Eina_Bool update_last_used_col; + update_last_used_col = ((r->last_used) && (r->last_used->col >= cols)); + while (c && c->col >= cols) + { + Eina_Matrixsparse_Cell *c_aux = c; + c = c->prev; + _eina_matrixsparse_cell_free(c_aux, free_func, user_data); + } + if (!c) + { + r->cols = NULL; + r->last_col = NULL; + Eina_Matrixsparse_Row *r_aux = r; + if (r->next) + r->next->prev = r->prev; + else + m->last_row = r->prev; + if (r->prev) + r->prev->next = r->next; + else + m->rows = r->next; + r = r->next; + _eina_matrixsparse_row_free(r_aux, free_func, user_data); + } + else + { + if (c != r->last_col) + { + c->next = NULL; + r->last_col = c; + } + if (update_last_used_col) + r->last_used = r->last_col; + + r = r->next; + } + } + + update_last_used_row = 0; + if (m->last_used) + { + if (m->last_row) + update_last_used_row = m->last_used->row > m->last_row->row; + else + update_last_used_row = 1; + } + + if (update_last_used_row) + m->last_used = m->last_row; + + m->size.rows = rows; + m->size.cols = cols; + return 1; +} + +/** + * Get the cell reference inside Sparse Matrix. + * + * @param m the sparse matrix to operate on. + * @param row the new number of row to clear. + * @param col the new number of column to clear. + * @param cell pointer to return cell reference, if any exists. + * + * @return 1 on success, 0 on failure. It is considered success if did not + * exist but index is inside matrix size, in this case @c *cell == NULL + * + * @see eina_matrixsparse_cell_data_get() + * @see eina_matrixsparse_data_idx_get() + */ +EAPI Eina_Bool +eina_matrixsparse_cell_idx_get(const Eina_Matrixsparse *m, unsigned long row, unsigned long col, Eina_Matrixsparse_Cell **cell) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_NULL_RETURN_VAL(cell, 0); + *cell = NULL; + EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0); + *cell = _eina_matrixsparse_cell_idx_get(m, row, col); + return 1; +} + +/** + * Get data associated with given cell reference. + * + * @param cell given cell reference, must @b not be @c NULL. + * + * @return data associated with given cell. + * + * @see eina_matrixsparse_cell_idx_get() + * @see eina_matrixsparse_data_idx_get() + */ +EAPI void * +eina_matrixsparse_cell_data_get(const Eina_Matrixsparse_Cell *cell) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, NULL); + return cell->data; +} + +/** + * Get data associated with given cell given its indexes. + * + * @param m the sparse matrix to operate on. + * @param row the new number of row to clear. + * @param col the new number of column to clear. + * + * @return data associated with given cell or NULL if nothing is associated. + * + * @see eina_matrixsparse_cell_idx_get() + * @see eina_matrixsparse_cell_data_get() + */ +EAPI void * +eina_matrixsparse_data_idx_get(const Eina_Matrixsparse *m, unsigned long row, unsigned long col) +{ + Eina_Matrixsparse_Cell *c; + EINA_MAGIC_CHECK_MATRIXSPARSE(m, NULL); + c = _eina_matrixsparse_cell_idx_get(m, row, col); + if (c) return c->data; + else return NULL; +} + +/** + * Get position (indexes) of the given cell. + * + * @param cell the cell reference, must @b not be @c NULL. + * @param row where to store cell row number, may be @c NULL. + * @param col where to store cell column number, may be @c NULL. + * + * @return 1 on success, 0 otherwise (@c cell is @c NULL). + */ +EAPI Eina_Bool +eina_matrixsparse_cell_position_get(const Eina_Matrixsparse_Cell *cell, unsigned long *row, unsigned long *col) +{ + if (row) *row = 0; + if (col) *col = 0; + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0); + EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0); + if (row) *row = cell->parent->row; + if (col) *col = cell->col; + return 1; +} + +/** + * Change cell reference value without freeing the possibly existing old value. + * + * @param cell the cell reference, must @b not be @c NULL. + * @param data new data to set. + * @param p_old returns the old value intact (not freed). + * + * @return 1 on success, 0 otherwise (@a cell is @c NULL). + * + * @see eina_matrixsparse_cell_data_set() + * @see eina_matrixsparse_data_idx_replace() + */ +EAPI Eina_Bool +eina_matrixsparse_cell_data_replace(Eina_Matrixsparse_Cell *cell, const void *data, void **p_old) +{ + if (p_old) *p_old = NULL; + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0); + + if (p_old) *p_old = cell->data; + cell->data = (void *)data; + return 1; +} + +/** + * Change cell value freeing the possibly existing old value. + * + * In contrast to eina_matrixsparse_cell_data_replace(), this function will + * call @c free_func() on existing value. + * + * @param cell the cell reference, must @b not be @c NULL. + * @param data new data to set. + * + * @return 1 on success, 0 otherwise (@a cell is @c NULL). + * + * @see eina_matrixsparse_cell_data_replace() + * @see eina_matrixsparse_data_idx_set() + */ +EAPI Eina_Bool +eina_matrixsparse_cell_data_set(Eina_Matrixsparse_Cell *cell, const void *data) +{ + Eina_Matrixsparse *m; + + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0); + EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0); + EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0); + + m = cell->parent->parent; + + if (m->free.func) + m->free.func(m->free.user_data, cell->data); + + cell->data = (void *)data; + return 1; +} + +/** + * Change cell value without freeing the possibly existing old value, using + * indexes. + * + * @param cell the cell reference, must @b not be @c NULL. + * @param row the row number to set the value. + * @param col the column number to set the value. + * @param data new data to set. + * @param p_old returns the old value intact (not freed). + * + * @return 1 on success, 0 otherwise (@a m is @c NULL, indexes are not valid). + * + * @see eina_matrixsparse_cell_data_replace() + * @see eina_matrixsparse_data_idx_set() + */ +EAPI Eina_Bool +eina_matrixsparse_data_idx_replace(Eina_Matrixsparse *m, unsigned long row, unsigned long col, const void *data, void **p_old) +{ + Eina_Matrixsparse_Cell *cell; + + if (p_old) *p_old = NULL; + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0); + + cell = _eina_matrixsparse_cell_idx_get(m, row, col); + if (cell) + { + if (p_old) *p_old = cell->data; + cell->data = (void *)data; + return 1; + } + + return _eina_matrixsparse_cell_idx_add(m, row, col, data); +} + +/** + * Change cell value freeing the possibly existing old value, using + * indexes. + * + * In contrast to eina_matrixsparse_data_idx_replace(), this function will + * call @c free_func() on existing value. + * + * @param cell the cell reference, must @b not be @c NULL. + * @param row the row number to set the value. + * @param col the column number to set the value. + * @param data new data to set. + * + * @return 1 on success, 0 otherwise (@a m is @c NULL, indexes are not valid). + * + * @see eina_matrixsparse_cell_data_replace() + */ +EAPI Eina_Bool +eina_matrixsparse_data_idx_set(Eina_Matrixsparse *m, unsigned long row, unsigned long col, const void *data) +{ + Eina_Matrixsparse_Cell *cell; + + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0); + + cell = _eina_matrixsparse_cell_idx_get(m, row, col); + if (cell) + { + if (m->free.func) + m->free.func(m->free.user_data, cell->data); + cell->data = (void *)data; + return 1; + } + + return _eina_matrixsparse_cell_idx_add(m, row, col, data); +} + +/** + * Clear (erase all cells) of row given its index. + * + * Existing cells will be cleared with @c free_func() given to + * eina_matrixsparse_new(). + * + * @param m the sparse matrix to operate on. + * @param row the new number of row to clear. + * + * @return 1 on success, 0 on failure. It is considered success if row + * had no cells filled. Failure is asking for clear row outside + * matrix size. + * + * @warning cells, rows or columns are not reference counted and thus + * after this call any reference might be invalid if instance were + * freed. + */ +EAPI Eina_Bool +eina_matrixsparse_row_idx_clear(Eina_Matrixsparse *m, unsigned long row) +{ + Eina_Matrixsparse_Row *r; + + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0); + + r = _eina_matrixsparse_row_idx_get(m, row); + if (!r) return 1; + + _eina_matrixsparse_row_unlink(r); + _eina_matrixsparse_row_free(r, m->free.func, m->free.user_data); + + return 1; +} + +/** + * Clear (erase all cells) of column given its index. + * + * Existing cells will be cleared with @c free_func() given to + * eina_matrixsparse_new(). + * + * @param m the sparse matrix to operate on. + * @param col the new number of column to clear. + * + * @return 1 on success, 0 on failure. It is considered success if column + * had no cells filled. Failure is asking for clear column outside + * matrix size. + * + * @warning cells, rows or columns are not reference counted and thus + * after this call any reference might be invalid if instance were + * freed. + */ +EAPI Eina_Bool +eina_matrixsparse_column_idx_clear(Eina_Matrixsparse *m, unsigned long col) +{ + Eina_Matrixsparse_Row *r; + void (*free_func)(void *, void *); + void *user_data; + + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0); + + free_func = m->free.func; + user_data = m->free.user_data; + + for (r = m->rows; r != NULL;) + { + Eina_Matrixsparse_Row *r_aux = r; + Eina_Matrixsparse_Cell *c; + + c = _eina_matrixsparse_row_cell_idx_get(r, col); + r = r->next; + + if (!c) + continue; + + if ((r_aux->cols != c) || (r_aux->last_col != c)) + { + _eina_matrixsparse_cell_unlink(c); + _eina_matrixsparse_cell_free(c, free_func, user_data); + } + else + { + _eina_matrixsparse_row_unlink(r_aux); + _eina_matrixsparse_row_free(r_aux, free_func, user_data); + } + } + + return 1; +} + +/** + * Clear (erase) cell given its indexes. + * + * Existing cell will be cleared with @c free_func() given to + * eina_matrixsparse_new(). + * + * @param m the sparse matrix to operate on. + * @param row the new number of row to clear. + * @param col the new number of column to clear. + * + * @return 1 on success, 0 on failure. It is considered success if did not + * exist but index is inside matrix size. + * + * @warning cells, rows or columns are not reference counted and thus + * after this call any reference might be invalid if instance were + * freed. Note that this call might delete container column and + * row if this cell was the last remainder. + */ +EAPI Eina_Bool +eina_matrixsparse_cell_idx_clear(Eina_Matrixsparse *m, unsigned long row, unsigned long col) +{ + Eina_Matrixsparse_Cell *c; + + EINA_MAGIC_CHECK_MATRIXSPARSE(m, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(row < m->size.rows, 0); + EINA_SAFETY_ON_FALSE_RETURN_VAL(col < m->size.cols, 0); + + c = _eina_matrixsparse_cell_idx_get(m, row, col); + if (!c) return 1; + + _eina_matrixsparse_cell_unlink(c); + _eina_matrixsparse_cell_free(c, m->free.func, m->free.user_data); + + return 1; +} + +/** + * Clear (erase) cell given its reference. + * + * @param cell the cell reference, must @b not be @c NULL. + * + * @return 1 on success, 0 on failure. + * + * @warning cells, rows or columns are not reference counted and thus + * after this call any reference might be invalid if instance were + * freed. Note that this call might delete container column and + * row if this cell was the last remainder. + */ +EAPI Eina_Bool +eina_matrixsparse_cell_clear(Eina_Matrixsparse_Cell *cell) +{ + Eina_Matrixsparse *m; + + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, 0); + EINA_MAGIC_CHECK_MATRIXSPARSE_ROW(cell->parent, 0); + EINA_MAGIC_CHECK_MATRIXSPARSE(cell->parent->parent, 0); + + m = cell->parent->parent; + + _eina_matrixsparse_cell_unlink(cell); + _eina_matrixsparse_cell_free(cell, m->free.func, m->free.user_data); + return 1; +} + +/** + * Creates a new iterator over existing matrix cells. + * + * This is a cheap walk, it will just report existing cells and holes + * in the sparse matrix will be ignored. That means the reported + * indexes will not be sequential. + * + * The iterator data will be the cell reference, one may query current + * position with eina_matrixsparse_cell_position_get() and cell value + * with eina_matrixsparse_cell_data_get(). + * + * @param m The Sparse Matrix reference, must @b not be @c NULL. + * @return A new iterator. + * + * @warning if the matrix structure changes then the iterator becomes + * invalid! That is, if you add or remove cells this iterator + * behavior is undefined and your program may crash! + */ +EAPI Eina_Iterator * +eina_matrixsparse_iterator_new(const Eina_Matrixsparse *m) +{ + Eina_Matrixsparse_Iterator *it; + + it = calloc(1, sizeof(*it)); + if (!it) + { + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + return NULL; + } + + EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR); + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); + + it->m = m; + it->ref.row = m->rows; + it->ref.col = m->rows ? m->rows->cols : NULL; + + it->iterator.next = FUNC_ITERATOR_NEXT(_eina_matrixsparse_iterator_next); + it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(_eina_matrixsparse_iterator_get_container); + it->iterator.free = FUNC_ITERATOR_FREE(_eina_matrixsparse_iterator_free); + return &it->iterator; +} + +/** + * Creates a new iterator over all matrix cells. + * + * Unlike eina_matrixsparse_iterator_new() this one will report all + * matrix cells, even those that are still empty (holes). These will + * be reported as dummy cells that contains no data. + * + * Be aware that iterating a big matrix (1000x1000) will call your + * function that number of times (1000000 times in that case) even if + * your matrix have no elements at all! + * + * The iterator data will be the cell reference, one may query current + * position with eina_matrixsparse_cell_position_get() and cell value + * with eina_matrixsparse_cell_data_get(). If cell is empty then the + * reference will be a dummy/placeholder, thus setting value with + * eina_matrixsparse_cell_data_set() will leave pointer unreferenced. + * + * @param m The Sparse Matrix reference, must @b not be @c NULL. + * @return A new iterator. + * + * @warning if the matrix structure changes then the iterator becomes + * invalid! That is, if you add or remove cells this iterator + * behavior is undefined and your program may crash! + */ +EAPI Eina_Iterator * +eina_matrixsparse_iterator_complete_new(const Eina_Matrixsparse *m) +{ + Eina_Matrixsparse_Iterator_Complete *it; + + it = calloc(1, sizeof(*it)); + if (!it) + { + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + return NULL; + } + + EINA_MAGIC_SET(it, EINA_MAGIC_MATRIXSPARSE_ITERATOR); + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); + + it->m = m; + it->idx.row = 0; + it->idx.col = 0; + it->ref.row = m->rows; + it->ref.col = m->rows ? m->rows->cols : NULL; + + it->dummy.row.next = it->dummy.row.prev = NULL; + it->dummy.row.cols = it->dummy.row.last_col = it->dummy.row.last_used = NULL; + it->dummy.row.parent = (Eina_Matrixsparse *)m; + EINA_MAGIC_SET(&it->dummy.row, EINA_MAGIC_MATRIXSPARSE_ROW); + + it->dummy.col.next = it->dummy.col.prev = NULL; + it->dummy.col.data = NULL; + it->dummy.col.parent = &it->dummy.row; + EINA_MAGIC_SET(&it->dummy.col, EINA_MAGIC_MATRIXSPARSE_CELL); + + it->iterator.next = FUNC_ITERATOR_NEXT(_eina_matrixsparse_iterator_complete_next); + it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(_eina_matrixsparse_iterator_complete_get_container); + it->iterator.free = FUNC_ITERATOR_FREE(_eina_matrixsparse_iterator_complete_free); + return &it->iterator; +} diff --git a/src/tests/Makefile.am b/src/tests/Makefile.am index e18431c..d616380 100644 --- a/src/tests/Makefile.am +++ b/src/tests/Makefile.am @@ -65,7 +65,8 @@ eina_test_file.c \ eina_test_benchmark.c \ eina_test_mempool.c \ eina_test_rectangle.c \ -eina_test_list.c +eina_test_list.c \ +eina_test_matrixsparse.c eina_suite_LDADD = @CHECK_LIBS@ $(top_builddir)/src/lib/libeina.la diff --git a/src/tests/eina_suite.c b/src/tests/eina_suite.c index a7ec5e5..b7a37cf 100644 --- a/src/tests/eina_suite.c +++ b/src/tests/eina_suite.c @@ -53,6 +53,7 @@ static const Eina_Test_Case etc[] = { { "Benchmark", eina_test_benchmark }, { "Mempool", eina_test_mempool }, { "Rectangle", eina_test_rectangle }, + { "Matrix Sparse", eina_test_matrixsparse }, { NULL, NULL } }; diff --git a/src/tests/eina_suite.h b/src/tests/eina_suite.h index 91c1e31..2928c05 100644 --- a/src/tests/eina_suite.h +++ b/src/tests/eina_suite.h @@ -41,5 +41,6 @@ void eina_test_file(TCase *tc); void eina_test_benchmark(TCase *tc); void eina_test_mempool(TCase *tc); void eina_test_rectangle(TCase *tc); +void eina_test_matrixsparse(TCase *tc); #endif /* EINA_SUITE_H_ */ diff --git a/src/tests/eina_test_matrixsparse.c b/src/tests/eina_test_matrixsparse.c new file mode 100644 index 0000000..1ba922d --- /dev/null +++ b/src/tests/eina_test_matrixsparse.c @@ -0,0 +1,481 @@ +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include + +#include "eina_matrixsparse.h" +#include "eina_suite.h" + +#define MAX_ROWS 10 +#define MAX_COLS 10 + +static void eina_matrixsparse_free_cell_cb(void *user_data, void *cell_data) +{ + long *value = cell_data; + long **data = user_data; +} + +static void matrixsparse_initialize(Eina_Matrixsparse *matrix, long data[MAX_ROWS][MAX_COLS], unsigned long nrows, unsigned long ncols) +{ + unsigned long i, j; + Eina_Bool r; + + for (i = 0; i < nrows; i++) + for (j = 0; j < ncols; j++) + if (data[i][j] != 0) + { + r = eina_matrixsparse_data_idx_set(matrix, i, j, &data[i][j]); + fail_if(r == EINA_FALSE); + } +} + +static void matrixsparse_check(Eina_Matrixsparse *matrix, long data[MAX_ROWS][MAX_COLS], unsigned long nrows, unsigned long ncols) +{ + unsigned long i, j; + long *test1; + + for (i = 0; i < MAX_ROWS; i++) + for (j = 0; j < MAX_COLS; j++) + { + if (data[i][j] != 0) + { + test1 = eina_matrixsparse_data_idx_get(matrix, i, j); + fail_if(test1 == NULL || *test1 != data[i][j]); + } + else + { + test1 = eina_matrixsparse_data_idx_get(matrix, i, j); + fail_if(test1 != NULL); + } + } +} + +START_TEST(eina_test_simple) +{ + Eina_Matrixsparse *matrix = NULL; + Eina_Matrixsparse_Cell *cell = NULL; + Eina_Bool r; + long *test1, value, value2, value3, value4; + unsigned long i, j; + unsigned long nrows, ncols, row, col; + + long data[MAX_ROWS][MAX_COLS]; + + for (i = 0; i < MAX_ROWS; i++) + for (j = 0; j < MAX_COLS; j++) + data[i][j] = 0; + + data[0][3] = 3; + data[1][3] = 13; + data[1][6] = 16; + data[1][9] = 19; + data[1][8] = 18; + data[1][7] = 17; + data[2][8] = 28; + data[2][7] = 27; + data[2][6] = 26; + data[3][5] = 35; + data[3][6] = 36; + data[3][7] = 37; + data[3][9] = 39; + data[3][0] = 30; + data[4][6] = 46; + data[4][8] = 48; + data[4][2] = 42; + data[4][3] = 43; + data[4][7] = 47; + data[5][3] = 53; + data[6][3] = 63; + data[6][4] = 64; + data[6][6] = 66; + data[7][3] = 73; + data[7][7] = 77; + data[8][8] = 88; + + value = -1; + value2 = -2; + value3 = -3; + value4 = -4; + + eina_matrixsparse_init(); + + matrix = eina_matrixsparse_new(MAX_ROWS, MAX_COLS, + eina_matrixsparse_free_cell_cb, data); + fail_if(matrix == NULL); + + r = eina_matrixsparse_cell_idx_get(matrix, 3, 5, &cell); + fail_if(r == EINA_FALSE); + fail_if(cell != NULL); + + matrixsparse_initialize(matrix, data, MAX_ROWS, MAX_COLS); + + /* data fetching */ + test1 = eina_matrixsparse_data_idx_get(matrix, 3, 0); + fail_if(test1 == NULL); + fail_if(*test1 != data[3][0]); + + test1 = eina_matrixsparse_data_idx_get(matrix, 3, 5); + fail_if(test1 == NULL); + fail_if(*test1 != data[3][5]); + + test1 = eina_matrixsparse_data_idx_get(matrix, 3, 6); + fail_if(test1 == NULL); + fail_if(*test1 != data[3][6]); + + test1 = eina_matrixsparse_data_idx_get(matrix, 3, 1); + fail_if(test1 != NULL); + + r = eina_matrixsparse_cell_idx_get(matrix, 3, 5, &cell); + fail_if(r == EINA_FALSE); + fail_if(cell == NULL); + + test1 = eina_matrixsparse_cell_data_get(cell); + fail_if(test1 == NULL); + fail_if(*test1 != data[3][5]); + + r = eina_matrixsparse_cell_position_get(cell, &row, &col); + fail_if(r == EINA_FALSE); + fail_if(row != 3 || col != 5); + + test1 = eina_matrixsparse_data_idx_get(matrix, 4, 3); + fail_if(*test1 != data[4][3]); + + test1 = eina_matrixsparse_data_idx_get(matrix, 1, 3); + fail_if(*test1 != data[1][3]); + + /* data changing */ + r = eina_matrixsparse_data_idx_set(matrix, 1, 9, &data[1][9]); + fail_if(r == EINA_FALSE); + + r = eina_matrixsparse_data_idx_replace(matrix, 4, 3, &value, &test1); + fail_if(r == EINA_FALSE); + fail_if(test1 == NULL); + fail_if(*test1 != data[4][3]); + data[4][3] = value; + + test1 = eina_matrixsparse_data_idx_get(matrix, 4, 3); + fail_if(test1 == NULL || *test1 != value); + + r = eina_matrixsparse_cell_data_replace(cell, &value2, &test1); + fail_if(r == EINA_FALSE); + fail_if(test1 == NULL); + fail_if(*test1 != data[3][5]); + data[3][5] = value2; + + test1 = eina_matrixsparse_data_idx_get(matrix, 3, 5); + fail_if(test1 == NULL); + fail_if(*test1 != value2); + + r = eina_matrixsparse_cell_idx_get(matrix, 4, 2, &cell); + fail_if(r == EINA_FALSE || cell == NULL); + + r = eina_matrixsparse_cell_data_set(cell, &value3); + fail_if(r == EINA_FALSE); + data[4][2] = value3; + + test1 = eina_matrixsparse_data_idx_get(matrix, 4, 2); + fail_if(test1 == NULL || *test1 != value3); + + r = eina_matrixsparse_data_idx_replace(matrix, 6, 5, &value4, &test1); + fail_if(r == EINA_FALSE || test1 != NULL); + data[6][5] = value4; + + + /* cell deletion */ + r = eina_matrixsparse_row_idx_clear(matrix, 4); + fail_if(r == EINA_FALSE); + data[4][6] = 0; + data[4][8] = 0; + data[4][2] = 0; + data[4][3] = 0; + data[4][7] = 0; + + test1 = eina_matrixsparse_data_idx_get(matrix, 4, 3); + fail_if(test1 != NULL); + + test1 = eina_matrixsparse_data_idx_get(matrix, 4, 8); + fail_if(test1 != NULL); + + test1 = eina_matrixsparse_data_idx_get(matrix, 5, 3); + fail_if(*test1 != data[5][3]); + + r = eina_matrixsparse_column_idx_clear(matrix, 3); + fail_if(r != EINA_TRUE); + data[0][3] = 0; + data[1][3] = 0; + data[4][3] = 0; + data[5][3] = 0; + data[6][3] = 0; + data[7][3] = 0; + + r = eina_matrixsparse_cell_idx_clear(matrix, 3, 5); + fail_if(r != EINA_TRUE); + data[3][5] = 0; + + r = eina_matrixsparse_cell_idx_clear(matrix, 3, 9); + fail_if(r != EINA_TRUE); + data[3][9] = 0; + + r = eina_matrixsparse_cell_idx_clear(matrix, 4, 3); + fail_if(r != EINA_TRUE); + data[4][3] = 0; + + r = eina_matrixsparse_cell_idx_get(matrix, 3, 7, &cell); + fail_if(r == EINA_FALSE); + fail_if(cell == NULL); + + r = eina_matrixsparse_cell_clear(cell); + fail_if(r == EINA_FALSE); + data[3][7] = 0; + + r = eina_matrixsparse_cell_idx_get(matrix, 2, 7, &cell); + fail_if(r == EINA_FALSE); + + r = eina_matrixsparse_cell_idx_clear(matrix, 2, 8); + fail_if(r == EINA_FALSE); + data[2][8] = 0; + + r = eina_matrixsparse_cell_idx_clear(matrix, 2, 7); + fail_if(r == EINA_FALSE); + data[2][7] = 0; + + r = eina_matrixsparse_cell_idx_get(matrix, 7, 7, &cell); + fail_if(r == EINA_FALSE); + + r = eina_matrixsparse_row_idx_clear(matrix, 8); + fail_if(r == EINA_FALSE); + data[8][8] = 0; + + r = eina_matrixsparse_row_idx_clear(matrix, 7); + fail_if(r == EINA_FALSE); + data[7][3] = 0; + data[7][7] = 0; + + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + eina_matrixsparse_free(matrix); + + eina_matrixsparse_shutdown(); +} +END_TEST + +START_TEST(eina_test_resize) +{ + Eina_Matrixsparse *matrix = NULL; + Eina_Matrixsparse_Cell *cell = NULL; + Eina_Bool r; + long *test1; + unsigned long i, j; + unsigned long nrows, ncols; + + long data[MAX_ROWS][MAX_COLS]; + + for (i = 0; i < MAX_ROWS; i++) + for (j = 0; j < MAX_COLS; j++) + data[i][j] = 0; + + eina_matrixsparse_init(); + + matrix = eina_matrixsparse_new(MAX_ROWS, MAX_COLS, + eina_matrixsparse_free_cell_cb, data); + fail_if(matrix == NULL); + + /* cell insertion */ + data[0][5] = 5; + data[1][0] = 10; + data[1][3] = 13; + data[1][6] = 16; + data[1][9] = 19; + data[1][8] = 18; + data[1][7] = 17; + data[2][8] = 28; + data[2][7] = 27; + data[2][6] = 26; + data[3][0] = 30; + data[3][5] = 35; + data[3][6] = 36; + data[3][7] = 37; + data[3][9] = 39; + data[3][0] = 30; + data[4][8] = 48; + data[4][2] = 42; + data[4][3] = 43; + data[4][7] = 47; + data[4][6] = 46; + data[5][3] = 53; + data[6][3] = 63; + data[6][4] = 64; + data[6][6] = 66; + data[7][3] = 73; + data[7][7] = 77; + data[8][8] = 88; + + matrixsparse_initialize(matrix, data, MAX_ROWS, MAX_COLS); + + eina_matrixsparse_size_get(matrix, &nrows, &ncols); + fail_if(nrows != MAX_ROWS || ncols != MAX_COLS); + + r = eina_matrixsparse_size_set(matrix, nrows - 2, ncols - 2); + fail_if(r == EINA_FALSE); + data[1][9] = 0; + data[1][8] = 0; + data[2][8] = 0; + data[3][9] = 0; + data[4][8] = 0; + data[8][8] = 0; + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + + r = eina_matrixsparse_size_set(matrix, 5, 1); + fail_if(r == EINA_FALSE); + data[0][5] = 0; + data[1][3] = 0; + data[1][6] = 0; + data[1][7] = 0; + data[2][7] = 0; + data[2][6] = 0; + data[3][5] = 0; + data[3][6] = 0; + data[3][7] = 0; + data[4][2] = 0; + data[4][3] = 0; + data[4][7] = 0; + data[4][6] = 0; + data[5][3] = 0; + data[6][3] = 0; + data[6][4] = 0; + data[6][6] = 0; + data[7][3] = 0; + data[7][7] = 0; + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + + r = eina_matrixsparse_size_set(matrix, 1, 1); + fail_if(r == EINA_FALSE); + data[3][0] = 0; + data[1][0] = 0; + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + + r = eina_matrixsparse_size_set(matrix, 5, 4); + fail_if(r == EINA_FALSE); + + r = eina_matrixsparse_data_idx_set(matrix, 4, 2, &data[4][2]); + fail_if(r == EINA_FALSE); + data[4][2] = 42; + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + + r = eina_matrixsparse_size_set(matrix, 5, 1); + fail_if(r == EINA_FALSE); + data[4][2] = 0; + matrixsparse_check(matrix, data, MAX_ROWS, MAX_COLS); + + eina_matrixsparse_free(matrix); + + eina_matrixsparse_shutdown(); +} +END_TEST + +START_TEST(eina_test_iterators) +{ + Eina_Matrixsparse *matrix = NULL; + Eina_Matrixsparse_Cell *cell = NULL; + Eina_Iterator *it = NULL; + Eina_Bool r; + long *test1, value; + unsigned long i, j; + unsigned long row, col; + + long data[MAX_ROWS][MAX_COLS]; + + value = 0; + for (i = 0; i < MAX_ROWS; i++) + { + for (j = 0; j < MAX_COLS; j++) + { + data[i][j] = value++; + printf("%4ld ", data[i][j]); + } + printf("\n"); + } + + eina_matrixsparse_init(); + + matrix = eina_matrixsparse_new(MAX_ROWS, MAX_COLS, + eina_matrixsparse_free_cell_cb, data); + fail_if(matrix == NULL); + + r = eina_matrixsparse_data_idx_set(matrix, 3, 5, &data[3][5]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 3, 6, &data[3][6]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 3, 7, &data[3][7]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 3, 9, &data[3][9]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 3, 0, &data[3][0]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 4, 6, &data[4][6]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 4, 8, &data[4][8]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 4, 2, &data[4][2]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 4, 3, &data[4][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 4, 7, &data[4][7]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 6, 4, &data[6][4]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 5, 3, &data[5][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 6, 3, &data[6][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 7, 3, &data[7][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 0, 3, &data[0][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 1, 3, &data[1][3]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 1, 6, &data[1][6]); + fail_if(r == EINA_FALSE); + r = eina_matrixsparse_data_idx_set(matrix, 1, 9, &data[1][9]); + fail_if(r == EINA_FALSE); + + it = eina_matrixsparse_iterator_new(matrix); + fail_if(it == NULL); + EINA_ITERATOR_FOREACH(it, cell) + { + fail_if(cell == NULL); + r = eina_matrixsparse_cell_position_get(cell, &row, &col); + fail_if(r == EINA_FALSE); + + test1 = eina_matrixsparse_cell_data_get(cell); + fail_if(test1 == NULL || *test1 != data[row][col]); + } + eina_iterator_free(it); + + it = eina_matrixsparse_iterator_complete_new(matrix); + fail_if(it == NULL); + EINA_ITERATOR_FOREACH(it, cell) + { + fail_if(cell == NULL); + r = eina_matrixsparse_cell_position_get(cell, &row, &col); + fail_if(r == EINA_FALSE); + + test1 = eina_matrixsparse_cell_data_get(cell); + if (test1) + fail_if(*test1 != data[row][col]); + } + eina_iterator_free(it); + + eina_matrixsparse_free(matrix); + + eina_matrixsparse_shutdown(); +} +END_TEST + +void +eina_test_matrixsparse(TCase *tc) +{ + tcase_add_test(tc, eina_test_simple); + tcase_add_test(tc, eina_test_resize); + tcase_add_test(tc, eina_test_iterators); +} -- 2.7.4