Skip to content

🥐 🥮 Rust port and drop-in replacement for the `st_hash` C hash table library

License

MIT, Unknown licenses found

Licenses found

MIT
LICENSE
Unknown
COPYING
Notifications You must be signed in to change notification settings

artichoke/strudel

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

strudel

GitHub Actions Discord Twitter
Crate API API trunk

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 [email protected]
PATH="/usr/local/opt/[email protected]/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 <[email protected]>.  */

About

🥐 🥮 Rust port and drop-in replacement for the `st_hash` C hash table library

Topics

Resources

License

MIT, Unknown licenses found

Licenses found

MIT
LICENSE
Unknown
COPYING

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •