unordered_fast_key_table_internal.h

// unordered_fast_key_table_internal.h


/*    Copyright 2012 10gen Inc.
 *
 *    Licensed under the Apache License, Version 2.0 (the "License");
 *    you may not use this file except in compliance with the License.
 *    You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing, software
 *    distributed under the License is distributed on an "AS IS" BASIS,
 *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *    See the License for the specific language governing permissions and
 *    limitations under the License.
 */

#include "mongo/util/assert_util.h"
#include "mongo/util/debug_util.h"

namespace mongo {
template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(unsigned capacity,
                                                                     double maxProbeRatio)
    : _capacity(capacity),
      _maxProbe(static_cast<unsigned>(capacity * maxProbeRatio)),
      _entries(new Entry[_capacity]) {}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::Area(const Area& other)
    : _capacity(other._capacity), _maxProbe(other._maxProbe), _entries(new Entry[_capacity]) {
    for (unsigned i = 0; i < _capacity; i++) {
        _entries[i] = other._entries[i];
    }
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline int UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::find(
    const K_L& key, size_t hash, int* firstEmpty, const UnorderedFastKeyTable& sm) const {
    if (firstEmpty)
        *firstEmpty = -1;

    for (unsigned probe = 0; probe < _maxProbe; probe++) {
        unsigned pos = (hash + probe) % _capacity;

        if (!_entries[pos].used) {
            // space is empty
            if (firstEmpty && *firstEmpty == -1)
                *firstEmpty = pos;
            if (!_entries[pos].everUsed)
                return -1;
            continue;
        }

        if (_entries[pos].curHash != hash) {
            // space has something else
            continue;
        }

        if (!sm._equals(key, sm._convertor(_entries[pos].data.first))) {
            // hashes match
            // strings are not equals
            continue;
        }

        // hashes and strings are equal
        // yay!
        return pos;
    }
    return -1;
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline bool UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::Area::transfer(
    Area* newArea, const UnorderedFastKeyTable& sm) const {
    for (unsigned i = 0; i < _capacity; i++) {
        if (!_entries[i].used)
            continue;

        int firstEmpty = -1;
        int loc = newArea->find(
            sm._convertor(_entries[i].data.first), _entries[i].curHash, &firstEmpty, sm);

        verify(loc == -1);
        if (firstEmpty < 0) {
            return false;
        }

        newArea->_entries[firstEmpty] = _entries[i];
    }
    return true;
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable(
    unsigned startingCapacity, double maxProbeRatio)
    : _maxProbeRatio(maxProbeRatio), _area(startingCapacity, maxProbeRatio) {
    _size = 0;
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::UnorderedFastKeyTable(
    const UnorderedFastKeyTable& other)
    : _size(other._size),
      _maxProbeRatio(other._maxProbeRatio),
      _area(other._area),
      _hash(other._hash),
      _equals(other._equals),
      _convertor(other._convertor),
      _convertorOther(other._convertorOther) {}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::copyTo(
    UnorderedFastKeyTable* out) const {
    out->_size = _size;
    out->_maxProbeRatio = _maxProbeRatio;
    Area x(_area);
    out->_area.swap(&x);
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline V& UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::get(const K_L& key) {
    const size_t hash = _hash(key);

    for (int numGrowTries = 0; numGrowTries < 5; numGrowTries++) {
        int firstEmpty = -1;
        int pos = _area.find(key, hash, &firstEmpty, *this);
        if (pos >= 0)
            return _area._entries[pos].data.second;

        // key not in map
        // need to add
        if (firstEmpty >= 0) {
            _size++;
            _area._entries[firstEmpty].used = true;
            _area._entries[firstEmpty].everUsed = true;
            _area._entries[firstEmpty].curHash = hash;
            _area._entries[firstEmpty].data.first = _convertorOther(key);
            return _area._entries[firstEmpty].data.second;
        }

        // no space left in map
        _grow();
    }
    msgasserted(16471, "UnorderedFastKeyTable couldn't add entry after growing many times");
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline size_t UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase(const K_L& key) {
    const size_t hash = _hash(key);
    int pos = _area.find(key, hash, NULL, *this);

    if (pos < 0)
        return 0;

    --_size;
    _area._entries[pos].used = false;
    _area._entries[pos].data.second = V();
    return 1;
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::erase(const_iterator it) {
    dassert(it._position >= 0);
    dassert(it._area == &_area);

    --_size;
    _area._entries[it._position].used = false;
    _area._entries[it._position].data.second = V();
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline void UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::_grow() {
    unsigned capacity = _area._capacity;
    for (int numGrowTries = 0; numGrowTries < 5; numGrowTries++) {
        capacity *= 2;
        Area newArea(capacity, _maxProbeRatio);
        bool success = _area.transfer(&newArea, *this);
        if (!success) {
            continue;
        }
        _area.swap(&newArea);
        return;
    }
    msgasserted(16845, "UnorderedFastKeyTable::_grow couldn't add entry after growing many times");
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::find(const K_L& key) const {
    if (_size == 0)
        return const_iterator();
    int pos = _area.find(key, _hash(key), 0, *this);
    if (pos < 0)
        return const_iterator();
    return const_iterator(&_area, pos);
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::end() const {
    return const_iterator();
}

template <typename K_L, typename K_S, typename V, typename H, typename E, typename C, typename C_LS>
inline typename UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::const_iterator
UnorderedFastKeyTable<K_L, K_S, V, H, E, C, C_LS>::begin() const {
    return const_iterator(&_area);
}
}