LockfreeListのC++実装

厳密にはLinkedListSetです。
Timothy L. Harrisの論文「A Pragmatic Implementation of Non-Blocking Linked-Lists」より。
前回の日記で紹介したものと同一のアルゴリズムを、今度はスライドではなくソースコードとコメントで説明します。

LockfreeListによる並列Setの実装
キーを昇順で保管し、キーの重複は認めません。

insert: find() → 挿入処理
erase: find() → 削除処理
と、二つの関数でfind()関数を共有しているためまずはfind関数から説明します。

// headから探索を開始し、*pred < t <= *currを満たす pred,currの組を返す
// headはダミーなので有効な値を持たない。
void find(const T& t, node* head, mptr* pred, mptr* curr){ 
	while(1){
		*pred = head; // 先頭を複製
		*curr = (*pred)->next; // これが線形リストとしての最初のノード
		if(*pred != head) continue; // ここまででデータが書き換えられたのならやり直し

		while(1){
			if(curr->get() == NULL){return;} // リストの末尾まで探索したので pred=末尾 curr=NULLで返却
			mptr succ = (*curr)->next; // currの次のノードへのポインタを複製

			if(curr->is_marked()){ // もしcurrに削除マークが付いているのなら
				if(compare_and_set(&(*pred)->next, curr->get(), succ.get())){ // predのnextをcurrのnextに繋ぎ変え
					delete curr.get_pointer();
					*curr = succ; // 成功したなら手元のデータも更新してやり直し
				}else{
					break; // 失敗したならheadからやり直し
				}
			}else{ // 削除マークが付いていない場合
				if((*curr)->item < t){ // 要素が小さいならイタレーションを続ける
					*pred = *curr;
					*curr = succ;
				}else{
					return; // pred < t <= currという条件を満たしたので返却
				}
			}
		}
	}
}

続いて挿入処理。find()を利用しています。

bool insert(const T& t){

	node* newnode = new node(t);

	while(1){
		mptr pred,curr;
		find(t, &mHead, &pred, &curr); // pred < t <= currを満たすpred,currのペアを獲得

		if(curr.get() == NULL || curr->item != t){ // リスト末尾もしくは同一ノードが見あたらなければ

			newnode->next = curr;
			if(compare_and_set(&pred->next, curr.get(), newnode)){ // CASで挿入を試みる
				return true; // 成功
			}else{
				continue; // pred,currが当初の条件を満たさなくなった可能性があるため初めからやり直し
			}

		}else{
			delete newnode;
			return false; // 既に存在していたのでfalseを返却
		}
	}
}

そして削除処理

bool erase(const T& t){
	while(1){
		mptr pred,curr;
		find(t, &mHead, &pred, &curr); // pred < t <= currを満たすpred,currのペアを獲得
		if(curr.get() == NULL){ return false;} // 存在しなかったので終了

		if(curr->item == t){ // 発見したので削除処理

			mptr succ = curr->next; // 継ぎ替え先のポインタを確保して
			if(curr->next.attempt_mark()){ // 削除マーキングが成功したなら
				compare_and_set(&pred->next, curr.get(), succ.get()); // although it failed, no problem
				return true; // ↑のCASが失敗する場合は既に他のfind()で消してくれた場合。よってcasの結果は気にしない
			}else{ // 削除マーキング失敗
				// 他のスレッドによってマークされたか、currのポインタが書き換わったかのどちらか
				continue; // 目標を見失ったので初めからやり直し
			}

		}else{
			return false; // 一致しなかったので終了
		}
	}
}

デストラクタが未実装なためこのままでは使えません。

このリスト単体では「並列アクセスできるだけの線形速度のセットデータ」のような状態のため実用的ではありませんが
このリストをベースにスキップリストやハッシュマップをLockfree化していきます。