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_VECTOR_H 24 #define NV_CONTAINERS_VECTOR_H 1 25 26 #include "containers/type_safety.h" 27 #include "nvtypes.h" 28 #include "nvmisc.h" 29 #include "nvport/nvport.h" 30 #include "utils/nvassert.h" 31 32 #ifdef __cplusplus 33 extern "C" { 34 #endif 35 36 /** 37 * @defgroup NV_CONTAINERS_VECTOR Vector 38 * 39 * @brief Sequence of user-defined values. 40 * 41 * @details Order of values is not necessarily increasing or sorted, but order is 42 * preserved across mutation. Please see 43 * https://en.wikipedia.org/wiki/Sequence for a formal definition. 44 * 45 * - Time Complexity: 46 * * Operations are \b O(1), 47 * * Unless stated otherwise. 48 * 49 * - Memory Usage: 50 * * \b O(N) memory is required for N values. 51 * * See @ref mem-ownership for further details. 52 * 53 * - Synchronization: 54 * * \b None. The container is not thread-safe. 55 * * Locking must be handled by the user if required. 56 * 57 */ 58 59 #define MAKE_VECTOR(vectTypeName, dataType) \ 60 typedef union vectTypeName##Iter \ 61 { \ 62 dataType *pValue; \ 63 VectorIterBase iter; \ 64 } vectTypeName##Iter; \ 65 typedef union vectTypeName \ 66 { \ 67 VectorWrapper real; \ 68 CONT_TAG_TYPE(Vector, dataType, vectTypeName##Iter); \ 69 CONT_TAG_NON_INTRUSIVE(dataType); \ 70 } vectTypeName 71 72 #define DECLARE_VECTOR(vectTypeName) \ 73 typedef union vectTypeName##Iter vectTypeName##Iter; \ 74 typedef union vectTypeName vectTypeName 75 76 typedef struct Vector Vector; 77 typedef struct VectorIterBase VectorIterBase; 78 typedef struct VectorWrapper VectorWrapper; 79 80 /** 81 * Note that the vector values are NvU32 and Iterator values are NvS32, 82 * so in case there is a need for a vector with over ~2 billion entries 83 * this might not work. 84 */ 85 struct VectorIterBase 86 { 87 void *pValue; 88 Vector *pVector; 89 NvS32 nextIndex; 90 NvS32 prevIndex; 91 NvS32 firstIndex; 92 NvS32 lastIndex; 93 NvBool bForward; 94 #if PORT_IS_CHECKED_BUILD 95 NvU32 versionNumber; 96 #endif 97 }; 98 99 VectorIterBase vectIterRange_IMPL(Vector *pVector, void *pFirst, void *pLast); 100 CONT_VTABLE_DECL(Vector, VectorIterBase); 101 102 struct Vector 103 { 104 CONT_VTABLE_FIELD(Vector); 105 void *pHead; 106 PORT_MEM_ALLOCATOR *pAllocator; 107 NvU32 valueSize; 108 NvU32 capacity; 109 NvU32 size; 110 #if PORT_IS_CHECKED_BUILD 111 NvU32 versionNumber; 112 #endif 113 }; 114 115 struct VectorWrapper 116 { 117 Vector base; 118 }; 119 120 #define vectInit(pVector, pAllocator, capacity) \ 121 vectInit_IMPL(&((pVector)->real.base), \ 122 pAllocator, \ 123 capacity, \ 124 sizeof(*(pVector)->valueSize)) 125 #define vectDestroy(pVector) vectDestroy_IMPL(&((pVector)->real.base)) 126 #define vectCount(pVector) vectCount_IMPL(&((pVector)->real.base)) 127 #define vectCapacity(pVector) vectCapacity_IMPL(&((pVector)->real.base)) 128 #define vectIsEmpty(pVector) vectIsEmpty_IMPL(&((pVector)->real.base)) 129 #define vectAt(pVector, index) \ 130 CONT_CAST_ELEM((pVector), \ 131 vectAt_IMPL(&((pVector)->real.base), index), \ 132 vectIsValid_IMPL) 133 #define vectInsert(pVector, index, pValue) \ 134 CONT_CAST_ELEM((pVector), \ 135 vectInsert_IMPL(&(pVector)->real.base, \ 136 index, \ 137 CONT_CHECK_ARG(pVector, pValue)), \ 138 vectIsValid_IMPL) 139 #define vectRemove(pVector, index) \ 140 vectRemove_IMPL(&((pVector)->real.base), index) 141 #define vectClear(pVector) vectDestroy(pVector) 142 #define vectAppend(pVector, pValue) \ 143 CONT_CAST_ELEM((pVector), \ 144 vectAppend_IMPL(&(pVector)->real.base, \ 145 CONT_CHECK_ARG(pVector, pValue)), \ 146 vectIsValid_IMPL) 147 #define vectPrepend(pVector, pValue) \ 148 CONT_CAST_ELEM((pVector), \ 149 vectPrepend_IMPL(&(pVector)->real.base, \ 150 CONT_CHECK_ARG(pVector, pValue)), \ 151 vectIsValid_IMPL) 152 #define vectReserve(pVector, size) \ 153 vectReserve_IMPL(&((pVector)->real.base), size) 154 #define vectTrim(pVector, size) vectTrim_IMPL(&((pVector)->real.base), size) 155 156 #define vectIterAll(pVector) \ 157 vectIterRangeIndex(pVector, 0, vectCount(pVector) - 1) 158 #define vectIterRangeIndex(pVector, firstIndex, lastIndex) \ 159 vectIterRange(pVector, \ 160 vectAt(pVector, firstIndex), \ 161 vectAt(pVector, lastIndex)) 162 #define vectIterRange(pVector, pFirst, pLast) \ 163 CONT_ITER_RANGE(pVector, \ 164 &vectIterRange_IMPL, \ 165 CONT_CHECK_ARG(pVector, pFirst), \ 166 CONT_CHECK_ARG(pVector, pLast), \ 167 vectIsValid_IMPL) 168 #define vectIterNext(pIterator) \ 169 vectIterNext_IMPL(&((pIterator)->iter), (void **)&(pIterator)->pValue) 170 #define vectIterPrev(pIterator) \ 171 vectIterPrev_IMPL(&((pIterator)->iter), (void **)&(pIterator)->pValue) 172 173 NV_STATUS vectInit_IMPL(Vector *pVector, 174 PORT_MEM_ALLOCATOR *pAllocator, 175 NvU32 capacity, 176 NvU32 valueSize); 177 void vectDestroy_IMPL(Vector *pVector); 178 NvU32 vectCount_IMPL(Vector *pVector); 179 NvU32 vectCapacity_IMPL(Vector *pVector); 180 NvBool vectIsEmpty_IMPL(Vector *pVector); 181 182 void *vectAt_IMPL(Vector *pVector, NvU32 index); 183 void *vectInsert_IMPL(Vector *pVector, NvU32 index, const void *pData); 184 void vectRemove_IMPL(Vector *pVector, NvU32 index); 185 void *vectAppend_IMPL(Vector *pVector, const void *pData); 186 void *vectPrepend_IMPL(Vector *pvector, const void *pData); 187 188 NV_STATUS vectReserve_IMPL(Vector *pVector, NvU32 n); 189 NV_STATUS vectTrim_IMPL(Vector *pvector, NvU32 n); 190 191 VectorIterBase vectIterRange_IMPL(Vector *pVector, void *pFirst, void *pLast); 192 NvBool vectIterNext_IMPL(VectorIterBase *pIter, void **ppValue); 193 NvBool vectIterPrev_IMPL(VectorIterBase *pIter, void **ppValue); 194 195 NvBool vectIsValid_IMPL(void *pVect); 196 197 #ifdef __cplusplus 198 } 199 #endif 200 201 #endif // NV_CONTAINERS_VECTOR_H 202