find_slot()

template<typename Key, typename T, typename Hash = Hash<Key>, typename KeyEqual = EqualTo<Key>, int INLINED_COUNT = FASTLED_HASHMAP_INLINED_COUNT>

pair< size_t, bool > fl::HashMap< Key, T, Hash, KeyEqual, INLINED_COUNT >::find_slot ( const Key & key ) const

inlineprivate

Definition at line 333 of file hash_map.h.

                                                       {
        const size_t cap = _buckets.size();
        const size_t mask = cap - 1;
        const size_t h = _hash(key) & mask;
        size_t first_tomb = npos;
 
        if (cap <= 8) {
            // linear probing
            for (size_t i = 0; i < cap; ++i) {
                const size_t idx = (h + i) & mask;
 
                if (is_empty(idx))
                    return {first_tomb != npos ? first_tomb : idx, true};
                if (is_deleted(idx)) {
                    if (first_tomb == npos)
                        first_tomb = idx;
                } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) {
                    return {idx, false};
                }
            }
        } else {
            // quadratic probing up to 8 tries
            size_t i = 0;
            for (; i < 8; ++i) {
                const size_t idx = (h + i + i * i) & mask;
 
                if (is_empty(idx))
                    return {first_tomb != npos ? first_tomb : idx, true};
                if (is_deleted(idx)) {
                    if (first_tomb == npos)
                        first_tomb = idx;
                } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) {
                    return {idx, false};
                }
            }
            // fallback to linear for the rest
            for (; i < cap; ++i) {
                const size_t idx = (h + i) & mask;
 
                if (is_empty(idx))
                    return {first_tomb != npos ? first_tomb : idx, true};
                if (is_deleted(idx)) {
                    if (first_tomb == npos)
                        first_tomb = idx;
                } else if (is_occupied(idx) && _equal(_buckets[idx].key, key)) {
                    return {idx, false};
                }
            }
        }
 
        return {npos, false};
    }

Referenced by fl::HashMap< Key, T, Hash, KeyEqual >::insert(), and fl::HashMap< Key, T, Hash, KeyEqual >::operator[]().

Here is the caller graph for this function: