include/amino/stack.h

Go to the documentation of this file.

/*
 * (c) Copyright 2008, IBM Corporation.
 * Licensed under the Apache License, Version 2.0 (the "License");
 you may not use this file except in compliance with the License.
 You may obtain a copy of the License at

 http://www.apache.org/licenses/LICENSE-2.0

 Unless required by applicable law or agreed to in writing, software
 distributed under the License is distributed on an "AS IS" BASIS,
 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 See the License for the specific language governing permissions and
 limitations under the License.
 */

#ifndef AMINO_STACK_H
#define AMINO_STACK_H

#include <amino/smr.h>
#include <stdexcept>

namespace amino {

using namespace internal;
/*
 * T must be a pointer or built-in type right now. 20070904 Mo Jiong Qiu
 * I will extend it according to STL potential rules, but for now ignore this extention
 *
 * backoff mechanism should be added to prevent high contention
 */
template<typename T> class LockFreeStack {
public:
        class StackNode {
        public:
                /*the data*/
                T data;
                /*pointer to the next node*/
                StackNode* next;

                StackNode() {
                        next = NULL;
                }

                StackNode(const T& val) :
                        data(val), next(NULL) {
                }
        };

private:
#ifdef DEBUG_STACK
        atomic_int retries;
        atomic_int t_newNodes;
#endif

        atomic<StackNode *> top;
        SMR<StackNode, 1>* mm; //for memory management

        /* prevent the use of copy constructor and copy assignment*/
        LockFreeStack(const LockFreeStack& s) {
        }

        LockFreeStack& operator=(const LockFreeStack& st) {
        }

public:
        LockFreeStack() {
                mm = getSMR<StackNode, 1> (); //for memory management, here 1 hazard pointer is OK
                top.store(NULL, memory_order_relaxed);

#ifdef DEBUG_STACK
                retries = 0;
#endif
        }

        ~LockFreeStack() {
                StackNode *first = top.load(memory_order_relaxed);
                while (first != NULL) {
                        StackNode *next = first->next;
                        delete first;
                        first = next;
                }
        }

        bool pop(T& ret) {
                StackNode *oldTop, *newTop;
        typename SMR<StackNode, 1>::HP_Rec * hp = mm->getHPRec();

                while (true) {
                        oldTop = top.load(memory_order_relaxed);//no need to imply membar
                        if (oldTop == NULL)
                                return false;

                        mm->employ(hp, 0, oldTop); //for memory management, hp0 = oldTop

                        //memory barrier necessary here
                        if (top.load(memory_order_relaxed) != oldTop)
                                continue;
                        newTop = oldTop->next;
                        if (top.compare_swap(oldTop, newTop))
                                break; //yes, successful
#ifdef DEBUG_STACK
                        retries++;
#endif
                }
                mm->retire(hp, 0);//hp0 = NULL. optional. for memory management

                ret = oldTop->data;
                mm->delNode(hp, oldTop); //for memory management
                return true;
        }

        void push(const T d) {
                StackNode*oldTop, *newTop;

#ifdef DEBUG_STACK
                struct timeval start, end;
                gettimeofday(&start, NULL);
#endif

#ifdef FREELIST
        newTop = mm->newNode();
#else
                newTop = new StackNode();
#endif

#ifdef DEBUG_STACK
                gettimeofday(&end, NULL);
                t_newNodes += 1000000*(end.tv_sec-start.tv_sec) + (end.tv_usec-start.tv_usec);
#endif

                newTop->data = d;

                /* do we check whether newTop is NULL here? */
                do {
                        oldTop = top.load(memory_order_relaxed); //no need to use a barrier
                        newTop->next = oldTop;
                } while (top.compare_swap(oldTop, newTop) == false);
        }

        bool empty() /*const*/{
                return top.load(memory_order_relaxed) == NULL;
        }

        int size() {
                int ret = 0;
                StackNode *node = top.load(memory_order_relaxed);
                while (node != NULL) {
                        ++ret;
                        node = node -> next;
                }
                return ret;
        }

        bool peekTop(T& ret) {
                StackNode *node = top.load(memory_order_relaxed);
                if (node == NULL)
                        return false;
                ret = node->data;
                return true;
        }
#ifdef DEBUG_STACK
        int getCASRetries() {
                return retries.load(memory_order_relaxed);
        }
        int getTimeNewNodes() {
                return t_newNodes.load(memory_order_relaxed);
        }
#endif

};

}
#endif

---