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 NvBool bValid; 97 #endif 98 }; 99 100 VectorIterBase vectIterRange_IMPL(Vector *pVector, void *pFirst, void *pLast); 101 CONT_VTABLE_DECL(Vector, VectorIterBase); 102 103 struct Vector 104 { 105 CONT_VTABLE_FIELD(Vector); 106 void *pHead; 107 PORT_MEM_ALLOCATOR *pAllocator; 108 NvU32 valueSize; 109 NvU32 capacity; 110 NvU32 size; 111 #if PORT_IS_CHECKED_BUILD 112 NvU32 versionNumber; 113 #endif 114 }; 115 116 struct VectorWrapper 117 { 118 Vector base; 119 }; 120 121 #define vectInit(pVector, pAllocator, capacity) \ 122 vectInit_IMPL(&((pVector)->real.base), \ 123 pAllocator, \ 124 capacity, \ 125 sizeof(*(pVector)->valueSize)) 126 #define vectDestroy(pVector) vectDestroy_IMPL(&((pVector)->real.base)) 127 #define vectClear(pVector) vectClear_IMPL(&((pVector)->real.base)) 128 #define vectCount(pVector) vectCount_IMPL(&((pVector)->real.base)) 129 #define vectCapacity(pVector) vectCapacity_IMPL(&((pVector)->real.base)) 130 #define vectIsEmpty(pVector) vectIsEmpty_IMPL(&((pVector)->real.base)) 131 #define vectAt(pVector, index) \ 132 CONT_CAST_ELEM((pVector), \ 133 vectAt_IMPL(&((pVector)->real.base), index), \ 134 vectIsValid_IMPL) 135 #define vectInsert(pVector, index, pValue) \ 136 CONT_CAST_ELEM((pVector), \ 137 vectInsert_IMPL(&(pVector)->real.base, \ 138 index, \ 139 CONT_CHECK_ARG(pVector, pValue)), \ 140 vectIsValid_IMPL) 141 #define vectRemove(pVector, index) \ 142 vectRemove_IMPL(&((pVector)->real.base), index) 143 #define vectAppend(pVector, pValue) \ 144 CONT_CAST_ELEM((pVector), \ 145 vectAppend_IMPL(&(pVector)->real.base, \ 146 CONT_CHECK_ARG(pVector, pValue)), \ 147 vectIsValid_IMPL) 148 #define vectPrepend(pVector, pValue) \ 149 CONT_CAST_ELEM((pVector), \ 150 vectPrepend_IMPL(&(pVector)->real.base, \ 151 CONT_CHECK_ARG(pVector, pValue)), \ 152 vectIsValid_IMPL) 153 #define vectReserve(pVector, size) \ 154 vectReserve_IMPL(&((pVector)->real.base), size) 155 #define vectTrim(pVector, size) vectTrim_IMPL(&((pVector)->real.base), size) 156 157 #define vectIterAll(pVector) \ 158 vectIterRangeIndex(pVector, 0, vectCount(pVector) - 1) 159 #define vectIterRangeIndex(pVector, firstIndex, lastIndex) \ 160 vectIterRange(pVector, \ 161 vectAt(pVector, firstIndex), \ 162 vectAt(pVector, lastIndex)) 163 #define vectIterRange(pVector, pFirst, pLast) \ 164 CONT_ITER_RANGE(pVector, \ 165 &vectIterRange_IMPL, \ 166 CONT_CHECK_ARG(pVector, pFirst), \ 167 CONT_CHECK_ARG(pVector, pLast), \ 168 vectIsValid_IMPL) 169 #define vectIterNext(pIterator) \ 170 vectIterNext_IMPL(&((pIterator)->iter), (void **)&(pIterator)->pValue) 171 #define vectIterPrev(pIterator) \ 172 vectIterPrev_IMPL(&((pIterator)->iter), (void **)&(pIterator)->pValue) 173 174 NV_STATUS vectInit_IMPL(Vector *pVector, 175 PORT_MEM_ALLOCATOR *pAllocator, 176 NvU32 capacity, 177 NvU32 valueSize); 178 void vectDestroy_IMPL(Vector *pVector); 179 void vectClear_IMPL(Vector *pVector); 180 NvU32 vectCount_IMPL(Vector *pVector); 181 NvU32 vectCapacity_IMPL(Vector *pVector); 182 NvBool vectIsEmpty_IMPL(Vector *pVector); 183 184 void *vectAt_IMPL(Vector *pVector, NvU32 index); 185 void *vectInsert_IMPL(Vector *pVector, NvU32 index, const void *pData); 186 void vectRemove_IMPL(Vector *pVector, NvU32 index); 187 void *vectAppend_IMPL(Vector *pVector, const void *pData); 188 void *vectPrepend_IMPL(Vector *pvector, const void *pData); 189 190 NV_STATUS vectReserve_IMPL(Vector *pVector, NvU32 n); 191 NV_STATUS vectTrim_IMPL(Vector *pvector, NvU32 n); 192 193 VectorIterBase vectIterRange_IMPL(Vector *pVector, void *pFirst, void *pLast); 194 NvBool vectIterNext_IMPL(VectorIterBase *pIter, void **ppValue); 195 NvBool vectIterPrev_IMPL(VectorIterBase *pIter, void **ppValue); 196 197 NvBool vectIsValid_IMPL(void *pVect); 198 199 #ifdef __cplusplus 200 } 201 #endif 202 203 #endif // NV_CONTAINERS_VECTOR_H 204