clob_engine/order_book/
orderbook.rs

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

clob_engine/order_book/
orderbook.rs
