Skip to content

Removing 0 from SkipList<int> breaks enumeration #138

Open
@Mabar16

Description

@Mabar16

Describe the bug
Attempting to enumerate a SkipList<int> whose head node has been removed leads to the program running indefinitely. The head can be removed by calling Remove(0), the defualt value for int, whilst the list contains a negative int.

To Reproduce
Reproducing this bug can be done as follows:

  1. Instantiate a new SkipList<int>
    var list = new SkipList<int>();
  2. Add any negative integer to the list
    list.Add(-23);
  3. Attempt to remove 0 (the head node) from the list
    list.Remove(0);
  4. Perform (almost) any operation that enumerates the skip list
    list.Contains(2);

Expected behavior
list.Remove(0); should not modify the list unless 0 has been added explicitly.

Environment
OS: Windows 10 Home (Version 10.0.18362 Build 18362)
.NET Version: .NET Core v3.1.101
IDE: Microsoft Visual Studio Community 2019 - Version 16.4.5

Additional context

  • The bug can only be reproduced if the SkipList<int> contains at least one negative integer.

  • The bug will not occur if the value 0 has been added to (and not removed from) the SkipList<int>.

  • Step 4 in To Reproduce can be replaced by any function that iterates over the skip list: Contains, Find, Remove, for-each looping over the list, etc.

  • NB: Contains and Find will function as intended if you search for an int that exists in the list (list.Contains(-23); in the case of the example would still work).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions