src/lib/eina_array.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2008 Cedric Bail
   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 #ifdef HAVE_CONFIG_H
  21 # include "config.h"
  22 #endif
  23
  24 #include <assert.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <stdio.h>
  28
  29 #include "eina_config.h"
  30 #include "eina_private.h"
  31 #include "eina_error.h"
  32 #include "eina_log.h"
  33
  34 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
  35 #include "eina_safety_checks.h"
  36 #include "eina_array.h"
  37
  38 /*============================================================================*
  39  *                                  Local                                     *
  40  *============================================================================*/
  41
  42 /**
  43  * @cond LOCAL
  44  */
  45
  46 static const char EINA_MAGIC_ARRAY_STR[] = "Eina Array";
  47 static const char EINA_MAGIC_ARRAY_ITERATOR_STR[] = "Eina Array Iterator";
  48 static const char EINA_MAGIC_ARRAY_ACCESSOR_STR[] = "Eina Array Accessor";
  49
  50 #define EINA_MAGIC_CHECK_ARRAY(d)                       \
  51    do {                                                  \
  52         if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY)) {        \
  53              EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY); }            \
  54      } while (0)
  55
  56 #define EINA_MAGIC_CHECK_ARRAY_ITERATOR(d, ...)                 \
  57    do {                                                          \
  58         if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ITERATOR))       \
  59           {                                                        \
  60              EINA_MAGIC_FAIL(d, EINA_MAGIC_ARRAY_ITERATOR);        \
  61              return __VA_ARGS__;                                   \
  62           }                                                        \
  63      } while (0)
  64
  65 #define EINA_MAGIC_CHECK_ARRAY_ACCESSOR(d, ...)                 \
  66    do {                                                          \
  67         if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_ARRAY_ACCESSOR))       \
  68           {                                                        \
  69              EINA_MAGIC_FAIL(d, EINA_MAGIC_ACCESSOR);              \
  70              return __VA_ARGS__;                                   \
  71           }                                                        \
  72      } while (0)
  73
  74
  75 typedef struct _Eina_Iterator_Array Eina_Iterator_Array;
  76 struct _Eina_Iterator_Array
  77 {
  78    Eina_Iterator iterator;
  79
  80    const Eina_Array *array;
  81    unsigned int index;
  82
  83    EINA_MAGIC
  84 };
  85
  86 typedef struct _Eina_Accessor_Array Eina_Accessor_Array;
  87 struct _Eina_Accessor_Array
  88 {
  89    Eina_Accessor accessor;
  90    const Eina_Array *array;
  91    EINA_MAGIC
  92 };
  93
  94 static int _eina_array_log_dom = -1;
  95
  96 #ifdef ERR
  97 #undef ERR
  98 #endif
  99 #define ERR(...) EINA_LOG_DOM_ERR(_eina_array_log_dom, __VA_ARGS__)
 100
 101 #ifdef DBG
 102 #undef DBG
 103 #endif
 104 #define DBG(...) EINA_LOG_DOM_DBG(_eina_array_log_dom, __VA_ARGS__)
 105
 106 static void        eina_array_iterator_free(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1);
 107 static Eina_Array *eina_array_iterator_get_container(Eina_Iterator_Array *it) EINA_ARG_NONNULL(1);
 108 static Eina_Bool   eina_array_iterator_next(Eina_Iterator_Array *it,
 109                                             void **data) EINA_ARG_NONNULL(1);
 110
 111 static Eina_Bool   eina_array_accessor_get_at(Eina_Accessor_Array *it,
 112                                               unsigned int idx,
 113                                               void **data) EINA_ARG_NONNULL(1);
 114 static Eina_Array *eina_array_accessor_get_container(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1);
 115 static void        eina_array_accessor_free(Eina_Accessor_Array *it) EINA_ARG_NONNULL(1);
 116
 117 static Eina_Bool
 118 eina_array_iterator_next(Eina_Iterator_Array *it, void **data)
 119 {
 120    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, EINA_FALSE);
 121
 122    if (!(it->index < eina_array_count(it->array)))
 123       return EINA_FALSE;
 124
 125    if (data)
 126       *data = eina_array_data_get(it->array, it->index);
 127
 128    it->index++;
 129    return EINA_TRUE;
 130 }
 131
 132 static Eina_Array *
 133 eina_array_iterator_get_container(Eina_Iterator_Array *it)
 134 {
 135    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it, NULL);
 136    return (Eina_Array *)it->array;
 137 }
 138
 139 static void
 140 eina_array_iterator_free(Eina_Iterator_Array *it)
 141 {
 142    EINA_MAGIC_CHECK_ARRAY_ITERATOR(it);
 143    MAGIC_FREE(it);
 144 }
 145
 146 static Eina_Bool
 147 eina_array_accessor_get_at(Eina_Accessor_Array *it,
 148                            unsigned int idx,
 149                            void **data)
 150 {
 151    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, EINA_FALSE);
 152
 153    if (!(idx < eina_array_count(it->array)))
 154       return EINA_FALSE;
 155
 156    if (data)
 157       *data = eina_array_data_get(it->array, idx);
 158
 159    return EINA_TRUE;
 160 }
 161
 162 static Eina_Array *
 163 eina_array_accessor_get_container(Eina_Accessor_Array *it)
 164 {
 165    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it, NULL);
 166    return (Eina_Array *)it->array;
 167 }
 168
 169 static void
 170 eina_array_accessor_free(Eina_Accessor_Array *it)
 171 {
 172    EINA_MAGIC_CHECK_ARRAY_ACCESSOR(it);
 173    MAGIC_FREE(it);
 174 }
 175
 176 /* used from eina_inline_array.x, thus a needed symbol */
 177 EAPI Eina_Bool
 178 eina_array_grow(Eina_Array *array)
 179 {
 180    void **tmp;
 181    unsigned int total;
 182
 183    EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
 184
 185    EINA_MAGIC_CHECK_ARRAY(array);
 186
 187    total = array->total + array->step;
 188    eina_error_set(0);
 189    tmp = realloc(array->data, sizeof (void *) * total);
 190    if (EINA_UNLIKELY(!tmp))
 191      {
 192         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 193         return 0;
 194      }
 195
 196    array->total = total;
 197    array->data = tmp;
 198
 199    return 1;
 200 }
 201
 202 /**
 203  * @endcond
 204  */
 205
 206
 207 /*============================================================================*
 208  *                                 Global                                     *
 209  *============================================================================*/
 210
 211 /**
 212  * @internal
 213  * @brief Initialize the array module.
 214  *
 215  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 216  *
 217  * This function sets up the error and magic modules or Eina. It is
 218  * called by eina_init().
 219  *
 220  * @see eina_init()
 221  */
 222 Eina_Bool
 223 eina_array_init(void)
 224 {
 225    _eina_array_log_dom = eina_log_domain_register("eina_array",
 226                                                   EINA_LOG_COLOR_DEFAULT);
 227    if (_eina_array_log_dom < 0)
 228      {
 229         EINA_LOG_ERR("Could not register log domain: eina_array");
 230         return EINA_FALSE;
 231      }
 232
 233 #define EMS(n) eina_magic_string_static_set(n, n ## _STR)
 234    EMS(EINA_MAGIC_ARRAY);
 235    EMS(EINA_MAGIC_ARRAY_ITERATOR);
 236    EMS(EINA_MAGIC_ARRAY_ACCESSOR);
 237 #undef EMS
 238    return EINA_TRUE;
 239 }
 240
 241 /**
 242  * @internal
 243  * @brief Shut down the array module.
 244  *
 245  * @return #EINA_TRUE on success, #EINA_FALSE on failure.
 246  *
 247  * This function shuts down the array module set up by
 248  * eina_array_init(). It is called by eina_shutdown().
 249  *
 250  * @see eina_shutdown()
 251  */
 252 Eina_Bool
 253 eina_array_shutdown(void)
 254 {
 255    eina_log_domain_unregister(_eina_array_log_dom);
 256    _eina_array_log_dom = -1;
 257    return EINA_TRUE;
 258 }
 259
 260 /*============================================================================*
 261  *                                   API                                      *
 262  *============================================================================*/
 263
 264 EAPI Eina_Array *
 265 eina_array_new(unsigned int step)
 266 {
 267    Eina_Array *array;
 268
 269    eina_error_set(0);
 270    array = malloc(sizeof (Eina_Array));
 271    if (!array)
 272      {
 273         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 274         return NULL;
 275      }
 276
 277    EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 278
 279    array->version = EINA_ARRAY_VERSION;
 280    array->data = NULL;
 281    array->total = 0;
 282    array->count = 0;
 283    array->step = step;
 284
 285    return array;
 286 }
 287
 288 EAPI void
 289 eina_array_free(Eina_Array *array)
 290 {
 291    eina_array_flush(array);
 292
 293    EINA_SAFETY_ON_NULL_RETURN(array);
 294    EINA_MAGIC_CHECK_ARRAY(array);
 295    MAGIC_FREE(array);
 296 }
 297
 298 EAPI void
 299 eina_array_step_set(Eina_Array *array,
 300                     unsigned int sizeof_eina_array,
 301                     unsigned int step)
 302 {
 303    EINA_SAFETY_ON_NULL_RETURN(array);
 304
 305    if (sizeof (Eina_Array) != sizeof_eina_array)
 306      {
 307         ERR("Unknow Eina_Array size ! Got %i, expected %i !\n",
 308             sizeof_eina_array,
 309             (int) sizeof (Eina_Array));
 310         /* Force memory to zero to provide a small layer of security */
 311         memset(array, 0, sizeof_eina_array);
 312         return ;
 313      }
 314
 315    array->version = EINA_ARRAY_VERSION;
 316    array->data = NULL;
 317    array->total = 0;
 318    array->count = 0;
 319    array->step = step;
 320    EINA_MAGIC_SET(array, EINA_MAGIC_ARRAY);
 321 }
 322
 323 EAPI void
 324 eina_array_flush(Eina_Array *array)
 325 {
 326    EINA_SAFETY_ON_NULL_RETURN(array);
 327    EINA_MAGIC_CHECK_ARRAY(array);
 328
 329    array->count = 0;
 330    array->total = 0;
 331
 332    if (!array->data)
 333       return;
 334
 335    free(array->data);
 336    array->data = NULL;
 337 }
 338
 339 EAPI Eina_Bool
 340 eina_array_remove(Eina_Array *array, Eina_Bool (*keep)(void *data,
 341                                                        void *gdata),
 342                   void *gdata)
 343 {
 344    void **tmp;
 345    /* WARNING:
 346       The algorithm does exit before using unitialized data. So compiler is
 347       giving you a false positiv here too.
 348     */
 349    void *data = NULL;
 350    unsigned int total = 0;
 351    unsigned int limit;
 352    unsigned int i;
 353
 354    EINA_SAFETY_ON_NULL_RETURN_VAL(array, EINA_FALSE);
 355    EINA_SAFETY_ON_NULL_RETURN_VAL(keep,  EINA_FALSE);
 356    EINA_MAGIC_CHECK_ARRAY(array);
 357
 358    if (array->total == 0)
 359       return EINA_TRUE;
 360
 361    for (i = 0; i < array->count; ++i)
 362      {
 363         data = eina_array_data_get(array, i);
 364
 365         if (keep(data, gdata) == EINA_FALSE)
 366            break;
 367      }
 368    limit = i;
 369    if (i < array->count)
 370       ++i;
 371
 372    for (; i < array->count; ++i)
 373      {
 374         data = eina_array_data_get(array, i);
 375
 376         if (keep(data, gdata) == EINA_TRUE)
 377            break;
 378      }
 379    /* Special case all objects that need to stay are at the beginning of the array. */
 380    if (i == array->count)
 381      {
 382         array->count = limit;
 383         if (array->count == 0)
 384           {
 385              free(array->data);
 386              array->total = 0;
 387              array->data = NULL;
 388           }
 389
 390         return EINA_TRUE;
 391      }
 392
 393    eina_error_set(0);
 394    tmp = malloc(sizeof (void *) * array->total);
 395    if (!tmp)
 396      {
 397         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 398         return EINA_FALSE;
 399      }
 400
 401    memcpy(tmp, array->data, limit * sizeof(void *));
 402    total = limit;
 403
 404    if (i < array->count)
 405      {
 406         tmp[total] = data;
 407         total++;
 408         ++i;
 409      }
 410
 411    for (; i < array->count; ++i)
 412      {
 413         data = eina_array_data_get(array, i);
 414
 415         if (keep(data, gdata))
 416           {
 417              tmp[total] = data;
 418              total++;
 419           }
 420      }
 421
 422    free(array->data);
 423
 424    /* If we do not keep any object in the array, we should have exited
 425       earlier in test (i == array->count). */
 426    assert(total != 0);
 427
 428    array->data = tmp;
 429    array->count = total;
 430    return EINA_TRUE;
 431 }
 432
 433 EAPI Eina_Iterator *
 434 eina_array_iterator_new(const Eina_Array *array)
 435 {
 436    Eina_Iterator_Array *it;
 437
 438    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 439    EINA_MAGIC_CHECK_ARRAY(array);
 440
 441    eina_error_set(0);
 442    it = calloc(1, sizeof (Eina_Iterator_Array));
 443    if (!it)
 444      {
 445         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 446         return NULL;
 447      }
 448
 449    EINA_MAGIC_SET(it,            EINA_MAGIC_ARRAY_ITERATOR);
 450    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
 451
 452    it->array = array;
 453
 454    it->iterator.version = EINA_ITERATOR_VERSION;
 455    it->iterator.next = FUNC_ITERATOR_NEXT(eina_array_iterator_next);
 456    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
 457          eina_array_iterator_get_container);
 458    it->iterator.free = FUNC_ITERATOR_FREE(eina_array_iterator_free);
 459
 460    return &it->iterator;
 461 }
 462
 463 EAPI Eina_Accessor *
 464 eina_array_accessor_new(const Eina_Array *array)
 465 {
 466    Eina_Accessor_Array *ac;
 467
 468    EINA_SAFETY_ON_NULL_RETURN_VAL(array, NULL);
 469    EINA_MAGIC_CHECK_ARRAY(array);
 470
 471    eina_error_set(0);
 472    ac = calloc(1, sizeof (Eina_Accessor_Array));
 473    if (!ac)
 474      {
 475         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 476         return NULL;
 477      }
 478
 479    EINA_MAGIC_SET(ac,            EINA_MAGIC_ARRAY_ACCESSOR);
 480    EINA_MAGIC_SET(&ac->accessor, EINA_MAGIC_ACCESSOR);
 481
 482    ac->array = array;
 483
 484    ac->accessor.version = EINA_ACCESSOR_VERSION;
 485    ac->accessor.get_at = FUNC_ACCESSOR_GET_AT(eina_array_accessor_get_at);
 486    ac->accessor.get_container = FUNC_ACCESSOR_GET_CONTAINER(
 487          eina_array_accessor_get_container);
 488    ac->accessor.free = FUNC_ACCESSOR_FREE(eina_array_accessor_free);
 489
 490    return &ac->accessor;
 491 }