strudel

Insertion-ordered hash table suitable for embedding via FFI.

Status: Work in progress.

Strudel was conceived as a drop-in replacement for st_hash, a hash map implemented in C originally written by Peter Moore @ UCB and used in Ruby's implementation of the Hash core class.

This crate is an exercise in implementing an insertion-ordered hash map in Rust that cannot use the built-in Hasher infrastructure. The implementation uses Ruby's Hash backend and Python's dict as prior art.

This crate exports two types:

• StHashMap is a hash map built on top of the high performance HashMap and Vec in Rust std. It is designed to implement the st_hash C API and be FFI-friendly. This map supports in-place updates of hash keys. No mutable iterators are provided.
• StHashSet is a set that wraps an StHashMap like HashSet does in std.

The api and capi modules in strudel build on top of StHashMap to implement a compatible C API to st_hash. This API includes support for iterating over a mutable map and in-place updates of (key, value) pairs. These features distinguish it from the HashMap in Rust std.

Usage

Add this to your Cargo.toml:

[dependencies]
strudel = "1.0"

Building Ruby with Strudel

Strudel exports most of the symbols implemented by st.c in MRI 2.6.3. The included patch and some configure arguments can build the bootstrapping phase of MRI 2.6.3 with Strudel as the hash backend.

To build miniruby with Strudel, run:

./build.sh

build.sh requires autoconf 2.69. On macOS with Homebrew, this can be done with:

brew install autoconf@2.69
PATH="/usr/local/opt/autoconf@2.69/bin:$PATH" ./build.sh

The resulting Ruby is in ./build/ruby-strudel-build-root/miniruby. miniruby can run simple scripts involving Hash, for example:

$ ./build/ruby-strudel-build-root/miniruby -e 'h = {}' -e '1000.times { |i| h[i] = i }' -e 'puts h.length'
1000

miniruby successfully executes the benchmarks in benches.

NOTE: Strudel cannot build a full Ruby due to bugs in the implementation of the st_hash API.

License

strudel is licensed under the MIT License (c) Ryan Lopopolo.

This repository includes a vendored copy of st.h and st.c from Ruby 2.6.3, which is licensed under the Ruby license or BSD 2-clause license. See vendor/README.md for more details. These sources are not distributed on crates.io.

The st_hash implementation in Ruby includes the following notice:

/* This is a public domain general purpose hash table package
   originally written by Peter Moore @ UCB.

   The hash table data strutures were redesigned and the package was
   rewritten by Vladimir Makarov <vmakarov@redhat.com>.  */