Safe Haskell	None
Language	Haskell2010

Ouroboros.Consensus.Mempool.TxSeq

Contents

Reference implementations for testing

Description

Intended for qualified import.

import           Ouroboros.Consensus.Mempool.TxSeq (TxSeq (..))
import qualified Ouroboros.Consensus.Mempool.TxSeq as TxSeq

Synopsis

newtype TicketNo = TicketNo Word64
data TxSeq tx where
- pattern Empty :: TxSeq tx
- pattern (:>) :: TxSeq tx -> TxTicket tx -> TxSeq tx
- pattern (:<) :: TxTicket tx -> TxSeq tx -> TxSeq tx
data TxTicket tx = TxTicket {
- txTicketTx :: !tx
- txTicketNo :: ! TicketNo
- txTicketTxSizeInBytes :: ! TxSizeInBytes
}
fromList :: [ TxTicket tx] -> TxSeq tx
lookupByTicketNo :: TxSeq tx -> TicketNo -> Maybe tx
splitAfterTicketNo :: TxSeq tx -> TicketNo -> ( TxSeq tx, TxSeq tx)
splitAfterTxSize :: TxSeq tx -> TxSizeInBytes -> ( TxSeq tx, TxSeq tx)
toList :: TxSeq tx -> [ TxTicket tx]
toMempoolSize :: TxSeq tx -> MempoolSize
toTuples :: TxSeq tx -> [(tx, TicketNo )]
zeroTicketNo :: TicketNo
splitAfterTxSizeSpec :: TxSeq tx -> TxSizeInBytes -> ( TxSeq tx, TxSeq tx)

Documentation

newtype TicketNo Source #

We allocate each transaction a (monotonically increasing) ticket number as it enters the mempool.

Constructors

TicketNo Word64

Instances

Instances details

Bounded TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods minBound :: TicketNo Source # maxBound :: TicketNo Source #
Enum TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods succ :: TicketNo -> TicketNo Source # pred :: TicketNo -> TicketNo Source # toEnum :: Int -> TicketNo Source # fromEnum :: TicketNo -> Int Source # enumFrom :: TicketNo -> [ TicketNo ] Source # enumFromThen :: TicketNo -> TicketNo -> [ TicketNo ] Source # enumFromTo :: TicketNo -> TicketNo -> [ TicketNo ] Source # enumFromThenTo :: TicketNo -> TicketNo -> TicketNo -> [ TicketNo ] Source #
Eq TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods (==) :: TicketNo -> TicketNo -> Bool Source # (/=) :: TicketNo -> TicketNo -> Bool Source #
Ord TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods compare :: TicketNo -> TicketNo -> Ordering Source # (<) :: TicketNo -> TicketNo -> Bool Source # (<=) :: TicketNo -> TicketNo -> Bool Source # (>) :: TicketNo -> TicketNo -> Bool Source # (>=) :: TicketNo -> TicketNo -> Bool Source # max :: TicketNo -> TicketNo -> TicketNo Source # min :: TicketNo -> TicketNo -> TicketNo Source #
Show TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods showsPrec :: Int -> TicketNo -> ShowS Source # show :: TicketNo -> String Source # showList :: [ TicketNo ] -> ShowS Source #
NoThunks TicketNo Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods noThunks :: Context -> TicketNo -> IO ( Maybe ThunkInfo ) Source # wNoThunks :: Context -> TicketNo -> IO ( Maybe ThunkInfo ) Source # showTypeOf :: Proxy TicketNo -> String Source #

data TxSeq tx where Source #

The mempool is a sequence of transactions with their ticket numbers and size in bytes.

Transactions are allocated monotonically increasing ticket numbers as they are appended to the mempool sequence. Transactions can be removed from any position, not just the front.

The sequence is thus ordered by the ticket numbers. We can use the ticket numbers as a compact representation for a "reader" location in the sequence. If a reader knows it has seen all txs with a lower ticket number then it is only interested in transactions with higher ticket numbers.

The mempool sequence is represented by a fingertree. We use a fingertree measure to allow not just normal sequence operations but also efficient splitting and indexing by the ticket number.

Bundled Patterns

pattern Empty :: TxSeq tx

An empty mempool sequence.

pattern (:>) :: TxSeq tx -> TxTicket tx -> TxSeq tx infixl 5

\( O(1) \) . Access or add a tx at the back of the mempool sequence.

New txs are always added at the back.

pattern (:<) :: TxTicket tx -> TxSeq tx -> TxSeq tx infixl 5

\( O(1) \) . Access a tx at the front of the mempool sequence.

Note that we never add txs at the front. We access txs from front to back when forwarding txs to other peers, or when adding txs to blocks.

Instances

Instances details

