src/lib/eina_matrixsparse.c

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