| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Ouroboros.Consensus.Mempool.TxSeq
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 TxTicket tx = TxTicket {
- txTicketTx :: !tx
- txTicketNo :: !TicketNo
- txTicketTxSizeInBytes :: !TxSizeInBytes
- data TxSeq tx where
- fromList :: [TxTicket tx] -> TxSeq tx
- toList :: TxSeq tx -> [TxTicket tx]
- toTuples :: TxSeq tx -> [(tx, TicketNo)]
- lookupByTicketNo :: TxSeq tx -> TicketNo -> Maybe tx
- splitAfterTicketNo :: TxSeq tx -> TicketNo -> (TxSeq tx, TxSeq tx)
- splitAfterTxSize :: TxSeq tx -> TxSizeInBytes -> (TxSeq tx, TxSeq tx)
- zeroTicketNo :: TicketNo
- toMempoolSize :: TxSeq tx -> MempoolSize
- splitAfterTxSizeSpec :: TxSeq tx -> TxSizeInBytes -> (TxSeq tx, TxSeq tx)
Documentation
We allocate each transaction a (monotonically increasing) ticket number as it enters the mempool.
Instances
| Bounded TicketNo Source # | |
| Enum TicketNo Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq | |
| Eq TicketNo Source # | |
| Ord TicketNo Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq | |
| Show TicketNo Source # | |
| NoThunks TicketNo Source # | |
We associate transactions in the mempool with their ticket number and size in bytes.
Constructors
| TxTicket | |
Fields
| |
Instances
| Eq tx => Eq (TxTicket tx) Source # | |
| Show tx => Show (TxTicket tx) Source # | |
| Generic (TxTicket tx) Source # | |
| NoThunks tx => NoThunks (TxTicket tx) Source # | |
| type Rep (TxTicket tx) Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq type Rep (TxTicket tx) = D1 ('MetaData "TxTicket" "Ouroboros.Consensus.Mempool.TxSeq" "ouroboros-consensus-0.1.0.0-GfJNvFcM6lj2s5utKAUPEp" '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)))) | |
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
| Foldable TxSeq Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq Methods fold :: Monoid m => TxSeq m -> m # foldMap :: Monoid m => (a -> m) -> TxSeq a -> m # foldMap' :: Monoid m => (a -> m) -> TxSeq a -> m # foldr :: (a -> b -> b) -> b -> TxSeq a -> b # foldr' :: (a -> b -> b) -> b -> TxSeq a -> b # foldl :: (b -> a -> b) -> b -> TxSeq a -> b # foldl' :: (b -> a -> b) -> b -> TxSeq a -> b # foldr1 :: (a -> a -> a) -> TxSeq a -> a # foldl1 :: (a -> a -> a) -> TxSeq a -> a # elem :: Eq a => a -> TxSeq a -> Bool # maximum :: Ord a => TxSeq a -> a # minimum :: Ord a => TxSeq a -> a # | |
| Show tx => Show (TxSeq tx) Source # | |
| NoThunks tx => NoThunks (TxSeq tx) Source # | |
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.
zeroTicketNo :: TicketNo Source #
The transaction ticket number from which our counter starts.
toMempoolSize :: TxSeq tx -> MempoolSize Source #
\( O(1) \). Return the MempoolSize of the given TxSeq.
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.