Skip to content

Instantly share code, notes, and snippets.

@bitnenfer
Last active January 8, 2022 16:53
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bitnenfer/11c5587525756b29ea5262b418c70c0e to your computer and use it in GitHub Desktop.
Save bitnenfer/11c5587525756b29ea5262b418c70c0e to your computer and use it in GitHub Desktop.
Fast tiny pool of 64 elements that allows random allocation and freeing
/* 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