kazachkovaanna

[Ready] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List

1

1. TODO stress tests 2. TODO remove() By team Bakaev, Diogenova, Kazachkova

https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/intrusive/impl/skip_list.h#L1101-L1106 https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/intrusive/impl/skip_list.h#L359-L363 Inside conditional minimum value is choosen, and in random_level max is bounded with 32. But, array index will be initialized with greater number from conditional. So it is...

https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/container/skip_list_set_dhp.h#L7 https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/container/skip_list_map_dhp.h#L7 In skip_list_set_dhp.h name is defined as map, and in map it is set.

A probability of segmentation fault

3

https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/intrusive/skip_list_nogc.h#L55-L61 Afrter m_arrNext = nullptr and before m_nHeight = 1 call of method next(uint nLevel) will cause segmentation fault. This to lines should be in reverse order

Potential error

1

https://github.com/khizmax/libcds/blob/44c052bdb69aaf26d7010074547356c80e55421a/cds/intrusive/skip_list_nogc.h#L356-L369 m_nMinHeight must not be less than m_nMaxHeight. This could be possible with custom random generator [0..n], n < 3. Possibly leading to segmentation fault.