SKL

[][Github-url] [][CI-url] [][codecov-url] [][doc-url] [][crates-url] 1. A lock-free thread-safe concurrent ARENA based skiplist implementation which helps develop MVCC memtable for LSM-Tree. 2. A lock-free thread-safe concurrent memory map based on-disk skiplist. Inspired by [Dgraph's badger](https://github.com/dgraph-io/badger/tree/main/skl).

Installation

• Only use heap backend (suppport no_std)

  toml [dependencies] skl = "0.4-alpha.1"

• Enable memory map backend

  toml [dependencies] skl = { version = "0.4.0-alpha.1", features = ["mmap"] }

Examples

Please see examples folder for more details.

Tests

• test:

  sh cargo test --all-features

• miri:

  sh cargo miri test --all-features

Support Platforms

| targets | status | |:-----------------------------:|:---------:| | aarch64-linux-android | ✅ | | aarch64-unknown-linux-gnu | ✅ | | aarch64-unknown-linux-musl | ✅ | | i686-pc-windows-gnu | ✅ | | i686-linux-android | ✅ | | i686-unknown-linux-gnu | ✅ | | mips64-unknown-linux-gnuabi64 | ✅ | | powerpc64-unknown-linux-gnu | ✅ | | riscv64gc-unknown-linux-gnu | ✅ | | wasm32-unknown-unknown | ✅ | | wasm32-unknown-emscripten | ✅ | | x8664-unknown-linux-gnu | ✅ | | x8664-pc-windows-gnu | ✅ | | x86_64-linux-android | ✅ |

TODO (help wanted)

• [x] make the crate test cases pass cargo miri
• [ ] make the crate test cases pass cargo loom
• [ ] Implement
  • [ ] get_or_insert
  • [ ] remove
  • [ ] contains
  • [ ] change signature from insert(k, v) => insert(k, v) -> Option<ValueRef>
  • [x] mmap backend (currently is vector backend)
  • [ ] Supports SkipSet

License

skl-rs is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.

Copyright (c) 2022 Al Liu.