include/amino/list.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_LIST_H
#define AMINO_LIST_H
#include <iostream>
#include <stdexcept>
#include <iterator>
#include "smr.h"

namespace amino {

/*internal namespace for SMR*/
using namespace internal;
/*
 * Number of pointers protected by SMR.
 */
#define NHPOINTER 3
/* clear the last two bits of pointers */
#define POINTER(p) ((NodeType<KeyType>*)(((long)(p))&(~3)))
/* set the last bit of pointers */
#define MARK(p) ((NodeType<KeyType>*)(((long)(p))|(1)))
/* get the last bit of pointers */
#define MARKED(p) (((long)(p))&(1))

template<typename KeyType> class NodeType {
public:
        /*the data*/
        KeyType data;

        /*pointer to the next node*/
        atomic<NodeType<KeyType>*> next;

        NodeType() {
                next.store(NULL, memory_order_relaxed);
        }

        NodeType(const KeyType& val) :
                data(val) {
                next.store(NULL);
        }
};

template<typename KeyType> class FindStateHolder {
public:
        atomic<NodeType<KeyType>*>* prev;
        NodeType<KeyType>* cur;
        NodeType<KeyType>* next;
        bool isFound;

        FindStateHolder() :
                prev(NULL), cur(NULL), next(NULL), isFound(false) {
        }
};

template<typename T> struct __list_iterator {
        typedef __list_iterator<T> _Self;
        typedef NodeType<T> _Node;

        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef T* pointer;
        typedef T& reference;

        NodeType<T>* node;

        __list_iterator(_Node* x) :
                node(x) {
        }

        __list_iterator(const _Self& x) :
                node(x.node) {
        }

        __list_iterator() {
        }

        _Self& operator ++() {
                node = node->next.load(memory_order_relaxed);
                return *this;
        }

        _Self operator ++(int) {
                _Self tmp = *this;
                ++*this;
                return tmp;
        }

        bool operator ==(const _Self & x) const {
                return node == x.node;
        }
        bool operator !=(const _Self & x) const {
                return node != x.node;
        }

        reference operator *() const {
                return node->data;
        }

        pointer operator ->() const {
                return &(node->data);
        }

};

template<typename T> struct __list_const_iterator {
        typedef __list_const_iterator<T> _Self;
        typedef const NodeType<T> _Node;
        typedef __list_iterator<T>                iterator;

        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef const T* pointer;
        typedef const T& reference;

        const NodeType<T>* node;

        __list_const_iterator(const _Node* x) :
                node(x) {
        }

        __list_const_iterator(const _Self& x) :
                node(x.node) {
        }

        __list_const_iterator(const iterator& x)
    : node(x.node) { }

        __list_const_iterator() {
        }

        _Self& operator ++() {
                node = node->next.load(memory_order_relaxed);
                return *this;
        }

        _Self operator ++(int) {
                _Self tmp = *this;
                ++*this;
                return tmp;
        }

        bool operator ==(const _Self & x) const {
                return node == x.node;
        }
        bool operator !=(const _Self & x) const {
                return node != x.node;
        }

        reference operator *() const {
                return node->data;
        }

        pointer operator ->() const {
                return &(node->data);
        }

};

template<typename T>
inline bool operator==(const __list_iterator<T>& lhs,
                const __list_const_iterator<T>& rhs) {
        return lhs.node == rhs.node;
}

template<typename T>
inline bool operator!=(const __list_iterator<T>& lhs,
                const __list_const_iterator<T>& rhs) {
        return lhs.node != rhs.node;
}

template<typename KeyType>
class List {
public:
        typedef __list_iterator<KeyType> iterator;
        typedef __list_const_iterator<KeyType> const_iterator;

protected:
        atomic<NodeType<KeyType>*> head;
        NodeType<KeyType>* dummy;

        SMR<NodeType<KeyType>, NHPOINTER>* mm;
    typedef typename SMR<NodeType<KeyType>, NHPOINTER>::HP_Rec HazardP;

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

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

public:
        List() {
                mm = getSMR<NodeType<KeyType> , NHPOINTER> (); //for memory management, 1 hazard pointer is OK
                dummy = new NodeType<KeyType> ();
                head.store(dummy->next.load(memory_order_relaxed), memory_order_relaxed);
        }

        ~List() {
                NodeType<KeyType>* tmp = head.load();
                while (tmp != NULL) {/* if the list is not empty. delete the node of it until it is empty*/
                        NodeType<KeyType>*tmp_keep = tmp;
                        tmp = tmp_keep->next.load(memory_order_relaxed);
                        delete tmp_keep;
                }

                delete dummy;
        }

        bool front(KeyType& ret) {
                NodeType<KeyType>* first = head.load(memory_order_relaxed);
                if (first == NULL)
                        return false;
                ret = first->data;
                return true;
        }

        bool insert(int index, const KeyType& e) {
                return add(e);
        }

        iterator begin() {
                return iterator(head.load(memory_order_relaxed));
        }

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

        const_iterator begin() const {
                return const_iterator(head.load(memory_order_relaxed));
        }

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

