| Safe Haskell | Safe-Inferred |
|---|---|
| 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 TxSeq sz tx where
- data TxTicket sz tx = TxTicket {
- txTicketTx ∷ !tx
- txTicketNo ∷ !TicketNo
- txTicketSize ∷ !sz
- fromList ∷ Measure sz ⇒ [TxTicket sz tx] → TxSeq sz tx
- lookupByTicketNo ∷ Measure sz ⇒ TxSeq sz tx → TicketNo → Maybe tx
- splitAfterTicketNo ∷ Measure sz ⇒ TxSeq sz tx → TicketNo → (TxSeq sz tx, TxSeq sz tx)
- splitAfterTxSize ∷ Measure sz ⇒ TxSeq sz tx → sz → (TxSeq sz tx, TxSeq sz tx)
- toList ∷ TxSeq sz tx → [TxTicket sz tx]
- toSize ∷ Measure sz ⇒ TxSeq sz tx → sz
- toTuples ∷ HasByteSize sz ⇒ TxSeq sz tx → [(tx, TicketNo, ByteSize32)]
- zeroTicketNo ∷ TicketNo
- splitAfterTxSizeSpec ∷ ∀ sz tx. Measure sz ⇒ TxSeq sz tx → sz → (TxSeq sz tx, TxSeq sz tx)
Documentation
We allocate each transaction a (monotonically increasing) ticket number as it enters the mempool.
Instances
| Bounded TicketNo Source # | |
| Enum TicketNo Source # | |
| Show TicketNo Source # | |
| Eq TicketNo Source # | |
| Ord TicketNo Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq | |
| NoThunks TicketNo Source # | |
data TxSeq sz 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 ∷ Measure sz ⇒ TxSeq sz tx | An empty mempool sequence. |
| pattern (:>) ∷ Measure sz ⇒ TxSeq sz tx → TxTicket sz tx → TxSeq sz 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 (:<) ∷ Measure sz ⇒ TxTicket sz tx → TxSeq sz tx → TxSeq sz 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
| Measure sz ⇒ Foldable (TxSeq sz) Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq Methods fold ∷ Monoid m ⇒ TxSeq sz m → m # foldMap ∷ Monoid m ⇒ (a → m) → TxSeq sz a → m # foldMap' ∷ Monoid m ⇒ (a → m) → TxSeq sz a → m # foldr ∷ (a → b → b) → b → TxSeq sz a → b # foldr' ∷ (a → b → b) → b → TxSeq sz a → b # foldl ∷ (b → a → b) → b → TxSeq sz a → b # foldl' ∷ (b → a → b) → b → TxSeq sz a → b # foldr1 ∷ (a → a → a) → TxSeq sz a → a # foldl1 ∷ (a → a → a) → TxSeq sz a → a # elem ∷ Eq a ⇒ a → TxSeq sz a → Bool # maximum ∷ Ord a ⇒ TxSeq sz a → a # minimum ∷ Ord a ⇒ TxSeq sz a → a # | |
| (Show tx, Show sz) ⇒ Show (TxSeq sz tx) Source # | |
| (NoThunks tx, NoThunks sz) ⇒ NoThunks (TxSeq sz tx) Source # | |
We associate transactions in the mempool with their ticket number and size in bytes.
Constructors
| TxTicket | |
Fields
| |
Instances
| Generic (TxTicket sz tx) Source # | |
| (Show tx, Show sz) ⇒ Show (TxTicket sz tx) Source # | |
| (Eq tx, Eq sz) ⇒ Eq (TxTicket sz tx) Source # | |
| (NoThunks tx, NoThunks sz) ⇒ NoThunks (TxTicket sz tx) Source # | |
| type Rep (TxTicket sz tx) Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq type Rep (TxTicket sz tx) = D1 ('MetaData "TxTicket" "Ouroboros.Consensus.Mempool.TxSeq" "ouroboros-consensus-0.21.0.0-inplace" '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 "txTicketSize") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 sz)))) | |
lookupByTicketNo ∷ Measure sz ⇒ TxSeq sz tx → TicketNo → Maybe tx Source #
\( O(\log(n)) \). Look up a transaction in the sequence by its TicketNo.
splitAfterTicketNo ∷ Measure sz ⇒ TxSeq sz tx → TicketNo → (TxSeq sz tx, TxSeq sz 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 ∷ Measure sz ⇒ TxSeq sz tx → sz → (TxSeq sz tx, TxSeq sz tx) Source #
\( O(\log(n)) \). Split the sequence of transactions into two parts based
on the given sz. The first part has transactions whose summed sz is less
than or equal to the given sz, and the second part has the remaining
transactions in the sequence.
toSize ∷ Measure sz ⇒ TxSeq sz tx → sz Source #
\( O(1) \). Return the total size of the given TxSeq.
toTuples ∷ HasByteSize sz ⇒ TxSeq sz tx → [(tx, TicketNo, ByteSize32)] Source #
Convert a TxSeq to a list of pairs of transactions and their
associated TicketNos and ByteSize32s.
zeroTicketNo ∷ TicketNo Source #
The transaction ticket number from which our counter starts.
Reference implementations for testing
splitAfterTxSizeSpec ∷ ∀ sz tx. Measure sz ⇒ TxSeq sz tx → sz → (TxSeq sz tx, TxSeq sz 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.