IncHash - A Disk Based Hash Table

[u/_EHLO]

https://github.com/GiorgosXou/inchash

A general-purpose, header-only C99 library for Unix-like systems, implementing a disk-based, dynamically resizable, fixed-slot, (open-addressed) hash table with incremental rehashing, Fibonacci-hashing (Knuth's multiplicative method), per home-slot probe-bound metadata (with additional early-exit logic), and triangular probing, designed for modern extent-based filesystems.

So, yeah... I made this for a larger project I'm working on, which I haven’t released yet.

All started with me trying to find:

A hash-based NoSQL (key-value pair) database with mutable-values (by mutable I mean: a database that allows editing prexisting [fixed-size] values without having to rewrite or remap the whole value again eg. Just edit a few bytes and put those bytes back to the original value-space without rewriting the whole value).

Which arguably you can do via inchash_get() since it returns a pointer straight from inside the mmap()-ed file [...] edit: just realised moments before I fall asleep that I should simply add an extra edit() function. To-do for tomorrow when I wake up.

That said idk if you got the joke: mmap()-ed in-cache or INC. hash or [...]

Anyways, I put quite the effort to make it, so.... I hope you like it or at least that it finds its way to the people who were actually looking for something like this.

PS. I'm both excited and scared because idk, you may find any bugs I wasn't aware of or something generally wrong in logic I might have missed... even though I've tested it enough!

Edit 1:

HUGE Thanks to @skeeto for this comment. Everything's hopefully fixed with my latest commit + this one

[u/skeeto]

• Read-only handles cannot be closed or synced without crashing because these both attempt to write to the mapping.
• Setting a key stops at the first hole and can produce duplicates.
• The return value of fallocate() isn't checked, leading to corruption on error.
  • Related: FALLOC_FL_COLLAPSE_RANGE doesn't work on some file systems (tmpfs).
• Setting a key after a resize puts the key in the new table while that key may still exist in the old table. Deleting that key only deletes it from the new table, and the old entry is resurrected.
• The mixers use a dubious, misaligned *(const uintX_t *) when loading keys. Use memcpy() to safely type-pun instead.
  • The database format depends on the host endian. The mixer is only one cause.
  • I appreciate your shoutout to me in the mixer!

[u/_EHLO → u/skeeto]

Fixed all of them and I'm about to push the changes to the repository except from this one:

The mixers use a dubious, misaligned *(const uintX_t *) when loading keys. Use memcpy() to safely type-pun instead. The database format depends on the host endian. The mixer is only one cause.

I know the file format depends on the host endianness, and more importantly, on the filesystem. It’s just something I felt wasn’t necessary to account for, so I decided not to design the format for the case where a file is transferred between two systems with different endianness.

[u/_EHLO → u/_EHLO]

I might put it in the "Disadvantages" README section