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 <dementiev@mpi-sb.mpg.de> 7 * Copyright (C) 2007-2009 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_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 22 STXXL_BEGIN_NAMESPACE 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 31 struct basic_allocation_strategy 32 { 33 basic_allocation_strategy(int disks_begin, int disks_end); 34 basic_allocation_strategy(); 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 { 43 unsigned_type begin, diff; 44 45 public: stripingstriping46 striping(unsigned_type b, unsigned_type e) : begin(b), diff(e - b) 47 { } 48 stripingstriping49 striping() : begin(0) 50 { 51 diff = config::get_instance()->disks_number(); 52 } 53 operatorstriping54 unsigned_type operator () (unsigned_type i) const 55 { 56 return begin + i % diff; 57 } 58 namestriping59 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: 70 typedef random_number<random_uniform_fast> rnd_type; 71 rnd_type rnd; 72 73 public: FRFR74 FR(unsigned_type b, unsigned_type e) : striping(b, e) 75 { } 76 FRFR77 FR() : striping() 78 { } 79 operatorFR80 unsigned_type operator () (unsigned_type /*i*/) const 81 { 82 return begin + rnd(rnd_type::value_type(diff)); 83 } 84 nameFR85 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: 96 unsigned_type offset; 97 98 typedef random_number<random_uniform_fast> rnd_type; 99 initSR100 void init() 101 { 102 rnd_type rnd; 103 offset = rnd(rnd_type::value_type(diff)); 104 } 105 106 public: SRSR107 SR(unsigned_type b, unsigned_type e) : striping(b, e) 108 { 109 init(); 110 } 111 SRSR112 SR() : striping() 113 { 114 init(); 115 } 116 operatorSR117 unsigned_type operator () (unsigned_type i) const 118 { 119 return begin + (i + offset) % diff; 120 } 121 nameSR122 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 initRC135 void init() 136 { 137 for (unsigned_type i = 0; i < diff; i++) 138 perm[i] = i; 139 140 stxxl::random_number<random_uniform_fast> rnd; 141 std::random_shuffle(perm.begin(), perm.end(), rnd _STXXL_FORCE_SEQUENTIAL); 142 } 143 144 public: RCRC145 RC(unsigned_type b, unsigned_type e) : striping(b, e), perm(diff) 146 { 147 init(); 148 } 149 RCRC150 RC() : striping(), perm(diff) 151 { 152 init(); 153 } 154 operatorRC155 unsigned_type operator () (unsigned_type i) const 156 { 157 return begin + perm[i % diff]; 158 } 159 nameRC160 static const char * name() 161 { 162 return "randomized cycling striping"; 163 } 164 }; 165 166 struct RC_disk : public RC 167 { RC_diskRC_disk168 RC_disk(unsigned_type b, unsigned_type e) : RC(b, e) 169 { } 170 RC_diskRC_disk171 RC_disk() : RC(config::get_instance()->regular_disk_range().first, config::get_instance()->regular_disk_range().second) 172 { } 173 nameRC_disk174 static const char * name() 175 { 176 return "Randomized cycling striping on regular disks"; 177 } 178 }; 179 180 struct RC_flash : public RC 181 { RC_flashRC_flash182 RC_flash(unsigned_type b, unsigned_type e) : RC(b, e) 183 { } 184 RC_flashRC_flash185 RC_flash() : RC(config::get_instance()->flash_range().first, config::get_instance()->flash_range().second) 186 { } 187 nameRC_flash188 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 196 struct single_disk 197 { 198 unsigned_type disk; disksingle_disk199 single_disk(unsigned_type d, unsigned_type = 0) : disk(d) 200 { } 201 single_disksingle_disk202 single_disk() : disk(0) 203 { } 204 operatorsingle_disk205 unsigned_type operator () (unsigned_type /*i*/) const 206 { 207 return disk; 208 } 209 namesingle_disk210 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> 220 struct offset_allocator 221 { 222 BaseAllocator base; 223 int_type offset; 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 offset_allocatoroffset_allocator229 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 offset_allocatoroffset_allocator234 offset_allocator(const BaseAllocator& base_) : base(base_), offset(0) 235 { } 236 237 //! Creates functor based on default \c BaseAllocator functor. offset_allocatoroffset_allocator238 offset_allocator() : offset(0) 239 { } 240 operatoroffset_allocator241 unsigned_type operator () (unsigned_type i) const 242 { 243 return base(offset + i); 244 } 245 get_offsetoffset_allocator246 int_type get_offset() const 247 { 248 return offset; 249 } 250 set_offsetoffset_allocator251 void set_offset(int_type i) 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 263 STXXL_END_NAMESPACE 264 265 #endif // !STXXL_MNG_BLOCK_ALLOC_HEADER 266 // vim: et:ts=4:sw=4 267