Concurrent Skip List

[This is my write-up for Intel Threading Challenge 2010. You may download the code for Microsoft Visual C++ at the bottom of the page]

Problem Statement

Write an implementation of a skip list data structure that is thread-safe for searching and insertion of key-value pairs.

A skip list is a randomized variant of an ordered linked list with many parallel lists through the data held in the list. When searching for a position in a skip list--to either insert a new key-value item, delete an item, or find a previously inserted item--parallel lists at higher levels skip over large numbers of items. Searching begins at the highest level until a key greater than the one being searched for is encountered. The search shifts to progressively lower levels of parallel lists until the desired location is found. A new item is added by randomly selecting a level, then inserting it in order on the lists for that and all lower levels. With enough levels, searching is O(log n).

To test the correctness of a skip list implementation, write an application that constructs an endgame dictionary held within a skip list. An endgame dictionary is a collection of legal game positions and the sequence of moves for one player to win the game.

The game for which you need to construct an endgame dictionary is known as QuARI. The application must generate every possible starting configuration and generate every possible legal position that can be reached from any given starting configuration and which player will ultimately win from optimal play. The collection of legal generated positions with a notation of which player will win shall make up the endgame dictionary. Once the dictionary is completely constructed, the application will read possible board positions from a file and print out which player (O or X) will win from the given position. If any input positions are unreachable from any starting configuration, this should fact will be output instead of a winning player.

Move on to Scalability Prerequisites