This repository contains implementation of 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
Binary file is in bin directory
Source files are in src directory
How to compile?

1. Change the Makefile appropriately and run make
   How to run?
   $./bin/castle.o numOfThreads readPercentage insertPercentage deletePercentage durationInSeconds maximumKeySize initialSeed hotKeyFrequency constantFactor sortPercent keySpread keyDistribution distributionParameter
   Example: $./bin/castle.o 64 70 20 10 1 10000 0 100 1 0 s z 1.0
   Output is a semicolon separated line with the last entry denoting throughput in millions of operations per second
   Required Libraries:
   

• GSL to create random numbers
• Intel "Threading Building Blocks(TBB)" atomic library(freely available)
• C++ std library can be used by commenting out "#define TBB" in header.h file
• Some memory allocator like jemalloc, tcmalloc, tbbmalloc,etc

Any questions?

contact - arunmoezhi at gmail dot com