Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/mng/block_alloc_interleaved.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002, 2003 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 00012 **************************************************************************/ 00013 00014 #ifndef STXXL_INTERLEAVED_ALLOC_HEADER 00015 #define STXXL_INTERLEAVED_ALLOC_HEADER 00016 00017 #include <vector> 00018 00019 #include <stxxl/bits/mng/mng.h> 00020 #include <stxxl/bits/common/rand.h> 00021 00022 00023 __STXXL_BEGIN_NAMESPACE 00024 00025 #define CHECK_RUN_BOUNDS(pos) 00026 00027 struct interleaved_striping 00028 { 00029 int_type nruns; 00030 int begindisk; 00031 int diff; 00032 interleaved_striping(int_type _nruns, int _begindisk, 00033 int _enddisk) : nruns(_nruns), 00034 begindisk(_begindisk), diff(_enddisk - _begindisk) 00035 { } 00036 00037 int operator () (int_type i) const 00038 { 00039 return begindisk + (i / nruns) % diff; 00040 } 00041 00042 virtual ~interleaved_striping() 00043 { } 00044 }; 00045 00046 struct interleaved_FR : public interleaved_striping 00047 { 00048 interleaved_FR(int_type _nruns, int _begindisk, 00049 int _enddisk) : interleaved_striping(_nruns, _begindisk, 00050 _enddisk) 00051 { } 00052 random_number<random_uniform_fast> rnd; 00053 int operator () (int_type /*i*/) const 00054 { 00055 return begindisk + rnd(diff); 00056 } 00057 }; 00058 00059 struct interleaved_SR : public interleaved_striping 00060 { 00061 std::vector<int> offsets; 00062 00063 interleaved_SR(int_type _nruns, int _begindisk, 00064 int _enddisk) : interleaved_striping(_nruns, 00065 _begindisk, 00066 _enddisk) 00067 { 00068 random_number<random_uniform_fast> rnd; 00069 for (int_type i = 0; i < nruns; i++) 00070 offsets.push_back(rnd(diff)); 00071 } 00072 00073 int operator () (int_type i) const 00074 { 00075 return begindisk + (i / nruns + offsets[i % nruns]) % diff; 00076 } 00077 }; 00078 00079 00080 struct interleaved_RC : public interleaved_striping 00081 { 00082 std::vector<std::vector<int> > perms; 00083 00084 interleaved_RC(int_type _nruns, int _begindisk, 00085 int _enddisk) : interleaved_striping(_nruns, 00086 _begindisk, 00087 _enddisk), 00088 perms(nruns, std::vector<int>(diff)) 00089 { 00090 for (int_type i = 0; i < nruns; i++) 00091 { 00092 for (int j = 0; j < diff; j++) 00093 perms[i][j] = j; 00094 00095 00096 random_number<random_uniform_fast> rnd; 00097 std::random_shuffle(perms[i].begin(), 00098 perms[i].end(), rnd); 00099 } 00100 } 00101 00102 int operator () (int_type i) const 00103 { 00104 return begindisk + perms[i % nruns][(i / nruns) % diff]; 00105 } 00106 }; 00107 00108 struct first_disk_only : public interleaved_striping 00109 { 00110 first_disk_only(int_type _nruns, int _begindisk, int) 00111 : interleaved_striping(_nruns, _begindisk, _begindisk + 1) 00112 { } 00113 00114 int operator () (int_type) const 00115 { 00116 return begindisk; 00117 } 00118 }; 00119 00120 template <typename scheme> 00121 struct interleaved_alloc_traits 00122 { }; 00123 00124 template <> 00125 struct interleaved_alloc_traits<striping> 00126 { 00127 typedef interleaved_striping strategy; 00128 }; 00129 00130 template <> 00131 struct interleaved_alloc_traits<FR> 00132 { 00133 typedef interleaved_FR strategy; 00134 }; 00135 00136 template <> 00137 struct interleaved_alloc_traits<SR> 00138 { 00139 typedef interleaved_SR strategy; 00140 }; 00141 00142 template <> 00143 struct interleaved_alloc_traits<RC> 00144 { 00145 typedef interleaved_RC strategy; 00146 }; 00147 00148 template <> 00149 struct interleaved_alloc_traits<RC_disk> 00150 { 00151 // FIXME! HACK! 00152 typedef interleaved_RC strategy; 00153 }; 00154 00155 template <> 00156 struct interleaved_alloc_traits<RC_flash> 00157 { 00158 // FIXME! HACK! 00159 typedef interleaved_RC strategy; 00160 }; 00161 00162 template <> 00163 struct interleaved_alloc_traits<single_disk> 00164 { 00165 typedef first_disk_only strategy; 00166 }; 00167 00168 __STXXL_END_NAMESPACE 00169 00170 #endif // !STXXL_INTERLEAVED_ALLOC_HEADER