sorted_forward_list.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 __SORTED_FORWARD_LIST_HH
# define __SORTED_FORWARD_LIST_HH

# include <functional>
# include <atomic>
# include <cassert>
# include "simple_stack.hh"
# include "marked_pointer.hh"

namespace lockfree {
  template <typename Elt,
            typename Eq = std::equal_to<Elt>,
            typename Compare = std::less<Elt>,
            typename Alloc = std::allocator<Elt>,
            typename Multi = typename std::true_type
            >
  class sorted_forward_list {
  private:
    struct node;
    struct node_base {
    private:
      std::atomic<node_base*> next;
    public:
      node_base(node_base* next): next(next) {}
      node_base* get_next() const {
        return next.load();
      }
      bool set_next(node_base* expected, node_base* newnext) {
        return next.compare_exchange_strong(expected, newnext);
      }
      void force_set_next(node_base* newnext) {
        node_base *old;
        do
          old = next.load();
        while (!next.compare_exchange_strong(old, newnext));
      }
      const Elt& operator*() const {
        return static_cast<const node*>(this)->operator*();
      }

      node_base& operator=(node_base&& other) {
        std::swap(next, other.next);
        return *this;
      }
    };
    struct node: public node_base {
    private:
      Elt e;
    public:
      node(Elt&& e, node_base* next): node_base(next), e(std::move(e)) {}
      node& operator=(node&& other) {
        std::swap(e, other.e);
        this->node_base::operator=((node_base&&)std::move(other));
        return *this;
      }
      const Elt& operator*() const {
        return e;
      }
    };

    typedef typename Alloc::template rebind<node>::other node_allocator_t;
    typedef simple_stack<node*,Alloc> sstack_t;

    node_allocator_t    node_alloc;
    Eq                  eq;
    Compare             compare;
    node_base           head;
    sstack_t            free;
    std::atomic<size_t> _size;

  public:

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

    sorted_forward_list(Eq eq = Eq(), Compare compare = Compare(),
                        Alloc alloc = Alloc())
      : node_alloc(alloc), eq(eq), compare(compare), head(NULL), free(alloc),
        _size(0) {}

    struct iterator;

    struct const_iterator: private iterator {
      explicit const_iterator(node_base* n): iterator(n) {}
      const_iterator(const iterator& other): iterator(other) {}
      const_iterator(const const_iterator& other): iterator(other) {}

      node_base* get_node() const {
        return this->iterator::get_node();
      }

      const Elt& operator*() const {
        return this->iterator::operator*();
      }
      const_iterator& operator++() {
        this->iterator::operator++();
        return *this;
      }
      const_iterator& operator++(int) {
        const_iterator tmp(*this);
        this->iterator::operator++();
        return tmp;
      }
      bool operator==(const const_iterator& other) const {
        return this->iterator::operator==(other);
      }
      bool operator!=(const const_iterator& other) const {
        return this->iterator::operator!=(other);
      }
      bool operator==(const iterator& other) const {
        return this->iterator::operator==(other);
      }
      bool operator!=(const iterator& other) const {
        return this->iterator::operator!=(other);
      }
    };

    struct iterator {
    private:
      node_base* n;

    public:
      explicit iterator(node_base* n): n(n) {}
      iterator(const iterator& other): n(other.n) {}

      const Elt& operator*() const {
        return **n;
      }
      iterator& operator++() {
        n = n->get_next();
        return *this;
      }

      iterator& operator++(int) {
        iterator tmp(*this);
        n = n->get_next();
        return tmp;
      }

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

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

      node_base* get_node() const {
        return n;
      }
    };

    const_iterator begin() const {
      return const_iterator(head.get_next());
    }

    const_iterator end() const {
      return const_iterator(NULL);
    }

    iterator begin() {
      return iterator(head.get_next());
    }

    iterator end() {
      return iterator(NULL);
    }

    std::pair<iterator,bool>
    insert_after(Elt&& elt, const const_iterator& hint,
                 bool once = !Multi::value) {
      return insert_after(std::move(elt), hint.get_node(), once);
    }

  private:
    std::pair<iterator,bool>
    insert_after(Elt&& elt, node_base* hint,
                 bool once = !Multi::value) {
      node* n = node_alloc.allocate(1);
      node_alloc.construct(n, std::move(elt), (node_base*)NULL);

      std::pair<node_base*,node_base*> found;
      while (true) {
        found = search(hint, **n);
        if (once)
          if ((found.second==NULL)?false:eq(**found.second, **n)) {
            std::swap(*const_cast<Elt*>(&**n), elt);
            node_alloc.destroy(n);
            node_alloc.deallocate(n, 1);
            return std::pair<iterator,bool>
              (iterator(static_cast<node*>(found.second)),
               false);
          }

        n->force_set_next(found.second);
        if (found.first->set_next(found.second, n)) {
          _size++;
          return std::pair<iterator,bool>(iterator(n), true);
        }
      };
    }

