protected int insertionIndex()

in core/src/main/java/gnu/trove/TIntHash.java [217:263]

• 38 lines of code
• 15 McCabe index (conditional complexity)

  protected int insertionIndex(int val) {
    if (_set == null) {
      setUp((int)(DEFAULT_INITIAL_CAPACITY / DEFAULT_LOAD_FACTOR + 1));
    }
    byte[] states = _states;
    int[] set = _set;
    int length = states.length;
    int hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
    int index = hash % length;

    if (states[index] == FREE) {
      return index;       // empty, all done
    }
    else if (states[index] == FULL && set[index] == val) {
      return -index - 1;   // already stored
    }
    else {                // 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.
      do {
        index -= probe;
        if (index < 0) {
          index += length;
        }
      }
      while (states[index] == FULL && 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 (states[index] == REMOVED) {
        int firstRemoved = index;
        while (states[index] != FREE &&
               (states[index] == REMOVED || set[index] != val)) {
          index -= probe;
          if (index < 0) {
            index += length;
          }
        }
        return states[index] == FULL ? -index - 1 : firstRemoved;
      }
      // if it's full, the key is already stored
      return states[index] == FULL ? -index - 1 : index;
    }
  }