Stxxl  1.3.2
block_alloc_interleaved.h
1 /***************************************************************************
2  * include/stxxl/bits/mng/block_alloc_interleaved.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002, 2003 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007-2009, 2011 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_INTERLEAVED_ALLOC_HEADER
15 #define STXXL_INTERLEAVED_ALLOC_HEADER
16 
17 #include <vector>
18 
19 #include <stxxl/bits/mng/mng.h>
20 #include <stxxl/bits/common/rand.h>
21 
22 
23 __STXXL_BEGIN_NAMESPACE
24 
25 #define CHECK_RUN_BOUNDS(pos)
26 
27 struct interleaved_striping
28 {
29 protected:
30  int_type nruns;
31  int begindisk;
32  int diff;
33 
34  interleaved_striping(int_type nruns, int begindisk, int diff)
35  : nruns(nruns), begindisk(begindisk), diff(diff)
36  { }
37 
38 public:
39  interleaved_striping(int_type _nruns, const striping & strategy)
40  : nruns(_nruns), begindisk(strategy.begin), diff(strategy.diff)
41  { }
42 
43  int operator () (int_type i) const
44  {
45  return begindisk + (i / nruns) % diff;
46  }
47 };
48 
49 struct interleaved_FR : public interleaved_striping
50 {
52 
53  interleaved_FR(int_type _nruns, const FR & strategy)
54  : interleaved_striping(_nruns, strategy.begin, strategy.diff)
55  { }
56 
57  int operator () (int_type /*i*/) const
58  {
59  return begindisk + rnd(diff);
60  }
61 };
62 
63 struct interleaved_SR : public interleaved_striping
64 {
65  std::vector<int> offsets;
66 
67  interleaved_SR(int_type _nruns, const SR & strategy)
68  : interleaved_striping(_nruns, strategy.begin, strategy.diff)
69  {
71  for (int_type i = 0; i < nruns; i++)
72  offsets.push_back(rnd(diff));
73  }
74 
75  int operator () (int_type i) const
76  {
77  return begindisk + (i / nruns + offsets[i % nruns]) % diff;
78  }
79 };
80 
81 
82 struct interleaved_RC : public interleaved_striping
83 {
84  std::vector<std::vector<int> > perms;
85 
86  interleaved_RC(int_type _nruns, const RC & strategy)
87  : interleaved_striping(_nruns, strategy.begin, strategy.diff),
88  perms(nruns, std::vector<int>(diff))
89  {
90  for (int_type i = 0; i < nruns; i++)
91  {
92  for (int j = 0; j < diff; j++)
93  perms[i][j] = j;
94 
96  std::random_shuffle(perms[i].begin(), perms[i].end(), rnd _STXXL_FORCE_SEQUENTIAL);
97  }
98  }
99 
100  int operator () (int_type i) const
101  {
102  return begindisk + perms[i % nruns][(i / nruns) % diff];
103  }
104 };
105 
106 struct first_disk_only : public interleaved_striping
107 {
108  first_disk_only(int_type _nruns, const single_disk & strategy)
109  : interleaved_striping(_nruns, strategy.disk, 1)
110  { }
111 
112  int operator () (int_type) const
113  {
114  return begindisk;
115  }
116 };
117 
118 template <typename scheme>
119 struct interleaved_alloc_traits
120 { };
121 
122 template <>
123 struct interleaved_alloc_traits<striping>
124 {
125  typedef interleaved_striping strategy;
126 };
127 
128 template <>
129 struct interleaved_alloc_traits<FR>
130 {
131  typedef interleaved_FR strategy;
132 };
133 
134 template <>
135 struct interleaved_alloc_traits<SR>
136 {
137  typedef interleaved_SR strategy;
138 };
139 
140 template <>
141 struct interleaved_alloc_traits<RC>
142 {
143  typedef interleaved_RC strategy;
144 };
145 
146 template <>
147 struct interleaved_alloc_traits<RC_disk>
148 {
149  // FIXME! HACK!
150  typedef interleaved_RC strategy;
151 };
152 
153 template <>
154 struct interleaved_alloc_traits<RC_flash>
155 {
156  // FIXME! HACK!
157  typedef interleaved_RC strategy;
158 };
159 
160 template <>
161 struct interleaved_alloc_traits<single_disk>
162 {
163  typedef first_disk_only strategy;
164 };
165 
166 __STXXL_END_NAMESPACE
167 
168 #endif // !STXXL_INTERLEAVED_ALLOC_HEADER
169 // vim: et:ts=4:sw=4
fully randomized disk allocation scheme functor
Definition: block_alloc.h:69
striping disk allocation scheme functor
Definition: block_alloc.h:43
void random_shuffle(ExtIterator_ first, ExtIterator_ last, RandomNumberGenerator_ &rand, unsigned_type M, AllocStrategy_ AS=STXXL_DEFAULT_ALLOC_STRATEGY())
External equivalent of std::random_shuffle.
Definition: random_shuffle.h:49
simple randomized disk allocation scheme functor
Definition: block_alloc.h:94
External vector container.
Definition: vector.h:259
&#39;single disk&#39; disk allocation scheme functor
Definition: block_alloc.h:195
randomized cycling disk allocation scheme functor
Definition: block_alloc.h:129