Revision: 5432
Author: [email protected]
Date: Thu Sep 9 05:57:32 2010
Log: Add sparse array handling to Array.protoype.indexOf/lastIndexOf.
Review URL: http://codereview.chromium.org/3132046
http://code.google.com/p/v8/source/detail?r=5432
Modified:
/branches/bleeding_edge/src/array.js
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/test/mjsunit/array-indexing.js
=======================================
--- /branches/bleeding_edge/src/array.js Mon Aug 30 11:08:50 2010
+++ /branches/bleeding_edge/src/array.js Thu Sep 9 05:57:32 2010
@@ -957,14 +957,41 @@
// 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 @@
} 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;
}
=======================================
--- /branches/bleeding_edge/src/runtime.cc Wed Sep 8 05:57:50 2010
+++ /branches/bleeding_edge/src/runtime.cc Thu Sep 9 05:57:32 2010
@@ -8022,8 +8022,10 @@
// 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;
=======================================
--- /branches/bleeding_edge/test/mjsunit/array-indexing.js Tue Sep 9
13:08:45 2008
+++ /branches/bleeding_edge/test/mjsunit/array-indexing.js Thu Sep 9
05:57:32 2010
@@ -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(array.indexOf(3), 2);
+assertEquals(-1, [].indexOf(1));
+assertEquals(-1, array.indexOf(4));
+assertEquals(-1, array.indexOf(3, array.length));
+
+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(array.lastIndexOf(1), 9);
+assertEquals(-1, [].lastIndexOf(1));
+assertEquals(-1, array.lastIndexOf(1, -17));
+
+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));
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
