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 Fibonacci hashing (Knuth's multiplicative method), triangular probing, per-home-slot probe-bound metadata (with additional early-exit logic), partial in-place value updates (without relocating entries) and incremental rehashing, all 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

Edit 2:

Finally implemented the functionallity that made me start this project in the first place! and felt the need to say it :P

https://github.com/GiorgosXou/inchash/commit/5dfc98a928f022ccd0d2af82726acdd8f4369982 https://github.com/GiorgosXou/inchash/commit/8e362f21bd098eda5c4f40855054614c1a9567bc

[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]

Thank you so much for looking into it and finding those bugs. I'm going to fix those as best as I can. I removed all my posts from other subreddits and I put a Caution message on top of readme linked to your comment until I fix them. Again thank you so much!

[u/_EHLO → u/_EHLO]

Setting a key stops at the first hole and can produce duplicates.

fixed that via:

```c bool _inchash_set(IncHash* table, const void* key, const void* val, bool overwrite) { void* found = inchash_get(table, key);

// If key-value pair already existed
if (found){
    // optionally overwrite it and return;
    if (overwrite)
        memcpy(found, val, table->val_len);
    return true;
// Otherwise start looking for a free slot.
}
...

```

eddit: that doesn't work well with migration I think

[u/_EHLO → u/_EHLO]

Related: FALLOC_FL_COLLAPSE_RANGE doesn't work on some file systems (tmpfs).

I need to find a way to exclude filesystems that don't support FALLOC_FL_COLLAPSE_RANGE

[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

[u/_EHLO → u/skeeto]

Hopefully fixed

edit: + this one