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/asmjs/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 64
