clob_engine/order_book/matching_engine.rs
1use crate::order_book::{
2 orderbook::OrderBook,
3 types::{
4 BookDepth, CancelOutcome, EngineCancelOrder, EngineModifyOrder, EngineNewOrder, MatchOutcome, ModifyOutcome, OrderBookError, OrderNode, OrderType
5 },
6};
7use anyhow::{anyhow};
8use std::{collections::HashMap, time::Instant};
9
10#[derive(Debug)]
11pub struct MatchingEngine {
12 _book: HashMap<u32, OrderBook>,
13}
14
15impl MatchingEngine {
16 pub fn new() -> Self {
17 Self {
18 _book: HashMap::new(),
19 }
20 }
21
22 fn get_orderbook(&mut self, security_id: u32) -> Option<&mut OrderBook> {
23 let Some(book) = self._book.get_mut(&security_id) else {
24 return None;
25 };
26 Some(book)
27 }
28
29 pub fn modify(
30 &mut self,
31 order_id: u64,
32 security_id: u32,
33 new_price: Option<u32>,
34 new_qty: Option<u32>,
35 is_buy_side: bool,
36 ) -> Result<&'static str, OrderBookError> {
37 let orderbook = self
38 .get_orderbook(security_id);
39
40 if orderbook.is_none(){
41 return Err(OrderBookError::OrderBookNotFound);
42 }
43 if let Ok(potential_modfication) = orderbook.unwrap().modify_order(
44 order_id,
45 EngineModifyOrder {
46 order_id,
47 security_id,
48 new_price,
49 is_buy_side,
50 new_quantity: new_qty,
51 },
52 ) {
53 if let Some(modification_result) = potential_modfication {
54 match modification_result {
55 ModifyOutcome::Both {
56 new_price,
57 new_initial_qty,
58 old_current_qty,
59 } => {
60 let _ = self.match_order(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::GoodTillCancel,
68 });
69 return Ok("Both");
70 }
71 ModifyOutcome::Repriced {
72 new_price,
73 old_initial_qty,
74 old_current_qty,
75 } => {
76 let _ = self.match_order(EngineNewOrder {
77 engine_order_id: order_id,
78 price: Some(new_price),
79 initial_quantity: old_initial_qty,
80 current_quantity: old_current_qty,
81 is_buy_side,
82 security_id,
83 order_type: OrderType::GoodTillCancel,
84 });
85 return Ok("Repriced");
86 }
87 ModifyOutcome::Requantized {
88 old_price,
89 new_initial_qty,
90 old_current_qty,
91 } => {
92 let _ = self.match_order(EngineNewOrder {
93 engine_order_id: order_id,
94 price: Some(old_price),
95 initial_quantity: new_initial_qty,
96 current_quantity: old_current_qty,
97 is_buy_side,
98 security_id,
99 order_type: OrderType::GoodTillCancel,
100 });
101 return Ok("Requantized");
102 }
103 ModifyOutcome::Inplace => return Ok("Inplace"),
104 }
105 }
106 return Ok("No potential modification");
107 } else {
108 return Ok("No modification occured");
109 }
110 }
111
112 pub fn cancel(
113 &mut self,
114 order_id: u64,
115 security_id: u32,
116 is_buy_side: bool,
117 ) -> Result<CancelOutcome, OrderBookError> {
118 let timer = Instant::now();
119 let orderbook = self
120 .get_orderbook(security_id);
121
122 if orderbook.is_none(){
123 return Err(OrderBookError::OrderBookNotFound);
124 }
125 if let Err(_) = orderbook.unwrap().cancel_order(
126 order_id,
127 EngineCancelOrder {
128 is_buy_side,
129 security_id,
130 order_id,
131 },
132 ) {
133 let elapsed_time = timer.elapsed().as_micros() as f64;
134 return Ok(CancelOutcome::Failed(elapsed_time));
135 };
136 let elapsed_time = timer.elapsed().as_micros() as f64;
137 return Ok(CancelOutcome::Success(elapsed_time));
138 }
139
140 pub fn depth(
141 &self,
142 security_id: u32,
143 levels_count: Option<u32>,
144 ) -> Result<BookDepth, anyhow::Error> {
145 let Some(order_book) = self._book.get(&security_id) else {
146 return Err(anyhow!("order not found"));
147 };
148 match order_book.depth(levels_count) {
149 Ok(book_depth) => Ok(book_depth),
150 Err(e) => Err(anyhow!("{}", e)),
151 }
152 }
153
154 pub fn match_order(&mut self, order: EngineNewOrder) -> Result<MatchOutcome, OrderBookError> {
155 let timer = Instant::now();
156
157 let orderbook = match self._book.get_mut(&order.security_id) {
158 Some(orderbook) => orderbook,
159 None => self
160 ._book
161 .entry(order.security_id)
162 .or_insert(OrderBook::new()),
163 };
164
165 if !order.is_buy_side {
166 // for ASK order
167 match order.order_type {
168 OrderType::Market => {
169 // need to immediatly execute the order on the best of other half
170 let mut fill_quantity = order.initial_quantity;
171 let mut levels_consumed = 0;
172 let mut orders_touched = 0;
173 while fill_quantity > 0 {
174 let remove_node: bool;
175 {
176 let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
177 break;
178 };
179 let price_level = price_node.get_mut();
180 while price_level.total_quantity > 0 && fill_quantity > 0 {
181 if let Some(head_idx) = price_level.head {
182 match orderbook.bid.order_pool[head_idx].as_mut() {
183 Some(first_order_node) => {
184 if fill_quantity >= first_order_node.current_quantity {
185 fill_quantity -= first_order_node.current_quantity;
186
187 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
188 let next = first_order_node.next;
189 orderbook.bid.order_pool[head_idx] = None;
190 orderbook.bid.free_list.push(head_idx);
191 orders_touched += 1;
192 if let Some(next_order_idx) = next {
193 price_level.head = Some(next_order_idx);
194 } else {
195 price_level.total_quantity = 0;
196 price_level.head = None;
197 price_level.tail = None;
198 price_level.order_count = 0;
199 break;
200 }
201 } else {
202 first_order_node.current_quantity =
203 first_order_node
204 .current_quantity
205 .checked_sub(fill_quantity)
206 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
207 price_level.total_quantity = price_level
208 .total_quantity
209 .checked_sub(fill_quantity)
210 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
211 fill_quantity = 0;
212 orders_touched += 1;
213 }
214 }
215 None => {
216 return Err(OrderBookError::HeadNotFound);
217 }
218 };
219 } else {
220 // price level has no head. i.e head = None
221 break;
222 }
223 }
224 remove_node = price_level.total_quantity == 0;
225 }
226 if remove_node {
227 match orderbook.bid.price_map.pop_last() {
228 Some(_) => {
229 levels_consumed += 1;
230 }
231 None => {
232 break;
233 }
234 };
235 }
236 }
237 let elapsed_time = timer.elapsed().as_micros() as f64;
238 Ok(MatchOutcome {
239 order_index: None,
240 levels_consumed,
241 orders_touched,
242 timer: elapsed_time,
243 })
244 }
245 OrderType::ImmediateOrCancel(market_limit) => {
246 let mut fill_quantity = order.initial_quantity;
247 let mut levels_consumed = 0;
248 let mut orders_touched = 0;
249 while fill_quantity > 0 {
250 let remove_node: bool;
251 {
252 let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
253 break;
254 };
255
256 if market_limit > *price_node.key() {
257 break;
258 }
259
260 let price_level = price_node.get_mut();
261 while price_level.total_quantity > 0 && fill_quantity > 0 {
262 if let Some(head_idx) = price_level.head {
263 match orderbook.bid.order_pool[head_idx].as_mut() {
264 Some(first_order_node) => {
265 if fill_quantity >= first_order_node.current_quantity {
266 fill_quantity -= first_order_node.current_quantity;
267 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
268 let next = first_order_node.next;
269 orderbook.bid.order_pool[head_idx] = None;
270 orderbook.bid.free_list.push(head_idx);
271 orders_touched += 1;
272 if let Some(next_order_idx) = next {
273 price_level.head = Some(next_order_idx);
274 } else {
275 price_level.total_quantity = 0;
276 price_level.head = None;
277 price_level.tail = None;
278 price_level.order_count = 0;
279 break;
280 }
281 } else {
282 first_order_node.current_quantity =
283 first_order_node
284 .current_quantity
285 .checked_sub(fill_quantity)
286 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
287 price_level.total_quantity = price_level
288 .total_quantity
289 .checked_sub(fill_quantity)
290 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
291 fill_quantity = 0;
292 orders_touched += 1;
293 }
294 }
295 None => {
296 return Err(OrderBookError::HeadNotFound);
297 }
298 };
299 } else {
300 break;
301 }
302 }
303 remove_node = price_level.total_quantity == 0;
304 }
305 if remove_node {
306 match orderbook.bid.price_map.pop_last() {
307 Some(_) => {
308 levels_consumed += 1;
309 }
310 None => {
311 break;
312 }
313 };
314 }
315 }
316 let elapsed_time = timer.elapsed().as_micros() as f64;
317 Ok(MatchOutcome {
318 order_index: None,
319 levels_consumed,
320 orders_touched,
321 timer: elapsed_time,
322 })
323 }
324 OrderType::GoodTillCancel => {
325 let mut fill_quantity = order.initial_quantity;
326 let mut levels_consumed = 0;
327 let mut orders_touched = 0;
328 while fill_quantity > 0 {
329 let remove_node: bool;
330 {
331 let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
332 break;
333 };
334
335 match order.price {
336 Some(price) => {
337 if price > *price_node.key() {
338 break;
339 }
340 }
341 None => {
342 return Err(OrderBookError::PriceNotFound);
343 }
344 }
345 let price_level = price_node.get_mut();
346 while price_level.total_quantity > 0 && fill_quantity > 0 {
347 if let Some(head_idx) = price_level.head {
348 match orderbook.bid.order_pool[head_idx].as_mut() {
349 Some(first_order_node) => {
350 if fill_quantity >= first_order_node.current_quantity {
351 fill_quantity -= first_order_node.current_quantity;
352 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
353 let next = first_order_node.next;
354 orderbook.bid.order_pool[head_idx] = None;
355 orderbook.bid.free_list.push(head_idx);
356 orders_touched += 1;
357 if let Some(next_order_idx) = next {
358 price_level.head = Some(next_order_idx);
359 } else {
360 price_level.total_quantity = 0;
361 price_level.head = None;
362 price_level.tail = None;
363 price_level.order_count = 0;
364 break;
365 }
366 } else {
367 first_order_node.current_quantity =
368 first_order_node
369 .current_quantity
370 .checked_sub(fill_quantity)
371 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
372 price_level.total_quantity = price_level
373 .total_quantity
374 .checked_sub(fill_quantity)
375 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
376 fill_quantity = 0;
377 orders_touched += 1;
378 }
379 }
380 None => {
381 return Err(OrderBookError::HeadNotFound);
382 }
383 };
384 } else {
385 break;
386 }
387 }
388 remove_node = price_level.total_quantity == 0;
389 }
390 if remove_node {
391 match orderbook.bid.price_map.pop_last() {
392 Some(_) => {
393 levels_consumed += 1;
394 }
395 None => {
396 break;
397 }
398 };
399 }
400 }
401 if fill_quantity > 0 {
402 let alloted_index = orderbook.create_sell_order(OrderNode {
403 order_id: order.engine_order_id,
404 initial_quantity: order.initial_quantity,
405 current_quantity: fill_quantity,
406 market_limit: order.price.unwrap(),
407 next: None,
408 prev: None,
409 })?;
410 let elapsed_time = timer.elapsed().as_micros() as f64;
411 return Ok(MatchOutcome {
412 order_index: Some(alloted_index as u32),
413 levels_consumed,
414 orders_touched,
415 timer: elapsed_time,
416 });
417 }
418 let elapsed_time = timer.elapsed().as_micros() as f64;
419 Ok(MatchOutcome {
420 order_index: None,
421 levels_consumed,
422 orders_touched,
423 timer: elapsed_time,
424 })
425 }
426 OrderType::FillOrKill(limit_price) => {
427 let mut available_quantity: u32 = 0;
428 for (level_price, level) in orderbook.bid.price_map.iter().rev() {
429 if limit_price > *level_price {
430 break;
431 }
432 available_quantity =
433 available_quantity
434 .checked_add(level.total_quantity)
435 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
436 if available_quantity >= order.initial_quantity {
437 break;
438 }
439 }
440
441 if available_quantity < order.initial_quantity {
442 let elapsed_time = timer.elapsed().as_micros() as f64;
443 return Ok(MatchOutcome {
444 order_index: None,
445 levels_consumed: 0,
446 orders_touched: 0,
447 timer: elapsed_time,
448 });
449 }
450
451 let mut fill_quantity = order.initial_quantity;
452 let mut levels_consumed = 0;
453 let mut orders_touched = 0;
454
455 while fill_quantity > 0 {
456 let remove_node: bool;
457 {
458 let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
459 return Err(OrderBookError::PriceLevelEmpty);
460 };
461
462 if limit_price > *price_node.key() {
463 return Err(OrderBookError::UnexpectedReturn);
464 }
465
466 let price_level = price_node.get_mut();
467 while price_level.total_quantity > 0 && fill_quantity > 0 {
468 if let Some(head_idx) = price_level.head {
469 match orderbook.bid.order_pool[head_idx].as_mut() {
470 Some(first_order_node) => {
471 if fill_quantity >= first_order_node.current_quantity {
472 fill_quantity -= first_order_node.current_quantity;
473 price_level.total_quantity = price_level
474 .total_quantity
475 .checked_sub(first_order_node.current_quantity)
476 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
477 let next = first_order_node.next;
478 orderbook.bid.order_pool[head_idx] = None;
479 orderbook.bid.free_list.push(head_idx);
480 orders_touched += 1;
481 if let Some(next_order_idx) = next {
482 price_level.head = Some(next_order_idx);
483 } else {
484 price_level.total_quantity = 0;
485 price_level.head = None;
486 price_level.tail = None;
487 price_level.order_count = 0;
488 break;
489 }
490 } else {
491 first_order_node.current_quantity =
492 first_order_node
493 .current_quantity
494 .checked_sub(fill_quantity)
495 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
496 price_level.total_quantity = price_level
497 .total_quantity
498 .checked_sub(fill_quantity)
499 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
500 fill_quantity = 0;
501 orders_touched += 1;
502 }
503 }
504 None => {
505 return Err(OrderBookError::HeadNotFound);
506 }
507 };
508 } else {
509 break;
510 }
511 }
512 remove_node = price_level.total_quantity == 0;
513 }
514 if remove_node {
515 orderbook.bid.price_map.pop_last();
516 levels_consumed += 1;
517 }
518 }
519
520 let elapsed_time = timer.elapsed().as_micros() as f64;
521 Ok(MatchOutcome {
522 order_index: None,
523 levels_consumed,
524 orders_touched,
525 timer: elapsed_time,
526 })
527 }
528 }
529 } else {
530 match order.order_type {
531 OrderType::Market => {
532 // need to immediatly execute the order on the best of other half
533 let mut fill_quantity = order.initial_quantity;
534 let mut levels_consumed = 0;
535 let mut orders_touched = 0;
536 while fill_quantity > 0 {
537 let remove_node: bool;
538 {
539 let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
540 break;
541 };
542 let price_level = price_node.get_mut();
543 while price_level.total_quantity > 0 && fill_quantity > 0 {
544 if let Some(head_idx) = price_level.head {
545 match orderbook.ask.order_pool[head_idx].as_mut() {
546 Some(first_order_node) => {
547 if fill_quantity >= first_order_node.current_quantity {
548 fill_quantity -= first_order_node.current_quantity;
549 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
550 let next = first_order_node.next;
551 orderbook.ask.order_pool[head_idx] = None;
552 orderbook.ask.free_list.push(head_idx);
553 orders_touched += 1;
554 if let Some(next_order_idx) = next {
555 price_level.head = Some(next_order_idx);
556 } else {
557 price_level.total_quantity = 0;
558 price_level.head = None;
559 price_level.tail = None;
560 price_level.order_count = 0;
561 break;
562 }
563 } else {
564 first_order_node.current_quantity =
565 first_order_node
566 .current_quantity
567 .checked_sub(fill_quantity)
568 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
569 price_level.total_quantity = price_level
570 .total_quantity
571 .checked_sub(fill_quantity)
572 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
573 fill_quantity = 0;
574 orders_touched += 1;
575 }
576 }
577 None => {
578 return Err(OrderBookError::HeadNotFound);
579 }
580 };
581 } else {
582 break;
583 }
584 }
585 remove_node = price_level.total_quantity == 0;
586 }
587 if remove_node {
588 match orderbook.ask.price_map.pop_first() {
589 Some(_) => {
590 levels_consumed += 1;
591 }
592 None => {
593 break;
594 }
595 };
596 }
597 }
598 let elapsed_time = timer.elapsed().as_micros() as f64;
599 Ok(MatchOutcome {
600 order_index: None,
601 levels_consumed,
602 orders_touched,
603 timer: elapsed_time,
604 })
605 }
606 OrderType::ImmediateOrCancel(market_limit) => {
607 let mut fill_quantity = order.initial_quantity;
608 let mut levels_consumed = 0;
609 let mut orders_touched = 0;
610 while fill_quantity > 0 {
611 let remove_node: bool;
612 {
613 let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
614 break;
615 };
616 if market_limit < *price_node.key() {
617 break;
618 }
619
620 let price_level = price_node.get_mut();
621 while price_level.total_quantity > 0 && fill_quantity > 0 {
622 let head_pointer = price_level.head;
623 if let Some(head_idx) = head_pointer {
624 match orderbook.ask.order_pool[head_idx].as_mut() {
625 Some(first_order_node) => {
626 if fill_quantity >= first_order_node.current_quantity {
627 fill_quantity -= first_order_node.current_quantity;
628 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
629 let next = first_order_node.next;
630 orderbook.ask.order_pool[head_idx] = None;
631 orderbook.ask.free_list.push(head_idx);
632 orders_touched += 1;
633 if let Some(next_order_idx) = next {
634 price_level.head = Some(next_order_idx);
635 } else {
636 price_level.head = None;
637 price_level.total_quantity = 0;
638 price_level.head = None;
639 price_level.tail = None;
640 price_level.order_count = 0;
641 break;
642 }
643 } else {
644 first_order_node.current_quantity =
645 first_order_node
646 .current_quantity
647 .checked_sub(fill_quantity)
648 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
649 price_level.total_quantity = price_level
650 .total_quantity
651 .checked_sub(fill_quantity)
652 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
653 fill_quantity = 0;
654 orders_touched += 1;
655 }
656 }
657 None => {
658 return Err(OrderBookError::HeadNotFound);
659 }
660 };
661 } else {
662 break;
663 }
664 }
665 remove_node = price_level.total_quantity == 0;
666 }
667 if remove_node {
668 match orderbook.ask.price_map.pop_first() {
669 Some(_) => {
670 levels_consumed += 1;
671 }
672 None => {
673 break;
674 }
675 };
676 }
677 }
678 let elapsed_time = timer.elapsed().as_micros() as f64;
679 Ok(MatchOutcome {
680 order_index: None,
681 levels_consumed,
682 orders_touched,
683 timer: elapsed_time,
684 })
685 }
686 OrderType::GoodTillCancel => {
687 let mut fill_quantity = order.initial_quantity;
688 let mut levels_consumed = 0;
689 let mut orders_touched = 0;
690 while fill_quantity > 0 {
691 let remove_node: bool;
692 {
693 let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
694 break;
695 };
696
697 match order.price {
698 Some(price) => {
699 if price < *price_node.key() {
700 break;
701 }
702 }
703 None => {
704 return Err(OrderBookError::PriceNotFound);
705 }
706 }
707 let price_level = price_node.get_mut();
708 while price_level.total_quantity > 0 && fill_quantity > 0 {
709 if let Some(head_idx) = price_level.head {
710 match orderbook.ask.order_pool[head_idx].as_mut() {
711 Some(first_order_node) => {
712 if fill_quantity >= first_order_node.current_quantity {
713 fill_quantity -= first_order_node.current_quantity;
714 price_level.total_quantity = price_level.total_quantity.checked_sub(first_order_node.current_quantity).ok_or_else(|| OrderBookError::QuantityUnderflow)?;
715 let next = first_order_node.next;
716 orderbook.ask.order_pool[head_idx] = None;
717 orderbook.ask.free_list.push(head_idx);
718 orders_touched += 1;
719 if let Some(next_order_idx) = next {
720 price_level.head = Some(next_order_idx);
721 } else {
722 price_level.total_quantity = 0;
723 price_level.head = None;
724 price_level.tail = None;
725 price_level.order_count = 0;
726 break;
727 }
728 } else {
729 first_order_node.current_quantity =
730 first_order_node
731 .current_quantity
732 .checked_sub(fill_quantity)
733 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
734 price_level.total_quantity = price_level
735 .total_quantity
736 .checked_sub(fill_quantity)
737 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
738 fill_quantity = 0;
739 orders_touched += 1;
740 }
741 }
742 None => {
743 return Err(OrderBookError::HeadNotFound);
744 }
745 };
746 } else {
747 break;
748 }
749 }
750 remove_node = price_level.total_quantity == 0;
751 }
752 if remove_node {
753 match orderbook.ask.price_map.pop_first() {
754 Some(_) => {
755 levels_consumed += 1;
756 }
757 None => {
758 break;
759 }
760 };
761 }
762 }
763 if fill_quantity > 0 {
764 let alloted_index = orderbook.create_buy_order(OrderNode {
765 order_id: order.engine_order_id,
766 initial_quantity: order.initial_quantity,
767 current_quantity: fill_quantity,
768 market_limit: order.price.unwrap(),
769 next: None,
770 prev: None,
771 })?;
772
773 let elapsed_time = timer.elapsed().as_micros() as f64;
774 return Ok(MatchOutcome {
775 order_index: Some(alloted_index as u32),
776 levels_consumed,
777 orders_touched,
778 timer: elapsed_time,
779 });
780 }
781 let elapsed_time = timer.elapsed().as_micros() as f64;
782 Ok(MatchOutcome {
783 order_index: None,
784 levels_consumed,
785 orders_touched,
786 timer: elapsed_time,
787 })
788 }
789 OrderType::FillOrKill(limit_price) => {
790 let mut available_quantity: u32 = 0;
791 for (level_price, level) in orderbook.ask.price_map.iter() {
792 if limit_price < *level_price {
793 break;
794 }
795 available_quantity =
796 available_quantity
797 .checked_add(level.total_quantity)
798 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
799 if available_quantity >= order.initial_quantity {
800 break;
801 }
802 }
803
804 if available_quantity < order.initial_quantity {
805 let elapsed_time = timer.elapsed().as_micros() as f64;
806 return Ok(MatchOutcome {
807 order_index: None,
808 levels_consumed: 0,
809 orders_touched: 0,
810 timer: elapsed_time,
811 });
812 }
813
814 let mut fill_quantity = order.initial_quantity;
815 let mut levels_consumed = 0;
816 let mut orders_touched = 0;
817
818 while fill_quantity > 0 {
819 let remove_node: bool;
820 {
821 let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
822 return Err(OrderBookError::PriceLevelEmpty);
823 };
824
825 if limit_price < *price_node.key() {
826 return Err(OrderBookError::UnexpectedReturn);
827 }
828
829 let price_level = price_node.get_mut();
830 while price_level.total_quantity > 0 && fill_quantity > 0 {
831 if let Some(head_idx) = price_level.head {
832 match orderbook.ask.order_pool[head_idx].as_mut() {
833 Some(first_order_node) => {
834 if fill_quantity >= first_order_node.current_quantity {
835 fill_quantity -= first_order_node.current_quantity;
836 price_level.total_quantity = price_level
837 .total_quantity
838 .checked_sub(first_order_node.current_quantity)
839 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
840 let next = first_order_node.next;
841 orderbook.ask.order_pool[head_idx] = None;
842 orderbook.ask.free_list.push(head_idx);
843 orders_touched += 1;
844 if let Some(next_order_idx) = next {
845 price_level.head = Some(next_order_idx);
846 } else {
847 price_level.total_quantity = 0;
848 price_level.head = None;
849 price_level.tail = None;
850 price_level.order_count = 0;
851 break;
852 }
853 } else {
854 first_order_node.current_quantity =
855 first_order_node
856 .current_quantity
857 .checked_sub(fill_quantity)
858 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
859 price_level.total_quantity = price_level
860 .total_quantity
861 .checked_sub(fill_quantity)
862 .ok_or_else(|| OrderBookError::QuantityUnderflow)?;
863 fill_quantity = 0;
864 orders_touched += 1;
865 }
866 }
867 None => {
868 return Err(OrderBookError::HeadNotFound);
869 }
870 };
871 } else {
872 break;
873 }
874 }
875 remove_node = price_level.total_quantity == 0;
876 }
877 if remove_node {
878 orderbook.ask.price_map.pop_first();
879 levels_consumed += 1;
880 }
881 }
882
883 let elapsed_time = timer.elapsed().as_micros() as f64;
884 Ok(MatchOutcome {
885 order_index: None,
886 levels_consumed,
887 orders_touched,
888 timer: elapsed_time,
889 })
890 }
891 }
892 }
893 }
894}