hashtables.cabal

Cabal-Version: 2.2
Name:                hashtables
Version:             1.3.1
Synopsis:            Mutable hash tables in the ST monad
Homepage:            http://github.com/gregorycollins/hashtables
License:             BSD-3-Clause
License-file:        LICENSE
Author:              Gregory Collins
Maintainer:          greg@gregorycollins.net, mgoremeier@gmail.com, erikd@mega-nerd.com
Copyright:           (c) 2011-2014, Google, Inc., 2016-present contributors
Category:            Data
Build-type:          Simple


tested-with:
  GHC == 9.6.1
  GHC == 9.4.4
  GHC == 9.2.7
  GHC == 9.0.2
  GHC == 8.10.7
  GHC == 8.8.4
  GHC == 8.6.5
  GHC == 8.4.4
  GHC == 8.2.2
  GHC == 8.0.2
  GHC == 7.10.3
  GHC == 7.8.4

Description:
  This package provides a couple of different implementations of mutable hash
  tables in the ST monad, as well as a typeclass abstracting their common
  operations, and a set of wrappers to use the hash tables in the IO monad.
  .
  /QUICK START/: documentation for the hash table operations is provided in the
  "Data.HashTable.Class" module, and the IO wrappers (which most users will
  probably prefer) are located in the "Data.HashTable.IO" module.
  .
  This package currently contains three hash table implementations:
  .
    1. "Data.HashTable.ST.Cuckoo" contains an implementation of \"cuckoo
       hashing\" as introduced by Pagh and Rodler in 2001 (see
       <http://en.wikipedia.org/wiki/Cuckoo_hashing>). Cuckoo hashing has
       worst-case /O(1)/ lookups and can reach a high \"load factor\", in which
       the table can perform acceptably well even when approaching 90% full.
       Randomized testing shows this implementation of cuckoo hashing to be
       slightly faster on insert and slightly slower on lookup than
       "Data.HashTable.ST.Basic", while being more space efficient by about a
       half-word per key-value mapping. Cuckoo hashing, like the basic hash
       table implementation using linear probing, can suffer from long delays
       when the table is resized.
  .
    2. "Data.HashTable.ST.Basic" contains a basic open-addressing hash table
       using linear probing as the collision strategy. On a pure speed basis it
       should currently be the fastest available Haskell hash table
       implementation for lookups, although it has a higher memory overhead
       than the other tables and can suffer from long delays when the table is
       resized because all of the elements in the table need to be rehashed.
  .
    3. "Data.HashTable.ST.Linear" contains a linear hash table (see
       <http://en.wikipedia.org/wiki/Linear_hashing>), which trades some insert
       and lookup performance for higher space efficiency and much shorter
       delays when expanding the table. In most cases, benchmarks show this
       table to be currently slightly faster than @Data.HashTable@ from the
       Haskell base library.
  .
  It is recommended to create a concrete type alias in your code when using this
  package, i.e.:
  .
  > import qualified Data.HashTable.IO as H
  >
  > type HashTable k v = H.BasicHashTable k v
  >
  > foo :: IO (HashTable Int Int)
  > foo = do
  >     ht <- H.new
  >     H.insert ht 1 1
  >     return ht
  .
  Firstly, this makes it easy to switch to a different hash table implementation,
  and secondly, using a concrete type rather than leaving your functions abstract
  in the HashTable class should allow GHC to optimize away the typeclass
  dictionaries.
  .
  This package accepts a couple of different cabal flags:
  .
    * @unsafe-tricks@, default /ON/. If this flag is enabled, we use some
      unsafe GHC-specific tricks to save indirections (namely @unsafeCoerce#@
      and @reallyUnsafePtrEquality#@. These techniques rely on assumptions
      about the behaviour of the GHC runtime system and, although they've been
      tested and should be safe under normal conditions, are slightly
      dangerous. Caveat emptor. In particular, these techniques are
      incompatible with HPC code coverage reports.
  .
    * @sse42@, default /OFF/. If this flag is enabled, we use some SSE 4.2
      instructions (see <http://en.wikipedia.org/wiki/SSE4>, first available on
      Intel Core 2 processors) to speed up cache-line searches for cuckoo
      hashing.
  .
    * @bounds-checking@, default /OFF/. If this flag is enabled, array accesses
      are bounds-checked.
  .
    * @debug@, default /OFF/. If turned on, we'll rudely spew debug output to
      stdout.
  .
    * @portable@, default /OFF/. If this flag is enabled, we use only pure
      Haskell code and try not to use unportable GHC extensions. Turning this
      flag on forces @unsafe-tricks@ and @sse42@ /OFF/.
  .
  Please send bug reports to
  <https://github.com/gregorycollins/hashtables/issues>.

Extra-Source-Files:
  README.md,
  cabal.project,
  haddock.sh,
  benchmark/hashtable-benchmark.cabal,
  benchmark/LICENSE,
  benchmark/src/Criterion/Collection/Internal/Types.hs,
  benchmark/src/Criterion/Collection/Chart.hs,
  benchmark/src/Criterion/Collection/Main.hs,
  benchmark/src/Criterion/Collection/Types.hs,
  benchmark/src/Criterion/Collection/Sample.hs,
  benchmark/src/Main.hs,
  benchmark/src/Data/Vector/Algorithms/Shuffle.hs,
  benchmark/src/Data/Benchmarks/UnorderedCollections/Distributions.hs,
  benchmark/src/Data/Benchmarks/UnorderedCollections/Types.hs,
  cbits/Makefile,
  cbits/check.c,
  cbits/defs.h,
  cbits/sse-42-check.c,
  changelog.md,
  test/compute-overhead/ComputeOverhead.hs,
  test/hashtables-test.cabal,
  test/suite/Data/HashTable/Test/Common.hs,
  test/suite/TestSuite.hs


------------------------------------------------------------------------------
Flag unsafe-tricks
  Description: turn on unsafe GHC tricks
  Default:   True

Flag bounds-checking
  Description: if on, use bounds-checking array accesses
  Default: False

Flag debug
  Description: if on, spew debugging output to stdout
  Default: False
  Manual: True

Flag detailed-profiling
  Description: add detailed profiling information to profiled build-depends
  Default: False
  Manual: True

Flag sse42
  Description: if on, use SSE 4.2 extensions to search cache lines very
               efficiently. The portable flag forces this off.
  Default: False

Flag portable
  Description: if on, use only pure Haskell code and no GHC extensions.
  Default: False


Library
  Default-Language: Haskell2010
  hs-source-dirs:    src

  if flag(sse42) && !flag(portable)
    cc-options:  -DUSE_SSE_4_2 -msse4.2
    cpp-options: -DUSE_SSE_4_2
    C-sources:   cbits/sse-42.c

  if !flag(portable) && !flag(sse42)
    C-sources:       cbits/default.c

  if !flag(portable)
    C-sources:       cbits/common.c

  Exposed-modules:   Data.HashTable.Class,
                     Data.HashTable.IO,
                     Data.HashTable.ST.Basic,
                     Data.HashTable.ST.Cuckoo,
                     Data.HashTable.ST.Linear

  Other-modules:     Data.HashTable.Internal.Array,
                     Data.HashTable.Internal.IntArray,
                     Data.HashTable.Internal.CacheLine,
                     Data.HashTable.Internal.CheapPseudoRandomBitStream,
                     Data.HashTable.Internal.UnsafeTricks,
                     Data.HashTable.Internal.Utils,
                     Data.HashTable.Internal.Linear.Bucket

  Build-depends:     base      >= 4.7 && <5,
                     hashable  >= 1.4 && < 1.5,
                     primitive,
                     vector    >= 0.7 && <0.14

  if flag(portable)
    cpp-options: -DNO_C_SEARCH -DPORTABLE

  if !flag(portable) && flag(unsafe-tricks) && impl(ghc)
    build-depends: ghc-prim
    cpp-options: -DUNSAFETRICKS

  if flag(debug)
    cpp-options: -DDEBUG

  if flag(bounds-checking)
    cpp-options: -DBOUNDS_CHECKING

  if flag(detailed-profiling)
    if impl(ghc >= 7.4.1)
     ghc-prof-options: -fprof-auto
    if impl(ghc < 7.4.1)
     ghc-prof-options: -auto-all

  if impl(ghc >= 6.12.0)
    ghc-options: -Wall -fwarn-tabs -funbox-strict-fields
                 -fno-warn-unused-do-bind
  else
    ghc-options: -Wall -fwarn-tabs -funbox-strict-fields

test-suite testsuite
  Default-Language: Haskell2010
  hs-source-dirs:    src test/suite
  main-is:           TestSuite.hs
  type: exitcode-stdio-1.0

  other-modules:
        Data.HashTable.Class
        Data.HashTable.IO
        Data.HashTable.Internal.Array
        Data.HashTable.Internal.CacheLine
        Data.HashTable.Internal.CheapPseudoRandomBitStream
        Data.HashTable.Internal.IntArray
        Data.HashTable.Internal.Linear.Bucket
        Data.HashTable.Internal.UnsafeTricks
        Data.HashTable.Internal.Utils
        Data.HashTable.ST.Basic
        Data.HashTable.ST.Cuckoo
        Data.HashTable.ST.Linear
        Data.HashTable.Test.Common

  if flag(sse42) && !flag(portable)
    cc-options:  -DUSE_SSE_4_2 -msse4.2
    cpp-options: -DUSE_SSE_4_2
    C-sources:   cbits/sse-42.c

  if !flag(portable) && !flag(sse42)
    C-sources:       cbits/default.c

  if !flag(portable)
    C-sources:       cbits/common.c

  if flag(detailed-profiling)
    ghc-prof-options:  -auto-all

  if flag(portable)
    cpp-options: -DNO_C_SEARCH -DPORTABLE

  if !flag(portable) && flag(unsafe-tricks) && impl(ghc)
    cpp-options: -DUNSAFETRICKS
    build-depends: ghc-prim

  if flag(debug)
    cpp-options: -DDEBUG

  if flag(bounds-checking)
    cpp-options: -DBOUNDS_CHECKING

  Build-depends:     base                       >= 4     && <5,
                     hashable                   >= 1.4 && < 1.5,
                     mwc-random                 >= 0.8   && <0.16,
                     primitive,
                     QuickCheck                 >= 2.3.0.2,
                     HUnit                      >= 1.2   && <2,
                     test-framework             >= 0.3.1 && <0.9,
                     test-framework-quickcheck2 >= 0.2.6 && <0.4,
                     test-framework-hunit       >= 0.2.6 && <3,
                     vector                     >= 0.7

  cpp-options: -DTESTSUITE

  if impl(ghc >= 7)
    ghc-options: -rtsopts

  if impl(ghc >= 6.12.0)
    ghc-options: -Wall -fwarn-tabs -funbox-strict-fields
                 -fno-warn-unused-do-bind -threaded
  else
    ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -threaded



source-repository head
  type:     git
  location: https://github.com/gregorycollins/hashtables.git