diff options
author | Sergey Prigogin | 2014-04-16 19:10:39 +0000 |
---|---|---|
committer | Sergey Prigogin | 2014-04-16 19:10:39 +0000 |
commit | 4381cc5da1c1a91c603ce956c8737947170cc3e9 (patch) | |
tree | 40814a7ab9dee486e19bad67295ef6057f92b0d8 /core | |
parent | d7ceaaed42b07875ab2d2410e76855b714190163 (diff) | |
download | org.eclipse.cdt-4381cc5da1c1a91c603ce956c8737947170cc3e9.tar.gz org.eclipse.cdt-4381cc5da1c1a91c603ce956c8737947170cc3e9.tar.xz org.eclipse.cdt-4381cc5da1c1a91c603ce956c8737947170cc3e9.zip |
Fixed integer overflow in binary search methods.
Diffstat (limited to 'core')
5 files changed, 30 insertions, 29 deletions
diff --git a/core/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/ToStringSorter.java b/core/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/ToStringSorter.java index ce2e39e02af..72be2e5b58e 100644 --- a/core/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/ToStringSorter.java +++ b/core/org.eclipse.cdt.core/model/org/eclipse/cdt/internal/core/util/ToStringSorter.java @@ -1,16 +1,15 @@ /******************************************************************************* - * Copyright (c) 2002, 2006 IBM Corporation and others. + * Copyright (c) 2002, 2014 IBM Corporation and others. * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * http://www.eclipse.org/legal/epl-v10.html * * Contributors: - * Rational Software - Initial API and implementation + * Rational Software - Initial API and implementation *******************************************************************************/ package org.eclipse.cdt.internal.core.util; - /** * The SortOperation takes a collection of objects and returns * a sorted collection of these objects. The sorting of these @@ -22,6 +21,7 @@ package org.eclipse.cdt.internal.core.util; public class ToStringSorter { Object[] sortedObjects; String[] sortedStrings; + /** * Returns true if stringTwo is 'greater than' stringOne * This is the 'ordering' method of the sort operation. @@ -29,13 +29,14 @@ public class ToStringSorter { public boolean compare(String stringOne, String stringTwo) { return stringOne.compareTo(stringTwo) < 0; } + /** * Sort the objects in sorted collection and return that collection. */ private void quickSort(int left, int right) { int originalLeft = left; int originalRight = right; - int midIndex = (left + right) / 2; + int midIndex = (left + right) >>> 1; String midToString = this.sortedStrings[midIndex]; do { @@ -60,6 +61,7 @@ public class ToStringSorter { if (left < originalRight) quickSort(left, originalRight); } + /** * Return a new sorted collection from this unsorted collection. * Sort using quick sort. diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java index ed518c28ec3..2608f573256 100644 --- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java +++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/core/parser/util/ArrayUtil.java @@ -36,7 +36,7 @@ public abstract class ArrayUtil { * the given class object. */ @SuppressWarnings("unchecked") - static public <T> T[] append(Class<T> c, T[] array, T obj) { + public static <T> T[] append(Class<T> c, T[] array, T obj) { if (obj == null) return array; if (array == null || array.length == 0) { @@ -65,7 +65,7 @@ public abstract class ArrayUtil { * Object. */ @SuppressWarnings("unchecked") - static public <T> T[] append(T[] array, T obj) { + public static <T> T[] append(T[] array, T obj) { if (obj == null) return array; if (array == null || array.length == 0) { @@ -90,22 +90,21 @@ public abstract class ArrayUtil { /** * Assumes that array contains {@code null}s at the end, only. - * @returns index of first {@code null}, or -1 + * + * @return index of first {@code null}, or -1 */ private static int findFirstNull(Object[] array) { - boolean haveNull= false; - int left= 0; - int right= array.length - 1; - while (left <= right) { - int mid= (left + right) / 2; + int low= 0; + int high= array.length; + while (low < high) { + int mid= (low + high) >>> 1; if (array[mid] == null) { - haveNull= true; - right= mid - 1; + high= mid; } else { - left= mid + 1; + low= mid + 1; } } - return haveNull ? right + 1 : -1; + return high < array.length ? high : -1; } /** @@ -114,7 +113,7 @@ public abstract class ArrayUtil { */ @Deprecated @SuppressWarnings("unchecked") - static public Object[] append(Class<?> c, Object[] array, int currentLength, Object obj) { + public static Object[] append(Class<?> c, Object[] array, int currentLength, Object obj) { return appendAt((Class<Object>) c, array, currentLength, obj); } @@ -124,7 +123,7 @@ public abstract class ArrayUtil { * @since 5.1 */ @SuppressWarnings("unchecked") - static public <T> T[] appendAt(Class<T> c, T[] array, int currentLength, T obj) { + public static <T> T[] appendAt(Class<T> c, T[] array, int currentLength, T obj) { if (obj == null) return array; if (array == null || array.length == 0) { @@ -155,7 +154,7 @@ public abstract class ArrayUtil { * @return The modified array, which may be the same as the first parameter. * @since 5.4 */ - static public <T> T[] appendAt(T[] array, int currentLength, T obj) { + public static <T> T[] appendAt(T[] array, int currentLength, T obj) { if (obj == null) return array; if (currentLength >= array.length) { @@ -180,7 +179,7 @@ public abstract class ArrayUtil { * @param forceNew */ @SuppressWarnings("unchecked") - static public <T> T[] trim(Class<T> c, T[] array, boolean forceNew) { + public static <T> T[] trim(Class<T> c, T[] array, boolean forceNew) { if (array == null) return (T[]) Array.newInstance(c, 0); @@ -214,7 +213,7 @@ public abstract class ArrayUtil { * @param forceNew * @since 5.2 */ - static public <T> T[] trim(T[] array, boolean forceNew) { + public static <T> T[] trim(T[] array, boolean forceNew) { int i = array.length; if (i == 0 || array[i - 1] != null) { if (!forceNew) { @@ -235,7 +234,7 @@ public abstract class ArrayUtil { * @param array the array to be trimmed * @since 5.2 */ - static public <T> T[] trim(T[] array) { + public static <T> T[] trim(T[] array) { return trim(array, false); } @@ -250,7 +249,7 @@ public abstract class ArrayUtil { * @return the modified array, which may be the same as the first parameter. * @since 5.4 */ - static public <T> T[] trim(T[] array, int newLength) { + public static <T> T[] trim(T[] array, int newLength) { if (newLength == array.length) return array; Assert.isTrue(array[newLength] == null); diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/rewrite/changegenerator/ChangeGenerator.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/rewrite/changegenerator/ChangeGenerator.java index 50cf4385bd6..c0a251c7281 100644 --- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/rewrite/changegenerator/ChangeGenerator.java +++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/dom/rewrite/changegenerator/ChangeGenerator.java @@ -601,7 +601,7 @@ public class ChangeGenerator extends ASTVisitor { int low = 0; int high = preprocessorStatements.length; while (low < high) { - int mid = (low + high) / 2; + int mid = (low + high) >>> 1; IASTNode statement = preprocessorStatements[mid]; if (statement.isPartOfTranslationUnitFile() && endOffset(statement) > offset) { high = mid; diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/search/LinkedNamesFinder.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/search/LinkedNamesFinder.java index ebbb4d403ef..c16f8caa6ba 100644 --- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/search/LinkedNamesFinder.java +++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/search/LinkedNamesFinder.java @@ -252,7 +252,7 @@ public class LinkedNamesFinder { int low = 0; int high = comments.length; while (low < high) { - int mid = (low + high) / 2; + int mid = (low + high) >>> 1; int offset = comments[mid].getFileLocation().getNodeOffset(); if (offset < startOffset) { low = mid + 1; diff --git a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/util/TwoArrayQuickSort.java b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/util/TwoArrayQuickSort.java index 43330ffdbcd..4270c58ec7d 100644 --- a/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/util/TwoArrayQuickSort.java +++ b/core/org.eclipse.cdt.ui/src/org/eclipse/cdt/internal/ui/util/TwoArrayQuickSort.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2005, 2006 IBM Corporation and others. + * Copyright (c) 2005, 2014 IBM Corporation and others. * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at @@ -13,18 +13,16 @@ package org.eclipse.cdt.internal.ui.util; import org.eclipse.core.runtime.Assert; - /** * Quick sort to sort two arrays in parallel. */ public class TwoArrayQuickSort { private static void internalSort(String[] keys, Object[] values, int left, int right, boolean ignoreCase) { - int original_left= left; int original_right= right; - String mid= keys[(left + right) / 2]; + String mid= keys[(left + right) >>> 1]; do { while (smaller(keys[left], mid, ignoreCase)) { left++; @@ -53,11 +51,13 @@ public class TwoArrayQuickSort { internalSort(keys, values, left, original_right, ignoreCase); } } + private static boolean smaller(String left, String right, boolean ignoreCase) { if (ignoreCase) return left.compareToIgnoreCase(right) < 0; return left.compareTo(right) < 0; } + /** * Sorts keys and values in parallel. */ |