include/amino/lockfree_dictionary.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.
 *
 */
/*
 * lockfree_dictionary.h
 *
 *  Created on: Sep 9, 2008
 *      Author: daixj
 */

#ifndef LOCKFREE_DICTIONARY_H_
#define LOCKFREE_DICTIONARY_H_

#include <amino/smr.h>

namespace amino {

using namespace internal;

#define COPY_NODE(node) (node)
#define READ_NODE(node) (IS_MARKED(node) ? NULL : (node))
#define RELEASE_NODE(node) (node)
#define GET_UNMARKED(p) ((DictNode<K,V>*)(((long)(p))&(~3)))
#define GET_UNMARKED_VALUE(p) ((Value<V>*)(((long)(p))&(~3)))
/* set the last bit of pointers */
#define GET_MARKED(p) ((DictNode<K,V>*)(((long)(p))|(1)))
/* set the last bit of pointers */
#define GET_MARKED_VALUE(p) ((Value<V>*)(((long)(p))|(1)))
/* get the last bit of pointers */
#define IS_MARKED(p) (((long)(p))&(1))

#define MAXLEVEL 10
#define SLCONST 0.5

template<typename E> struct Value {
        E v;

        Value() {
        }

        Value(const E& value) :
                v(value) {
        }
};

template<typename K, typename V> struct DictNode {
        int level;
        /* as the nodes, which are used in the lock-free memory management
         * scheme, will be reused for the same purpose when re-allocated
         * again after being reclaimed, the individual fields of the nodes
         * that are not being reclaimed, the individual fields of the nodes
         * that are not part of the memory management scheme will be intact.
         * the validLevel field can therefore be used for indicating if the
         * current node can be used for possibly traversing further on a
         * certain level. A value of 0 indicates that this node can not be
         * used for traversing at all, as it is possibly reclaimed or not yet
         * inserted. As the validLevel field is only set to 0 directly before
         * reclamation, a positive value indicates that the node is allocated.
         * A value of n+1 indicated that this node has been inserted up to level n.
         */
        int validLevel;
        int version;
        atomic<Value<V>*> value;
        DictNode<K, V>* prev;
        atomic<DictNode<K, V>*> next[MAXLEVEL];
        K key;

        DictNode() :
                level(-1), validLevel(0), version(0), prev(NULL),key()  {
                value.store(NULL);
                for (int i = 0; i < MAXLEVEL; ++i) {
                        next[i].store(NULL, memory_order_relaxed);
                }
        }

        DictNode(int l, K k, V v) :
                level(-1), validLevel(0), version(0), prev(NULL), key(k) {
                value.store(new Value<V> (v), memory_order_relaxed);
                for (int i = 0; i < MAXLEVEL; ++i) {
                        next[i].store(NULL, memory_order_relaxed);
                }
        }
    
    ~DictNode() {
                delete GET_UNMARKED_VALUE(value.load(memory_order_relaxed));
        }

};

template<typename K, typename V> class LockFreeDictionary {
private:
        DictNode<K, V>* head;
        DictNode<K, V>* tail;
        DictNode<K, V>* INVALID;
    
    SMR<DictNode<K, V>, MAXLEVEL>* mm; // MAXLEVEL for next pointer on every level
        typedef typename SMR<DictNode<K, V>, MAXLEVEL>::HP_Rec HazardP;

public:
        LockFreeDictionary() {
        mm = getSMR<DictNode<K, V>, MAXLEVEL> ();
                head = new DictNode<K, V> ();
                head->validLevel = MAXLEVEL - 1;
                tail = new DictNode<K, V> ();
                tail->validLevel = MAXLEVEL - 1;
                INVALID = new DictNode<K, V> ();

                for (int i = 0; i < MAXLEVEL; ++i) {
                        head->next[i].store(tail, memory_order_relaxed);
                }

                srand( time(NULL));
        }
    
    ~LockFreeDictionary() {
        cout << "size = " << size() << endl;
//        dumpQueue();
                DictNode<K,V> *curr = head->next[0].load(memory_order_relaxed);
        DictNode<K,V> *tmp = NULL;
        int count = 0;
                while (tail != curr) {
            ++count ;
//            cout << "destructing node .........." << GET_UNMARKED(curr)->value.load(memory_order_relaxed)->v<< endl;
            tmp = curr;
            curr = curr->next[0].load(memory_order_relaxed);
            delete tmp;
                }
        
        cout << "count " << count << endl; 
//        cout << "destructing head .........." << head << endl;
//        cout << "destructing tail .........." << tail << endl;
//        cout << "destructing node .........." << INVALID << endl;
        delete head;
        delete tail;
        delete INVALID;
    }

        bool empty() {
                return head->next[0].load(memory_order_relaxed) == tail;
        }

        int size() {
                int size = 0;
                for (DictNode<K,V>* itr = head->next[0].load(memory_order_relaxed); itr
                                != tail; itr = itr->next[0].load(memory_order_relaxed)) {
                        ++size;
                }
                return size;
        }

        bool insert(const K& key, const V& value) {
                DictNode<K, V>* node1;
                DictNode<K, V>* node2;
                Value<V>* value2;
                int curLevel = randomLevel();
//        static int count = 0;
//        ++count;
        
//              cout << "count " << count << ", insert " << key << " to level " << curLevel << endl;
//              dumpQueue();
        HazardP * hp = mm->getHPRec();
#ifdef FREELIST
        DictNode<K, V>* newNode = mm->newNode(hp); /*Allocate a new node*/
        newNode->level = curLevel;
        newNode->key = key;
        newNode->value.store(new Value<V> (value), memory_order_relaxed);
#else
        DictNode<K, V>* newNode = new DictNode<K, V> (curLevel, key, value);/*Allocate a new node*/
#endif
                //              COPY_NODE(newNode);
                //              newNode is local, doesn't need to protected by SMR

                /* search phase to find the node after which the new node (newNode)
                 * should be inserted. This search phase starts from the head node
                 * at the head node at the highest level and traverse down to the
                 * lowest level until the correct node is found (node1). When going
                 * down one level, the last node traversed on that level is remembered
                 * (savedNodes) for later use (this is where we should insert the new
                 * node at that level). */
                DictNode<K, V>* savedNodes[MAXLEVEL + 1];
                savedNodes[MAXLEVEL] = head;
                for (int i = MAXLEVEL - 1; i >= 0; --i) {
                        savedNodes[i] = searchLevel(savedNodes[i + 1], i, key);
                        if ((i < MAXLEVEL - 1) && (i >= curLevel - 1)) {
//                              RELEASE_NODE(savedNodes[i + 1]);
                mm->retire(hp,savedNodes[i + 1]);
                        }
                }
                node1 = savedNodes[0];

                //              int count1 = 0;

                while (true) {
                        //                      cout << "insert loop1 " << ++count1 << endl;
                        node2 = scanKey(node1, 0, key);
                        value2 = node2->value.load(memory_order_relaxed);
                        /* now it is possible that there already exists a node with the same key as of
                         * the new node, the value of the old node (node2) is changed atomically with a CAS.
                         */
                        /*
                         * all keys on nodes are greater than key on head and less than key on tail
                         */
                        if (!IS_MARKED(value2) && (node2->value.load(memory_order_relaxed) != NULL
                                        && node2->key == key)) {
                                if (node2->value.compare_swap(value2, new Value<V> (value))) {
//                                      RELEASE_NODE(node1);
//                                      RELEASE_NODE(node2);
                    mm->retire(hp,node1);
                    mm->retire(hp,node2);
                                        for (int i = 1; i < curLevel; ++i) {
//                                              RELEASE_NODE(savedNodes[i]);
                        mm->retire(hp,savedNodes[i]);
                                        }
//                                      RELEASE_NODE(newNode);
//                                      RELEASE_NODE(newNode);
                    delete value2;
                    mm->delNode(hp,newNode);
//                    cout << "found same value" << endl;
                                        return true;
                                } else {
//                                      RELEASE_NODE(node2);
                    mm->retire(hp,node2);
                                        continue;
                                }
                        }
                        /* otherwise, it starts trying to insert the new node starting with the lowest
                         * level increasing up to the level of the new node. The next pointers of the
                         * (to be previous) nodes are changed atomically with a CAS. */
                        newNode->next[0] = node2;
//                      RELEASE_NODE(node2);
            mm->retire(hp,node2);
                        if (node1->next[0].compare_swap(node2, newNode)) {
//                              RELEASE_NODE(node1);
                mm->retire(hp,node1);
                                break;
                        }
                        //TODO add backoff
                }
                ++newNode->version;
                newNode->validLevel = 1;

                for (int i = 1; i < curLevel; ++i) {
                        node1 = savedNodes[i];
                        while (true) {
                                node2 = scanKey(node1, i, key);
                                newNode->next[i] = node2;
//                              RELEASE_NODE(node2);
                mm->retire(hp,node2);
                                /* after the new node has been insered at the lowest level, it is possible that it is
                                 * deleted by a concurrent Delete operation before it has been inserted at all levels,
                                 */
                                if (IS_MARKED(newNode->value.load(memory_order_relaxed))) {
//                                      RELEASE_NODE(node1);
                    mm->retire(hp,node1);
                                        break;
                                }
                                if (node1->next[i].compare_swap(node2, newNode)) {
                                        newNode->validLevel = i + 1;
//                                      RELEASE_NODE(node1);
                    mm->retire(hp,node1);
                                        break;
                                }
                                // TODO add backoff
                        }
                }
                if (IS_MARKED(newNode->value.load(memory_order_relaxed))) {
                        newNode = helpDelete(newNode, 0);
                }
//              RELEASE_NODE(newNode);
        mm->retire(hp,newNode);
        // newNode is local variable, no need to release
                return true;
        }

        bool findKey(const K& key, V& value) {
        HazardP * hp = mm->getHPRec();
        
                /* basically follows the Insert operation */
                try_again:
        DictNode<K, V>* last = COPY_NODE(head);
        
                mm->employ(hp,0,head);
                if(last != head) {
                        goto try_again;
                }
        
                DictNode<K, V>* node1;
                DictNode<K, V>* node2;

                for (int i = MAXLEVEL - 1; i >= 0; --i) {
                        node1 = searchLevel(last, i, key);
//                      RELEASE_NODE(last);
            mm->retire(hp,last);
                        last = node1;
                }
                node2 = scanKey(last, 0, key);
//              RELEASE_NODE(last);
        mm->retire(hp,last);
                Value<V>* result = node2->value.load(memory_order_relaxed);
                if ((node2->key != key) || (IS_MARKED(result))) {
//                      RELEASE_NODE(node2);
            mm->retire(hp,node2);
                        return false;
                }
                value = result->v;
//              RELEASE_NODE(node2);
        mm->retire(hp,node2);
                return true;
        }

        bool deleteKey(const K& key, V& value) {
                return _delete(key, false, value);
        }

        bool findValue(const V& value, K& key) {
                return fDValue(value, false, key);
        }

        bool deleteValue(const V& value, K& key) {
                return fDValue(value, true, key);
        }

        void dumpQueue() {
                cout << "dumping queue...................." << endl;
                cout << "head:" << head << "->";
                for (DictNode<K, V>* itr = head->next[0].load(memory_order_relaxed); itr
                                != tail; itr = itr->next[0].load(memory_order_relaxed)) {
                        cout << GET_UNMARKED(itr)->value.load(memory_order_relaxed)->v << "->";
                }
                cout << tail << ":tail" << endl;
        }

private:
        /*
         * traverse rapidly from an allocated node last and return the node which key
         * field is the highest key that is lower than the searched key at the current level.
         */
        DictNode<K, V>* searchLevel(DictNode<K, V>*& last, int curLevel,
                        const K& expectedKey) {
        HazardP * hp = mm->getHPRec();
        
        try_again:
                DictNode<K, V>* curNode = last;
                DictNode<K, V>* stop = NULL;
                DictNode<K, V>* nextNode = NULL;
                int count1 = 0;
                int count2 = 0;
                int count3 = 0;
                int count4 = 0;
                int count5 = 0;

                assert(last != tail);

                while (true) {
                        //loop1
                        nextNode = GET_UNMARKED(curNode->next[curLevel].load(memory_order_relaxed));
                        ++count1;
                        if (count1 > 10000) {
                                cout << "searchLevel loop1: count1 = " << count1
                                                << ", count2 = " << count2 << ", count3 = " << count3
                                                << ", count4 = " << count4 << ", count5 = " << count5
                                                << endl;
                                exit(1);
                                //                              dumpQueue();
                                //                              cout << "head: " << head->key << ", tail: " << tail->key
                                //                                              << ", curNode: " << curNode->key << ", nextNode: "
                                //                                              << nextNode->key << endl;
                        }
                        /*
                         * reach the end of this level
                         */
                        if (NULL == nextNode) {
                                //loop2
                                ++count2;
                                if (curNode == last) {
                                        last = helpDelete(last, curLevel);
                                }
                                curNode = last;
                        }
                        /*
                         *current key is lower than expected key, continue search
                         */
                        else if ((nextNode != head) && (nextNode == tail || nextNode->key
                                        >= expectedKey)) {
                                assert(nextNode != head);
                                //                              cout << "nextNode == tail: " << nextNode == tail << endl;
                                //loop3
                                ++count3;
//                              COPY_NODE(curNode);
                // curNode is local, no need to proteted by SMR
                
                                //                              cout << "searchLevel loop3 " << ++count3 << endl;
                                //                              cout << "searchLevel loop3 " << nextNode << ": tail = " << tail
                                //                              << ":" << nextNode->key << ":" << expectedKey << endl;
                                /*
                                 * current key is within the search boundaries. When the node
                                 * suitable for returning has been reached, it is checked
                                 * that it is allocated and also assured that it hen stays
                                 * allocated. If this succeeds the node is returned, otherwise
                                 * the traversal restarted at node last. If this fails twice,
                                 * the traversal are done using the safe scanKey operations,
                                 * as this indicates that the node possibly is inserted at
                                 * the current level, but the validLevel field has not yet
                                 * been updated. In case the node last is marked for deletion,
                                 * it might have been deleted at the current level and thus it
                                 * can not be used for traversal. Therefore the node last is
                                 * checked if it is marked. If marked, the node last will be
                                 * helped fully delete on the current level and last is set to
                                 * the previous node.
                                 *
                                 */
                                //                              cout << "searchLevel loop3: head = " << head << ":" << curNode->validLevel << ": curLevel = " << curLevel
                                //                              << ": curNode = " << curNode << ": last = " << last << ": stop = " << stop << ":" << curNode->key << ":"
                                //                              << expectedKey << endl;
                                if ((curNode->validLevel > curLevel || curNode == last
                                                || curNode == stop) && ((curNode != tail) && (curNode
                                                == head || curNode->key < expectedKey))
                                                && (last == head || curNode == tail || curNode->key
                                                                >= last->key)) {
                                        if (curNode->validLevel <= curLevel) {
//                                              RELEASE_NODE(curNode);
                        mm->retire(hp,curNode);

                        curNode = COPY_NODE(last);
                                mm->employ(hp,0,last);
                                if(curNode != last) {
                                        goto try_again;
                                }

                                                nextNode = scanKey(curNode, curLevel, expectedKey);
//                                              RELEASE_NODE(nextNode);
                        mm->retire(hp,nextNode);
                                        }
                                        return curNode;
                                }
//                              RELEASE_NODE(curNode);
                mm->retire(hp,curNode);

                                stop = curNode;
                                if (IS_MARKED(last->value.load(memory_order_relaxed))) {
                                        last = helpDelete(last, curLevel);
                                }
                                curNode = last;
                        }
                        /*
                         * current key is within the search boundaries
                         */
                        else if (last != tail && nextNode != head && (last == head
                                        || nextNode == tail || nextNode->key >= last->key)) {
                                //loop4
                                assert(last != tail);
                                ++count4;
                                curNode = nextNode;
                        }
                        /*
                         * reach the end of current level but not found a higher key than
                         * expected key
                         */
                        else {
                                //loop5
                                ++count5;
                                if (IS_MARKED(last->value.load(memory_order_relaxed))) {
                                        last = helpDelete(last, curLevel);
                                }
                                curNode = last;
                        }
                }
        }

        bool _delete(const K& key, bool delval, V& value) {
                //              dumpQueue();
//               cout << "delete key: " << key << endl;
        HazardP * hp = mm->getHPRec();
        
                DictNode<K, V>* node1;
                DictNode<K, V>* node2;
                DictNode<K, V>* prev;
                DictNode<K, V>* last;
                DictNode<K, V>* savedNodes[MAXLEVEL + 1];
                Value<V>* tmpValue = NULL;

                /* start with a search phase to find the first node which key is
                 * equal or higher than the searched key. this search phase starts
                 * from the head node at the highest level and traverse down to the
                 * lowest level until the correct node is found (node1). When going
                 * down one level, the last node traversed on that level is remembered
                 * (savedNodes) for later use (this is the previous node at which the
                 * next pointer should be changed in order to delete the targeted node
                 * at that level.)
                 */
        try_again:
                savedNodes[MAXLEVEL] = head;
                for (int i = MAXLEVEL - 1; i >= 0; --i) {
                        savedNodes[i] = searchLevel(savedNodes[i + 1], i, key);
                }
                node1 = scanKey(savedNodes[0], 0, key);

        /* don't find */
        if (node1 == tail) {
            cout << "didn't find" << endl;
            return false;
        }
        
                int count1 = 0;
                while (true) {
                        ++count1;
                        if (count1 > 10000) {
                                cout << "_delete  loop1 : " << count1 << endl;
                        }

                        if (!delval) {
                                tmpValue = node1->value.load(memory_order_relaxed);
                value = tmpValue->v;
                        }
                        //                      cout << node1->value.load(memory_order_relaxed) << ":" << tmpValue << endl;;
                        /* TODO node1->value.load(memory_order_relaxed)->v == value is only
                         * called by FdValue
                         */
                        if ((node1->value.load(memory_order_relaxed) != NULL && node1->key
                                        == key) && (!delval || node1->value.load(
                                        memory_order_relaxed)->v == value) && (!IS_MARKED(tmpValue))) {
                                /* if the found node is the correct node, it tries to set the
                                 * deletion mark of the value field using CAS primitive, and
                                 * if it succeeds it also writes a valid pointer (which
                                 * corresponding node will stay allocated until this node gets
                                 * reclaimed) to the prev field of the node. This prev field is
                                 * necessary in order to increase the performance of concurrent
                                 * HelpDelete operations. these otherwise would have to search for
                                 * the previous node in order to complete the deletion.*/
                                if (node1->value.compare_swap(tmpValue, GET_MARKED_VALUE(tmpValue))) {
                    int index = (node1->level - 1)/2;
                                        node1->prev = COPY_NODE(savedNodes[index]);
                    
                    mm->employ(hp,0,savedNodes[index]);
                        if(node1->prev != savedNodes[index]) {
                                goto try_again;
                        }

                                        break;
                                } else {
                                        continue;
                                }
                        }
//                      RELEASE_NODE(node1);
            mm->retire(hp,node1);
                        for (int i = 0; i < MAXLEVEL; ++i) {
//                              RELEASE_NODE(savedNodes[i]);
                mm->retire(hp,savedNodes[i]);
                        }
                        return false;
                }

                /* the next step is to mark the deletion bits of the next pointers in
                 * the node, starting with the lowest level and going upwards, using
                 * the CAS primitive in each step
                 */
                for (int i = 0; i < node1->level; ++i) {
                        do {
                                node2 = node1->next[i].load(memory_order_relaxed);
                        } while (!IS_MARKED(node2) && !node1->next[i].compare_swap(node2, GET_MARKED(node2)));
                }

                /* it starts the actual deletion by changing the next pointers of the
                 * previous node (prev), starting at the highest level and continuing
                 * downward. the reason for doing the deletion in decreasing order of
                 * levels, is that concurrent operations that are in the search phase also
                 * start at the highest level and proceed downwards, in this way the
                 * concurrent search operations will sooner avoid traversing this node.
                 * the procedure performed by Delete operation in order to change each
                 * next pointer of the previous nodes, is to first search for the previous
                 * node and then perform the CAS primitive until it succeeds.*/

                int count2 = 0;
                for (int i = node1->level - 1; i >= 0; --i) {
                        prev = savedNodes[i];
                        while (true) {
                                ++count2;
                                if (count2 > 10000) {
                                        cout << "_delete  loop2 : " << count2 << endl;
                                }

                                if (node1->next[i].load(memory_order_relaxed) == INVALID) {
                                        break;
                                }
                                last = scanKey(prev, i, node1->key);
//                              RELEASE_NODE(last);
                mm->retire(hp,last);
                                if ((last != node1) || (node1->next[i].load(
                                                memory_order_relaxed) == INVALID)) {
                                        break;
                                }
                                if (prev->next[i].compare_swap(node1, GET_UNMARKED(node1->next[i].load(memory_order_relaxed)))) {
                                        node1->next[i].store(INVALID, memory_order_relaxed);
                                        break;
                                }
                                if (node1->next[i].load(memory_order_relaxed) == INVALID) {
                                        break;
                                }
                                // TODO backoff
                        }
//                      RELEASE_NODE(prev);
            mm->retire(hp,prev);
                }
                for (int i = node1->level; i < MAXLEVEL; ++i) {
//                      RELEASE_NODE(savedNodes[i]);
            mm->retire(hp,savedNodes[i]);
                }
//              RELEASE_NODE(node1);
//              RELEASE_NODE(node1);
//        cout << "delNode " << node1 << endl;
        mm->delNode(node1);
                return true;
        }

        /*
         * traverse from the head node along the lowest level in the skiplist until
         * a node with the searched value is found. In every traversal step, it has
         * to be assured that the step is taken from a valid node to a valid node,
         * both valid at the same time. The validLevel field of the node can be used
         * to safely verify the validity, unless the node has be reclaimed.
         */
        bool fDValue(const V& value, bool del, K& key) {
        HazardP * hp = mm->getHPRec();
                DictNode<K, V>* node1;
                DictNode<K, V>* node2;
                bool ok;
                int version;
                int version2;
                K key2;

                int jump = 16;
        try_again:
                DictNode<K, V>* last = COPY_NODE(head);

        mm->employ(hp,0,head);
        if(last != head) {
                goto try_again;
        }

        next_jump: node1 = last;
                K key1 = node1->key;
                int step = 0;

                while (true) {
                        ok = false;
                        /* The versions field is incremented by the Insert operation, after the node has been
                         * inserted at the lowest level, and directly before the validLevel is set
                         * to indicate validity. By performing two consecutive reads of the version
                         * field with the same contents, and successfully verifying he validity in between
                         * the reads, it can be concluded that the node has stayed valid from the first
                         * read of the version until he successful validity check.
                         */
                        version = node1->version;
                        node2 = node1->next[0].load(memory_order_relaxed);
                        if (!IS_MARKED(node2) && (node2 != NULL)) {
                                version2 = node2->version;
                                key2 = node2->key;
//                              assert(node1 != head);
                                assert(node1 != tail);
                                assert(node2 != head);
//                              assert(node2 != tail);
                                // node1 and node2 could be head and tail
                                if ((node1->key == key1) && (node1->validLevel > 0)
                                                && (node1->next[0].load(memory_order_relaxed) == node2
                                                                && (node1->version == version) && (node2->key
                                                                == key2) && (node2->validLevel > 0)
                                                                && (node2->version == version2))) {
                                        ok = true;
                                }
                        }
                        /*
                         * If this fails, it restarts and traverse the safe node last one step
                         * using ReadNext function.
                         */
                        if (!ok) {
                                node1 = node2 = readNext(last, 0);
                                key1 = key2 = node2->key;
                                version2 = node2->version;
//                              RELEASE_NODE(last);
                mm->retire(hp,last);
                                last = node2;
                                step = 0;
                        }

                        /*
                         * this traversal fails until the tail node is reached
                         */

                        if (node2 == tail) {
                                //RELEASE_NODE(last);
//                cout << "need to delete last" << endl;
                mm->retire(hp,last);
                                return false;
                        }
                        /*
                         * this traversal is continued until a node with the searched
                         * value is reached
                         */
                        if (node2->value.load(memory_order_relaxed)->v == value) {
                                if (node2->version == version2) {
                                        /*
                                         * In case the found node should be deleted, the Delete operation
                                         * if called for this purpose
                                         */
                                        // FIXME value is changed in _delete()
                                        // if (!del || (_delete(key2, true, value) == value)) {
                                        if (del) {
                                                // DeleteValue always reach here
                                                V tmpValue = value;
                                                //                                              cout << "value :" << value << endl;
                                                bool result = _delete(key2, true, tmpValue);
                                                //                                              cout << "result :" << result << ", tmpValue :"
                                                //                                                              << tmpValue << endl;
                                                if (result && tmpValue == value) {
//                                                      RELEASE_NODE(last);
                            mm->retire(hp,last);
                                                        key = key2;
//                            cout << "need to delete last" << endl;
                                                        return true;
                                                }
                                        } else {
                                                // DeleteKey always reach here
//                                              RELEASE_NODE(last);
                        mm->retire(hp,last);
                                                key = key2;
//                        cout << "need to delete last" << endl;
                                                return true;
                                        }
                                }
                        }
                        /*
                         * After a certain number (jump) of successful fast step, an attempt
                         * to advance the last node to current position is performed.
                         */
                        else if (++step >= jump) {
//                              COPY_NODE(node2);
                //node2 is local variable, no need to be protected by SMR
                                /*
                                 * If this attemp succeeds, the threshold jump is increased by 1.5 times,
                                 * otherwise it is halved.
                                 */
                                if ((node2->validLevel == 0) || (node2->key != key2)) {
//                                      RELEASE_NODE(node2);
                    mm->retire(hp,node2);
                                        node2 = readNext(last, 0);
                                        if (jump >= 4) {
                                                jump /= 2;
                                        }
                                } else {
                                        jump += jump / 2;
                                }
//                              RELEASE_NODE(last);
                mm->retire(hp,last);
                                last = node2;
                                goto next_jump;
                        } else {
                                key1 = key2;
                                node1 = node2;
                        }
                }
        }
        DictNode<K, V>* readNext(DictNode<K, V>*& node, int curLevel) {
                //              cout<< "readNext" << endl;
                DictNode<K, V>* nextNode;
                DictNode<K, V>* tmpNode;

                assert(node != tail);
                if (IS_MARKED(node->value.load(memory_order_relaxed))) {
                        node = helpDelete(node, curLevel);
                }
                tmpNode = node->next[curLevel].load(memory_order_relaxed);
                nextNode = READ_NODE(tmpNode);
                while (NULL == nextNode) {
                        node = helpDelete(node, curLevel);
                        tmpNode = node->next[curLevel].load(memory_order_relaxed);
                        nextNode = READ_NODE(tmpNode);
                }
                assert(!IS_MARKED(nextNode));
                return nextNode;
        }

        DictNode<K, V>* scanKey(DictNode<K, V>*& node, int curLevel,
                        const K& expectedKey) {
        HazardP * hp = mm->getHPRec();
                
        DictNode<K, V>* nextNode = readNext(node, curLevel);
                while ((nextNode != tail) && ((nextNode == head) || nextNode->key
                                < expectedKey)) {
//                      RELEASE_NODE(node);
            mm->retire(hp,node);
                        node = nextNode;
                        nextNode = readNext(node, curLevel);
                }
                return nextNode;
        }

        DictNode<K, V>* helpDelete(DictNode<K, V>* node, int curLevel) {
                assert(node != tail && node != head);
        HazardP * hp = mm->getHPRec();
        
                DictNode<K, V>* prevNode;
                DictNode<K, V>* node1;
                DictNode<K, V>* node2;
                DictNode<K, V>* last;

        try_again:
                /*
                 * setting the deletion mark on all next pointers in case they have not been set.
                 * physical deletion of continuous marked nodes on all levels
                 * from the next node of node
                 */
                for (int i = curLevel; i < node->level; ++i) {
                        /*
                         * physical deletion of continuous marked nodes on current level
                         * from the next node of node
                         */
                        do {
                                node2 = node->next[i].load(memory_order_relaxed);
                        } while (!IS_MARKED(node2) && (!node->next[i].compare_swap(node2, GET_MARKED(node2))));
                }

                /*
                 * it checks if the node given in the prev field is valid for deletion on the current
                 * level, otherwise it starts the search at the head node.
                 * increase the reference counter for node
                 */
                prevNode = node->prev;
                if ((prevNode == NULL) || (curLevel >= prevNode->validLevel)) {
                        prevNode = COPY_NODE(head);
            
            mm->employ(hp,0,head);
            if(prevNode != head) {
                goto try_again;
            }
                } else {
                        //COPY_NODE(prevNode);
            // no need to protecteed by SMR, prevNode is local variable
                }

                /*
                 * repeat until the node is deleted at the current level.
                 * remove the current node. it is also marked.
                 */
                int count1 = 0;
                while (true) {
                        ++count1;
                        if (count1 > 10000) {
                                cout << "helpDelete loop1 " << count1 << endl;
                                exit(1);
                        }
                        if (INVALID == node->next[curLevel].load(memory_order_relaxed)) {
                                break;
                        }
                        /* it searches for the correct node (prev). */
                        for (int i = prevNode->validLevel - 1; i >= curLevel; --i) {
                                node1 = searchLevel(prevNode, i, node->key);
//                              RELEASE_NODE(prevNode);
                mm->retire(hp,prevNode);
                                prevNode = node1;
                        }
                        last = scanKey(prevNode, curLevel, node->key);
//                      RELEASE_NODE(last);
            mm->retire(hp,last);
                        if (last != node || INVALID == node->next[curLevel].load(
                                        memory_order_relaxed)) {
                                break;
                        }
                        /* the actual deletion of this node on the current level takes place */
                        if (prevNode->next[curLevel].compare_swap(node, GET_UNMARKED(
                                        node->next[curLevel].load(memory_order_relaxed)))) {
                                node->next[curLevel].store(INVALID, memory_order_relaxed);
                                break;
                        }
                        if (INVALID == node->next[curLevel].load(memory_order_relaxed)) {
                                break;
                        }

                        //TODO add backoff
                }

//              RELEASE_NODE(node);
        mm->retire(hp,node);
                return prevNode;
        }

        int randomLevel() {
                int v = 1;
                while (((static_cast<double> (rand()) / RAND_MAX) < SLCONST) && (v
                                < MAXLEVEL - 1)) {
                        ++v;
                }
                //              cout << v << " ";
                return v;
        }

};
}

#endif /* LOCKFREE_DICTIONARY_H_ */

---