free_list.h (7055B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #ifndef FITEM_TYPE 17 /* 18 * Declare regular free list types and macros. May be include before any free 19 * list declaration 20 */ 21 # ifndef FREE_LIST_H 22 # define FREE_LIST_H 23 24 #include "rsys.h" 25 26 /* A free list item must be a structure with a FITEM field */ 27 #define FITEM \ 28 struct { \ 29 struct fid id; \ 30 uint32_t next; \ 31 uint32_t prev; \ 32 } fitem__ 33 34 /* Unique identifier of a free list item */ 35 struct fid { 36 uint32_t index; /* Index into the free list */ 37 uint32_t name; /* Unique id that identifies this item */ 38 }; 39 40 static const struct fid FID_NULL = { UINT32_MAX, UINT32_MAX }; 41 42 /* Helper macros that defines if a free list identifier is NULL or not */ 43 #define IS_FID_NULL(Fid) ((Fid).index == UINT32_MAX) 44 45 /* Compare 2 free list identifiers */ 46 #define FID_EQ(Fid0, Fid1) \ 47 ((Fid0).index == (Fid1).index && (Fid0).name == (Fid1).name) 48 49 /* Helper macro that iterates over the items of the free list */ 50 #define FLIST_FOR_EACH(Item, List) \ 51 for((Item) = (List)->tail != UINT32_MAX \ 52 ? (List)->items + (List)->tail : NULL; \ 53 (Item) != NULL; \ 54 (Item) = (Item)->fitem__.prev != UINT32_MAX \ 55 ? (List)->items + (Item)->fitem__.prev : NULL) 56 57 # endif /* FREE_LIST_H */ 58 59 #else 60 /* 61 * Free list API generated with respect to the FITEM_TYPE macro. 62 * 63 * The name of the generated free list type is: 64 * struct flist_<FITEM_TYPE> 65 * 66 * while each generated `function' respect the following naming convention: 67 * flist_<FITEM_TYPE>_<function> 68 */ 69 #define FLIST_FUNC__(Func) CONCAT(CONCAT(CONCAT(flist_, FITEM_TYPE), _), Func) 70 #define FLIST_TYPE__ CONCAT(flist_, FITEM_TYPE) 71 72 #include "mem_allocator.h" 73 #include <string.h> 74 75 struct FLIST_TYPE__ { 76 uint32_t head; /* Index toward the first free item */ 77 uint32_t tail; /* Index toward the last created item */ 78 uint32_t name_next; /* Next unique free list item name */ 79 struct FITEM_TYPE* items; 80 uint32_t nitems; 81 struct mem_allocator* allocator; 82 }; 83 84 static FINLINE void 85 FLIST_FUNC__(init) 86 (struct mem_allocator* allocator, /* May be NULL <=> use default allocator */ 87 struct FLIST_TYPE__* list) 88 { 89 ASSERT(list); 90 list->head = UINT32_MAX; 91 list->tail = UINT32_MAX; 92 list->name_next = 0; 93 list->items = NULL; 94 list->nitems = 0; 95 list->allocator = allocator ? allocator : &mem_default_allocator; 96 } 97 98 static FINLINE void 99 FLIST_FUNC__(release)(struct FLIST_TYPE__* list) 100 { 101 ASSERT(list); 102 MEM_RM(list->allocator, list->items); 103 } 104 105 static FINLINE char 106 FLIST_FUNC__(hold)(struct FLIST_TYPE__* list, struct fid id) 107 { 108 ASSERT(list); 109 return id.index < list->nitems 110 && list->items[id.index].fitem__.id.name == id.name; 111 } 112 113 static FINLINE struct FITEM_TYPE* 114 FLIST_FUNC__(get)(struct FLIST_TYPE__* list, struct fid id) 115 { 116 ASSERT(list); 117 if(FLIST_FUNC__(hold)(list, id)) { 118 return list->items + id.index; 119 } else { 120 return NULL; 121 } 122 } 123 124 static INLINE struct fid 125 FLIST_FUNC__(add)(struct FLIST_TYPE__* list) 126 { 127 struct fid id; 128 ASSERT(list); 129 130 id.name = list->name_next++; 131 if(list->head != UINT32_MAX) { 132 id.index = list->head; 133 list->head = list->items[list->head].fitem__.next; 134 } else { /* Increase the free list size */ 135 const uint32_t nitems_new = list->nitems ? list->nitems * 2 : 16; 136 uint32_t iitem = 0; 137 struct FITEM_TYPE item; 138 memset(&item, 0, sizeof(struct FITEM_TYPE)); 139 140 id.index = list->nitems; 141 list->items = (struct FITEM_TYPE*)MEM_REALLOC 142 (list->allocator, 143 list->items, 144 nitems_new * sizeof(struct FITEM_TYPE)); 145 if(!list->items) 146 FATAL("Unsufficient memory\n"); 147 FOR_EACH(iitem, list->nitems, nitems_new) { 148 list->items[iitem].fitem__.prev = iitem - 1; 149 list->items[iitem].fitem__.next = iitem + 1; 150 list->items[iitem].fitem__.id.name = UINT32_MAX; 151 } 152 list->items[nitems_new - 1].fitem__.next = UINT32_MAX; 153 list->head = list->nitems + 1; 154 list->nitems = nitems_new; 155 } 156 list->items[id.index].fitem__.id = id; 157 158 /* Add the item in the linked list of valid element */ 159 if(list->tail != UINT32_MAX) 160 list->items[list->tail].fitem__.next = id.index; 161 list->items[id.index].fitem__.prev = list->tail; 162 list->items[id.index].fitem__.next = UINT32_MAX; 163 list->tail = id.index; 164 return id; 165 } 166 167 static FINLINE void 168 FLIST_FUNC__(del)(struct FLIST_TYPE__* list, struct fid id) 169 { 170 ASSERT(list); 171 if(FLIST_FUNC__(hold)(list, id)) { 172 struct FITEM_TYPE* item = FLIST_FUNC__(get)(list, id); 173 174 /* Unlink the item from the double linked list of valid items */ 175 if(item->fitem__.prev != UINT32_MAX) 176 list->items[item->fitem__.prev].fitem__.next = item->fitem__.next; 177 if(item->fitem__.next != UINT32_MAX) { 178 list->items[item->fitem__.next].fitem__.prev = item->fitem__.prev; 179 } else { 180 ASSERT(item->fitem__.id.index == list->tail); 181 list->tail = item->fitem__.prev; 182 } 183 184 /* Add the item to the single linked list of free items */ 185 item->fitem__.next = list->head; 186 list->head = item->fitem__.id.index; 187 item->fitem__.id = FID_NULL; 188 } 189 } 190 191 static FINLINE void 192 FLIST_FUNC__(clear)(struct FLIST_TYPE__* list) 193 { 194 uint32_t iitem; 195 ASSERT(list); 196 FOR_EACH(iitem, 0, list->nitems) { 197 list->items[iitem].fitem__.next = iitem + 1; 198 list->items[iitem].fitem__.prev = iitem - 1; 199 list->items[iitem].fitem__.id.name = UINT32_MAX; 200 } 201 if(!list->nitems) { 202 list->head = UINT32_MAX; 203 } else { 204 list->head = 0; 205 list->items[list->nitems - 1].fitem__.next = UINT32_MAX; 206 } 207 list->tail = UINT32_MAX; 208 } 209 210 static FINLINE struct fid 211 CONCAT(FITEM_TYPE, _id_get)(const struct FITEM_TYPE* item) 212 { 213 ASSERT(item); 214 return item->fitem__.id; 215 } 216 217 static FINLINE int 218 FLIST_FUNC__(is_empty)(struct FLIST_TYPE__* list) 219 { 220 ASSERT(list); 221 return list->tail == UINT32_MAX; 222 } 223 224 #undef FLIST_TYPE__ 225 #undef FLIST_FUNC__ 226 #undef FITEM_TYPE 227 228 #endif /* ifdef FITEM_TYPE */