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