hare-ds — Data structures examples for Hare

This module provides various general-purpose data structures examples for use in the Hare programming language.

Implemented

• Map-like interface
  • B-tree map
  • Red-black tree map
  • Generic hashmap
    • Convenience wrapper: Fowler-Noll-Vo hashmap
    • Convenience wrapper: SipHash hashmap
  • Generic Swiss table
    • Convenience wrapper: Fowler-Noll-Vo Swiss table
    • Convenience wrapper: SipHash Swiss table
  • Trivial linear slice map
  • Sorted binary search slice map
• Set-like interface
  • Generic bloom filter
    • Convenience wrapper: Fowler-Noll-Vo bloom filter
    • Convenience wrapper: SipHash bloom filter

Planned

• SIMD optimizations
• Map-like interface
  • B+-tree map
  • LSM-tree map
  • Order-statistic tree map
  • Robin-Hood hashmap
  • Generic LRU cache
  • Generic LFU cache
  • TinyLFU cache
  • Trie map (maybe radix tree?)
• Set-like interface
  • Cuckoo filter
• Ring buffer
• Binary heap

Note

The maintainers of Hare would not recommend using this as a library.

From Why doesn’t Hare have generics?,

Our semi-official casual explanation of this choice is that many programs have, at most, one or two really important data structures central to their design (and responsible for their bottlenecks), and because these data structures are important and central to the design, it’s wise for you to implement these yourself so that you can (1) understand them and (2) adapt them to your specific use-case. Optimizing every other data structure that your program makes use of, but which is not bottlenecking your performance, is a premature optimization.

As a consequence of not having generics, the data structures here are not type safe. Structures here typically use []u8 keys and *opaque values.

You should consider copying implementations here to paste into your own code and adapting them to your particular needs as upstream suggests.

Currently, this codebase lacks comments and explanations. Drew DeVault's hare-datastructures may be better-documented implementations worth checking out.

It may be worth investigating reimplementing this to use hare-template.

(See also this alternative viewpoint.)

Support

#chat on irc.runxiyu.org.