26 #ifndef INCLUDE_FSBALLOCATOR_HH
27 #define INCLUDE_FSBALLOCATOR_HH
33 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
34 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OPENMP
35 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_PTHREAD
36 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC
37 #define FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
38 #include <boost/thread.hpp>
39 typedef boost::mutex FSBAllocator_Mutex;
42 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OPENMP
43 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
44 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_PTHREAD
45 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC
46 #define FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
49 class FSBAllocator_Mutex
54 FSBAllocator_Mutex() { omp_init_lock(&mutex); }
55 ~FSBAllocator_Mutex() { omp_destroy_lock(&mutex); }
56 void lock() { omp_set_lock(&mutex); }
57 void unlock() { omp_unset_lock(&mutex); }
61 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_PTHREAD
62 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
63 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OPENMP
64 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC
65 #define FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
68 class FSBAllocator_Mutex
70 pthread_mutex_t mutex;
73 FSBAllocator_Mutex() { pthread_mutex_init(&mutex, NULL); }
74 ~FSBAllocator_Mutex() { pthread_mutex_destroy(&mutex); }
75 void lock() { pthread_mutex_lock(&mutex); }
76 void unlock() { pthread_mutex_unlock(&mutex); }
80 #if defined(FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC) || defined(FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC_WITH_SCHED)
81 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
82 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OPENMP
83 #undef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_PTHREAD
84 #define FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
85 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC_WITH_SCHED
88 class FSBAllocator_Mutex
90 volatile int lockFlag;
93 FSBAllocator_Mutex(): lockFlag(0) {}
96 while(!__sync_bool_compare_and_swap(&lockFlag, 0, 1))
98 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC_WITH_SCHED
103 void unlock() { lockFlag = 0; }
107 template<
unsigned ElemSize>
110 typedef std::size_t Data_t;
111 static const Data_t BlockElements = 512;
113 static const Data_t DSize =
sizeof(Data_t);
114 static const Data_t ElemSizeInDSize = (ElemSize + (DSize-1)) / DSize;
115 static const Data_t UnitSizeInDSize = ElemSizeInDSize + 1;
116 static const Data_t BlockSize = BlockElements*UnitSizeInDSize;
121 Data_t firstFreeUnitIndex, allocatedElementsAmount, endIndex;
126 firstFreeUnitIndex(Data_t(-1)),
127 allocatedElementsAmount(0)
132 return allocatedElementsAmount == BlockElements;
139 firstFreeUnitIndex = Data_t(-1);
142 void* allocate(Data_t vectorIndex)
144 if(firstFreeUnitIndex == Data_t(-1))
148 block =
new Data_t[BlockSize];
153 Data_t* retval = block + endIndex;
154 endIndex += UnitSizeInDSize;
155 retval[ElemSizeInDSize] = vectorIndex;
156 ++allocatedElementsAmount;
161 Data_t* retval = block + firstFreeUnitIndex;
162 firstFreeUnitIndex = *retval;
163 ++allocatedElementsAmount;
168 void deallocate(Data_t* ptr)
170 *ptr = firstFreeUnitIndex;
171 firstFreeUnitIndex = ptr - block;
173 if(--allocatedElementsAmount == 0)
180 std::vector<MemBlock> data;
186 for(std::size_t i = 0; i < data.size(); ++i)
192 static std::vector<Data_t> blocksWithFree;
194 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
195 static FSBAllocator_Mutex mutex;
197 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
198 struct Lock: boost::mutex::scoped_lock
200 Lock(): boost::mutex::scoped_lock(mutex) {}
205 Lock() { mutex.lock(); }
206 ~Lock() { mutex.unlock(); }
212 static void* allocate()
214 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
218 if(blocksWithFree.empty())
220 blocksWithFree.push_back(blocksVector.data.size());
221 blocksVector.data.push_back(MemBlock());
224 const Data_t index = blocksWithFree.back();
225 MemBlock& block = blocksVector.data[index];
226 void* retval = block.allocate(index);
229 blocksWithFree.pop_back();
234 static void deallocate(
void* ptr)
238 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
242 Data_t* unitPtr = (Data_t*)ptr;
243 const Data_t blockIndex = unitPtr[ElemSizeInDSize];
244 MemBlock& block = blocksVector.data[blockIndex];
247 blocksWithFree.push_back(blockIndex);
248 block.deallocate(unitPtr);
252 template<
unsigned ElemSize>
256 template<
unsigned ElemSize>
257 std::vector<typename FSBAllocator_ElemAllocator<ElemSize>::Data_t>
260 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
261 template<
unsigned ElemSize>
266 template<
unsigned ElemSize>
269 static const std::size_t BlockElements = 1024;
271 static const std::size_t DSize =
sizeof(std::size_t);
272 static const std::size_t ElemSizeInDSize = (ElemSize + (DSize-1)) / DSize;
273 static const std::size_t BlockSize = BlockElements*ElemSizeInDSize;
277 std::vector<std::size_t*> ptrs;
282 ptrs.push_back(
new std::size_t[BlockSize]);
287 for(std::size_t i = 0; i < ptrs.size(); ++i)
293 static std::size_t headIndex;
294 static std::size_t* freeList;
295 static std::size_t allocatedElementsAmount;
297 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
298 static FSBAllocator_Mutex mutex;
300 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
301 struct Lock: boost::mutex::scoped_lock
303 Lock(): boost::mutex::scoped_lock(mutex) {}
308 Lock() { mutex.lock(); }
309 ~Lock() { mutex.unlock(); }
314 static void freeAll()
316 for(std::size_t i = 1; i < blocks.ptrs.size(); ++i)
317 delete[] blocks.ptrs[i];
318 blocks.ptrs.resize(1);
324 static void* allocate()
326 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
330 ++allocatedElementsAmount;
334 std::size_t* retval = freeList;
335 freeList =
reinterpret_cast<std::size_t*
>(*freeList);
339 if(headIndex == BlockSize)
341 blocks.ptrs.push_back(
new std::size_t[BlockSize]);
345 std::size_t* retval = &(blocks.ptrs.back()[headIndex]);
346 headIndex += ElemSizeInDSize;
350 static void deallocate(
void* ptr)
354 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
358 std::size_t* sPtr = (std::size_t*)ptr;
359 *sPtr =
reinterpret_cast<std::size_t
>(freeList);
362 if(--allocatedElementsAmount == 0)
367 static void cleanSweep(std::size_t unusedValue = std::size_t(-1))
369 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
375 std::size_t* current = freeList;
376 freeList =
reinterpret_cast<std::size_t*
>(*freeList);
377 *current = unusedValue;
380 for(std::size_t i = headIndex; i < BlockSize; i += ElemSizeInDSize)
381 blocks.ptrs.back()[i] = unusedValue;
383 for(std::size_t blockInd = 1; blockInd < blocks.ptrs.size();)
385 std::size_t* block = blocks.ptrs[blockInd];
386 std::size_t freeAmount = 0;
387 for(std::size_t i = 0; i < BlockSize; i += ElemSizeInDSize)
388 if(block[i] == unusedValue)
391 if(freeAmount == BlockElements)
394 blocks.ptrs[blockInd] = blocks.ptrs.back();
395 blocks.ptrs.pop_back();
400 const std::size_t* lastBlock = blocks.ptrs.back();
401 for(headIndex = BlockSize; headIndex > 0; headIndex -= ElemSizeInDSize)
402 if(lastBlock[headIndex-ElemSizeInDSize] != unusedValue)
405 const std::size_t lastBlockIndex = blocks.ptrs.size() - 1;
406 for(std::size_t blockInd = 0; blockInd <= lastBlockIndex; ++blockInd)
408 std::size_t* block = blocks.ptrs[blockInd];
409 for(std::size_t i = 0; i < BlockSize; i += ElemSizeInDSize)
411 if(blockInd == lastBlockIndex && i == headIndex)
414 if(block[i] == unusedValue)
415 deallocate(block + i);
421 template<
unsigned ElemSize>
425 template<
unsigned ElemSize>
428 template<
unsigned ElemSize>
431 template<
unsigned ElemSize>
434 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
435 template<
unsigned ElemSize>
440 template<
typename Ty>
444 typedef std::size_t size_type;
445 typedef std::ptrdiff_t difference_type;
447 typedef const Ty *const_pointer;
448 typedef Ty& reference;
449 typedef const Ty& const_reference;
450 typedef Ty value_type;
452 pointer address(reference val)
const {
return &val; }
453 const_pointer address(const_reference val)
const {
return &val; }
455 template<
class Other>
463 template<
class Other>
466 template<
class Other>
469 pointer allocate(size_type count,
const void* = 0)
472 return static_cast<pointer
>
476 void deallocate(pointer ptr, size_type)
481 void construct(pointer ptr,
const Ty& val)
483 new ((
void *)ptr) Ty(val);
486 void destroy(pointer ptr)
491 size_type max_size()
const throw() {
return 1; }
495 template<
typename Ty>
499 typedef std::size_t size_type;
500 typedef std::ptrdiff_t difference_type;
502 typedef const Ty *const_pointer;
503 typedef Ty& reference;
504 typedef const Ty& const_reference;
505 typedef Ty value_type;
507 pointer address(reference val)
const {
return &val; }
508 const_pointer address(const_reference val)
const {
return &val; }
510 template<
class Other>
518 template<
class Other>
521 template<
class Other>
524 pointer allocate(size_type count,
const void* = 0)
527 return static_cast<pointer
>
531 void deallocate(pointer ptr, size_type)
536 void construct(pointer ptr,
const Ty& val)
538 new ((
void *)ptr) Ty(val);
541 void destroy(pointer ptr)
546 size_type max_size()
const throw() {
return 1; }
548 void cleanSweep(std::size_t unusedValue = std::size_t(-1))