1 /** 2 * @file 3 * Linear Array data structure 4 * 5 * @authors 6 * Copyright (C) 2020 Pietro Cerutti <gahr@gahr.ch> 7 * 8 * @copyright 9 * This program is free software: you can redistribute it and/or modify it under 10 * the terms of the GNU General Public License as published by the Free Software 11 * Foundation, either version 2 of the License, or (at your option) any later 12 * version. 13 * 14 * This program is distributed in the hope that it will be useful, but WITHOUT 15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 16 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 17 * details. 18 * 19 * You should have received a copy of the GNU General Public License along with 20 * this program. If not, see <http://www.gnu.org/licenses/>. 21 */ 22 23 /** 24 * @page mutt_array Linear array API 25 * 26 * API to store contiguous elements. 27 */ 28 29 #include <stdbool.h> 30 #include <string.h> 31 #include "memory.h" 32 33 /** 34 * ARRAY_HEADROOM - Additional number of elements to reserve, to prevent frequent reallocations 35 */ 36 #define ARRAY_HEADROOM 25 37 38 /** 39 * ARRAY_HEAD - Define a named struct for arrays of elements of a certain type 40 * @param name Name of the resulting struct 41 * @param type Type of the elements stored in the array 42 */ 43 #define ARRAY_HEAD(name, type) \ 44 struct name \ 45 { \ 46 size_t size; /**< Number of items in the array */ \ 47 size_t capacity; /**< Maximum number of items in the array */ \ 48 type *entries; /**< A C array of the items */ \ 49 } 50 51 /** 52 * ARRAY_HEAD_INITIALIZER - Static initializer for arrays 53 */ 54 #define ARRAY_HEAD_INITIALIZER \ 55 { 0, 0, NULL } 56 57 /** 58 * ARRAY_INIT - Initialize an array 59 * @param head Pointer to a struct defined using ARRAY_HEAD() 60 */ 61 #define ARRAY_INIT(head) \ 62 memset((head), 0, sizeof(*(head))) 63 64 /** 65 * ARRAY_EMPTY - Check if an array is empty 66 * @param head Pointer to a struct defined using ARRAY_HEAD() 67 * @retval true The array is empty 68 * @retval false The array is not empty 69 */ 70 #define ARRAY_EMPTY(head) \ 71 ((head)->size == 0) 72 73 /** 74 * ARRAY_SIZE - The number of elements stored 75 * @param head Pointer to a struct defined using ARRAY_HEAD() 76 * @retval num Number of elements stored 77 * 78 * @note Because it is possible to add elements in the middle of the array, see 79 * ARRAY_SET(), the number returned by ARRAY_SIZE() can be larger than 80 * the number of elements actually stored. Holes are filled with zero at 81 * ARRAY_RESERVE() time and are left untouched by ARRAY_SHRINK(). 82 */ 83 #define ARRAY_SIZE(head) \ 84 ((head)->size) 85 86 /** 87 * ARRAY_CAPACITY - The number of elements the array can store without reallocation 88 * @param head Pointer to a struct defined using ARRAY_HEAD() 89 * @retval num The capacity of the array 90 */ 91 #define ARRAY_CAPACITY(head) \ 92 ((head)->capacity) 93 94 /** 95 * ARRAY_GET - Return the element at index 96 * @param head Pointer to a struct defined using ARRAY_HEAD() 97 * @param idx Index, between 0 and ARRAY_SIZE()-1 98 * @retval ptr Pointer to the element at the given index 99 * @retval NULL Index was out of bounds 100 * 101 * @note Because it is possible to add elements in the middle of the array, it 102 * is also possible to retrieve elements that weren't previously 103 * explicitly set. In that case, the memory returned is all zeroes. 104 */ 105 #define ARRAY_GET(head, idx) \ 106 ((head)->size > (idx) ? &(head)->entries[(idx)] : NULL) 107 108 /** 109 * ARRAY_SET - Set an element in the array 110 * @param head Pointer to a struct defined using ARRAY_HEAD() 111 * @param idx Index, between 0 and ARRAY_SIZE()-1 112 * @param elem Element to copy 113 * @retval true Element was inserted 114 * @retval false Element was not inserted, array was full 115 * 116 * @note This method has the side effect of changing the array size, 117 * if the insertion happens after the last element. 118 */ 119 #define ARRAY_SET(head, idx, elem) \ 120 (((head)->capacity > (idx) \ 121 ? true \ 122 : ARRAY_RESERVE((head), (idx) + 1)), \ 123 ARRAY_SET_NORESERVE((head), (idx), (elem))) 124 125 /** 126 * ARRAY_FIRST - Convenience method to get the first element 127 * @param head Pointer to a struct defined using ARRAY_HEAD() 128 * @retval ptr Pointer to the first element 129 * @retval NULL Array is empty 130 */ 131 #define ARRAY_FIRST(head) \ 132 ARRAY_GET((head), 0) 133 134 /** 135 * ARRAY_LAST - Convenience method to get the last element 136 * @param head Pointer to a struct defined using ARRAY_HEAD() 137 * @retval ptr Pointer to the last element 138 * @retval NULL Array is empty 139 */ 140 #define ARRAY_LAST(head) \ 141 (ARRAY_EMPTY((head)) \ 142 ? NULL \ 143 : ARRAY_GET((head), ARRAY_SIZE((head)) - 1)) 144 145 /** 146 * ARRAY_ADD - Add an element at the end of the array 147 * @param head Pointer to a struct defined using ARRAY_HEAD() 148 * @param elem Element to copy 149 * @retval true Element was added 150 * @retval false Element was not added, array was full 151 */ 152 #define ARRAY_ADD(head, elem) \ 153 (((head)->capacity > (head)->size \ 154 ? true \ 155 : ARRAY_RESERVE((head), (head)->size + 1)), \ 156 ARRAY_ADD_NORESERVE((head), (elem))) 157 158 /** 159 * ARRAY_SHRINK - Mark a number of slots at the end of the array as unused 160 * @param head Pointer to a struct defined using ARRAY_HEAD() 161 * @param num Number of slots to mark as unused 162 * @retval num New size of the array 163 * 164 * @note This method does not do any memory management and has no effect on the 165 * capacity nor the contents of the array. It is just a resize which only 166 * works downwards. 167 */ 168 #define ARRAY_SHRINK(head, num) \ 169 ((head)->size -= MIN((num), (head)->size)) 170 171 /** 172 * ARRAY_ELEM_SIZE - Number of bytes occupied by an element of this array 173 * @param head Pointer to a struct defined using ARRAY_HEAD() 174 * @retval num Number of bytes per element 175 */ 176 #define ARRAY_ELEM_SIZE(head) \ 177 (sizeof(*(head)->entries)) 178 179 /** 180 * ARRAY_RESERVE - Reserve memory for the array 181 * @param head Pointer to a struct defined using ARRAY_HEAD() 182 * @param num Number of elements to make room for 183 * @retval num New capacity of the array 184 */ 185 #define ARRAY_RESERVE(head, num) \ 186 (((head)->capacity > (num)) ? \ 187 (head)->capacity : \ 188 ((mutt_mem_realloc( \ 189 &(head)->entries, ((num) + ARRAY_HEADROOM) * ARRAY_ELEM_SIZE(head))), \ 190 (memset((head)->entries + (head)->capacity, 0, \ 191 ((num) + ARRAY_HEADROOM - (head)->capacity) * \ 192 ARRAY_ELEM_SIZE(head))), \ 193 ((head)->capacity = (num) + ARRAY_HEADROOM))) 194 195 /** 196 * ARRAY_FREE - Release all memory 197 * @param head Pointer to a struct defined using ARRAY_HEAD() 198 * @retval 0 199 */ 200 #define ARRAY_FREE(head) \ 201 (FREE(&(head)->entries), (head)->size = (head)->capacity = 0) 202 203 /** 204 * ARRAY_FOREACH - Iterate over all elements of the array 205 * @param elem Variable to be used as pointer to the element at each iteration 206 * @param head Pointer to a struct defined using ARRAY_HEAD() 207 */ 208 #define ARRAY_FOREACH(elem, head) \ 209 ARRAY_FOREACH_FROM_TO((elem), (head), 0, (head)->size) 210 211 /** 212 * ARRAY_FOREACH_FROM - Iterate from an index to the end 213 * @param elem Variable to be used as pointer to the element at each iteration 214 * @param head Pointer to a struct defined using ARRAY_HEAD() 215 * @param from Starting index (inclusive) 216 * 217 * @note The from index must be between 0 and ARRAY_SIZE(head) 218 */ 219 #define ARRAY_FOREACH_FROM(elem, head, from) \ 220 ARRAY_FOREACH_FROM_TO((elem), (head), (from), (head)->size) 221 222 /** 223 * ARRAY_FOREACH_TO - Iterate from the beginning to an index 224 * @param elem Variable to be used as pointer to the element at each iteration 225 * @param head Pointer to a struct defined using ARRAY_HEAD() 226 * @param to Terminating index (exclusive) 227 * 228 * @note The to index must be between 0 and ARRAY_SIZE(head) 229 */ 230 #define ARRAY_FOREACH_TO(elem, head, to) \ 231 ARRAY_FOREACH_FROM_TO((elem), (head), 0, (to)) 232 233 /** 234 * ARRAY_FOREACH_FROM_TO - Iterate between two indexes 235 * @param elem Variable to be used as pointer to the element at each iteration 236 * @param head Pointer to a struct defined using ARRAY_HEAD() 237 * @param from Starting index (inclusive) 238 * @param to Terminating index (exclusive) 239 * 240 * @note The from and to indexes must be between 0 and ARRAY_SIZE(head); 241 * the from index must not be bigger than to index. 242 */ 243 #define ARRAY_FOREACH_FROM_TO(elem, head, from, to) \ 244 for (size_t ARRAY_FOREACH_IDX = (from); \ 245 (ARRAY_FOREACH_IDX < (to)) && \ 246 ((elem) = ARRAY_GET((head), ARRAY_FOREACH_IDX)); \ 247 ARRAY_FOREACH_IDX++) 248 249 /** 250 * ARRAY_IDX - Return the index of an element of the array 251 * @param head Pointer to a struct defined using ARRAY_HEAD() 252 * @param elem Pointer to an element of the array 253 * @retval num The index of element in the array 254 */ 255 #define ARRAY_IDX(head, elem) \ 256 (elem - (head)->entries) 257 258 /** 259 * ARRAY_REMOVE - Remove an entry from the array, shifting down the subsequent entries 260 * @param head Pointer to a struct defined using ARRAY_HEAD() 261 * @param elem Pointer to the element of the array to remove 262 */ 263 #define ARRAY_REMOVE(head, elem) \ 264 (memmove((elem), (elem) + 1, \ 265 ARRAY_ELEM_SIZE((head)) * \ 266 MAX(0, (ARRAY_SIZE((head)) - ARRAY_IDX((head), (elem)) - 1))), \ 267 ARRAY_SHRINK((head), 1)) 268 269 /** 270 * ARRAY_SORT - Sort an array 271 * @param head Pointer to a struct defined using ARRAY_HEAD() 272 * @param fn Sort function, see ::sort_t 273 */ 274 #define ARRAY_SORT(head, fn) \ 275 qsort((head)->entries, ARRAY_SIZE(head), ARRAY_ELEM_SIZE(head), (fn)) 276 277 /****************************************************************************** 278 * Internal APIs 279 *****************************************************************************/ 280 #define ARRAY_SET_NORESERVE(head, idx, elem) \ 281 ((head)->capacity > (idx) \ 282 ? (((head)->size = MAX((head)->size, ((idx) + 1))), \ 283 ((head)->entries[(idx)] = (elem)), \ 284 true) \ 285 : false) 286 287 #define ARRAY_ADD_NORESERVE(head, elem) \ 288 ((head)->capacity > (head)->size \ 289 ? (((head)->entries[(head)->size++] = (elem)), \ 290 true) \ 291 : false) 292 293