map_t.hpp

Go to the documentation of this file.

/*
 * Title:        bits/map_t.hpp
 * Description:  C++ header-only wrapper for C-ABI data_t type
 * $Copyright (c) 2015-2016 Software AG, Darmstadt, Germany and/or Software AG USA Inc., Reston, VA, USA, and/or its subsidiaries and/or its affiliates and/or their licensors.$
 * Use, reproduction, transfer, publication or disclosure is prohibited except as specifically provided for in your License Agreement with Software AG
 * @Version:     $Id: map_t.hpp 294926 2016-11-09 18:33:24Z matj $
 */

#ifndef _DATAT_BITS_INCLUDE_TAG
#error Must only be included from sag_connectivity_cpp.hpp, use that instead
#endif

class map_t: protected sag_underlying_map_t
{
        friend class data_t;
        friend class Message;
        static size_t MIN_CAPACITY() { return 8; }
protected:
        typedef sag_underlying_map_table_entry_t item_t;
        typedef int64_t hash_t;
public:

        template<typename DATA>
        struct pair
        {
                hash_t hash;
                DATA first;
                DATA second;
        };

        template<typename DATA, typename UNDERLYING, typename PAIR>
        struct _iterator: public std::iterator<std::bidirectional_iterator_tag, DATA>
        {
                friend class map_t;
                typedef _iterator<DATA, UNDERLYING, PAIR> iterator;
                typedef PAIR element_t;

                _iterator(): tabledata(0), capacity(0), offs(0) {}
                _iterator(const UNDERLYING &tabledata, size_t capacity, int64_t offs, bool stepToItem=false)
                        : tabledata(tabledata), capacity(capacity), offs(offs)
                {
                        if (!valid() && stepToItem) {
                                operator++();
                        }
                }

                iterator &operator--() 
                {
                        if (offs > -1) {
                                do {
                                        --offs;
                                } while (!valid());
                        }
                        return *this; 
                }
                iterator operator--(int)
                {
                        iterator tmp(*this);
                        operator--();
                        return tmp;
                }
                iterator &operator++()
                {
                        if (offs < capacity) {
                                do {
                                        ++offs;
                                } while (!valid());
                        }
                        return *this; 
                }
                iterator operator++(int)
                {
                        iterator tmp(*this);
                        operator++();
                        return tmp;
                }

                DATA &key() const { return static_cast<DATA&>(tabledata[offs].key); }
                DATA &value() const { return static_cast<DATA&>(tabledata[offs].value); }

                bool operator==(const iterator &other) const 
                {
                        bool b = offs == other.offs;
                        return b;
                }
                bool operator!=(const iterator &other) const 
                {
                        bool b = !operator==(other);
                        return b;
                }
                element_t &operator*() const
                {
                        return reinterpret_cast<element_t &>(tabledata[offs]);
                }
                element_t *operator->() const
                {
                        return reinterpret_cast<element_t *>(tabledata + offs);
                }
        protected:
                bool valid() const
                {       
                        return offs >= capacity || offs < 0 || tabledata[offs].hash > 1 || SAG_DATA_EMPTY != tabledata[offs].key.tag;
                }
                UNDERLYING tabledata;
                int64_t capacity;
                int64_t offs;
        };
        typedef _iterator<data_t, sag_underlying_map_table_entry_t *, pair<data_t> > iterator;
        typedef _iterator<const data_t, sag_underlying_map_table_entry_t const *, const pair<const data_t> > const_iterator;
        typedef pair<data_t> element;
        typedef pair<const data_t> const_element;

        map_t()
        {
                table = 0;
        }
        explicit map_t(size_t n);

        ~map_t()
        {
                clear();
        }

        map_t &operator=(map_t &&other)
        {
                map_t tmp;
                // put us in tmp
                swap(std::move(tmp));
                // put other in us (and by extension the null tmp in other)
                swap(std::move(other));
                return *this;
        }
        map_t(map_t &&other)
        {
                table = 0;
                swap(std::move(other));
        }

        map_t(std::initializer_list<std::pair<data_t,data_t>> l)
        {
                table = 0;
                for (auto it = l.begin(); it != l.end(); ++it) {
                        insert(std::make_pair(it->first.copy(), it->second.copy()));
                }
        }

        void swap(map_t &&other)
        {
                std::swap(table, other.table);
        }

        map_t copy() const
        {
                map_t newmap(size());
                for (const_iterator it = begin(); it != end(); ++it) {
                        newmap.insert(std::make_pair(it->first.copy(), it->second.copy()));
                }
                return newmap;
        }

private:
        map_t &operator=(const map_t &other) { abort(); }
        map_t(const map_t &other) { abort(); }
public:

