diskhash (empty) → 0.0.1.0

raw patch · 9 files changed

+879/−0 lines, 9 filesdep +HUnitdep +QuickCheckdep +basesetup-changed

Dependencies added: HUnit, QuickCheck, base, bytestring, directory, test-framework, test-framework-hunit, test-framework-quickcheck2, test-framework-th

Files

• COPYING +23/−0
• ChangeLog +0/−0
• README.md +156/−0
• Setup.hs +2/−0
• diskhash.cabal +48/−0
• haskell/Data/DiskHash.hs +171/−0
• haskell/Data/DiskHash/Tests.hs +82/−0
• haskell/Data/diskhash2.c +7/−0
• src/diskhash.c +390/−0

@@ -0,0 +1,23 @@+Copyright (c) 2017+Luis Pedro Coelho <luis@luispedro.org>++Permission is hereby granted, free of charge, to any person+obtaining a copy of this software and associated documentation+files (the "Software"), to deal in the Software without+restriction, including without limitation the rights to use,+copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the+Software is furnished to do so, subject to the following+conditions:++The above copyright notice and this permission notice shall be+included in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT+HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR+OTHER DEALINGS IN THE SOFTWARE.

@@ -0,0 +1,156 @@+# Disk-based hashtable++[![Travis](https://api.travis-ci.org/luispedro/diskhash.png)](https://travis-ci.org/luispedro/diskhash)+[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT)+++A simple disk-based hash table.++The code is in C, wrappers are provided for Python, Haskell, and C++. The+wrappers follow similar APIs with variations to accomodate the language+specificity. They all use the same underlying code, so you can open a hashtable+created in C from Haskell, modify it within your Haskell code, and open the+result in Python (although Python's version currently only deals with integers,+stored as longs).++Cross-language functionality will work best for very simple types so that you+can control their binary representation (64-bit integers, for example).++Reading does not touch the disk representation at all and, thus, can be done on+top of read-only files or using multiple threads. Writing or modifying values+is, however, not thread-safe.++## Examples++The following examples all create a hashtable to store longs (`int64_t`), then+set the value associated with the key `"key"` to 9. In the current API, the+maximum size of the keys needs to be pre-specified, which is the value `15`+below.++### Raw C++```c+#include <stdio.h>+#include <inttypes.h>+#include "diskhash.h"++int main(void) {+    HashTableOpts opts;+    opts.key_maxlen = 15;+    opts.object_datalen = sizeof(int64_t);+    char* err = NULL;+    HashTable* ht = dht_open("testing.dht", opts, O_RDWR|O_CREAT, &err);+    if (!ht) {+        if (!err) err = "Unknown error";+        fprintf(stderr, "Failed opening hash table: %s.\n", err);+        return 1;+    }+    long i = 9;+    dht_insert(ht, "key", &i);+    +    long* val = (long*) dht_lookup(ht, "key");+    printf("Looked up value: %l\n", *val);++    dht_free(ht);+    return 0;+}+```++### Haskell++In Haskell, you have different types/functions for read-write and read-only+hashtables.++Read write example:++```haskell+import Data.DiskHash+import Data.Int+main = do+    ht <- htOpenRW "testing.dht" 15+    htInsertRW ht "key" (9 :: Int64)+    val <- htLookupRW "key" ht+    print val+```++Read only example (`htLookupRO` is pure in this case):++```haskell+import Data.DiskHash+import Data.Int+main = do+    ht <- htOpenRO "testing.dht" 15+    let val :: Int64+        val = htLookupRO "key" ht+    print val+```+++### Python++Python's interface is more limited and only integers are supported as values in+the hash table (they are stored as 64-bit integers).++```python+import diskhash+tb = diskhash.Str2int("testing.dht", 15)+tb.insert("key", 9)+print(tb.lookup("key"))+```++The Python interface is currently Python 3 only. Patches to extend it to 2.7+are welcome, but it's not a priority.+++### C++++```c+++#include <iostream>+#include <string>++#include <diskhash.hpp>++int main() {+    const int key_maxlen = 15;+    dht::DiskHash<uint64_t> ht("testing.dht", key_maxlen, dht::DHOpenRW);+    std::string line;+    uint64_t ix = 0;+    while (std::getline(std::cine, line)) {+        if (line.length() > key_maxlen) {+            std::cerr << "Key too long: '" << line << "'. Aborting.\n";+            return 2;+        }+        const bool inserted = ht.insert(line.c_str(), ix);+        if (!inserted) {+            std::cerr  << "Found repeated key '" << line << "' (ignored).\n";+        }+        ++ix;+    }+    return 0;+}+```++## Statibility++This is _beta_ software. It is good enough that I am using it, but the API can+change in the future with little warning. The binary format will be fixed once+there is an upload to PyPI or Stackage, but that format is versioned (the magic+string encodes its version, so changes can be detected).++[Automated unit testing](https://travis-ci.org/luispedro/diskhash) ensures that+basic mistakes will not go uncaught.++## Limitations++- You must specify the maximum key size. This can be worked around either by+  pre-hashing the keys (with a strong hash) or using multiple hash tables for+  different key sizes. Neither is currently implemented in diskhash.++- You cannot delete objects. This was not a necessity for my uses, so it was+  not implemented. A simple implementation could be done by marking objects as+  "deleted" in place and recompacting when the hash table size changes or with+  an explicit `dht_gc()` call. It may also be important to add functionality to+  shrink hashtables so as to not waste disk space.++License: MIT+

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,48 @@+name:               diskhash+version:            0.0.1.0+synopsis:           Disk-based hash table+description:        Disk-based hash table+category:           Data+author:             Luis Pedro Coelho+maintainer:         Luis Pedro Coelho+license:            MIT+license-file:       COPYING+cabal-version:      >= 1.10+build-type:         Simple+bug-reports:        https://github.com/luispedro/diskhash/issues+extra-source-files: README.md ChangeLog++library+  default-language: Haskell2010+  exposed-modules: Data.DiskHash+  hs-source-dirs: haskell/+  C-sources: haskell/Data/diskhash2.c src/diskhash.c+  Include-dirs: src/+  ghc-options: -Wall+  build-depends:+    base > 4 && < 5,+    bytestring++Test-Suite diskhashtest+  default-language: Haskell2010+  type: exitcode-stdio-1.0+  main-is: Data/DiskHash/Tests.hs+  other-modules: Data.DiskHash+  C-sources: haskell/Data/diskhash2.c src/diskhash.c+  ghc-options: -Wall+  hs-source-dirs: haskell/+  include-dirs: src/+  build-depends:+    base > 4 && < 5,+    bytestring,+    directory,+    HUnit,+    QuickCheck,+    test-framework,+    test-framework-hunit,+    test-framework-quickcheck2,+    test-framework-th++source-repository head+  type: git+  location: https://github.com/luispedro/diskhash

@@ -0,0 +1,171 @@+{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}+module Data.DiskHash+    ( DiskHashRO+    , DiskHashRW+    , htOpenRO+    , htOpenRW+    , withDiskHashRW+    , htLookupRO+    , htLookupRW+    , htSizeRW+    , htSizeRO+    , htInsert+    , htModify+    , htReserve+    ) where++import qualified Data.ByteString as B+import qualified Data.ByteString.Char8 as B8+import Control.Exception (throwIO)+import System.IO.Unsafe (unsafeDupablePerformIO)+import Foreign.Ptr (Ptr, FunPtr, castPtr, nullPtr)+import Foreign.ForeignPtr (ForeignPtr, newForeignPtr, withForeignPtr, finalizeForeignPtr)+import Foreign.Storable (Storable(..))+import Foreign.Marshal.Alloc (alloca, free)+import Foreign.C.Types (CInt(..), CSize(..))+import Foreign.C.String (CString, peekCString)++-- | Disk based hash table+--+-- The Haskell interface has two types, distinguishing between read-only and+-- read-write hash tables. Operations on the RW variant are in the IO monad,+-- while operations on RO tables are all pure (after opening the table,+-- naturally).+--+-- The datastructures are all strict.++type HashTable_t = ForeignPtr ()+newtype DiskHashRO a = DiskHashRO HashTable_t+newtype DiskHashRW a = DiskHashRW HashTable_t++foreign import ccall "dht_open2" c_dht_open2:: CString -> CInt -> CInt -> CInt -> Ptr CString -> IO (Ptr ())+foreign import ccall "dht_lookup" c_dht_lookup :: Ptr () -> CString -> IO (Ptr ())+foreign import ccall "dht_reserve" c_dht_reserve :: Ptr () -> CInt -> Ptr CString -> IO ()+foreign import ccall "dht_insert" c_dht_insert :: Ptr () -> CString -> Ptr () -> Ptr CString -> IO CInt+foreign import ccall "dht_size" c_dht_size :: Ptr () -> IO CSize+foreign import ccall "&dht_free" c_dht_free_p :: FunPtr (Ptr () -> IO ())++-- | Internal function to handle error message interface+--+-- If argument points to NULL, then return "No message"+-- Otherwise, return its contents and release memory+getError :: Ptr CString -> IO String+getError err = do+    err' <- peek err+    if err' == nullPtr+        then return "No message"+        else do+            m <- peekCString err'+            free err'+            return m+-- | open a hash table in read-write mode+htOpenRW :: forall a. (Storable a) => FilePath -> Int -> IO (DiskHashRW a)+htOpenRW fpath maxk = DiskHashRW <$> open' (undefined :: a) fpath maxk 66++-- | open a hash table in read-only mode+htOpenRO :: forall a. (Storable a) => FilePath -> Int -> IO (DiskHashRO a)+htOpenRO fpath maxk = DiskHashRO <$> open' (undefined :: a) fpath maxk 0++open' :: forall a. (Storable a) => a -> FilePath -> Int -> CInt -> IO HashTable_t+open' unused fpath maxk flags = B.useAsCString (B8.pack fpath) $ \fpath' ->+    alloca $ \err -> do+        poke err nullPtr+        ht <- c_dht_open2 fpath' (fromIntegral maxk) (fromIntegral $ sizeOf unused) flags err+        if ht == nullPtr+            then do+                errmsg <- getError err+                throwIO $ userError ("Could not open hash table: " ++ show errmsg)+            else+                newForeignPtr c_dht_free_p ht++-- | Open a hash table in read-write mode and pass it to an action+--+-- Once the action is is complete, the hashtable is closed (and sync'ed to disk).+withDiskHashRW :: (Storable a) => FilePath -> Int -> (DiskHashRW a -> IO b) -> IO b+withDiskHashRW fp s act = do+    ht@(DiskHashRW ht') <- htOpenRW fp s+    r <- act ht+    finalizeForeignPtr ht'+    return r+++-- | Retrieve the size of the hash table+htSizeRW :: DiskHashRW a -> IO Int+htSizeRW (DiskHashRW ht) = withForeignPtr ht $ \ht' -> fromIntegral <$> (c_dht_size ht')++-- | Retrieve the size of the hash table+htSizeRO :: DiskHashRO a -> Int+htSizeRO (DiskHashRO ht) = unsafeDupablePerformIO (htSizeRW (DiskHashRW ht))+++-- | insert an element into the hash table+--+-- Returns whether an insertion took place (if an object with that key already+-- exists, no insertion is made).+htInsert :: (Storable a) => B.ByteString+                            -- ^ key+                            -> a+                            -- ^ value+                            -> DiskHashRW a+                            -- ^ hash table+                            -> IO Bool+                            -- ^ True if inserted, False if not+htInsert key val (DiskHashRW ht) =+        withForeignPtr ht $ \ht' ->+            B.useAsCString key $ \key' ->+                alloca $ \val' ->+                    alloca $ \err -> do+                        poke err nullPtr+                        poke val' val+                        r <- c_dht_insert ht' key' (castPtr val') err+                        case r of+                            1 -> return True+                            0 -> return False+                            -1 -> do+                                errmsg <- getError err+                                throwIO $ userError ("insertion failed ("++errmsg++")")+                            _ -> do+                                errmsg <- getError err+                                throwIO $ userError ("Unexpected return from dht_insert: " ++ errmsg)+-- | Lookup by key+htLookupRW :: (Storable a) => B.ByteString -> DiskHashRW a -> IO (Maybe a)+htLookupRW key (DiskHashRW ht) =+    withForeignPtr ht $ \ht' ->+        B.useAsCString key $ \key' -> do+            r <- c_dht_lookup ht' key'+            if r == nullPtr+                then return Nothing+                else Just <$> peek (castPtr r)++-- | Lookup by key+htLookupRO :: (Storable a) => B.ByteString -> DiskHashRO a -> Maybe a+htLookupRO key (DiskHashRO ht) = unsafeDupablePerformIO (htLookupRW key (DiskHashRW ht))++-- | Modify a value+htModify :: (Storable a) => B.ByteString -> (a -> a) -> DiskHashRW a -> IO Bool+htModify key f (DiskHashRW ht) =+    withForeignPtr ht $ \ht' ->+        B.useAsCString key $ \key' -> do+            r <- castPtr <$> c_dht_lookup ht' key'+            if r == nullPtr+                then return False+                else do+                    val <- peek r+                    poke r (f val)+                    return True++-- | Reserve space in the hash table+--+-- If the operation fails, an exception is raised+htReserve :: (Storable a) => Int -> DiskHashRW a -> IO Int+htReserve cap (DiskHashRW ht) =+    withForeignPtr ht $ \ht' ->+        alloca $ \err -> do+            poke err nullPtr+            cap' <- fromEnum <$> c_dht_reserve ht' (fromIntegral cap) err+            if cap' == 0+                then do+                    errmsg <- getError err+                    throwIO . userError $ "Could not change capacity: " ++ errmsg+                else return cap'+

@@ -0,0 +1,82 @@+{-# LANGUAGE OverloadedStrings, TemplateHaskell, QuasiQuotes #-}++module Main where++import           Test.Framework.TH+import           Test.HUnit+import           Test.QuickCheck.Property+import           Test.Framework.Providers.HUnit+import           Test.Framework.Providers.QuickCheck2++import qualified Data.ByteString as B+import qualified Data.ByteString.Char8 as B8+import           Control.Arrow (first)+import           Control.Monad (forM, forM_)+import           Control.Exception (throwIO)+import           System.IO.Error (isDoesNotExistError, catchIOError)+import           System.Directory (doesFileExist, removeFile)+import           Data.Int++import Data.DiskHash++main :: IO ()+main = do+    removeFileIfExists outname+    $(defaultMainGenerator)++removeFileIfExists :: FilePath -> IO ()+removeFileIfExists fp = removeFile fp `catchIOError` ignoreDoesNotExistError+    where+        ignoreDoesNotExistError e+                | isDoesNotExistError e = return ()+                | otherwise = throwIO e++outname :: FilePath+outname = "testing.dht"++case_smoke = do+    ht <- htOpenRW outname 15+    s <- htSizeRW ht+    assertEqual "new table has size 0" s 0+    inserted <- htInsert "key" (9 :: Int64) ht+    assertBool "inserted should have return True" inserted+    reInserted <- htInsert "key" (9 :: Int64) ht+    assertBool "inserted should have return False (2nd time around)" (not reInserted)+    s' <- htSizeRW ht+    assertEqual "after insert table has size 1" s' 1+    val <- htLookupRW "key" ht+    assertEqual "Lookup" (Just 9) val+    removeFileIfExists outname++case_open_close = do+    withDiskHashRW outname 15 $ \ht -> do+        s <- htSizeRW ht+        assertEqual "new table has size 0" s 0+        inserted <- htInsert "key" (9 :: Int64) ht+        assertBool "inserted should have return True" inserted+    ht <- htOpenRO outname 15+    assertEqual "read-only table after reopen" (htSizeRO ht) 1+    assertEqual "Lookup" (Just (9 :: Int64)) (htLookupRO "key" ht)+    removeFileIfExists outname++-- prop_insert_find :: [(String, Int64)] -> IO Bool+prop_insert_find args = ioProperty $ do+    let args' = normArgs args+    found <- withDiskHashRW outname 15 $ \ht -> do+        forM_ args' $ \(k,val) -> htInsert k val ht+        forM args' $ \(k, val) -> do+            v <- htLookupRW k ht+            return $ v == Just val+    removeFileIfExists outname+    return $! and found+++normArgs :: [(String, Int64)] -> [(B.ByteString, Int64)]+normArgs = normArgs' [] . map (first normKey)+    where+        normKey = B8.pack . (filter (/= '\0'))+        normArgs' r [] = r+        normArgs' r (x@(k,_):xs)+            | k `elem` (map fst r) = normArgs' r xs+            | B.length k >= 15 = normArgs' r xs+            | otherwise = normArgs' (x:r) xs

@@ -0,0 +1,7 @@+#include "diskhash.h"+HashTable* dht_open2(const char* f, unsigned int key_maxlen, unsigned int object_datalen, int flags, char** err) {+    HashTableOpts opts;+    opts.key_maxlen = key_maxlen;+    opts.object_datalen = object_datalen;+    return dht_open(f, opts, flags, err);+}

@@ -0,0 +1,390 @@+#include <inttypes.h>+#include <stdlib.h>+#include <stdio.h>+#include <string.h>+#include <assert.h>+#include <errno.h>++#include <unistd.h>+#include <fcntl.h>++#include <sys/types.h>+#include <sys/stat.h>+#include <sys/mman.h>++#include "diskhash.h"+#include "primes.h"++typedef struct HashTableHeader {+    char magic[16];+    HashTableOpts opts_;+    size_t cursize_;+    size_t slots_used_;+} HashTableHeader;++typedef struct HashTableEntry {+    const char* ht_key;+    void* ht_data;+} HashTableEntry;++static+uint64_t hash_key(const char* k) {+    /* Taken from http://www.cse.yorku.ca/~oz/hash.html */+    uint64_t hash = 5381;+    for ( ; *k; ++k) {+        hash *= 33;+        hash ^= (uint64_t)*k;+    }+    return hash;+}++inline static+size_t aligned_size(size_t s) {+    size_t s_8bytes = s & ~0x7;+    return s_8bytes == s ? s : (s_8bytes + 8);+}++inline static+HashTableHeader* header_of(HashTable* ht) {+    return (HashTableHeader*)ht->data_;+}++inline static+const HashTableHeader* cheader_of(const HashTable* ht) {+    return (const HashTableHeader*)ht->data_;+}++inline static+int is_64bit(const HashTable* ht) {+    return cheader_of(ht)->cursize_ > (1L << 32);+}++inline static+size_t node_size_opts(HashTableOpts opts) {+    return aligned_size(opts.key_maxlen + 1) + aligned_size(opts.object_datalen);+}++inline static+size_t node_size(const HashTable* ht) {+    return node_size_opts(cheader_of(ht)->opts_);+}++inline static+int entry_empty(const HashTableEntry et) {+    return !et.ht_key;+}++void* hashtable_of(HashTable* ht) {+    return (unsigned char*)ht->data_ + sizeof(HashTableHeader);+}+++static+uint64_t get_table_at(const HashTable* ht, uint64_t ix) {+    if (is_64bit(ht)) {+        uint64_t* table = (uint64_t*)hashtable_of((HashTable*)ht);+        return table[ix];+    } else {+        uint32_t* table = (uint32_t*)hashtable_of((HashTable*)ht);+        return table[ix];+    }+}++static+void set_table_at(HashTable* ht, uint64_t ix, const uint64_t val) {+    if (is_64bit(ht)) {+        uint64_t* table = (uint64_t*)hashtable_of(ht);+        table[ix] = val;+    } else {+        uint32_t* table = (uint32_t*)hashtable_of(ht);+        table[ix] = val;+    }+}++void show_ht(const HashTable* ht) {+    fprintf(stderr, "HT {\n"+                "\tmagic = \"%s\",\n"+                "\tcursize = %d,\n"+                "\tslots used = %ld\n"+                "\n", cheader_of(ht)->magic, (int)cheader_of(ht)->cursize_, cheader_of(ht)->slots_used_);++    int i;+    for (i = 0; i < cheader_of(ht)->cursize_; ++i) {+        fprintf(stderr, "\tTable [ %d ] = %d\n",(int)i, (int)get_table_at(ht, i));+    }+    fprintf(stderr, "}\n");+}++static+HashTableEntry entry_at(const HashTable* ht, size_t ix) {+    ix = get_table_at(ht, ix);+    HashTableEntry r;+    if (ix == 0) {+        r.ht_key = 0;+        r.ht_data = 0;+        return r;+    }+    --ix;+    const size_t sizeof_table_elem = is_64bit(ht) ? sizeof(uint64_t) : sizeof(uint32_t);+    const char* node_data = (const char*)ht->data_+                            + sizeof(HashTableHeader)+                            + cheader_of(ht)->cursize_ * sizeof_table_elem;+    r.ht_key = node_data + ix * node_size(ht);+    r.ht_data = (void*)( node_data + ix * node_size(ht) + aligned_size(cheader_of(ht)->opts_.key_maxlen + 1) );+    return r;+}++HashTableOpts dht_zero_opts() {+    HashTableOpts r;+    r.key_maxlen = 0;+    r.object_datalen = 0;+    return r;+}++HashTable* dht_open(const char* fpath, HashTableOpts opts, int flags, char** err) {+    if (!fpath || !*fpath) return NULL;+    const int fd = open(fpath, flags, 0644);+    int needs_init = 0;+    if (fd < 0) {+        if (err) { *err = strdup("open call failed."); }+        return NULL;+    }+    HashTable* rp = (HashTable*)malloc(sizeof(HashTable));+    if (!rp) {+        if (err) { *err = NULL; }+        return NULL;+    }+    rp->fd_ = fd;+    rp->fname_ = strdup(fpath);+    if (!rp->fname_) {+        if (err) { *err = NULL; }+        close(rp->fd_);+        free(rp);+        return NULL;+    }+    struct stat st;+    fstat(rp->fd_, &st);+    rp->datasize_ = st.st_size;+    if (rp->datasize_ == 0) {+        needs_init = 1;+        rp->datasize_ = sizeof(HashTableHeader) + 7 * sizeof(uint32_t) + 3 * node_size_opts(opts);+        if (ftruncate(fd, rp->datasize_) < 0) {+            if (err) { *err = strdup("Could not allocate disk space."); }+            close(rp->fd_);+            free((char*)rp->fname_);+            free(rp);+            return NULL;+        }+    }+    const int prot = (flags == O_RDONLY) ?+                                PROT_READ+                                : PROT_READ|PROT_WRITE;+    rp->data_ = mmap(NULL, +            rp->datasize_,+            prot,+            MAP_SHARED,+            rp->fd_,+            0);+    if (rp->data_ == MAP_FAILED) {+        if (err) { *err = strdup("mmap() call failed."); }+        close(rp->fd_);+        free((char*)rp->fname_);+        free(rp);+        return NULL;+    }+    if (needs_init) {+        strcpy(header_of(rp)->magic, "DiskBasedHash10");+        header_of(rp)->opts_ = opts;+        header_of(rp)->cursize_ = 7;+        header_of(rp)->slots_used_ = 0;+    } else if (strcmp(header_of(rp)->magic, "DiskBasedHash10")) {+        char start[16];+        strncpy(start, header_of(rp)->magic, 14);+        start[13] = '\0';+        if (!strcmp(start, "DiskBasedHash")) {+            if (err) { *err = strdup("Version mismatch. This code can only load version 1.0."); }+        } else {+            if (err) { *err = strdup("No magic number found."); }+        }+        dht_free(rp);+        return 0;+    } else if (header_of(rp)->opts_.key_maxlen != opts.key_maxlen+                || header_of(rp)->opts_.object_datalen != opts.object_datalen) {+        if (err) { *err = strdup("Options mismatch."); }+        dht_free(rp);+        return 0;+    }+    return rp;+}++void dht_free(HashTable* ht) {+    munmap(ht->data_, ht->datasize_);+    fsync(ht->fd_);+    close(ht->fd_);+    free((char*)ht->fname_);+    free(ht);+}++char random_char(void) {+    const char* available =+        "0123456789"+        "abcdefghijklmnopqrstuvwxyz"+        "ABCDEFGHIJKLMNOPQRSTUVWXYZ";+    return available[rand() % (26*2 + 10)];+}+++char* generate_tempname_from(const char* base) {+    char* res = (char*)malloc(strlen(base) + 21);+    if (!res) return NULL;+    strcpy(res, base);+    char* p = res;+    while (*p) ++p;+    *p++ = '.';+    int i;+    for (i = 0; i < 19; ++i) {+        *p++ = random_char();+    }+    *p = 0;+    return res;+}++size_t dht_reserve(HashTable* ht, size_t cap, char** err) {+    if (header_of(ht)->cursize_ / 2 > cap) {+        return header_of(ht)->cursize_ / 2;+    }+    const int starting_slots = cheader_of(ht)->slots_used_;+    const int min_slots = cap * 2 + 1;+    int i = 0;+    while (primes[i] && primes[i] < min_slots) ++i;+    const int n = primes[i];+    cap = n / 2;+    const size_t sizeof_table_elem = is_64bit(ht) ? sizeof(uint64_t) : sizeof(uint32_t);+    const size_t total_size = sizeof(HashTableHeader) + n * sizeof_table_elem + cap * node_size(ht);++    HashTable* temp_ht = (HashTable*)malloc(sizeof(HashTable));+    while (1) {+        temp_ht->fname_ = generate_tempname_from(ht->fname_);+        if (!temp_ht->fname_) {+            if (err) { *err = NULL; }+            free(temp_ht);+            return 0;+        }+        temp_ht->fd_ = open(temp_ht->fname_, O_EXCL | O_CREAT | O_RDWR, 0600 );+        if (temp_ht->fd_) break;+        free((char*)temp_ht->fname_);+    }+    if (ftruncate(temp_ht->fd_, total_size) < 0) {+        if (err) { *err = strdup("Could not allocate disk space."); }+        free((char*)temp_ht->fname_);+        free(temp_ht);+        return 0;+    }+    temp_ht->datasize_ = total_size;+    temp_ht->data_ = mmap(NULL, +            temp_ht->datasize_,+            PROT_READ|PROT_WRITE,+            MAP_SHARED,+            temp_ht->fd_,+            0);+    if (temp_ht->data_ == MAP_FAILED) {+        if (err) {+            const int errorbufsize = 512;+            *err = (char*)malloc(errorbufsize);+            if (*err) {+                snprintf(*err, errorbufsize, "Could not mmap() new hashtable: %s.\n", strerror(errno));+            }+        }+        close(temp_ht->fd_);+        unlink(temp_ht->fname_);+        free((char*)temp_ht->fname_);+        free(temp_ht);+        return 0;+    }+    memcpy(header_of(temp_ht), header_of(ht), sizeof(HashTableHeader));+    header_of(temp_ht)->cursize_ = n;+    header_of(temp_ht)->slots_used_ = 0;++    HashTableEntry et;+    for (i = 0; i < header_of(ht)->slots_used_; ++i) {+        set_table_at(ht, 0, i + 1);+        et = entry_at(ht, 0);+        dht_insert(temp_ht, et.ht_key, et.ht_data, NULL);+    }++    const char* temp_fname = strdup(temp_ht->fname_);+    if (!temp_fname) {+        if (err) { *err = NULL; }+        unlink(temp_ht->fname_);+        dht_free(temp_ht);+        return 0;+    }++    dht_free(temp_ht);+    const HashTableOpts opts = header_of(ht)->opts_;++    munmap(ht->data_, ht->datasize_);+    close(ht->fd_);++    rename(temp_fname, ht->fname_);++    temp_ht = dht_open(ht->fname_, opts, O_RDWR, err);+    if (!temp_ht) {+        /* err is set by dht_open */+        return 0;+    }+    free((char*)ht->fname_);+    memcpy(ht, temp_ht, sizeof(HashTable));+    assert(starting_slots == cheader_of(ht)->slots_used_);+    return cap;+}++size_t dht_size(const HashTable* ht) {+    return cheader_of(ht)->slots_used_;+}++void* dht_lookup(const HashTable* ht, const char* key) {+    int h = hash_key(key) % cheader_of(ht)->cursize_;+    int i;+    for (i = 0; i < cheader_of(ht)->cursize_; ++i) {+        HashTableEntry et = entry_at(ht, h);+        if (!et.ht_key) return NULL;+        if (!strcmp(et.ht_key, key)) return et.ht_data;+        ++h;+        if (h == cheader_of(ht)->cursize_) h = 0;+    }+    fprintf(stderr, "dht_lookup: the code should never have reached this line.\n");+    return NULL;+}++int dht_insert(HashTable* ht, const char* key, const void* data, char** err) {+    if (strlen(key) >= header_of(ht)->opts_.key_maxlen) {+        if (err) { *err = strdup("Key is too long"); }+        return -EINVAL;+    }+    /* Max load is 50% */+    if (cheader_of(ht)->cursize_ / 2 <= cheader_of(ht)->slots_used_) {+        if (!dht_reserve(ht, cheader_of(ht)->slots_used_ + 1, err)) return -ENOMEM;+    }+    int h = hash_key(key) % cheader_of(ht)->cursize_;+    while (1) {+        HashTableEntry et = entry_at(ht, h);+        if (entry_empty(et)) break;+        if (!strcmp(et.ht_key, key)) {+            return 0;+        }+        ++h;+        if (h == cheader_of(ht)->cursize_) {+            h = 0;+        }+    }+    set_table_at(ht, h, header_of(ht)->slots_used_ + 1);+    ++header_of(ht)->slots_used_;+    HashTableEntry et = entry_at(ht, h);++    strcpy((char*)et.ht_key, key);+    memcpy(et.ht_data, data, cheader_of(ht)->opts_.object_datalen);++    return 1;+}+