1 /**************************************************************************** 2 * Copyright (C) 2006, 2008 by Matteo Franchin * 3 * * 4 * This file is part of Box. * 5 * * 6 * Box is free software: you can redistribute it and/or modify it * 7 * under the terms of the GNU Lesser General Public License as published * 8 * by the Free Software Foundation, either version 3 of the License, or * 9 * (at your option) any later version. * 10 * * 11 * Box is distributed in the hope that it will be useful, * 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 14 * GNU Lesser General Public License for more details. * 15 * * 16 * You should have received a copy of the GNU Lesser General Public * 17 * License along with Box. If not, see <http://www.gnu.org/licenses/>. * 18 ****************************************************************************/ 19 20 /** 21 * @file array.h 22 * @brief Array object, contiguous resizable collection of objects. 23 * 24 * This file implements the #BoxArr object: a resizable collection of blocks of 25 * equal size which are stored contiguously in memory and which. Useful to 26 * accumulate objects whose number is not known a priori and which have to be 27 * referred by index. 28 */ 29 30 #ifndef _BOX_ARRAY_H 31 # define _BOX_ARRAY_H 32 33 # include <box/types.h> 34 # include <box/error.h> 35 36 typedef void (*BoxArrFinalizer)(void *); 37 38 /** 39 * @brief The new array object. 40 */ 41 typedef struct { 42 BoxErr err; /**< Error status */ 43 struct { 44 unsigned int 45 zero : 1; /**< Empty pushed items are zeroed */ 46 } attr; 47 void *ptr; /**< Points to region containing the array of blocks */ 48 BoxUInt 49 dim, /**< Size (in blocks) of the allocated region */ 50 size, /**< Size (in bytes) of the allocated region */ 51 mindim, /**< Minimum value for dim */ 52 elsize, /**< Size of each block */ 53 numel; /**< Number of blocks currently present on the array */ 54 BoxArrFinalizer fin; /**< Used to finalize elements before destruction */ 55 } BoxArr; 56 57 /** Initialize the (already allocated) BoxArr object 'arr' as a new array. 58 * The BoxArr object implements the automatic resizeable array. The array 59 * has an the provided 'initial_size' and when elements are added a check 60 * is made to guarantee that the array is big enough to contain them. 61 * It the array needs to be resized this is done automatically. 62 * @param arr pointer to the memory region where the BoxArr will be kept 63 * @param element_size size of each element of the array 64 * @param initial_size minimum size of the array (this is the size of the 65 * array, even when no elements are contained in it) 66 * @see BoxArr_Finish, BoxArr_New 67 */ 68 BOXEXPORT void BoxArr_Init(BoxArr *arr, size_t element_size, 69 size_t initial_size); 70 71 /** Finalize a BoxArr object, calling the finalizer for each remaining 72 * element, if necessary. The function does not deallocate the region 73 * of memory which contains the BoxArr object itself, but rather deallocates 74 * the data block of the array. Therefore this function is to be used 75 * in couple with BoxArr_Init. 76 * @see BoxArr_Init 77 */ 78 BOXEXPORT void BoxArr_Finish(BoxArr *arr); 79 80 /** Similar to BoxArr_Init, but also allocates the memory region to contain 81 * the BoxArr data structure. Consequently, if you use this function, 82 * you should use BoxArr_Destroy to finalize the array (you must not use 83 * BoxArr_Finish). 84 * @see BoxArr_Destroy, BoxArr_Init 85 */ 86 BOXEXPORT BoxArr *BoxArr_Create(size_t element_size, size_t initial_size); 87 88 #define BoxArr_New BoxArr_Create 89 90 /** Similar to BoxArr_Init, but frees also the region containing 91 * the BoxArr object. Suitable to be used with BoxArr_New (and must NOT 92 * be used with BoxArr_Init). 93 * @see BoxArr_New 94 */ 95 BOXEXPORT void BoxArr_Destroy(BoxArr *arr); 96 97 /** Attributes corresponding to different behaviours of the BoxArr object: 98 * BOXARR_ERR_STATUS corresponds to the error status of the array, which is set 99 * when an allocation or similar problem occurs. BOXARR_ERR_TOLERANT decides 100 * how to behave on such errors: abort the program, or tolerate the error and 101 * just put the BoxArr object in the error state. BOXARR_CLEAR_ITEMS decides 102 * whether a NULL pointer in BoxArr_MPush, BoxArr_Insert, etc. should lead to 103 * insertion of zero filled items or to the insertion of uninitialised items. 104 */ 105 typedef enum { 106 BOXARR_ERR_STATUS = 1, /**< When set, this bit indicates a failure */ 107 BOXARR_ERR_TOLERANT = 2, /**< When set, errors (such as failure in allocation 108 or reallocation of the array) are tolerated 109 and signalled. When cleared, the program is 110 aborted. */ 111 BOXARR_CLEAR_ITEMS = 4 /**< When set, new items in the array are zeroed 112 (in BoxArr_MPush or BoxArr_Insert). */ 113 } BoxArrAttr; 114 115 /** Set the attributes which control the behaviour of the BoxArr object. 116 * @see BoxArrAttr 117 */ 118 BOXEXPORT void BoxArr_Set_Attr(BoxArr *arr, BoxArrAttr mask, 119 BoxArrAttr value); 120 121 /** Returns 1 if the provided BoxArr object is in error state, 0 otherwise. 122 */ 123 BOXEXPORT int BoxArr_Is_Err(BoxArr *arr); 124 125 /** Sets a finalizer to call for each element which is removed 126 * from the array (just before doing it). 127 */ 128 BOXEXPORT void BoxArr_Set_Finalizer(BoxArr *arr, BoxArrFinalizer fin); 129 130 /** Returns the pointer to the item of the provided array with index 131 * item_index. Out of bounds errors are detected and treated conformly 132 * to the error policy set with BoxArr_Set_Err_Policy 133 * @see BoxArr_Set_Err_Policy 134 */ 135 BOXEXPORT void *BoxArr_Get_Item_Ptr(BoxArr *arr, BoxUInt item_index); 136 137 #define BoxArr_Item_Ptr BoxArr_Get_Item_Ptr 138 139 /** Prototype of function used by BoxArr_Iter to iterate over the elements 140 * of the provided array. 141 * @param item_index the index (1..num_items) of the considered item 142 * @param item_ptr pointer to the item 143 * @param pass_data data provided to the BoxArr_Iter function to be passed 144 * to the iterator. 145 * @return 1 to continue the iteration, 0 to break it 146 * @see BoxArr_Iter 147 */ 148 typedef int (*BoxArrIterator)(BoxUInt item_index, void *item_ptr, 149 void *pass_data); 150 151 /** Execute the iterator 'iter' for each element of the array 'arr'. 152 * The iterator receives the element index, the element pointer and 153 * the pointer 'pass_data', which was given in the call to BoxArr_Iter. 154 * @return 0 if the iteration was broken by the iterator, 0 otherwise 155 * @see BoxArrIterator 156 */ 157 BOXEXPORT int BoxArr_Iter(BoxArr *arr, BoxArrIterator iter, void *pass_data); 158 159 /** Function which is expected to compare 'left' and 'right', returning 160 * 0 if they are equal, 1 if left > right or -1 if left < right. 161 * @see BoxArr_Find 162 */ 163 typedef int (*BoxArrCmp)(void *left, void *right, void *pass_data); 164 165 /** 166 * @brief Find an item in the array. 167 * 168 * Goes through the elements of the given array 'arr' and returns the 169 * index of the first item 'x' for which 'cmp(x, item, pass_data)' 170 * returned 0 ('item', 'cmp', and 'pass_data' are the second, third and fourth 171 * arguments given to the function). 172 * If the user specifies 'cmp == NULL', then return the index of the first 173 * element of the array which matches (via memcmp) with the one pointed by 174 * 'item'. 175 */ 176 BOXEXPORT size_t 177 BoxArr_Find(BoxArr *arr, void *item, BoxArrCmp cmp, void *pass_data); 178 179 /** Remove all the elements of the 'arr' invoking the destructor for each 180 * removed item, if necessary. After the call to this function, the BoxArr 181 * object will be empty and with no allocated space for its elements 182 * (if an element is then inserted an automatic malloc will restore 183 * the data block for the BoxArr object). 184 */ 185 BOXEXPORT void BoxArr_Clear(BoxArr *arr); 186 187 /** Remove all the elements from the array. */ 188 #define BoxArr_Empty(arr) \ 189 do {BoxArr_MPop((arr), NULL, BoxArr_Get_Num_Items((arr)));} while(0) 190 191 /** 192 * Push new elements into the provided array. The items are appended to the 193 * array. If 'items' is the NULL pointer the items are inserted being set to 194 * zero or without being set at all, if BoxArr_Set_Attr was used to disable the 195 * automatic clearing. 196 * 197 * @param arr the target array 198 * @param items the pointer to the items to be inserted 199 * @param num_items the number of items to be inserted 200 * @see BoxArr_Push, BoxArr_Set_Attr 201 * @note Return the pointer in memory to the last inserted item. One may 202 * then pass 'items == NULL' and fill the items after they have been 203 * allocated, like this: 204 * ItemType *item = BoxArr_MPush(a, NULL, 2); 205 * item[0] = ...; item[1] = ...; 206 */ 207 BOXEXPORT void *BoxArr_MPush(BoxArr *arr, const void *items, size_t num_items); 208 209 /** Similar to BoxArr_MPush, but pushes just one item into the array. 210 * @see BoxArr_MPush 211 */ 212 #define BoxArr_Push(arr, item) BoxArr_MPush((arr), (item), (BoxUInt) 1) 213 214 /** Remove the specified number of items from the top of the array 215 * and put them in 'items'. If 'items' is the NULL pointer, then the items 216 * are just removed from the array. The finalizer is called before moving 217 * the items, if defined. 218 * @see BoxArr_Pop 219 */ 220 BOXEXPORT void BoxArr_MPop(BoxArr *arr, void *items, BoxUInt num_items); 221 222 /** Similar to BoxArr_MPop, but pops just one item into from the array. 223 * @see BoxArr_MPop 224 */ 225 #define BoxArr_Pop(arr, item) BoxArr_MPop((arr), (item), (BoxUInt) 1) 226 227 /** Inserts elements at the specified position in the array. 228 * If 'items' is the NULL pointer the items are inserted being set to zero 229 * or without being set at all, if BoxArr_Set_Attr was used to disable 230 * the automatic clearing. 231 * @param arr the target array 232 * @param items the pointer to the items to be inserted 233 * @param num_items the number of items to be inserted 234 * @see BoxArr_Set_Attr, BoxArr_Push, BoxArr_Overwrite 235 */ 236 BOXEXPORT void *BoxArr_Insert(BoxArr *arr, BoxUInt insert_index, 237 const void *items, BoxUInt num_items); 238 239 /** Overwrite the array at position 'ow_index' with the provided items. 240 * If 'items' is the NULL pointer the items are written as if they were zero 241 * filled or without being set at all, if BoxArr_Set_Attr was used to disable 242 * the automatic clearing. 243 * @see BoxArr_Set_Attr, BoxArr_Push, BoxArr_Insert 244 */ 245 BOXEXPORT void *BoxArr_Overwrite(BoxArr *arr, BoxUInt ow_index, 246 const void *items, BoxUInt num_items); 247 248 /** Reallocate the array so that it occupies just the amount of memory which 249 * is needed to store its elements. The function is useful to reduce the 250 * memory footprint and should be called when the array has been populated 251 * and no further elements are going to be added to it (even if that may still 252 * happen without faults). 253 */ 254 BOXEXPORT void BoxArr_Compactify(BoxArr *arr); 255 256 /** Returns the number of elements currently inserted in the provided array. 257 */ 258 #define BoxArr_Get_Num_Items(arr) ((const size_t) (arr)->numel) 259 260 /** Obsolete version of BoxArr_Get_Num_Items. */ 261 #define BoxArr_Num_Items(arr) ((arr)->numel) 262 263 /** Returns the pointer to the memory block containing the data for the array. 264 */ 265 #define BoxArr_Get_First_Item(arr) ((arr)->ptr) 266 267 #define BoxArr_First_Item_Ptr BoxArr_Get_First_Item 268 269 /** Returns the pointer to the last item stored in the array. 270 */ 271 #define BoxArr_Get_Last_Item_Ptr(arr) \ 272 ((arr)->ptr + ((arr)->numel - 1)*((BoxUInt) (arr)->elsize)) 273 274 #define BoxArr_Last_Item_Ptr BoxArr_Get_Last_Item_Ptr 275 276 277 /*#define BOXARR_DEBUG_MACROS*/ 278 279 #ifdef BOXARR_DEBUG_MACROS 280 # define BOXARR_MACRO1(fn, ...) (fn(__VA_ARGS__) + 0*printf(#fn" in %s (%d) \n", __FILE__, __LINE__)) 281 # define BOXARR_MACRO2(fn, ...) {fn(__VA_ARGS__); (void) printf(#fn" in %s (%d) \n", __FILE__, __LINE__);} 282 283 # define BoxArr_Init(...) BOXARR_MACRO2(BoxArr_Init, __VA_ARGS__) 284 #endif 285 286 #endif /* _BOX_ARRAY_H */ 287