• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 {
CreateBst(ZoneVector<CaseNode * > * nodes,size_t begin,size_t end)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 
OrderCases(ZoneVector<int> * cases,Zone * zone)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