Last active
January 8, 2022 16:53
-
-
Save bitnenfer/11c5587525756b29ea5262b418c70c0e to your computer and use it in GitHub Desktop.
Fast tiny pool of 64 elements that allows random allocation and freeing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* x64 Fast tiny pool of 64 elements that allows random allocation and freeing */ | |
/* by Felipe Alfonso - http://voitptr.io */ | |
#include <stdint.h> | |
#if _WIN32 | |
#include <intrin.h> | |
#endif | |
template<typename T> | |
struct TinyPool | |
{ | |
#if _WIN32 | |
inline bool Bsf(unsigned long* Index, uint64_t Mask) const { return _BitScanForward64(Index, Mask); } | |
inline uint64_t CountBits(uint64_t Mask) const { return __popcnt64(Mask); } | |
#else | |
inline bool Bsf(unsigned long* Index, uint64_t Mask) const { int Idx = __builtin_ctzll(Mask); *Index = (unsigned long)Idx; return Idx != 64; } | |
inline uint64_t CountBits(uint64_t Mask) const { return __builtin_popcountll(Mask); } | |
#endif | |
static constexpr uint64_t kMaxPoolSize = 64ull; | |
T* Alloc() { unsigned long Index = 0; return Bsf(&Index, Bitmap) ? &Pool[AllocBit((uint64_t)Index)] : nullptr; } | |
void Free(T* Ptr) { FreeBit(GetIndex(Ptr)); } | |
inline bool CanAllocate() const { return Bitmap > 0ull; } | |
inline bool IsPtrAllocated(const T* Ptr) const { return IsBitAllocated(GetIndex(Ptr)); } | |
inline bool OwnsAllocation(const T* Ptr) const { return ((uint64_t)Ptr - (uint64_t)Pool) < sizeof(Pool); } | |
inline uint64_t GetAvailableCount() const { return CountBits(Bitmap); } | |
inline uint64_t GetUsedCount() const { return kMaxPoolSize - CountBits(Bitmap); } | |
private: | |
inline uint64_t GetIndex(const T* Ptr) const { return ((uint64_t)Ptr - (uint64_t)Pool) / sizeof(T); } | |
inline bool IsBitAllocated(uint64_t Index) const { return Index < kMaxPoolSize && ((Bitmap& (1ull << Index)) == 0ull); } | |
inline uint64_t AllocBit(uint64_t Index) { Bitmap &= ~(1ull << Index); return Index; } | |
inline void FreeBit(uint64_t Index) { if (Index < kMaxPoolSize) Bitmap |= (1ull << Index); } | |
T Pool[kMaxPoolSize]; | |
uint64_t Bitmap = ~0ull; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment