application/mov/match/order_book.go

   1 package match
   2
   3 import (
   4         "sort"
   5         "sync"
   6
   7         "github.com/bytom/vapor/application/mov/common"
   8         "github.com/bytom/vapor/application/mov/database"
   9 )
  10
  11 // OrderBook is used to handle the mov orders in memory like stack
  12 type OrderBook struct {
  13         movStore database.MovStore
  14         // key of tradePair -> []order
  15         dbOrders *sync.Map
  16         // key of tradePair -> iterator
  17         orderIterators *sync.Map
  18
  19         // key of tradePair -> []order
  20         arrivalAddOrders *sync.Map
  21         // key of order -> order
  22         arrivalDelOrders *sync.Map
  23 }
  24
  25 func arrangeArrivalAddOrders(orders []*common.Order) *sync.Map {
  26         orderMap := make(map[string][]*common.Order)
  27         for _, order := range orders {
  28                 orderMap[order.TradePair().Key()] = append(orderMap[order.TradePair().Key()], order)
  29         }
  30
  31         arrivalOrderMap := &sync.Map{}
  32         for key, orders := range orderMap {
  33                 sort.Sort(sort.Reverse(common.OrderSlice(orders)))
  34                 arrivalOrderMap.Store(key, orders)
  35         }
  36         return arrivalOrderMap
  37 }
  38
  39 func arrangeArrivalDelOrders(orders []*common.Order) *sync.Map {
  40         arrivalDelOrderMap := &sync.Map{}
  41         for _, order := range orders {
  42                 arrivalDelOrderMap.Store(order.Key(), order)
  43         }
  44         return arrivalDelOrderMap
  45 }
  46
  47 // NewOrderBook create a new OrderBook object
  48 func NewOrderBook(movStore database.MovStore, arrivalAddOrders, arrivalDelOrders []*common.Order) *OrderBook {
  49         return &OrderBook{
  50                 movStore:       movStore,
  51                 dbOrders:       &sync.Map{},
  52                 orderIterators: &sync.Map{},
  53
  54                 arrivalAddOrders: arrangeArrivalAddOrders(arrivalAddOrders),
  55                 arrivalDelOrders: arrangeArrivalDelOrders(arrivalDelOrders),
  56         }
  57 }
  58
  59 // AddOrder add the in memory temp order to order table, because temp order is what left for the
  60 // partial trade order, so the price should be lowest.
  61 func (o *OrderBook) AddOrder(order *common.Order) error {
  62         tradePairKey := order.TradePair().Key()
  63         orders := o.getArrivalAddOrders(tradePairKey)
  64         // use binary search to find the insert position
  65         i := sort.Search(len(orders), func(i int) bool { return order.Cmp(orders[i]) > 0 })
  66         orders = append(orders, order)
  67         copy(orders[i+1:], orders[i:])
  68         orders[i] = order
  69
  70         o.arrivalAddOrders.Store(tradePairKey, orders)
  71         return nil
  72 }
  73
  74 // DelOrder mark the order has been deleted in order book
  75 func (o *OrderBook) DelOrder(order *common.Order) {
  76         o.arrivalDelOrders.Store(order.Key(), order)
  77 }
  78
  79 // PeekOrder return the next lowest order of given trade pair
  80 func (o *OrderBook) PeekOrder(tradePair *common.TradePair) *common.Order {
  81         if len(o.getDBOrders(tradePair.Key())) == 0 {
  82                 o.extendDBOrders(tradePair)
  83         }
  84
  85         var nextOrder *common.Order
  86         orders := o.getDBOrders(tradePair.Key())
  87         if len(orders) != 0 {
  88                 nextOrder = orders[len(orders)-1]
  89         }
  90
  91         if nextOrder != nil && o.getArrivalDelOrders(nextOrder.Key()) != nil {
  92                 o.dbOrders.Store(tradePair.Key(), orders[0:len(orders)-1])
  93                 return o.PeekOrder(tradePair)
  94         }
  95
  96         arrivalOrder := o.peekArrivalOrder(tradePair)
  97         if nextOrder == nil || (arrivalOrder != nil && arrivalOrder.Cmp(nextOrder) < 0) {
  98                 nextOrder = arrivalOrder
  99         }
 100         return nextOrder
 101 }
 102
 103 // PeekOrders return the next lowest orders by given array of trade pairs
 104 func (o *OrderBook) PeekOrders(tradePairs []*common.TradePair) []*common.Order {
 105         var orders []*common.Order
 106         for _, tradePair := range tradePairs {
 107                 order := o.PeekOrder(tradePair)
 108                 if order == nil {
 109                         return nil
 110                 }
 111
 112                 orders = append(orders, order)
 113         }
 114         return orders
 115 }
 116
 117 // PopOrder delete the next lowest order of given trade pair
 118 func (o *OrderBook) PopOrder(tradePair *common.TradePair) {
 119         order := o.PeekOrder(tradePair)
 120         if order == nil {
 121                 return
 122         }
 123
 124         orders := o.getDBOrders(tradePair.Key())
 125         if len(orders) != 0 && orders[len(orders)-1].Key() == order.Key() {
 126                 o.dbOrders.Store(tradePair.Key(), orders[0:len(orders)-1])
 127                 return
 128         }
 129
 130         arrivalOrders := o.getArrivalAddOrders(tradePair.Key())
 131         if len(arrivalOrders) != 0 && arrivalOrders[len(arrivalOrders)-1].Key() == order.Key() {
 132                 o.arrivalAddOrders.Store(tradePair.Key(), arrivalOrders[0:len(arrivalOrders)-1])
 133         }
 134 }
 135
 136 // PopOrders delete the next lowest orders by given trade pairs
 137 func (o *OrderBook) PopOrders(tradePairs []*common.TradePair) []*common.Order {
 138         var orders []*common.Order
 139         for _, tradePair := range tradePairs {
 140                 o.PopOrder(tradePair)
 141         }
 142         return orders
 143 }
 144
 145 func (o *OrderBook) getDBOrders(tradePairKey string) []*common.Order {
 146         if orders, ok := o.dbOrders.Load(tradePairKey); ok {
 147                 return orders.([]*common.Order)
 148         }
 149         return []*common.Order{}
 150 }
 151
 152 func (o *OrderBook) getArrivalAddOrders(tradePairKey string) []*common.Order {
 153         if orders, ok := o.arrivalAddOrders.Load(tradePairKey); ok {
 154                 return orders.([]*common.Order)
 155         }
 156         return []*common.Order{}
 157 }
 158
 159 func (o *OrderBook) getArrivalDelOrders(orderKey string) *common.Order {
 160         if order, ok := o.arrivalDelOrders.Load(orderKey); ok {
 161                 return order.(*common.Order)
 162         }
 163         return nil
 164 }
 165
 166 func (o *OrderBook) extendDBOrders(tradePair *common.TradePair) {
 167         iterator, ok := o.orderIterators.Load(tradePair.Key())
 168         if !ok {
 169                 iterator = database.NewOrderIterator(o.movStore, tradePair)
 170                 o.orderIterators.Store(tradePair.Key(), iterator)
 171         }
 172
 173         nextOrders := iterator.(*database.OrderIterator).NextBatch()
 174         orders := o.getDBOrders(tradePair.Key())
 175         for i := len(nextOrders) - 1; i >= 0; i-- {
 176                 orders = append(orders, nextOrders[i])
 177         }
 178         o.dbOrders.Store(tradePair.Key(), orders)
 179 }
 180
 181 func (o *OrderBook) peekArrivalOrder(tradePair *common.TradePair) *common.Order {
 182         orders := o.getArrivalAddOrders(tradePair.Key())
 183         delPos := len(orders)
 184         for i := delPos - 1; i >= 0; i-- {
 185                 if o.getArrivalDelOrders(orders[i].Key()) != nil {
 186                         delPos = i
 187                 } else {
 188                         break
 189                 }
 190         }
 191
 192         if delPos < len(orders) {
 193                 orders = orders[:delPos]
 194                 o.arrivalAddOrders.Store(tradePair.Key(), orders)
 195         }
 196
 197         if size := len(orders); size > 0 {
 198                 return orders[size-1]
 199         }
 200         return nil
 201 }