Method _insertOnly

Fleece/Support/StringTable.cc:158–183

Subroutine of insertOnly() and grow() that doesn't bump count or grow table. This repeats a lot of the logic of insert(), but I decided performance trumps DRY.

    // Subroutine of insertOnly() and grow() that doesn't bump count or grow table.
    // This repeats a lot of the logic of insert(), but I decided performance trumps DRY.
    __hot void StringTable::_insertOnly(hash_t hash, entry_t entry) noexcept {
        assert_precondition(entry.first);
        assert_precondition(hash != hash_t::Empty);
        ssize_t distance = 0;
        auto maxDistance = _maxDistance;
        // Walk along the table looking for an empty space:
        size_t i;
        for (i = indexOfHash(hash); _hashes[i] != hash_t::Empty; i = wrap(i + 1)) {
            assert(distance < _count);
            ssize_t itsDistance = wrap(i - indexOfHash(_hashes[i]) + _size);
            if (itsDistance < distance) {
                // Robin Hood hashing: Put new item where a less-distant existing item was:
                std::swap(hash,  _hashes[i]);
                std::swap(entry, _entries[i]);
                maxDistance = std::max(distance, maxDistance);
                distance = itsDistance;
                // Then continue, to find a new spot for the existing item we removed...
            }
            ++distance;
        }

        // Now place the final item in the empty space:
        _hashes[i]  = hash;
        _entries[i] = std::move(entry);
        _maxDistance = std::max(distance, maxDistance);
    }


#pragma mark - TABLE ALLOCATION: