hare-ds — Data structures for Hare

This module provides various general-purpose data structures 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

• 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.

Contributing

Create a branch that begins with contrib/ and push to the main repo via SSH directly.

git clone ssh://forge.lindenii.org/hare/:/repos/hare-ds/
cd hare-git
git checkout -b contrib/whatever
# edit and commit stuff
git push -u origin HEAD

Support

#chat on irc.runxiyu.org.

Quick dissent to the argument against generic data structures

While the above is an explanation of why Hare does not have generics, it serves as a general argument against general-purpose data structures, such as those implemented in this library. For examples, when a key-value map is needed but is not a bottleneck, they may recommend using a simple slice of pairs and iterate through them linearly. We respectfully dissent, because we believe that general-purpose data structures can be implemented in a way that is efficient enough for many use cases, even if not as efficient as a hand-crafted data structure for each specific use case. It is, instead, a premature optimization to hand-craft maps for specific use case that would want something better than a linear search. Even though hashmaps and tree-based maps could be considered an optimization over a linear search, optimization should not be all-or-nothing; an appropriate amount of optimization such as using hashmaps in many places, is better than having linear searches everywhere where they are slow, and is also better than hand-crafting maps for every conceivable use case where linear searches are too slow. In practice, many codebases use numerous auxillary maps which share similar access patterns but may use differen types. Re-implementing a bespoke and non-general-purpose map for each key/value type is likely a waste of effort if access patterns are similar.