Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
block_alloc_strategy.hpp
Go to the documentation of this file.
1 /***************************************************************************
2  * foxxll/mng/block_alloc_strategy.hpp
3  *
4  * Part of FOXXLL. See http://foxxll.org
5  *
6  * Copyright (C) 2002-2007 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007-2009 Andreas Beckmann <[email protected]>
8  *
9  * Distributed under the Boost Software License, Version 1.0.
10  * (See accompanying file LICENSE_1_0.txt or copy at
11  * http://www.boost.org/LICENSE_1_0.txt)
12  **************************************************************************/
13 
14 #ifndef FOXXLL_MNG_BLOCK_ALLOC_STRATEGY_HEADER
15 #define FOXXLL_MNG_BLOCK_ALLOC_STRATEGY_HEADER
16 
17 #include <algorithm>
18 #include <random>
19 #include <vector>
20 
22 #include <foxxll/mng/config.hpp>
23 
24 namespace foxxll {
25 
26 //! \defgroup foxxll_alloc Allocation Functors
27 //! \ingroup foxxll_mnglayer
28 //! Standard allocation strategies encapsulated in functors.
29 //! \{
30 
31 //! Example parallel disk block allocation scheme functor.
32 //! \remarks model of \b allocation_strategy concept
34 {
35  basic_allocation_strategy(size_t disks_begin, size_t disks_end);
37  size_t operator () (size_t i) const;
38  static const char * name();
39 };
40 
41 //! Striping parallel disk block allocation scheme functor.
42 //! \remarks model of \b allocation_strategy concept
43 struct striping
44 {
45  size_t begin_, diff_;
46 
47 public:
48  striping(size_t begin, size_t end)
49  : begin_(begin), diff_(end - begin) { }
50 
52  {
54  }
55 
56  size_t operator () (size_t i) const
57  {
58  return begin_ + i % diff_;
59  }
60 
61  static const char * name()
62  {
63  return "striping";
64  }
65 };
66 
67 //! Fully randomized parallel disk block allocation scheme functor.
68 //! \remarks model of \b allocation_strategy concept
69 struct fully_random : public striping
70 {
71 private:
72  mutable std::default_random_engine rng_ { std::random_device { } () };
73 
74 public:
75  fully_random(size_t begin, size_t end) : striping(begin, end) { }
76 
78 
79  size_t operator () (size_t /* i */) const
80  {
81  return begin_ + rng_() % diff_;
82  }
83 
84  static const char * name()
85  {
86  return "fully randomized striping";
87  }
88 };
89 
90 //! Simple randomized parallel disk block allocation scheme functor.
91 //! \remarks model of \b allocation_strategy concept
92 struct simple_random : public striping
93 {
94 private:
95  size_t offset;
96 
97  void init()
98  {
99  std::default_random_engine rng { std::random_device { } () };
100  offset = rng() % diff_;
101  }
102 
103 public:
104  simple_random(size_t begin, size_t end) : striping(begin, end)
105  {
106  init();
107  }
108 
110  {
111  init();
112  }
113 
114  size_t operator () (size_t i) const
115  {
116  return begin_ + (i + offset) % diff_;
117  }
118 
119  static const char * name()
120  {
121  return "simple randomized striping";
122  }
123 };
124 
125 //! Randomized cycling parallel disk block allocation scheme functor.
126 //! \remarks model of \b allocation_strategy concept
127 struct random_cyclic : public striping
128 {
129 private:
130  std::vector<size_t> perm_;
131 
132  void init()
133  {
134  for (size_t i = 0; i < diff_; i++)
135  perm_[i] = i;
136 
137  std::random_shuffle(perm_.begin(), perm_.end());
138  }
139 
140 public:
141  random_cyclic(size_t begin, size_t end)
142  : striping(begin, end), perm_(diff_)
143  {
144  init();
145  }
146 
148  {
149  init();
150  }
151 
152  size_t operator () (size_t i) const
153  {
154  return begin_ + perm_[i % diff_];
155  }
156 
157  static const char * name()
158  {
159  return "randomized cycling striping";
160  }
161 };
162 
164 {
165  random_cyclic_disk(size_t begin, size_t end) : random_cyclic(begin, end) { }
166 
168  : random_cyclic(config::get_instance()->regular_disk_range().first,
169  config::get_instance()->regular_disk_range().second)
170  { }
171 
172  static const char * name()
173  {
174  return "Randomized cycling striping on regular disks";
175  }
176 };
177 
179 {
180  random_cyclic_flash(size_t begin, size_t end)
181  : random_cyclic(begin, end) { }
182 
184  : random_cyclic(config::get_instance()->flash_range().first,
185  config::get_instance()->flash_range().second)
186  { }
187 
188  static const char * name()
189  {
190  return "Randomized cycling striping on flash devices";
191  }
192 };
193 
194 //! 'Single disk' parallel disk block allocation scheme functor.
195 //! \remarks model of \b allocation_strategy concept
197 {
198  size_t disk_;
199 
200  explicit single_disk(size_t disk = 0, size_t = 0) : disk_(disk) { }
201 
202  size_t operator () (size_t /* i */) const
203  {
204  return disk_;
205  }
206 
207  static const char * name()
208  {
209  return "single disk";
210  }
211 };
212 
213 //! Allocator functor adapter.
214 //!
215 //! Gives offset to disk number sequence defined in constructor
216 template <class BaseAllocator>
218 {
219  BaseAllocator base_;
220  int offset_;
221 
222  //! Creates functor based on instance of \c BaseAllocator functor
223  //! with offset.
224  //! \param offset offset
225  //! \param base used to create a copy
226  offset_allocator(int offset, const BaseAllocator& base)
227  : base_(base), offset_(offset) { }
228 
229  //! Creates functor based on instance of \c BaseAllocator functor.
230  //! \param base used to create a copy
231  explicit offset_allocator(const BaseAllocator& base)
232  : base_(base), offset_(0) { }
233 
234  //! Creates functor based on default \c BaseAllocator functor.
235  offset_allocator() : offset_(0) { }
236 
237  size_t operator () (size_t i) const
238  {
239  return base_(offset_ + i);
240  }
241 
242  int get_offset() const
243  {
244  return offset_;
245  }
246 
247  void set_offset(int i)
248  {
249  offset_ = i;
250  }
251 };
252 
254 
255 //! \}
256 
257 } // namespace foxxll
258 
259 #endif // !FOXXLL_MNG_BLOCK_ALLOC_STRATEGY_HEADER
260 
261 /**************************************************************************/
offset_allocator(int offset, const BaseAllocator &base)
size_t operator()(size_t) const
random_cyclic(size_t begin, size_t end)
static const char * name()
offset_allocator()
Creates functor based on default BaseAllocator functor.
size_t operator()(size_t i) const
fully_random(size_t begin, size_t end)
simple_random(size_t begin, size_t end)
single_disk(size_t disk=0, size_t=0)
random_cyclic_disk(size_t begin, size_t end)
static const char * name()
static const char * name()
static const char * name()
size_t disks_number()
Definition: config.hpp:195
std::default_random_engine rng_
static instance_pointer get_instance()
Definition: singleton.hpp:44
offset_allocator(const BaseAllocator &base)
static const char * name()
std::vector< size_t > perm_
random_cyclic_flash(size_t begin, size_t end)
static const char * name()
striping(size_t begin, size_t end)
size_t operator()(size_t i) const