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/ordered_block_graph.h"
16 :
17 : #include "base/strings/stringprintf.h"
18 : #include "gmock/gmock.h"
19 : #include "gtest/gtest.h"
20 :
21 : namespace block_graph {
22 :
23 : using testing::ElementsAre;
24 :
25 : namespace {
26 :
27 : // A functor for comparing two blocks based on their size.
28 : struct BlockSizeCompareFunctor {
29 : bool operator()(const BlockGraph::Block* block1,
30 E : const BlockGraph::Block* block2) const {
31 E : DCHECK(block1 != NULL);
32 E : DCHECK(block2 != NULL);
33 E : return block1->size() < block2->size();
34 E : }
35 : };
36 :
37 : // A functor for comparing two sections based on their name. Reverses the
38 : // sort order.
39 : struct ReverseSectionNameCompareFunctor {
40 : bool operator()(const BlockGraph::Section* section1,
41 E : const BlockGraph::Section* section2) const {
42 E : DCHECK(section1 != NULL);
43 E : DCHECK(section2 != NULL);
44 E : return section1->name() > section2->name();
45 E : }
46 : };
47 :
48 E : template<typename C> std::vector<size_t> GetIds(const C& c) {
49 E : std::vector<size_t> ids;
50 E : typename C::const_iterator it = c.begin();
51 E : for (; it != c.end(); ++it)
52 E : ids.push_back((*it)->id());
53 E : return ids;
54 E : }
55 :
56 : const OrderedBlockGraph::BlockList& GetSectionBlockList(
57 E : const OrderedBlockGraph& obg, size_t section_id) {
58 : const BlockGraph::Section* section =
59 E : obg.block_graph()->GetSectionById(section_id);
60 E : return obg.ordered_section(section).ordered_blocks();
61 E : }
62 :
63 : #define EXPECT_SECTION_ORDER(obg, ...) \
64 : EXPECT_THAT(GetIds(obg.ordered_sections()), ElementsAre(__VA_ARGS__))
65 :
66 : #define EXPECT_SECTION_CONTAINS(obg, section_id, ...) \
67 : EXPECT_THAT(GetIds(GetSectionBlockList(obg, section_id)), \
68 : ElementsAre(__VA_ARGS__))
69 :
70 : class TestOrderedBlockGraph : public OrderedBlockGraph {
71 : public:
72 E : explicit TestOrderedBlockGraph(BlockGraph* block_graph)
73 : : OrderedBlockGraph(block_graph) { }
74 :
75 E : bool IndicesAreValid() {
76 E : SectionList::iterator section_it = ordered_sections_.begin();
77 E : for (; section_it != ordered_sections_.end(); ++section_it) {
78 E : SectionInfo* section_info = GetSectionInfo((*section_it)->section());
79 E : if (section_info == NULL || section_info->it != section_it)
80 i : return false;
81 :
82 : const BlockList& ordered_blocks(
83 E : section_info->ordered_section.ordered_blocks());
84 E : BlockList::const_iterator block_it = ordered_blocks.begin();
85 E : for (; block_it != ordered_blocks.end(); ++block_it) {
86 E : BlockInfo* block_info = GetBlockInfo(*block_it);
87 E : if (block_info == NULL || block_info->it != block_it)
88 i : return false;
89 E : }
90 E : }
91 :
92 E : return true;
93 E : }
94 : };
95 :
96 : class OrderedBlockGraphTest : public testing::Test {
97 : public:
98 E : virtual void SetUp() {
99 E : }
100 :
101 : // Creates a bunch of blocks in a bunch of sections. The blocks will be
102 : // distributed to the section in order of increasing block ID, with blocks
103 : // not in any section coming last. The sizes of the blocks will be inversely
104 : // related to their ID.
105 : void InitBlockGraph(size_t sections,
106 : size_t blocks_per_section,
107 E : size_t blocks_no_section) {
108 E : size_t block_count = 0;
109 : const size_t kTotalBlockCount = sections * blocks_per_section +
110 E : blocks_no_section;
111 :
112 : // Create sections and blocks in each section.
113 E : for (size_t i = 0; i < sections; ++i) {
114 : BlockGraph::Section* section = block_graph_.AddSection(
115 E : base::StringPrintf("s%d", i), 0);
116 E : ASSERT_TRUE(section);
117 E : for (size_t j = 0; j < blocks_per_section; ++j) {
118 : BlockGraph::Block* block = block_graph_.AddBlock(
119 : BlockGraph::DATA_BLOCK, 10 + kTotalBlockCount - block_count,
120 E : base::StringPrintf("b%d", block_count));
121 E : ASSERT_TRUE(block);
122 E : block->set_section(section->id());
123 E : ++block_count;
124 E : }
125 E : }
126 :
127 : // Create blocks not in any section.
128 E : for (size_t i = 0; i < blocks_no_section; ++i) {
129 : BlockGraph::Block* block = block_graph_.AddBlock(
130 : BlockGraph::DATA_BLOCK, 10 + kTotalBlockCount - block_count,
131 E : base::StringPrintf("b%d", block_count));
132 E : ASSERT_TRUE(block);
133 E : ++block_count;
134 E : }
135 E : }
136 :
137 : BlockGraph block_graph_;
138 : };
139 :
140 : } // namespace
141 :
142 E : TEST_F(OrderedBlockGraphTest, CreateEmpty) {
143 E : TestOrderedBlockGraph ordered(&block_graph_);
144 E : EXPECT_TRUE(ordered.IndicesAreValid());
145 E : }
146 :
147 E : TEST_F(OrderedBlockGraphTest, CreateNonEmpty) {
148 E : InitBlockGraph(3, 3, 3);
149 E : TestOrderedBlockGraph ordered(&block_graph_);
150 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
151 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1, 2, 3);
152 E : EXPECT_SECTION_CONTAINS(ordered, 1, 4, 5, 6);
153 E : EXPECT_SECTION_CONTAINS(ordered, 2, 7, 8, 9);
154 : EXPECT_SECTION_CONTAINS(ordered, BlockGraph::kInvalidSectionId,
155 E : 10, 11, 12);
156 E : EXPECT_TRUE(ordered.IndicesAreValid());
157 E : }
158 :
159 E : TEST_F(OrderedBlockGraphTest, SectionPlaceAtHead) {
160 E : InitBlockGraph(3, 0, 0);
161 E : TestOrderedBlockGraph ordered(&block_graph_);
162 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
163 E : BlockGraph::Section* section0 = block_graph_.GetSectionById(0);
164 E : BlockGraph::Section* section1 = block_graph_.GetSectionById(1);
165 :
166 : // This should be a noop.
167 E : ordered.PlaceAtHead(section0);
168 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
169 E : EXPECT_TRUE(ordered.IndicesAreValid());
170 :
171 : // This should move a section.
172 E : ordered.PlaceAtHead(section1);
173 E : EXPECT_SECTION_ORDER(ordered, 1, 0, 2);
174 E : EXPECT_TRUE(ordered.IndicesAreValid());
175 E : }
176 :
177 E : TEST_F(OrderedBlockGraphTest, SectionPlaceAtTail) {
178 E : InitBlockGraph(3, 0, 0);
179 E : TestOrderedBlockGraph ordered(&block_graph_);
180 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
181 E : BlockGraph::Section* section1 = block_graph_.GetSectionById(1);
182 E : BlockGraph::Section* section2 = block_graph_.GetSectionById(2);
183 :
184 : // This should be a noop.
185 E : ordered.PlaceAtTail(section2);
186 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
187 E : EXPECT_TRUE(ordered.IndicesAreValid());
188 :
189 : // This should move a section.
190 E : ordered.PlaceAtTail(section1);
191 E : EXPECT_SECTION_ORDER(ordered, 0, 2, 1);
192 E : EXPECT_TRUE(ordered.IndicesAreValid());
193 E : }
194 :
195 E : TEST_F(OrderedBlockGraphTest, SectionPlaceBefore) {
196 E : InitBlockGraph(3, 0, 0);
197 E : TestOrderedBlockGraph ordered(&block_graph_);
198 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
199 E : BlockGraph::Section* section1 = block_graph_.GetSectionById(1);
200 E : BlockGraph::Section* section2 = block_graph_.GetSectionById(2);
201 :
202 : // This should be a noop.
203 E : ordered.PlaceBefore(section2, section1);
204 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
205 E : EXPECT_TRUE(ordered.IndicesAreValid());
206 :
207 : // This should move a section.
208 E : ordered.PlaceBefore(section1, section2);
209 E : EXPECT_SECTION_ORDER(ordered, 0, 2, 1);
210 E : EXPECT_TRUE(ordered.IndicesAreValid());
211 E : }
212 :
213 E : TEST_F(OrderedBlockGraphTest, SectionPlaceAfter) {
214 E : InitBlockGraph(3, 0, 0);
215 E : TestOrderedBlockGraph ordered(&block_graph_);
216 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
217 E : BlockGraph::Section* section0 = block_graph_.GetSectionById(0);
218 E : BlockGraph::Section* section1 = block_graph_.GetSectionById(1);
219 :
220 : // This should be a noop.
221 E : ordered.PlaceAfter(section0, section1);
222 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
223 E : EXPECT_TRUE(ordered.IndicesAreValid());
224 :
225 : // This should move a section.
226 E : ordered.PlaceAfter(section1, section0);
227 E : EXPECT_SECTION_ORDER(ordered, 1, 0, 2);
228 E : EXPECT_TRUE(ordered.IndicesAreValid());
229 E : }
230 :
231 E : TEST_F(OrderedBlockGraphTest, SectionSortEmpty) {
232 E : InitBlockGraph(0, 0, 0);
233 E : TestOrderedBlockGraph ordered(&block_graph_);
234 E : ordered.Sort(ReverseSectionNameCompareFunctor());
235 E : }
236 :
237 E : TEST_F(OrderedBlockGraphTest, SectionSort) {
238 E : InitBlockGraph(3, 0, 0);
239 E : TestOrderedBlockGraph ordered(&block_graph_);
240 E : EXPECT_SECTION_ORDER(ordered, 0, 1, 2);
241 E : EXPECT_TRUE(ordered.IndicesAreValid());
242 :
243 E : ordered.Sort(ReverseSectionNameCompareFunctor());
244 E : EXPECT_SECTION_ORDER(ordered, 2, 1, 0);
245 E : EXPECT_TRUE(ordered.IndicesAreValid());
246 E : }
247 :
248 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAtHead) {
249 E : InitBlockGraph(0, 0, 3);
250 E : TestOrderedBlockGraph ordered(&block_graph_);
251 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
252 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
253 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
254 :
255 : // This should be a noop.
256 E : ordered.PlaceAtHead(NULL, block1);
257 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
258 E : EXPECT_TRUE(ordered.IndicesAreValid());
259 :
260 : // This should move a block.
261 E : ordered.PlaceAtHead(NULL, block2);
262 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 2, 1, 3);
263 E : EXPECT_TRUE(ordered.IndicesAreValid());
264 E : }
265 :
266 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAtTail) {
267 E : InitBlockGraph(0, 0, 3);
268 E : TestOrderedBlockGraph ordered(&block_graph_);
269 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
270 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
271 E : BlockGraph::Block* block3 = block_graph_.GetBlockById(3);
272 :
273 : // This should be a noop.
274 E : ordered.PlaceAtTail(NULL, block3);
275 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
276 E : EXPECT_TRUE(ordered.IndicesAreValid());
277 :
278 : // This should move a block.
279 E : ordered.PlaceAtTail(NULL, block2);
280 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 3, 2);
281 E : EXPECT_TRUE(ordered.IndicesAreValid());
282 E : }
283 :
284 E : TEST_F(OrderedBlockGraphTest, BlockPlaceBefore) {
285 E : InitBlockGraph(0, 0, 3);
286 E : TestOrderedBlockGraph ordered(&block_graph_);
287 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
288 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
289 E : BlockGraph::Block* block3 = block_graph_.GetBlockById(3);
290 :
291 : // This should be a noop.
292 E : ordered.PlaceBefore(block3, block2);
293 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
294 E : EXPECT_TRUE(ordered.IndicesAreValid());
295 :
296 : // This should move a block.
297 E : ordered.PlaceBefore(block2, block3);
298 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 3, 2);
299 E : EXPECT_TRUE(ordered.IndicesAreValid());
300 E : }
301 :
302 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAfter) {
303 E : InitBlockGraph(0, 0, 3);
304 E : TestOrderedBlockGraph ordered(&block_graph_);
305 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
306 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
307 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
308 :
309 : // This should be a noop.
310 E : ordered.PlaceAfter(block1, block2);
311 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
312 E : EXPECT_TRUE(ordered.IndicesAreValid());
313 :
314 : // This should move a block.
315 E : ordered.PlaceAfter(block2, block1);
316 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 2, 1, 3);
317 E : EXPECT_TRUE(ordered.IndicesAreValid());
318 E : }
319 :
320 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAtHeadDifferentSection) {
321 E : InitBlockGraph(2, 1, 0);
322 E : TestOrderedBlockGraph ordered(&block_graph_);
323 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1);
324 E : EXPECT_SECTION_CONTAINS(ordered, 1, 2);
325 E : BlockGraph::Section* section0 = block_graph_.GetSectionById(0);
326 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
327 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
328 E : EXPECT_EQ(block1->section(), 0);
329 E : EXPECT_EQ(block2->section(), 1);
330 E : ordered.PlaceAtHead(section0, block2);
331 E : EXPECT_EQ(block1->section(), 0);
332 E : EXPECT_EQ(block2->section(), 0);
333 E : EXPECT_SECTION_CONTAINS(ordered, 0, 2, 1);
334 E : EXPECT_SECTION_CONTAINS(ordered, 1);
335 E : EXPECT_TRUE(ordered.IndicesAreValid());
336 E : }
337 :
338 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAtTailDifferentSection) {
339 E : InitBlockGraph(2, 1, 0);
340 E : TestOrderedBlockGraph ordered(&block_graph_);
341 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1);
342 E : EXPECT_SECTION_CONTAINS(ordered, 1, 2);
343 E : BlockGraph::Section* section0 = block_graph_.GetSectionById(0);
344 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
345 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
346 E : EXPECT_EQ(block1->section(), 0);
347 E : EXPECT_EQ(block2->section(), 1);
348 E : ordered.PlaceAtTail(section0, block2);
349 E : EXPECT_EQ(block1->section(), 0);
350 E : EXPECT_EQ(block2->section(), 0);
351 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1, 2);
352 E : EXPECT_SECTION_CONTAINS(ordered, 1);
353 E : EXPECT_TRUE(ordered.IndicesAreValid());
354 E : }
355 :
356 E : TEST_F(OrderedBlockGraphTest, BlockPlaceBeforeDifferentSection) {
357 E : InitBlockGraph(2, 1, 0);
358 E : TestOrderedBlockGraph ordered(&block_graph_);
359 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1);
360 E : EXPECT_SECTION_CONTAINS(ordered, 1, 2);
361 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
362 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
363 E : EXPECT_EQ(block1->section(), 0);
364 E : EXPECT_EQ(block2->section(), 1);
365 E : ordered.PlaceBefore(block1, block2);
366 E : EXPECT_EQ(block1->section(), 0);
367 E : EXPECT_EQ(block2->section(), 0);
368 E : EXPECT_SECTION_CONTAINS(ordered, 0, 2, 1);
369 E : EXPECT_SECTION_CONTAINS(ordered, 1);
370 E : EXPECT_TRUE(ordered.IndicesAreValid());
371 E : }
372 :
373 E : TEST_F(OrderedBlockGraphTest, BlockPlaceAfterDifferentSection) {
374 E : InitBlockGraph(2, 1, 0);
375 E : TestOrderedBlockGraph ordered(&block_graph_);
376 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1);
377 E : EXPECT_SECTION_CONTAINS(ordered, 1, 2);
378 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
379 E : BlockGraph::Block* block2 = block_graph_.GetBlockById(2);
380 E : EXPECT_EQ(block1->section(), 0);
381 E : EXPECT_EQ(block2->section(), 1);
382 E : ordered.PlaceAfter(block1, block2);
383 E : EXPECT_EQ(block1->section(), 0);
384 E : EXPECT_EQ(block2->section(), 0);
385 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1, 2);
386 E : EXPECT_SECTION_CONTAINS(ordered, 1);
387 E : EXPECT_TRUE(ordered.IndicesAreValid());
388 E : }
389 :
390 E : TEST_F(OrderedBlockGraphTest, BlockChangeToAnotherSectionAndBack) {
391 E : InitBlockGraph(2, 1, 0);
392 E : TestOrderedBlockGraph ordered(&block_graph_);
393 E : EXPECT_SECTION_CONTAINS(ordered, 0, 1);
394 E : EXPECT_SECTION_CONTAINS(ordered, 1, 2);
395 :
396 E : BlockGraph::Section* section0 = block_graph_.GetSectionById(0);
397 E : BlockGraph::Section* section1 = block_graph_.GetSectionById(1);
398 E : BlockGraph::Block* block1 = block_graph_.GetBlockById(1);
399 E : EXPECT_EQ(block1->section(), 0);
400 :
401 : // Move from section0 to section1, and back to section0.
402 E : ordered.PlaceAtHead(section1, block1);
403 E : ordered.PlaceAtHead(section0, block1);
404 E : }
405 :
406 E : TEST_F(OrderedBlockGraphTest, BlockEmpty) {
407 E : InitBlockGraph(0, 0, 0);
408 E : TestOrderedBlockGraph ordered(&block_graph_);
409 E : ordered.Sort(NULL, BlockSizeCompareFunctor());
410 E : }
411 :
412 E : TEST_F(OrderedBlockGraphTest, BlockSort) {
413 E : InitBlockGraph(0, 0, 3);
414 E : TestOrderedBlockGraph ordered(&block_graph_);
415 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 1, 2, 3);
416 E : ordered.Sort(NULL, BlockSizeCompareFunctor());
417 E : EXPECT_SECTION_CONTAINS(ordered, NULL, 3, 2, 1);
418 E : EXPECT_TRUE(ordered.IndicesAreValid());
419 E : }
420 :
421 : } // namespace block_graph
|