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_ITERATOR, "Eina Iterator");
 342    eina_magic_string_set(EINA_MAGIC_ACCESSOR, "Eina Accessor");
 343    eina_magic_string_set(EINA_MAGIC_ARRAY, "Eina Array");
 344    eina_magic_string_set(EINA_MAGIC_ARRAY_ITERATOR, "Eina Array Iterator");
 345    eina_magic_string_set(EINA_MAGIC_ARRAY_ACCESSOR, "Eina Array Accessor");
 346    return EINA_TRUE;
 347 }
 348
 349 /**
 350  * @internal
 351  * @brief Shut down the array module.
 352  *
 353  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 354  *
 355  * This function shuts down the array module set up by
 356  * eina_array_init(). It is called by eina_shutdown().
 357  *
 358  * @see eina_shutdown()
 359  */
 360 Eina_Bool
 361 eina_array_shutdown(void)
 362 {
 363    eina_log_domain_unregister(_eina_array_log_dom);
 364    _eina_array_log_dom = -1;
 365    return EINA_TRUE;
 366 }
 367
 368 /**
 369  * @brief Create a new array.
 370  *
 371  * @param step The count of pointers to add when increasing the array size.
 372  * @return @c NULL on failure, non @c NULL otherwise.
 373  *
 374  * This function creates a new array. When adding an element, the array
 375  * allocates @p step elements. When that buffer is full, then adding
 376  * another element will increase the buffer of @p step elements again.
 377  *
 378  * This function return a valid array on success, or @c NULL if memory
 379  * allocation fails. In that case, the error is set to
 380  * #EINA_ERROR_OUT_OF_MEMORY.
 381  */
 382 EAPI Eina_Array *
 383 eina_array_new(unsigned int step)
 384 {
 385    Eina_Array *array;
 386
 387    eina_error_set(0);
 388    array = malloc(sizeof (Eina_Array));
 389    if (!array) {
 390       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 391       return NULL;
 392    }
 393
 394    EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 395
 396    array->data = NULL;
 397    array->total = 0;
 398    array->count = 0;
 399    array->step = step;
 400
 401    DBG("array=%p", array);
 402
 403    return array;
 404 }
 405
 406 /**
 407  * @brief Free an array.
 408  *
 409  * @param array The array to free.
 410  *
 411  * This function frees @p array. It calls first eina_array_flush() then
 412  * free the memory of the pointeur. It does not free the memory
 413  * allocated for the elements of @p array. To free them, use
 414  * #EINA_ARRAY_ITER_NEXT. For performance reasons, there is no check
 415  * of @p array.
 416  */
 417 EAPI void
 418 eina_array_free(Eina_Array *array)
 419 {
 420    eina_array_flush(array);
 421
 422    EINA_MAGIC_CHECK_ARRAY(array);
 423    EINA_SAFETY_ON_NULL_RETURN(array);
 424    DBG("array=%p", array);
 425    MAGIC_FREE(array);
 426 }
 427
 428 /**
 429  * @brief Set the step of an array.
 430  *
 431  * @param array The array.
 432  * @param step The count of pointers to add when increasing the array size.
 433  *
 434  * This function sets the step of @p array to @p step. For performance
 435  * reasons, there is no check of @p array. If it is @c NULL or
 436  * invalid, the program may crash.
 437  */
 438 EAPI void
 439 eina_array_step_set(Eina_Array *array, unsigned int step)
 440 {
 441   EINA_SAFETY_ON_NULL_RETURN(array);
 442   array->data = NULL;
 443   array->total = 0;
 444   array->count = 0;
 445   array->step = step;
 446   EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 447   DBG("array=%p, step=%u", array, step);
 448 }
 449
 450 /**
 451  * @brief Clean an array.
 452  *
 453  * @param array The array to clean.
 454  *
 455  * This function sets the count member of @p array to 0. For
 456  * performance reasons, there is no check of @p array. If it is
 457  * @c NULL or invalid, the program may crash.
 458  */
 459 EAPI void
 460 eina_array_clean(Eina_Array *array)
 461 {
 462    EINA_MAGIC_CHECK_ARRAY(array);
 463    EINA_SAFETY_ON_NULL_RETURN(array);
 464    array->count = 0;
 465    DBG("array=%p", array);
 466 }
 467
 468 /**
 469  * @brief Flush an array.
 470  *
 471  * @param array The array to flush.
 472  *
 473  * This function sets the count and total members of @p array to 0,
 474  * frees and set to NULL its data member. For performance reasons,
 475  * there is no check of @p array. If it is @c NULL or invalid, the
 476  * program may crash.
 477  */
 478 EAPI void
 479 eina_array_flush(Eina_Array *array)
 480 {
 481    EINA_MAGIC_CHECK_ARRAY(array);
 482    EINA_SAFETY_ON_NULL_RETURN(array);
 483    DBG("array=%p", array);
 484    array->count = 0;
 485    array->total = 0;
 486
 487    if (!array->data) return;
 488    free(array->data);
 489    array->data = NULL;
 490 }
 491
 492 /**
 493  * @brief Rebuild an array by specifying the data to keep.
 494  *
 495  * @param array The array.
 496  * @param keep The functions which selects the data to keep.
 497  * @param gdata The data to pass to the function keep.
 498  * @return #EINA_TRUE on success, #EINA_FALSE oterwise.
 499  *
 500  * This function rebuilds @p array be specifying the elements to keep
 501  * with the function @p keep. @p gdata is an additional data to pass
 502  * to @p keep. For performance reasons, there is no check of @p
 503  * array. If it is @c NULL or invalid, the program may crash.
 504  *
 505  * This function always return a valid array. If it wasn't able to
 506  * remove items due to an allocation failure, it will return #EINA_FALSE
 507  * and the error is set to #EINA_ERROR_OUT_OF_MEMORY.
 508  */
 509 EAPI Eina_Bool
 510 eina_array_remove(Eina_Array *array, Eina_Bool (*keep)(void *data, void *gdata), void *gdata)
 511 {
 512    void **tmp;
 513    void *data;
 514    unsigned int total = 0;
 515    unsigned int limit;
 516    unsigned int i;
 517
 518    EINA_MAGIC_CHECK_ARRAY(array);
 519    EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
 520    EINA_SAFETY_ON_NULL_RETURN_VAL(keep, EINA_FALSE);
 521
 522    DBG("array=%p, keep=%p, gdata=%p", array, keep, gdata);
 523
 524    if (array->total == 0) return EINA_TRUE;
 525
 526    for (i = 0; i < array->count; ++i)
 527      {
 528         data = eina_array_data_get(array, i);
 529
 530         if (keep(data, gdata) == EINA_FALSE) break;
 531      }
 532    limit = i;
 533    if (i < array->count) ++i;
 534    for (; i < array->count; ++i)
 535      {
 536         data = eina_array_data_get(array, i);
 537
 538         if (keep(data, gdata) == EINA_TRUE) break;
 539      }
 540    /* Special case all objects that need to stay are at the beginning of the array. */
 541    if (i == array->count)
 542      {
 543         array->count = limit;
 544         if (array->count == 0)
 545           {
 546              free(array->data);
 547              array->total = 0;
 548              array->data = NULL;
 549           }
 550
 551         return EINA_TRUE;
 552      }
 553
 554    eina_error_set(0);
 555    tmp = malloc(sizeof (void*) * array->total);
 556    if (!tmp) {
 557       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 558       return EINA_FALSE;
 559    }
 560
 561    memcpy(tmp, array->data, limit * sizeof(void*));
 562    total = limit;
 563
 564    if (i < array->count)
 565      {
 566         tmp[total] = data;
 567         total++;
 568         ++i;
 569      }
 570
 571    for (; i < array->count; ++i)
 572      {
 573         data = eina_array_data_get(array, i);
 574
 575         if (keep(data, gdata))
 576           {
 577              tmp[total] = data;
 578              total++;
 579           }
 580      }
 581
 582    free(array->data);
 583
 584    /* If we do not keep any object in the array, we should have exited
 585       earlier in test (i == array->count). */
 586    assert(total != 0);
 587
 588    array->data = tmp;
 589    array->count = total;
 590
 591    return EINA_TRUE;
 592 }
 593
 594 /**
 595  * @brief Returned a new iterator asociated to an array.
 596  *
 597  * @param array The array.
 598  * @return A new iterator.
 599  *
 600  * This function returns a newly allocated iterator associated to
 601  * @p array. If @p array is @c NULL or the count member of @p array is
 602  * less or equal than 0, this function returns NULL. If the memory can
 603  * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
 604  * set. Otherwise, a valid iterator is returned.
 605  */
 606 EAPI Eina_Iterator *
 607 eina_array_iterator_new(const Eina_Array *array)
 608 {
 609    Eina_Iterator_Array *it;
 610
 611    EINA_MAGIC_CHECK_ARRAY(array);
 612    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 613
 614    eina_error_set(0);
 615    it = calloc(1, sizeof (Eina_Iterator_Array));
 616    if (!it) {
 617       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 618       return NULL;
 619    }
 620
 621    EINA_MAGIC_SET(it, EINA_MAGIC_ARRAY_ITERATOR);
 622    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
 623
 624    it->array = array;
 625
 626    it->iterator.next = FUNC_ITERATOR_NEXT(eina_array_iterator_next);
 627    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(eina_array_iterator_get_container);
 628    it->iterator.free = FUNC_ITERATOR_FREE(eina_array_iterator_free);
 629
 630    DBG("array=%p, iterator=%p", array, it);
 631
 632    return &it->iterator;
 633 }
 634
 635 /**
 636  * @brief Returned a new accessor asociated to an array.
 637  *
 638  * @param array The array.
 639  * @return A new accessor.
 640  *
 641  * This function returns a newly allocated accessor associated to
 642  * @p array. If @p array is @c NULL or the count member of @p array is
 643  * less or equal than 0, this function returns NULL. If the memory can
 644  * not be allocated, NULL is returned and #EINA_ERROR_OUT_OF_MEMORY is
 645  * set. Otherwise, a valid accessor is returned.
 646  */
 647 EAPI Eina_Accessor *
 648 eina_array_accessor_new(const Eina_Array *array)
 649 {
 650    Eina_Accessor_Array *it;
 651
 652    EINA_MAGIC_CHECK_ARRAY(array);
 653    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 654
 655    eina_error_set(0);
 656    it = calloc(1, sizeof (Eina_Accessor_Array));
 657    if (!it) {
 658       eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 659       return NULL;
 660    }
 661
 662    EINA_MAGIC_SET(it, EINA_MAGIC_ARRAY_ACCESSOR);
 663    EINA_MAGIC_SET(&it->accessor, EINA_MAGIC_ACCESSOR);
 664
 665    it->array = array;
 666
 667    it->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_array_accessor_get_at);
 668    it->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(eina_array_accessor_get_container);
 669    it->accessor.free = FUNC_ACCESSOR_FREE(eina_array_accessor_free);
 670
 671    DBG("array=%p, accessor=%p", array, it);
 672
 673    return &it->accessor;
 674 }
 675
 676 /**
 677  * @}
 678  */