Warning: Due to various recent migrations, viewing non-HEAD refs may be broken.

/README.md (raw)

# 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?](https://harelang.org/documentation/faq.html#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](https://git.sr.ht/~sircmpwn/hare-datastructures) may be
better-documented implementations worth checking out.

## Contributing

Create a branch that begins with `contrib/` and push to the
[main repo](https://forge.lindenii.org/hare/-/repos/hare-ds/)
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`](https://webirc.runxiyu.org/kiwiirc/#chat)
on
[irc.runxiyu.org](https://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](https://paste.sr.ht/~runxiyu/a0b49d84a3c9f3b35a05dd60993a3cd9d185bfff)
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.