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) {
  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 }
  72
  73 // DelOrder mark the order has been deleted in order book
  74 func (o *OrderBook) DelOrder(order *common.Order) {
  75         o.arrivalDelOrders.Store(order.Key(), order)
  76 }
  77
  78 // PeekOrder return the next lowest order of given trade pair
  79 func (o *OrderBook) PeekOrder(tradePair *common.TradePair) *common.Order {
  80         if len(o.getDBOrders(tradePair.Key())) == 0 {
  81                 o.extendDBOrders(tradePair)
  82         }
  83
  84         var nextOrder *common.Order
  85         orders := o.getDBOrders(tradePair.Key())
  86         if len(orders) != 0 {
  87                 nextOrder = orders[len(orders)-1]
  88         }
  89
  90         if nextOrder != nil && o.getArrivalDelOrders(nextOrder.Key()) != nil {
  91                 o.dbOrders.Store(tradePair.Key(), orders[0:len(orders)-1])
  92                 return o.PeekOrder(tradePair)
  93         }
  94
  95         arrivalOrder := o.peekArrivalOrder(tradePair)
  96         if nextOrder == nil || (arrivalOrder != nil && arrivalOrder.Cmp(nextOrder) < 0) {
  97                 nextOrder = arrivalOrder
  98         }
  99         return nextOrder
 100 }
 101
 102 // PeekOrders return the next lowest orders by given array of trade pairs
 103 func (o *OrderBook) PeekOrders(tradePairs []*common.TradePair) []*common.Order {
 104         var orders []*common.Order
 105         for _, tradePair := range tradePairs {
 106                 order := o.PeekOrder(tradePair)
 107                 if order == nil {
 108                         return nil
 109                 }
 110
 111                 orders = append(orders, order)
 112         }
 113         return orders
 114 }
 115
 116 // PopOrder delete the next lowest order of given trade pair
 117 func (o *OrderBook) PopOrder(tradePair *common.TradePair) {
 118         order := o.PeekOrder(tradePair)
 119         if order == nil {
 120                 return
 121         }
 122
 123         orders := o.getDBOrders(tradePair.Key())
 124         if len(orders) != 0 && orders[len(orders)-1].Key() == order.Key() {
 125                 o.dbOrders.Store(tradePair.Key(), orders[0:len(orders)-1])
 126                 return
 127         }
 128
 129         arrivalOrders := o.getArrivalAddOrders(tradePair.Key())
 130         if len(arrivalOrders) != 0 && arrivalOrders[len(arrivalOrders)-1].Key() == order.Key() {
 131                 o.arrivalAddOrders.Store(tradePair.Key(), arrivalOrders[0:len(arrivalOrders)-1])
 132         }
 133 }
 134
 135 // PopOrders delete the next lowest orders by given trade pairs
 136 func (o *OrderBook) PopOrders(tradePairs []*common.TradePair) []*common.Order {
 137         var orders []*common.Order
 138         for _, tradePair := range tradePairs {
 139                 o.PopOrder(tradePair)
 140         }
 141         return orders
 142 }
 143
 144 func (o *OrderBook) getDBOrders(tradePairKey string) []*common.Order {
 145         if orders, ok := o.dbOrders.Load(tradePairKey); ok {
 146                 return orders.([]*common.Order)
 147         }
 148         return []*common.Order{}
 149 }
 150
 151 func (o *OrderBook) getArrivalAddOrders(tradePairKey string) []*common.Order {
 152         if orders, ok := o.arrivalAddOrders.Load(tradePairKey); ok {
 153                 return orders.([]*common.Order)
 154         }
 155         return []*common.Order{}
 156 }
 157
 158 func (o *OrderBook) getArrivalDelOrders(orderKey string) *common.Order {
 159         if order, ok := o.arrivalDelOrders.Load(orderKey); ok {
 160                 return order.(*common.Order)
 161         }
 162         return nil
 163 }
 164
 165 func (o *OrderBook) extendDBOrders(tradePair *common.TradePair) {
 166         iterator, ok := o.orderIterators.Load(tradePair.Key())
 167         if !ok {
 168                 iterator = database.NewOrderIterator(o.movStore, tradePair)
 169                 o.orderIterators.Store(tradePair.Key(), iterator)
 170         }
 171
 172         nextOrders := iterator.(*database.OrderIterator).NextBatch()
 173         orders := o.getDBOrders(tradePair.Key())
 174         for i := len(nextOrders) - 1; i >= 0; i-- {
 175                 orders = append(orders, nextOrders[i])
 176         }
 177         o.dbOrders.Store(tradePair.Key(), orders)
 178 }
 179
 180 func (o *OrderBook) peekArrivalOrder(tradePair *common.TradePair) *common.Order {
 181         orders := o.getArrivalAddOrders(tradePair.Key())
 182         delPos := len(orders)
 183         for i := delPos - 1; i >= 0; i-- {
 184                 if o.getArrivalDelOrders(orders[i].Key()) != nil {
 185                         delPos = i
 186                 } else {
 187                         break
 188                 }
 189         }
 190
 191         if delPos < len(orders) {
 192                 orders = orders[:delPos]
 193                 o.arrivalAddOrders.Store(tradePair.Key(), orders)
 194         }
 195
 196         if size := len(orders); size > 0 {
 197                 return orders[size-1]
 198         }
 199         return nil
 200 }