  public:
    std::pair<iterator,bool> insert(Elt&& elt) {
      return insert_after(std::move(elt), &head);
    }

  private:
    std::pair<node_base*, node_base*>
    search(node_base* hint, const Elt& elt, node_base* exact = NULL) {
      typedef std::pair<node_base*, node_base*> rt;

      node_base* before = NULL;
      node_base* before_next = NULL;

      while (true) {
        node_base* t = hint;
        node_base* t_next = t->get_next();

        do {
          if (!details::is_marked(t_next)) {
            before = t;
            before_next = t_next;
          }

          if (NULL == (t = details::unmarked(t_next)))
            break ;
          t_next = t->get_next();
        } while (details::is_marked(t_next)?true:
                 (exact==NULL)?(compare(**t, elt)?true:
                                (!compare(elt, **t)?!eq(**t,elt):false)):
                 (exact==t)?false:!compare(elt, **t));

        if (before_next == t) {
          if ((t == NULL)?false:details::is_marked(t->get_next()))
            continue ;
          else
            return rt(before, t);
        }

        if (before->set_next(before_next, t)) {
          if ((t == NULL)?false:!details::is_marked(t->get_next()))
            continue ;
          else
            return rt(before, t);
        }
      }
    }

    bool erase(node_base* item, node_base* hint) {
      std::pair<node_base*, node_base*> found;
      node_base* next;

      while (true) {
        found = search(hint, **item, item);
        if ((found.second == NULL)?true:(found.second != item)) {
          return false;
        }
        next = found.second->get_next();
        if (!details::is_marked(next))
          if (found.second->set_next(next, details::marked(next))) {
            break ;
          }
      }
      _size--;
      node_alloc.destroy(static_cast<node*>(found.second));
      free.push(static_cast<node*>(found.second));
      if (!found.first->set_next(found.second, next))
        search(hint, **found.second);
      return true;
    }

    bool erase(const Elt& item, node_base* hint) {
      static_assert(!Multi::value, "Cannot erase elements on multilists");
      std::pair<node_base*, node_base*> found;
      node_base* next;

      while (true) {
        found = search(hint, item);
        if ((found.second == NULL)?true:(!eq(**found.second,item))) {
          return ;
        }
        next = found.second->get_next();
        if (!details::is_marked(next))
          if (found.second->set_next(next, details::marked(next))) {
            break ;
          }
      }
      if (found.first->set_next(found.second, next)) {
        --_size;
        node_alloc.destroy(static_cast<node*>(found.second));
        free.push(static_cast<node*>(found.second));
        return true;
      }
      else {
        search(hint, **found.second);
      }
    }


  public:
    bool erase(const Elt& elt) {
      static_assert(!Multi::value, "Cannot erase elements on multilists");
      return erase(elt, &head);
    }

    bool erase(const Elt& elt, const const_iterator& hint) {
      static_assert(!Multi::value, "Cannot erase elements on multilists");
      return erase(elt, hint.get_node());
    }

    bool erase(const const_iterator& it, const const_iterator& hint) {
      return erase(it.get_node(), hint.get_node());
    }

    bool erase(const iterator& it) {
      return erase(it.get_node(), &head);
    }

  private:
    const_iterator find(const Elt& elt, node_base*hint) const {
      return const_cast<sorted_forward_list*>(this)->find(elt, hint);
    }

    iterator find(const Elt& elt, node_base*hint) {
      std::pair<node_base*, node_base*> found = search(hint, elt);
      if (found.second == NULL)
        return iterator(NULL);
      if (eq(**found.second, elt))
        return iterator(static_cast<node*>(found.second));
      return iterator(NULL);
    }

  public:
    const_iterator find(const Elt& elt) const {
      return find(elt, &head);
    }
    const_iterator find(const Elt& elt, const const_iterator& hint) const {
      return find(elt, hint.get_node());
    }

    iterator find(const Elt& elt) {
      return find(elt, &head);
    }
    iterator find(const Elt& elt, const const_iterator& hint) {
      return find(elt, hint.get_node());
    }

    bool collect() {
      bool did = false;
      while (true) {
        typename sstack_t::wrapped w = free.pop();
        if (w.end())
          break ;
        did = true;
        node* n = *w;
        //node_alloc.destroy(n);
        node_alloc.deallocate(n, 1);
      }
      return did;
    }

    void clear() {
      node* last = NULL;
      for (node_base* n = head.get_next();
           ; n = n->get_next()) {
        if (last != NULL) {
          node_alloc.destroy(last);
          node_alloc.deallocate(last, 1);
        }
        if (n == NULL) {
          head.force_set_next(NULL);
          break ;
        }
        last = static_cast<node*>(n);
      }
      collect();
    }

    ~sorted_forward_list() {
      clear();
    }
  };

}

#endif