1 /* 2 * Copyright 2010-2019 Branimir Karadzic. All rights reserved. 3 * License: https://github.com/bkaradzic/bx#license-bsd-2-clause 4 */ 5 6 #ifndef BX_HANDLE_ALLOC_H_HEADER_GUARD 7 #define BX_HANDLE_ALLOC_H_HEADER_GUARD 8 9 #include "bx.h" 10 #include "allocator.h" 11 #include "uint32_t.h" 12 13 namespace bx 14 { 15 static const uint16_t kInvalidHandle = UINT16_MAX; 16 17 /// 18 class HandleAlloc 19 { 20 public: 21 /// 22 HandleAlloc(uint16_t _maxHandles); 23 24 /// 25 ~HandleAlloc(); 26 27 /// 28 const uint16_t* getHandles() const; 29 30 /// 31 uint16_t getHandleAt(uint16_t _at) const; 32 33 /// 34 uint16_t getNumHandles() const; 35 36 /// 37 uint16_t getMaxHandles() const; 38 39 /// 40 uint16_t alloc(); 41 42 /// 43 bool isValid(uint16_t _handle) const; 44 45 /// 46 void free(uint16_t _handle); 47 48 /// 49 void reset(); 50 51 private: 52 HandleAlloc(); 53 54 /// 55 uint16_t* getDensePtr() const; 56 57 /// 58 uint16_t* getSparsePtr() const; 59 60 uint16_t m_numHandles; 61 uint16_t m_maxHandles; 62 }; 63 64 /// 65 HandleAlloc* createHandleAlloc(AllocatorI* _allocator, uint16_t _maxHandles); 66 67 /// 68 void destroyHandleAlloc(AllocatorI* _allocator, HandleAlloc* _handleAlloc); 69 70 /// 71 template <uint16_t MaxHandlesT> 72 class HandleAllocT : public HandleAlloc 73 { 74 public: 75 /// 76 HandleAllocT(); 77 78 /// 79 ~HandleAllocT(); 80 81 private: 82 uint16_t m_padding[2*MaxHandlesT]; 83 }; 84 85 /// 86 template <uint16_t MaxHandlesT> 87 class HandleListT 88 { 89 public: 90 /// 91 HandleListT(); 92 93 /// 94 void pushBack(uint16_t _handle); 95 96 /// 97 uint16_t popBack(); 98 99 /// 100 void pushFront(uint16_t _handle); 101 102 /// 103 uint16_t popFront(); 104 105 /// 106 uint16_t getFront() const; 107 108 /// 109 uint16_t getBack() const; 110 111 /// 112 uint16_t getNext(uint16_t _handle) const; 113 114 /// 115 uint16_t getPrev(uint16_t _handle) const; 116 117 /// 118 void remove(uint16_t _handle); 119 120 /// 121 void reset(); 122 123 private: 124 /// 125 void insertBefore(uint16_t _before, uint16_t _handle); 126 127 /// 128 void insertAfter(uint16_t _after, uint16_t _handle); 129 130 /// 131 bool isValid(uint16_t _handle) const; 132 133 /// 134 void updateFrontBack(uint16_t _handle); 135 136 uint16_t m_front; 137 uint16_t m_back; 138 139 struct Link 140 { 141 uint16_t m_prev; 142 uint16_t m_next; 143 }; 144 145 Link m_links[MaxHandlesT]; 146 }; 147 148 /// 149 template <uint16_t MaxHandlesT> 150 class HandleAllocLruT 151 { 152 public: 153 /// 154 HandleAllocLruT(); 155 156 /// 157 ~HandleAllocLruT(); 158 159 /// 160 const uint16_t* getHandles() const; 161 162 /// 163 uint16_t getHandleAt(uint16_t _at) const; 164 165 /// 166 uint16_t getNumHandles() const; 167 168 /// 169 uint16_t getMaxHandles() const; 170 171 /// 172 uint16_t alloc(); 173 174 /// 175 bool isValid(uint16_t _handle) const; 176 177 /// 178 void free(uint16_t _handle); 179 180 /// 181 void touch(uint16_t _handle); 182 183 /// 184 uint16_t getFront() const; 185 186 /// 187 uint16_t getBack() const; 188 189 /// 190 uint16_t getNext(uint16_t _handle) const; 191 192 /// 193 uint16_t getPrev(uint16_t _handle) const; 194 195 /// 196 void reset(); 197 198 private: 199 HandleListT<MaxHandlesT> m_list; 200 HandleAllocT<MaxHandlesT> m_alloc; 201 }; 202 203 /// 204 template <uint32_t MaxCapacityT, typename KeyT = uint32_t> 205 class HandleHashMapT 206 { 207 public: 208 /// 209 HandleHashMapT(); 210 211 /// 212 ~HandleHashMapT(); 213 214 /// 215 bool insert(KeyT _key, uint16_t _handle); 216 217 /// 218 bool removeByKey(KeyT _key); 219 220 /// 221 bool removeByHandle(uint16_t _handle); 222 223 /// 224 uint16_t find(KeyT _key) const; 225 226 /// 227 void reset(); 228 229 /// 230 uint32_t getNumElements() const; 231 232 /// 233 uint32_t getMaxCapacity() const; 234 235 /// 236 struct Iterator 237 { 238 uint16_t handle; 239 240 private: 241 friend class HandleHashMapT<MaxCapacityT, KeyT>; 242 uint32_t pos; 243 uint32_t num; 244 }; 245 246 /// 247 Iterator first() const; 248 249 /// 250 bool next(Iterator& _it) const; 251 252 private: 253 /// 254 uint32_t findIndex(KeyT _key) const; 255 256 /// 257 void removeIndex(uint32_t _idx); 258 259 /// 260 uint32_t mix(uint32_t _x) const; 261 262 /// 263 uint64_t mix(uint64_t _x) const; 264 265 uint32_t m_maxCapacity; 266 uint32_t m_numElements; 267 268 KeyT m_key[MaxCapacityT]; 269 uint16_t m_handle[MaxCapacityT]; 270 }; 271 272 /// 273 template <uint16_t MaxHandlesT, typename KeyT = uint32_t> 274 class HandleHashMapAllocT 275 { 276 public: 277 /// 278 HandleHashMapAllocT(); 279 280 /// 281 ~HandleHashMapAllocT(); 282 283 /// 284 uint16_t alloc(KeyT _key); 285 286 /// 287 void free(KeyT _key); 288 289 /// 290 void free(uint16_t _handle); 291 292 /// 293 uint16_t find(KeyT _key) const; 294 295 /// 296 const uint16_t* getHandles() const; 297 298 /// 299 uint16_t getHandleAt(uint16_t _at) const; 300 301 /// 302 uint16_t getNumHandles() const; 303 304 /// 305 uint16_t getMaxHandles() const; 306 307 /// 308 bool isValid(uint16_t _handle) const; 309 310 /// 311 void reset(); 312 313 private: 314 HandleHashMapT<MaxHandlesT+MaxHandlesT/2, KeyT> m_table; 315 HandleAllocT<MaxHandlesT> m_alloc; 316 }; 317 318 } // namespace bx 319 320 #include "inline/handlealloc.inl" 321 322 #endif // BX_HANDLE_ALLOC_H_HEADER_GUARD 323