Home | History | Annotate | Download | only in tools 
      1 // Copyright 2009 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 
     29 /**
     30  * Constructs a ConsArray object. It is used mainly for tree traversal.
     31  * In this use case we have lots of arrays that we need to iterate
     32  * sequentally. The internal Array implementation is horribly slow
     33  * when concatenating on large (10K items) arrays due to memory copying.
     34  * That's why we avoid copying memory and insead build a linked list
     35  * of arrays to iterate through.
     36  *
     37  * @constructor
     38  */
     39 function ConsArray() {
     40   this.tail_ = new ConsArray.Cell(null, null);
     41   this.currCell_ = this.tail_;
     42   this.currCellPos_ = 0;
     43 };
     44 
     45 
     46 /**
     47  * Concatenates another array for iterating. Empty arrays are ignored.
     48  * This operation can be safely performed during ongoing ConsArray
     49  * iteration.
     50  *
     51  * @param {Array} arr Array to concatenate.
     52  */
     53 ConsArray.prototype.concat = function(arr) {
     54   if (arr.length > 0) {
     55     this.tail_.data = arr;
     56     this.tail_ = this.tail_.next = new ConsArray.Cell(null, null);
     57   }
     58 };
     59 
     60 
     61 /**
     62  * Whether the end of iteration is reached.
     63  */
     64 ConsArray.prototype.atEnd = function() {
     65   return this.currCell_ === null ||
     66       this.currCell_.data === null ||
     67       this.currCellPos_ >= this.currCell_.data.length;
     68 };
     69 
     70 
     71 /**
     72  * Returns the current item, moves to the next one.
     73  */
     74 ConsArray.prototype.next = function() {
     75   var result = this.currCell_.data[this.currCellPos_++];
     76   if (this.currCellPos_ >= this.currCell_.data.length) {
     77     this.currCell_ = this.currCell_.next;
     78     this.currCellPos_ = 0;
     79   }
     80   return result;
     81 };
     82 
     83 
     84 /**
     85  * A cell object used for constructing a list in ConsArray.
     86  *
     87  * @constructor
     88  */
     89 ConsArray.Cell = function(data, next) {
     90   this.data = data;
     91   this.next = next;
     92 };
     93