You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@uima.apache.org by sc...@apache.org on 2013/11/07 19:33:12 UTC
svn commit: r1539752 - in
/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees:
Int2IntRBT.java IntArrayRBT.java
Author: schor
Date: Thu Nov 7 18:33:12 2013
New Revision: 1539752
URL: http://svn.apache.org/r1539752
Log:
[UIMA-3415] [UIMA-3416] Fix bugs causing array-index-out-of-bounds
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java?rev=1539752&r1=1539751&r2=1539752&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/Int2IntRBT.java Thu Nov 7 18:33:12 2013
@@ -341,15 +341,17 @@ public class Int2IntRBT {
// keys that are larger than all keys already in the tree.
private int greatestNode;
- private static final int default_size = 1024;
+ private static final int default_size = 1024; // must be pwr of 2 for useklrp true
- private static final int default_growth_factor = 2;
+ private static final int default_growth_factor = 2; // must be pwr of 2 for useklrp true
- private static final int default_multiplication_limit = 2000000;
+ private static final int default_multiplication_limit = 1024 * 1024 * 2; // must be pwr of 2 for useklrp true
- private final int growth_factor;
+ final private int initialSize;
- private final int multiplication_limit;
+ final private int growth_factor; // must be pwr of 2 for useklrp true
+
+ final private int multiplication_limit; // must be pwr of 2 for useklrp true
// The NIL sentinel
public static final int NIL = 0;
@@ -374,8 +376,19 @@ public class Int2IntRBT {
initVars();
// Increase initialSize by one since we use one slot for sentinel.
++initialSize;
+ this.initialSize = nextPowerOf2(initialSize);
this.growth_factor = default_growth_factor;
this.multiplication_limit = default_multiplication_limit;
+ setupArrays();
+ }
+
+ private int nextPowerOf2(int v) {
+ // v is >= 0
+ int v2 = Integer.highestOneBit(v);
+ return (v2 < v) ? (v2 << 1) : v2;
+ }
+
+ private void setupArrays() {
// Init the arrays.
if (useklrp) {
klrp = new int[initialSize << 2];
@@ -423,8 +436,18 @@ public class Int2IntRBT {
}
public void clear() {
- // All we do for flush is set the root to NIL and the size to 0. Doesn't release space
+ // All we do for flush is set the root to NIL and the size to 0.
initVars();
+ // and potentially release extra storage
+ if (useklrp) {
+ if (klrp.length > (initialSize << 2)) {
+ setupArrays();
+ }
+ } else {
+ if (key.length > initialSize) {
+ setupArrays();
+ }
+ }
}
public final int size() {
@@ -433,34 +456,53 @@ public class Int2IntRBT {
private void grow(int requiredSize) {
if (useklrp) {
+
+ // the klrp design stacks 4 pointers together into the int array
+ // When growing, the last array is grown by the needed amount.
+ // Edge case: if the new required size jumps up by more than
+ // about 2 million, the previous array might need to be
+ // expanded too.
+ // This could in a real edge case require all previous arrays
+ // to be expanded.
+
final int w = requiredSize >> 29; // w is 0-3
+ final int requiredSizeForLastSegment = requiredSize - w * MAXklrp0;
switch (w) {
- case 0:
- if (klrp == null) {
- klrp = new int[requiredSize << 2];
+ case 3: {
+ if (klrp3 == null) {
+ klrp3 = new int[requiredSizeForLastSegment << 2];
} else {
- klrp = grow(klrp, requiredSize << 2);
+ klrp3 = grow(klrp3, requiredSizeForLastSegment << 2);
+ }
+ maximize(klrp2);
+ maximize(klrp1);
+ maximize(klrp);
}
break;
- case 1:
- if (klrp1 == null) {
- klrp1 = new int[(requiredSize & MAXklrpMask) << 2];
+ case 2: {
+ if (klrp2 == null) {
+ klrp2 = new int[requiredSizeForLastSegment << 2];
} else {
- klrp1 = grow(klrp1, (requiredSize & MAXklrpMask) << 2);
+ klrp2 = grow(klrp2, requiredSizeForLastSegment << 2);
+ }
+ maximize(klrp1);
+ maximize(klrp);
}
break;
- case 2:
- if (klrp2 == null) {
- klrp2 = new int[(requiredSize & MAXklrpMask) << 2];
+ case 1: {
+ if (klrp1 == null) {
+ klrp1 = new int[requiredSizeForLastSegment << 2];
} else {
- klrp2 = grow(klrp2, (requiredSize & MAXklrpMask) << 2);
+ klrp1 = grow(klrp1, requiredSizeForLastSegment << 2);
+ }
+ maximize(klrp);
}
break;
- case 3:
- if (klrp3 == null) {
- klrp3 = new int[(requiredSize & MAXklrpMask) << 2];
+ case 0:
+ if (klrp == null) {
+ klrp = new int[requiredSizeForLastSegment << 2];
} else {
- klrp3 = grow(klrp3, (requiredSize & MAXklrpMask) << 2);
+ klrp = grow(klrp, requiredSizeForLastSegment << 2);
}
break;
default:
@@ -473,9 +515,19 @@ public class Int2IntRBT {
this.parent = grow(this.parent, requiredSize);
}
this.color = grow(this.color, requiredSize);
- this.values = growPlainIntArray(this.values, requiredSize);
+ this.values = grow(this.values, requiredSize);
}
+ // only called for krlp style
+ private int[] maximize(int[] array) {
+ if (array.length < MAXklrp0) {
+ int[] a = new int[MAXklrp0];
+ System.arraycopy(array, 0, a, 0, array.length);
+ return a;
+ }
+ return array;
+ }
+
/**
*
* @param k
@@ -563,17 +615,6 @@ public class Int2IntRBT {
* @return expanded array
*/
private final int[] grow(final int[] array, final int newSize) {
- if (useklrp) {
- if (newSize < MAXklrp0) {
- return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
- } else {
- throw new RuntimeException(); // never happen
- }
- }
- return growPlainIntArray(array, newSize);
- }
-
- private final int[] growPlainIntArray(int[] array, int newSize) {
return IntArrayUtils.ensure_size(array, newSize, this.growth_factor, this.multiplication_limit);
}
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java?rev=1539752&r1=1539751&r2=1539752&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/rb_trees/IntArrayRBT.java Thu Nov 7 18:33:12 2013
@@ -572,9 +572,8 @@ public class IntArrayRBT {
setParent(z, y);
return z;
}
- int y = NIL;
int x = this.root;
- y = NIL;
+ int y = NIL;
while (x != NIL) {
y = x;
final int xKey = getKey(x);