KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#developer-tools #typescript #claude-code #codex #dsh #dsh-plugin #ai-agent #ai-agents #deepseek-harness #agent-skills #macos #cli

radix-cpp

★ 19 Open GitHub ↗

Radix set/map implementation

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# radix-cpp

[![GitHub License](https://img.shields.io/github/license/rekola/radix-cpp?logo=github&logoColor=lightgrey&color=yellow)](https://github.com/rekola/radix-cpp/blob/main/LICENSE)
[![CI](https://github.com/rekola/radix-cpp/workflows/Ubuntu-CI/badge.svg)]()
[![VS17-CI](https://github.com/rekola/radix-cpp/workflows/VS17-CI/badge.svg)]()
[![PRs Welcome](https://img.shields.io/badge/PRs-welcome-brightgreen.svg?style=flat-square)](http://makeapullrequest.com)

## Radix set and map implementation for C++

radix-cpp is an experimental flat implementation of ordered set and
map. It uses a hash table with open addressing to implement a form of
radix sort combined with prefix trees, thus providing Θ(1) search time
as is usual for hash tables, but also quick in order traversal of the
keys. Ordinarily hash tables are not ordered, and while in theory, an
order preserving hash function could be used, it would lead to large
number of collisions. In this implementation the key is divided into
multiple 8-bit digits, and each digit is inserted separately in to the
hash table. The prefix key is also stored along with each digit to
construct the prefix tree. According to benchmarks (given uint32_t
keys) the radix-cpp set construction is much faster than that of
std::set, and also faster than sorting the keys using std::sort. Both
std::sort and std::set use comparison sorthing so they have time
complexity of O(n) = n log n.

Iterators are automatically repaired if the underlying table changes,
so they are stable.

Currently only integers, floats, doubles and strings are supported as
keys, but more support is forthcoming.

### Time Complexity

| Operation | Average | Worst Case |
| - | - | - |
| Search | Θ(1) | O(n) |
| Insert | Θ(w) | O(w*n) |
| Delete | Θ(w) | O(w*n) |
| upper_bound() | ? | ? |

* w is the key length in bytes

Iterating over nodes in order can be somewhat expensive if the next
node has different prefix. Also, it's unclear what the time complexity
of the iteration operation is.

### Benchmarks

In these initial benchmarks, radix_cpp::set has been compared with
std::set using uint32_t as the key type. For comparison, a test with
std::sort and a std::vector is also done, and they have similar speed
as std::flat_set. The test consists of constructing a set out of
shuffled array of N consecutive integers and doing an ordered
iteration over the entire set. Search speed comparison has been
intentionally left out, since it would not be very useful given that
radix-cpp has avarage complexity of Θ(1).

![Ordered Set Construction Time](https://github.com/rekola/radix-cpp/assets/6755525/ec1adb25-52dc-407c-86c5-af1b2d97eca9 "Ordered Set Construction Time")
![Ordered Set Iteration Time](https://github.com/rekola/radix-cpp/assets/6755525/fe83baa4-7b15-4642-8f5e-1efed45f17a7 "Ordered Set Iteration Time")

## Implementation

radix-cpp uses Murmur3 as the hash function. The keys can be of
arbitrary size.

### Node

A Node contains the following data:

### Inserting

When inserting a key, each 8-bit digit is inserted along with its
prefix. A prefix tree is thus created inside the hash table.

### Search

When searching for a known key, only the Node for the last digit needs
to be found. The input key is split into a prefix of n-1 bytes and 1
byte ordinal, where n is the size of the key. If a Node with the
prefix and ordinal is found, it is returned.

### Deletion

Deletion works by using tombstones.

### Iteration

An iterator has four variables: the depth (in the prefix tree), the
unordered prefix, the 8-bit ordinal value, and the offset. While the
ordinal is smaller than 255, we know that there are still nodes
available in the ordered range, and when advancing to the next stored
value, we can check them all in order. When the range runs out, we
fall back to the previous digit and advance that one. If the new node
is not a final node, we go upwards in the tree and find the smallest
final node. The offset is used for probing in case of collisions.

### Limitations and Future Plans

- Maximum number of elements on 64-bit system is is 2^56
- NaNs are sorted as they were larger than any other value
- How to sort std::any?
- Unordered iteration is needed (e.g. for set union and intersection)

## Extending types

To implement set and map for custom type, the following free functions must be defined:

Additionally, there must exist a specialization of std::hash for
key_type. Signed integers and floating point numbers are not naturally
ascending, and in such case the initial deconstruct also converts the
data to ordered binary type.

radix-cpp

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README