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 TxSeq tx where
-
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
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 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 # | |
Ord TicketNo Source # | |
Defined in Ouroboros.Consensus.Mempool.TxSeq |
|
Show TicketNo Source # | |
NoThunks TicketNo 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
Foldable TxSeq Source # | |
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 # |
|
Show tx => Show ( TxSeq tx) Source # | |
NoThunks tx => NoThunks ( TxSeq tx) 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.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
))))
|
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.
toMempoolSize :: TxSeq tx -> MempoolSize Source #
\( O(1) \)
. Return the
MempoolSize
of the given
TxSeq
.
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.