packages feed

diskhash 0.0.1.2 → 0.0.2.1

raw patch · 6 files changed

+123/−39 lines, 6 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

ChangeLog view
@@ -1,3 +1,12 @@+Version 0.0.2.1 2017-10-12 by luispedro+	* Export reserve() in Python interface++Version 0.0.2.0 2017-10-05 by luispedro+	* Python improvement: support generic types through struct+	* Do not crash when attempting to write to RO tables+	* More flexible option checking+	* Better error messages+ Version 0.0.1.2 2017-06-27 by luispedro 	* Fix cabal release: include C header files in extra-source-files
README.md view
@@ -4,21 +4,26 @@ [![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](https://opensource.org/licenses/MIT)  -A simple disk-based hash table.+A simple disk-based hash table (i.e., persistent hash table). +It is a hashtable implemented on memory-mapped disk, so that it can be loaded+with a single `mmap()` system call and used in memory directly (being as fast+as an in-memory hashtable once it is loaded from disk).+ The code is in C, wrappers are provided for Python, Haskell, and C++. The-wrappers follow similar APIs with variations to accomodate the language+wrappers follow similar APIs with variations to accommodate 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).+created in C from Haskell, modify it within your Haskell code, and later 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.+top of read-only files or using multiple threads (and different processes will+share the memory: the operating system does that for you). Writing or modifying+values is, however, not thread-safe.  ## Examples @@ -88,13 +93,14 @@  ### 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's interface is based on the [struct+module](https://docs.python.org/3/library/struct.html). For example, `'ll'`+refers to a pair of 64-bit ints (_longs_):  ```python import diskhash-tb = diskhash.Str2int("testing.dht", 15)-tb.insert("key", 9)+tb = diskhash.StructHash("testing.dht", 15, 'll', 'rw')+tb.insert("key", 1, 2) print(tb.lookup("key")) ``` @@ -135,11 +141,12 @@ } ``` -## Statibility+## Stability  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 is versioned (the-magic string encodes its version, so changes can be detected).+magic string encodes its version, so changes can be detected and you will get+an error message in the future rather than some silent misbehaviour.  [Automated unit testing](https://travis-ci.org/luispedro/diskhash) ensures that basic mistakes will not go uncaught.@@ -155,6 +162,11 @@   "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.++- The algorithm is a rather naïve implementation of linear addression. It would+  not be hard to switch to [robin hood+  hashing](https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/)+  and this may indeed happen in the near future.  License: MIT
diskhash.cabal view
@@ -1,5 +1,5 @@ name:               diskhash-version:            0.0.1.2+version:            0.0.2.1 synopsis:           Disk-based hash table description:        Disk-based hash table category:           Data@@ -20,8 +20,8 @@   Include-dirs: src/   ghc-options: -Wall   build-depends:-    base > 4 && < 5,-    bytestring+    base > 4.8 && < 5,+    bytestring == 0.10.*  Test-Suite diskhashtest   default-language: Haskell2010@@ -32,8 +32,8 @@   hs-source-dirs: haskell/   include-dirs: src/   build-depends:-    base > 4 && < 5,-    bytestring,+    base > 4.8 && < 5,+    bytestring == 0.10.*,     directory,     diskhash,     HUnit,
haskell/Data/DiskHash.hs view
@@ -1,4 +1,20 @@ {-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}+{-|++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 the 'htOpenRO' call, naturally).+Using read-write hashtables with more than one thread is undefined behaviour,+but the read-only variant is perfectly thread safe.++All data structures are strict (naturally: they write to disk).++The Haskell API can be used to access diskhashes created from other languages+as long as the types are compatible.+-}+ module Data.DiskHash     ( DiskHashRO     , DiskHashRW@@ -25,17 +41,12 @@ 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 ()++-- | Represents a read-only diskhash storing type 'a' newtype DiskHashRO a = DiskHashRO HashTable_t++-- | Represents a read-write diskhash storing type 'a' newtype DiskHashRW a = DiskHashRW HashTable_t  foreign import ccall "dht_open2" c_dht_open2:: CString -> CInt -> CInt -> CInt -> Ptr CString -> IO (Ptr ())@@ -58,12 +69,25 @@             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 :: forall a. (Storable a) => FilePath+                                        -- ^ file path+                                        -> Int+                                        -- ^ maximum key size+                                        -> 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)+--+-- The 'maxk' argument can be 0, in which case the value of the maximum key+-- will be taken from the disk file. If not zero, then it is checked against+-- the value on disk and an exception is raised if there is  a mismatch.+htOpenRO :: forall a. (Storable a) => FilePath+                                        -- ^ file path+                                        -> Int+                                        -- ^ maximum key size+                                        -> 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@@ -81,7 +105,11 @@ -- | 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 :: (Storable a) => FilePath+                                    -- ^ file path+                                    -> Int+                                    -- ^ maximum key size+                                    -> (DiskHashRW a -> IO b) -> IO b withDiskHashRW fp s act = do     ht@(DiskHashRW ht') <- htOpenRW fp s     r <- act ht@@ -102,6 +130,10 @@ -- -- Returns whether an insertion took place (if an object with that key already -- exists, no insertion is made).+--+-- This operation can fail (throwing an exception) if space could not be+-- allocated. You can pre-allocate space using 'htReserve'.+-- htInsert :: (Storable a) => B.ByteString                             -- ^ key                             -> a@@ -128,7 +160,12 @@                                 errmsg <- getError err                                 throwIO $ userError ("Unexpected return from dht_insert: " ++ errmsg) -- | Lookup by key-htLookupRW :: (Storable a) => B.ByteString -> DiskHashRW a -> IO (Maybe a)+--+-- This is in the IO Monad to ensure ordering of operations.+htLookupRW :: (Storable a) => B.ByteString+                                    -- ^ key+                                    -> DiskHashRW a+                                    -> IO (Maybe a) htLookupRW key (DiskHashRW ht) =     withForeignPtr ht $ \ht' ->         B.useAsCString key $ \key' -> do@@ -138,6 +175,8 @@                 else Just <$> peek (castPtr r)  -- | Lookup by key+--+-- This is a pure operation htLookupRO :: (Storable a) => B.ByteString -> DiskHashRO a -> Maybe a htLookupRO key (DiskHashRO ht) = unsafeDupablePerformIO (htLookupRW key (DiskHashRW ht)) @@ -155,6 +194,8 @@                     return True  -- | Reserve space in the hash table+--+-- Reserving space can ensure that any subsequent 'htInsert' calls will not fail. -- -- If the operation fails, an exception is raised htReserve :: (Storable a) => Int -> DiskHashRW a -> IO Int
src/diskhash.c view
@@ -15,6 +15,10 @@ #include "diskhash.h" #include "primes.h" +enum {+    HT_FLAG_CAN_WRITE = 1,+};+ typedef struct HashTableHeader {     char magic[16];     HashTableOpts opts_;@@ -176,10 +180,12 @@             return NULL;         }     }+    rp->flags_ = 0;     const int prot = (flags == O_RDONLY) ?                                 PROT_READ                                 : PROT_READ|PROT_WRITE;-    rp->data_ = mmap(NULL, +    if (prot & PROT_WRITE) rp->flags_ |= HT_FLAG_CAN_WRITE;+    rp->data_ = mmap(NULL,             rp->datasize_,             prot,             MAP_SHARED,@@ -208,9 +214,9 @@         }         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."); }+    } else if ((header_of(rp)->opts_.key_maxlen != opts.key_maxlen && opts.key_maxlen != 0)+                || (header_of(rp)->opts_.object_datalen != opts.object_datalen && opts.object_datalen != 0)) {+        if (err) { *err = strdup("Options mismatch (diskhash table on disk was not created with the same options used to open it)."); }         dht_free(rp);         return 0;     }@@ -250,6 +256,10 @@ }  size_t dht_reserve(HashTable* ht, size_t cap, char** err) {+    if (!(ht->flags_ & HT_FLAG_CAN_WRITE)) {+        if (err) { *err = strdup("Hash table is read-only. Cannot call dht_reserve."); }+        return -EACCES;+    }     if (header_of(ht)->cursize_ / 2 > cap) {         return header_of(ht)->cursize_ / 2;     }@@ -281,12 +291,13 @@         return 0;     }     temp_ht->datasize_ = total_size;-    temp_ht->data_ = mmap(NULL, +    temp_ht->data_ = mmap(NULL,             temp_ht->datasize_,             PROT_READ|PROT_WRITE,             MAP_SHARED,             temp_ht->fd_,             0);+    temp_ht->flags_ = ht->flags_;     if (temp_ht->data_ == MAP_FAILED) {         if (err) {             const int errorbufsize = 512;@@ -358,6 +369,10 @@ }  int dht_insert(HashTable* ht, const char* key, const void* data, char** err) {+    if (!(ht->flags_ & HT_FLAG_CAN_WRITE)) {+        if (err) { *err = strdup("Hash table is read-only. Cannot insert."); }+        return -EACCES;+    }     if (strlen(key) >= header_of(ht)->opts_.key_maxlen) {         if (err) { *err = strdup("Key is too long"); }         return -EINVAL;
src/diskhash.h view
@@ -28,6 +28,7 @@     const char* fname_;     void* data_;     size_t datasize_;+    int flags_; } HashTable;  @@ -59,8 +60,10 @@  *  * When opening an existing disk table, you can pass `{ 0, 0 }` (the return  * value of `dht_zero_opts()`) as the options, in which case the values will be- * taken from the table on disk. If you do pass values, they are checked- * against the values on disk and it is an error if there is a mismatch.+ * taken from the table on disk. If you do pass values > 0, they are checked+ * against the values on disk and it is an error if there is a mismatch+ * (passing zero to one of the option fields and not the other is supported:+ * only the non-zero field is checked).  *  * The last argument is an error output argument. If it is set to a non-NULL  * value, then the memory must be released with free(). Passing NULL is valid@@ -105,7 +108,8 @@  *         0 if the key was already present in the table. The hash table was  *         not modified.  *         -EINVAL : key is too long- *	   -ENOMEM : dht_reserve failed.+ *         -EACCES : attempted to insert into a read-only table.+ *	       -ENOMEM : dht_reserve failed.  *  * The last argument is an error output argument. If it is set to a non-NULL  * value, then the memory must be released with free(). Passing NULL is valid@@ -133,6 +137,9 @@  * The last argument is an error output argument. If it is set to a non-NULL  * value, then the memory must be released with free(). Passing NULL is valid  * (and no error message will be produced).+ *+ * Attempting to call this function on a read-only table will fail (return+ * value: -EACCES).  */ size_t dht_reserve(HashTable*, size_t capacity, char** err);