        int size() {
                int ret = 0;
                NodeType<KeyType>* curr = head.load(memory_order_relaxed);
                while (curr != NULL) {
                        ++ret;
                        curr = curr->next.load(memory_order_relaxed);
                }
                return ret;
        }

        bool push_front(const KeyType& e) {
                return add(e);
        }

        bool empty() {
                return head.load(memory_order_relaxed) == NULL;
        }

        bool remove(const KeyType& e) {
                return remove(e, &head);
        }

        bool search(const KeyType& e) {
                return search(e, &head);
        }

private:
        bool add(const KeyType& e) {
                NodeType<KeyType>* node = new NodeType<KeyType> (e);
                bool result;

                while (true) {
                        /*add to the head of list*/
                        /*get the head pointer of the list*/
                        NodeType<KeyType>* cur = POINTER(head.load(memory_order_relaxed));

                        node->next.store(cur, memory_order_relaxed);

                        if (head.compare_swap(cur, node)) {
                                result = true;
                                break;
                        }
                }
                return result;
        }

        bool search(const KeyType& e, atomic<NodeType<KeyType>*>* start) {
                FindStateHolder<KeyType> holder = FindStateHolder<KeyType> ();
                bool result = find(e, start, holder);
                retireAll();
                return result;
        }

        bool remove(const KeyType& e, atomic<NodeType<KeyType>*>* start) {
                FindStateHolder<KeyType> holder = FindStateHolder<KeyType> ();
                bool result;
        HazardP * hp = mm->getHPRec();

                while (true) {
                        if (!find(e, start, holder)) {/* return false if the element is not found in the list*/
                                result = false;
                                break;
                        }
                        atomic<NodeType<KeyType>*>* prev = holder.prev;
                        NodeType<KeyType>* cur = holder.cur;
                        NodeType<KeyType>* next = holder.next;

                        /*
                         * CAS operation, mark cur as deleted.
                         * if successful, the thread attempts to remove it at next step.
                         * else, it implies that one or more of three events must have taken place since the snapshot
                         * in Find method was taken. Then goto the start of this while loop
                         */
                        if (!cur->next.compare_swap(next, MARK(next))) {
                                continue;
                        }

                        /*
                         *CAS operation, set the next pointer of prew to the next pointer of cur.
                         *If successful, delete cur by delNode of SMR.
                         *If failed, ,it implies that another thread must have removed the node from the list after the success of the MARK CAS before.
                         *and a new Find is invoked in order to guarantee that the number of deleted nodes not yet removed never exceeds the maximum
                         *number of concurrent threads operating on the object
                         */
                        if (prev->compare_swap(cur, next)) {
                                mm->delNode(hp, cur);
                        } else {
                                find(e, &head, holder);
                        }
                        result = true;
                        break;
                }
                retireAll();
                return result;
        }

        void retireAll() {
        HazardP * hp = mm->getHPRec();
                mm->retire(hp, 0);
                mm->retire(hp, 1);
                mm->retire(hp, 2);
        }

        bool find(const KeyType& key, atomic<NodeType<KeyType>*>* start,
                        FindStateHolder<KeyType>& holder) {
        HazardP * hp = mm->getHPRec();

                try_again:

                NodeType<KeyType>* next = NULL;
                atomic<NodeType<KeyType>*>* prev = start;

                NodeType<KeyType>* cur = POINTER(prev->load());//memory_order_relaxed
                mm->employ(hp, 1, cur);

                if (prev->load(memory_order_relaxed) != cur)/* if the holder.pre changed, start over from the beginning */
                        goto try_again;

                while (true) {
                        if (NULL == cur) {
                                /*set value of state holder*/
                                holder.isFound = false;
                                holder.prev = prev;
                                holder.cur = cur;
                                holder.next = next;
                                return false;
                        }

                        NodeType<KeyType>* markedNext =
                                        cur->next.load(memory_order_relaxed);
                        bool cmark = MARKED(markedNext);
                        next = POINTER(markedNext);

                        mm->employ(hp, 0, next);

                        if (cur->next.load() != markedNext) /*memory_order_relaxed.If the next node changed, start over from the beginning*/
                                goto try_again;

                        KeyType cKey = cur->data;

                        if (prev->load() != cur) /*memory_order_relaxed.If the holder.pre changed, start over from the beginning*/
                                goto try_again;

                        if (!cmark) {
                                if (cKey == key) {
                                        /*set value of state holder*/
                                        holder.isFound = true;
                                        holder.prev = prev;
                                        holder.cur = cur;
                                        holder.next = next;
                                        return true;
                                }
                                prev = &(cur->next);
                                mm->employ(hp, 2, cur);
                        } else {/* if the thread encounters a node marked to be deleted, it attempts to remove it from the list*/
                                if (prev->compare_swap(cur, next)) {
                                        mm->delNode(hp, cur);
                                } else {
                                        goto try_again;
                                }
                        }

                        cur = next;
                        mm->employ(hp, 1, next);
                }
        }

};

}
#endif /*AMINO_LIST_H*/

---