Stxxl  1.2.1
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 <dementiev@mpi-sb.mpg.de>
7  * Copyright (C) 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
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  int_type nruns;
30  int begindisk;
31  int diff;
32  interleaved_striping(int_type _nruns, int _begindisk,
33  int _enddisk) : nruns(_nruns),
34  begindisk(_begindisk), diff(_enddisk - _begindisk)
35  { }
36 
37  int operator () (int_type i) const
38  {
39  return begindisk + (i / nruns) % diff;
40  }
41 
42  virtual ~interleaved_striping()
43  { }
44 };
45 
46 struct interleaved_FR : public interleaved_striping
47 {
48  interleaved_FR(int_type _nruns, int _begindisk,
49  int _enddisk) : interleaved_striping(_nruns, _begindisk,
50  _enddisk)
51  { }
53  int operator () (int_type /*i*/) const
54  {
55  return begindisk + rnd(diff);
56  }
57 };
58 
59 struct interleaved_SR : public interleaved_striping
60 {
61  std::vector<int> offsets;
62 
63  interleaved_SR(int_type _nruns, int _begindisk,
64  int _enddisk) : interleaved_striping(_nruns,
65  _begindisk,
66  _enddisk)
67  {
69  for (int_type i = 0; i < nruns; i++)
70  offsets.push_back(rnd(diff));
71  }
72 
73  int operator () (int_type i) const
74  {
75  return begindisk + (i / nruns + offsets[i % nruns]) % diff;
76  }
77 };
78 
79 
80 struct interleaved_RC : public interleaved_striping
81 {
82  std::vector<std::vector<int> > perms;
83 
84  interleaved_RC(int_type _nruns, int _begindisk,
85  int _enddisk) : interleaved_striping(_nruns,
86  _begindisk,
87  _enddisk),
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 
95 
97  std::random_shuffle(perms[i].begin(),
98  perms[i].end(), rnd);
99  }
100  }
101 
102  int operator () (int_type i) const
103  {
104  return begindisk + perms[i % nruns][(i / nruns) % diff];
105  }
106 };
107 
108 struct first_disk_only : public interleaved_striping
109 {
110  first_disk_only(int_type _nruns, int _begindisk, int)
111  : interleaved_striping(_nruns, _begindisk, _begindisk + 1)
112  { }
113 
114  int operator () (int_type) const
115  {
116  return begindisk;
117  }
118 };
119 
120 template <typename scheme>
121 struct interleaved_alloc_traits
122 { };
123 
124 template <>
125 struct interleaved_alloc_traits<striping>
126 {
127  typedef interleaved_striping strategy;
128 };
129 
130 template <>
131 struct interleaved_alloc_traits<FR>
132 {
133  typedef interleaved_FR strategy;
134 };
135 
136 template <>
137 struct interleaved_alloc_traits<SR>
138 {
139  typedef interleaved_SR strategy;
140 };
141 
142 template <>
143 struct interleaved_alloc_traits<RC>
144 {
145  typedef interleaved_RC strategy;
146 };
147 
148 template <>
149 struct interleaved_alloc_traits<RC_disk>
150 {
151  // FIXME! HACK!
152  typedef interleaved_RC strategy;
153 };
154 
155 template <>
156 struct interleaved_alloc_traits<RC_flash>
157 {
158  // FIXME! HACK!
159  typedef interleaved_RC strategy;
160 };
161 
162 template <>
163 struct interleaved_alloc_traits<single_disk>
164 {
165  typedef first_disk_only strategy;
166 };
167 
168 __STXXL_END_NAMESPACE
169 
170 #endif // !STXXL_INTERLEAVED_ALLOC_HEADER