Documentation
¶
Index ¶
- Constants
- Variables
- type PooledSkiplist
- func (sl *PooledSkiplist) Capacity() int32
- func (sl *PooledSkiplist) Contains(price udecimal.Decimal) bool
- func (sl *PooledSkiplist) Count() int32
- func (sl *PooledSkiplist) Delete(price udecimal.Decimal) bool
- func (sl *PooledSkiplist) DeleteMin() (udecimal.Decimal, bool)
- func (sl *PooledSkiplist) InOrderSlice() []udecimal.Decimal
- func (sl *PooledSkiplist) Insert(price udecimal.Decimal) (bool, error)
- func (sl *PooledSkiplist) Iterator() *SkiplistIterator
- func (sl *PooledSkiplist) Min() (udecimal.Decimal, bool)
- func (sl *PooledSkiplist) MustInsert(price udecimal.Decimal) bool
- type PriceLevel
- type PriceLevelTree
- func (t *PriceLevelTree) Contains(price udecimal.Decimal) bool
- func (t *PriceLevelTree) Count() int32
- func (t *PriceLevelTree) Delete(price udecimal.Decimal) bool
- func (t *PriceLevelTree) DeleteMin() (udecimal.Decimal, bool)
- func (t *PriceLevelTree) InOrderSlice() []udecimal.Decimal
- func (t *PriceLevelTree) Insert(price udecimal.Decimal) bool
- func (t *PriceLevelTree) Max() (udecimal.Decimal, bool)
- func (t *PriceLevelTree) Min() (udecimal.Decimal, bool)
- func (t *PriceLevelTree) Successor(price udecimal.Decimal) (udecimal.Decimal, bool)
- type SkiplistIterator
- type SkiplistNode
- type SkiplistOptions
Constants ¶
const ( // SkiplistMaxLevel is the maximum height of the skiplist. SkiplistMaxLevel = 16 // Maximum level height // SkiplistP is the 1/P probability of level increase. SkiplistP = 4 // 1/P probability of level increase // DefaultGrowthFactor is the default expansion factor for the arena. DefaultGrowthFactor = 2 // Default expansion factor )
const ( // NullIndex represents a null pointer in the arena. NullIndex int32 = -1 )
Variables ¶
var ErrMaxCapacityReached = errors.New("skiplist: max capacity reached")
ErrMaxCapacityReached is returned when the skiplist arena is full and cannot grow.
Functions ¶
This section is empty.
Types ¶
type PooledSkiplist ¶
type PooledSkiplist struct {
// contains filtered or unexported fields
}
PooledSkiplist is an arena-backed skiplist for price levels.
func NewPooledSkiplist ¶
func NewPooledSkiplist(capacity int32, seed int64) *PooledSkiplist
NewPooledSkiplist creates a new pooled skiplist with pre-allocated capacity. Default sort order is ascending (lowest first).
func NewPooledSkiplistWithOptions ¶
func NewPooledSkiplistWithOptions(capacity int32, seed int64, opts SkiplistOptions) *PooledSkiplist
NewPooledSkiplistWithOptions creates a new pooled skiplist with custom options.
func (*PooledSkiplist) Capacity ¶
func (sl *PooledSkiplist) Capacity() int32
Capacity returns the current capacity of the arena.
func (*PooledSkiplist) Contains ¶
func (sl *PooledSkiplist) Contains(price udecimal.Decimal) bool
Contains checks if a price exists in the skiplist.
func (*PooledSkiplist) Count ¶
func (sl *PooledSkiplist) Count() int32
Count returns the number of nodes.
func (*PooledSkiplist) Delete ¶
func (sl *PooledSkiplist) Delete(price udecimal.Decimal) bool
Delete removes a price from the skiplist. Returns true if deleted, false if not found.
func (*PooledSkiplist) DeleteMin ¶
func (sl *PooledSkiplist) DeleteMin() (udecimal.Decimal, bool)
DeleteMin removes and returns the minimum price.
func (*PooledSkiplist) InOrderSlice ¶
func (sl *PooledSkiplist) InOrderSlice() []udecimal.Decimal
InOrderSlice returns all prices in sorted order.
func (*PooledSkiplist) Insert ¶
func (sl *PooledSkiplist) Insert(price udecimal.Decimal) (bool, error)
Insert inserts a price into the skiplist. Returns true if inserted, false if already exists. Returns error if max capacity is reached.
func (*PooledSkiplist) Iterator ¶
func (sl *PooledSkiplist) Iterator() *SkiplistIterator
Iterator returns an iterator positioned at the first (minimum) element.
func (*PooledSkiplist) Min ¶
func (sl *PooledSkiplist) Min() (udecimal.Decimal, bool)
Min returns the minimum price in the skiplist.
func (*PooledSkiplist) MustInsert ¶
func (sl *PooledSkiplist) MustInsert(price udecimal.Decimal) bool
MustInsert is like Insert but panics on error. Use only when you're certain capacity won't be exceeded.
type PriceLevel ¶
type PriceLevel struct {
Left int32 // Left child index
Right int32 // Right child index
Parent int32 // Parent index (for efficient successor traversal)
Color bool // true = Red, false = Black
Price udecimal.Decimal // Key: price level
}
PriceLevel represents a node in the LLRB tree. Each node corresponds to a price level in the order book.
type PriceLevelTree ¶
type PriceLevelTree struct {
// contains filtered or unexported fields
}
PriceLevelTree is an arena-backed LLRB tree for price levels.
func NewPriceLevelTree ¶
func NewPriceLevelTree(capacity int32) *PriceLevelTree
NewPriceLevelTree creates a new LLRB tree with pre-allocated capacity.
func (*PriceLevelTree) Contains ¶
func (t *PriceLevelTree) Contains(price udecimal.Decimal) bool
Contains checks if a price exists in the tree.
func (*PriceLevelTree) Count ¶
func (t *PriceLevelTree) Count() int32
Count returns the number of nodes in the tree.
func (*PriceLevelTree) Delete ¶
func (t *PriceLevelTree) Delete(price udecimal.Decimal) bool
Delete removes a price from the tree. Returns true if the price was found and deleted.
func (*PriceLevelTree) DeleteMin ¶
func (t *PriceLevelTree) DeleteMin() (udecimal.Decimal, bool)
DeleteMin removes and returns the minimum price.
func (*PriceLevelTree) InOrderSlice ¶
func (t *PriceLevelTree) InOrderSlice() []udecimal.Decimal
InOrderSlice returns all prices in sorted order (for testing/debugging).
func (*PriceLevelTree) Insert ¶
func (t *PriceLevelTree) Insert(price udecimal.Decimal) bool
Insert inserts a price into the tree. Returns true if the price was newly inserted, false if it already existed.
func (*PriceLevelTree) Max ¶
func (t *PriceLevelTree) Max() (udecimal.Decimal, bool)
Max returns the maximum price in the tree.
type SkiplistIterator ¶
type SkiplistIterator struct {
// contains filtered or unexported fields
}
SkiplistIterator provides ordered traversal over the skiplist. Usage:
iter := sl.Iterator()
for iter.Valid() {
price := iter.Price()
// ...
iter.Next()
}
func (*SkiplistIterator) Next ¶
func (it *SkiplistIterator) Next()
Next advances the iterator to the next element.
func (*SkiplistIterator) Price ¶
func (it *SkiplistIterator) Price() udecimal.Decimal
Price returns the price at the current iterator position. Only valid when Valid() returns true.
func (*SkiplistIterator) Valid ¶
func (it *SkiplistIterator) Valid() bool
Valid returns true if the iterator points to a valid element.
type SkiplistNode ¶
type SkiplistNode struct {
Forward [SkiplistMaxLevel]int32 // Forward pointers (fixed size for pooling)
Price udecimal.Decimal // Key
Level int32 // Actual level of this node (1 to MaxLevel)
}
SkiplistNode represents a node in the pooled skiplist.
type SkiplistOptions ¶
type SkiplistOptions struct {
// MaxCapacity sets the maximum number of nodes allowed.
// If 0 (default), there is no limit and the skiplist will grow indefinitely.
MaxCapacity int32
// OnGrow is called when the skiplist expands.
// Can be used for logging or metrics.
OnGrow func(oldCap, newCap int32)
// Descending sets the sort order to descending (highest first).
// Default is ascending (lowest first).
Descending bool
}
SkiplistOptions configures the pooled skiplist behavior.
Source Files