blob: cb0ebacd3f56cf5964a2c54e662d4f06cd15a4bc [file] [log] [blame]
// Copyright 2012 Google Inc. All Rights Reserved.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
// Internal implementation details for OrderedBlockGraph. This is meant to be
// included from ordered_block_graph.h only.
#include <utility>
#include <vector>
namespace block_graph {
struct OrderedBlockGraph::SectionInfo {
// The ordered section itself.
OrderedSection ordered_section;
// The iterator pointing to the SectionList node storing a pointer to
// |ordered_section|.
SectionList::iterator it;
// A convenience function for getting the id associated with the enclosed
// section.
BlockGraph::SectionId id() const { return; }
struct OrderedBlockGraph::BlockInfo {
// The iterator pointing to the list node storing a block.
BlockList::iterator it;
// The ordered section owning the list to which the iterator belongs.
OrderedSection* ordered_section;
namespace internal {
// Sorts a linked list using the provided sort-functor, which must operate
// on the iterators of the list.
template<typename ListType, typename CompareFunctor>
void SortList(CompareFunctor compare_functor, size_t size_hint,
ListType* list) {
DCHECK(list != NULL);
// If the list is empty sort will complete, but --list->end() will blow up
// below. Thus an early termination.
if (list->begin() == list->end())
typedef typename ListType::iterator Iterator;
std::vector<Iterator> its;
for (Iterator it = list->begin(); it != list->end(); ++it)
std::sort(its.begin(), its.end(), compare_functor);
// Relink the list in the same order. We use splice so that no reallocations
// are performed.
if (its[0] != --list->end())
list->splice(list->end(), *list, its[0]);
for (size_t i = 1; i < its.size(); ++i)
list->splice(list->end(), *list, its[i]);
// An adapter for comparing Sectionlist::iterator objects via the underlying
// Section pointers.
template<typename CompareFunctor>
struct SectionListSortAdapter {
explicit SectionListSortAdapter(CompareFunctor compare_functor)
: compare_functor_(compare_functor) { }
bool operator()(OrderedBlockGraph::SectionList::iterator it1,
OrderedBlockGraph::SectionList::iterator it2) {
return compare_functor_((*it1)->section(), (*it2)->section());
CompareFunctor compare_functor_;
// An adapter for comparing BlockList::iterator objects via the underlying
// Block pointers.
template<typename CompareFunctor>
struct BlockListSortAdapter {
explicit BlockListSortAdapter(CompareFunctor compare_functor)
: compare_functor_(compare_functor) {
bool operator()(OrderedBlockGraph::BlockList::iterator it1,
OrderedBlockGraph::BlockList::iterator it2) {
return compare_functor_(*it1, *it2);
CompareFunctor compare_functor_;
} // namespace internal
template<typename SectionCompareFunctor>
void OrderedBlockGraph::Sort(SectionCompareFunctor section_compare_functor) {
typedef internal::SectionListSortAdapter<SectionCompareFunctor> Adapter;
section_infos_.size() - 1,
template<typename BlockCompareFunctor>
void OrderedBlockGraph::Sort(const Section* section,
BlockCompareFunctor block_compare_functor) {
SectionInfo* section_info = GetSectionInfo(section);
DCHECK(section_info != NULL);
// Build an index which can be used to find the BlockInfo index from a
// Block*.
typedef std::vector<std::pair<Block*, size_t>> ReverseIndex;
ReverseIndex rindex;
BlockList& blocks(section_info->ordered_section.ordered_blocks_);
BlockList::iterator it = blocks.begin();
for (; it != blocks.end(); ++it) {
Block* block = *it;
DCHECK(block != NULL);
BlockInfo* block_info = GetBlockInfo(block);
DCHECK(block_info != NULL);
size_t index = block_info - &block_infos_[0];
rindex.push_back(std::make_pair(block, index));
// Sort this based on Block*, which std::pair does for us by default.
std::sort(rindex.begin(), rindex.end());
typedef internal::BlockListSortAdapter<BlockCompareFunctor> Adapter;
// Rebuild the block index using the index to find the affected BlockInfo
// entries.
for (it = blocks.begin(); it != blocks.end(); ++it) {
Block* block = *it;
DCHECK(block != NULL);
ReverseIndex::const_iterator rindex_it = std::lower_bound(
rindex.begin(), rindex.end(),
std::make_pair(block, static_cast<size_t>(0)));
DCHECK(rindex_it != rindex.end());
DCHECK_EQ(rindex_it->first, block);
block_infos_[rindex_it->second].it = it;
} // namespace block_graph