include/amino/ordered_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_ORDERDED_LIST_H
#define AMINO_ORDERDED_LIST_H
#include "smr.h"
#include "list.h"

namespace amino {

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

private:
        template<typename T> friend class Set;
        atomic<NodeType<KeyType>*> head;
        NodeType<KeyType>* dummy;
        /*for memory management*/
        SMR<NodeType<KeyType> , NHPOINTER>* mm;

        /* prevent the use of copy constructor and copy assignment*/
        OrderedList(const OrderedList& s) {
        }
        OrderedList& operator=(const OrderedList& st) {
        }

public:
        OrderedList() {
                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);
        }

        /*
         * @brief Destructor, supposed to be called when its associated data structure is to be deleted
         */
        ~OrderedList() {
                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>* node = head.load();
                if (node != NULL) {
                        ret = node->data;
                        return true;
                } else
                        return false;
        }

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

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

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

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

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

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

                while (true) {
                        if (!find(e, start, holder)) {/* return false if the element is not found in the list*/
                                result = false;
                                break;
                        }
                        if (!POINTER(holder.cur)->next.compare_swap(holder.next, MARK(
                                        holder.next))) {
                                continue;
                        }
                        if (holder.prev->compare_swap(holder.cur, POINTER(holder.next))) {
                                mm->delNode(POINTER(holder.cur));
                        } else {
                                find(e, start, holder);
                        }
                        result = true;
                        break;
                }
                retireAll();
                return result;
        }

        bool search(const KeyType& e) {
                FindStateHolder<KeyType> holder = FindStateHolder<KeyType> ();
                bool result = find(e, &head, holder);
                retireAll();
                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;
        }

private:
        void retireAll() {
                mm->retire(0);
                mm->retire(1);
                mm->retire(2);
        }

        bool add(const KeyType& e, atomic<NodeType<KeyType>*>* start) {
                NodeType<KeyType>* node = new NodeType<KeyType> ();
                node->data = e;
                FindStateHolder<KeyType> holder = FindStateHolder<KeyType> ();
                bool result;

                while (true) {
                        if (find(e, start, holder)) {/* if the element is existed in the list. do nothing and return false*/
                                delete node;
                                result = false;
                                break;
                        }
                        node->next.store(POINTER(holder.cur), memory_order_relaxed);/* set the next pointer of new node to holder.cur */

                        if (holder.prev->compare_swap(holder.cur, POINTER(node))) {
                                result = true;
                                break;
                        }
                }

                retireAll();
                return result;
        }

        NodeType<KeyType>* add_returnAddress(const KeyType& e, atomic<NodeType<
                        KeyType>*>* start) {
                NodeType<KeyType>* node = new NodeType<KeyType> ();
                node->data = e;
                FindStateHolder<KeyType> holder = FindStateHolder<KeyType> ();
                NodeType<KeyType>* result;

                while (true) {
                        if (find(e, start, holder)) {/* if the element is existed in the list. do nothing and return false*/
                                delete node;
                                result = holder.cur;
                                break;
                        }
                        node->next.store(POINTER(holder.cur), memory_order_relaxed);/* set the next pointer of new node to holder.cur */
                        //FIXME need POINTER(holder.prev) and POINTER(holder.cur) here?

                        if (holder.prev->compare_swap(holder.cur, POINTER(node))) {
                                result = node;
                                assert(result != NULL);
                                break;
                        }
                }

                retireAll();
                return result;
        }

        bool find(const KeyType& key, atomic<NodeType<KeyType>*>* start,
                        FindStateHolder<KeyType>& holder) {
                try_again:
                NodeType<KeyType>* next = NULL;
                atomic<NodeType<KeyType>*>* prev = start;

                NodeType<KeyType>* cur = POINTER(prev->load(memory_order_relaxed));

                mm->employ(1, cur);

                if (prev->load(memory_order_relaxed) != cur)
                        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(0, next);

                        if (cur->next.load(memory_order_relaxed) != markedNext)
                                goto try_again;

                        KeyType cKey = cur->data;

                        if (prev->load(memory_order_relaxed) != cur)
                                goto try_again;

                        if (!cmark) {
                                if (cKey >= key) {/* find the lowest key in the list that is greater than or equal the input key*/
                                        /*set value of state holder*/
                                        holder.isFound = (cKey == key);
                                        holder.prev = prev;
                                        holder.cur = cur;
                                        holder.next = next;
                                        return holder.isFound;
                                }
                                prev = &(cur->next);
                                mm->employ(2, cur);
                        } else {
                                if (prev->compare_swap(cur, next)) {
                                        mm->delNode(cur);
                                } else {
                                        goto try_again;
                                }
                        }

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

};

}

#endif /*AMINO_ORDERDED_LIST_H*/

---