Bitmap - Performance and Implementation

1
protected static int hybridUnsignedBinarySearch(final short[] array, final int begin,
2
      final int end, final short k) {
3
    int ikey = toIntUnsigned(k);
4
    // next line accelerates the possibly common case where the value would
5
    // be inserted at the end
6
    if ((end > 0) && (toIntUnsigned(array[end - 1]) < ikey)) {
7
      return -end - 1;
8
    }
9
    int low = begin;
10
    int high = end - 1;
11
    // 32 in the next line matches the size of a cache line
12
    while (low + 32 <= high) {
13
      final int middleIndex = (low + high) >>> 1;
14
      final int middleValue = toIntUnsigned(array[middleIndex]);
15

16
      if (middleValue < ikey) {
17
        low = middleIndex + 1;
18
      } else if (middleValue > ikey) {
19
        high = middleIndex - 1;
20
      } else {
21
        return middleIndex;
22
      }
23
    }
24
    // we finish the job with a sequential search
25
    int x = low;
26
    for (; x <= high; ++x) {
27
      final int val = toIntUnsigned(array[x]);
28
      if (val >= ikey) {
29
        if (val == ikey) {
30
          return x;
31
        }
32
        break;
33
      }
34
    }
35
    return -(x + 1);
36
}

1
short[] content;
2

3
@Override
4
public Container add(final short x) {
5
    int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);
6
    if (loc < 0) {
7
      // Transform the ArrayContainer to a BitmapContainer
8
      // when cardinality = DEFAULT_MAX_SIZE
9
      if (cardinality >= DEFAULT_MAX_SIZE) {
10
        BitmapContainer a = this.toBitmapContainer();
11
        a.add(x);
12
        return a;
13
      }
14
      if (cardinality >= this.content.length) {
15
        increaseCapacity();
16
      }
17
      // insertion : shift the elements > x by one position to
18
      // the right
19
      // and put x in it's appropriate place
20
      System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);
21
      content[-loc - 1] = x;
22
      ++cardinality;
23
    }
24
    return this;
25
}

1
final long[] bitmap;
2

3
@Override
4
public Container add(final short i) {
5
    final int x = Util.toIntUnsigned(i);
6
    final long previous = bitmap[x / 64];
7
    long newval = previous | (1L << x);
8
    bitmap[x / 64] = newval;
9
    if (USE_BRANCHLESS) {
10
      cardinality += (previous ^ newval) >>> x;
11
    } else if (previous != newval) {
12
      ++cardinality;
13
    }
14
    return this;
15
}

1
private short[] valueslength;
2
int nbrruns = 0;

1
@Override
2
public Container add(short k) {
3
    // TODO: it might be better and simpler to do return
4
    // toBitmapOrArrayContainer(getCardinality()).add(k)
5
    // but note that some unit tests use this method to build up test runcontainers without calling
6
    // runOptimize
7
    int index = unsignedInterleavedBinarySearch(valueslength, 0, nbrruns, k);
8
    if (index >= 0) {
9
      return this;// already there
10
    }
11
    index = -index - 2;// points to preceding value, possibly -1
12
    if (index >= 0)   {// possible match
13
      int offset = toIntUnsigned(k) - toIntUnsigned(getValue(index));
14
      int le = toIntUnsigned(getLength(index));
15
      if (offset <= le) {
16
        return this;
17
      }
18
      if (offset == le + 1) {
19
        // we may need to fuse
20
        if (index + 1 < nbrruns) {
21
          if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
22
            // indeed fusion is needed
23
            setLength(index,
24
                (short) (getValue(index + 1) + getLength(index + 1) - getValue(index)));
25
            recoverRoomAtIndex(index + 1);
26
            return this;
27
          }
28
        }
29
        incrementLength(index);
30
        return this;
31
      }
32
      if (index + 1 < nbrruns) {
33
        // we may need to fuse
34
        if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
35
          // indeed fusion is needed
36
          setValue(index + 1, k);
37
          setLength(index + 1, (short) (getLength(index + 1) + 1));
38
          return this;
39
        }
40
      }
41
    }
42
    if (index == -1) {
43
      // we may need to extend the first run
44
      if (0 < nbrruns) {
45
        if (getValue(0) == k + 1) {
46
          incrementLength(0);
47
          decrementValue(0);
48
          return this;
49
        }
50
      }
51
    }
52
    makeRoomAtIndex(index + 1);
53
    setValue(index + 1, k);
54
    setLength(index + 1, (short) 0);
55
    return this;
56
}