src/lib/eina_array.c

   1 /*
   2  * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2
   3  */
   4 /* EINA - EFL data type library
   5  * Copyright (C) 2008 Cedric Bail
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library;
  19  * if not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22
  23 /**
  24  * @page tutorial_array_page Array Tutorial
  25  *
  26  * The Array data type is allow the storage of data like a C array.
  27  * It is designed such that the access to its element is very fast.
  28  * But the addition or removal can be done only at the end of the
  29  * array. To add or remove an element at any location, the Eina
  30  * @ref Eina_List_Group is the correct container is the correct one.
  31  *
  32  * @section tutorial_error_basic_usage Basic Usage
  33  *
  34  * An array must created with eina_array_new(). That function
  35  * takes an integer as parameter, which is the count of pointers to
  36  * add when increasing the array size. Once the array is not used
  37  * anymore, it must be destroyed with eina_array_free().
  38  *
  39  * To append data at the end of the array, the function
  40  * eina_array_push() must be used. To remove the data at the end of
  41  * the array, eina_array_pop() must be used. Once the array is filled,
  42  * one can check its elements by iterating over it. A while loop and
  43  * eina_array_data_get() can be used, or else one can use the
  44  * predefined macro EINA_ARRAY_ITER_NEXT(). To free all the elements,
  45  * a while loop can be used with eina_array_count_get(). Here is an
  46  * example of use:
  47  *
  48  * @code
  49  * #include <stdlib.h>
  50  * #include <stdio.h>
  51  * #include <string.h>
  52  *
  53  * #include <eina_array.h>
  54  *
  55  * int main(void)
  56  * {
  57  *     const char *strings[] = {
  58  *         "first string",
  59  *         "second string",
  60  *         "third string",
  61  *         "fourth string"
  62  *     };
  63  *     Eina_Array         *array;
  64  *     char               *item;
  65  *     Eina_Array_Iterator iterator;
  66  *     unsigned int        i;
  67  *
  68  *     if (!eina_init())
  69  *     {
  70  *         printf ("Error during the initialization of eina\n");
  71  *         return EXIT_FAILURE;
  72  *     }
  73  *
  74  *     array = eina_array_new(16);
  75  *     if (!array)
  76  *         goto shutdown;
  77  *
  78  *     for (i = 0; i < 4; i++)
  79  *     {
  80  *         eina_array_push(array, strdup(strings[i]));
  81  *     }
  82  *
  83  *     printf("array count: %d\n", eina_array_count_get(array));
  84  *     EINA_ARRAY_ITER_NEXT(array, i, item, iterator)
  85  *     {
  86  *         printf("item #%d: %s\n", i, item);
  87  *     }
  88  *
  89  *     while (eina_array_count_get(array))
  90  *     {
  91  *         void *data;
  92  *
  93  *         data = eina_array_pop(array);
  94  *         free(data);
  95  *     }
  96  *
  97  *     eina_array_free(array);
  98  *     eina_shutdown();
  99  *
 100  *     return EXIT_SUCCESS;
 101  *
 102  *   shutdown:
 103  *     eina_shutdown();
 104  *
 105  *     return EXIT_FAILURE;
 106  * }
 107  * @endcode
 108  *
 109  * To be continued
 110  */
 111
 112 #ifdef HAVE_CONFIG_H
 113 # include "config.h"
 114 #endif
 115
 116 #include <assert.h>
 117 #include <stdlib.h>
 118 #include <string.h>
 119 #include <stdio.h>
 120
 121 #include "eina_config.h"
 122 #include "eina_private.h"
 123 #include "eina_error.h"
 124
 125 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
 126 #include "eina_safety_checks.h"
 127 #include "eina_array.h"
 128
 129 /*============================================================================*
 130  *                                  Local                                     *
 131  *============================================================================*/
 132
 133 /**
 134  * @cond LOCAL
 135  */
 136
 137 #define EINA_MAGIC_CHECK_ARRAY(d)                       \
 138   do {                                                  \
 139      if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY))        \
 140        EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY);            \
 141   } while (0);
 142
 143 #define EINA_MAGIC_CHECK_ARRAY_ITERATOR(d, ...)                 \
 144   do {                                                          \
 145      if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ITERATOR))       \
 146        {                                                        \
 147           EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY_ITERATOR);        \
 148           return __VA_ARGS__;                                   \
 149        }                                                        \
 150   } while (0);
 151
 152 #define EINA_MAGIC_CHECK_ARRAY_ACCESSOR(d, ...)                 \
 153   do {                                                          \
 154      if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ACCESSOR))       \
 155        {                                                        \
 156           EINA_MAGIC_FAIL(d, EINA_MAGIC_ACCESSOR);              \
 157           return __VA_ARGS__;                                   \
 158        }                                                        \
 159   } while (0);
 160
 161
 162 typedef struct _Eina_Iterator_Array Eina_Iterator_Array;
 163 struct _Eina_Iterator_Array
 164 {
 165    Eina_Iterator iterator;
 166
 167    const Eina_Array *array;
 168    unsigned int index;
 169
 170    EINA_MAGIC
 171 };
 172
 173 typedef struct _Eina_Accessor_Array Eina_Accessor_Array;
 174 struct _Eina_Accessor_Array
 175 {
 176    Eina_Accessor accessor;
 177    const Eina_Array *array;
 178    EINA_MAGIC
 179 };
 180
 181 static int _eina_array_log_dom = -1;
 182 #define ERR(...) EINA_LOG_DOM_ERR(_eina_array_log_dom, __VA_ARGS__)
 183 #define DBG(...) EINA_LOG_DOM_DBG(_eina_array_log_dom, __VA_ARGS__)
 184
 185 static void eina_array_iterator_free(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1);
 186 static Eina_Array *eina_array_iterator_get_container(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1);
 187 static Eina_Bool eina_array_iterator_next(Eina_Iterator_Array *it, void **data) EINA_ARG_NONNULL(1);
 188
 189 static Eina_Bool eina_array_accessor_get_at(Eina_Accessor_Array *it, unsigned int index, void **data) EINA_ARG_NONNULL(1);
 190 static Eina_Array *eina_array_accessor_get_container(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1);
 191 static void eina_array_accessor_free(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1);
 192
 193 static Eina_Bool
 194 eina_array_iterator_next(Eina_Iterator_Array *it, void **data)
 195 {
 196    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, EINA_FALSE);
 197
 198    if (!(it->index < eina_array_count_get(it->array)))
 199      return EINA_FALSE;
 200    if (data)
 201      *data = eina_array_data_get(it->array, it->index);
 202    it->index++;
 203    return EINA_TRUE;
 204 }
 205
 206 static Eina_Array *
 207 eina_array_iterator_get_container(Eina_Iterator_Array *it)
 208 {
 209    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, NULL);
 210    return (Eina_Array *) it->array;
 211 }
 212
 213 static void
 214 eina_array_iterator_free(Eina_Iterator_Array *it)
 215 {
 216    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it);
 217    MAGIC_FREE(it);
 218 }
 219
 220 static Eina_Bool
 221 eina_array_accessor_get_at(Eina_Accessor_Array *it, unsigned int index, void **data)
 222 {
 223    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, EINA_FALSE);
 224
 225    if (!(index < eina_array_count_get(it->array)))
 226      return EINA_FALSE;
 227    if (data)
 228      *data = eina_array_data_get(it->array, index);
 229    return EINA_TRUE;
 230 }
 231
 232 static Eina_Array *
 233 eina_array_accessor_get_container(Eina_Accessor_Array *it)
 234 {
 235    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, NULL);
 236    return (Eina_Array *) it->array;
 237 }
 238
 239 static void
 240 eina_array_accessor_free(Eina_Accessor_Array *it)
 241 {
 242    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it);
 243    MAGIC_FREE(it);
 244 }
 245
 246 EAPI Eina_Bool
 247 eina_array_grow(Eina_Array *array)
 248 {
 249    void **tmp;
 250    unsigned int total;
 251
 252    EINA_MAGIC_CHECK_ARRAY(array);
 253    EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
 254
 255    total = array->total + array->step;
 256    eina_error_set(0);
 257    tmp = realloc(array->data, sizeof (void*) * total);
 258    if (UNLIKELY(!tmp)) {
 259       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 260       return 0;
 261    }
 262
 263    array->total = total;
 264    array->data = tmp;
 265
 266    return 1;
 267 }
 268
 269 /**
 270  * @endcond
 271  */
 272
 273
 274 /*============================================================================*
 275  *                                 Global                                     *
 276  *============================================================================*/
 277
 278 /*============================================================================*
 279  *                                   API                                      *
 280  *============================================================================*/
 281
 282 /**
 283  * @addtogroup Eina_Array_Group Array
 284  *
 285  * @brief These functions provide array management.
 286  *
 287  * The Array data type in Eina is designed to have a very fast access to
 288  * its data (compared to the Eina @ref Eina_List_Group). On the other hand,
 289  * data can be added or removed only at the end of the array. To insert
 290  * data at any place, the Eina @ref Eina_List_Group is the correct container
 291  * to use.
 292  *
 293  * To use the array data type, eina_init() must be called before any
 294  * other array functions. When eina is no more array function is used,
 295  * eina_shutdown() must be called to free all the resources.
 296  *
 297  * An array must be created with eina_array_new(). It allocated all
 298  * the necessary data for an array. When not needed anymore, an array
 299  * is freed with eina_array_free(). This function does not free any
 300  * allocated memory used to store the data of each element. For that,
 301  * just iterate over the array to free them. A convenient way to do
 302  * that is by using #EINA_ARRAY_ITER_NEXT. An example of code is given
 303  * in the description of this macro.
 304  *
 305  * @warning All the other functions do not check if the used array is
 306  * valid or not. It's up to the user to be sure of that. It is
 307  * designed like that for performance reasons.
 308  *
 309  * The usual features of an array are classic ones: to append an
 310  * element, use eina_array_push() and to remove the last element, use
 311  * eina_array_pop(). To retrieve the element at a given positin, use
 312  * eina_array_data_get(). The number of elements can be retrieved with
 313  * eina_array_count_get().
 314  *
 315  * For more information, you can look at the @ref tutorial_array_page.
 316  *
 317  * @{
 318  */
 319
 320 /**
 321  * @internal
 322  * @brief Initialize the array module.
 323  *
 324  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 325  *
 326  * This function sets up the error and magic modules or Eina. It is
 327  * called by eina_init().
 328  *
 329  * @see eina_init()
 330  */
 331 Eina_Bool
 332 eina_array_init(void)
 333 {
 334    _eina_array_log_dom = eina_log_domain_register("eina_array", EINA_LOG_COLOR_DEFAULT);
 335    if (_eina_array_log_dom < 0)
 336      {
 337         EINA_LOG_ERR("Could not register log domain: eina_array");
 338         return EINA_FALSE;
 339      }
 340
 341    eina_magic_string_set(EINA_MAGIC_ARRAY, "Eina Array");
 342    eina_magic_string_set(EINA_MAGIC_ARRAY_ITERATOR, "Eina Array Iterator");
 343    eina_magic_string_set(EINA_MAGIC_ARRAY_ACCESSOR, "Eina Array Accessor");
 344    return EINA_TRUE;
 345 }
 346
 347 /**
 348  * @internal
 349  * @brief Shut down the array module.
 350  *
 351  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 352  *
 353  * This function shuts down the array module set up by
 354  * eina_array_init(). It is called by eina_shutdown().
 355  *
 356  * @see eina_shutdown()
 357  */
 358 Eina_Bool
 359 eina_array_shutdown(void)
 360 {
 361    eina_log_domain_unregister(_eina_array_log_dom);
 362    _eina_array_log_dom = -1;
 363    return EINA_TRUE;
 364 }
 365
 366 /**
 367  * @brief Create a new array.
 368  *
 369  * @param step The count of pointers to add when increasing the array size.
 370  * @return @c NULL on failure, non @c NULL otherwise.
 371  *
 372  * This function creates a new array. When adding an element, the array
 373  * allocates @p step elements. When that buffer is full, then adding
 374  * another element will increase the buffer of @p step elements again.
 375  *
 376  * This function return a valid array on success, or @c NULL if memory
 377  * allocation fails. In that case, the error is set to
 378  * #EINA_ERROR_OUT_OF_MEMORY.
 379  */
 380 EAPI Eina_Array *
 381 eina_array_new(unsigned int step)
 382 {
 383    Eina_Array *array;
 384
 385    eina_error_set(0);
 386    array = malloc(sizeof (Eina_Array));
 387    if (!array) {
 388       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 389       return NULL;
 390    }
 391
 392    EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 393
 394    array->data = NULL;
 395    array->total = 0;
 396    array->count = 0;
 397    array->step = step;
 398
 399    DBG("array=%p", array);
 400
 401    return array;
 402 }
 403
 404 /**
 405  * @brief Free an array.
 406  *
 407  * @param array The array to free.
 408  *
 409  * This function frees @p array. It calls first eina_array_flush() then
 410  * free the memory of the pointeur. It does not free the memory
 411  * allocated for the elements of @p array. To free them, use
 412  * #EINA_ARRAY_ITER_NEXT. For performance reasons, there is no check
 413  * of @p array.
 414  */
 415 EAPI void
 416 eina_array_free(Eina_Array *array)
 417 {
 418    eina_array_flush(array);
 419
 420    EINA_MAGIC_CHECK_ARRAY(array);
 421    EINA_SAFETY_ON_NULL_RETURN(array);
 422    DBG("array=%p", array);
 423    MAGIC_FREE(array);
 424 }
 425
 426 /**
 427  * @brief Set the step of an array.
 428  *
 429  * @param array The array.
 430  * @param step The count of pointers to add when increasing the array size.
 431  *
 432  * This function sets the step of @p array to @p step. For performance
 433  * reasons, there is no check of @p array. If it is @c NULL or
 434  * invalid, the program may crash.
 435  */
 436 EAPI void
 437 eina_array_step_set(Eina_Array *array, unsigned int step)
 438 {
 439   EINA_SAFETY_ON_NULL_RETURN(array);
 440   array->data = NULL;
 441   array->total = 0;
 442   array->count = 0;
 443   array->step = step;
 444   EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 445   DBG("array=%p, step=%u", array, step);
 446 }
 447
 448 /**
 449  * @brief Clean an array.
 450  *
 451  * @param array The array to clean.
 452  *
 453  * This function sets the count member of @p array to 0. For
 454  * performance reasons, there is no check of @p array. If it is
 455  * @c NULL or invalid, the program may crash.
 456  */
 457 EAPI void
 458 eina_array_clean(Eina_Array *array)
 459 {
 460    EINA_MAGIC_CHECK_ARRAY(array);
 461    EINA_SAFETY_ON_NULL_RETURN(array);
 462    array->count = 0;
 463    DBG("array=%p", array);
 464 }
 465
 466 /**
 467  * @brief Flush an array.
 468  *
 469  * @param array The array to flush.
 470  *
 471  * This function sets the count and total members of @p array to 0,
 472  * frees and set to NULL its data member. For performance reasons,
 473  * there is no check of @p array. If it is @c NULL or invalid, the
 474  * program may crash.
 475  */
 476 EAPI void
 477 eina_array_flush(Eina_Array *array)
 478 {
 479    EINA_MAGIC_CHECK_ARRAY(array);
 480    EINA_SAFETY_ON_NULL_RETURN(array);
 481    DBG("array=%p", array);
 482    array->count = 0;
 483    array->total = 0;
 484
 485    if (!array->data) return;
 486    free(array->data);
 487    array->data = NULL;
 488 }
 489
 490 /**
 491  * @brief Rebuild an array by specifying the data to keep.
 492  *
 493  * @param array The array.
 494  * @param keep The functions which selects the data to keep.
 495  * @param gdata The data to pass to the function keep.
 496  * @return #EINA_TRUE on success, #EINA_FALSE oterwise.
 497  *
 498  * This function rebuilds @p array be specifying the elements to keep
 499  * with the function @p keep. @p gdata is an additional data to pass
 500  * to @p keep. For performance reasons, there is no check of @p
 501  * array. If it is @c NULL or invalid, the program may crash.
 502  *
 503  * This function always return a valid array. If it wasn't able to
 504  * remove items due to an allocation failure, it will return #EINA_FALSE
 505  * and the error is set to #EINA_ERROR_OUT_OF_MEMORY.
 506  */
 507 EAPI Eina_Bool
 508 eina_array_remove(Eina_Array *array, Eina_Bool (*keep)(void *data, void *gdata), void *gdata)
 509 {
 510    void **tmp;
 511    void *data;
 512    unsigned int total = 0;
 513    unsigned int limit;
 514    unsigned int i;
 515
 516    EINA_MAGIC_CHECK_ARRAY(array);
 517    EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
 518    EINA_SAFETY_ON_NULL_RETURN_VAL(keep, EINA_FALSE);
 519
 520    DBG("array=%p, keep=%p, gdata=%p", array, keep, gdata);
 521
 522    if (array->total == 0) return EINA_TRUE;
 523
 524    for (i = 0; i < array->count; ++i)
 525      {
 526         data = eina_array_data_get(array, i);
 527
 528         if (keep(data, gdata) == EINA_FALSE) break;
 529      }
 530    limit = i;
 531    if (i < array->count) ++i;
 532    for (; i < array->count; ++i)
 533      {
 534         data = eina_array_data_get(array, i);
 535
 536         if (keep(data, gdata) == EINA_TRUE) break;
 537      }
 538    /* Special case all objects that need to stay are at the beginning of the array. */
 539    if (i == array->count)
 540      {
 541         array->count = limit;
 542         if (array->count == 0)
 543           {
 544              free(array->data);
 545              array->total = 0;
 546              array->data = NULL;
 547           }
 548
 549         return EINA_TRUE;
 550      }
 551
 552    eina_error_set(0);
 553    tmp = malloc(sizeof (void*) * array->total);
 554    if (!tmp) {
 555       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 556       return EINA_FALSE;
 557    }
 558
 559    memcpy(tmp, array->data, limit * sizeof(void*));
 560    total = limit;
 561
 562    if (i < array->count)
 563      {
 564         tmp[total] = data;
 565         total++;
 566         ++i;
 567      }
 568
 569    for (; i < array->count; ++i)
 570      {
 571         data = eina_array_data_get(array, i);
 572
 573         if (keep(data, gdata))
 574           {
 575              tmp[total] = data;
 576              total++;
 577           }
 578      }
 579
 580    free(array->data);
 581
 582    /* If we do not keep any object in the array, we should have exited
 583       earlier in test (i == array->count). */
 584    assert(total != 0);
 585
 586    array->data = tmp;
 587    array->count = total;
 588
 589    return EINA_TRUE;
 590 }
 591
 592 /**
 593  * @brief Returned a new iterator asociated to an array.
 594  *
 595  * @param array The array.
 596  * @return A new iterator.
 597  *
 598  * This function returns a newly allocated iterator associated to
 599  * @p array. If @p array is @c NULL or the count member of @p array is
 600  * less or equal than 0, this function returns NULL. If the memory can
 601  * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
 602  * set. Otherwise, a valid iterator is returned.
 603  */
 604 EAPI Eina_Iterator *
 605 eina_array_iterator_new(const Eina_Array *array)
 606 {
 607    Eina_Iterator_Array *it;
 608
 609    EINA_MAGIC_CHECK_ARRAY(array);
 610    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 611
 612    eina_error_set(0);
 613    it = calloc(1, sizeof (Eina_Iterator_Array));
 614    if (!it) {
 615       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 616       return NULL;
 617    }
 618
 619    EINA_MAGIC_SET(it, EINA_MAGIC_ARRAY_ITERATOR);
 620    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
 621
 622    it->array = array;
 623
 624    it->iterator.next = FUNC_ITERATOR_NEXT(eina_array_iterator_next);
 625    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_array_iterator_get_container);
 626    it->iterator.free = FUNC_ITERATOR_FREE(eina_array_iterator_free);
 627
 628    DBG("array=%p, iterator=%p", array, it);
 629
 630    return &it->iterator;
 631 }
 632
 633 /**
 634  * @brief Returned a new accessor asociated to an array.
 635  *
 636  * @param array The array.
 637  * @return A new accessor.
 638  *
 639  * This function returns a newly allocated accessor associated to
 640  * @p array. If @p array is @c NULL or the count member of @p array is
 641  * less or equal than 0, this function returns NULL. If the memory can
 642  * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
 643  * set. Otherwise, a valid accessor is returned.
 644  */
 645 EAPI Eina_Accessor *
 646 eina_array_accessor_new(const Eina_Array *array)
 647 {
 648    Eina_Accessor_Array *it;
 649
 650    EINA_MAGIC_CHECK_ARRAY(array);
 651    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 652
 653    eina_error_set(0);
 654    it = calloc(1, sizeof (Eina_Accessor_Array));
 655    if (!it) {
 656       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 657       return NULL;
 658    }
 659
 660    EINA_MAGIC_SET(it, EINA_MAGIC_ARRAY_ACCESSOR);
 661    EINA_MAGIC_SET(&it->accessor, EINA_MAGIC_ACCESSOR);
 662
 663    it->array = array;
 664
 665    it->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_array_accessor_get_at);
 666    it->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(eina_array_accessor_get_container);
 667    it->accessor.free = FUNC_ACCESSOR_FREE(eina_array_accessor_free);
 668
 669    DBG("array=%p, accessor=%p", array, it);
 670
 671    return &it->accessor;
 672 }
 673
 674 /**
 675  * @}
 676  */