ouroboros-consensus-0.1.0.2: Consensus layer for the Ouroboros blockchain protocol
Safe HaskellNone
LanguageHaskell2010

Ouroboros.Consensus.Mempool.TxSeq

Description

Intended for qualified import.

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

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

Enum TicketNo Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

Eq TicketNo Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

Ord TicketNo Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

Show TicketNo Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

NoThunks TicketNo Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

Methods

noThunks ∷ Context → TicketNoIO (Maybe ThunkInfo) #

wNoThunks ∷ Context → TicketNoIO (Maybe ThunkInfo) #

showTypeOfProxy TicketNoString #

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 EmptyTxSeq 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

foldMonoid m ⇒ TxSeq m → m Source #

foldMapMonoid 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 #

toListTxSeq a → [a] Source #

nullTxSeq a → Bool Source #

lengthTxSeq a → Int Source #

elemEq a ⇒ a → TxSeq a → Bool Source #

maximumOrd a ⇒ TxSeq a → a Source #

minimumOrd a ⇒ TxSeq a → a Source #

sumNum a ⇒ TxSeq a → a Source #

productNum a ⇒ TxSeq a → a Source #

Show tx ⇒ Show (TxSeq tx) Source # 
Instance details

Defined in Ouroboros.Consensus.Mempool.TxSeq

Methods

showsPrecIntTxSeq tx → ShowS Source #

showTxSeq 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) #

wNoThunks ∷ Context → TxSeq tx → IO (Maybe ThunkInfo) #

showTypeOfProxy (TxSeq tx) → String #

data TxTicket tx Source #

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

Constructors

TxTicket 

Fields

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

showsPrecIntTxTicket tx → ShowS Source #

showTxTicket 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) ∷ TypeType Source #

Methods

fromTxTicket tx → Rep (TxTicket tx) x Source #

toRep (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) #

wNoThunks ∷ Context → TxTicket tx → IO (Maybe ThunkInfo) #

showTypeOfProxy (TxTicket tx) → String #

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.2-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 "txTicketTxSizeInBytes") 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 TxSizeInBytes))))

fromList ∷ [TxTicket tx] → TxSeq tx Source #

Given a list of TxTickets, construct a TxSeq.

lookupByTicketNoTxSeq tx → TicketNoMaybe tx Source #

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

splitAfterTicketNoTxSeq 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.

splitAfterTxSizeTxSeq 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.

toListTxSeq tx → [TxTicket tx] Source #

Convert a TxSeq to a list of TxTickets.

toMempoolSizeTxSeq tx → MempoolSize Source #

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

toTuplesTxSeq tx → [(tx, TicketNo)] Source #

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

zeroTicketNoTicketNo Source #

The transaction ticket number from which our counter starts.

Reference implementations for testing

splitAfterTxSizeSpecTxSeq 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.