summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bx/include/bx/inline/handlealloc.inl
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bx/include/bx/inline/handlealloc.inl')
-rw-r--r--3rdparty/bx/include/bx/inline/handlealloc.inl708
1 files changed, 708 insertions, 0 deletions
diff --git a/3rdparty/bx/include/bx/inline/handlealloc.inl b/3rdparty/bx/include/bx/inline/handlealloc.inl
new file mode 100644
index 00000000000..8738c3d7038
--- /dev/null
+++ b/3rdparty/bx/include/bx/inline/handlealloc.inl
@@ -0,0 +1,708 @@
+/*
+ * Copyright 2010-2017 Branimir Karadzic. All rights reserved.
+ * License: https://github.com/bkaradzic/bx#license-bsd-2-clause
+ */
+
+#ifndef BX_HANDLE_ALLOC_H_HEADER_GUARD
+# error "Must be included from bx/handlealloc.h!"
+#endif // BX_HANDLE_ALLOC_H_HEADER_GUARD
+
+namespace bx
+{
+ inline HandleAlloc::HandleAlloc(uint16_t _maxHandles)
+ : m_numHandles(0)
+ , m_maxHandles(_maxHandles)
+ {
+ reset();
+ }
+
+ inline HandleAlloc::~HandleAlloc()
+ {
+ }
+
+ inline const uint16_t* HandleAlloc::getHandles() const
+ {
+ return getDensePtr();
+ }
+
+ inline uint16_t HandleAlloc::getHandleAt(uint16_t _at) const
+ {
+ return getDensePtr()[_at];
+ }
+
+ inline uint16_t HandleAlloc::getNumHandles() const
+ {
+ return m_numHandles;
+ }
+
+ inline uint16_t HandleAlloc::getMaxHandles() const
+ {
+ return m_maxHandles;
+ }
+
+ inline uint16_t HandleAlloc::alloc()
+ {
+ if (m_numHandles < m_maxHandles)
+ {
+ uint16_t index = m_numHandles;
+ ++m_numHandles;
+
+ uint16_t* dense = getDensePtr();
+ uint16_t handle = dense[index];
+ uint16_t* sparse = getSparsePtr();
+ sparse[handle] = index;
+ return handle;
+ }
+
+ return invalid;
+ }
+
+ inline bool HandleAlloc::isValid(uint16_t _handle) const
+ {
+ uint16_t* dense = getDensePtr();
+ uint16_t* sparse = getSparsePtr();
+ uint16_t index = sparse[_handle];
+
+ return index < m_numHandles
+ && dense[index] == _handle
+ ;
+ }
+
+ inline void HandleAlloc::free(uint16_t _handle)
+ {
+ uint16_t* dense = getDensePtr();
+ uint16_t* sparse = getSparsePtr();
+ uint16_t index = sparse[_handle];
+ --m_numHandles;
+ uint16_t temp = dense[m_numHandles];
+ dense[m_numHandles] = _handle;
+ sparse[temp] = index;
+ dense[index] = temp;
+ }
+
+ inline void HandleAlloc::reset()
+ {
+ m_numHandles = 0;
+ uint16_t* dense = getDensePtr();
+ for (uint16_t ii = 0, num = m_maxHandles; ii < num; ++ii)
+ {
+ dense[ii] = ii;
+ }
+ }
+
+ inline uint16_t* HandleAlloc::getDensePtr() const
+ {
+ uint8_t* ptr = (uint8_t*)reinterpret_cast<const uint8_t*>(this);
+ return (uint16_t*)&ptr[sizeof(HandleAlloc)];
+ }
+
+ inline uint16_t* HandleAlloc::getSparsePtr() const
+ {
+ return &getDensePtr()[m_maxHandles];
+ }
+
+ inline HandleAlloc* createHandleAlloc(AllocatorI* _allocator, uint16_t _maxHandles)
+ {
+ uint8_t* ptr = (uint8_t*)BX_ALLOC(_allocator, sizeof(HandleAlloc) + 2*_maxHandles*sizeof(uint16_t) );
+ return ::new (ptr) HandleAlloc(_maxHandles);
+ }
+
+ inline void destroyHandleAlloc(AllocatorI* _allocator, HandleAlloc* _handleAlloc)
+ {
+ _handleAlloc->~HandleAlloc();
+ BX_FREE(_allocator, _handleAlloc);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline HandleAllocT<MaxHandlesT>::HandleAllocT()
+ : HandleAlloc(MaxHandlesT)
+ {
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline HandleAllocT<MaxHandlesT>::~HandleAllocT()
+ {
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline HandleListT<MaxHandlesT>::HandleListT()
+ {
+ reset();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::pushBack(uint16_t _handle)
+ {
+ insertAfter(m_back, _handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::popBack()
+ {
+ uint16_t last = invalid != m_back
+ ? m_back
+ : m_front
+ ;
+
+ if (invalid != last)
+ {
+ remove(last);
+ }
+
+ return last;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::pushFront(uint16_t _handle)
+ {
+ insertBefore(m_front, _handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::popFront()
+ {
+ uint16_t front = m_front;
+
+ if (invalid != front)
+ {
+ remove(front);
+ }
+
+ return front;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::getFront() const
+ {
+ return m_front;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::getBack() const
+ {
+ return m_back;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::getNext(uint16_t _handle) const
+ {
+ BX_CHECK(isValid(_handle), "Invalid handle %d!", _handle);
+ const Link& curr = m_links[_handle];
+ return curr.m_next;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleListT<MaxHandlesT>::getPrev(uint16_t _handle) const
+ {
+ BX_CHECK(isValid(_handle), "Invalid handle %d!", _handle);
+ const Link& curr = m_links[_handle];
+ return curr.m_prev;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::remove(uint16_t _handle)
+ {
+ BX_CHECK(isValid(_handle), "Invalid handle %d!", _handle);
+ Link& curr = m_links[_handle];
+
+ if (invalid != curr.m_prev)
+ {
+ Link& prev = m_links[curr.m_prev];
+ prev.m_next = curr.m_next;
+ }
+ else
+ {
+ m_front = curr.m_next;
+ }
+
+ if (invalid != curr.m_next)
+ {
+ Link& next = m_links[curr.m_next];
+ next.m_prev = curr.m_prev;
+ }
+ else
+ {
+ m_back = curr.m_prev;
+ }
+
+ curr.m_prev = invalid;
+ curr.m_next = invalid;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::reset()
+ {
+ memSet(m_links, 0xff, sizeof(m_links) );
+ m_front = invalid;
+ m_back = invalid;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::insertBefore(uint16_t _before, uint16_t _handle)
+ {
+ Link& curr = m_links[_handle];
+ curr.m_next = _before;
+
+ if (invalid != _before)
+ {
+ Link& link = m_links[_before];
+ if (invalid != link.m_prev)
+ {
+ Link& prev = m_links[link.m_prev];
+ prev.m_next = _handle;
+ }
+
+ curr.m_prev = link.m_prev;
+ link.m_prev = _handle;
+ }
+
+ updateFrontBack(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::insertAfter(uint16_t _after, uint16_t _handle)
+ {
+ Link& curr = m_links[_handle];
+ curr.m_prev = _after;
+
+ if (invalid != _after)
+ {
+ Link& link = m_links[_after];
+ if (invalid != link.m_next)
+ {
+ Link& next = m_links[link.m_next];
+ next.m_prev = _handle;
+ }
+
+ curr.m_next = link.m_next;
+ link.m_next = _handle;
+ }
+
+ updateFrontBack(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline bool HandleListT<MaxHandlesT>::isValid(uint16_t _handle) const
+ {
+ return _handle < MaxHandlesT;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleListT<MaxHandlesT>::updateFrontBack(uint16_t _handle)
+ {
+ Link& curr = m_links[_handle];
+
+ if (invalid == curr.m_prev)
+ {
+ m_front = _handle;
+ }
+
+ if (invalid == curr.m_next)
+ {
+ m_back = _handle;
+ }
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline HandleAllocLruT<MaxHandlesT>::HandleAllocLruT()
+ {
+ reset();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline HandleAllocLruT<MaxHandlesT>::~HandleAllocLruT()
+ {
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline const uint16_t* HandleAllocLruT<MaxHandlesT>::getHandles() const
+ {
+ return m_alloc.getHandles();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getHandleAt(uint16_t _at) const
+ {
+ return m_alloc.getHandleAt(_at);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getNumHandles() const
+ {
+ return m_alloc.getNumHandles();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getMaxHandles() const
+ {
+ return m_alloc.getMaxHandles();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::alloc()
+ {
+ uint16_t handle = m_alloc.alloc();
+ if (invalid != handle)
+ {
+ m_list.pushFront(handle);
+ }
+ return handle;
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline bool HandleAllocLruT<MaxHandlesT>::isValid(uint16_t _handle) const
+ {
+ return m_alloc.isValid(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleAllocLruT<MaxHandlesT>::free(uint16_t _handle)
+ {
+ BX_CHECK(isValid(_handle), "Invalid handle %d!", _handle);
+ m_list.remove(_handle);
+ m_alloc.free(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleAllocLruT<MaxHandlesT>::touch(uint16_t _handle)
+ {
+ BX_CHECK(isValid(_handle), "Invalid handle %d!", _handle);
+ m_list.remove(_handle);
+ m_list.pushFront(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getFront() const
+ {
+ return m_list.getFront();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getBack() const
+ {
+ return m_list.getBack();
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getNext(uint16_t _handle) const
+ {
+ return m_list.getNext(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline uint16_t HandleAllocLruT<MaxHandlesT>::getPrev(uint16_t _handle) const
+ {
+ return m_list.getPrev(_handle);
+ }
+
+ template <uint16_t MaxHandlesT>
+ inline void HandleAllocLruT<MaxHandlesT>::reset()
+ {
+ m_list.reset();
+ m_alloc.reset();
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline HandleHashMapT<MaxCapacityT, KeyT>::HandleHashMapT()
+ : m_maxCapacity(MaxCapacityT)
+ {
+ reset();
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline HandleHashMapT<MaxCapacityT, KeyT>::~HandleHashMapT()
+ {
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline bool HandleHashMapT<MaxCapacityT, KeyT>::insert(KeyT _key, uint16_t _handle)
+ {
+ if (invalid == _handle)
+ {
+ return false;
+ }
+
+ const KeyT hash = mix(_key);
+ const uint32_t firstIdx = hash % MaxCapacityT;
+ uint32_t idx = firstIdx;
+ do
+ {
+ if (m_handle[idx] == invalid)
+ {
+ m_key[idx] = _key;
+ m_handle[idx] = _handle;
+ ++m_numElements;
+ return true;
+ }
+
+ if (m_key[idx] == _key)
+ {
+ return false;
+ }
+
+ idx = (idx + 1) % MaxCapacityT;
+
+ } while (idx != firstIdx);
+
+ return false;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline bool HandleHashMapT<MaxCapacityT, KeyT>::removeByKey(KeyT _key)
+ {
+ uint32_t idx = findIndex(_key);
+ if (UINT32_MAX != idx)
+ {
+ removeIndex(idx);
+ return true;
+ }
+
+ return false;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline bool HandleHashMapT<MaxCapacityT, KeyT>::removeByHandle(uint16_t _handle)
+ {
+ if (invalid != _handle)
+ {
+ for (uint32_t idx = 0; idx < MaxCapacityT; ++idx)
+ {
+ if (m_handle[idx] == _handle)
+ {
+ removeIndex(idx);
+ }
+ }
+ }
+
+ return false;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint16_t HandleHashMapT<MaxCapacityT, KeyT>::find(KeyT _key) const
+ {
+ uint32_t idx = findIndex(_key);
+ if (UINT32_MAX != idx)
+ {
+ return m_handle[idx];
+ }
+
+ return invalid;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline void HandleHashMapT<MaxCapacityT, KeyT>::reset()
+ {
+ memSet(m_handle, 0xff, sizeof(m_handle) );
+ m_numElements = 0;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint32_t HandleHashMapT<MaxCapacityT, KeyT>::getNumElements() const
+ {
+ return m_numElements;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint32_t HandleHashMapT<MaxCapacityT, KeyT>::getMaxCapacity() const
+ {
+ return m_maxCapacity;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline typename HandleHashMapT<MaxCapacityT, KeyT>::Iterator HandleHashMapT<MaxCapacityT, KeyT>::first() const
+ {
+ Iterator it;
+ it.handle = invalid;
+ it.pos = 0;
+ it.num = m_numElements;
+
+ if (0 == it.num)
+ {
+ return it;
+ }
+
+ ++it.num;
+ next(it);
+ return it;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline bool HandleHashMapT<MaxCapacityT, KeyT>::next(Iterator& _it) const
+ {
+ if (0 == _it.num)
+ {
+ return false;
+ }
+
+ for (
+ ;_it.pos < MaxCapacityT && invalid == m_handle[_it.pos]
+ ; ++_it.pos
+ );
+ _it.handle = m_handle[_it.pos];
+ ++_it.pos;
+ --_it.num;
+ return true;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint32_t HandleHashMapT<MaxCapacityT, KeyT>::findIndex(KeyT _key) const
+ {
+ const KeyT hash = mix(_key);
+
+ const uint32_t firstIdx = hash % MaxCapacityT;
+ uint32_t idx = firstIdx;
+ do
+ {
+ if (m_handle[idx] == invalid)
+ {
+ return UINT32_MAX;
+ }
+
+ if (m_key[idx] == _key)
+ {
+ return idx;
+ }
+
+ idx = (idx + 1) % MaxCapacityT;
+
+ } while (idx != firstIdx);
+
+ return UINT32_MAX;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline void HandleHashMapT<MaxCapacityT, KeyT>::removeIndex(uint32_t _idx)
+ {
+ m_handle[_idx] = invalid;
+ --m_numElements;
+
+ for (uint32_t idx = (_idx + 1) % MaxCapacityT
+ ; m_handle[idx] != invalid
+ ; idx = (idx + 1) % MaxCapacityT)
+ {
+ if (m_handle[idx] != invalid)
+ {
+ const KeyT key = m_key[idx];
+ if (idx != findIndex(key) )
+ {
+ const uint16_t handle = m_handle[idx];
+ m_handle[idx] = invalid;
+ --m_numElements;
+ insert(key, handle);
+ }
+ }
+ }
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint32_t HandleHashMapT<MaxCapacityT, KeyT>::mix(uint32_t _x) const
+ {
+ const uint32_t tmp0 = uint32_mul(_x, UINT32_C(2246822519) );
+ const uint32_t tmp1 = uint32_rol(tmp0, 13);
+ const uint32_t result = uint32_mul(tmp1, UINT32_C(2654435761) );
+ return result;
+ }
+
+ template <uint32_t MaxCapacityT, typename KeyT>
+ inline uint64_t HandleHashMapT<MaxCapacityT, KeyT>::mix(uint64_t _x) const
+ {
+ const uint64_t tmp0 = uint64_mul(_x, UINT64_C(14029467366897019727) );
+ const uint64_t tmp1 = uint64_rol(tmp0, 31);
+ const uint64_t result = uint64_mul(tmp1, UINT64_C(11400714785074694791) );
+ return result;
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline HandleHashMapAllocT<MaxHandlesT, KeyT>::HandleHashMapAllocT()
+ {
+ reset();
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline HandleHashMapAllocT<MaxHandlesT, KeyT>::~HandleHashMapAllocT()
+ {
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline uint16_t HandleHashMapAllocT<MaxHandlesT, KeyT>::alloc(KeyT _key)
+ {
+ uint16_t handle = m_alloc.alloc();
+ if (invalid == handle)
+ {
+ return invalid;
+ }
+
+ bool ok = m_table.insert(_key, handle);
+ if (!ok)
+ {
+ m_alloc.free(handle);
+ return invalid;
+ }
+
+ return handle;
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline void HandleHashMapAllocT<MaxHandlesT, KeyT>::free(KeyT _key)
+ {
+ uint16_t handle = m_table.find(_key);
+ if (invalid == handle)
+ {
+ return;
+ }
+
+ m_table.removeByKey(_key);
+ m_alloc.free(handle);
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline void HandleHashMapAllocT<MaxHandlesT, KeyT>::free(uint16_t _handle)
+ {
+ m_table.removeByHandle(_handle);
+ m_alloc.free(_handle);
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline uint16_t HandleHashMapAllocT<MaxHandlesT, KeyT>::find(KeyT _key) const
+ {
+ return m_table.find(_key);
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline const uint16_t* HandleHashMapAllocT<MaxHandlesT, KeyT>::getHandles() const
+ {
+ return m_alloc.getHandles();
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline uint16_t HandleHashMapAllocT<MaxHandlesT, KeyT>::getHandleAt(uint16_t _at) const
+ {
+ return m_alloc.getHandleAt(_at);
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline uint16_t HandleHashMapAllocT<MaxHandlesT, KeyT>::getNumHandles() const
+ {
+ return m_alloc.getNumHandles();
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline uint16_t HandleHashMapAllocT<MaxHandlesT, KeyT>::getMaxHandles() const
+ {
+ return m_alloc.getMaxHandles();
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline bool HandleHashMapAllocT<MaxHandlesT, KeyT>::isValid(uint16_t _handle) const
+ {
+ return m_alloc.isValid(_handle);
+ }
+
+ template <uint16_t MaxHandlesT, typename KeyT>
+ inline void HandleHashMapAllocT<MaxHandlesT, KeyT>::reset()
+ {
+ m_table.reset();
+ m_alloc.reset();
+ }
+
+} // namespace bx