1    :  // Copyright 2012 Google Inc. All Rights Reserved.
   2    :  //
   3    :  // Licensed under the Apache License, Version 2.0 (the "License");
   4    :  // you may not use this file except in compliance with the License.
   5    :  // You may obtain a copy of the License at
   6    :  //
   7    :  //     http://www.apache.org/licenses/LICENSE-2.0
   8    :  //
   9    :  // Unless required by applicable law or agreed to in writing, software
  10    :  // distributed under the License is distributed on an "AS IS" BASIS,
  11    :  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12    :  // See the License for the specific language governing permissions and
  13    :  // limitations under the License.
  14    :  
  15    :  #include "syzygy/block_graph/orderers/random_orderer.h"
  16    :  
  17    :  #include <time.h>
  18    :  
  19    :  namespace block_graph {
  20    :  namespace orderers {
  21    :  
  22    :  const char RandomOrderer::kOrdererName[] = "RandomOrderer";
  23    :  
  24    :  RandomOrderer::RandomOrderer(bool default_shuffle_section)
  25    :      : default_shuffle_section_(default_shuffle_section),
  26  E :        rng_(static_cast<uint32>(time(NULL))) {
  27  E :  }
  28    :  
  29    :  RandomOrderer::RandomOrderer(bool default_shuffle_section, uint32 seed)
  30  E :      : default_shuffle_section_(default_shuffle_section), rng_(seed) {
  31  E :  }
  32    :  
  33    :  void RandomOrderer::SetShuffleSection(const BlockGraph::Section* section,
  34  E :                                        bool shuffle) {
  35  E :    DCHECK(section != NULL);
  36  E :    shuffle_map_[section] = shuffle;
  37  E :  }
  38    :  
  39    :  bool RandomOrderer::ShouldShuffleSection(
  40  E :      const BlockGraph::Section* section) const {
  41    :    // Look for an overridden value, otherwise use the default.
  42  E :    ShuffleMap::const_iterator shuffle_map_it = shuffle_map_.find(section);
  43  E :    if (shuffle_map_it != shuffle_map_.end())
  44  E :      return shuffle_map_it->second;
  45  E :    return default_shuffle_section_;
  46  E :  }
  47    :  
  48    :  bool RandomOrderer::OrderBlockGraph(OrderedBlockGraph* ordered_block_graph,
  49  E :                                      BlockGraph::Block* /* header_block */) {
  50  E :    DCHECK(ordered_block_graph != NULL);
  51    :  
  52    :    // Run through the sections shuffling those that we need to.
  53    :    OrderedBlockGraph::SectionList::const_iterator section_it =
  54  E :        ordered_block_graph->ordered_sections().begin();
  55  E :    for (; section_it != ordered_block_graph->ordered_sections().end();
  56  E :         ++section_it) {
  57  E :      const BlockGraph::Section* section = (*section_it)->section();
  58    :  
  59    :      // Shuffle the sections.
  60  E :      if (ShouldShuffleSection(section))
  61  E :        ShuffleBlocks(*section_it, ordered_block_graph);
  62  E :    }
  63    :  
  64  E :    return true;
  65  E :  }
  66    :  
  67    :  void RandomOrderer::ShuffleBlocks(
  68  E :      const OrderedBlockGraph::OrderedSection* section, OrderedBlockGraph* obg) {
  69  E :    DCHECK(section != NULL);
  70    :  
  71    :    BlockVector blocks(section->ordered_blocks().begin(),
  72  E :                       section->ordered_blocks().end());
  73  E :    std::random_shuffle(blocks.begin(), blocks.end(), rng_);
  74    :  
  75  E :    for (size_t i = 0; i < blocks.size(); ++i)
  76  E :      obg->PlaceAtTail(section->section(), blocks[i]);
  77  E :  }
  78    :  
  79    :  }  // namespace orderers
  80    :  }  // namespace block_graph