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