From d1a674f7c1cbeb1851a7516a4eb6a3ce65bf6f66 Mon Sep 17 00:00:00 2001 From: "lrn@chromium.org" Date: Thu, 9 Sep 2010 12:57:32 +0000 Subject: [PATCH] Add sparse array handling to Array.protoype.indexOf/lastIndexOf. Review URL: http://codereview.chromium.org/3132046 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5432 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/array.js | 63 +++++++++++++++++++--- src/runtime.cc | 6 ++- test/mjsunit/array-indexing.js | 115 +++++++++++++++++++++++++++++++++++------ 3 files changed, 159 insertions(+), 25 deletions(-) diff --git a/src/array.js b/src/array.js index e12df64..b2ebece 100644 --- a/src/array.js +++ b/src/array.js @@ -957,14 +957,41 @@ function ArrayIndexOf(element, index) { // If index is still negative, search the entire array. if (index < 0) index = 0; } + var min = index; + var max = length; + if (UseSparseVariant(this, length, true)) { + var intervals = %GetArrayKeys(this, length); + if (intervals.length == 2 && intervals[0] < 0) { + // A single interval. + var intervalMin = -(intervals[0] + 1); + var intervalMax = intervalMin + intervals[1]; + min = MAX(min, intervalMin); + max = intervalMax; // Capped by length already. + // Fall through to loop below. + } else { + if (intervals.length == 0) return -1; + // Get all the keys in sorted order. + var sortedKeys = GetSortedArrayKeys(this, intervals); + var n = sortedKeys.length; + var i = 0; + while (i < n && sortedKeys[i] < index) i++; + while (i < n) { + var key = sortedKeys[i]; + if (!IS_UNDEFINED(key) && this[key] === element) return key; + i++; + } + return -1; + } + } // Lookup through the array. if (!IS_UNDEFINED(element)) { - for (var i = index; i < length; i++) { + for (var i = min; i < max; i++) { if (this[i] === element) return i; } return -1; } - for (var i = index; i < length; i++) { + // Lookup through the array. + for (var i = min; i < max; i++) { if (IS_UNDEFINED(this[i]) && i in this) { return i; } @@ -981,19 +1008,43 @@ function ArrayLastIndexOf(element, index) { } else { index = TO_INTEGER(index); // If index is negative, index from end of the array. - if (index < 0) index = length + index; + if (index < 0) index += length; // If index is still negative, do not search the array. - if (index < 0) index = -1; + if (index < 0) return -1; else if (index >= length) index = length - 1; } + var min = 0; + var max = index; + if (UseSparseVariant(this, length, true)) { + var intervals = %GetArrayKeys(this, index + 1); + if (intervals.length == 2 && intervals[0] < 0) { + // A single interval. + var intervalMin = -(intervals[0] + 1); + var intervalMax = intervalMin + intervals[1]; + min = MAX(min, intervalMin); + max = intervalMax; // Capped by index already. + // Fall through to loop below. + } else { + if (intervals.length == 0) return -1; + // Get all the keys in sorted order. + var sortedKeys = GetSortedArrayKeys(this, intervals); + var i = sortedKeys.length - 1; + while (i >= 0) { + var key = sortedKeys[i]; + if (!IS_UNDEFINED(key) && this[key] === element) return key; + i--; + } + return -1; + } + } // Lookup through the array. if (!IS_UNDEFINED(element)) { - for (var i = index; i >= 0; i--) { + for (var i = max; i >= min; i--) { if (this[i] === element) return i; } return -1; } - for (var i = index; i >= 0; i--) { + for (var i = max; i >= min; i--) { if (IS_UNDEFINED(this[i]) && i in this) { return i; } diff --git a/src/runtime.cc b/src/runtime.cc index 1c4e2e1..f9c2e5b 100644 --- a/src/runtime.cc +++ b/src/runtime.cc @@ -8022,8 +8022,10 @@ static Object* Runtime_SwapElements(Arguments args) { // Returns an array that tells you where in the [0, length) interval an array -// might have elements. Can either return keys or intervals. Keys can have -// gaps in (undefined). Intervals can also span over some undefined keys. +// might have elements. Can either return keys (positive integers) or +// intervals (pair of a negative integer (-start-1) followed by a +// positive (length)) or undefined values. +// Intervals can span over some keys that are not in the object. static Object* Runtime_GetArrayKeys(Arguments args) { ASSERT(args.length() == 2); HandleScope scope; diff --git a/test/mjsunit/array-indexing.js b/test/mjsunit/array-indexing.js index 2322c54..180a4d6 100644 --- a/test/mjsunit/array-indexing.js +++ b/test/mjsunit/array-indexing.js @@ -26,41 +26,122 @@ // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. var array = [1,2,3,1,2,3,1,2,3,1,2,3]; +var undef_array = [0,,2,undefined,4,,6,undefined,8,,10]; +// Sparse arrays with lenght 42000. +var sparse_array = []; +sparse_array[100] = 3; +sparse_array[200] = undefined; +sparse_array[300] = 4; +sparse_array[400] = 5; +sparse_array[500] = 6; +sparse_array[600] = 5; +sparse_array[700] = 4; +sparse_array[800] = undefined; +sparse_array[900] = 3 +sparse_array[41999] = "filler"; // ---------------------------------------------------------------------- // Array.prototype.indexOf. // ---------------------------------------------------------------------- // Negative cases. -assertEquals([].indexOf(1), -1); -assertEquals(array.indexOf(4), -1); -assertEquals(array.indexOf(3, array.length), -1); +assertEquals(-1, [].indexOf(1)); +assertEquals(-1, array.indexOf(4)); +assertEquals(-1, array.indexOf(3, array.length)); -assertEquals(array.indexOf(3), 2); +assertEquals(2, array.indexOf(3)); // Negative index out of range. -assertEquals(array.indexOf(1, -17), 0); +assertEquals(0, array.indexOf(1, -17)); // Negative index in rage. -assertEquals(array.indexOf(1, -11), 3); +assertEquals(3, array.indexOf(1, -11)); // Index in range. -assertEquals(array.indexOf(1, 1), 3); -assertEquals(array.indexOf(1, 3), 3); -assertEquals(array.indexOf(1, 4), 6); +assertEquals(3, array.indexOf(1, 1)); +assertEquals(3, array.indexOf(1, 3)); +assertEquals(6, array.indexOf(1, 4)); + +// Find undefined, not holes. +assertEquals(3, undef_array.indexOf(undefined)); +assertEquals(3, undef_array.indexOf(undefined, 3)); +assertEquals(7, undef_array.indexOf(undefined, 4)); +assertEquals(7, undef_array.indexOf(undefined, 7)); +assertEquals(-1, undef_array.indexOf(undefined, 8)); +assertEquals(3, undef_array.indexOf(undefined, -11)); +assertEquals(3, undef_array.indexOf(undefined, -8)); +assertEquals(7, undef_array.indexOf(undefined, -7)); +assertEquals(7, undef_array.indexOf(undefined, -4)); +assertEquals(-1, undef_array.indexOf(undefined, -3)); + +// Find in sparse array. +assertEquals(100, sparse_array.indexOf(3)); +assertEquals(900, sparse_array.indexOf(3, 101)); +assertEquals(-1, sparse_array.indexOf(3, 901)); +assertEquals(100, sparse_array.indexOf(3, -42000)); +assertEquals(900, sparse_array.indexOf(3, 101 - 42000)); +assertEquals(-1, sparse_array.indexOf(3, 901 - 42000)); + +assertEquals(300, sparse_array.indexOf(4)); +assertEquals(700, sparse_array.indexOf(4, 301)); +assertEquals(-1, sparse_array.indexOf(4, 701)); +assertEquals(300, sparse_array.indexOf(4, -42000)); +assertEquals(700, sparse_array.indexOf(4, 301 - 42000)); +assertEquals(-1, sparse_array.indexOf(4, 701 - 42000)); + +assertEquals(200, sparse_array.indexOf(undefined)); +assertEquals(800, sparse_array.indexOf(undefined, 201)); +assertEquals(-1, sparse_array.indexOf(undefined, 801)); +assertEquals(200, sparse_array.indexOf(undefined, -42000)); +assertEquals(800, sparse_array.indexOf(undefined, 201 - 42000)); +assertEquals(-1, sparse_array.indexOf(undefined, 801 - 42000)); + // ---------------------------------------------------------------------- // Array.prototype.lastIndexOf. // ---------------------------------------------------------------------- // Negative cases. -assertEquals([].lastIndexOf(1), -1); -assertEquals(array.lastIndexOf(1, -17), -1); +assertEquals(-1, [].lastIndexOf(1)); +assertEquals(-1, array.lastIndexOf(1, -17)); -assertEquals(array.lastIndexOf(1), 9); +assertEquals(9, array.lastIndexOf(1)); // Index out of range. -assertEquals(array.lastIndexOf(1, array.length), 9); +assertEquals(9, array.lastIndexOf(1, array.length)); // Index in range. -assertEquals(array.lastIndexOf(1, 2), 0); -assertEquals(array.lastIndexOf(1, 4), 3); -assertEquals(array.lastIndexOf(1, 3), 3); +assertEquals(0, array.lastIndexOf(1, 2)); +assertEquals(3, array.lastIndexOf(1, 4)); +assertEquals(3, array.lastIndexOf(1, 3)); // Negative index in range. -assertEquals(array.lastIndexOf(1, -11), 0); +assertEquals(0, array.lastIndexOf(1, -11)); + +// Find undefined, not holes. +assertEquals(7, undef_array.lastIndexOf(undefined)); +assertEquals(-1, undef_array.lastIndexOf(undefined, 2)); +assertEquals(3, undef_array.lastIndexOf(undefined, 3)); +assertEquals(3, undef_array.lastIndexOf(undefined, 6)); +assertEquals(7, undef_array.lastIndexOf(undefined, 7)); +assertEquals(7, undef_array.lastIndexOf(undefined, -1)); +assertEquals(-1, undef_array.lastIndexOf(undefined, -9)); +assertEquals(3, undef_array.lastIndexOf(undefined, -8)); +assertEquals(3, undef_array.lastIndexOf(undefined, -5)); +assertEquals(7, undef_array.lastIndexOf(undefined, -4)); + +// Find in sparse array. +assertEquals(900, sparse_array.lastIndexOf(3)); +assertEquals(100, sparse_array.lastIndexOf(3, 899)); +assertEquals(-1, sparse_array.lastIndexOf(3, 99)); +assertEquals(900, sparse_array.lastIndexOf(3, -1)); +assertEquals(100, sparse_array.lastIndexOf(3, 899 - 42000)); +assertEquals(-1, sparse_array.lastIndexOf(3, 99 - 42000)); + +assertEquals(700, sparse_array.lastIndexOf(4)); +assertEquals(300, sparse_array.lastIndexOf(4, 699)); +assertEquals(-1, sparse_array.lastIndexOf(4, 299)); +assertEquals(700, sparse_array.lastIndexOf(4, -1)); +assertEquals(300, sparse_array.lastIndexOf(4, 699 - 42000)); +assertEquals(-1, sparse_array.lastIndexOf(4, 299 - 42000)); +assertEquals(800, sparse_array.lastIndexOf(undefined)); +assertEquals(200, sparse_array.lastIndexOf(undefined, 799)); +assertEquals(-1, sparse_array.lastIndexOf(undefined, 199)); +assertEquals(800, sparse_array.lastIndexOf(undefined, -1)); +assertEquals(200, sparse_array.lastIndexOf(undefined, 799 - 42000)); +assertEquals(-1, sparse_array.lastIndexOf(undefined, 199 - 42000)); -- 2.7.4