unordered_set.hh

// This file is a part of Aurelia.
// Copyright (C) 2010  Valentin David
// Copyright (C) 2010  University of Bergen
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#ifndef __UNORDERED_SET_HH
# define __UNORDERED_SET_HH

# include "sorted_forward_list.hh"
# include "vector.hh"
# include "../fast/reset_msb.hh"
# include "../fast/invert_bits.hh"

namespace lockfree {
  template <typename T,
            typename Hash = std::hash<T>,
            typename Eq = std::equal_to<T>,
            typename Alloc = std::allocator<T>,
            typename Multi = std::false_type>
  class unordered_set {
    struct elts {
    private:
      size_t _invhash;
      typename std::aligned_storage<sizeof(T),
                                    std::alignment_of<T>::value>::type _elt;

      T& elt() {
        return *reinterpret_cast<T*>(&_elt);
      }
      const T& elt() const {
        return *reinterpret_cast<const T*>(&_elt);
      }

    public:
      size_t invhash() const {
        return _invhash;
      }

      const T& operator*() const {
        return elt();
      }
      elts(size_t _invhash, T&& elt): _invhash(_invhash) {
        assert(_invhash & 0x1);
        new (reinterpret_cast<T*>(&_elt)) T(std::move(elt));
      }
      elts(size_t _invhash): _invhash(_invhash) {
        assert(!(_invhash & 0x1));
      }

      elts() = delete;
      elts(const elts&) = delete;
      elts(elts&& other): _invhash(other._invhash) {
        if (other._invhash & 0x1) {
          new (reinterpret_cast<T*>(&_elt)) T(std::move(other.elt()));
        }
      }

      elts& operator=(const elts&) = delete;
      elts& operator=(elts&& other) {
        if (_invhash & 0x1) {
          if (other._invhash & 0x1)
            std::swap(*reinterpret_cast<T*>(&_elt), *reinterpret_cast<T*>(&other._elt));
          else
            new (reinterpret_cast<T*>(&other._elt)) T(std::move(elt()));
        }
        else {
          if (!(other._invhash & 0x1))
            new (reinterpret_cast<T*>(&_elt)) T(std::move(other.elt()));
        }
        std::swap(_invhash, other._invhash);
        return *this;
      }

      ~elts() {
        if (_invhash & 0x1)
          elt().~T();
      }
    };

    struct compare_elts {
      bool operator()(const elts& a, const elts& b) const {
        return a.invhash() < b.invhash();
      }
    };

    struct eq_elts {
      Eq eq;
      eq_elts(Eq eq): eq(eq) {}

      bool operator()(const elts& a, const elts& b) const {
        if (a.invhash() != b.invhash())
          return false;
        if (!(a.invhash()&0x1))
          return false;
        return eq(*a, *b);
      }
    };

    typedef typename Alloc::template rebind<elts>::other elt_alloc_t;
    typedef sorted_forward_list<elts,
                                eq_elts, compare_elts,
                                elt_alloc_t, Multi> list_t;

    typedef typename Alloc::template rebind<typename list_t::const_iterator>
    ::other it_alloc_t;

    typedef vector<typename list_t::const_iterator,
                   1024u, it_alloc_t> entries_t;

    double max_load_factor;
    Eq eq;
    Hash hash;

    list_t list;
    entries_t entries;

    std::atomic<size_t> _size;

  public:
    unordered_set(Hash hash = Hash(), Eq eq = Eq(), Alloc alloc = Alloc()):
      max_load_factor(.3),
      eq(eq), hash(hash), list(eq_elts(eq), compare_elts(),
                               alloc), entries(list.end(), alloc) {
      entries.resize(1);
      entries[0x0] = list.insert(elts(0x0)).first;
      _size.store(0);
    }

  private:
    typename list_t::const_iterator _get_bucket(size_t b) const {
      typename list_t::const_iterator i = entries[b];
      if (i == list.end()) {
        typename list_t::const_iterator parent =
          _get_bucket(fast::reset_msb(b));
        i = const_cast<unordered_set*>(this)->list
          .insert_after(elts(get_invert(b)&~0x1), parent, true).first;
        const_cast<unordered_set*>(this)->entries[b] = i;
      }
      return i;
    }

    size_t get_invert(size_t h) const {
      fast::invert_bits(h);
      return h | 0x1;
    }

    typename list_t::const_iterator get_bucket(size_t h) const {
      return _get_bucket(h%entries.size());
    }

  public:
    ~unordered_set() {
      clear();
      while (collect()) ;
    }

    struct iterator {
    private:
      typename list_t::const_iterator i;

    public:
      iterator(const typename list_t::const_iterator& i): i(i) {
        while ((this->i.get_node() == NULL)?false
               :(!((*(this->i)).invhash()&0x1)))
          ++(this->i);
      }
      iterator(const iterator&) = default;
      iterator() = delete;

      const T& operator*() const {
        return **i;
      }

      operator const typename list_t::const_iterator&() const {
        return i;
      }

      iterator& operator++() {
        do
          ++i;
        while ((this->i.get_node() == NULL)?false
               :(!((*(this->i)).invhash()&0x1)));
        return *this;
      }

      iterator operator++(int) {
        iterator tmp(*this);
        ++(*this);
        return tmp;
      }

      bool operator==(const iterator& other) const {
        return i == other.i;
      }
      bool operator!=(const iterator& other) const {
        return i != other.i;
      }
    };

    iterator end() const {
      return list.end();
    }

    iterator begin() const {
      return list.begin();
    }

    void clear() {
      for (iterator i = begin(); i != end();) {
        iterator tmp = i++;
        erase(tmp);
      }
    }

    iterator find(const T& elt) const {
      size_t h = hash(elt);
      typename list_t::const_iterator i = get_bucket(h);
      size_t inv = get_invert(h);
      size_t f = 0;
      for (;
           i != list.end(); ++i) {
        if (inv < (*i).invhash())
          return end();
        if (inv == (*i).invhash())
          if (eq(**i, elt))
            return iterator(i);
        ++f;
      }
      return end();
    }

    std::pair<iterator,bool> insert(T&& elt) {
      size_t h = hash(elt);
      typename list_t::const_iterator i = get_bucket(h);
      elts toinsert(get_invert(h), std::move(elt));
      std::pair<typename list_t::const_iterator,bool> ret =
        list.insert_after(std::move(toinsert), i);
      if (ret.second) {
        size_t nelts = ++_size;
        size_t size = entries.size();
        if ((((double)nelts) / size) > max_load_factor) {
          entries.resize(2*size);
        }
      }
      else {
        std::swap(*const_cast<T*>(&*toinsert), elt);
      }
      return std::pair<iterator,bool>(iterator(ret.first),ret.second);
    }

    size_t size() const {
      return _size.load();
    }

    bool collect() {
      entries.collect();
      return list.collect();
    }

    void erase(const T& t) {
      static_assert(!Multi::value, "Cannot erase elements on multiset");
      erase(find(t));
    }

    void erase(const iterator& i) {
      if (i == end())
        return ;
      typename list_t::const_iterator j = i;
      size_t h = (*j).invhash();
      fast::invert_bits(h);
      typename list_t::const_iterator b = get_bucket(h);
      if (list.erase(j, b))
        --_size;
    }
  };
}

#endif