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 <algorithm>
6
7 #include "src/asmjs/switch-logic.h"
8
9 namespace v8 {
10 namespace internal {
11 namespace wasm {
12
13 namespace {
CreateBst(ZoneVector<CaseNode * > * nodes,size_t begin,size_t end)14 CaseNode* CreateBst(ZoneVector<CaseNode*>* nodes, size_t begin, size_t end) {
15 if (end < begin) {
16 return nullptr;
17 } else if (end == begin) {
18 return nodes->at(begin);
19 } else {
20 size_t root_index = (begin + end) / 2;
21 CaseNode* root = nodes->at(root_index);
22 if (root_index != 0) {
23 root->left = CreateBst(nodes, begin, root_index - 1);
24 }
25 root->right = CreateBst(nodes, root_index + 1, end);
26 return root;
27 }
28 }
29 } // namespace
30
OrderCases(ZoneVector<int> * cases,Zone * zone)31 CaseNode* OrderCases(ZoneVector<int>* cases, Zone* zone) {
32 const int max_distance = 2;
33 const int min_size = 4;
34 if (cases->empty()) {
35 return nullptr;
36 }
37 std::sort(cases->begin(), cases->end());
38 ZoneVector<size_t> table_breaks(zone);
39 for (size_t i = 1; i < cases->size(); ++i) {
40 if (cases->at(i) - cases->at(i - 1) > max_distance) {
41 table_breaks.push_back(i);
42 }
43 }
44 table_breaks.push_back(cases->size());
45 ZoneVector<CaseNode*> nodes(zone);
46 size_t curr_pos = 0;
47 for (size_t i = 0; i < table_breaks.size(); ++i) {
48 size_t break_pos = table_breaks[i];
49 if (break_pos - curr_pos >= min_size) {
50 int begin = cases->at(curr_pos);
51 int end = cases->at(break_pos - 1);
52 nodes.push_back(new (zone) CaseNode(begin, end));
53 curr_pos = break_pos;
54 } else {
55 for (; curr_pos < break_pos; curr_pos++) {
56 nodes.push_back(new (zone)
57 CaseNode(cases->at(curr_pos), cases->at(curr_pos)));
58 }
59 }
60 }
61 return CreateBst(&nodes, 0, nodes.size() - 1);
62 }
63 } // namespace wasm
64 } // namespace internal
65 } // namespace v8
66