Program Listing for File FixedSizePool.hpp¶
↰ Return to documentation for file (umpire/strategy/FixedSizePool.hpp
)
//////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2016-20, Lawrence Livermore National Security, LLC and Umpire
// project contributors. See the COPYRIGHT file for details.
//
// SPDX-License-Identifier: (MIT)
//////////////////////////////////////////////////////////////////////////////
#ifndef _FIXEDSIZEPOOL_HPP
#define _FIXEDSIZEPOOL_HPP
#include <stdio.h>
#include <cstring>
#include <iostream>
#include "StdAllocator.hpp"
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4244)
#pragma warning(disable : 4245)
#pragma warning(disable : 4267)
#endif
inline int find_first_set(int i)
{
#if defined(_MSC_VER)
unsigned long bit;
unsigned long i_l = static_cast<unsigned long>(i);
_BitScanForward(&bit, i_l);
return static_cast<int>(bit);
#else
return ffs(i);
#endif
}
template <class T, class MA, class IA = StdAllocator, int NP = (1 << 6)>
class FixedSizePool {
protected:
struct Pool {
unsigned char *data;
unsigned int *avail;
unsigned int numAvail;
struct Pool *next;
};
struct Pool *pool;
const std::size_t numPerPool;
const std::size_t totalPoolSize;
std::size_t numBlocks;
void newPool(struct Pool **pnew)
{
struct Pool *p = static_cast<struct Pool *>(
IA::allocate(sizeof(struct Pool) + NP * sizeof(unsigned int)));
p->numAvail = numPerPool;
p->next = NULL;
p->data =
reinterpret_cast<unsigned char *>(MA::allocate(numPerPool * sizeof(T)));
p->avail = reinterpret_cast<unsigned int *>(p + 1);
for (int i = 0; i < NP; i++)
p->avail[i] = (~0);
*pnew = p;
}
T *allocInPool(struct Pool *p)
{
if (!p->numAvail)
return NULL;
for (int i = 0; i < NP; i++) {
const int bit = find_first_set(p->avail[i]) - 1;
if (bit >= 0) {
p->avail[i] ^= 1 << bit;
p->numAvail--;
const int entry = i * sizeof(unsigned int) * 8 + bit;
return reinterpret_cast<T *>(p->data) + entry;
}
}
return NULL;
}
public:
static inline FixedSizePool &getInstance()
{
static FixedSizePool instance;
return instance;
}
FixedSizePool()
: numPerPool(NP * sizeof(unsigned int) * 8),
totalPoolSize(sizeof(struct Pool) + numPerPool * sizeof(T) +
NP * sizeof(unsigned int)),
numBlocks(0)
{
newPool(&pool);
}
~FixedSizePool()
{
for (struct Pool *curr = pool; curr;) {
struct Pool *next = curr->next;
MA::deallocate(curr->data);
IA::deallocate(curr);
curr = next;
}
}
T *allocate()
{
T *ptr = NULL;
struct Pool *prev = NULL;
struct Pool *curr = pool;
while (!ptr && curr) {
ptr = allocInPool(curr);
prev = curr;
curr = curr->next;
}
if (!ptr) {
newPool(&prev->next);
ptr = allocate();
// TODO: In this case we should reverse the linked list for optimality
} else {
numBlocks++;
}
return ptr;
}
void deallocate(T *ptr)
{
int i = 0;
for (struct Pool *curr = pool; curr; curr = curr->next) {
const T *start = reinterpret_cast<T *>(curr->data);
const T *end = reinterpret_cast<T *>(curr->data) + numPerPool;
if ((ptr >= start) && (ptr < end)) {
// indexes bits 0 - numPerPool-1
const int indexD = ptr - reinterpret_cast<T *>(curr->data);
const int indexI = indexD / (sizeof(unsigned int) * 8);
const int indexB = indexD % (sizeof(unsigned int) * 8);
#ifndef NDEBUG
if ((curr->avail[indexI] & (1 << indexB))) {
std::cerr << "Trying to deallocate an entry that was not marked as "
"allocated"
<< std::endl;
}
#endif
curr->avail[indexI] ^= 1 << indexB;
curr->numAvail++;
numBlocks--;
return;
}
i++;
}
std::cerr << "Could not find pointer to deallocate" << std::endl;
throw(std::bad_alloc());
}
/// Return allocated size to user.
std::size_t getCurrentSize() const
{
return numBlocks * sizeof(T);
}
/// Return total size with internal overhead.
std::size_t getActualSize() const
{
return numPools() * totalPoolSize;
}
/// Return the number of pools
std::size_t numPools() const
{
std::size_t np = 0;
for (struct Pool *curr = pool; curr; curr = curr->next)
np++;
return np;
}
/// Return the pool size
std::size_t poolSize() const
{
return totalPoolSize;
}
};
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
#endif // _FIXEDSIZEPOOL_HPP