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