packages feed

haskoin-store-1.16.0: src/Haskoin/Store/Database/Table.hs

-- |
-- Module      : Haskoin.Store.Database.Table
-- Copyright   : (c) Haskoin Developers
-- License     : MIT
-- Maintainer  : jprupp@protonmail.ch
-- Stability   : experimental
-- Portability : POSIX
--
-- The hash tables of a batch of writes ("Haskoin.Store.Database.Writer"):
-- mutable tables whose keys are hashed quickly.
--
-- = Why not the 'Hashable' instances of the keys
--
-- A batch keeps its changes in hash tables keyed by outputs, addresses and
-- pairs of them, and importing a block makes some forty insertions and
-- lookups for each transaction. The 'Hashable' instances of those types are
-- derived generically, which walks the structure of the type for each
-- hash: 0.4 microseconds for an output or an address, 0.8 for an address
-- with a transaction, where hashing the 32 bytes of a transaction hash
-- takes 0.03. An insertion under an address and a transaction took 3.4
-- microseconds, and the tables were most of the time of a block once its
-- reads were out of the way.
--
-- Every one of those keys holds a hash already: of a transaction, a public
-- key or a script. Those bytes are as good as random, so 'tableHash' mixes
-- them and nothing else: the same output of two transactions, or two
-- outputs of the same address, differ in them. The insertion above takes
-- 0.6 microseconds with it.
--
-- The alternatives were faster instances in haskoin-core, which is where
-- they belong and would serve everyone, but is another package with its
-- own releases; and tables keyed by the serialised keys, which hash fast
-- too, but serialising a key costs more than this hash, and has to be done
-- for lookups as well.
module Haskoin.Store.Database.Table
  ( Table,
    TableKey (..),
    new,
    lookup,
    insert,
    delete,
    toList,
  )
where

import Data.Coerce (coerce)
import Data.HashTable.IO qualified as H
import Data.Hashable (Hashable (..))
import Data.Word (Word32)
import Haskoin (Address (..), BlockHash, OutPoint (..), TxHash)
import Haskoin.Store.Data (BlockRef, TxRef (..))
import Prelude hiding (lookup)

-- | A mutable hash table, for one thread at a time.
newtype Table k v = Table (H.BasicHashTable (Key k) v)

-- | A key as the table holds it, hashed with 'tableHash'.
newtype Key k = Key k
  deriving (Eq)

instance (TableKey k) => Hashable (Key k) where
  hashWithSalt salt (Key k) = tableHash salt k

-- | What can be the key of a t'Table'.
class (Eq k) => TableKey k where
  -- | Mix a key into a salt. Two keys that are equal must give the same
  -- result; two that are not should differ in what is mixed, though they
  -- need not: the table compares the keys themselves in the end.
  tableHash :: Int -> k -> Int

instance TableKey TxHash where
  tableHash = hashWithSalt

instance TableKey BlockHash where
  tableHash = hashWithSalt

instance TableKey Word32 where
  tableHash = hashWithSalt

-- | The hash of the transaction and the index of the output.
instance TableKey OutPoint where
  tableHash salt p = salt `hashWithSalt` p.hash `hashWithSalt` p.index

-- | The hash that the address holds, for the usual kinds of address, each
-- with a salt of its own, so that a script and a key with the same hash
-- stay apart. The others are hashed as their type says.
instance TableKey Address where
  tableHash salt = \case
    PubKeyAddress h -> hashWithSalt salt h
    ScriptAddress h -> hashWithSalt (salt + 1) h
    WitnessPubKeyAddress h -> hashWithSalt (salt + 2) h
    WitnessScriptAddress h -> hashWithSalt (salt + 3) h
    a -> hashWithSalt (salt + 4) a

-- | A group of outputs of a transaction: its hash and the number of the
-- group.
instance TableKey (TxHash, Word32) where
  tableHash salt (h, g) = salt `hashWithSalt` h `hashWithSalt` g

-- | The address and the hash of the transaction. The position of the
-- transaction is left out: a transaction has one at a time.
instance TableKey (Address, TxRef) where
  tableHash salt (a, t) = tableHash salt a `hashWithSalt` t.txid

-- | The address and the output, without the position of its transaction.
instance TableKey (Address, BlockRef, OutPoint) where
  tableHash salt (a, _, p) = tableHash (tableHash salt a) p

-- | An empty table.
new :: IO (Table k v)
new = Table <$> H.new

-- | The value of a key, if the table has it.
lookup :: (TableKey k) => Table k v -> k -> IO (Maybe v)
lookup (Table t) k = H.lookup t (Key k)

-- | Set the value of a key.
insert :: (TableKey k) => Table k v -> k -> v -> IO ()
insert (Table t) k = H.insert t (Key k)

-- | Take a key out of the table, if it is there.
delete :: (TableKey k) => Table k v -> k -> IO ()
delete (Table t) k = H.delete t (Key k)

-- | Every key with its value, in no particular order.
toList :: forall k v. (TableKey k) => Table k v -> IO [(k, v)]
toList (Table t) = coerce <$> (H.toList t :: IO [(Key k, v)])