clob_engine/order_book/
orderbook.rs

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

clob_engine/order_book/
orderbook.rs
