clob_engine/order_book/
orderbook.rs

1use std::collections::{BTreeMap, btree_map::{Entry}};
2use anyhow::anyhow;
3use tracing::instrument;
4use crate::order_book::types::{BookDepth, EngineCancelOrder, EngineModifyOrder, ModifyOutcome, OrderNode, PriceLevel, PriceLevelDepth};
5
6#[derive(Debug)]
7pub struct OrderBook{
8    pub ask : HalfBook,
9    pub bid : HalfBook
10}
11impl OrderBook {
12    pub fn new () -> Self{
13        Self { ask : HalfBook::new(), bid : HalfBook::new() }
14    }
15
16    #[instrument( // used for auto span creation & drop.
17        name = "create_buy_order",
18        skip(self),
19        fields(
20            order_id = %order_id,
21            price = resting_order.market_limit
22        ),
23        err
24    )]
25    pub fn create_buy_order(&mut self, order_id : u64, resting_order : OrderNode) -> Result<usize, anyhow::Error>{
26        
27        let mut order = resting_order;
28        let order_quantity = order.current_quantity;
29        let price = order.market_limit;
30
31        match self.bid.price_map.entry(price){ // here price is not moved, bcoz u32 implements Copy
32            Entry::Occupied(mut entry) => {
33                let price_level = entry.get_mut();
34                if price_level.total_quantity == 0 || price_level.head == None || price_level.tail == None{
35                    entry.remove();
36                } else {
37                     order.prev = price_level.tail;
38                if let Some(free_index) = self.bid.free_list.pop(){
39                    self.bid.order_pool[free_index] = Some(order);
40                    let prev_tail_idx = price_level.tail.unwrap();
41                    price_level.tail = Some(free_index);
42                    price_level.total_quantity += order_quantity;
43                    price_level.order_count += 1;
44                        if let Some(prev_order) = self.bid.order_pool.get_mut(prev_tail_idx).unwrap(){
45                            prev_order.next = Some(free_index);
46                        };
47                    return Ok(free_index);
48                }
49                else {
50                self.bid.order_pool.push(Some(order));
51                let new_tail = self.bid.order_pool.len() - 1;
52                let pre_tail_idx = price_level.tail.unwrap();
53                price_level.tail = Some(new_tail);
54                price_level.total_quantity += order_quantity;
55                price_level.order_count += 1;
56                if let Some(prev_order) = self.bid.order_pool.get_mut(pre_tail_idx).unwrap(){
57                    prev_order.next = Some(new_tail);
58                };
59                return Ok(new_tail);
60                }
61                }
62            }
63            Entry::Vacant(_) => {
64                // it means price_level doesn't exist. we create below
65            }
66        }
67
68        let mut new_price_level = PriceLevel{
69            head : None,
70            tail : None,
71            order_count : 0,
72            total_quantity : 0
73        };
74        if let Some(free_index) = self.bid.free_list.pop(){
75            self.bid.order_pool[free_index] = Some(order);
76            new_price_level.head = Some(free_index);
77            new_price_level.tail = Some(free_index);
78            new_price_level.order_count += 1;
79            new_price_level.total_quantity += order_quantity;
80            self.bid.price_map.entry(price).or_insert(new_price_level);
81            return Ok(free_index)
82        }
83        self.bid.order_pool.push(Some(order));
84        let new_index = self.bid.order_pool.len()-1;
85        new_price_level.head = Some(new_index);
86        new_price_level.tail = Some(new_index);
87        new_price_level.order_count += 1;
88        new_price_level.total_quantity += order_quantity;
89        self.bid.price_map.entry(price).or_insert(new_price_level);
90        
91        Ok(new_index)
92    }
93
94    #[instrument( 
95        name = "create_sell_order",
96        skip(self),
97        fields(
98            order_id = %order_id,
99            price = resting_order.market_limit 
100        ),
101        err
102    )]
103    pub fn create_sell_order(&mut self, order_id : u64, resting_order : OrderNode) -> Result<usize, anyhow::Error>{
104        let mut order = resting_order;
105        let order_quantity = order.current_quantity;
106        let price = order.market_limit;
107
108        match self.ask.price_map.entry(price){
109            Entry::Occupied(mut entry) => {
110                let price_level = entry.get_mut();
111                if price_level.total_quantity == 0 || price_level.head == None || price_level.tail == None{
112                    entry.remove();
113                }else {
114                    order.prev = price_level.tail;
115                if let Some(free_index) = self.ask.free_list.pop(){
116                    self.ask.order_pool[free_index] = Some(order);
117                    let prev_tail_idx = price_level.tail.unwrap();
118                    price_level.tail = Some(free_index);
119                    price_level.total_quantity += order_quantity;
120                    price_level.order_count += 1;
121                    if let Some(prev_order) = self.ask.order_pool.get_mut(prev_tail_idx).unwrap(){
122                        prev_order.next = Some(free_index);
123                    };
124                    return Ok(free_index);
125                }
126                else {
127                self.ask.order_pool.push(Some(order));
128                let new_tail = self.ask.order_pool.len() - 1;
129                let prev_tail_idx = price_level.tail.unwrap();
130                price_level.tail = Some(new_tail);
131                price_level.total_quantity += order_quantity;
132                price_level.order_count += 1;
133                if let Some(prev_order) = self.ask.order_pool.get_mut(prev_tail_idx).unwrap(){
134                    prev_order.next = Some(new_tail);
135                };
136                return Ok(new_tail);
137                }
138                }
139            }
140            Entry::Vacant(_) => {
141                //do nothing
142            }
143        }
144        
145        let mut new_price_level = PriceLevel{
146            head : None,
147            tail : None,
148            order_count : 0,
149            total_quantity : 0
150        };
151        if let Some(free_index) = self.ask.free_list.pop(){
152            self.ask.order_pool[free_index] = Some(order);
153            new_price_level.head = Some(free_index);
154            new_price_level.tail = Some(free_index);
155            new_price_level.order_count += 1;
156            new_price_level.total_quantity += order_quantity;
157            self.ask.price_map.entry(price).or_insert(new_price_level);
158            return Ok(free_index)
159        }
160        self.ask.order_pool.push(Some(order));
161        let new_index = self.ask.order_pool.len()-1;
162        new_price_level.head = Some(new_index);
163        new_price_level.tail = Some(new_index);
164        new_price_level.order_count += 1;
165        new_price_level.total_quantity += order_quantity;
166        self.ask.price_map.entry(price).or_insert(new_price_level);
167        
168        Ok(new_index)
169    }
170
171    #[instrument( 
172        name = "cancel_order",
173        skip(self),
174        fields(
175            order_id = %order_id
176        ),
177        err
178    )]
179    pub fn cancel_order(&mut self, order_id : u64, order : EngineCancelOrder) -> Result<(), anyhow::Error>{
180        if order.is_buy_side {
181                            let (prev, next, old_price, old_quantity) = {
182                                match self.bid.order_pool[order.order_index].as_ref(){
183                                    Some(node) => {
184                                        (node.prev, node.next, node.market_limit, node.current_quantity)
185                                    }
186                                    None => {
187                                        return Err(anyhow!("order node doesn't exist at index for cancellation"));
188                                    }
189                                }
190                            };
191                    if let Some(price_level) = self.bid.price_map.get_mut(&old_price){
192
193                        if price_level.head.is_some() && price_level.tail.is_some(){
194                            if order.order_index == price_level.head.unwrap() && order.order_index == price_level.tail.unwrap(){
195                                self.bid.order_pool[order.order_index] = None;
196                                price_level.head = None;
197                                price_level.tail = None;
198                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
199                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
200                                self.bid.free_list.push(order.order_index);
201                                return Ok(());
202                            }
203                            else if order.order_index == price_level.tail.unwrap() {
204                               if let Some(prev_index) = prev{
205                                    if let Some(possible_prev_node) = self.bid.order_pool.get_mut(prev_index){
206                                        if let Some(prev_node) = possible_prev_node{
207                                            prev_node.next = None;
208                                            price_level.tail = Some(prev_index);
209                                        }           
210                                    }
211                                self.bid.order_pool[order.order_index] = None;
212                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
213                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
214                                self.bid.free_list.push(order.order_index);
215                                return Ok(()); 
216                                } else {
217                                    return Err(anyhow!("no prev node found for deletion of tail node"));
218                                }
219                            }
220                            else if order.order_index == price_level.head.unwrap() {
221                                if let Some(next_index) = next{
222                                    if let Some(possible_next_node) = self.bid.order_pool.get_mut(next_index){
223                                        if let Some(next_node) = possible_next_node{
224                                            next_node.prev = None;
225                                            price_level.head = Some(next_index);
226                                        }
227                                    }
228                                    self.bid.order_pool[order.order_index] = None;
229                                    price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
230                                    price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
231                                    self.bid.free_list.push(order.order_index);
232                                    return Ok(());
233                                } else {
234                                    return Err(anyhow!("no next node found for deletion of head node"));
235                                }                    
236                            }
237                            else {
238                                if let Some(prev_index) = prev{
239                                    if let Some(possible_prev_node) = self.bid.order_pool.get_mut(prev_index){
240                                        if let Some(prev_node) = possible_prev_node{
241                                            prev_node.next = next
242                                        }
243                                    }
244                                }
245                                else {
246                                    return Err(anyhow!("no prev node found for deletion of middle node"));
247                                }
248                                if let Some(next_index) = next{
249                                    if let Some(possible_next_node) = self.bid.order_pool.get_mut(next_index){
250                                        if let Some(next_node) = possible_next_node{
251                                            next_node.prev = prev
252                                        }
253                                    }
254                                }
255                                else {
256                                    return Err(anyhow!("no next node found for deletion of middle node"));
257                                }
258                                self.bid.order_pool[order.order_index] = None;
259                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
260                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
261                                self.bid.free_list.push(order.order_index);
262                                return Ok(());
263                            }
264                        } else {
265                            self.bid.price_map.remove(&old_price);
266                            return Err(anyhow::anyhow!("head and tail corrupted so deleted"));
267                        }
268                    } else {
269                        return Err(anyhow!("unable to get old price node to perform cancellation"));
270                    }
271        } else {
272                    let (prev, next, old_price, old_quantity) = {
273                                match self.ask.order_pool[order.order_index].as_ref(){
274                                    Some(node) => {
275                                        (node.prev, node.next, node.market_limit, node.current_quantity)
276                                    }
277                                    None => {
278                                        return Err(anyhow!("order node doesn't exist at index for cancellation"));
279                                    }
280                                }
281                            };
282                    if let Some(price_level) = self.ask.price_map.get_mut(&old_price){
283
284                        if price_level.head.is_some() && price_level.tail.is_some(){
285                            if order.order_index == price_level.head.unwrap() && order.order_index == price_level.tail.unwrap(){
286                                self.ask.order_pool[order.order_index] = None;
287                                price_level.head = None;
288                                price_level.tail = None;
289                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
290                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
291                                self.ask.free_list.push(order.order_index);
292                                return Ok(());
293                            }
294                            else if order.order_index == price_level.tail.unwrap() {
295                               if let Some(prev_index) = prev{
296                                    if let Some(possible_prev_node) = self.ask.order_pool.get_mut(prev_index){
297                                        if let Some(prev_node) = possible_prev_node{
298                                            prev_node.next = None;
299                                            price_level.tail = Some(prev_index);
300                                        }           
301                                    }
302                                self.ask.order_pool[order.order_index] = None;
303                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
304                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
305                                self.ask.free_list.push(order.order_index);
306                                return Ok(()); 
307                                } else {
308                                    return Err(anyhow!("no prev node found for deletion of tail node"));
309                                }
310                            }
311                            else if order.order_index == price_level.head.unwrap() {
312                                if let Some(next_index) = next{
313                                    if let Some(possible_next_node) = self.ask.order_pool.get_mut(next_index){
314                                        if let Some(next_node) = possible_next_node{
315                                            next_node.prev = None;
316                                            price_level.head = Some(next_index);
317                                        }
318                                    }
319                                    self.ask.order_pool[order.order_index] = None;
320                                    price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
321                                    price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
322                                    self.ask.free_list.push(order.order_index);
323                                    return Ok(());
324                                } else {
325                                    return Err(anyhow!("no next node found for deletion of head node"));
326                                }                    
327                            }
328                            else {
329                                if let Some(prev_index) = prev{
330                                    if let Some(possible_prev_node) = self.ask.order_pool.get_mut(prev_index){
331                                        if let Some(prev_node) = possible_prev_node{
332                                            prev_node.next = next
333                                        }
334                                    }
335                                }
336                                else {
337                                    return Err(anyhow!("no prev node found for deletion of middle node"));
338                                }
339                                if let Some(next_index) = next{
340                                    if let Some(possible_next_node) = self.ask.order_pool.get_mut(next_index){
341                                        if let Some(next_node) = possible_next_node{
342                                            next_node.prev = prev
343                                        }
344                                    }
345                                }
346                                else {
347                                    return Err(anyhow!("no next node found for deletion of middle node"));
348                                }
349                                self.ask.order_pool[order.order_index] = None;
350                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
351                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
352                                self.ask.free_list.push(order.order_index);
353                                return Ok(());
354                            }
355                        } else {
356                            self.ask.price_map.remove(&old_price);
357                            return Err(anyhow::anyhow!("head and tail corrupted so deleted"));
358                        }
359                    } else {
360                        return Err(anyhow!("unable to get old price node to perform cancellation"));
361                    }
362        }
363    }
364
365    #[instrument( 
366        name = "modify_order",
367        skip(self),
368        fields(
369            order_id = %order_id,
370        ),
371        err
372    )]
373    pub fn modify_order(&mut self, order_id : u64, order : EngineModifyOrder) -> Result<Option<ModifyOutcome>, anyhow::Error>{
374        if order.is_buy_side{
375                let (old_initial_qty, old_current_qty, old_price) = {
376                    match self.bid.order_pool[order.order_index].as_ref(){
377                        Some(node) => {
378                            (node.initial_quantity, node.current_quantity, node.market_limit)
379                        }
380                        None => {
381                            return Err(anyhow!("order node not found at index for modification (buy)"));
382                        }
383                    }
384                };
385                if let Some(new_price) = order.new_price && let Some(new_qty) = order.new_quantity{
386                    if new_price != old_price{
387                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
388                            return Ok(Some(ModifyOutcome::Both {new_price, new_initial_qty: new_qty, old_current_qty }));
389                            }
390                        }
391                    return Ok(None);
392                } else if let Some(new_qty) = order.new_quantity  {
393                    if new_qty > old_initial_qty{
394                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
395                            return Ok(Some(ModifyOutcome::Requantized {old_price, new_initial_qty: new_qty, old_current_qty }))
396                        }
397                        return Ok(None);
398                    }
399                    else {
400                        match self.bid.order_pool[order.order_index].as_mut(){
401                            Some(order_node) => {
402                                order_node.initial_quantity = new_qty;
403                                return Ok(Some(ModifyOutcome::Inplace));
404                            }
405                            None => {
406                                return Err(anyhow!("couldn't find order node to modify qty in-place (buy)"));
407                            }
408                        }
409                    }
410                } else {
411                    if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
412                        return Ok(Some(ModifyOutcome::Repriced {new_price : order.new_price.unwrap(), old_initial_qty, old_current_qty }));
413                    }
414                    return Ok(None);
415                }
416        } else {
417                let (old_initial_qty, old_current_qty, old_price) = {
418                    match self.ask.order_pool[order.order_index].as_ref(){
419                        Some(node) => {
420                            (node.initial_quantity, node.current_quantity, node.market_limit)
421                        }
422                        None => {
423                            return Err(anyhow!("order node not found at index for modification (sell)"));
424                        }
425                    }
426                };
427
428                if let Some(new_price) = order.new_price && let Some(new_qty) = order.new_quantity{
429                    if new_price != old_price{
430                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
431                           return Ok(Some(ModifyOutcome::Requantized {old_price, new_initial_qty: new_qty, old_current_qty }))
432                        }
433                    }
434                    return Ok(None);
435                } else if let Some(new_qty) = order.new_quantity  {
436                    if new_qty > old_initial_qty{
437                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
438                            return Ok(Some(ModifyOutcome::Requantized { old_price, new_initial_qty: new_qty, old_current_qty }))
439                        }
440                        return Ok(None);
441                    }
442                    else {
443                        match self.ask.order_pool[order.order_index].as_mut(){
444                            Some(order_node) => {
445                                order_node.initial_quantity = new_qty;
446                                return Ok(Some(ModifyOutcome::Inplace));
447                            }
448                            None => {
449                                return Err(anyhow!("couldn't find order node to modify qty in-place (sell)"));
450                            }
451                        }
452                    }
453                }else {
454                    if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_index : order.order_index, is_buy_side: order.is_buy_side,}){
455                        return Ok(Some(ModifyOutcome::Repriced { new_price : order.new_price.unwrap(), old_initial_qty, old_current_qty }));
456                    }
457                    return Ok(None);
458                }
459        }
460    }
461    
462    #[instrument( 
463        name = "book_depth",
464        skip(self),
465        err
466    )]
467    pub fn depth(&self, levels_count : Option<u32>) -> Result<BookDepth, anyhow::Error>{
468
469        let ask_iter = self.ask.price_map.iter().rev();
470        let bid_iter = self.bid.price_map.iter();
471
472        let ask_depth : Vec<_> = match levels_count {
473            Some(n) => ask_iter.take(n as usize)
474            .map(|(price, price_level)| PriceLevelDepth {
475                price_level : *price,
476                quantity : price_level.total_quantity
477            })
478            .collect(),
479            None => ask_iter.map(|(price, price_level)| PriceLevelDepth {
480                price_level : *price,
481                quantity : price_level.total_quantity
482            }).collect()
483        };
484        let bid_depth = match levels_count {
485            Some(n) => bid_iter.take(n as usize)
486            .map(|(price, price_level)| PriceLevelDepth {
487                price_level : *price,
488                quantity : price_level.total_quantity
489            })
490            .collect(),
491            None => bid_iter.map(|(price, price_level)| PriceLevelDepth {
492                price_level : *price,
493                quantity : price_level.total_quantity
494            }).collect()
495        };
496        Ok(BookDepth { bid_depth, ask_depth })
497    }
498}
499
500#[derive(Debug)]
501pub struct HalfBook{
502    pub price_map : BTreeMap<u32, PriceLevel>,
503    pub order_pool : Vec<Option<OrderNode>>,
504    pub free_list : Vec<usize>, // we're storing the free indices from the price level to keep the cache lines hot.
505}
506
507impl HalfBook {
508    pub fn new() -> Self{
509        Self { price_map: BTreeMap::new(), order_pool: Vec::new(), free_list: Vec::new()}
510    }
511}
clob_engine/order_book/orderbook.rs

clob_engine/order_book/
orderbook.rs
