test_class.file: oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexV1Test.java
test_class.identifier: IndexV1Test
test_case.body: @Test
      public void testFindEntry() throws Exception {
          Buffer buffer = Buffer.allocate(4 * IndexEntryV1.SIZE);
          buffer.duplicate()
                  .putLong(1).putLong(1).putInt(0).putInt(0).putInt(0)
                  .putLong(1).putLong(3).putInt(0).putInt(0).putInt(0)
                  .putLong(3).putLong(1).putInt(0).putInt(0).putInt(0)
                  .putLong(3).putLong(3).putInt(0).putInt(0).putInt(0);
          IndexV1 index = new IndexV1(buffer);
          assertEquals(-1, index.findEntry(1, 0));
          assertEquals(0, index.findEntry(1, 1));
          assertEquals(-1, index.findEntry(1, 2));
          assertEquals(1, index.findEntry(1, 3));
          assertEquals(-1, index.findEntry(3, 0));
          assertEquals(2, index.findEntry(3, 1));
          assertEquals(-1, index.findEntry(3, 2));
          assertEquals(3, index.findEntry(3, 3));
      }
test_case.class_method_signature: IndexV1Test.testFindEntry()
test_case.full_signature: @Test public void testFindEntry()
test_case.identifier: testFindEntry
test_case.invocations: allocate putInt putInt putInt putLong putLong putInt putInt putInt putLong putLong putInt putInt putInt putLong putLong putInt putInt putInt putLong putLong duplicate assertEquals findEntry assertEquals findEntry assertEquals findEntry assertEquals findEntry assertEquals findEntry assertEquals findEntry assertEquals findEntry assertEquals findEntry
test_case.modifiers: @Test public
test_case.parameters: ()
test_case.return: void
test_case.signature: void testFindEntry()
focal_class.declarator: FOOTER_SIZE = 16
focal_class.modifier: static final
focal_class.original_string: static final int FOOTER_SIZE = 16;
focal_class.type: int
focal_class.var_name: FOOTER_SIZE
focal_class.declarator: entries
focal_class.modifier: private final
focal_class.original_string: private final Buffer entries;
focal_class.type: Buffer
focal_class.var_name: entries
focal_class.file: oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexV1.java
focal_class.identifier: IndexV1
focal_class.interfaces: implements Index
focal_class.class_method_signature: IndexV1.IndexV1(Buffer entries)
focal_class.full_signature:   IndexV1(Buffer entries)
focal_class.identifier: IndexV1
focal_class.parameters: (Buffer entries)
focal_class.signature:  IndexV1(Buffer entries)
focal_class.class_method_signature: IndexV1.getUUIDs()
focal_class.full_signature: @Override public Set<UUID> getUUIDs()
focal_class.identifier: getUUIDs
focal_class.modifiers: @Override public
focal_class.parameters: ()
focal_class.return: Set<UUID>
focal_class.signature: Set<UUID> getUUIDs()
focal_class.class_method_signature: IndexV1.findEntry(long msb, long lsb)
focal_class.full_signature: @Override public int findEntry(long msb, long lsb)
focal_class.identifier: findEntry
focal_class.modifiers: @Override public
focal_class.parameters: (long msb, long lsb)
focal_class.return: int
focal_class.signature: int findEntry(long msb, long lsb)
focal_class.class_method_signature: IndexV1.size()
focal_class.full_signature: @Override public int size()
focal_class.identifier: size
focal_class.modifiers: @Override public
focal_class.parameters: ()
focal_class.return: int
focal_class.signature: int size()
focal_class.class_method_signature: IndexV1.count()
focal_class.full_signature: @Override public int count()
focal_class.identifier: count
focal_class.modifiers: @Override public
focal_class.parameters: ()
focal_class.return: int
focal_class.signature: int count()
focal_class.class_method_signature: IndexV1.entry(int i)
focal_class.full_signature: @Override public IndexEntryV1 entry(int i)
focal_class.identifier: entry
focal_class.modifiers: @Override public
focal_class.parameters: (int i)
focal_class.return: IndexEntryV1
focal_class.signature: IndexEntryV1 entry(int i)
focal_method.body: @Override
      public int findEntry(long msb, long lsb) {
          // The segment identifiers are randomly generated with uniform
          // distribution, so we can use interpolation search to find the
          // matching entry in the index. The average runtime is O(log log n).
  
          int lowIndex = 0;
          int highIndex = entries.remaining() / IndexEntryV1.SIZE - 1;
          float lowValue = Long.MIN_VALUE;
          float highValue = Long.MAX_VALUE;
          float targetValue = msb;
  
          while (lowIndex <= highIndex) {
              int guessIndex = lowIndex + Math.round(
                      (highIndex - lowIndex)
                              * (targetValue - lowValue)
                              / (highValue - lowValue));
              int position = entries.position() + guessIndex * IndexEntryV1.SIZE;
              long m = entries.getLong(position);
              if (msb < m) {
                  highIndex = guessIndex - 1;
                  highValue = m;
              } else if (msb > m) {
                  lowIndex = guessIndex + 1;
                  lowValue = m;
              } else {
                  // getting close...
                  long l = entries.getLong(position + 8);
                  if (lsb < l) {
                      highIndex = guessIndex - 1;
                      highValue = m;
                  } else if (lsb > l) {
                      lowIndex = guessIndex + 1;
                      lowValue = m;
                  } else {
                      return position / IndexEntryV1.SIZE;
                  }
              }
          }
  
          return -1;
      }
focal_method.class_method_signature: IndexV1.findEntry(long msb, long lsb)
focal_method.full_signature: @Override public int findEntry(long msb, long lsb)
focal_method.identifier: findEntry
focal_method.invocations: remaining round position getLong getLong
focal_method.modifiers: @Override public
focal_method.parameters: (long msb, long lsb)
focal_method.return: int
focal_method.signature: int findEntry(long msb, long lsb)