Line data    Source code

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