Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-5045582

(coll) binarySearch() fails for size larger than 1<<30

    Details

    • Subcomponent:
    • Resolved In Build:
      b83
    • CPU:
      generic, x86
    • OS:
      generic, linux
    • Verification:
      Verified

      Description

      Name: rmT116609 Date: 05/11/2004


      FULL PRODUCT VERSION :
      java version "1.5.0-beta"
      Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-beta-b32c)
      Java HotSpot(TM) Client VM (build 1.5.0-beta-b32c, mixed mode)


      ADDITIONAL OS VERSION INFORMATION :
      Linux freeway 2.4.21-4-686 #1 Sat Aug 2 23:27:25 EST 2003 i686 GNU/Linux


      A DESCRIPTION OF THE PROBLEM :
      java.util.Arrays.binarySearch() will throw an ArrayIndexOutOfBoundsException if the array
      is large. This is caused by overflow in the calculation:

                 int mid = (low + high) >> 1;

      The correct calculation uses unsigned shift:

                 int mid = (low + high) >>> 1;

      There are similar problems in Collections, and TreeMap also includes the faulty calculation

                 int mid = (lo + hi) / 2;

      There may be others.


      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Run the included code example.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The code should print

      index = 1099999999

      ACTUAL -
      The code printed

      Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
              at java.util.Arrays.binarySearch(Arrays.java:1509)
              at infinitum.tom.Search.main(Search.java:7)


      ERROR MESSAGES/STACK TRACES THAT OCCUR :
      $ /jdk/j2sdk1.5.0/bin/java -Xmx1200m -server Search
      Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1064671149
              at java.util.Arrays.binarySearch(Arrays.java:1509)
              at infinitum.tom.Search.main(Search.java:7)


      REPRODUCIBILITY :
      This bug can be reproduced rarely.

      ---------- BEGIN SOURCE ----------
      class Search {
          public static void main (String[] args) {
              byte[] b = new byte[1100000000];
              b[b.length - 1] = 1;
              int index = java.util.Arrays.binarySearch(b, (byte)1);
              System.out.println("index = " + index);
          }
      }
      ---------- END SOURCE ----------
      (Incident Review ID: 261136)
      ======================================================================

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                martin Martin Buchholz
                Reporter:
                rmandalasunw Ranjith Mandala (Inactive)
              • Votes:
                0 Vote for this issue
                Watchers:
                2 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:
                  Imported:
                  Indexed: