spot  2.10.0.dev
fixpool.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) 2011, 2015-2018, 2020 Laboratoire de Recherche et
3 // Développement de l'Epita (LRDE)
4 //
5 // This file is part of Spot, a model checking library.
6 //
7 // Spot is free software; you can redistribute it and/or modify it
8 // under the terms of the GNU General Public License as published by
9 // the Free Software Foundation; either version 3 of the License, or
10 // (at your option) any later version.
11 //
12 // Spot is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 // License for more details.
16 //
17 // You should have received a copy of the GNU General Public License
18 // along with this program. If not, see <http://www.gnu.org/licenses/>.
19 
20 #pragma once
21 
22 #include <spot/misc/common.hh>
23 #include <spot/misc/clz.hh>
24 
25 #if SPOT_DEBUG && defined(HAVE_VALGRIND_MEMCHECK_H)
26 #include <valgrind/memcheck.h>
27 #endif
28 
29 namespace spot
30 {
40  enum class pool_type { Safe , Unsafe };
41 
43  template<pool_type Kind>
44  class SPOT_API fixed_size_pool
45  {
46  public:
48  fixed_size_pool(size_t size)
49  : size_(
50  [](size_t size)
51  {
52  // to properly store chunks and freelist, we need size to be at
53  // least the size of a block_
54  if (size < sizeof(block_))
55  size = sizeof(block_);
56  // powers of 2 are a good alignment
57  if (!(size & (size-1)))
58  return size;
59  // small numbers are best aligned to the next power of 2
60  else if (size < alignof(std::max_align_t))
61  return size_t{1} << (CHAR_BIT*sizeof(size_t) - clz(size));
62  else
63  {
64  size_t mask = alignof(std::max_align_t)-1;
65  return (size + mask) & ~mask;
66  }
67  }(size)),
68  freelist_(nullptr),
69  chunklist_(nullptr)
70  {
71  new_chunk_();
72  }
73 
76  {
77  while (chunklist_)
78  {
79  chunk_* prev = chunklist_->prev;
80  ::operator delete(chunklist_);
81  chunklist_ = prev;
82  }
83  }
84 
86  void*
88  {
89  block_* f = freelist_;
90  // If we have free blocks available, return the first one.
91  if (f)
92  {
93 #if SPOT_DEBUG && defined(HAVE_VALGRIND_MEMCHECK_H)
94  if (Kind == pool_type::Safe)
95  {
96  VALGRIND_MALLOCLIKE_BLOCK(f, size_, 0, false);
97  // field f->next is initialized: prevents valgrind from
98  // complaining about jumps depending on uninitialized memory
99  VALGRIND_MAKE_MEM_DEFINED(f, sizeof(block_*));
100  }
101 #endif
102  freelist_ = f->next;
103  return f;
104  }
105 
106  // Else, create a block out of the last chunk of allocated
107  // memory.
108 
109  // If all the last chunk has been used, allocate one more.
110  if (free_start_ + size_ > free_end_)
111  new_chunk_();
112 
113  void* res = free_start_;
114  free_start_ += size_;
115 #if SPOT_DEBUG && defined(HAVE_VALGRIND_MEMCHECK_H)
116  if (Kind == pool_type::Safe)
117  {
118  VALGRIND_MALLOCLIKE_BLOCK(res, size_, 0, false);
119  }
120 #endif
121  return res;
122  }
123 
130  void
131  deallocate(void* ptr)
132  {
133  SPOT_ASSERT(ptr);
134  block_* b = reinterpret_cast<block_*>(ptr);
135  b->next = freelist_;
136  freelist_ = b;
137 #if SPOT_DEBUG && defined(HAVE_VALGRIND_MEMCHECK_H)
138  if (Kind == pool_type::Safe)
139  {
140  VALGRIND_FREELIKE_BLOCK(ptr, 0);
141  }
142 #endif
143  }
144 
145  private:
146  void new_chunk_()
147  {
148  const size_t requested = (size_ > 128 ? size_ : 128) * 8192 - 64;
149  chunk_* c = reinterpret_cast<chunk_*>(::operator new(requested));
150  c->prev = chunklist_;
151  chunklist_ = c;
152 
153  free_start_ = c->data_ + size_;
154  free_end_ = c->data_ + requested;
155  }
156 
157 
158  const size_t size_;
159  struct block_ { block_* next; }* freelist_;
160  char* free_start_;
161  char* free_end_;
162  // chunk = several agglomerated blocks
163  union chunk_ { chunk_* prev; char data_[1]; }* chunklist_;
164  };
165 }
A fixed-size memory pool implementation.
Definition: fixpool.hh:45
void * allocate()
Allocate size bytes of memory.
Definition: fixpool.hh:87
void deallocate(void *ptr)
Recycle size bytes of memory.
Definition: fixpool.hh:131
~fixed_size_pool()
Free any memory allocated by this pool.
Definition: fixpool.hh:75
fixed_size_pool(size_t size)
Create a pool allocating objects of size bytes.
Definition: fixpool.hh:48
Definition: automata.hh:27
pool_type
Definition: fixpool.hh:40

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.1