Skip to content

xline-kv/interval_map

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

18 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

rb-interval-map

rb-interval-map is a map based on interval tree. It fully implements the insertion and deletion functionality of a red-black tree, ensuring that each modification operation requires at most $O(logN)$ time complexity.

The implementation of the interval tree in rb-interval-map references "Introduction to Algorithms" (3rd ed., Section 14.3: Interval trees, pp. 348–354).

To safely and efficiently handle insertion and deletion operations in Rust, rb-interval-map innovatively uses arrays to simulate pointers for managing the parent-child references in the red-black tree. This approach also ensures that rb-interval-map has the Send and Unpin traits, allowing it to be safely transferred between threads and to maintain a fixed memory location during asynchronous operations.

rb-interval-map implements an IntervalMap struct:

  • It accepts Interval<T> as the key, where T can be any type that implements Ord trait. Therefore, intervals such as $[1, 2)$ and $["aaa", "bbb")$ are allowed
  • The value can be of any type

rb-interval-map supports insert, delete, and iter fns. Traversal is performed in the order of Interval<T> . For instance, with intervals of type Interval<u32>:

  • $[1,4)&lt;[2,5)$, because $1&lt;2$
  • $[1,4)&lt;[1,5)$, because $4&lt;5$

So the order of intervals in IntervalMap is $[1,4)&lt;[1,5)&lt;[2,5)$.

Currently, rb-interval-map only supports half-open intervals, i.e., $[...,...)$.

Benchmark

The benchmark was conducted on a platform with AMD R7 7840H + DDR5 5600MHz. The result are as follows:

  1. Only insert
    insert 100 1000 10, 000 100, 000
    Total time 5.4168 µs 80.518 µs 2.2823 ms 36.528 ms
  2. Insert N and remove N
    insert_and_remove 100 1000 10, 000 100, 000
    Total time 10.333 µs 223.43 µs 4.9358 ms 81.634 ms

TODO

  • Support for $(...,...)$, $[...,...]$ and $(...,...]$ interval types. There's no way to support these interval type without performance loss now.
  • Add Point type for Interval To support Point type, it should also support $[...,...]$, so it couldn't be supported now, either. But you could write code like examples/new_point.
  • Add more tests like etcd.
  • Refine iter mod.

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published