Document behaviour of IntegerUtils.shiftLeftFromSpecifiedPosition

[richardstartin]

I found this method after discovering (from an OOME in tests) that within the ART module ints are modified by unpacking to a byte[], performing the modification, and then packing back to an int again.

IntegerUtils.shiftLeftFromSpecifiedPosition looks a little odd to me:

  /**
   * shift the byte left from the specified position
   * @param v a integer value
   * @param pos the position from which to shift byte values left
   * @param count the shifting numbers
   * @return a fresh integer value
   */
  public static int shiftLeftFromSpecifiedPosition(int v, int pos, int count) {
    byte[] initialVal = toBDBytes(v);
    System.arraycopy(initialVal, pos + 1, initialVal, pos, count);
    return fromBDBytes(initialVal);
  }

The following test case, which covers the combinations of position and count for which the method doesn't throw, passes:

  @Test
  public void testShiftLeftFromSpecifiedPosition() {
    assertEquals(0xBBCCDDDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 0, 3));
    assertEquals(0xBBCCCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 0, 2));
    assertEquals(0xBBBBCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 0, 1));
    assertEquals(0xAABBCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 0, 0));
    assertEquals(0xAACCDDDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 1, 2));
    assertEquals(0xAACCCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 1, 1));
    assertEquals(0xAABBCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 1, 0));
    assertEquals(0xAABBDDDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 2, 1));
    assertEquals(0xAABBCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 2, 0));
    assertEquals(0xAABBCCDD, IntegerUtil.shiftLeftFromSpecifiedPosition(0xAABBCCDD, 3, 0));
  }

The method is only used in node removal, which is unlikely to be widely used. The pattern above looks a little suspicious to me, so the behaviour in node removal is either quite subtle or perhaps wrong:

  @Override
  public Node remove(int pos) {
    assert pos < count;
    children[pos] = null;
    count--;
    key = IntegerUtil.shiftLeftFromSpecifiedPosition(key, pos, (4 - pos - 1));
    for (; pos < count; pos++) {
      children[pos] = children[pos + 1];
    }
    if (count == 1) {
      //shrink to leaf node
      Node child = children[0];
      byte newLength = (byte) (child.prefixLength + this.prefixLength + 1);
      byte[] newPrefix = new byte[newLength];
      System.arraycopy(this.prefix, 0, newPrefix, 0, this.prefixLength);
      newPrefix[this.prefixLength] = IntegerUtil.firstByte(key);
      System.arraycopy(child.prefix, 0, newPrefix, this.prefixLength + 1, child.prefixLength);
      child.prefixLength = newLength;
      child.prefix = newPrefix;
      return child;
    }
    return this;
  }

If the method's implementation is correct, I think explaining the logic for modifying the key when removing nodes would be helpful.

[weijietong]

shiftLeftFromSpecifiedPosition() is to move the bytes after the removed position to a previouse position one by one. For example: the four bytes of the key is : 8,11, 13, 16 , now we remove the position 2 key(13), then move the afterward key value (16) to key value(13) poistion ,that is the final keys would be : 8, 11, 16,16;

[weijietong]

If the 4 bytes not stored as an int to save the java array object memory footprint,and stored as byte[4] keys, the logic would be as follow :

for (; pos < cout; pos++) { keys[pos]=keys[pos + 1]};

[weijietong]

@richardstartin if you still wanna this, would be appreciate you could give a concise description to document this behavior in your native language or pr it.