lockfreeskiplist.cpp

#include <atomic>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <thread>
#include <chrono>
#include <assert.h>
#include <vector>

static size_t randomLeveLGen() {
	size_t total = 1;
	while (rand() % 2) {
		++total;
	}
	return total;
}

enum class InsertResult {
	MoveAcross,
	MoveBelow,
	InsertAt
};

struct Node {
	int value = -1;
	Node* up = nullptr; // NOT atomic
	std::atomic<Node*> across = nullptr;
	std::atomic<Node*> below = nullptr;

	InsertResult determineInsert(Node* other, Node** nextSpot) {
		Node* belowPtr = below.load();
		Node* acrossPtr = across.load();

		if (acrossPtr) {
			if (acrossPtr->value < other->value) {
				*nextSpot = acrossPtr;
				return InsertResult::MoveAcross;
			} else {
				if (belowPtr) {
					*nextSpot = belowPtr;
					return InsertResult::MoveBelow;
				} else {
					*nextSpot = acrossPtr; // This is just the observed value we should use
					return InsertResult::InsertAt;
				}
			}
		} else {
			if (belowPtr) {
				*nextSpot = belowPtr;
				return InsertResult::MoveBelow;
			} else {
				*nextSpot = nullptr;
				return InsertResult::InsertAt;
			}
		}
		
	}

	static Node* makeWithLevel(int val, size_t len) {
		Node* base = new Node();
		Node* cur = base;
		base->value = val;
		while (len--) {
			Node* next = new Node();
			next->up = cur;
			next->value = val;
			cur->below.store(next);
			cur = next;
		}
		return cur;
	}

	size_t getUpLen() const {
		Node* curPtr = this;
		size_t len = 1;
		while (curPtr->up != nullptr) {
			curPtr = curPtr->up;
			++len;
		}
		return len;
	}

	Node* getLowest() {
		Node* curPtr = this;
		while (curPtr->below.load() != nullptr) {
			curPtr = curPtr->below.load();
		}
		return curPtr;
	}
};

struct SkipList {
	std::atomic<Node*> _root = nullptr;

	SkipList() {
		_root.store(new Node());
	}

	void increaseRootLevel() {
		Node* blank = new Node();
		Node* root = _root.load();
		blank->below.store(root);
		while(!_root.compare_exchange_weak(root, blank)) {
			blank->below.store(root);
		}
	}

	void connectTowers() {
		// gradually go up the tree, from low to high
		Node* lowRoot = _root.load()->getLowest();
		Node* curPtr = lowRoot;
		while (lowRoot != nullptr) {
			Node* upPtr = curPtr->up;
			Node* acrossPtr = curPtr->across.load();
			// try to connect left lower most poles firsrt
			if (acrossPtr == nullptr) {
				if (upPtr == nullptr)
			}
		}
	}


	void insert(int val) {
		Node* toInsert = Node::makeWithLevel(val, 2);
		Node* nextPlace = nullptr;
		Node* curPtr = _root.load();
		while (true) {
			InsertResult outcome = curPtr->determineInsert(toInsert, &nextPlace);
			if (outcome == InsertResult::MoveAcross) {
				curPtr = nextPlace;
			} else if (outcome == InsertResult::MoveBelow) {
				curPtr = nextPlace;
			} else if (outcome == InsertResult::InsertAt) {
				if (curPtr->across.compare_exchange_strong(nextPlace, toInsert)) {
					break;
				}
			} else {
				fprintf(stderr, "Unexpected enum case insert");
				assert(0);
			}
		}
	}
};

static void checkCondition(bool cond, const char* express, unsigned lineno) {
	if (!cond) {
		fprintf(stderr, "FAIL %s line %u\n", express, lineno);
	}
}

#define CHECKIT(cond) checkCondition(cond, #cond, __LINE__)

static void testInsert() {
	SkipList s;
	s.insert(5);
	CHECKIT(s._root.load() != nullptr);
	CHECKIT(s._root.load()->below.load() == nullptr);
	CHECKIT(s._root.load()->across.load() != nullptr);
	CHECKIT(s._root.load()->across.load()->value == 5);
	CHECKIT(s._root.load()->across.load()->across.load() == nullptr);
}

int main(int argc, char const *argv[])
{
	srand(time(nullptr));
	testInsert();
	return 0;
}