Skip to content

flode/ARTSynchronized

Repository files navigation

ART Synchronized

This repository provides an implementation of the Adaptive Radix Tree (ART) in a thread safe manner. Two different synchronization schemes are used, Optimistic Lock Coupling and Read-Optimized-Write-Exclusion (ROWEX).

The techniques used are described in the following papers:

Required packages

  • cmake
  • C++ 14 compiler
  • tbb
  • jemalloc

for Debian/Ubuntu: sudo apt-get install cmake g++ libtbb-dev libjemalloc-dev

Build instructions

mkdir build
cd build/
cmake ..
make

Execution instructions

Run the example test with:

./example n 0|1|2

n: number of keys
0: sorted keys
1: dense keys
2: sparse keys

Note that there may not be any keys that are prefixes of other keys. This can be achieved by all keys having the same length or by always passing the null terminator as part of the key.

Known problems

Some g++ versions fail to link jemalloc. Ensure with ldd that jemalloc is linked. If it's not then either use clang or load jemalloc manually:

LD_PRELOAD=/path/to/jemalloc.so ./example ...

License

Copyright 2015-2016 Florian Scheibner

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published