LZW Compressor
 All Classes Files Functions Typedefs
FSBAllocator.hh
1 /*===========================================================================
2  This library is released under the MIT license. See FSBAllocator.html
3  for further information and documentation.
4 
5 Copyright (c) 2008-2011 Juha Nieminen
6 
7 Permission is hereby granted, free of charge, to any person obtaining a copy
8 of this software and associated documentation files (the "Software"), to deal
9 in the Software without restriction, including without limitation the rights
10 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 copies of the Software, and to permit persons to whom the Software is
12 furnished to do so, subject to the following conditions:
13 
14 The above copyright notice and this permission notice shall be included in
15 all copies or substantial portions of the Software.
16 
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 THE SOFTWARE.
24 =============================================================================*/
25 
26 #ifndef INCLUDE_FSBALLOCATOR_HH
27 #define INCLUDE_FSBALLOCATOR_HH
28 
29 #include <new>
30 #include <cassert>
31 #include <vector>
32 
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;
40 #endif
41 
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
47 #include <omp.h>
48 
49 class FSBAllocator_Mutex
50 {
51  omp_lock_t mutex;
52 
53  public:
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); }
58 };
59 #endif
60 
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
66 #include <pthread.h>
67 
68 class FSBAllocator_Mutex
69 {
70  pthread_mutex_t mutex;
71 
72  public:
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); }
77 };
78 #endif
79 
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
86 #include <sched.h>
87 #endif
88 class FSBAllocator_Mutex
89 {
90  volatile int lockFlag;
91 
92  public:
93  FSBAllocator_Mutex(): lockFlag(0) {}
94  void lock()
95  {
96  while(!__sync_bool_compare_and_swap(&lockFlag, 0, 1))
97  {
98 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC_WITH_SCHED
99  sched_yield();
100 #endif
101  }
102  }
103  void unlock() { lockFlag = 0; }
104 };
105 #endif
106 
107 template<unsigned ElemSize>
109 {
110  typedef std::size_t Data_t;
111  static const Data_t BlockElements = 512;
112 
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;
117 
118  class MemBlock
119  {
120  Data_t* block;
121  Data_t firstFreeUnitIndex, allocatedElementsAmount, endIndex;
122 
123  public:
124  MemBlock():
125  block(0),
126  firstFreeUnitIndex(Data_t(-1)),
127  allocatedElementsAmount(0)
128  {}
129 
130  bool isFull() const
131  {
132  return allocatedElementsAmount == BlockElements;
133  }
134 
135  void clear()
136  {
137  delete[] block;
138  block = 0;
139  firstFreeUnitIndex = Data_t(-1);
140  }
141 
142  void* allocate(Data_t vectorIndex)
143  {
144  if(firstFreeUnitIndex == Data_t(-1))
145  {
146  if(!block)
147  {
148  block = new Data_t[BlockSize];
149  if(!block) return 0;
150  endIndex = 0;
151  }
152 
153  Data_t* retval = block + endIndex;
154  endIndex += UnitSizeInDSize;
155  retval[ElemSizeInDSize] = vectorIndex;
156  ++allocatedElementsAmount;
157  return retval;
158  }
159  else
160  {
161  Data_t* retval = block + firstFreeUnitIndex;
162  firstFreeUnitIndex = *retval;
163  ++allocatedElementsAmount;
164  return retval;
165  }
166  }
167 
168  void deallocate(Data_t* ptr)
169  {
170  *ptr = firstFreeUnitIndex;
171  firstFreeUnitIndex = ptr - block;
172 
173  if(--allocatedElementsAmount == 0)
174  clear();
175  }
176  };
177 
179  {
180  std::vector<MemBlock> data;
181 
182  BlocksVector() { data.reserve(1024); }
183 
184  ~BlocksVector()
185  {
186  for(std::size_t i = 0; i < data.size(); ++i)
187  data[i].clear();
188  }
189  };
190 
191  static BlocksVector blocksVector;
192  static std::vector<Data_t> blocksWithFree;
193 
194 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
195  static FSBAllocator_Mutex mutex;
196 
197 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
198  struct Lock: boost::mutex::scoped_lock
199  {
200  Lock(): boost::mutex::scoped_lock(mutex) {}
201  };
202 #else
203  struct Lock
204  {
205  Lock() { mutex.lock(); }
206  ~Lock() { mutex.unlock(); }
207  };
208 #endif
209 #endif
210 
211  public:
212  static void* allocate()
213  {
214 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
215  Lock lock;
216 #endif
217 
218  if(blocksWithFree.empty())
219  {
220  blocksWithFree.push_back(blocksVector.data.size());
221  blocksVector.data.push_back(MemBlock());
222  }
223 
224  const Data_t index = blocksWithFree.back();
225  MemBlock& block = blocksVector.data[index];
226  void* retval = block.allocate(index);
227 
228  if(block.isFull())
229  blocksWithFree.pop_back();
230 
231  return retval;
232  }
233 
234  static void deallocate(void* ptr)
235  {
236  if(!ptr) return;
237 
238 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
239  Lock lock;
240 #endif
241 
242  Data_t* unitPtr = (Data_t*)ptr;
243  const Data_t blockIndex = unitPtr[ElemSizeInDSize];
244  MemBlock& block = blocksVector.data[blockIndex];
245 
246  if(block.isFull())
247  blocksWithFree.push_back(blockIndex);
248  block.deallocate(unitPtr);
249  }
250 };
251 
252 template<unsigned ElemSize>
255 
256 template<unsigned ElemSize>
257 std::vector<typename FSBAllocator_ElemAllocator<ElemSize>::Data_t>
259 
260 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
261 template<unsigned ElemSize>
263 #endif
264 
265 
266 template<unsigned ElemSize>
268 {
269  static const std::size_t BlockElements = 1024;
270 
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;
274 
275  struct Blocks
276  {
277  std::vector<std::size_t*> ptrs;
278 
279  Blocks()
280  {
281  ptrs.reserve(256);
282  ptrs.push_back(new std::size_t[BlockSize]);
283  }
284 
285  ~Blocks()
286  {
287  for(std::size_t i = 0; i < ptrs.size(); ++i)
288  delete[] ptrs[i];
289  }
290  };
291 
292  static Blocks blocks;
293  static std::size_t headIndex;
294  static std::size_t* freeList;
295  static std::size_t allocatedElementsAmount;
296 
297 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
298  static FSBAllocator_Mutex mutex;
299 
300 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_BOOST
301  struct Lock: boost::mutex::scoped_lock
302  {
303  Lock(): boost::mutex::scoped_lock(mutex) {}
304  };
305 #else
306  struct Lock
307  {
308  Lock() { mutex.lock(); }
309  ~Lock() { mutex.unlock(); }
310  };
311 #endif
312 #endif
313 
314  static void freeAll()
315  {
316  for(std::size_t i = 1; i < blocks.ptrs.size(); ++i)
317  delete[] blocks.ptrs[i];
318  blocks.ptrs.resize(1);
319  headIndex = 0;
320  freeList = 0;
321  }
322 
323  public:
324  static void* allocate()
325  {
326 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
327  Lock lock;
328 #endif
329 
330  ++allocatedElementsAmount;
331 
332  if(freeList)
333  {
334  std::size_t* retval = freeList;
335  freeList = reinterpret_cast<std::size_t*>(*freeList);
336  return retval;
337  }
338 
339  if(headIndex == BlockSize)
340  {
341  blocks.ptrs.push_back(new std::size_t[BlockSize]);
342  headIndex = 0;
343  }
344 
345  std::size_t* retval = &(blocks.ptrs.back()[headIndex]);
346  headIndex += ElemSizeInDSize;
347  return retval;
348  }
349 
350  static void deallocate(void* ptr)
351  {
352  if(ptr)
353  {
354 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
355  Lock lock;
356 #endif
357 
358  std::size_t* sPtr = (std::size_t*)ptr;
359  *sPtr = reinterpret_cast<std::size_t>(freeList);
360  freeList = sPtr;
361 
362  if(--allocatedElementsAmount == 0)
363  freeAll();
364  }
365  }
366 
367  static void cleanSweep(std::size_t unusedValue = std::size_t(-1))
368  {
369 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
370  Lock lock;
371 #endif
372 
373  while(freeList)
374  {
375  std::size_t* current = freeList;
376  freeList = reinterpret_cast<std::size_t*>(*freeList);
377  *current = unusedValue;
378  }
379 
380  for(std::size_t i = headIndex; i < BlockSize; i += ElemSizeInDSize)
381  blocks.ptrs.back()[i] = unusedValue;
382 
383  for(std::size_t blockInd = 1; blockInd < blocks.ptrs.size();)
384  {
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)
389  ++freeAmount;
390 
391  if(freeAmount == BlockElements)
392  {
393  delete[] block;
394  blocks.ptrs[blockInd] = blocks.ptrs.back();
395  blocks.ptrs.pop_back();
396  }
397  else ++blockInd;
398  }
399 
400  const std::size_t* lastBlock = blocks.ptrs.back();
401  for(headIndex = BlockSize; headIndex > 0; headIndex -= ElemSizeInDSize)
402  if(lastBlock[headIndex-ElemSizeInDSize] != unusedValue)
403  break;
404 
405  const std::size_t lastBlockIndex = blocks.ptrs.size() - 1;
406  for(std::size_t blockInd = 0; blockInd <= lastBlockIndex; ++blockInd)
407  {
408  std::size_t* block = blocks.ptrs[blockInd];
409  for(std::size_t i = 0; i < BlockSize; i += ElemSizeInDSize)
410  {
411  if(blockInd == lastBlockIndex && i == headIndex)
412  break;
413 
414  if(block[i] == unusedValue)
415  deallocate(block + i);
416  }
417  }
418  }
419 };
420 
421 template<unsigned ElemSize>
424 
425 template<unsigned ElemSize>
427 
428 template<unsigned ElemSize>
430 
431 template<unsigned ElemSize>
433 
434 #ifdef FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_OBJECT
435 template<unsigned ElemSize>
437 #endif
438 
439 
440 template<typename Ty>
442 {
443  public:
444  typedef std::size_t size_type;
445  typedef std::ptrdiff_t difference_type;
446  typedef Ty *pointer;
447  typedef const Ty *const_pointer;
448  typedef Ty& reference;
449  typedef const Ty& const_reference;
450  typedef Ty value_type;
451 
452  pointer address(reference val) const { return &val; }
453  const_pointer address(const_reference val) const { return &val; }
454 
455  template<class Other>
456  struct rebind
457  {
458  typedef FSBAllocator<Other> other;
459  };
460 
461  FSBAllocator() throw() {}
462 
463  template<class Other>
464  FSBAllocator(const FSBAllocator<Other>&) throw() {}
465 
466  template<class Other>
467  FSBAllocator& operator=(const FSBAllocator<Other>&) { return *this; }
468 
469  pointer allocate(size_type count, const void* = 0)
470  {
471  assert(count == 1);
472  return static_cast<pointer>
474  }
475 
476  void deallocate(pointer ptr, size_type)
477  {
479  }
480 
481  void construct(pointer ptr, const Ty& val)
482  {
483  new ((void *)ptr) Ty(val);
484  }
485 
486  void destroy(pointer ptr)
487  {
488  ptr->Ty::~Ty();
489  }
490 
491  size_type max_size() const throw() { return 1; }
492 };
493 
494 
495 template<typename Ty>
497 {
498  public:
499  typedef std::size_t size_type;
500  typedef std::ptrdiff_t difference_type;
501  typedef Ty *pointer;
502  typedef const Ty *const_pointer;
503  typedef Ty& reference;
504  typedef const Ty& const_reference;
505  typedef Ty value_type;
506 
507  pointer address(reference val) const { return &val; }
508  const_pointer address(const_reference val) const { return &val; }
509 
510  template<class Other>
511  struct rebind
512  {
513  typedef FSBAllocator2<Other> other;
514  };
515 
516  FSBAllocator2() throw() {}
517 
518  template<class Other>
519  FSBAllocator2(const FSBAllocator2<Other>&) throw() {}
520 
521  template<class Other>
522  FSBAllocator2& operator=(const FSBAllocator2<Other>&) { return *this; }
523 
524  pointer allocate(size_type count, const void* = 0)
525  {
526  assert(count == 1);
527  return static_cast<pointer>
529  }
530 
531  void deallocate(pointer ptr, size_type)
532  {
534  }
535 
536  void construct(pointer ptr, const Ty& val)
537  {
538  new ((void *)ptr) Ty(val);
539  }
540 
541  void destroy(pointer ptr)
542  {
543  ptr->Ty::~Ty();
544  }
545 
546  size_type max_size() const throw() { return 1; }
547 
548  void cleanSweep(std::size_t unusedValue = std::size_t(-1))
549  {
551  }
552 };
553 
555 
556 #endif