        bool operator==(const map_t &other) const
        {
                if (size() != other.size()) return false;
                for (const_iterator it = begin(); it != end(); ++it) {
                        const_iterator jt = other.find(it.key());
                        if (jt == other.end()) return false;
                        if (it.value() != jt.value()) return false;
                }
                return true;
        }

        bool operator!=(const map_t &other) const { return !operator==(other); }

        /* Iteration: 
         * begin() and end() methods, both const and non-const. 
         * Unordered, so forward iteration only
         */
        iterator begin() { return iterator(table?table->table:0, table?table->capacity:0, 0, true); }
        iterator end() { return iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0, false); }
        const_iterator begin() const { return const_iterator(table?table->table:0, table?table->capacity:0, 0, true); }
        const_iterator end() const { return const_iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0, false); }
        const_iterator cbegin() const { return const_iterator(table?table->table:0, table?table->capacity:0, 0, true); }
        const_iterator cend() const { return const_iterator(table?table->table:0, table?table->capacity:0, table?table->capacity:0, false); }

        size_t size() const { return table?table->count:0; }

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

        data_t &operator[](data_t &&k)
        {
                return maybe_insert(std::pair<data_t&&,data_t&&>(std::move(k), data_t())).first->second;
        }

        data_t &operator[](const data_t &k)
        {
                return maybe_insert(std::pair<const data_t&,const data_t&>(k, data_t())).first->second;
        }
        const data_t &operator[](const data_t &k) const
        {
                const_iterator it = find(k);
                if (it == end()) {
                        throw std::runtime_error("Element not in map");
                } else {
                        return it.value();
                }
        }
        iterator find(const data_t &k);

        const_iterator find(const data_t &k) const;

        std::pair<iterator, bool> insert(const std::pair<data_t&&, data_t&&> &v);

        std::pair<iterator, bool> insert(data_t&& k, data_t&& v) {
                return insert(std::make_pair(std::move(k), std::move(v)));
        }

        std::pair<iterator, bool> insert(const std::pair<data_t&&, data_t&&> &v, hash_t hash);

        size_t erase(const data_t &k);
        void erase(iterator it);
        void clear();

protected:
        void resize(size_t newsize);

        void really_insert(item_t &item, const std::pair<data_t&&, data_t&&> &v, hash_t hash);
        std::pair<iterator, bool> maybe_insert(const std::pair<const data_t&, const data_t&> &v);
        std::pair<iterator, bool> maybe_insert(const std::pair<data_t&&, data_t&&> &v);
        std::pair<map_t::const_iterator, map_t::const_iterator> find_for_insert(const data_t &k, hash_t hash) const;

        bool empty(const item_t &item) const { return 0 == item.hash && SAG_DATA_EMPTY == item.key.tag; }
        bool empty(const const_iterator::element_t &item) const { return 0 == item.hash && SAG_DATA_EMPTY == item.first.tag; }
        bool hole(const item_t &item) const { return 1 == item.hash && SAG_DATA_EMPTY == item.key.tag; }
        bool hole(const const_iterator::element_t &item) const { return 1 == item.hash && SAG_DATA_EMPTY == item.first.tag; }
        bool live(const item_t &item) const { return SAG_DATA_EMPTY != item.key.tag || item.hash > 1; }
        bool live(const const_iterator::element_t &item) const { return SAG_DATA_EMPTY != item.first.tag || item.hash > 1; }

        size_t index(hash_t hash) const
        {
                if (!table) return 0;
                return table->capacity ? hash % table->capacity : 0;
        }

#ifdef _SAG_INTERNAL_UNSUPPORTED_DEBUG
public:
        SAG_CONNECTIVITY_API static size_t clashes;
        SAG_CONNECTIVITY_API static size_t inserts;
        SAG_CONNECTIVITY_API static double resizeUsage;
        SAG_CONNECTIVITY_API static size_t resizes;
        SAG_CONNECTIVITY_API static size_t max_lookup_clash;
        SAG_CONNECTIVITY_API static size_t lookups;
        SAG_CONNECTIVITY_API static size_t lookup_clashes;
        static double getInsertClashRatio() { return (double)clashes/(double)inserts; }
        static double getAverageResizeRatio() { return resizeUsage/(double)resizes; }
        static void resetCounters() { clashes = inserts = resizeUsage = resizes = 0; }
        static double getAverageLookupProbes() { return 1.0+(double)lookup_clashes/(double)lookups; }
        static size_t getMaxLookupProbes() { return 1+max_lookup_clash; }
#endif
};