1 /* 2 * SPDX-FileCopyrightText: Copyright (c) 2015-2023 NVIDIA CORPORATION & AFFILIATES. All rights reserved. 3 * SPDX-License-Identifier: MIT 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 * and/or sell copies of the Software, and to permit persons to whom the 10 * Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be included in 13 * all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 #ifndef _NV_CONTAINERS_LIST_H_ 24 #define _NV_CONTAINERS_LIST_H_ 25 26 // Contains mix of C/C++ declarations. 27 #include "containers/type_safety.h" 28 29 #ifdef __cplusplus 30 extern "C" { 31 #endif 32 33 #include "nvtypes.h" 34 #include "nvmisc.h" 35 #include "nvport/nvport.h" 36 #include "utils/nvassert.h" 37 38 /** 39 * @defgroup NV_CONTAINERS_LIST List 40 * 41 * @brief List (sequence) of user-defined values. 42 * 43 * @details Order of values is not necessarily increasing or sorted, but order is 44 * preserved across mutation. Please see 45 * https://en.wikipedia.org/wiki/Sequence for a formal definition. 46 * 47 * The provided interface is abstract, decoupling the user from the underlying 48 * list implementation. Two options are available with regard to memory 49 * management, intrusive and non-intrusive. Users can select either one based 50 * on different situations. Despite the two versions of the list, the following 51 * implementation constraints are guaranteed. 52 * 53 * - Time Complexity: 54 * * Operations are \b O(1), 55 * * Unless stated otherwise. 56 * 57 * - Memory Usage: 58 * * \b O(N) memory is required for N values. 59 * * Intrusive and non-intrusive variants are provided. 60 * See @ref mem-ownership for further details. 61 * 62 * - Synchronization: 63 * * \b None. The container is not thread-safe. 64 * * Locking must be handled by the user if required. 65 */ 66 67 #define MAKE_LIST(listTypeName, dataType) \ 68 typedef union listTypeName##Iter \ 69 { \ 70 dataType *pValue; \ 71 ListIterBase iter; \ 72 } listTypeName##Iter; \ 73 typedef union listTypeName \ 74 { \ 75 NonIntrusiveList real; \ 76 CONT_TAG_TYPE(ListBase, dataType, listTypeName##Iter); \ 77 CONT_TAG_NON_INTRUSIVE(dataType); \ 78 } listTypeName 79 80 #define DECLARE_LIST(listTypeName) \ 81 typedef union listTypeName##Iter listTypeName##Iter; \ 82 typedef union listTypeName listTypeName 83 84 #define MAKE_INTRUSIVE_LIST(listTypeName, dataType, node) \ 85 typedef union listTypeName##Iter \ 86 { \ 87 dataType *pValue; \ 88 ListIterBase iter; \ 89 } listTypeName##Iter; \ 90 typedef union listTypeName \ 91 { \ 92 IntrusiveList real; \ 93 CONT_TAG_TYPE(ListBase, dataType, listTypeName##Iter); \ 94 CONT_TAG_INTRUSIVE(dataType, node); \ 95 } listTypeName \ 96 97 #define DECLARE_INTRUSIVE_LIST(listTypeName) \ 98 typedef union listTypeName##Iter listTypeName##Iter; \ 99 typedef union listTypeName listTypeName 100 101 /** 102 * @brief Internal node structure to embed within intrusive list values. 103 */ 104 typedef struct ListNode ListNode; 105 106 /** 107 * @brief Base type common to both intrusive and non-intrusive variants. 108 */ 109 typedef struct ListBase ListBase; 110 111 /** 112 * @brief Non-intrusive list (container-managed memory). 113 */ 114 typedef struct NonIntrusiveList NonIntrusiveList; 115 116 /** 117 * @brief Intrusive list (user-managed memory). 118 */ 119 typedef struct IntrusiveList IntrusiveList; 120 121 /** 122 * @brief Iterator over a range of list values. 123 * 124 * See @ref iterators for usage details. 125 */ 126 typedef struct ListIterBase ListIterBase; 127 128 struct ListNode 129 { 130 /// @privatesection 131 ListNode *pPrev; 132 ListNode *pNext; 133 #if PORT_IS_CHECKED_BUILD 134 ListBase *pList; 135 #endif 136 }; 137 138 struct ListIterBase 139 { 140 void *pValue; 141 ListBase *pList; 142 ListNode *pNode; 143 ListNode *pLast; 144 #if PORT_IS_CHECKED_BUILD 145 NvU32 versionNumber; 146 #endif 147 }; 148 149 ListIterBase listIterRange_IMPL(ListBase *pList, void *pFirst, void *pLast); 150 CONT_VTABLE_DECL(ListBase, ListIterBase); 151 152 struct ListBase 153 { 154 CONT_VTABLE_FIELD(ListBase); 155 ListNode *pHead; 156 ListNode *pTail; 157 NvU32 count; 158 NvS32 nodeOffset; 159 #if PORT_IS_CHECKED_BUILD 160 NvU32 versionNumber; 161 #endif 162 }; 163 164 struct NonIntrusiveList 165 { 166 ListBase base; 167 PORT_MEM_ALLOCATOR *pAllocator; 168 NvU32 valueSize; 169 }; 170 171 struct IntrusiveList 172 { 173 ListBase base; 174 }; 175 176 #define listInit(pList, pAllocator) \ 177 listInit_IMPL(&((pList)->real), pAllocator, sizeof(*(pList)->valueSize)) 178 179 #define listInitIntrusive(pList) \ 180 listInitIntrusive_IMPL(&((pList)->real), sizeof(*(pList)->nodeOffset)) 181 182 #define listDestroy(pList) \ 183 CONT_DISPATCH_ON_KIND(pList, \ 184 listDestroy_IMPL((NonIntrusiveList*)&((pList)->real)), \ 185 listDestroyIntrusive_IMPL(&((pList)->real.base)), \ 186 contDispatchVoid_STUB()) 187 188 #define listCount(pList) \ 189 listCount_IMPL(&((pList)->real).base) 190 191 #define listInsertNew(pList, pNext) \ 192 CONT_CAST_ELEM(pList, \ 193 listInsertNew_IMPL(&(pList)->real, \ 194 CONT_CHECK_ARG(pList, pNext)), listIsValid_IMPL) 195 196 #define listAppendNew(pList) \ 197 CONT_CAST_ELEM(pList, listAppendNew_IMPL(&(pList)->real), listIsValid_IMPL) 198 199 #define listPrependNew(pList) \ 200 CONT_CAST_ELEM(pList, listPrependNew_IMPL(&(pList)->real), listIsValid_IMPL) 201 202 #define listInsertValue(pList, pNext, pValue) \ 203 CONT_CAST_ELEM(pList, \ 204 listInsertValue_IMPL(&(pList)->real, \ 205 CONT_CHECK_ARG(pList, pNext), \ 206 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 207 208 #define listAppendValue(pList, pValue) \ 209 CONT_CAST_ELEM(pList, \ 210 listAppendValue_IMPL(&(pList)->real, \ 211 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 212 213 #define listPrependValue(pList, pValue) \ 214 CONT_CAST_ELEM(pList, \ 215 listPrependValue_IMPL(&(pList)->real, \ 216 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 217 218 #define listInsertExisting(pList, pNext, pValue) \ 219 listInsertExisting_IMPL(&(pList)->real, \ 220 CONT_CHECK_ARG(pList, pNext), \ 221 CONT_CHECK_ARG(pList, pValue)) 222 223 #define listAppendExisting(pList, pValue) \ 224 listAppendExisting_IMPL(&(pList)->real, \ 225 CONT_CHECK_ARG(pList, pValue)) 226 227 #define listPrependExisting(pList, pValue) \ 228 listPrependExisting_IMPL(&(pList)->real, \ 229 CONT_CHECK_ARG(pList, pValue)) 230 231 #define listRemove(pList, pValue) \ 232 CONT_DISPATCH_ON_KIND(pList, \ 233 listRemove_IMPL((NonIntrusiveList*)&((pList)->real), \ 234 CONT_CHECK_ARG(pList, pValue)), \ 235 listRemoveIntrusive_IMPL(&((pList)->real).base, \ 236 CONT_CHECK_ARG(pList, pValue)), \ 237 contDispatchVoid_STUB()) 238 239 #define listRemoveFirstByValue(pList, pValue) \ 240 listRemoveFirstByValue_IMPL(&(pList)->real, \ 241 CONT_CHECK_ARG(pList, pValue)) 242 243 #define listRemoveAllByValue(pList, pValue) \ 244 listRemoveAllByValue_IMPL(&(pList)->real, \ 245 CONT_CHECK_ARG(pList, pValue)) 246 247 #define listClear(pList) \ 248 listDestroy(pList) 249 250 #define listFindByValue(pList, pValue) \ 251 CONT_CAST_ELEM(pList, \ 252 listFindByValue_IMPL(&(pList)->real, \ 253 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 254 255 #define listHead(pList) \ 256 CONT_CAST_ELEM(pList, listHead_IMPL(&((pList)->real).base), listIsValid_IMPL) 257 258 #define listTail(pList) \ 259 CONT_CAST_ELEM(pList, listTail_IMPL(&((pList)->real).base), listIsValid_IMPL) 260 261 #define listNext(pList, pValue) \ 262 CONT_CAST_ELEM(pList, \ 263 listNext_IMPL(&((pList)->real).base, \ 264 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 265 266 #define listPrev(pList, pValue) \ 267 CONT_CAST_ELEM(pList, \ 268 listPrev_IMPL(&((pList)->real).base, \ 269 CONT_CHECK_ARG(pList, pValue)), listIsValid_IMPL) 270 271 #define listIterAll(pList) \ 272 listIterRange(pList, listHead(pList), listTail(pList)) 273 274 #define listIterRange(pList, pFirst, pLast) \ 275 CONT_ITER_RANGE(pList, &listIterRange_IMPL, \ 276 CONT_CHECK_ARG(pList, pFirst), CONT_CHECK_ARG(pList, pLast), listIsValid_IMPL) 277 278 #define listIterNext(pIt) \ 279 listIterNext_IMPL(&((pIt)->iter)) 280 281 void listInit_IMPL(NonIntrusiveList *pList, PORT_MEM_ALLOCATOR *pAllocator, 282 NvU32 valueSize); 283 void listInitIntrusive_IMPL(IntrusiveList *pList, NvS32 nodeOffset); 284 void listDestroy_IMPL(NonIntrusiveList *pList); 285 void listDestroyIntrusive_IMPL(ListBase *pList); 286 287 NvU32 listCount_IMPL(ListBase *pList); 288 void *listInsertNew_IMPL(NonIntrusiveList *pList, void *pNext); 289 void *listAppendNew_IMPL(NonIntrusiveList *pList); 290 void *listPrependNew_IMPL(NonIntrusiveList *pList); 291 void *listInsertValue_IMPL(NonIntrusiveList *pList, 292 void *pNext, 293 const void *pValue); 294 void *listAppendValue_IMPL(NonIntrusiveList *pList, const void *pValue); 295 void *listPrependValue_IMPL(NonIntrusiveList *pList, const void *pValue); 296 void listInsertExisting_IMPL(IntrusiveList *pList, void *pNext, void *pValue); 297 void listAppendExisting_IMPL(IntrusiveList *pList, void *pValue); 298 void listPrependExisting_IMPL(IntrusiveList *pList, void *pValue); 299 void listRemove_IMPL(NonIntrusiveList *pList, void *pValue); 300 void listRemoveIntrusive_IMPL(ListBase *pList, void *pValue); 301 void listRemoveFirstByValue_IMPL(NonIntrusiveList *pList, void *pValue); 302 void listRemoveAllByValue_IMPL(NonIntrusiveList *pList, void *pValue); 303 304 void *listFindByValue_IMPL(NonIntrusiveList *pList, void *pValue); 305 void *listHead_IMPL(ListBase *pList); 306 void *listTail_IMPL(ListBase *pList); 307 void *listNext_IMPL(ListBase *pList, void *pValue); 308 void *listPrev_IMPL(ListBase *pList, void *pValue); 309 310 ListIterBase listIterAll_IMPL(ListBase *pList); 311 ListIterBase listIterRange_IMPL(ListBase *pList, void *pFirst, void *pLast); 312 NvBool listIterNext_IMPL(ListIterBase *pIt); 313 314 static NV_FORCEINLINE ListNode * 315 listValueToNode(ListBase *pList, void *pValue) 316 { 317 if (NULL == pList) return NULL; 318 if (NULL == pValue) return NULL; 319 return (ListNode*)((NvU8*)pValue + pList->nodeOffset); 320 } 321 322 static NV_FORCEINLINE void * 323 listNodeToValue(ListBase *pList, ListNode *pNode) 324 { 325 if (NULL == pList) return NULL; 326 if (NULL == pNode) return NULL; 327 return (NvU8*)pNode - pList->nodeOffset; 328 } 329 330 NvBool listIsValid_IMPL(void *pMap); 331 332 #ifdef __cplusplus 333 } 334 #endif 335 336 #endif // _NV_CONTAINERS_LIST_H_ 337