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 : // Internal implementation details for OrderedBlockGraph. This is meant to be
16 : // included from ordered_block_graph.h only.
17 :
18 : #ifndef SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_INTERNAL_H_
19 : #define SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_INTERNAL_H_
20 :
21 : #include <utility>
22 : #include <vector>
23 :
24 : namespace block_graph {
25 :
26 : struct OrderedBlockGraph::SectionInfo {
27 : // The ordered section itself.
28 : OrderedSection ordered_section;
29 : // The iterator pointing to the SectionList node storing a pointer to
30 : // |ordered_section|.
31 : SectionList::iterator it;
32 :
33 : // A convenience function for getting the id associated with the enclosed
34 : // section.
35 E : BlockGraph::SectionId id() const { return ordered_section.id(); }
36 : };
37 :
38 : struct OrderedBlockGraph::BlockInfo {
39 : // The iterator pointing to the list node storing a block.
40 : BlockList::iterator it;
41 : // The ordered section owning the list to which the iterator belongs.
42 : OrderedSection* ordered_section;
43 : };
44 :
45 : namespace internal {
46 :
47 : // Sorts a linked list using the provided sort-functor, which must operate
48 : // on the iterators of the list.
49 : template<typename ListType, typename CompareFunctor>
50 : void SortList(CompareFunctor compare_functor, size_t size_hint,
51 E : ListType* list) {
52 E : DCHECK(list != NULL);
53 :
54 : // If the list is empty sort will complete, but --list->end() will blow up
55 : // below. Thus an early termination.
56 E : if (list->begin() == list->end())
57 E : return;
58 :
59 : typedef typename ListType::iterator Iterator;
60 E : std::vector<Iterator> its;
61 E : its.reserve(size_hint);
62 :
63 E : for (Iterator it = list->begin(); it != list->end(); ++it)
64 E : its.push_back(it);
65 :
66 E : std::sort(its.begin(), its.end(), compare_functor);
67 :
68 : // Relink the list in the same order. We use splice so that no reallocations
69 : // are performed.
70 E : if (its[0] != --list->end())
71 E : list->splice(list->end(), *list, its[0]);
72 E : for (size_t i = 1; i < its.size(); ++i)
73 E : list->splice(list->end(), *list, its[i]);
74 E : }
75 :
76 : // An adapter for comparing Sectionlist::iterator objects via the underlying
77 : // Section pointers.
78 : template<typename CompareFunctor>
79 : struct SectionListSortAdapter {
80 E : explicit SectionListSortAdapter(CompareFunctor compare_functor)
81 : : compare_functor_(compare_functor) { }
82 :
83 : bool operator()(OrderedBlockGraph::SectionList::iterator it1,
84 E : OrderedBlockGraph::SectionList::iterator it2) {
85 E : return compare_functor_((*it1)->section(), (*it2)->section());
86 E : }
87 :
88 : CompareFunctor compare_functor_;
89 : };
90 :
91 : // An adapter for comparing BlockList::iterator objects via the underlying
92 : // Block pointers.
93 : template<typename CompareFunctor>
94 : struct BlockListSortAdapter {
95 E : explicit BlockListSortAdapter(CompareFunctor compare_functor)
96 : : compare_functor_(compare_functor) {
97 E : }
98 :
99 : bool operator()(OrderedBlockGraph::BlockList::iterator it1,
100 E : OrderedBlockGraph::BlockList::iterator it2) {
101 E : return compare_functor_(*it1, *it2);
102 E : }
103 :
104 : CompareFunctor compare_functor_;
105 : };
106 :
107 : } // namespace internal
108 :
109 : template<typename SectionCompareFunctor>
110 E : void OrderedBlockGraph::Sort(SectionCompareFunctor section_compare_functor) {
111 : typedef internal::SectionListSortAdapter<SectionCompareFunctor> Adapter;
112 : internal::SortList(Adapter(section_compare_functor),
113 : section_infos_.size() - 1,
114 E : &ordered_sections_);
115 E : RebuildSectionIndex();
116 E : }
117 :
118 : template<typename BlockCompareFunctor>
119 : void OrderedBlockGraph::Sort(const Section* section,
120 E : BlockCompareFunctor block_compare_functor) {
121 E : SectionInfo* section_info = GetSectionInfo(section);
122 E : DCHECK(section_info != NULL);
123 :
124 : // Build an index which can be used to find the BlockInfo index from a
125 : // Block*.
126 : typedef std::vector<std::pair<Block*, size_t>> ReverseIndex;
127 E : ReverseIndex rindex;
128 E : BlockList& blocks(section_info->ordered_section.ordered_blocks_);
129 E : rindex.reserve(blocks.size());
130 E : BlockList::iterator it = blocks.begin();
131 E : for (; it != blocks.end(); ++it) {
132 E : Block* block = *it;
133 E : DCHECK(block != NULL);
134 :
135 E : BlockInfo* block_info = GetBlockInfo(block);
136 E : DCHECK(block_info != NULL);
137 :
138 E : size_t index = block_info - &block_infos_[0];
139 E : rindex.push_back(std::make_pair(block, index));
140 E : }
141 : // Sort this based on Block*, which std::pair does for us by default.
142 E : std::sort(rindex.begin(), rindex.end());
143 :
144 : typedef internal::BlockListSortAdapter<BlockCompareFunctor> Adapter;
145 : internal::SortList(Adapter(block_compare_functor),
146 : rindex.size(),
147 E : &blocks);
148 :
149 : // Rebuild the block index using the index to find the affected BlockInfo
150 : // entries.
151 E : for (it = blocks.begin(); it != blocks.end(); ++it) {
152 E : Block* block = *it;
153 E : DCHECK(block != NULL);
154 :
155 : ReverseIndex::const_iterator rindex_it = std::lower_bound(
156 : rindex.begin(), rindex.end(),
157 E : std::make_pair(block, static_cast<size_t>(0)));
158 E : DCHECK(rindex_it != rindex.end());
159 E : DCHECK_EQ(rindex_it->first, block);
160 :
161 E : block_infos_[rindex_it->second].it = it;
162 E : }
163 E : }
164 :
165 : } // namespace block_graph
166 :
167 : #endif // SYZYGY_BLOCK_GRAPH_ORDERED_BLOCK_GRAPH_INTERNAL_H_
|