dynamic-sizednonblockinghashtables

dynamic-sizednonblockinghashtables内容摘要：

plied to fresh table help resize if needed – Resizing policy may use heuristics (and is orthogonal) Insert(k) resp Apply(INS, k) if policy Resize() return resp Remove(k) resp Apply(REM, k) if policy Resize() return resp Applying an Insert/Remove Operation 0 1 2 3 pred {8, 16} {9, 17} {14} {3, 7} head Apply(INS, 10) 0, 14} resp = true Invoke(INS, 10) Applying an Insert/Remove Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Apply(INS, 10) What if the bucket is nil? (Invariant) if some bucket of head is nil, then a predecessor table exists 0 1 2 3 4 5 6 7 pred {8, 16, 24} {12, 20} {9, 17} {5, 21} {18} {6} {3, 11, 19} {7, 15, 19} Applying an Insert/Remove Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Apply(INS, 10) 0 1 2 3 4 5 6 7 pred {8, 16, 24} {12, 20} {9, 17} {5, 21} {18} {6} {3, 11, 19} {7, 15, 19} Merge the corresponding buckets of the predecessor. Freeze() Freeze() Applying an Insert/Remove Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Apply(INS, 10) 0 1 2 3 4 5 6 7 pred {8, 16, 24} {12, 20} {9, 17} {5, 21} {18} {6} {3, 11, 19} {7, 15, 19} Merge the corresponding buckets of the predecessor. Applying an Insert/Remove Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Apply(INS, 10) 0 1 2 3 4 5 6 7 pred {8, 16, 24} {12, 20} {9, 17} {5, 21} {18} {6} {3, 11, 19} {7, 15, 19} {6, 18} Create a new FSet object by merging the frozen buckets Install the new FSet using a CAS Call Invoke(INS, 10) on this FSet 0, 18} resp = true The Resize Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Step1: Make sure every bucket of head is not nil … {6, 18} x Step2: Nullify the pred pointer after all buckets are not nil 0 1 pred Step3: Allocate a new table that links to the current head Step4: CAS head The Contains Operation 0 1 2 3 pred {8, 16} {9, 17} {3, 7} head Contains(3) HasMember(3) resp = true The Contains Operation。