| 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 |