前の記事の続き

node のdelete

prev <-> cur <-> next　で cur を削除するのを前提とすると

で次にdelete の戦略もLock-Free and Practical Doubly Linked List-Based Deques Using Single-Word Compare-and-Swap　に従うと

  1. 削除するノード(cur)のmarking
  2. あとでtraverse してきたやつがmarking を見つけたら
  3. prev.next が cur をさしていたら next をさすようにCAS
  4. next.prev が　cur をさしていたら prev をさすようにCAS

のように最初は実装した。

しかし、traverse してきたやつが marking をみつけた際に、 marking を越えたmarking されてないnode につなげないといけない

marking

ということで削除するノードからmarking をたどっていってmarking されなくなった　pointer が自分に 向くやつがいなくなった状態を safety と定義して(自分にむかってくる marking されてるnode がある場合は unsafety) そいつらを cas していくとこにした。

たとえば上の状態でいえば cur1 を基準にすると 自分にむかってくるnode は prev.next がいるので

dek2

cur1 はこれでsafety cur2 はunsafety だが　next.prev を prev につなげてしまえばsafety

これは単純な例だが

cur2 が先にmarking して cur1 のmarking 前に next の張替えをしてとか 行かのように互いに張替えをしてしまう

del3

この場合は cur1, cur2 ともにunsafety だがそれぞれが safety になるまで処理をすれば

del4

こうなるので cur1 cur2 はpurge できて

prev　<—-> next になる

書いてておもったのは marking は自分のnode しかやらない。delete 時のポインタの張替えは marking を越えても自分に向かっているnode にだけ cas でやるということをすればどうにかなるというこだ


func (l *ListHead) Delete() (err error) {


    for {
        // marking なしの次と前のnode
        prev1 := (*ListHead)(unsafe.Pointer(uintptr(unsafe.Pointer(l.prev)) & mask))
	    next1 := (*ListHead)(unsafe.Pointer(uintptr(unsafe.Pointer(l.next)) & mask))

		prev := prev1
		next := next1

        if !MarkListHead(&l.next, next) {
			continue
		}
		if !MarkListHead(&l.prev, prev) {
            continue
		}

        prevSkipMark := PrevSkipMark(l.prev)
		nextSkipMark := NextSkipMark(l.next)

		prevs := []**ListHead{&prev1.next, &prev2.next}
		nexts := []**ListHead{&next1.prev, &next2.prev}



        // prev で自分にむかってくるnode pointer たちをはりかえる
        t := false
		for _, pn := range prevs {
			if *pn != l {
				continue
			}
			next := next1
			if next.IsMarked() {
				next = nextSkipMark
			}
			t = Cas(prevs[i], l, next)
		}

         // next で自分にむかってくるnode pointer たちをはりかえる
		for _, np := range nexts {
			if *np != l {
				continue
			}
			prev := prev1
			if prev.IsMarked() {
				prev = prevSkipMark
			}
			t = Cas(np, l, prev)
		}

        // まだ自分にむかってくるポインタがあれば繰り返す
		for _, toL := range append(prevs, nexts...) {
			if l == *toL {
                continue
			}
		}
    }
}

safety かどうか

いちよsafety かどうかの関数も書いていて

func (head *ListHead) IsSafety() (bool, error) {

	prev := PrevSkipMark(head.prev)
	next := NextSkipMark(head.next)

	if prev.next.IsMarked() {
		return false, nil
	}

	if next.prev.IsMarked() {
		return false, nil
	}
	if prev.next == head {
		return false, nil
	}
	if next.prev == head {
		return false, nil
	}

	return true, nil
}

こんな感じになっている

traverse 編に続く