unordered_fast_key_table.h

// unordered_fast_key_table.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.
 */

#pragma once

#include <boost/smart_ptr/scoped_array.hpp>

#include "mongo/base/disallow_copying.h"

namespace mongo {

    template<typename K_L, typename K_S>
    struct UnorderedFastKeyTable_LS_C {
        K_S operator()( const K_L& a ) const {
            return K_S(a);
        }
    };

    template< typename K_L, // key lookup
              typename K_S, // key storage
              typename V, // value
              typename H , // hash of K_L
              typename E, // equal of K_L
              typename C, // convertor from K_S -> K_L
              typename C_LS=UnorderedFastKeyTable_LS_C<K_L,K_S> // convertor from K_L -> K_S
              >
    class UnorderedFastKeyTable {
    public:
        typedef std::pair<K_S, V> value_type;
        typedef K_L key_type;
        typedef V mapped_type;

    private:
        struct Entry {
            Entry()
                : used( false ), everUsed( false ) {
            }

            bool used;
            bool everUsed;
            size_t curHash;
            value_type data;
        };

        struct Area {
            Area( unsigned capacity, double maxProbeRatio );
            Area( const Area& other );

            int find( const K_L& key, size_t hash, int* firstEmpty, const UnorderedFastKeyTable& sm ) const;

            bool transfer( Area* newArea, const UnorderedFastKeyTable& sm ) const;

            void swap( Area* other ) {
                using std::swap;
                swap( _capacity, other->_capacity );
                swap( _maxProbe, other->_maxProbe );
                swap( _entries, other->_entries );
            }

            unsigned _capacity;
            unsigned _maxProbe;
            boost::scoped_array<Entry> _entries;
        };

    public:
        static const unsigned DEFAULT_STARTING_CAPACITY = 20;

        UnorderedFastKeyTable( unsigned startingCapacity = DEFAULT_STARTING_CAPACITY,
                               double maxProbeRatio = 0.05 );

        UnorderedFastKeyTable( const UnorderedFastKeyTable& other );

        UnorderedFastKeyTable& operator=( const UnorderedFastKeyTable& other ) {
            other.copyTo( this );
            return *this;
        }

        void copyTo( UnorderedFastKeyTable* out ) const;

        size_t size() const { return _size; }

        bool empty() const { return _size == 0; }

        /*
         * @return storage space
         */
        size_t capacity() const { return _area._capacity; }

        V& operator[]( const K_L& key ) { return get( key ); }

        V& get( const K_L& key );

        size_t erase( const K_L& key );

        class const_iterator {
            friend class UnorderedFastKeyTable;

        public:
            const_iterator() { _position = -1; }
            const_iterator( const Area* area ) {
                _area = area;
                _position = 0;
                _max = _area->_capacity - 1;
                _skip();
            }
            const_iterator( const Area* area, int pos ) {
                _area = area;
                _position = pos;
                _max = pos;
            }

            const value_type* operator->() const { return &_area->_entries[_position].data; }

            const value_type& operator*() const { return _area->_entries[_position].data; }

            const_iterator operator++() {
                if ( _position < 0 )
                    return *this;
                _position++;
                if ( _position > _max )
                    _position = -1;
                else
                    _skip();
                return *this;
            }

            bool operator==( const const_iterator& other ) const {
                return _position == other._position;
            }
            bool operator!=( const const_iterator& other ) const {
                return _position != other._position;
            }

        private:

            void _skip() {
                while ( true ) {
                    if ( _area->_entries[_position].used )
                        break;
                    if ( _position >= _max ) {
                        _position = -1;
                        break;
                    }
                    ++_position;
                }
            }

            const Area* _area;
            int _position;
            int _max; // inclusive
        };

        void erase( const_iterator it );

        const_iterator find( const K_L& key ) const;

        const_iterator begin() const;

        const_iterator end() const;

    private:
        /*
         * @param firstEmpty, if we return -1, and firstEmpty != NULL,
         *                    this will be set to the first empty bucket we found
         * @retrun offset into _entries or -1 if not there
         */
        int _find( const K_L& key, int hash, int* firstEmpty ) const;

        void _grow();

        // ----

        size_t _size;
        double _maxProbeRatio;
        Area _area;

        H _hash;
        E _equals;
        C _convertor;
        C_LS _convertorOther;
    };

}

#include "mongo/util/unordered_fast_key_table_internal.h"