SerialHashTable

A HashTable library designed to be used confined space. For example in a file backed mmap area.

Complexity

• Lookup: log(n)
• Insert: O(n)
• Update:
  • log(n): if the value fits into the same space
  • O(n): if new node needs to be allocated.
• Delete: O(1)

Features

• Uses fix region

Allocation, deallocation happens in the user provided buffer

• Relocatable in O(1)

The user provided buffer can be moved around the memory, as long as the base address is maintained.

• Defragmentation

Delete: the allocated node is marked as free space. Neighbouring spaces are joined. Insert: the first large enough space is used

Dependencies

• glib
• criterion (for the unit tests)

Build

$ # Omit or use your own install prefix.
$ # Tests can be disabled with -DBUILD_TESTING=NO
$ cmake -S . -B build -DCMAKE_INSTALL_PREFIX=`pwd`/install
$ cmake --build build/ --target install

Release tarball

export VERSION=1.0
git archive --format=tar.gz --prefix=SerialHashTable-${VERSION}/ master  > /tmp/SerialHashTable-${VERSION}.tar.gz