simple_stack.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 __SIMPLE_STACK_HH
# define __SIMPLE_STACK_HH

# include <memory>

namespace lockfree {

  template <typename Elt,
            typename Alloc = std::allocator<Elt>
            >
  class simple_stack {
  private:
    struct node {
      Elt e;
      node* next;
      node(Elt&& e, node* next): e(std::move(e)), next(next) {}
    };
    typedef typename Alloc::template rebind<node>::other node_allocator_t;

    node_allocator_t alloc;
    std::atomic<node*> head;
  public:
    simple_stack(Alloc alloc = Alloc()): alloc(alloc), head(NULL) {}

    struct wrapped {
    private:
      node_allocator_t& alloc;
      node* n;
    public:
      wrapped(node_allocator_t& alloc, node *n): alloc(alloc), n(n) {}
      bool end() const {
        return (n == NULL);
      }
      Elt operator*() const {
        return n->e;
      }
      ~wrapped() {
        if (n != NULL) {
          alloc.destroy(n);
          alloc.deallocate(n, 1);
        }
      }
    };

    void push(const Elt& e) {
      push(Elt(e));
    }

    void push(Elt&& e) {
      node* n = alloc.allocate(1);
      alloc.construct(n, std::move(e), (node*)NULL);
      node *h;
      do {
        h = head.load();
        n->next = h;
      } while (!head.compare_exchange_strong(h, n));
    }

    wrapped pop() {
      node* n;
      do {
        n = head.load();
        if (n == NULL)
          return wrapped(alloc, NULL);
      } while (!head.compare_exchange_strong(n, n->next));
      return wrapped(alloc, n);
    }
  };

}

#endif