lock_free/stack.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation 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, version 3 of the License.
#
# The Fuzion language implementation 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 The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion feature stack
#
# -----------------------------------------------------------------------

# lock-free stack using compare_and_set
# invented by R. Kent Treiber
#
public stack(T type) : container.Stack T is

  Node(data T, next option Node) ref is

  top := concur.atomic (option Node) nil


  # push an element to the stack
  #
  public redef push (e T) unit =>
    _ :=
      for o := top.read
          n := Node e o
      while !top.compare_and_set o n


  # pop an element from the stack
  #
  public redef pop option T =>

    next (x option Node) =>
      x.bind Node n->n.next

    for o := top.read
        n := next o
    while !o.is_nil && !top.compare_and_set o n
    else
      o.bind T node->node.data


  # peek at the top element from the stack
  #
  public redef peek option T =>
    top.read.bind T node->node.data