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 #ifndef EINA_ARRAY_H_ 20 #define EINA_ARRAY_H_ 21 22 #include <stdlib.h> 23 24 #include "eina_config.h" 25 26 #include "eina_types.h" 27 #include "eina_error.h" 28 #include "eina_iterator.h" 29 #include "eina_accessor.h" 30 #include "eina_magic.h" 31 32 33 /** 34 * @page eina_array_01_example_page Basic array usage 35 * @dontinclude eina_array_01.c 36 * 37 * For this example we add stdlib.h, stdio.h and string.h for some 38 * convenience functions. The first thing to do to be able to use an 39 * @ref Eina_Array is to include Eina.h: 40 * @skip #include 41 * @until Eina.h 42 * 43 * Here we have a callback that prints the element given to it: 44 * @until } 45 * 46 * Now we create our entry point and declare some variables, nothing special: 47 * @until unsigned 48 * 49 * Before we can start using any array function we need to initialize eina: 50 * @until eina_init 51 * 52 * So now to actually create our array. The interesting thing here is the 53 * argument given to the eina_array_new() function. This argument sets how fast 54 * the array grows. 55 * @until array_new 56 * 57 * If you know before hand how big the array will need to be you should set the 58 * step to that. In our case we can set it to the number of strings we have and 59 * since we didn't do that in the eina_array_new() we can do it now: 60 * @until array_step_set 61 * 62 * Now let us populate our array with some strings: 63 * @until push 64 * @note Notice we use strdup, so we will have to free that memory later on. 65 * 66 * Now lets check the size of the array: 67 * @until printf 68 * 69 * And now we call a function on every member of our array to print it: 70 * @until foreach 71 * 72 * One of the strengths of @ref Eina_Array over @ref Eina_List is that it has 73 * very fast random access to elements, so this is very efficient: 74 * @until printf 75 * 76 * And now we free up the memory allocated with the strdup()s: 77 * @until free 78 * 79 * And the array memory itself: 80 * @until array_free 81 * 82 * And finally shutdown eina and exit: 83 * @until } 84 * 85 * The full source code can be found in the examples folder 86 * in the @ref eina_array_01_c "eina_array_01.c" file. 87 */ 88 89 /** 90 * @page eina_array_01_c Basic array usage example 91 * 92 * @include eina_array_01.c 93 * @example eina_array_01.c 94 */ 95 96 /** 97 * @page eina_array_02_example_page Removing array elements 98 * @dontinclude eina_array_02.c 99 * 100 * Just the usual includes: 101 * @skip #include 102 * @until Eina.h 103 * 104 * This is the callback we are going to use to decide which strings stay on the 105 * array and which will be removed. We use something simple, but this can be as 106 * complex as you like: 107 * @until } 108 * 109 * This is the same code we used before to populate the list with the slight 110 * difference of not using strdup: 111 * @until array_push 112 * 113 * So we have added all our elements to the array, but it turns out that is not 114 * the elements we wanted, so let's empty the array and add the correct strings: 115 * @until array_push 116 * 117 * It seems we made a little mistake in one of our strings so we need to replace 118 * it, here is how: 119 * @until data_set 120 * 121 * Now that there is a populated array we can remove elements from it easily: 122 * @until array_remove 123 * 124 * And check that the elements were actually removed: 125 * @until printf 126 * 127 * Since this time we didn't use strdup we don't need to free each string: 128 * @until } 129 * 130 * The full source code can be found in the examples folder 131 * in the @ref eina_array_02_c "eina_array_02.c" file. 132 */ 133 134 /** 135 * @page eina_array_02_c Basic array usage example 136 * 137 * @include eina_array_02.c 138 * @example eina_array_02.c 139 */ 140 141 /** 142 * @addtogroup Eina_Array_Group Array 143 * 144 * @brief These functions provide array management. 145 * 146 * The Array data type in Eina is designed to have very fast access to 147 * its data (compared to the Eina @ref Eina_List_Group). On the other 148 * hand, data can be added or removed only at the end of the array. To 149 * insert data at arbitrary positions, the Eina @ref Eina_List_Group is 150 * the correct container to use. 151 * 152 * To use the array data type, eina_init() must be called before any 153 * other array functions. When no more eina array functions are used, 154 * eina_shutdown() must be called to free all the resources. 155 * 156 * An array must be created with eina_array_new(). It allocates all 157 * the necessary data for an array. When not needed anymore, an array 158 * is freed with eina_array_free(). This frees the memory used by the Eina_Array 159 * itself, but does not free any memory used to store the data of each element. 160 * To free that memory you must iterate over the array and free each data element 161 * individually. A convenient way to do that is by using #EINA_ARRAY_ITER_NEXT. 162 * An example of that pattern is given in the description of @ref EINA_ARRAY_ITER_NEXT. 163 * 164 * @warning Functions do not check if the used array is valid or not. It's up to 165 * the user to be sure of that. It is designed like that for performance 166 * reasons. 167 * 168 * The usual features of an array are classic ones: to append an 169 * element, use eina_array_push() and to remove the last element, use 170 * eina_array_pop(). To retrieve the element at a given position, use 171 * eina_array_data_get(). The number of elements can be retrieved with 172 * eina_array_count(). 173 * 174 * An Eina_Array differs most notably from a conventional C array in that it can 175 * grow and shrink dynamically as elements are added and removed. 176 * Since allocating memory is expensive, when the array needs to grow it adds 177 * enough memory to hold @p step additional elements, not just the element 178 * currently being added. Similarly when elements are removed, it won't deallocate 179 * until @p step elements are removed. 180 * 181 * The following image illustrates how an Eina_Array grows: 182 * 183 * @image html eina_array-growth.png 184 * @image latex eina_array-growth.eps "" width=\textwidth 185 * 186 * Eina_Array only stores pointers but it can store data of any type in the form 187 * of void pointers. 188 * 189 * See here some examples: 190 * @li @ref eina_array_01_example_page 191 * @li @ref eina_array_02_example_page 192 */ 193 194 /** 195 * @addtogroup Eina_Data_Types_Group Data Types 196 * 197 * @{ 198 */ 199 200 /** 201 * @addtogroup Eina_Containers_Group Containers 202 * 203 * @{ 204 */ 205 206 /** 207 * @defgroup Eina_Array_Group Array 208 * 209 * @{ 210 */ 211 212 /** 213 * @typedef Eina_Array 214 * Type for a generic one-dimensional linear data structure. 215 */ 216 typedef struct _Eina_Array Eina_Array; 217 218 /** 219 * @typedef Eina_Array_Iterator 220 * Type for an iterator on arrays, used with #EINA_ARRAY_ITER_NEXT. 221 */ 222 typedef void **Eina_Array_Iterator; 223 224 /** 225 * @struct _Eina_Array 226 * Type for an array of data. 227 */ 228 struct _Eina_Array 229 { 230 #define EINA_ARRAY_VERSION 1 231 int version; /**< Should match EINA_ARRAY_VERSION used when compiled your apps, provided for ABI compatibility */ 232 233 void **data; /**< Pointer to a C array of pointers to payloads */ 234 unsigned int total; /**< Number of allocated slots in @p data */ 235 unsigned int count; /**< Number of used slots in @p data that point to valid payloads */ 236 unsigned int step; /**< Number of slots to grow or shrink @p data */ 237 EINA_MAGIC 238 }; 239 240 241 /** 242 * @brief Creates a new array. 243 * 244 * @param[in] step The count of pointers to add when increasing the array size. 245 * @return @c NULL on failure, non @c NULL otherwise. 246 * 247 * This function creates a new array. When adding an element, the array 248 * allocates @p step elements. When that buffer is full, adding 249 * another element will increase the buffer by @p step elements again. 250 * 251 * This function return a valid array on success, or @c NULL if memory 252 * allocation fails. 253 */ 254 EAPI Eina_Array *eina_array_new(unsigned int step) EINA_WARN_UNUSED_RESULT EINA_MALLOC EINA_WARN_UNUSED_RESULT; 255 256 /** 257 * @brief Frees an array. 258 * 259 * @param[in] array The array to free. 260 * 261 * This function finalizes @p array by flushing (see 262 * eina_array_flush()), and then freeing the memory of the pointer. It 263 * does not free the memory allocated for the elements of @p array. To 264 * free them, walk the array with #EINA_ARRAY_ITER_NEXT. 265 */ 266 EAPI void eina_array_free(Eina_Array *array); 267 268 /** 269 * @brief Sets the step of an array. 270 * 271 * @param[in,out] array The array. 272 * @param[in] sizeof_eina_array Should be the value returned by sizeof(Eina_Array). 273 * @param[in] step The count of pointers to add when increasing the array size. 274 * 275 * This function sets the step of @p array to @p step. For performance 276 * reasons, there is no check of @p array. If it is @c NULL or 277 * invalid, the program may crash. 278 * 279 * @warning This function can @b only be called on uninitialized arrays. 280 */ 281 EAPI void eina_array_step_set(Eina_Array *array, 282 unsigned int sizeof_eina_array, 283 unsigned int step) EINA_ARG_NONNULL(1); 284 /** 285 * @brief Clears an array of its elements, without deallocating memory. 286 * 287 * @param[in,out] array The array to clean. 288 * 289 * This function sets the @p array's member count to 0 without freeing 290 * memory. This facilitates emptying an array and quickly refilling it 291 * with new elements. For performance reasons, there is no check of @p 292 * array. If it is @c NULL or invalid, the program may crash. 293 */ 294 static inline void eina_array_clean(Eina_Array *array) EINA_ARG_NONNULL(1); 295 296 /** 297 * @brief Clears an array's elements and deallocates the memory. 298 * 299 * @param[in,out] array The array to flush. 300 * 301 * This function sets the count and total members of @p array to 0, and 302 * frees its data member and sets it to NULL. For performance reasons, 303 * there is no check of @p array. If it is @c NULL or invalid, the 304 * program may crash. 305 */ 306 EAPI void eina_array_flush(Eina_Array *array) EINA_ARG_NONNULL(1); 307 308 /** 309 * @brief Rebuilds an array by specifying the data to keep. 310 * 311 * @param[in,out] array The array. 312 * @param[in] keep The functions which selects the data to keep. 313 * @param[in] gdata The data to pass to the function keep. 314 * @return #EINA_TRUE on success, #EINA_FALSE otherwise. 315 * 316 * This function rebuilds @p array by specifying the elements to keep with the 317 * function @p keep. No empty/invalid fields are left in the array. @p gdata is 318 * an additional data to pass to @p keep. For performance reasons, there is no 319 * check of @p array. If it is @c NULL or invalid, the program may crash. 320 * 321 * If it wasn't able to remove items due to an allocation failure, it will 322 * return #EINA_FALSE. 323 */ 324 EAPI Eina_Bool eina_array_remove(Eina_Array * array, 325 Eina_Bool (*keep)(void *data, void *gdata), 326 void *gdata) EINA_ARG_NONNULL(1, 2); 327 328 /** 329 * @brief Appends a data item to an array. 330 * 331 * @param[in,out] array The array. 332 * @param[in] data The data to add. 333 * @return #EINA_TRUE on success, #EINA_FALSE if allocation is necessary 334 * and fails or if @p data is @c NULL. 335 * 336 * This function appends @p data to @p array. For performance 337 * reasons, there is no check of @p array. If it is @c NULL or 338 * invalid, the program may crash. 339 */ 340 static inline Eina_Bool eina_array_push(Eina_Array *array, 341 const void *data) EINA_ARG_NONNULL(1, 2); 342 343 /** 344 * @brief Removes the last data item in an array. 345 * 346 * @param[in,out] array The array. 347 * @return The retrieved data, or @c NULL if there are no remaining items. 348 * 349 * This function removes the last data item from @p array, decreases the 350 * length of @p array and returns the data item. For performance reasons, 351 * there is no check of @p array, so if it is @c NULL or invalid, the 352 * program may crash. 353 */ 354 static inline void *eina_array_pop(Eina_Array *array) EINA_ARG_NONNULL(1); 355 356 /** 357 * @brief Returns the data at a given position in an array. 358 * 359 * @param[in] array The array. 360 * @param[in] idx The position of the data to retrieve. 361 * @return The retrieved data. 362 * 363 * This function returns the data at the position @p idx in @p 364 * array. For performance reasons, there is no check of @p array or @p 365 * idx. If @p array is @c NULL or invalid, or if @p idx is larger than 366 * the array's size, the program may crash. 367 */ 368 static inline void *eina_array_data_get(const Eina_Array *array, 369 unsigned int idx) EINA_ARG_NONNULL(1); 370 /** 371 * @brief Sets the data at a given position in an array. 372 * 373 * @param[in] array The array. 374 * @param[in] idx The position of the data to set. 375 * @param[in] data The data to set. 376 * 377 * This function sets the data at the position @p idx in @p array to @p 378 * data, this effectively replaces the previously held data, you must 379 * therefore get a pointer to it first if you need to free it. For 380 * performance reasons, there is no check of @p array or @p idx. If @p 381 * array is @c NULL or invalid, or if @p idx is larger than the array's 382 * size, the program may crash. 383 */ 384 static inline void eina_array_data_set(const Eina_Array *array, 385 unsigned int idx, 386 const void *data) EINA_ARG_NONNULL(1); 387 388 /** 389 * @deprecated use eina_array_count() 390 * @brief Returns the number of elements in an array. 391 * 392 * @param[in] array The array. 393 * @return The number of elements. 394 * 395 * This function returns the number of elements in @p array (array->count). For 396 * performance reasons, there is no check of @p array, so if it is 397 * @c NULL or invalid, the program may crash. 398 * 399 */ 400 static inline unsigned int eina_array_count_get(const Eina_Array *array) EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 401 402 /** 403 * @brief Returns the number of elements in an array. 404 * 405 * @param[in] array The array. 406 * @return The number of elements. 407 * 408 * This function returns the number of elements in @p array (array->count). For 409 * performance reasons, there is no check of @p array, so if it is 410 * @c NULL or invalid, the program may crash. 411 */ 412 static inline unsigned int eina_array_count(const Eina_Array *array) EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 413 414 /** 415 * @brief Search for the given data in an array. 416 * 417 * @param[in] array The array. 418 * @param[in] data need to be found. 419 * @param[out] out_idx The position of the data in the array if found. 420 * @return EINA_TRUE if found otherwise returns EINA_FALSE. 421 * 422 * This function searches for the data pointer @p data inside @p array, returning @c EINA_TRUE if found. 423 * The exact position where the pointer is found can be retrieved through @p out_idx. 424 * Please note that only the pointer is compared, not the actual data pointed by it. 425 * 426 * @since 1.23 427 */ 428 static inline Eina_Bool eina_array_find(const Eina_Array *array, 429 const void *data, 430 unsigned int *out_idx) EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 431 /** 432 * @brief Gets a new iterator associated with an array. 433 * 434 * @param[in] array The array. 435 * @return A new iterator, or @c NULL if @p array is @c NULL or has no 436 * items, or if memory could not be allocated. 437 * 438 * This function allocates a new iterator associated with @p array. 439 * Use EINA_ARRAY_ITER_NEXT() to iterate through the array's data items 440 * in order of entry. 441 * 442 * @see Eina_Iterator_Group 443 */ 444 EAPI Eina_Iterator *eina_array_iterator_new(const Eina_Array *array) EINA_MALLOC EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 445 446 /** 447 * @brief Gets a new accessor associated with an array. 448 * 449 * @param[in] array The array. 450 * @return A new accessor, or @c NULL if @p array is @c NULL or has no 451 * items, or if memory could not be allocated. 452 * 453 * This function returns a newly allocated accessor associated with 454 * @p array. Accessors differ from iterators in that they permit 455 * random access. 456 * 457 * @see Eina_Accessor_Group 458 */ 459 EAPI Eina_Accessor *eina_array_accessor_new(const Eina_Array *array) EINA_MALLOC EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 460 461 /** 462 * @brief Iterates over an array using a callback function. 463 * 464 * @param[in] array The array to iterate over. 465 * @param[in] cb The callback to invoke for each item. 466 * @param[in] fdata The user data to pass to the callback. 467 * @return #EINA_TRUE if it successfully iterated all items of the array. 468 * 469 * This function iterates over an array in order, calling @p cb for each 470 * item. @p cb should return #EINA_TRUE if the loop should continue, or 471 * #EINA_FALSE to exit the loop, in which case eina_array_foreach() will 472 * return #EINA_FALSE. 473 */ 474 static inline Eina_Bool eina_array_foreach(Eina_Array *array, 475 Eina_Each_Cb cb, 476 void *fdata); 477 /** 478 * @def EINA_ARRAY_ITER_NEXT 479 * @brief Iterates through an array's elements. 480 * 481 * @param[in] array The array to iterate over. 482 * @param[out] index The integer number that is increased while iterating. 483 * @param[out] item The data 484 * @param[in,out] iterator The #Eina_Array_Iterator. 485 * 486 * This macro iterates over @p array in order, increasing @p index from 487 * the first to last element and setting @p item to each element's data 488 * item in turn. 489 * 490 * This macro can be used for freeing the data of an array, such as 491 * the following example: 492 * 493 * @code 494 * Eina_Array *array; 495 * char *item; 496 * Eina_Array_Iterator iterator; 497 * unsigned int i; 498 * 499 * // array is already filled, 500 * // its elements are just duplicated strings, 501 * // EINA_ARRAY_ITER_NEXT will be used to free those strings 502 * 503 * EINA_ARRAY_ITER_NEXT(array, i, item, iterator) 504 * free(item); 505 * @endcode 506 */ 507 #define EINA_ARRAY_ITER_NEXT(array, index, item, iterator) \ 508 for (index = 0, iterator = (array)->data; \ 509 (index < eina_array_count(array)) && ((item = *((iterator)++))); \ 510 ++(index)) 511 512 #include "eina_inline_array.x" 513 514 /** 515 * @} 516 */ 517 518 /** 519 * @} 520 */ 521 522 /** 523 * @} 524 */ 525 526 #endif 527