protected int insertionIndex()

in core/src/main/java/gnu/trove/TObjectHash.java [228:288]
45 lines of code
19 McCabe index (conditional complexity)

  protected int insertionIndex(T obj) {
    if (_set == EMPTY_OBJECT_ARRAY) {
      setUp((int)(DEFAULT_INITIAL_CAPACITY / DEFAULT_LOAD_FACTOR + 1));
    }
    Object[] set = _set;
    int length = set.length;
    int hash = _hashingStrategy.computeHashCode(obj) & 0x7fffffff;
    int index = hash % length;
    Object cur = set[index];

    if (cur == null) {
      return index;       // empty, all done
    }
    if (cur != REMOVED && _hashingStrategy.equals((T)cur, obj)) {
      return -index - 1;   // already stored
    }

    // already FULL or REMOVED, must probe
    // compute the double hash
    int probe = 1 + hash % (length - 2);

    // keep track of the first removed cell. it's the natural candidate for re-insertion
    int firstRemoved = cur == REMOVED ? index : -1;

    // starting at the natural offset, probe until we find an
    // offset that isn't full.
    do {
      index -= probe;
      if (index < 0) {
        index += length;
      }
      cur = set[index];
      if (firstRemoved == -1 && cur == REMOVED) {
        firstRemoved = index;
      }
    }
    while (cur != null
           && cur != REMOVED
           && !_hashingStrategy.equals((T)cur, obj));

    // 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 (cur == REMOVED) {
      while (cur != null
             && (cur == REMOVED || !_hashingStrategy.equals((T)cur, obj))) {
        index -= probe;
        if (index < 0) {
          index += length;
        }
        cur = set[index];
      }
    }

    // if it's full, the key is already stored
    if (cur != null) {
      return -index - 1;
    }

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