include/amino/ebstack.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 EBSTACK_H_
#define EBSTACK_H_

#include "smr.h"

namespace amino {
template<typename T> class StackNode {
public:
        T data;
        StackNode* next;
        StackNode() :
                next(NULL) {
        }

        StackNode(const T& val) :
                data(val), next(NULL) {
        }
};
template<typename T> class EBStack {
private:
        atomic<StackNode<T>*> top; /*top pointer of stack*/
        SMR<StackNode<T> , 1>* mm; /*SMR for memory management*/

        /*collision array*/
        static const int TRY_TIMES = 4; /*times of try on collision array*/

        //TODO TOMB_STONE and REMOVED should be static
        StackNode<T> TOMB_STONE;
        StackNode<T> REMOVED;
        StackNode<T> EMPTY;

        const int coll_size; /*size of collision array*/
        atomic<StackNode<T>*>* coll_pop; /*collision array for pop*/
        atomic<StackNode<T>*>* coll_push; /*collision array for push*/
        atomic<int> position; /*position for try on collision array*/

        /*try to add element on collision array for pop*/
        bool try_add(StackNode<T>*);
        /*try to remove element on collision array for push*/
        StackNode<T>* try_remove();
        int get_rand_position();
        void initCollisionArray(int);
        void destoryCollisionArray();

public:
        EBStack(int num = 8) :
                TOMB_STONE(), REMOVED(), EMPTY(), coll_size(num), position() {
                top = NULL;
                mm = getSMR<StackNode<T> , 1> ();
                initCollisionArray(num);
        }

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

        void push(const T d);
        bool pop(T& ret);
        bool empty();
        int size();
        bool peekTop(T& ret);

};

template<typename T> void EBStack<T>::initCollisionArray(int num) {
        coll_push = new atomic<StackNode<T>*> [num];
        coll_pop = new atomic<StackNode<T>*> [num];
        for (int i = 0; i < num; ++i) {
                coll_push[i].store(NULL);
                coll_pop[i].store(NULL);
        }
}

template<typename T> void EBStack<T>::destoryCollisionArray() {
        /*all elements in coll_push and coll_pop is unavailable now.
         * no need to delete node put into coll_push and coll_pop first.
         */
        delete[] coll_push;
        delete[] coll_pop;
}
template<typename T> int EBStack<T>::get_rand_position() {
        return position++ % coll_size;
}

template<typename T> void EBStack<T>::push(T d) {
        StackNode<T>* newTop = new StackNode<T> (d);

        StackNode<T>* oldTop;
        while (true) {
                /*no need to use a barrier*/
                oldTop = top.load(memory_order_relaxed);
                newTop->next = oldTop;

                if (true == top.compare_swap(oldTop, newTop)) {
                        break;
                }

                /*collision*/
                if (true == try_add(newTop)) {
                        break;
                }
        }
}

template<typename T> bool EBStack<T>::try_add(StackNode<T>* node) {
        int pos = get_rand_position();

        for (int i = 0; i < TRY_TIMES; ++i) {
                int index = (pos + i) % coll_size;

                StackNode<T>* pop_op = coll_pop[index].load(memory_order_relaxed);
                /*if some thread is waiting for removal, let's feed it with
                 * added object and return success.
                 */
                if (pop_op == &TOMB_STONE) {
                        if (coll_pop[index].compare_swap(pop_op, node)) {
                                return true;
                        }
                }
        }

        /*
         * let's try to put adding objects to the buffer and
         * waiting for removal threads.
         */
        for (int i = 0; i < TRY_TIMES; ++i) {
                int index = (pos + i) % coll_size;
                StackNode<T>* push_op = coll_push[index].load(memory_order_relaxed);
                if (push_op == NULL) { /*this posiotion is empty*/
                        if (coll_push[index].compare_swap(push_op, node)) {
                                /* Now we check to see if added object is touched by removing threads.*/
                                while (true) {
                                        push_op = coll_push[index].load(memory_order_relaxed);
                                        if (push_op == node) {
                                                if (coll_push[index].compare_swap(node, NULL)) {
                                                        /*no removing thread touched us, return false*/
                                                        return false;
                                                }
                                        } else {
                                                /*current value should be REMOVED. change REMOVED to be
                                                 * null means this position is available again.
                                                 */
                                                coll_push[index] = NULL;
                                                return true;
                                        }
                                }
                        }
                }
        }
        return false;
}

template<typename T> bool EBStack<T>::pop(T& ret) {
        StackNode<T> *oldTop, *newTop = NULL;

        while (true) {
                oldTop = top.load(memory_order_relaxed);
                if (oldTop == NULL) {
                        return false;
                }

                mm->employ(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; //successful
                }

                // elimination backoff
                StackNode<T>* col_ele = try_remove();
                if (NULL != col_ele) {
                        ret = col_ele->data;
                        return true;
                }
        }
        mm->retire(0);//hp0 = NULL. optional. for memory management

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

template<typename T> StackNode<T>* EBStack<T>::try_remove() {
        int pos = get_rand_position();
        for (int i = 0; i < TRY_TIMES; ++i) {
                int index = (pos + i) % coll_size;
                StackNode<T>* push_op = coll_push[index].load(memory_order_relaxed);
                // collide with pop
                if (push_op == &EMPTY || push_op == &REMOVED) {
                        StackNode<T>* pop_op = coll_pop[index].load(memory_order_relaxed);
                        if (pop_op == NULL) {
                                if (coll_pop[index].compare_swap(pop_op, &TOMB_STONE)) {
                                        //TODO thread sleep
                                        while (true) {
                                                pop_op = coll_pop[index].load(memory_order_relaxed);
                                                if (pop_op != &TOMB_STONE) {
                                                        coll_pop[index] = NULL;
                                                        return pop_op;
                                                } else {
                                                        if (coll_pop[index].compare_swap(pop_op, &EMPTY)) {
                                                                return NULL;
                                                        }
                                                }
                                        }
                                }
                        }
                } else {
                        if (coll_push[index].compare_swap(push_op, &REMOVED)) {
                                return push_op;
                        }
                }

        }

        //TODO thread sleep
        return NULL;
}

template<typename T> bool EBStack<T>::empty() /*const*/{
        return top.load(memory_order_relaxed) == NULL;
}

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

template<typename T> bool EBStack<T>::peekTop(T& ret) {
        StackNode<T>* node = top.load(memory_order_relaxed);
        if (node == NULL)
                return false;
        ret = node->data;
        return true;
}

}
#endif /*EBSTACK_H_*/

---