From dd7595a3475407a7fa96a97393bae8c5220e8762 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Wed, 4 Jan 2012 18:41:13 +1000 Subject: Add the base Enlightenment Foundation Libraries - eina, eet, evas, ecore, embryo, and edje. Note that embryo wont be used, but I'm not sure yet if you can build edje without it. --- libraries/eina/src/lib/eina_matrixsparse.c | 1421 ++++++++++++++++++++++++++++ 1 file changed, 1421 insertions(+) create mode 100644 libraries/eina/src/lib/eina_matrixsparse.c (limited to 'libraries/eina/src/lib/eina_matrixsparse.c') diff --git a/libraries/eina/src/lib/eina_matrixsparse.c b/libraries/eina/src/lib/eina_matrixsparse.c new file mode 100644 index 0000000..3ac0439 --- /dev/null +++ b/libraries/eina/src/lib/eina_matrixsparse.c @@ -0,0 +1,1421 @@ +/* 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 Sparse Matrix 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_private.h" +#include "eina_error.h" +#include "eina_log.h" +#include "eina_magic.h" +#include "eina_mempool.h" + +/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ +#include "eina_safety_checks.h" +#include "eina_matrixsparse.h" + + +/*============================================================================* +* Local * +*============================================================================*/ + +/** + * @cond LOCAL + */ + +static const char EINA_MAGIC_MATRIXSPARSE_STR[] = "Eina Matrixsparse"; +static const char EINA_MAGIC_MATRIXSPARSE_ROW_STR[] = "Eina Matrixsparse Row"; +static const char EINA_MAGIC_MATRIXSPARSE_CELL_STR[] = "Eina Matrixsparse Cell"; +static const char EINA_MAGIC_MATRIXSPARSE_ITERATOR_STR[] = + "Eina Matrixsparse Iterator"; +static const char EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR_STR[] = + "Eina Matrixsparse Row Accessor"; +static const char EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR_STR[] = + "Eina Matrixsparse Row Iterator"; +static const char EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR_STR[] = + "Eina Matrixsparse Cell Accessor"; +static const char EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR_STR[] = + "Eina Matrixsparse Cell Iterator"; + + +#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_log_dom = -1; + +#ifdef ERR +#undef ERR +#endif +#define ERR(...) EINA_LOG_DOM_ERR(_eina_matrixsparse_log_dom, __VA_ARGS__) + +#ifdef DBG +#undef DBG +#endif +#define DBG(...) EINA_LOG_DOM_DBG(_eina_matrixsparse_log_dom, __VA_ARGS__) + +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; + + 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; 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; 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; 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; 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; r = r->next) + if (r->row > row) + break; + + assert(r != NULL); + *p_prev = r->prev; + *p_next = r; + } + else if (dir < 0) + { + for (; r; 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; c = c->next) + if (c->col > col) + break; + + assert(c != NULL); + *p_prev = c->prev; + *p_next = c; + } + else if (dir < 0) + { + for (; c; 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) + ERR("Last iterator call changed dummy cell!"); + + 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; + it->dummy.col.col = it->idx.col; + it->dummy.row.row = it->idx.row; + *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) + ERR("Last iterator call changed dummy cell!"); + + EINA_MAGIC_SET(it, EINA_MAGIC_NONE); + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE); + free(it); +} + + +/** + * @endcond + */ + +/*============================================================================* +* Global * +*============================================================================*/ + +/** + * @internal + * @brief Initialize the matrixsparse module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function sets up the matrixsparse module of Eina. It is called by + * eina_init(). + * + * This function creates mempool to speed up matrix rows and cells + * management, using EINA_MEMPOOL environment variable if it is set to + * choose the memory pool type to use. + * + * @see eina_init() + */ +Eina_Bool +eina_matrixsparse_init(void) +{ + const char *choice, *tmp; + + _eina_matrixsparse_log_dom = eina_log_domain_register("eina_matrixsparse", + EINA_LOG_COLOR_DEFAULT); + if (_eina_matrixsparse_log_dom < 0) + { + EINA_LOG_ERR("Could not register log domain: eina_matrixsparse"); + return EINA_FALSE; + } + +#ifdef EINA_DEFAULT_MEMPOOL + choice = "pass_through"; +#else + choice = "chained_mempool"; +#endif + tmp = getenv("EINA_MEMPOOL"); + if (tmp && tmp[0]) + choice = tmp; + + _eina_matrixsparse_cell_mp = eina_mempool_add + (choice, + "matrixsparse_cell", + NULL, + sizeof (Eina_Matrixsparse_Cell), + 120); + if (!_eina_matrixsparse_cell_mp) + { + ERR( + "Mempool for matrixsparse_cell cannot be allocated in matrixsparse init."); + 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) + { + ERR( + "Mempool for matrixsparse_row cannot be allocated in matrixsparse init."); + goto on_init_fail; + } + +#define EMS(n) eina_magic_string_static_set(n, n ## _STR) + EMS(EINA_MAGIC_MATRIXSPARSE); + EMS(EINA_MAGIC_MATRIXSPARSE_ROW); + EMS(EINA_MAGIC_MATRIXSPARSE_CELL); + EMS(EINA_MAGIC_MATRIXSPARSE_ITERATOR); + EMS(EINA_MAGIC_MATRIXSPARSE_ROW_ACCESSOR); + EMS(EINA_MAGIC_MATRIXSPARSE_ROW_ITERATOR); + EMS(EINA_MAGIC_MATRIXSPARSE_CELL_ACCESSOR); + EMS(EINA_MAGIC_MATRIXSPARSE_CELL_ITERATOR); +#undef EMS + + return EINA_TRUE; + +on_init_fail: + eina_log_domain_unregister(_eina_matrixsparse_log_dom); + _eina_matrixsparse_log_dom = -1; + return EINA_FALSE; +} + +/** + * @internal + * @brief Shut down the matrixsparse module. + * + * @return #EINA_TRUE on success, #EINA_FALSE on failure. + * + * This function shuts down the matrixsparse module set up by + * eina_matrixsparse_init(). It is called by eina_shutdown(). + * + * @see eina_shutdown() + */ +Eina_Bool +eina_matrixsparse_shutdown(void) +{ + eina_mempool_del(_eina_matrixsparse_row_mp); + eina_mempool_del(_eina_matrixsparse_cell_mp); + + eina_log_domain_unregister(_eina_matrixsparse_log_dom); + _eina_matrixsparse_log_dom = -1; + return EINA_TRUE; +} + +/*============================================================================* +* API * +*============================================================================*/ + +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; + } + + EINA_MAGIC_SET(m, EINA_MAGIC_MATRIXSPARSE); + + 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_error_set(0); + return m; +} + +EAPI void +eina_matrixsparse_free(Eina_Matrixsparse *m) +{ + void (*free_func)(void *, void *); + void *user_data; + + Eina_Matrixsparse_Row *r; + EINA_MAGIC_CHECK_MATRIXSPARSE(m); + + free_func = m->free.func; + 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); +} + +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; +} + +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) + { + Eina_Matrixsparse_Row *r_aux = r; + r->cols = NULL; + r->last_col = NULL; + 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; +} + +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; +} + +EAPI void * +eina_matrixsparse_cell_data_get(const Eina_Matrixsparse_Cell *cell) +{ + EINA_MAGIC_CHECK_MATRIXSPARSE_CELL(cell, NULL); + return cell->data; +} + +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; +} + +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; +} + +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; +} + +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; +} + +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); +} + +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); +} + +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; +} + +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; ) + { + 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; +} + +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; +} + +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; +} + +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.version = EINA_ITERATOR_VERSION; + 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; +} + +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.version = EINA_ITERATOR_VERSION; + 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; +} -- cgit v1.1