STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
block_alloc.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/mng/block_alloc.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
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 STXXL_MNG_BLOCK_ALLOC_HEADER
15 #define STXXL_MNG_BLOCK_ALLOC_HEADER
16 
17 #include <algorithm>
18 #include <stxxl/bits/parallel.h>
19 #include <stxxl/bits/common/rand.h>
20 #include <stxxl/bits/mng/config.h>
21 
23 
24 //! \defgroup alloc Allocation Functors
25 //! \ingroup mnglayer
26 //! Standard allocation strategies encapsulated in functors.
27 //! \{
28 
29 //! Example disk allocation scheme functor.
30 //! \remarks model of \b allocation_strategy concept
32 {
33  basic_allocation_strategy(int disks_begin, int disks_end);
35  int operator () (int i) const;
36  static const char * name();
37 };
38 
39 //! Striping disk allocation scheme functor.
40 //! \remarks model of \b allocation_strategy concept
41 struct striping
42 {
44 
45 public:
46  striping(unsigned_type b, unsigned_type e) : begin(b), diff(e - b)
47  { }
48 
49  striping() : begin(0)
50  {
51  diff = config::get_instance()->disks_number();
52  }
53 
54  unsigned_type operator () (unsigned_type i) const
55  {
56  return begin + i % diff;
57  }
58 
59  static const char * name()
60  {
61  return "striping";
62  }
63 };
64 
65 //! Fully randomized disk allocation scheme functor.
66 //! \remarks model of \b allocation_strategy concept
67 struct FR : public striping
68 {
69 private:
72 
73 public:
75  { }
76 
77  FR() : striping()
78  { }
79 
80  unsigned_type operator () (unsigned_type /*i*/) const
81  {
82  return begin + rnd(rnd_type::value_type(diff));
83  }
84 
85  static const char * name()
86  {
87  return "fully randomized striping";
88  }
89 };
90 
91 //! Simple randomized disk allocation scheme functor.
92 //! \remarks model of \b allocation_strategy concept
93 struct SR : public striping
94 {
95 private:
97 
99 
100  void init()
101  {
102  rnd_type rnd;
103  offset = rnd(rnd_type::value_type(diff));
104  }
105 
106 public:
108  {
109  init();
110  }
111 
112  SR() : striping()
113  {
114  init();
115  }
116 
117  unsigned_type operator () (unsigned_type i) const
118  {
119  return begin + (i + offset) % diff;
120  }
121 
122  static const char * name()
123  {
124  return "simple randomized striping";
125  }
126 };
127 
128 //! Randomized cycling disk allocation scheme functor.
129 //! \remarks model of \b allocation_strategy concept
130 struct RC : public striping
131 {
132 private:
133  std::vector<unsigned_type> perm;
134 
135  void init()
136  {
137  for (unsigned_type i = 0; i < diff; i++)
138  perm[i] = i;
139 
141  std::random_shuffle(perm.begin(), perm.end(), rnd _STXXL_FORCE_SEQUENTIAL);
142  }
143 
144 public:
145  RC(unsigned_type b, unsigned_type e) : striping(b, e), perm(diff)
146  {
147  init();
148  }
149 
150  RC() : striping(), perm(diff)
151  {
152  init();
153  }
154 
155  unsigned_type operator () (unsigned_type i) const
156  {
157  return begin + perm[i % diff];
158  }
159 
160  static const char * name()
161  {
162  return "randomized cycling striping";
163  }
164 };
165 
166 struct RC_disk : public RC
167 {
169  { }
170 
171  RC_disk() : RC(config::get_instance()->regular_disk_range().first, config::get_instance()->regular_disk_range().second)
172  { }
173 
174  static const char * name()
175  {
176  return "Randomized cycling striping on regular disks";
177  }
178 };
179 
180 struct RC_flash : public RC
181 {
183  { }
184 
185  RC_flash() : RC(config::get_instance()->flash_range().first, 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' disk allocation scheme functor.
195 //! \remarks model of \b allocation_strategy concept
197 {
200  { }
201 
202  single_disk() : disk(0)
203  { }
204 
205  unsigned_type operator () (unsigned_type /*i*/) const
206  {
207  return disk;
208  }
209 
210  static const char * name()
211  {
212  return "single disk";
213  }
214 };
215 
216 //! Allocator functor adaptor.
217 //!
218 //! Gives offset to disk number sequence defined in constructor
219 template <class BaseAllocator>
221 {
222  BaseAllocator base;
224 
225  //! Creates functor based on instance of \c BaseAllocator functor
226  //! with offset \c offset_.
227  //! \param offset_ offset
228  //! \param base_ used to create a copy
229  offset_allocator(int_type offset_, const BaseAllocator& base_) : base(base_), offset(offset_)
230  { }
231 
232  //! Creates functor based on instance of \c BaseAllocator functor.
233  //! \param base_ used to create a copy
234  offset_allocator(const BaseAllocator& base_) : base(base_), offset(0)
235  { }
236 
237  //! Creates functor based on default \c BaseAllocator functor.
238  offset_allocator() : offset(0)
239  { }
240 
241  unsigned_type operator () (unsigned_type i) const
242  {
243  return base(offset + i);
244  }
245 
247  {
248  return offset;
249  }
250 
252  {
253  offset = i;
254  }
255 };
256 
257 #ifndef STXXL_DEFAULT_ALLOC_STRATEGY
258  #define STXXL_DEFAULT_ALLOC_STRATEGY stxxl::RC
259 #endif
260 
261 //! \}
262 
264 
265 #endif // !STXXL_MNG_BLOCK_ALLOC_HEADER
266 // vim: et:ts=4:sw=4
striping(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:46
random_number< random_uniform_fast > rnd_type
Definition: block_alloc.h:70
Fully randomized disk allocation scheme functor.
Definition: block_alloc.h:67
SR(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:107
Allocator functor adaptor.
Definition: block_alloc.h:220
random_number< random_uniform_fast > rnd_type
Definition: block_alloc.h:98
int_type get_offset() const
Definition: block_alloc.h:246
Example disk allocation scheme functor.
Definition: block_alloc.h:31
&#39;Single disk&#39; disk allocation scheme functor.
Definition: block_alloc.h:196
static const char * name()
Definition: block_alloc.h:210
unsigned_type disk
Definition: block_alloc.h:198
RC_flash(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:182
offset_allocator()
Creates functor based on default BaseAllocator functor.
Definition: block_alloc.h:238
offset_allocator(int_type offset_, const BaseAllocator &base_)
Creates functor based on instance of BaseAllocator functor with offset offset_.
Definition: block_alloc.h:229
offset_allocator(const BaseAllocator &base_)
Creates functor based on instance of BaseAllocator functor.
Definition: block_alloc.h:234
void init()
Definition: block_alloc.h:135
unsigned_type offset
Definition: block_alloc.h:96
static const char * name()
Definition: block_alloc.h:160
unsigned_type diff
Definition: block_alloc.h:43
static const char * name()
Definition: block_alloc.h:122
Randomized cycling disk allocation scheme functor.
Definition: block_alloc.h:130
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
void random_shuffle(ExtIterator first, ExtIterator last, RandomNumberGenerator &rand, unsigned_type M, AllocStrategy AS=STXXL_DEFAULT_ALLOC_STRATEGY())
External equivalent of std::random_shuffle.
static const char * name()
Definition: block_alloc.h:59
rnd_type rnd
Definition: block_alloc.h:71
Striping disk allocation scheme functor.
Definition: block_alloc.h:41
std::vector< unsigned_type > perm
Definition: block_alloc.h:133
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
Simple randomized disk allocation scheme functor.
Definition: block_alloc.h:93
static const char * name()
Definition: block_alloc.h:85
FR(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:74
void init()
Definition: block_alloc.h:100
static const char * name()
Definition: block_alloc.h:174
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
Access point to disks properties. Since 1.4.0: no config files are read automatically! ...
Definition: config.h:112
RC_disk(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:168
RC(unsigned_type b, unsigned_type e)
Definition: block_alloc.h:145
#define _STXXL_FORCE_SEQUENTIAL
Definition: parallel.h:34
void set_offset(int_type i)
Definition: block_alloc.h:251
static const char * name()
Definition: block_alloc.h:188
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
single_disk(unsigned_type d, unsigned_type=0)
Definition: block_alloc.h:199