This repository contains implementation of a concurrent tree map. This uses a lock-based internal Binary Search Tree. The algorithm is described in our paper CASTLE: Fast Concurrent Internal Binary Search Tree using Edge-Based Locking published in PPoPP'15. The technical report is available in the papers directory.

1. Change the Makefile appropriately and run make from your shell to build.

$ ./bin/ConcurrentTreeMap.o numOfThreads read% insert% delete% durationInSeconds maximumKeySize initialSeed

• ConcurrentTreeMap() - constructs a concurrent tree map
• V lookup(const K key) - returns the value associated with they key if present
• bool insert(K key, V value) - inserts a (key, value) pair if key is absent
• bool remove(K key) - removes a (key, value) pair if key is present
• unsigned long size() - returns the size of the tree
• bool isValidTree() - validates if this tree is a valid binary search tree

• GSL to create random numbers (faster than standard PRNG)
• Intel "Threading Building Blocks(TBB)" atomic library
• TBB atomic can be used by replacing std::atomic in Node.h
• Some memory allocator like jemalloc, tcmalloc, tbbmalloc, etc. These libraries can improve performance since they are much faster than std malloc.

• Not a full blown templated library like std::map or std::unordered_map
• Supports only numeric types as keys

• Add support for concurrent iterator which returns the elements in sorted order (thinking of a global lock for now)

contact - arunmoezhi at gmail dot com