Skip to content

Latest commit

 

History

History
42 lines (32 loc) · 1.12 KB

README.org

File metadata and controls

42 lines (32 loc) · 1.12 KB
Raw

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

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