Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame^] | 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 |