Diff
Modified: trunk/LayoutTests/ChangeLog (183307 => 183308)
--- trunk/LayoutTests/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
@@ -1,3 +1,18 @@
+2015-04-24 Commit Queue <[email protected]>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
2015-04-24 Myles C. Maxfield <[email protected]>
Implement parsing support for font-synthesis CSS property
Modified: trunk/LayoutTests/js/array-holes-expected.txt (183307 => 183308)
--- trunk/LayoutTests/js/array-holes-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/array-holes-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
@@ -36,7 +36,7 @@
PASS showHoles([0, , 2, 3].reverse()) is '[3, 2, peekaboo, 0]'
PASS a = [0, , 2, 3]; a.shift(); showHoles(a) is '[peekaboo, 2, 3]'
PASS showHoles([0, , 2, 3].slice(0, 3)) is '[0, peekaboo, 2]'
-PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, peekaboo]'
+PASS showHoles([0, , 2, 3].sort()) is '[0, 2, 3, hole]'
PASS showHoles([0, undefined, 2, 3].sort()) is '[0, 2, 3, undefined]'
PASS a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a) is '[0, hole, 5, 6]'
PASS a = [0, , 2, 3]; a.unshift(4); showHoles(a) is '[4, 0, peekaboo, 2, 3]'
Modified: trunk/LayoutTests/js/array-sort-sparse-expected.txt (183307 => 183308)
--- trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/array-sort-sparse-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
@@ -5,11 +5,6 @@
PASS testSort([,undefined,0,1]) is true
PASS testSort({length:4,1:undefined,2:0,3:1}) is true
-PASS 0 in array is true
-PASS 1 in array is false
-PASS 0 in array is true
-PASS 1 in array is false
-PASS 2 in array is false
PASS successfullyParsed is true
TEST COMPLETE
Modified: trunk/LayoutTests/js/comparefn-sort-stability-expected.txt (183307 => 183308)
--- trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/comparefn-sort-stability-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
@@ -3,206 +3,14 @@
On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[i] is ones[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
-PASS array[count + i] is twos[i]
+PASS arr[0] is sortArr[0]
+PASS arr[1] is sortArr[2]
+PASS arr[2] is sortArr[1]
+PASS arr[3] is sortArr[3]
+PASS arr[0] is sortArr[0]
+PASS arr[1] is sortArr[2]
+PASS arr[2] is sortArr[1]
+PASS arr[3] is sortArr[3]
PASS successfullyParsed is true
TEST COMPLETE
Modified: trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt (183307 => 183308)
--- trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/dom/array-prototype-properties-expected.txt 2015-04-25 06:57:12 UTC (rev 183308)
@@ -12,7 +12,7 @@
PASS Array.prototype.reverse.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.reverse.call(undefined)').
PASS Array.prototype.shift.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.shift.call(undefined)').
PASS Array.prototype.slice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.slice.call(undefined, 0, 1)').
-PASS Array.prototype.sort.call(undefined) threw exception TypeError: Array.prototype.sort requires that |this| not be undefined.
+PASS Array.prototype.sort.call(undefined) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.sort.call(undefined)').
PASS Array.prototype.splice.call(undefined, 0, 1) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.splice.call(undefined, 0, 1)').
PASS Array.prototype.unshift.call(undefined, {}) threw exception TypeError: undefined is not an object (evaluating 'Array.prototype.unshift.call(undefined, {})').
PASS Array.prototype.every.call(undefined, toString) threw exception TypeError: Array.prototype.every requires that |this| not be undefined.
Modified: trunk/LayoutTests/js/script-tests/array-holes.js (183307 => 183308)
--- trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/array-holes.js 2015-04-25 06:57:12 UTC (rev 183308)
@@ -87,7 +87,7 @@
shouldBe("showHoles([0, , 2, 3].reverse())", "'[3, 2, peekaboo, 0]'");
shouldBe("a = [0, , 2, 3]; a.shift(); showHoles(a)", "'[peekaboo, 2, 3]'");
shouldBe("showHoles([0, , 2, 3].slice(0, 3))", "'[0, peekaboo, 2]'");
-shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, peekaboo]'");
+shouldBe("showHoles([0, , 2, 3].sort())", "'[0, 2, 3, hole]'");
shouldBe("showHoles([0, undefined, 2, 3].sort())", "'[0, 2, 3, undefined]'");
shouldBe("a = [0, , 2, 3]; a.splice(2, 3, 5, 6); showHoles(a)", "'[0, hole, 5, 6]'");
shouldBe("a = [0, , 2, 3]; a.unshift(4); showHoles(a)", "'[4, 0, peekaboo, 2, 3]'");
Modified: trunk/LayoutTests/js/script-tests/array-sort-sparse.js (183307 => 183308)
--- trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/array-sort-sparse.js 2015-04-25 06:57:12 UTC (rev 183308)
@@ -10,14 +10,3 @@
shouldBeTrue("testSort([,undefined,0,1])");
shouldBeTrue("testSort({length:4,1:undefined,2:0,3:1})");
-
-var array = [ , undefined ];
-array.sort();
-shouldBeTrue("0 in array");
-shouldBeFalse("1 in array");
-
-var array = [ , 1, , ];
-array.sort();
-shouldBeTrue("0 in array");
-shouldBeFalse("1 in array");
-shouldBeFalse("2 in array");
Modified: trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js (183307 => 183308)
--- trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/LayoutTests/js/script-tests/comparefn-sort-stability.js 2015-04-25 06:57:12 UTC (rev 183308)
@@ -2,25 +2,30 @@
"This tests that sort(compareFn) is a stable sort."
);
-var count = 100;
+function clone(source, target) {
+ for (i = 0; i < source.length; i++) {
+ target[i] = source[i];
+ }
+}
-var _ones_ = [];
-for (var i = 0; i < count; ++i)
- ones.push(new Number(1));
+var arr = [];
+arr[0] = new Number(1);
+arr[1] = new Number(2);
+arr[2] = new Number(1);
+arr[3] = new Number(2);
-var twos = [];
-for (var i = 0; i < count; ++i)
- twos.push(new Number(2));
+var sortArr = [];
+clone(arr, sortArr);
+sortArr.sort(function(a,b) { return a - b; });
-var array = [];
-for (var i = 0; i < count; ++i) {
- array.push(ones[i]);
- array.push(twos[i]);
-}
+shouldBe('arr[0]', 'sortArr[0]');
+shouldBe('arr[1]', 'sortArr[2]');
+shouldBe('arr[2]', 'sortArr[1]');
+shouldBe('arr[3]', 'sortArr[3]');
-array.sort(function(a,b) { return a - b; });
-for (var i = 0; i < count; ++i)
- shouldBe('array[i]', 'ones[i]');
-
-for (var i = 0; i < count; ++i)
- shouldBe('array[count + i]', 'twos[i]');
+// Just try again...
+sortArr.sort(function(a,b) { return a - b; });
+shouldBe('arr[0]', 'sortArr[0]');
+shouldBe('arr[1]', 'sortArr[2]');
+shouldBe('arr[2]', 'sortArr[1]');
+shouldBe('arr[3]', 'sortArr[3]');
Modified: trunk/Source/_javascript_Core/ChangeLog (183307 => 183308)
--- trunk/Source/_javascript_Core/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
@@ -1,3 +1,18 @@
+2015-04-24 Commit Queue <[email protected]>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
2015-04-24 Filip Pizlo <[email protected]>
CRASH in operationCreateDirectArgumentsDuringExit()
Modified: trunk/Source/_javascript_Core/builtins/Array.prototype.js (183307 => 183308)
--- trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/builtins/Array.prototype.js 2015-04-25 06:57:12 UTC (rev 183308)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -277,185 +277,3 @@
}
return false;
}
-
-function sort(comparator)
-{
- "use strict";
-
- function min(a, b)
- {
- return a < b ? a : b;
- }
-
- function stringComparator(a, b)
- {
- var aString = @String(a);
- var bString = @String(b);
-
- var aLength = aString.length;
- var bLength = bString.length;
- var length = min(aLength, bLength);
-
- for (var i = 0; i < length; ++i) {
- var aCharCode = aString.@charCodeAt(i);
- var bCharCode = bString.@charCodeAt(i);
-
- if (aCharCode == bCharCode)
- continue;
-
- if (aCharCode < bCharCode)
- return -1;
-
- return 1;
- }
-
- if (aLength == bLength)
- return 0;
-
- if (aLength < bLength)
- return -1;
-
- return 1;
- }
-
- // Move undefineds and holes to the end of a sparse array. Result is [values..., undefineds..., holes...].
- function compactSparse(array, dst, src, length)
- {
- var values = [ ];
- var seen = { };
- var valueCount = 0;
- var undefinedCount = 0;
-
- // Clean up after the in-progress non-sparse compaction that failed.
- for (var i = dst; i < src; ++i)
- delete array[i];
-
- for (var object = array; object; object = @Object.@getPrototypeOf(object)) {
- var propertyNames = @Object.@getOwnPropertyNames(object);
- for (var i = 0; i < propertyNames.length; ++i) {
- var index = propertyNames[i];
- if (index < length) { // Exclude non-numeric properties and properties past length.
- if (seen[index]) // Exclude duplicates.
- continue;
- seen[index] = 1;
-
- var value = array[index];
- delete array[index];
-
- if (value === undefined) {
- ++undefinedCount;
- continue;
- }
-
- array[valueCount++] = value;
- }
- }
- }
-
- for (var i = valueCount; i < valueCount + undefinedCount; ++i)
- array[i] = undefined;
-
- return valueCount;
- }
-
- // Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
- function compact(array, length)
- {
- var holeCount = 0;
-
- for (var dst = 0, src = "" src < length; ++src) {
- if (!(src in array)) {
- ++holeCount;
- if (holeCount < 256)
- continue;
- return compactSparse(array, dst, src, length);
- }
-
- var value = array[src];
- if (value === undefined)
- continue;
- array[dst++] = value;
- }
-
- var valueCount = dst;
- var undefinedCount = length - valueCount - holeCount;
-
- for (var i = valueCount; i < valueCount + undefinedCount; ++i)
- array[i] = undefined;
-
- for (var i = valueCount + undefinedCount; i < length; ++i)
- delete array[i];
-
- return valueCount;
- }
-
- function merge(dst, src, srcIndex, srcEnd, width, comparator)
- {
- var left = srcIndex;
- var leftEnd = min(left + width, srcEnd);
- var right = leftEnd;
- var rightEnd = min(right + width, srcEnd);
-
- for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
- if (right < rightEnd) {
- if (left >= leftEnd || comparator(src[left], src[right]) > 0) {
- dst[dstIndex] = src[right++];
- continue;
- }
- }
-
- dst[dstIndex] = src[left++];
- }
- }
-
- function mergeSort(array, valueCount, comparator)
- {
- var buffer = [ ];
- buffer.length = valueCount;
-
- var dst = buffer;
- var src = ""
- for (var width = 1; width < valueCount; width *= 2) {
- for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
- merge(dst, src, srcIndex, valueCount, width, comparator);
-
- var tmp = src;
- src = ""
- dst = tmp;
- }
-
- if (src != array) {
- for(var i = 0; i < valueCount; i++)
- array[i] = src[i];
- }
- }
-
- function comparatorSort(array, comparator)
- {
- var length = array.length >>> 0;
-
- // For compatibility with Firefox and Chrome, do nothing observable
- // to the target array if it has 0 or 1 sortable properties.
- if (length < 2)
- return;
-
- var valueCount = compact(array, length);
- mergeSort(array, valueCount, comparator);
- }
-
- if (this === null)
- throw new @TypeError("Array.prototype.sort requires that |this| not be null");
-
- if (this === undefined)
- throw new @TypeError("Array.prototype.sort requires that |this| not be undefined");
-
- if (typeof this == "string")
- throw new @TypeError("Attempted to assign to readonly property.");
-
- if (typeof comparator !== "function")
- comparator = stringComparator;
-
- var array = @Object(this);
- comparatorSort(array, comparator);
- return array;
-}
Modified: trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/builtins/BuiltinExecutables.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -101,6 +101,7 @@
if (closedVariable == m_vm.propertyNames->undefinedKeyword.impl())
continue;
+ RELEASE_ASSERT(m_vm.propertyNames->isPrivateName(closedVariable.get()));
}
body->overrideName(name);
UnlinkedFunctionExecutable* functionExecutable = UnlinkedFunctionExecutable::create(&m_vm, source, body, kind, WTF::move(sourceOverride));
Modified: trunk/Source/_javascript_Core/bytecode/CodeBlock.h (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecode/CodeBlock.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -249,6 +249,8 @@
return static_cast<Instruction*>(returnAddress) - instructions().begin();
}
+ bool isNumericCompareFunction() { return m_unlinkedCode->isNumericCompareFunction(); }
+
unsigned numberOfInstructions() const { return m_instructions.size(); }
RefCountedArray<Instruction>& instructions() { return m_instructions; }
const RefCountedArray<Instruction>& instructions() const { return m_instructions; }
Modified: trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -241,6 +241,7 @@
, m_globalObjectRegister(VirtualRegister())
, m_needsFullScopeChain(info.needsActivation())
, m_usesEval(info.usesEval())
+ , m_isNumericCompareFunction(false)
, m_isStrictMode(info.isStrictMode())
, m_isConstructor(info.isConstructor())
, m_hasCapturedVariables(false)
Modified: trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecode/UnlinkedCodeBlock.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -344,6 +344,9 @@
unsigned jumpTarget(int index) const { return m_jumpTargets[index]; }
unsigned lastJumpTarget() const { return m_jumpTargets.last(); }
+ void setIsNumericCompareFunction(bool isNumericCompareFunction) { m_isNumericCompareFunction = isNumericCompareFunction; }
+ bool isNumericCompareFunction() const { return m_isNumericCompareFunction; }
+
bool isBuiltinFunction() const { return m_isBuiltinFunction; }
ConstructorKind constructorKind() const { return static_cast<ConstructorKind>(m_constructorKind); }
@@ -533,6 +536,7 @@
unsigned m_needsFullScopeChain : 1;
unsigned m_usesEval : 1;
+ unsigned m_isNumericCompareFunction : 1;
unsigned m_isStrictMode : 1;
unsigned m_isConstructor : 1;
unsigned m_hasCapturedVariables : 1;
Modified: trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -2603,6 +2603,11 @@
return newTemporary();
}
+void BytecodeGenerator::setIsNumericCompareFunction(bool isNumericCompareFunction)
+{
+ m_codeBlock->setIsNumericCompareFunction(isNumericCompareFunction);
+}
+
bool BytecodeGenerator::isArgumentNumber(const Identifier& ident, int argumentNumber)
{
RegisterID* registerID = variable(ident).local();
Modified: trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecompiler/BytecodeGenerator.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -276,6 +276,8 @@
bool isArgumentNumber(const Identifier&, int);
+ void setIsNumericCompareFunction(bool isNumericCompareFunction);
+
Variable variable(const Identifier&);
// Ignores the possibility of intervening scopes.
Modified: trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/bytecompiler/NodesCodegen.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -2821,6 +2821,22 @@
generator.emitReturn(r0);
return;
}
+
+ // If there is a return statment, and it is the only statement in the function, check if this is a numeric compare.
+ if (static_cast<BlockNode*>(singleStatement)->singleStatement()) {
+ ExpressionNode* returnValueExpression = returnNode->value();
+ if (returnValueExpression && returnValueExpression->isSubtract()) {
+ ExpressionNode* lhsExpression = static_cast<SubNode*>(returnValueExpression)->lhs();
+ ExpressionNode* rhsExpression = static_cast<SubNode*>(returnValueExpression)->rhs();
+ if (lhsExpression->isResolveNode()
+ && rhsExpression->isResolveNode()
+ && generator.isArgumentNumber(static_cast<ResolveNode*>(lhsExpression)->identifier(), 0)
+ && generator.isArgumentNumber(static_cast<ResolveNode*>(rhsExpression)->identifier(), 1)) {
+
+ generator.setIsNumericCompareFunction(true);
+ }
+ }
+ }
}
// ------------------------------ FuncDeclNode ---------------------------------
Modified: trunk/Source/_javascript_Core/heap/Heap.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/heap/Heap.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/heap/Heap.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -481,6 +481,17 @@
}
}
+void Heap::pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
+{
+ m_tempSortingVectors.append(tempVector);
+}
+
+void Heap::popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>* tempVector)
+{
+ ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
+ m_tempSortingVectors.removeLast();
+}
+
void Heap::harvestWeakReferences()
{
m_slotVisitor.harvestWeakReferences();
@@ -560,6 +571,7 @@
visitSmallStrings();
visitConservativeRoots(conservativeRoots);
visitProtectedObjects(heapRootVisitor);
+ visitTempSortVectors(heapRootVisitor);
visitArgumentBuffers(heapRootVisitor);
visitException(heapRootVisitor);
visitStrongHandles(heapRootVisitor);
@@ -698,6 +710,23 @@
m_slotVisitor.donateAndDrain();
}
+void Heap::visitTempSortVectors(HeapRootVisitor& heapRootVisitor)
+{
+ GCPHASE(VisitTempSortVectors);
+
+ for (auto* vector : m_tempSortingVectors) {
+ for (auto& valueStringPair : *vector) {
+ if (valueStringPair.first)
+ heapRootVisitor.visit(&valueStringPair.first);
+ }
+ }
+
+ if (Options::logGC() == GCLogging::Verbose)
+ dataLog("Temp Sort Vectors:\n", m_slotVisitor);
+
+ m_slotVisitor.donateAndDrain();
+}
+
void Heap::visitArgumentBuffers(HeapRootVisitor& visitor)
{
GCPHASE(MarkingArgumentBuffers);
Modified: trunk/Source/_javascript_Core/heap/Heap.h (183307 => 183308)
--- trunk/Source/_javascript_Core/heap/Heap.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/heap/Heap.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -75,6 +75,7 @@
static void* const zombifiedBits = reinterpret_cast<void*>(0xdeadbeef);
+typedef std::pair<JSValue, WTF::String> ValueStringPair;
typedef HashCountedSet<JSCell*> ProtectCountSet;
typedef HashCountedSet<const char*> TypeCountSet;
@@ -185,6 +186,9 @@
JS_EXPORT_PRIVATE std::unique_ptr<TypeCountSet> objectTypeCounts();
void showStatistics();
+ void pushTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
+ void popTempSortVector(Vector<ValueStringPair, 0, UnsafeVectorOverflow>*);
+
HashSet<MarkedArgumentBuffer*>& markListSet();
template<typename Functor> typename Functor::ReturnType forEachProtectedCell(Functor&);
@@ -296,6 +300,7 @@
void visitCompilerWorklistWeakReferences();
void removeDeadCompilerWorklistEntries();
void visitProtectedObjects(HeapRootVisitor&);
+ void visitTempSortVectors(HeapRootVisitor&);
void visitArgumentBuffers(HeapRootVisitor&);
void visitException(HeapRootVisitor&);
void visitStrongHandles(HeapRootVisitor&);
@@ -366,6 +371,7 @@
HashSet<const JSCell*> m_copyingRememberedSet;
ProtectCountSet m_protectedValues;
+ Vector<Vector<ValueStringPair, 0, UnsafeVectorOverflow>*> m_tempSortingVectors;
std::unique_ptr<HashSet<MarkedArgumentBuffer*>> m_markListSet;
MachineThreads m_machineThreads;
Modified: trunk/Source/_javascript_Core/parser/Parser.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/parser/Parser.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/parser/Parser.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -288,6 +288,7 @@
features |= ModifiedArgumentsFeature;
Vector<RefPtr<StringImpl>> closedVariables;
if (m_parsingBuiltin) {
+ RELEASE_ASSERT(!capturedVariables.size());
IdentifierSet usedVariables;
scope->getUsedVariables(usedVariables);
for (const auto& variable : usedVariables) {
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -54,6 +54,7 @@
EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
+EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
@@ -69,6 +70,21 @@
namespace JSC {
+static inline bool isNumericCompareFunction(ExecState* exec, JSValue function, CallType callType, const CallData& callData)
+{
+ if (callType != CallTypeJS)
+ return false;
+
+ FunctionExecutable* executable = callData.js.functionExecutable;
+ JSScope* scope = callData.js.scope;
+
+ JSObject* error = executable->prepareForExecution(exec, jsCast<JSFunction*>(function), scope, CodeForCall);
+ if (error)
+ return false;
+
+ return executable->codeBlockForCall()->isNumericCompareFunction();
+}
+
// ------------------------------ ArrayPrototype ----------------------------
const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
@@ -638,6 +654,155 @@
return JSValue();
}
+static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType)
+{
+ if (thisObj->classInfo() != JSArray::info()
+ || asArray(thisObj)->hasSparseMap()
+ || shouldUseSlowPut(thisObj->indexingType()))
+ return false;
+
+ if (isNumericCompareFunction(exec, function, callType, callData))
+ asArray(thisObj)->sortNumeric(exec, function, callType, callData);
+ else if (callType != CallTypeNone)
+ asArray(thisObj)->sort(exec, function, callType, callData);
+ else
+ asArray(thisObj)->sort(exec);
+ return true;
+}
+
+static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType)
+{
+ // "Min" sort. Not the fastest, but definitely less code than heapsort
+ // or quicksort, and much less swapping than bubblesort/insertionsort.
+ for (unsigned i = 0; i < length - 1; ++i) {
+ JSValue iObj = getOrHole(thisObj, exec, i);
+ if (exec->hadException())
+ return false;
+ unsigned themin = i;
+ JSValue minObj = iObj;
+ for (unsigned j = i + 1; j < length; ++j) {
+ JSValue jObj = getOrHole(thisObj, exec, j);
+ if (exec->hadException())
+ return false;
+ double compareResult;
+ if (!jObj)
+ compareResult = 1;
+ else if (!minObj)
+ compareResult = -1;
+ else if (jObj.isUndefined())
+ compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
+ else if (minObj.isUndefined())
+ compareResult = -1;
+ else if (callType != CallTypeNone) {
+ MarkedArgumentBuffer l;
+ l.append(jObj);
+ l.append(minObj);
+ compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec);
+ } else
+ compareResult = codePointCompareLessThan(jObj.toWTFStringInline(exec), minObj.toWTFStringInline(exec)) ? -1 : 1;
+
+ if (compareResult < 0) {
+ themin = j;
+ minObj = jObj;
+ }
+ }
+ // Swap themin and i
+ if (themin > i) {
+ if (minObj) {
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, minObj, true);
+ if (exec->hadException())
+ return false;
+ } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, i)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return false;
+ }
+ if (iObj) {
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, themin, iObj, true);
+ if (exec->hadException())
+ return false;
+ } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, themin)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
+{
+ JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
+ unsigned length = getLength(exec, thisObj);
+ if (!length || exec->hadException())
+ return JSValue::encode(thisObj);
+
+ JSValue function = exec->argument(0);
+ CallData callData;
+ CallType callType = getCallData(function, callData);
+
+ if (attemptFastSort(exec, thisObj, function, callData, callType))
+ return JSValue::encode(thisObj);
+
+ // Assume that for small-ish arrays, doing the slow sort directly is better.
+ if (length < 1000)
+ return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined());
+
+ JSGlobalObject* globalObject = JSGlobalObject::create(
+ exec->vm(), JSGlobalObject::createStructure(exec->vm(), jsNull()));
+ JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), nullptr);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ PropertyNameArray nameArray(exec);
+ thisObj->methodTable(exec->vm())->getPropertyNames(thisObj, exec, nameArray, EnumerationMode(DontEnumPropertiesMode::Include));
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ Vector<uint32_t, 0, UnsafeVectorOverflow> keys;
+ for (size_t i = 0; i < nameArray.size(); ++i) {
+ PropertyName name = nameArray[i];
+ Optional<uint32_t> optionalIndex = parseIndex(name);
+ if (!optionalIndex)
+ continue;
+
+ uint32_t index = optionalIndex.value();
+ JSValue value = getOrHole(thisObj, exec, index);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ if (!value)
+ continue;
+ keys.append(index);
+ flatArray->push(exec, value);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
+ if (!attemptFastSort(exec, flatArray, function, callData, callType)
+ && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
+ return JSValue::encode(jsUndefined());
+
+ for (size_t i = 0; i < keys.size(); ++i) {
+ size_t index = keys[i];
+ if (index < flatArray->length())
+ continue;
+
+ if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) {
+ throwTypeError(exec, ASCIILiteral("Unable to delete property."));
+ return JSValue::encode(jsUndefined());
+ }
+ }
+
+ for (size_t i = flatArray->length(); i--;) {
+ JSValue value = getOrHole(flatArray, exec, i);
+ RELEASE_ASSERT(value);
+ thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
+ return JSValue::encode(thisObj);
+}
+
EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
{
// 15.4.4.12
Modified: trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/CommonIdentifiers.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -269,12 +269,9 @@
macro(objectGetOwnPropertySymbols) \
macro(Number) \
macro(Array) \
- macro(String) \
macro(abs) \
macro(floor) \
macro(isFinite) \
- macro(getPrototypeOf) \
- macro(getOwnPropertyNames) \
macro(TypeError) \
macro(undefined) \
macro(BuiltinLog) \
Modified: trunk/Source/_javascript_Core/runtime/JSArray.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/JSArray.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -34,6 +34,7 @@
#include "JSCInlines.h"
#include "PropertyNameArray.h"
#include "Reject.h"
+#include <wtf/AVLTree.h>
#include <wtf/Assertions.h>
using namespace std;
@@ -993,6 +994,521 @@
}
}
+static int compareNumbersForQSortWithInt32(const void* a, const void* b)
+{
+ int32_t ia = static_cast<const JSValue*>(a)->asInt32();
+ int32_t ib = static_cast<const JSValue*>(b)->asInt32();
+ return ia - ib;
+}
+
+static int compareNumbersForQSortWithDouble(const void* a, const void* b)
+{
+ double da = *static_cast<const double*>(a);
+ double db = *static_cast<const double*>(b);
+ return (da > db) - (da < db);
+}
+
+static int compareNumbersForQSort(const void* a, const void* b)
+{
+ double da = static_cast<const JSValue*>(a)->asNumber();
+ double db = static_cast<const JSValue*>(b)->asNumber();
+ return (da > db) - (da < db);
+}
+
+static int compareByStringPairForQSort(const void* a, const void* b)
+{
+ const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
+ const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
+ return codePointCompare(va->second, vb->second);
+}
+
+template<IndexingType arrayIndexingType>
+void JSArray::sortNumericVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(arrayIndexingType == ArrayWithInt32 || arrayIndexingType == ArrayWithDouble || arrayIndexingType == ArrayWithContiguous || arrayIndexingType == ArrayWithArrayStorage);
+
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<arrayIndexingType>(
+ lengthNotIncludingUndefined,
+ newRelevantLength);
+
+ ContiguousJSValues data = ""
+
+ if (arrayIndexingType == ArrayWithArrayStorage && arrayStorage()->m_sparseMap.get()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ if (!lengthNotIncludingUndefined)
+ return;
+
+ bool allValuesAreNumbers = true;
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ break;
+
+ default:
+ for (size_t i = 0; i < newRelevantLength; ++i) {
+ if (!data[i].isNumber()) {
+ allValuesAreNumbers = false;
+ break;
+ }
+ }
+ break;
+ }
+
+ if (!allValuesAreNumbers)
+ return sort(exec, compareFunction, callType, callData);
+
+ // For numeric comparison, which is fast, qsort is faster than mergesort. We
+ // also don't require mergesort's stability, since there's no user visible
+ // side-effect from swapping the order of equal primitive values.
+ int (*compare)(const void*, const void*);
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ compare = compareNumbersForQSortWithInt32;
+ break;
+
+ case ArrayWithDouble:
+ compare = compareNumbersForQSortWithDouble;
+ ASSERT(sizeof(WriteBarrier<Unknown>) == sizeof(double));
+ break;
+
+ default:
+ compare = compareNumbersForQSort;
+ break;
+ }
+ ASSERT(data.length() >= newRelevantLength);
+ qsort(data.data(), newRelevantLength, sizeof(WriteBarrier<Unknown>), compare);
+ return;
+}
+
+void JSArray::sortNumeric(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32:
+ sortNumericVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithDouble:
+ sortNumericVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithContiguous:
+ sortNumericVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortNumericVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ dataLog("Indexing type: ", indexingType(), "\n");
+ RELEASE_ASSERT_NOT_REACHED();
+ return;
+ }
+}
+
+template <IndexingType> struct ContiguousTypeAccessor {
+ typedef WriteBarrier<Unknown> Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { return data[i].get(); }
+ static void setWithValue(VM& vm, JSArray* thisValue, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i].set(vm, thisValue, value);
+ }
+ static void replaceDataReference(ContiguousData<Type>* outData, ContiguousJSValues inData)
+ {
+ *outData = inData;
+ }
+};
+
+template <> struct ContiguousTypeAccessor<ArrayWithDouble> {
+ typedef double Type;
+ static JSValue getAsValue(ContiguousData<Type> data, size_t i) { ASSERT(data[i] == data[i]); return JSValue(JSValue::EncodeAsDouble, data[i]); }
+ static void setWithValue(VM&, JSArray*, ContiguousData<Type> data, size_t i, JSValue value)
+ {
+ data[i] = value.asNumber();
+ }
+ static NO_RETURN_DUE_TO_CRASH void replaceDataReference(ContiguousData<Type>*, ContiguousJSValues)
+ {
+ RELEASE_ASSERT_WITH_MESSAGE(0, "Inconsistent indexing types during compact array sort.");
+ }
+};
+
+
+template<IndexingType arrayIndexingType, typename StorageType>
+void JSArray::sortCompactedVector(ExecState* exec, ContiguousData<StorageType> data, unsigned relevantLength)
+{
+ if (!relevantLength)
+ return;
+
+ VM& vm = exec->vm();
+
+ // Converting _javascript_ values to strings can be expensive, so we do it once up front and sort based on that.
+ // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+ // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
+ // random or otherwise changing results, effectively making compare function inconsistent.
+
+ Vector<ValueStringPair, 0, UnsafeVectorOverflow> values(relevantLength);
+ if (!values.begin()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ Heap::heap(this)->pushTempSortVector(&values);
+
+ bool isSortingPrimitiveValues = true;
+
+ for (size_t i = 0; i < relevantLength; i++) {
+ JSValue value = ContiguousTypeAccessor<arrayIndexingType>::getAsValue(data, i);
+ ASSERT(arrayIndexingType != ArrayWithInt32 || value.isInt32());
+ ASSERT(!value.isUndefined());
+ values[i].first = value;
+ if (arrayIndexingType != ArrayWithDouble && arrayIndexingType != ArrayWithInt32)
+ isSortingPrimitiveValues = isSortingPrimitiveValues && value.isPrimitive();
+ }
+
+ // FIXME: The following loop continues to call toString on subsequent values even after
+ // a toString call raises an exception.
+
+ for (size_t i = 0; i < relevantLength; i++)
+ values[i].second = values[i].first.toWTFStringInline(exec);
+
+ if (exec->hadException()) {
+ Heap::heap(this)->popTempSortVector(&values);
+ return;
+ }
+
+ // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
+ // than O(N log N).
+
+#if HAVE(MERGESORT)
+ if (isSortingPrimitiveValues)
+ qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+ else
+ mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#else
+ // FIXME: The qsort library function is likely to not be a stable sort.
+ // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
+ qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
+#endif
+
+ // If the toString function changed the length of the array or vector storage,
+ // increase the length to handle the orignal number of actual values.
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ case ArrayWithContiguous:
+ ensureLength(vm, relevantLength);
+ break;
+
+ case ArrayWithArrayStorage:
+ if (arrayStorage()->vectorLength() < relevantLength) {
+ increaseVectorLength(exec->vm(), relevantLength);
+ ContiguousTypeAccessor<arrayIndexingType>::replaceDataReference(&data, arrayStorage()->vector());
+ }
+ if (arrayStorage()->length() < relevantLength)
+ arrayStorage()->setLength(relevantLength);
+ break;
+
+ default:
+ CRASH();
+ }
+
+ for (size_t i = 0; i < relevantLength; i++)
+ ContiguousTypeAccessor<arrayIndexingType>::setWithValue(vm, this, data, i, values[i].first);
+
+ Heap::heap(this)->popTempSortVector(&values);
+}
+
+void JSArray::sort(ExecState* exec)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithInt32>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithInt32>(
+ exec, m_butterfly->contiguousInt32(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithDouble: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithDouble>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithDouble>(
+ exec, m_butterfly->contiguousDouble(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithContiguous: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithContiguous>(
+ lengthNotIncludingUndefined, newRelevantLength);
+
+ sortCompactedVector<ArrayWithContiguous>(
+ exec, m_butterfly->contiguous(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ case ArrayWithArrayStorage: {
+ unsigned lengthNotIncludingUndefined;
+ unsigned newRelevantLength;
+ compactForSorting<ArrayWithArrayStorage>(
+ lengthNotIncludingUndefined, newRelevantLength);
+ ArrayStorage* storage = m_butterfly->arrayStorage();
+ ASSERT(!storage->m_sparseMap);
+
+ sortCompactedVector<ArrayWithArrayStorage>(exec, storage->vector(), lengthNotIncludingUndefined);
+ return;
+ }
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+}
+
+struct AVLTreeNodeForArrayCompare {
+ JSValue value;
+
+ // Child pointers. The high bit of gt is robbed and used as the
+ // balance factor sign. The high bit of lt is robbed and used as
+ // the magnitude of the balance factor.
+ int32_t gt;
+ int32_t lt;
+};
+
+struct AVLTreeAbstractorForArrayCompare {
+ typedef int32_t handle; // Handle is an index into m_nodes vector.
+ typedef JSValue key;
+ typedef int32_t size;
+
+ Vector<AVLTreeNodeForArrayCompare, 0, UnsafeVectorOverflow> m_nodes;
+ ExecState* m_exec;
+ JSValue m_compareFunction;
+ CallType m_compareCallType;
+ const CallData* m_compareCallData;
+ std::unique_ptr<CachedCall> m_cachedCall;
+
+ handle get_less(handle h) { return m_nodes[h].lt & 0x7FFFFFFF; }
+ void set_less(handle h, handle lh) { m_nodes[h].lt &= 0x80000000; m_nodes[h].lt |= lh; }
+ handle get_greater(handle h) { return m_nodes[h].gt & 0x7FFFFFFF; }
+ void set_greater(handle h, handle gh) { m_nodes[h].gt &= 0x80000000; m_nodes[h].gt |= gh; }
+
+ int get_balance_factor(handle h)
+ {
+ if (m_nodes[h].gt & 0x80000000)
+ return -1;
+ return static_cast<unsigned>(m_nodes[h].lt) >> 31;
+ }
+
+ void set_balance_factor(handle h, int bf)
+ {
+ if (bf == 0) {
+ m_nodes[h].lt &= 0x7FFFFFFF;
+ m_nodes[h].gt &= 0x7FFFFFFF;
+ } else {
+ m_nodes[h].lt |= 0x80000000;
+ if (bf < 0)
+ m_nodes[h].gt |= 0x80000000;
+ else
+ m_nodes[h].gt &= 0x7FFFFFFF;
+ }
+ }
+
+ int compare_key_key(key va, key vb)
+ {
+ ASSERT(!va.isUndefined());
+ ASSERT(!vb.isUndefined());
+
+ if (m_exec->hadException())
+ return 1;
+
+ double compareResult;
+ if (m_cachedCall) {
+ m_cachedCall->setThis(jsUndefined());
+ m_cachedCall->setArgument(0, va);
+ m_cachedCall->setArgument(1, vb);
+ compareResult = m_cachedCall->call().toNumber(m_exec);
+ } else {
+ MarkedArgumentBuffer arguments;
+ arguments.append(va);
+ arguments.append(vb);
+ compareResult = call(m_exec, m_compareFunction, m_compareCallType, *m_compareCallData, jsUndefined(), arguments).toNumber(m_exec);
+ }
+ return (compareResult < 0) ? -1 : 1; // Not passing equality through, because we need to store all values, even if equivalent.
+ }
+
+ int compare_key_node(key k, handle h) { return compare_key_key(k, m_nodes[h].value); }
+ int compare_node_node(handle h1, handle h2) { return compare_key_key(m_nodes[h1].value, m_nodes[h2].value); }
+
+ static handle null() { return 0x7FFFFFFF; }
+};
+
+template<IndexingType arrayIndexingType>
+void JSArray::sortVector(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+ ASSERT(arrayIndexingType == indexingType());
+
+ // FIXME: This ignores exceptions raised in the compare function or in toNumber.
+
+ // The maximum tree depth is compiled in - but the caller is clearly up to no good
+ // if a larger array is passed.
+ ASSERT(m_butterfly->publicLength() <= static_cast<unsigned>(std::numeric_limits<int>::max()));
+ if (m_butterfly->publicLength() > static_cast<unsigned>(std::numeric_limits<int>::max()))
+ return;
+
+ unsigned usedVectorLength = relevantLength<arrayIndexingType>();
+ unsigned nodeCount = usedVectorLength;
+
+ if (!nodeCount)
+ return;
+
+ AVLTree<AVLTreeAbstractorForArrayCompare, 44> tree; // Depth 44 is enough for 2^31 items
+ tree.abstractor().m_exec = exec;
+ tree.abstractor().m_compareFunction = compareFunction;
+ tree.abstractor().m_compareCallType = callType;
+ tree.abstractor().m_compareCallData = &callData;
+ tree.abstractor().m_nodes.grow(nodeCount);
+
+ if (callType == CallTypeJS)
+ tree.abstractor().m_cachedCall = std::make_unique<CachedCall>(exec, jsCast<JSFunction*>(compareFunction), 2);
+
+ if (!tree.abstractor().m_nodes.begin()) {
+ throwOutOfMemoryError(exec);
+ return;
+ }
+
+ // FIXME: If the compare function modifies the array, the vector, map, etc. could be modified
+ // right out from under us while we're building the tree here.
+
+ unsigned numDefined = 0;
+ unsigned numUndefined = 0;
+
+ // Iterate over the array, ignoring missing values, counting undefined ones, and inserting all other ones into the tree.
+ for (; numDefined < usedVectorLength; ++numDefined) {
+ if (numDefined >= m_butterfly->vectorLength())
+ break;
+ JSValue v = getHolyIndexQuickly(numDefined);
+ if (!v || v.isUndefined())
+ break;
+ tree.abstractor().m_nodes[numDefined].value = v;
+ tree.insert(numDefined);
+ }
+ for (unsigned i = numDefined; i < usedVectorLength; ++i) {
+ if (i >= m_butterfly->vectorLength())
+ break;
+ JSValue v = getHolyIndexQuickly(i);
+ if (v) {
+ if (v.isUndefined())
+ ++numUndefined;
+ else {
+ tree.abstractor().m_nodes[numDefined].value = v;
+ tree.insert(numDefined);
+ ++numDefined;
+ }
+ }
+ }
+
+ unsigned newUsedVectorLength = numDefined + numUndefined;
+
+ // The array size may have changed. Figure out the new bounds.
+ unsigned newestUsedVectorLength = currentRelevantLength();
+
+ unsigned elementsToExtractThreshold = min(min(newestUsedVectorLength, numDefined), static_cast<unsigned>(tree.abstractor().m_nodes.size()));
+ unsigned undefinedElementsThreshold = min(newestUsedVectorLength, newUsedVectorLength);
+ unsigned clearElementsThreshold = min(newestUsedVectorLength, usedVectorLength);
+
+ // Copy the values back into m_storage.
+ AVLTree<AVLTreeAbstractorForArrayCompare, 44>::Iterator iter;
+ iter.start_iter_least(tree);
+ VM& vm = exec->vm();
+ for (unsigned i = 0; i < elementsToExtractThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ if (indexingType() == ArrayWithDouble)
+ butterfly()->contiguousDouble()[i] = tree.abstractor().m_nodes[*iter].value.asNumber();
+ else
+ currentIndexingData()[i].set(vm, this, tree.abstractor().m_nodes[*iter].value);
+ ++iter;
+ }
+ // Put undefined values back in.
+ switch (indexingType()) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ ASSERT(elementsToExtractThreshold == undefinedElementsThreshold);
+ break;
+
+ default:
+ for (unsigned i = elementsToExtractThreshold; i < undefinedElementsThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ currentIndexingData()[i].setUndefined();
+ }
+ }
+
+ // Ensure that unused values in the vector are zeroed out.
+ for (unsigned i = undefinedElementsThreshold; i < clearElementsThreshold; ++i) {
+ ASSERT(i < butterfly()->vectorLength());
+ if (indexingType() == ArrayWithDouble)
+ butterfly()->contiguousDouble()[i] = PNaN;
+ else
+ currentIndexingData()[i].clear();
+ }
+
+ if (hasAnyArrayStorage(indexingType()))
+ arrayStorage()->m_numValuesInVector = newUsedVectorLength;
+}
+
+void JSArray::sort(ExecState* exec, JSValue compareFunction, CallType callType, const CallData& callData)
+{
+ ASSERT(!inSparseIndexingMode());
+
+ switch (indexingType()) {
+ case ArrayClass:
+ case ArrayWithUndecided:
+ return;
+
+ case ArrayWithInt32:
+ sortVector<ArrayWithInt32>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithDouble:
+ sortVector<ArrayWithDouble>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithContiguous:
+ sortVector<ArrayWithContiguous>(exec, compareFunction, callType, callData);
+ return;
+
+ case ArrayWithArrayStorage:
+ sortVector<ArrayWithArrayStorage>(exec, compareFunction, callType, callData);
+ return;
+
+ default:
+ RELEASE_ASSERT_NOT_REACHED();
+ }
+}
+
void JSArray::fillArgList(ExecState* exec, MarkedArgumentBuffer& args)
{
unsigned i = 0;
@@ -1123,4 +1639,95 @@
}
}
+template<IndexingType arrayIndexingType>
+void JSArray::compactForSorting(unsigned& numDefined, unsigned& newRelevantLength)
+{
+ ASSERT(!inSparseIndexingMode());
+ ASSERT(arrayIndexingType == indexingType());
+
+ unsigned myRelevantLength = relevantLength<arrayIndexingType>();
+
+ numDefined = 0;
+ unsigned numUndefined = 0;
+
+ for (; numDefined < myRelevantLength; ++numDefined) {
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithInt32) {
+ JSValue v = m_butterfly->contiguousInt32()[numDefined].get();
+ if (!v)
+ break;
+ ASSERT(v.isInt32());
+ continue;
+ }
+ if (arrayIndexingType == ArrayWithDouble) {
+ double v = m_butterfly->contiguousDouble()[numDefined];
+ if (v != v)
+ break;
+ continue;
+ }
+ JSValue v = indexingData<arrayIndexingType>()[numDefined].get();
+ if (!v || v.isUndefined())
+ break;
+ }
+
+ for (unsigned i = numDefined; i < myRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithInt32) {
+ JSValue v = m_butterfly->contiguousInt32()[i].get();
+ if (!v)
+ continue;
+ ASSERT(v.isInt32());
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ m_butterfly->contiguousInt32()[numDefined++].setWithoutWriteBarrier(v);
+ continue;
+ }
+ if (arrayIndexingType == ArrayWithDouble) {
+ double v = m_butterfly->contiguousDouble()[i];
+ if (v != v)
+ continue;
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ m_butterfly->contiguousDouble()[numDefined++] = v;
+ continue;
+ }
+ JSValue v = indexingData<arrayIndexingType>()[i].get();
+ if (v) {
+ if (v.isUndefined())
+ ++numUndefined;
+ else {
+ ASSERT(numDefined < m_butterfly->vectorLength());
+ indexingData<arrayIndexingType>()[numDefined++].setWithoutWriteBarrier(v);
+ }
+ }
+ }
+
+ newRelevantLength = numDefined + numUndefined;
+
+ if (hasAnyArrayStorage(arrayIndexingType))
+ RELEASE_ASSERT(!arrayStorage()->m_sparseMap);
+
+ switch (arrayIndexingType) {
+ case ArrayWithInt32:
+ case ArrayWithDouble:
+ RELEASE_ASSERT(numDefined == newRelevantLength);
+ break;
+
+ default:
+ for (unsigned i = numDefined; i < newRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ indexingData<arrayIndexingType>()[i].setUndefined();
+ }
+ break;
+ }
+ for (unsigned i = newRelevantLength; i < myRelevantLength; ++i) {
+ ASSERT(i < m_butterfly->vectorLength());
+ if (arrayIndexingType == ArrayWithDouble)
+ m_butterfly->contiguousDouble()[i] = PNaN;
+ else
+ indexingData<arrayIndexingType>()[i].clear();
+ }
+
+ if (hasAnyArrayStorage(arrayIndexingType))
+ arrayStorage()->m_numValuesInVector = newRelevantLength;
+}
+
} // namespace JSC
Modified: trunk/Source/_javascript_Core/runtime/JSArray.h (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/JSArray.h 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/JSArray.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -70,6 +70,10 @@
// OK to use on new arrays, but not if it might be a RegExpMatchArray.
JS_EXPORT_PRIVATE bool setLength(ExecState*, unsigned, bool throwException = false);
+ JS_EXPORT_PRIVATE void sort(ExecState*);
+ JS_EXPORT_PRIVATE void sort(ExecState*, JSValue compareFunction, CallType, const CallData&);
+ JS_EXPORT_PRIVATE void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
JS_EXPORT_PRIVATE void push(ExecState*, JSValue);
JS_EXPORT_PRIVATE JSValue pop(ExecState*);
@@ -159,8 +163,20 @@
bool unshiftCountWithArrayStorage(ExecState*, unsigned startIndex, unsigned count, ArrayStorage*);
bool unshiftCountSlowCase(VM&, bool, unsigned);
+ template<IndexingType indexingType>
+ void sortNumericVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
+ template<IndexingType indexingType, typename StorageType>
+ void sortCompactedVector(ExecState*, ContiguousData<StorageType>, unsigned relevantLength);
+
+ template<IndexingType indexingType>
+ void sortVector(ExecState*, JSValue compareFunction, CallType, const CallData&);
+
bool setLengthWithArrayStorage(ExecState*, unsigned newLength, bool throwException, ArrayStorage*);
void setLengthWritable(ExecState*, bool writable);
+
+ template<IndexingType indexingType>
+ void compactForSorting(unsigned& numDefined, unsigned& newRelevantLength);
};
inline Butterfly* createContiguousArrayButterfly(VM& vm, JSCell* intendedOwner, unsigned length, unsigned& vectorLength)
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalObject.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -445,11 +445,8 @@
GlobalPropertyInfo(vm.propertyNames->BuiltinLogPrivateName, builtinLog, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->ArrayPrivateName, arrayConstructor, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->NumberPrivateName, numberConstructor, DontEnum | DontDelete | ReadOnly),
- GlobalPropertyInfo(vm.propertyNames->StringPrivateName, stringConstructor, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->absPrivateName, privateFuncAbs, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->floorPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
- GlobalPropertyInfo(vm.propertyNames->getPrototypeOfPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
- GlobalPropertyInfo(vm.propertyNames->getOwnPropertyNamesPrivateName, privateFuncFloor, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->isFinitePrivateName, privateFuncIsFinite, DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->arrayIterationKindKeyPrivateName, jsNumber(ArrayIterateKey), DontEnum | DontDelete | ReadOnly),
GlobalPropertyInfo(vm.propertyNames->arrayIterationKindValuePrivateName, jsNumber(ArrayIterateValue), DontEnum | DontDelete | ReadOnly),
Modified: trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp (183307 => 183308)
--- trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/_javascript_Core/runtime/ObjectConstructor.cpp 2015-04-25 06:57:12 UTC (rev 183308)
@@ -96,9 +96,6 @@
if (!globalObject->runtimeFlags().isSymbolDisabled())
JSC_NATIVE_FUNCTION("getOwnPropertySymbols", objectConstructorGetOwnPropertySymbols, DontEnum, 1);
-
- JSC_NATIVE_FUNCTION(vm.propertyNames->getPrototypeOfPrivateName, objectConstructorGetPrototypeOf, DontEnum, 1);
- JSC_NATIVE_FUNCTION(vm.propertyNames->getOwnPropertyNamesPrivateName, objectConstructorGetOwnPropertyNames, DontEnum, 1);
}
bool ObjectConstructor::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot &slot)
Modified: trunk/Source/WTF/ChangeLog (183307 => 183308)
--- trunk/Source/WTF/ChangeLog 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/ChangeLog 2015-04-25 06:57:12 UTC (rev 183308)
@@ -1,3 +1,18 @@
+2015-04-24 Commit Queue <[email protected]>
+
+ Unreviewed, rolling out r183288.
+ https://bugs.webkit.org/show_bug.cgi?id=144189
+
+ Made js/sort-with-side-effecting-comparisons.html time out in
+ debug builds (Requested by ap on #webkit).
+
+ Reverted changeset:
+
+ "It shouldn't take 1846 lines of code and 5 FIXMEs to sort an
+ array."
+ https://bugs.webkit.org/show_bug.cgi?id=144013
+ http://trac.webkit.org/changeset/183288
+
2015-04-21 Geoffrey Garen <[email protected]>
It shouldn't take 1846 lines of code and 5 FIXMEs to sort an array.
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (183307 => 183308)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-04-25 06:57:12 UTC (rev 183308)
@@ -163,6 +163,7 @@
<ClInclude Include="..\wtf\Assertions.h" />
<ClInclude Include="..\wtf\Atomics.h" />
<ClInclude Include="..\wtf\AutodrainedPool.h" />
+ <ClInclude Include="..\wtf\AVLTree.h" />
<ClInclude Include="..\wtf\Bag.h" />
<ClInclude Include="..\wtf\BagToHashMap.h" />
<ClInclude Include="..\wtf\Bitmap.h" />
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters (183307 => 183308)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj.filters 2015-04-25 06:57:12 UTC (rev 183308)
@@ -381,6 +381,9 @@
<ClInclude Include="..\wtf\Atomics.h">
<Filter>wtf</Filter>
</ClInclude>
+ <ClInclude Include="..\wtf\AVLTree.h">
+ <Filter>wtf</Filter>
+ </ClInclude>
<ClInclude Include="..\wtf\Bitmap.h">
<Filter>wtf</Filter>
</ClInclude>
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (183307 => 183308)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-04-25 06:57:12 UTC (rev 183308)
@@ -107,6 +107,7 @@
A8A47386151A825B004123FF /* Assertions.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A4725B151A825A004123FF /* Assertions.cpp */; };
A8A47387151A825B004123FF /* Assertions.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725C151A825A004123FF /* Assertions.h */; };
A8A47388151A825B004123FF /* Atomics.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725D151A825A004123FF /* Atomics.h */; };
+ A8A47389151A825B004123FF /* AVLTree.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725E151A825A004123FF /* AVLTree.h */; };
A8A4738A151A825B004123FF /* Bitmap.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A4725F151A825A004123FF /* Bitmap.h */; };
A8A4738B151A825B004123FF /* BitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A8A47260151A825A004123FF /* BitVector.cpp */; };
A8A4738C151A825B004123FF /* BitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = A8A47261151A825A004123FF /* BitVector.h */; };
@@ -391,6 +392,7 @@
A8A4725B151A825A004123FF /* Assertions.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Assertions.cpp; sourceTree = "<group>"; };
A8A4725C151A825A004123FF /* Assertions.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Assertions.h; sourceTree = "<group>"; };
A8A4725D151A825A004123FF /* Atomics.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Atomics.h; sourceTree = "<group>"; };
+ A8A4725E151A825A004123FF /* AVLTree.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AVLTree.h; sourceTree = "<group>"; };
A8A4725F151A825A004123FF /* Bitmap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Bitmap.h; sourceTree = "<group>"; };
A8A47260151A825A004123FF /* BitVector.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = BitVector.cpp; sourceTree = "<group>"; };
A8A47261151A825A004123FF /* BitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BitVector.h; sourceTree = "<group>"; };
@@ -694,6 +696,7 @@
A8A4725D151A825A004123FF /* Atomics.h */,
1469419A16EAB10A0024E146 /* AutodrainedPool.h */,
1469419B16EAB10A0024E146 /* AutodrainedPoolMac.mm */,
+ A8A4725E151A825A004123FF /* AVLTree.h */,
0FB14E18180FA218009B6B4D /* Bag.h */,
0FB14E1A1810E1DA009B6B4D /* BagToHashMap.h */,
A8A4725F151A825A004123FF /* Bitmap.h */,
@@ -1036,6 +1039,7 @@
A8A47438151A825B004123FF /* AtomicStringImpl.h in Headers */,
9BD8F40B176C2B470002D865 /* AtomicStringTable.h in Headers */,
1469419C16EAB10A0024E146 /* AutodrainedPool.h in Headers */,
+ A8A47389151A825B004123FF /* AVLTree.h in Headers */,
8134013915B092FD001FF0B8 /* Base64.h in Headers */,
A8A473A9151A825B004123FF /* bignum-dtoa.h in Headers */,
A8A473AB151A825B004123FF /* bignum.h in Headers */,
Added: trunk/Source/WTF/wtf/AVLTree.h (0 => 183308)
--- trunk/Source/WTF/wtf/AVLTree.h (rev 0)
+++ trunk/Source/WTF/wtf/AVLTree.h 2015-04-25 06:57:12 UTC (rev 183308)
@@ -0,0 +1,960 @@
+/*
+ * Copyright (C) 2008 Apple Inc. All rights reserved.
+ *
+ * Based on Abstract AVL Tree Template v1.5 by Walt Karas
+ * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of Apple Inc. ("Apple") nor the names of
+ * its contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef AVL_TREE_H_
+#define AVL_TREE_H_
+
+#include <array>
+#include <wtf/Assertions.h>
+
+namespace WTF {
+
+// Here is the reference class for BSet.
+//
+// class BSet
+// {
+// public:
+//
+// class ANY_bitref
+// {
+// public:
+// operator bool ();
+// void operator = (bool b);
+// };
+//
+// // Does not have to initialize bits.
+// BSet();
+//
+// // Must return a valid value for index when 0 <= index < maxDepth
+// ANY_bitref operator [] (unsigned index);
+//
+// // Set all bits to 1.
+// void set();
+//
+// // Set all bits to 0.
+// void reset();
+// };
+
+template<unsigned maxDepth>
+class AVLTreeDefaultBSet {
+public:
+ bool& operator[](unsigned i) { ASSERT_WITH_SECURITY_IMPLICATION(i < maxDepth); return m_data[i]; }
+ void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
+ void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
+
+private:
+ std::array<bool, maxDepth> m_data;
+};
+
+// How to determine maxDepth:
+// d Minimum number of nodes
+// 2 2
+// 3 4
+// 4 7
+// 5 12
+// 6 20
+// 7 33
+// 8 54
+// 9 88
+// 10 143
+// 11 232
+// 12 376
+// 13 609
+// 14 986
+// 15 1,596
+// 16 2,583
+// 17 4,180
+// 18 6,764
+// 19 10,945
+// 20 17,710
+// 21 28,656
+// 22 46,367
+// 23 75,024
+// 24 121,392
+// 25 196,417
+// 26 317,810
+// 27 514,228
+// 28 832,039
+// 29 1,346,268
+// 30 2,178,308
+// 31 3,524,577
+// 32 5,702,886
+// 33 9,227,464
+// 34 14,930,351
+// 35 24,157,816
+// 36 39,088,168
+// 37 63,245,985
+// 38 102,334,154
+// 39 165,580,140
+// 40 267,914,295
+// 41 433,494,436
+// 42 701,408,732
+// 43 1,134,903,169
+// 44 1,836,311,902
+// 45 2,971,215,072
+//
+// E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28.
+// You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
+
+template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth>>
+class AVLTree {
+public:
+
+ typedef typename Abstractor::key key;
+ typedef typename Abstractor::handle handle;
+ typedef typename Abstractor::size size;
+
+ enum SearchType {
+ EQUAL = 1,
+ LESS = 2,
+ GREATER = 4,
+ LESS_EQUAL = EQUAL | LESS,
+ GREATER_EQUAL = EQUAL | GREATER
+ };
+
+
+ Abstractor& abstractor() { return abs; }
+
+ inline handle insert(handle h);
+
+ inline handle search(key k, SearchType st = EQUAL);
+ inline handle search_least();
+ inline handle search_greatest();
+
+ inline handle remove(key k);
+
+ inline handle subst(handle new_node);
+
+ void purge() { abs.root = null(); }
+
+ bool is_empty() { return abs.root == null(); }
+
+ AVLTree() { abs.root = null(); }
+
+ class Iterator {
+ public:
+
+ // Initialize depth to invalid value, to indicate iterator is
+ // invalid. (Depth is zero-base.)
+ Iterator() { depth = ~0U; }
+
+ void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
+ {
+ // Mask of high bit in an int.
+ const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
+
+ // Save the tree that we're going to iterate through in a
+ // member variable.
+ tree_ = &tree;
+
+ int cmp, target_cmp;
+ handle h = tree_->abs.root;
+ unsigned d = 0;
+
+ depth = ~0U;
+
+ if (h == null())
+ // Tree is empty.
+ return;
+
+ if (st & LESS)
+ // Key can be greater than key of starting node.
+ target_cmp = 1;
+ else if (st & GREATER)
+ // Key can be less than key of starting node.
+ target_cmp = -1;
+ else
+ // Key must be same as key of starting node.
+ target_cmp = 0;
+
+ for (;;) {
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0) {
+ if (st & EQUAL) {
+ // Equal node was sought and found as starting node.
+ depth = d;
+ break;
+ }
+ cmp = -target_cmp;
+ } else if (target_cmp != 0) {
+ if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
+ // cmp and target_cmp are both negative or both positive.
+ depth = d;
+ }
+ }
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ if (h == null())
+ break;
+ branch[d] = cmp > 0;
+ path_h[d++] = h;
+ }
+ }
+
+ void start_iter_least(AVLTree &tree)
+ {
+ tree_ = &tree;
+
+ handle h = tree_->abs.root;
+
+ depth = ~0U;
+
+ branch.reset();
+
+ while (h != null()) {
+ if (depth != ~0U)
+ path_h[depth] = h;
+ depth++;
+ h = get_lt(h);
+ }
+ }
+
+ void start_iter_greatest(AVLTree &tree)
+ {
+ tree_ = &tree;
+
+ handle h = tree_->abs.root;
+
+ depth = ~0U;
+
+ branch.set();
+
+ while (h != null()) {
+ if (depth != ~0U)
+ path_h[depth] = h;
+ depth++;
+ h = get_gt(h);
+ }
+ }
+
+ handle operator*()
+ {
+ if (depth == ~0U)
+ return null();
+
+ return depth == 0 ? tree_->abs.root : path_h[depth - 1];
+ }
+
+ void operator++()
+ {
+ if (depth != ~0U) {
+ handle h = get_gt(**this);
+ if (h == null()) {
+ do {
+ if (depth == 0) {
+ depth = ~0U;
+ break;
+ }
+ depth--;
+ } while (branch[depth]);
+ } else {
+ branch[depth] = true;
+ path_h[depth++] = h;
+ for (;;) {
+ h = get_lt(h);
+ if (h == null())
+ break;
+ branch[depth] = false;
+ path_h[depth++] = h;
+ }
+ }
+ }
+ }
+
+ void operator--()
+ {
+ if (depth != ~0U) {
+ handle h = get_lt(**this);
+ if (h == null())
+ do {
+ if (depth == 0) {
+ depth = ~0U;
+ break;
+ }
+ depth--;
+ } while (!branch[depth]);
+ else {
+ branch[depth] = false;
+ path_h[depth++] = h;
+ for (;;) {
+ h = get_gt(h);
+ if (h == null())
+ break;
+ branch[depth] = true;
+ path_h[depth++] = h;
+ }
+ }
+ }
+ }
+
+ void operator++(int) { ++(*this); }
+ void operator--(int) { --(*this); }
+
+ protected:
+
+ // Tree being iterated over.
+ AVLTree *tree_;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ // Zero-based depth of path into tree.
+ unsigned depth;
+
+ // Handles of nodes in path from root to current node (returned by *).
+ handle path_h[maxDepth - 1];
+
+ int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
+ int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
+ handle get_lt(handle h) { return tree_->abs.get_less(h); }
+ handle get_gt(handle h) { return tree_->abs.get_greater(h); }
+ handle null() { return tree_->abs.null(); }
+ };
+
+ template<typename fwd_iter>
+ bool build(fwd_iter p, size num_nodes)
+ {
+ if (num_nodes == 0) {
+ abs.root = null();
+ return true;
+ }
+
+ // Gives path to subtree being built. If branch[N] is false, branch
+ // less from the node at depth N, if true branch greater.
+ BSet branch;
+
+ // If rem[N] is true, then for the current subtree at depth N, it's
+ // greater subtree has one more node than it's less subtree.
+ BSet rem;
+
+ // Depth of root node of current subtree.
+ unsigned depth = 0;
+
+ // Number of nodes in current subtree.
+ size num_sub = num_nodes;
+
+ // The algorithm relies on a stack of nodes whose less subtree has
+ // been built, but whose right subtree has not yet been built. The
+ // stack is implemented as linked list. The nodes are linked
+ // together by having the "greater" handle of a node set to the
+ // next node in the list. "less_parent" is the handle of the first
+ // node in the list.
+ handle less_parent = null();
+
+ // h is root of current subtree, child is one of its children.
+ handle h, child;
+
+ for (;;) {
+ while (num_sub > 2) {
+ // Subtract one for root of subtree.
+ num_sub--;
+ rem[depth] = !!(num_sub & 1);
+ branch[depth++] = false;
+ num_sub >>= 1;
+ }
+
+ if (num_sub == 2) {
+ // Build a subtree with two nodes, slanting to greater.
+ // I arbitrarily chose to always have the extra node in the
+ // greater subtree when there is an odd number of nodes to
+ // split between the two subtrees.
+
+ h = *p;
+ p++;
+ child = *p;
+ p++;
+ set_lt(child, null());
+ set_gt(child, null());
+ set_bf(child, 0);
+ set_gt(h, child);
+ set_lt(h, null());
+ set_bf(h, 1);
+ } else { // num_sub == 1
+ // Build a subtree with one node.
+
+ h = *p;
+ p++;
+ set_lt(h, null());
+ set_gt(h, null());
+ set_bf(h, 0);
+ }
+
+ while (depth) {
+ depth--;
+ if (!branch[depth])
+ // We've completed a less subtree.
+ break;
+
+ // We've completed a greater subtree, so attach it to
+ // its parent (that is less than it). We pop the parent
+ // off the stack of less parents.
+ child = h;
+ h = less_parent;
+ less_parent = get_gt(h);
+ set_gt(h, child);
+ // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
+ num_sub <<= 1;
+ num_sub += 1 - rem[depth];
+ if (num_sub & (num_sub - 1))
+ // num_sub is not a power of 2
+ set_bf(h, 0);
+ else
+ // num_sub is a power of 2
+ set_bf(h, 1);
+ }
+
+ if (num_sub == num_nodes)
+ // We've completed the full tree.
+ break;
+
+ // The subtree we've completed is the less subtree of the
+ // next node in the sequence.
+
+ child = h;
+ h = *p;
+ p++;
+ set_lt(h, child);
+
+ // Put h into stack of less parents.
+ set_gt(h, less_parent);
+ less_parent = h;
+
+ // Proceed to creating greater than subtree of h.
+ branch[depth] = true;
+ num_sub += rem[depth++];
+
+ } // end for (;;)
+
+ abs.root = h;
+
+ return true;
+ }
+
+protected:
+
+ friend class Iterator;
+
+ // Create a class whose sole purpose is to take advantage of
+ // the "empty member" optimization.
+ struct abs_plus_root : public Abstractor {
+ // The handle of the root element in the AVL tree.
+ handle root;
+ };
+
+ abs_plus_root abs;
+
+
+ handle get_lt(handle h) { return abs.get_less(h); }
+ void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
+
+ handle get_gt(handle h) { return abs.get_greater(h); }
+ void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
+
+ int get_bf(handle h) { return abs.get_balance_factor(h); }
+ void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
+
+ int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
+ int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
+
+ handle null() { return abs.null(); }
+
+private:
+
+ // Balances subtree, returns handle of root node of subtree
+ // after balancing.
+ handle balance(handle bal_h)
+ {
+ handle deep_h;
+
+ // Either the "greater than" or the "less than" subtree of
+ // this node has to be 2 levels deeper (or else it wouldn't
+ // need balancing).
+
+ if (get_bf(bal_h) > 0) {
+ // "Greater than" subtree is deeper.
+
+ deep_h = get_gt(bal_h);
+
+ if (get_bf(deep_h) < 0) {
+ handle old_h = bal_h;
+ bal_h = get_lt(deep_h);
+
+ set_gt(old_h, get_lt(bal_h));
+ set_lt(deep_h, get_gt(bal_h));
+ set_lt(bal_h, old_h);
+ set_gt(bal_h, deep_h);
+
+ int bf = get_bf(bal_h);
+ if (bf != 0) {
+ if (bf > 0) {
+ set_bf(old_h, -1);
+ set_bf(deep_h, 0);
+ } else {
+ set_bf(deep_h, 1);
+ set_bf(old_h, 0);
+ }
+ set_bf(bal_h, 0);
+ } else {
+ set_bf(old_h, 0);
+ set_bf(deep_h, 0);
+ }
+ } else {
+ set_gt(bal_h, get_lt(deep_h));
+ set_lt(deep_h, bal_h);
+ if (get_bf(deep_h) == 0) {
+ set_bf(deep_h, -1);
+ set_bf(bal_h, 1);
+ } else {
+ set_bf(deep_h, 0);
+ set_bf(bal_h, 0);
+ }
+ bal_h = deep_h;
+ }
+ } else {
+ // "Less than" subtree is deeper.
+
+ deep_h = get_lt(bal_h);
+
+ if (get_bf(deep_h) > 0) {
+ handle old_h = bal_h;
+ bal_h = get_gt(deep_h);
+ set_lt(old_h, get_gt(bal_h));
+ set_gt(deep_h, get_lt(bal_h));
+ set_gt(bal_h, old_h);
+ set_lt(bal_h, deep_h);
+
+ int bf = get_bf(bal_h);
+ if (bf != 0) {
+ if (bf < 0) {
+ set_bf(old_h, 1);
+ set_bf(deep_h, 0);
+ } else {
+ set_bf(deep_h, -1);
+ set_bf(old_h, 0);
+ }
+ set_bf(bal_h, 0);
+ } else {
+ set_bf(old_h, 0);
+ set_bf(deep_h, 0);
+ }
+ } else {
+ set_lt(bal_h, get_gt(deep_h));
+ set_gt(deep_h, bal_h);
+ if (get_bf(deep_h) == 0) {
+ set_bf(deep_h, 1);
+ set_bf(bal_h, -1);
+ } else {
+ set_bf(deep_h, 0);
+ set_bf(bal_h, 0);
+ }
+ bal_h = deep_h;
+ }
+ }
+
+ return bal_h;
+ }
+
+};
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
+{
+ set_lt(h, null());
+ set_gt(h, null());
+ set_bf(h, 0);
+
+ if (abs.root == null())
+ abs.root = h;
+ else {
+ // Last unbalanced node encountered in search for insertion point.
+ handle unbal = null();
+ // Parent of last unbalanced node.
+ handle parent_unbal = null();
+ // Balance factor of last unbalanced node.
+ int unbal_bf;
+
+ // Zero-based depth in tree.
+ unsigned depth = 0, unbal_depth = 0;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ handle hh = abs.root;
+ handle parent = null();
+ int cmp;
+
+ do {
+ if (get_bf(hh) != 0) {
+ unbal = hh;
+ parent_unbal = parent;
+ unbal_depth = depth;
+ }
+ cmp = cmp_n_n(h, hh);
+ if (cmp == 0)
+ // Duplicate key.
+ return hh;
+ parent = hh;
+ hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
+ branch[depth++] = cmp > 0;
+ } while (hh != null());
+
+ // Add node to insert as leaf of tree.
+ if (cmp < 0)
+ set_lt(parent, h);
+ else
+ set_gt(parent, h);
+
+ depth = unbal_depth;
+
+ if (unbal == null())
+ hh = abs.root;
+ else {
+ cmp = branch[depth++] ? 1 : -1;
+ unbal_bf = get_bf(unbal);
+ if (cmp < 0)
+ unbal_bf--;
+ else // cmp > 0
+ unbal_bf++;
+ hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
+ if ((unbal_bf != -2) && (unbal_bf != 2)) {
+ // No rebalancing of tree is necessary.
+ set_bf(unbal, unbal_bf);
+ unbal = null();
+ }
+ }
+
+ if (hh != null())
+ while (h != hh) {
+ cmp = branch[depth++] ? 1 : -1;
+ if (cmp < 0) {
+ set_bf(hh, -1);
+ hh = get_lt(hh);
+ } else { // cmp > 0
+ set_bf(hh, 1);
+ hh = get_gt(hh);
+ }
+ }
+
+ if (unbal != null()) {
+ unbal = balance(unbal);
+ if (parent_unbal == null())
+ abs.root = unbal;
+ else {
+ depth = unbal_depth - 1;
+ cmp = branch[depth] ? 1 : -1;
+ if (cmp < 0)
+ set_lt(parent_unbal, unbal);
+ else // cmp > 0
+ set_gt(parent_unbal, unbal);
+ }
+ }
+ }
+
+ return h;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
+{
+ const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
+
+ int cmp, target_cmp;
+ handle match_h = null();
+ handle h = abs.root;
+
+ if (st & LESS)
+ target_cmp = 1;
+ else if (st & GREATER)
+ target_cmp = -1;
+ else
+ target_cmp = 0;
+
+ while (h != null()) {
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0) {
+ if (st & EQUAL) {
+ match_h = h;
+ break;
+ }
+ cmp = -target_cmp;
+ } else if (target_cmp != 0)
+ if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
+ // cmp and target_cmp are both positive or both negative.
+ match_h = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ }
+
+ return match_h;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_least()
+{
+ handle h = abs.root, parent = null();
+
+ while (h != null()) {
+ parent = h;
+ h = get_lt(h);
+ }
+
+ return parent;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
+{
+ handle h = abs.root, parent = null();
+
+ while (h != null()) {
+ parent = h;
+ h = get_gt(h);
+ }
+
+ return parent;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
+{
+ // Zero-based depth in tree.
+ unsigned depth = 0, rm_depth;
+
+ // Records a path into the tree. If branch[n] is true, indicates
+ // take greater branch from the nth node in the path, otherwise
+ // take the less branch. branch[0] gives branch from root, and
+ // so on.
+ BSet branch;
+
+ handle h = abs.root;
+ handle parent = null(), child;
+ int cmp, cmp_shortened_sub_with_path = 0;
+
+ for (;;) {
+ if (h == null())
+ // No node in tree with given key.
+ return null();
+ cmp = cmp_k_n(k, h);
+ if (cmp == 0)
+ // Found node to remove.
+ break;
+ parent = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ branch[depth++] = cmp > 0;
+ cmp_shortened_sub_with_path = cmp;
+ }
+ handle rm = h;
+ handle parent_rm = parent;
+ rm_depth = depth;
+
+ // If the node to remove is not a leaf node, we need to get a
+ // leaf node, or a node with a single leaf as its child, to put
+ // in the place of the node to remove. We will get the greatest
+ // node in the less subtree (of the node to remove), or the least
+ // node in the greater subtree. We take the leaf node from the
+ // deeper subtree, if there is one.
+
+ if (get_bf(h) < 0) {
+ child = get_lt(h);
+ branch[depth] = false;
+ cmp = -1;
+ } else {
+ child = get_gt(h);
+ branch[depth] = true;
+ cmp = 1;
+ }
+ depth++;
+
+ if (child != null()) {
+ cmp = -cmp;
+ do {
+ parent = h;
+ h = child;
+ if (cmp < 0) {
+ child = get_lt(h);
+ branch[depth] = false;
+ } else {
+ child = get_gt(h);
+ branch[depth] = true;
+ }
+ depth++;
+ } while (child != null());
+
+ if (parent == rm)
+ // Only went through do loop once. Deleted node will be replaced
+ // in the tree structure by one of its immediate children.
+ cmp_shortened_sub_with_path = -cmp;
+ else
+ cmp_shortened_sub_with_path = cmp;
+
+ // Get the handle of the opposite child, which may not be null.
+ child = cmp > 0 ? get_lt(h) : get_gt(h);
+ }
+
+ if (parent == null())
+ // There were only 1 or 2 nodes in this tree.
+ abs.root = child;
+ else if (cmp_shortened_sub_with_path < 0)
+ set_lt(parent, child);
+ else
+ set_gt(parent, child);
+
+ // "path" is the parent of the subtree being eliminated or reduced
+ // from a depth of 2 to 1. If "path" is the node to be removed, we
+ // set path to the node we're about to poke into the position of the
+ // node to be removed.
+ handle path = parent == rm ? h : parent;
+
+ if (h != rm) {
+ // Poke in the replacement for the node to be removed.
+ set_lt(h, get_lt(rm));
+ set_gt(h, get_gt(rm));
+ set_bf(h, get_bf(rm));
+ if (parent_rm == null())
+ abs.root = h;
+ else {
+ depth = rm_depth - 1;
+ if (branch[depth])
+ set_gt(parent_rm, h);
+ else
+ set_lt(parent_rm, h);
+ }
+ }
+
+ if (path != null()) {
+ // Create a temporary linked list from the parent of the path node
+ // to the root node.
+ h = abs.root;
+ parent = null();
+ depth = 0;
+ while (h != path) {
+ if (branch[depth++]) {
+ child = get_gt(h);
+ set_gt(h, parent);
+ } else {
+ child = get_lt(h);
+ set_lt(h, parent);
+ }
+ parent = h;
+ h = child;
+ }
+
+ // Climb from the path node to the root node using the linked
+ // list, restoring the tree structure and rebalancing as necessary.
+ bool reduced_depth = true;
+ int bf;
+ cmp = cmp_shortened_sub_with_path;
+ for (;;) {
+ if (reduced_depth) {
+ bf = get_bf(h);
+ if (cmp < 0)
+ bf++;
+ else // cmp > 0
+ bf--;
+ if ((bf == -2) || (bf == 2)) {
+ h = balance(h);
+ bf = get_bf(h);
+ } else
+ set_bf(h, bf);
+ reduced_depth = (bf == 0);
+ }
+ if (parent == null())
+ break;
+ child = h;
+ h = parent;
+ cmp = branch[--depth] ? 1 : -1;
+ if (cmp < 0) {
+ parent = get_lt(h);
+ set_lt(h, child);
+ } else {
+ parent = get_gt(h);
+ set_gt(h, child);
+ }
+ }
+ abs.root = h;
+ }
+
+ return rm;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
+{
+ handle h = abs.root;
+ handle parent = null();
+ int cmp, last_cmp;
+
+ /* Search for node already in tree with same key. */
+ for (;;) {
+ if (h == null())
+ /* No node in tree with same key as new node. */
+ return null();
+ cmp = cmp_n_n(new_node, h);
+ if (cmp == 0)
+ /* Found the node to substitute new one for. */
+ break;
+ last_cmp = cmp;
+ parent = h;
+ h = cmp < 0 ? get_lt(h) : get_gt(h);
+ }
+
+ /* Copy tree housekeeping fields from node in tree to new node. */
+ set_lt(new_node, get_lt(h));
+ set_gt(new_node, get_gt(h));
+ set_bf(new_node, get_bf(h));
+
+ if (parent == null())
+ /* New node is also new root. */
+ abs.root = new_node;
+ else {
+ /* Make parent point to new node. */
+ if (last_cmp < 0)
+ set_lt(parent, new_node);
+ else
+ set_gt(parent, new_node);
+ }
+
+ return h;
+}
+
+}
+
+#endif
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (183307 => 183308)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-25 05:19:07 UTC (rev 183307)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-04-25 06:57:12 UTC (rev 183308)
@@ -1,5 +1,6 @@
set(WTF_HEADERS
ASCIICType.h
+ AVLTree.h
Assertions.h
Atomics.h
Bag.h