Foldable TxSeq Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods fold :: Monoid m => TxSeq m -> m Source # foldMap :: Monoid m => (a -> m) -> TxSeq a -> m Source # foldMap' :: Monoid m => (a -> m) -> TxSeq a -> m Source # foldr :: (a -> b -> b) -> b -> TxSeq a -> b Source # foldr' :: (a -> b -> b) -> b -> TxSeq a -> b Source # foldl :: (b -> a -> b) -> b -> TxSeq a -> b Source # foldl' :: (b -> a -> b) -> b -> TxSeq a -> b Source # foldr1 :: (a -> a -> a) -> TxSeq a -> a Source # foldl1 :: (a -> a -> a) -> TxSeq a -> a Source # toList :: TxSeq a -> [a] Source # null :: TxSeq a -> Bool Source # length :: TxSeq a -> Int Source # elem :: Eq a => a -> TxSeq a -> Bool Source # maximum :: Ord a => TxSeq a -> a Source # minimum :: Ord a => TxSeq a -> a Source # sum :: Num a => TxSeq a -> a Source # product :: Num a => TxSeq a -> a Source #
Show tx => Show ( TxSeq tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods showsPrec :: Int -> TxSeq tx -> ShowS Source # show :: TxSeq tx -> String Source # showList :: [ TxSeq tx] -> ShowS Source #
NoThunks tx => NoThunks ( TxSeq tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods noThunks :: Context -> TxSeq tx -> IO ( Maybe ThunkInfo ) Source # wNoThunks :: Context -> TxSeq tx -> IO ( Maybe ThunkInfo ) Source # showTypeOf :: Proxy ( TxSeq tx) -> String Source #

data TxTicket tx Source #

We associate transactions in the mempool with their ticket number and size in bytes.

Constructors

TxTicket
Fields txTicketTx :: !tx The transaction associated with this ticket. txTicketNo :: ! TicketNo The ticket number. txTicketTxSizeInBytes :: ! TxSizeInBytes The byte size of the transaction ( `txTicketTx` ) associated with this ticket.

Instances

Instances details

Eq tx => Eq ( TxTicket tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods (==) :: TxTicket tx -> TxTicket tx -> Bool Source # (/=) :: TxTicket tx -> TxTicket tx -> Bool Source #
Show tx => Show ( TxTicket tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods showsPrec :: Int -> TxTicket tx -> ShowS Source # show :: TxTicket tx -> String Source # showList :: [ TxTicket tx] -> ShowS Source #
Generic ( TxTicket tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Associated Types type Rep ( TxTicket tx) :: Type -> Type Source # Methods from :: TxTicket tx -> Rep ( TxTicket tx) x Source # to :: Rep ( TxTicket tx) x -> TxTicket tx Source #
NoThunks tx => NoThunks ( TxTicket tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq Methods noThunks :: Context -> TxTicket tx -> IO ( Maybe ThunkInfo ) Source # wNoThunks :: Context -> TxTicket tx -> IO ( Maybe ThunkInfo ) Source # showTypeOf :: Proxy ( TxTicket tx) -> String Source #
type Rep ( TxTicket tx) Source #
Instance details Defined in Ouroboros.Consensus.Mempool.TxSeq type Rep ( TxTicket tx) = D1 (' MetaData "TxTicket" "Ouroboros.Consensus.Mempool.TxSeq" "ouroboros-consensus-0.1.0.1-DT4Cvwf63DZKctsEvaJqCU" ' False ) ( C1 (' MetaCons "TxTicket" ' PrefixI ' True ) ( S1 (' MetaSel (' Just "txTicketTx") ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 tx) :: ( S1 (' MetaSel (' Just "txTicketNo") ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 TicketNo ) :: S1 (' MetaSel (' Just "txTicketTxSizeInBytes") ' NoSourceUnpackedness ' SourceStrict ' DecidedStrict ) ( Rec0 TxSizeInBytes ))))

fromList :: [ TxTicket tx] -> TxSeq tx Source #

Given a list of TxTicket s, construct a TxSeq .

lookupByTicketNo :: TxSeq tx -> TicketNo -> Maybe tx Source #

\( O(\log(n)) \) . Look up a transaction in the sequence by its TicketNo .

splitAfterTicketNo :: TxSeq tx -> TicketNo -> ( TxSeq tx, TxSeq tx) Source #

\( O(\log(n)) \) . Split the sequence of transactions into two parts based on the given TicketNo . The first part has transactions with tickets less than or equal to the given ticket, and the second part has transactions with tickets strictly greater than the given ticket.

splitAfterTxSize :: TxSeq tx -> TxSizeInBytes -> ( TxSeq tx, TxSeq tx) Source #

\( O(\log(n)) \) . Split the sequence of transactions into two parts based on the given TxSizeInBytes . The first part has transactions whose summed TxSizeInBytes is less than or equal to the given TxSizeInBytes , and the second part has the remaining transactions in the sequence.

toList :: TxSeq tx -> [ TxTicket tx] Source #

Convert a TxSeq to a list of TxTicket s.

toMempoolSize :: TxSeq tx -> MempoolSize Source #

\( O(1) \) . Return the MempoolSize of the given TxSeq .

toTuples :: TxSeq tx -> [(tx, TicketNo )] Source #

Convert a TxSeq to a list of pairs of transactions and their associated TicketNo s.

zeroTicketNo :: TicketNo Source #

The transaction ticket number from which our counter starts.

Reference implementations for testing

splitAfterTxSizeSpec :: TxSeq tx -> TxSizeInBytes -> ( TxSeq tx, TxSeq tx) Source #

\( O(n) \) . Specification of splitAfterTxSize .

Use splitAfterTxSize as it should be faster.

This function is used to verify whether splitAfterTxSize behaves as expected.