OLD | NEW |
| (Empty) |
1 // Copyright 2016 the V8 project authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "src/wasm/switch-logic.h" | |
6 | |
7 namespace v8 { | |
8 namespace internal { | |
9 namespace wasm { | |
10 | |
11 namespace { | |
12 CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) { | |
13 if (end < begin) { | |
14 return nullptr; | |
15 } else if (end == begin) { | |
16 return nodes->at(begin); | |
17 } else { | |
18 size_t root_index = (begin + end) / 2; | |
19 CaseNode* root = nodes->at(root_index); | |
20 if (root_index != 0) { | |
21 root->left = CreateBst(nodes, begin, root_index - 1); | |
22 } | |
23 root->right = CreateBst(nodes, root_index + 1, end); | |
24 return root; | |
25 } | |
26 } | |
27 } // namespace | |
28 | |
29 CaseNode* OrderCases(ZoneVector<int>* cases, Zone* zone) { | |
30 const int max_distance = 2; | |
31 const int min_size = 4; | |
32 if (cases->empty()) { | |
33 return nullptr; | |
34 } | |
35 std::sort(cases->begin(), cases->end()); | |
36 ZoneVector<size_t> table_breaks(zone); | |
37 for (size_t i = 1; i < cases->size(); ++i) { | |
38 if (cases->at(i) - cases->at(i - 1) > max_distance) { | |
39 table_breaks.push_back(i); | |
40 } | |
41 } | |
42 table_breaks.push_back(cases->size()); | |
43 ZoneVector<CaseNode*> nodes(zone); | |
44 size_t curr_pos = 0; | |
45 for (size_t i = 0; i < table_breaks.size(); ++i) { | |
46 size_t break_pos = table_breaks[i]; | |
47 if (break_pos - curr_pos >= min_size) { | |
48 int begin = cases->at(curr_pos); | |
49 int end = cases->at(break_pos - 1); | |
50 nodes.push_back(new (zone) CaseNode(begin, end)); | |
51 curr_pos = break_pos; | |
52 } else { | |
53 for (; curr_pos < break_pos; curr_pos++) { | |
54 nodes.push_back(new (zone) | |
55 CaseNode(cases->at(curr_pos), cases->at(curr_pos))); | |
56 } | |
57 } | |
58 } | |
59 return CreateBst(&nodes, 0, nodes.size() - 1); | |
60 } | |
61 } // namespace wasm | |
62 } // namespace internal | |
63 } // namespace v8 | |
OLD | NEW |