private int insertionIndex()

in core/src/main/java/gnu/trove/TIntObjectHashMap.java [338:393]
41 lines of code
18 McCabe index (conditional complexity)

  private int insertionIndex(int val) {
    if (_values == EMPTY_OBJECT_ARRAY) {
      setUp((int)(DEFAULT_INITIAL_CAPACITY / DEFAULT_LOAD_FACTOR + 1));
    }
    Object[] values = _values;
    int[] set = _set;
    int length = set.length;
    int hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
    int index = hash % length;

    if (isFree(values, index)) {
      return index;       // empty, all done
    }
    if (isFull(values, index) && set[index] == val) {
      return -index - 1;   // already stored
    }

    // already FULL or REMOVED, must probe
    // compute the double hash
    int probe = 1 + (hash % (length - 2));
    // starting at the natural offset, probe until we find an
    // offset that isn't full.

    // keep track of the first removed cell. it's the natural candidate for re-insertion
    int firstRemoved = isRemoved(values, index) ? index : -1;

    do {
      index -= probe;
      if (index < 0) {
        index += length;
      }
      if (firstRemoved == -1 && isRemoved(values, index)) {
        firstRemoved = index;
      }
    }
    while (isFull(values, index) && set[index] != val);

    // if the index we found was removed: continue probing until we
    // locate a free location or an element which equal()s the
    // one we have.
    if (isRemoved(values, index)) {
      while (!isFree(values, index) &&
             (isRemoved(values, index) || set[index] != val)) {
        index -= probe;
        if (index < 0) {
          index += length;
        }
      }
    }
    // if it's full, the key is already stored
    if (isFull(values, index)) {
      return -index - 1;
    }

    return firstRemoved == -1 ? index : firstRemoved;
  }