clob_engine/order_book/
matching_engine.rs

1use crate::order_book::{
2    orderbook::OrderBook, types::{
3        BookDepth, CancelOutcome, EngineCancelOrder, EngineModifyOrder, EngineNewOrder, MatchOutcome, ModifyOutcome, OrderNode, OrderType
4    }
5};
6use anyhow::{Context, anyhow};
7use std::{collections::HashMap, time::Instant};
8
9#[derive(Debug)]
10pub struct MatchingEngine {
11    _book: HashMap<u32, OrderBook>
12}
13
14impl MatchingEngine {
15
16    pub fn new() -> Self{
17        Self { _book: HashMap::new()}
18    }
19
20    fn get_orderbook(
21        &mut self,
22        security_id : u32
23    ) -> Option<&mut OrderBook> {
24        
25        let Some(book) = self._book.get_mut(&security_id) else {
26            return None;
27        };
28        Some(book)
29    }
30
31    pub fn modify(
32        &mut self,
33        order_id: u64,
34        security_id : u32,
35        new_price: Option<u32>,
36        new_qty: Option<u32>,
37        is_buy_side : bool,
38    ) -> Result< &'static str, anyhow::Error> {
39        let orderbook = self
40            .get_orderbook(security_id)
41            .context("Could not find the orderbook")?;
42        if let Ok(potential_modfication) = orderbook.modify_order(
43            order_id,
44            EngineModifyOrder {
45                order_id,
46                security_id,
47                new_price,
48                is_buy_side,
49                new_quantity: new_qty,
50            },
51        ) {
52            if let Some(modification_result) = potential_modfication {
53                match modification_result {
54                    ModifyOutcome::Both {
55                        new_price,
56                        new_initial_qty,
57                        old_current_qty,
58                    } => {
59                        let _ = self.match_order(
60                            EngineNewOrder {
61                                engine_order_id: order_id,
62                                price: Some(new_price),
63                                initial_quantity: new_initial_qty,
64                                current_quantity : old_current_qty,
65                                is_buy_side,
66                                security_id,
67                                order_type: OrderType::Limit,
68                            });
69                        return Ok("Both")
70                    },
71                    ModifyOutcome::Repriced { new_price, old_initial_qty, old_current_qty } => 
72                        {
73                            let _ = self.match_order(
74                            EngineNewOrder {
75                                engine_order_id: order_id,
76                                price: Some(new_price),
77                                initial_quantity: old_initial_qty,
78                                current_quantity : old_current_qty,
79                                is_buy_side,
80                                security_id,
81                                order_type: OrderType::Limit,
82                            });
83                        return Ok("Repriced")
84                    },
85                    ModifyOutcome::Requantized { old_price, new_initial_qty, old_current_qty } => {
86                            let _ = self.match_order(
87                            EngineNewOrder {
88                                engine_order_id: order_id,
89                                price: Some(old_price),
90                                initial_quantity: new_initial_qty,
91                                current_quantity : old_current_qty,
92                                is_buy_side,
93                                security_id,
94                                order_type: OrderType::Limit,
95                            });
96                            return Ok("Requantized")
97                    },
98                    ModifyOutcome::Inplace => {
99                        return Ok("Inplace")
100                    }
101                }
102            }
103            return Ok("No potential modification")
104        } else {
105            return Ok("No modification occured");
106        }
107    }
108
109    pub fn cancel(&mut self, order_id: u64,security_id : u32, is_buy_side : bool) -> Result<CancelOutcome, anyhow::Error>{
110        
111        let timer = Instant::now();
112        let orderbook = self
113            .get_orderbook(security_id)
114            .context("Could not find the orderbook")?;
115        if let Err(_) = orderbook.cancel_order(order_id, EngineCancelOrder{is_buy_side,security_id, order_id}){
116            let elapsed_time = timer.elapsed().as_micros() as f64;
117            return Ok(CancelOutcome::Failed(elapsed_time));
118        }; 
119        let elapsed_time = timer.elapsed().as_micros() as f64;
120        return Ok(CancelOutcome::Success(elapsed_time));
121    }
122
123    pub fn depth(&self, security_id : u32, levels_count :Option<u32> ) -> Result<BookDepth, anyhow::Error>{
124        
125        let Some(order_book) = self._book.get(&security_id) else {
126            return Err(anyhow!("orderbook doesn't exist"))
127        };
128        match order_book.depth(levels_count){
129            Ok(book_depth) => {
130                Ok(book_depth)
131            },
132            Err(e) => Err(anyhow!("{}", e))
133        }
134    }
135
136    pub fn match_order(&mut self, order: EngineNewOrder) -> Result<MatchOutcome, anyhow::Error> {
137        
138        let timer = Instant::now();
139
140        let orderbook = match self._book.get_mut(&order.security_id){
141            Some(orderbook) => {
142                orderbook
143            }
144            None => {
145                self._book.entry(order.security_id).or_insert(OrderBook::new())
146            }
147        };
148
149        if !order.is_buy_side {
150            // for ASK order
151            match order.order_type {
152                OrderType::Market(None) => {
153                    // need to immediatly execute the order on the best of other half
154                    let mut fill_quantity = order.initial_quantity;
155                    let mut levels_consumed = 0;
156                    let mut orders_touched = 0;
157                    while fill_quantity > 0 {
158                        let remove_node: bool;
159                        {
160                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
161                                break;
162                            };
163                            let price_level = price_node.get_mut();
164                            while price_level.total_quantity > 0 && fill_quantity > 0 {
165                                if let Some(head_idx) = price_level.head{
166
167                                    match orderbook.bid.order_pool[head_idx].as_mut(){
168                                        Some(first_order_node) => {
169
170                                            if fill_quantity >= first_order_node.current_quantity {
171                                                fill_quantity -= first_order_node.current_quantity;
172                                                
173                                                price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
174                                                let next = first_order_node.next;
175                                                orderbook.bid.order_pool[head_idx] = None;
176                                                orderbook.bid.free_list.push(head_idx);
177                                                orders_touched += 1;
178                                                if let Some(next_order_idx) = next {
179                                                    price_level.head = Some(next_order_idx);
180                                                } else {
181                                                    price_level.total_quantity = 0;
182                                                    price_level.head = None;
183                                                    price_level.tail = None;
184                                                    price_level.order_count = 0;
185                                                    break;
186                                                }
187                                            } else {
188                                                first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
189                                                price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
190                                                fill_quantity = 0;
191                                                orders_touched += 1;
192                                            }
193                                        }
194                                        None => {
195                                            return Err(anyhow!("failed to get head_idx from order pool"));
196                                        }
197                                    };
198                                }else {
199                                    // price level has no head. i.e head = None
200                                    break;
201                                }
202                            }
203                            remove_node = price_level.total_quantity == 0;
204                        }
205                        if remove_node {
206                            match orderbook.bid.price_map.pop_last(){
207                                Some(_) => {
208                                    levels_consumed += 1;
209                                }
210                                None => {
211                                    break;
212                                }
213                            };
214                        }
215                    }
216                    let elapsed_time = timer.elapsed().as_micros() as f64;
217                    Ok(MatchOutcome{
218                        order_index : None,
219                        levels_consumed,
220                        orders_touched,
221                        timer : elapsed_time
222                    })
223                }
224                OrderType::Market(market_limit) => {
225                    let mut fill_quantity = order.initial_quantity;
226                    let mut levels_consumed = 0;
227                    let mut orders_touched = 0;
228                    while fill_quantity > 0 {
229                        let remove_node: bool;
230                        {
231                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
232                                break;
233                            };
234
235                            match market_limit {
236                                Some(price) => {
237                                    if price > *price_node.key(){
238                                        break;
239                                    }
240                                }
241                                None => {
242                                    return Err(anyhow!("did not recieve price for market-limit(SELL)"))
243                                }
244                            }
245                            let price_level = price_node.get_mut();
246                            while price_level.total_quantity > 0 && fill_quantity > 0 {
247                                if let Some(head_idx) = price_level.head{
248
249                                    match orderbook.bid.order_pool[head_idx].as_mut(){
250                                        Some(first_order_node) => {
251
252                                            if fill_quantity >= first_order_node.current_quantity {
253                                                fill_quantity -= first_order_node.current_quantity;
254                                                price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
255                                                let next = first_order_node.next;
256                                                orderbook.bid.order_pool[head_idx] = None;
257                                                orderbook.bid.free_list.push(head_idx);
258                                                orders_touched += 1;
259                                                if let Some(next_order_idx) = next {
260                                                    price_level.head = Some(next_order_idx);
261                                                } else {
262                                                    price_level.total_quantity = 0;
263                                                    price_level.head = None;
264                                                    price_level.tail = None;
265                                                    price_level.order_count = 0;
266                                                    break;
267                                                }
268                                            } else {
269                                                first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
270                                                price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
271                                                fill_quantity = 0;
272                                                orders_touched += 1;
273                                            }
274                                        }
275                                        None => {
276                                            return Err(anyhow!("failed to get head_idx from order pool"));
277                                        }
278                                    };
279                                }else {
280                                    break;
281                                }
282                            }
283                            remove_node = price_level.total_quantity == 0;
284                        }
285                        if remove_node {
286                            match orderbook.bid.price_map.pop_last(){
287                                Some(_) => {
288                                    levels_consumed += 1;
289                                }
290                                None => {
291                                    break;
292                                }
293                            };
294                        }
295                    }
296                    let elapsed_time = timer.elapsed().as_micros() as f64;
297                    Ok(MatchOutcome{
298                        order_index : None,
299                        levels_consumed,
300                        orders_touched,
301                        timer : elapsed_time
302                    })
303                }
304                OrderType::Limit => {
305                    let mut fill_quantity = order.initial_quantity;
306                    let mut levels_consumed = 0;
307                    let mut orders_touched = 0;
308                    while fill_quantity > 0 {
309                        let remove_node: bool;
310                        {
311                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
312                                break;
313                            };
314
315                            match order.price {
316                                Some(price) => {
317                                    if price > *price_node.key(){
318                                        break;
319                                    }
320                                }
321                                None => {
322                                    return Err(anyhow!("did not recieve price for limit order (SELL)"))
323                                }
324                            }
325                            let price_level = price_node.get_mut();
326                            while price_level.total_quantity > 0 && fill_quantity > 0 {
327                                if let Some(head_idx) = price_level.head{
328                                    match orderbook.bid.order_pool[head_idx].as_mut(){
329                                        Some(first_order_node) => {
330                                            if fill_quantity >= first_order_node.current_quantity {
331                                        fill_quantity -= first_order_node.current_quantity;
332                                        price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
333                                        let next = first_order_node.next;
334                                        orderbook.bid.order_pool[head_idx] = None;
335                                        orderbook.bid.free_list.push(head_idx);
336                                        orders_touched += 1;
337                                        if let Some(next_order_idx) = next {
338                                            price_level.head = Some(next_order_idx);
339                                        } else {
340                                            price_level.total_quantity = 0;
341                                            price_level.head = None;
342                                            price_level.tail = None;
343                                            price_level.order_count = 0;
344                                            break;
345                                        }
346                                    } else {
347                                        first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
348                                        price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
349                                        fill_quantity = 0;
350                                        orders_touched += 1;
351                                    }
352                                        }
353                                        None => {
354                                            return Err(anyhow!("failed to get head_idx from order pool"));
355                                        }
356                                    };
357                                }else {
358                                    break;
359                                }
360                            }
361                            remove_node = price_level.total_quantity == 0;
362                        }
363                        if remove_node {
364                            match orderbook.bid.price_map.pop_last(){
365                                Some(_) => {
366                                    levels_consumed += 1;
367                                }
368                                None => {
369                                    break;
370                                }
371                            };
372                        }
373                    }
374                    if fill_quantity > 0 {
375                        let alloted_index = orderbook.create_sell_order(
376                            OrderNode {
377                                order_id : order.engine_order_id,
378                                initial_quantity: order.initial_quantity,
379                                current_quantity: fill_quantity,
380                                market_limit: order.price.unwrap(),
381                                next: None,
382                                prev: None,
383                            },
384                        )?;
385                        let elapsed_time = timer.elapsed().as_micros() as f64;
386                        return Ok(MatchOutcome{
387                        order_index : Some(alloted_index as u32),
388                        levels_consumed,
389                        orders_touched,
390                        timer : elapsed_time
391                    })
392                    }
393                    let elapsed_time = timer.elapsed().as_micros() as f64;
394                    Ok(MatchOutcome{
395                        order_index : None,
396                        levels_consumed,
397                        orders_touched,
398                        timer : elapsed_time
399                    })
400                }
401            }
402        } else {
403            match order.order_type {
404                OrderType::Market(None) => {
405                    // need to immediatly execute the order on the best of other half
406                    let mut fill_quantity = order.initial_quantity;
407                    let mut levels_consumed = 0;
408                    let mut orders_touched = 0;
409                    while fill_quantity > 0 {
410                        let remove_node: bool;
411                        {
412                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
413                                break;
414                            };
415                            let price_level = price_node.get_mut();
416                            while price_level.total_quantity > 0 && fill_quantity > 0 {
417                                if let Some(head_idx) = price_level.head{
418                                    match orderbook.ask.order_pool[head_idx].as_mut(){
419                                        Some(first_order_node) => {
420
421                                            if fill_quantity >= first_order_node.current_quantity {
422                                                fill_quantity -= first_order_node.current_quantity;
423                                                price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
424                                                let next = first_order_node.next;
425                                                orderbook.ask.order_pool[head_idx] = None;
426                                                orderbook.ask.free_list.push(head_idx);
427                                                orders_touched += 1;
428                                                if let Some(next_order_idx) = next {
429                                                    price_level.head = Some(next_order_idx);
430                                                } else {
431                                                    price_level.total_quantity = 0;
432                                                    price_level.head = None;
433                                                    price_level.tail = None;
434                                                    price_level.order_count = 0;
435                                                    break;
436                                                }
437                                            } else {
438                                                first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
439                                                price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
440                                                fill_quantity = 0;
441                                                orders_touched += 1;
442                                            }
443                                        }
444                                        None => {
445                                            return Err(anyhow!("failed to get head_idx from order pool"));
446                                        }
447                                    };
448                                }
449                                else {
450                                    break;
451                                }
452                            }
453                            remove_node = price_level.total_quantity == 0;
454                        }
455                        if remove_node {
456                            match orderbook.ask.price_map.pop_first(){
457                                Some(_) => {
458                                    levels_consumed += 1;
459                                }
460                                None => {
461                                    break;
462                                }
463                            };
464                        }
465                    }
466                    let elapsed_time = timer.elapsed().as_micros() as f64;
467                    Ok(MatchOutcome{
468                        order_index : None,
469                        levels_consumed,
470                        orders_touched,
471                        timer : elapsed_time
472                    })
473                }
474                OrderType::Market(market_limit) => {
475                    let mut fill_quantity = order.initial_quantity;
476                    let mut levels_consumed = 0;
477                    let mut orders_touched = 0;
478                    while fill_quantity > 0 {
479                        let remove_node: bool;
480                        {
481                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
482                                break;
483                            };
484
485                            match market_limit {
486                                Some(price) => {
487                                    if price < *price_node.key(){
488                                        break;
489                                    }
490                                }
491                                None => {
492                                    return Err(anyhow!("did not recieve price for market-limit(BUY)"))
493                                }
494                            }
495                            let price_level = price_node.get_mut();
496                            while price_level.total_quantity > 0 && fill_quantity > 0 {
497                                let head_pointer = price_level.head;
498                                if let Some(head_idx) = head_pointer{
499                                    match orderbook.ask.order_pool[head_idx].as_mut(){
500                                        Some(first_order_node) => {
501
502                                            if fill_quantity >= first_order_node.current_quantity {
503                                                fill_quantity -= first_order_node.current_quantity;
504                                                price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
505                                                let next = first_order_node.next;
506                                                orderbook.ask.order_pool[head_idx] = None;
507                                                orderbook.ask.free_list.push(head_idx);
508                                                orders_touched += 1;
509                                                if let Some(next_order_idx) = next {
510                                                    price_level.head = Some(next_order_idx);
511                                                } else {
512                                                    price_level.head = None;
513                                                    price_level.total_quantity = 0;
514                                                    price_level.head = None;
515                                                    price_level.tail = None;
516                                                    price_level.order_count = 0;
517                                                    break;
518                                                }
519                                            } else {
520                                                first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
521                                                price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
522                                                fill_quantity = 0;
523                                                orders_touched += 1;
524                                            }
525                                        }
526                                        None => {
527                                            return Err(anyhow!("failed to get head_idx from order pool"));
528                                        }
529                                    };
530                                }
531                                else {
532                                    break;
533                                }
534                            }
535                            remove_node = price_level.total_quantity == 0;
536                        }
537                        if remove_node {
538                            match orderbook.ask.price_map.pop_first(){
539                                Some(_) => {
540                                    levels_consumed += 1;
541                                }
542                                None => {
543                                    break;
544                                }
545                            };
546                        }
547                    }
548                    let elapsed_time = timer.elapsed().as_micros() as f64;
549                    Ok(MatchOutcome{
550                        order_index : None,
551                        levels_consumed,
552                        orders_touched,
553                        timer : elapsed_time
554                    })
555                }
556                OrderType::Limit => {
557                    let mut fill_quantity = order.initial_quantity;
558                    let mut levels_consumed = 0;
559                    let mut orders_touched = 0;
560                    while fill_quantity > 0 {
561                        let remove_node: bool;
562                        {
563                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
564                                break;
565                            };
566
567                            match order.price {
568                                Some(price) => {
569                                    if price < *price_node.key(){
570                                        break;
571                                    }
572                                }
573                                None => {
574                                    return Err(anyhow!("did not recieve price for limit(BUY)"))
575                                }
576                            }
577                            let price_level = price_node.get_mut();
578                            while price_level.total_quantity > 0 && fill_quantity > 0 {
579                                if let Some(head_idx) = price_level.head{
580
581                                    match orderbook.ask.order_pool[head_idx].as_mut(){
582                                        Some(first_order_node) => {
583
584                                            if fill_quantity >= first_order_node.current_quantity {
585                                                fill_quantity -= first_order_node.current_quantity;
586                                                price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or(anyhow!("error occured in sub of total qty - current qyt"))?;
587                                                let next = first_order_node.next;
588                                                orderbook.ask.order_pool[head_idx] = None;
589                                                orderbook.ask.free_list.push(head_idx);
590                                                orders_touched += 1;
591                                                if let Some(next_order_idx) = next {
592                                                    price_level.head = Some(next_order_idx);
593                                                } else {
594                                                    price_level.total_quantity = 0;
595                                                    price_level.head = None;
596                                                    price_level.tail = None;
597                                                    price_level.order_count = 0;
598                                                    break;
599                                                }
600                                            } else {
601                                                first_order_node.current_quantity = first_order_node.current_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fnq - fq"))?;
602                                                price_level.total_quantity = price_level.total_quantity.checked_sub(fill_quantity).ok_or(anyhow!("error occured subtracting fntq - fq"))?;
603                                                fill_quantity = 0;
604                                                orders_touched += 1;
605                                            }
606                                        }
607                                        None => {
608                                            return Err(anyhow!("failed to get head_idx from order pool"));
609                                        }
610                                    };
611                                }else {
612                                    break;
613                                }
614                            }
615                            remove_node = price_level.total_quantity == 0;
616                        }
617                        if remove_node {
618                            match orderbook.ask.price_map.pop_first(){
619                                Some(_) => {
620                                    levels_consumed += 1;
621                                }
622                                None => {
623                                    break;
624                                }
625                            };
626                        }
627                    }
628                    if fill_quantity > 0{
629                        let alloted_index = orderbook.create_buy_order(
630                            OrderNode {
631                                order_id : order.engine_order_id,
632                                initial_quantity: order.initial_quantity,
633                                current_quantity: fill_quantity,
634                                market_limit: order.price.unwrap(),
635                                next: None,
636                                prev: None,
637                            },
638                        )?;
639                        let elapsed_time = timer.elapsed().as_micros() as f64;
640                        return Ok(MatchOutcome{
641                        order_index : Some(alloted_index as u32),
642                        levels_consumed,
643                        orders_touched,
644                        timer : elapsed_time
645                    })
646                    }
647                    let elapsed_time = timer.elapsed().as_micros() as f64;
648                    Ok(MatchOutcome{
649                        order_index : None,
650                        levels_consumed,
651                        orders_touched,
652                        timer : elapsed_time
653                    })
654                }
655            }
656        }
657    }
658}
clob_engine/order_book/matching_engine.rs

clob_engine/order_book/
matching_engine.rs
