diff options
author | Leonid Logvinov <logvinov.leon@gmail.com> | 2017-11-21 04:40:53 +0800 |
---|---|---|
committer | Leonid Logvinov <logvinov.leon@gmail.com> | 2017-11-21 04:40:53 +0800 |
commit | 5788b90c522b63b53f5e8480f2b357ee24bb08a3 (patch) | |
tree | 6d74945b10e65b316c5f8906e56c18fa39e0cd01 /packages/0x.js/src/order_watcher | |
parent | 71475d3ceafd8f1a4a76d1e5b49ff0d186bacd9b (diff) | |
download | dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar.gz dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar.bz2 dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar.lz dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar.xz dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.tar.zst dexon-sol-tools-5788b90c522b63b53f5e8480f2b357ee24bb08a3.zip |
Remove custom heap and use bintrees
Diffstat (limited to 'packages/0x.js/src/order_watcher')
-rw-r--r-- | packages/0x.js/src/order_watcher/expiration_watcher.ts | 22 | ||||
-rw-r--r-- | packages/0x.js/src/order_watcher/order_state_watcher.ts | 2 |
2 files changed, 14 insertions, 10 deletions
diff --git a/packages/0x.js/src/order_watcher/expiration_watcher.ts b/packages/0x.js/src/order_watcher/expiration_watcher.ts index 71199e75f..7d6f8df65 100644 --- a/packages/0x.js/src/order_watcher/expiration_watcher.ts +++ b/packages/0x.js/src/order_watcher/expiration_watcher.ts @@ -1,9 +1,9 @@ import * as _ from 'lodash'; import {BigNumber} from 'bignumber.js'; +import {RBTree} from 'bintrees'; import {utils} from '../utils/utils'; import {intervalUtils} from '../utils/interval_utils'; import {SignedOrder, ZeroExError} from '../types'; -import {Heap} from '../utils/heap'; import {ZeroEx} from '../0x'; const DEFAULT_EXPIRATION_MARGIN_MS = 0; @@ -14,7 +14,7 @@ const DEFAULT_ORDER_EXPIRATION_CHECKING_INTERVAL_MS = 50; * It stores them in a min heap by expiration time and checks for expired ones every `orderExpirationCheckingIntervalMs` */ export class ExpirationWatcher { - private orderHashHeapByExpiration: Heap<string>; + private orderHashRBTreeByExpiration: RBTree<string>; private expiration: {[orderHash: string]: BigNumber} = {}; private callbackIfExists?: (orderHash: string) => void; private orderExpirationCheckingIntervalMs: number; @@ -27,7 +27,8 @@ export class ExpirationWatcher { this.orderExpirationCheckingIntervalMs = expirationMarginIfExistsMs || DEFAULT_ORDER_EXPIRATION_CHECKING_INTERVAL_MS; const scoreFunction = (orderHash: string) => this.expiration[orderHash].toNumber(); - this.orderHashHeapByExpiration = new Heap(scoreFunction); + const comparator = (lhs: string, rhs: string) => scoreFunction(lhs) - scoreFunction(rhs); + this.orderHashRBTreeByExpiration = new RBTree(comparator); } public subscribe(callback: (orderHash: string) => void): void { if (!_.isUndefined(this.callbackIfExists)) { @@ -48,20 +49,23 @@ export class ExpirationWatcher { } public addOrder(orderHash: string, expirationUnixTimestampMs: BigNumber): void { this.expiration[orderHash] = expirationUnixTimestampMs; - // We don't remove hashes from the heap on order remove because it's slow (linear). - // We just skip them later if the order was already removed from the order watcher. - this.orderHashHeapByExpiration.push(orderHash); + this.orderHashRBTreeByExpiration.insert(orderHash); + } + public removeOrder(orderHash: string): void { + this.orderHashRBTreeByExpiration.remove(orderHash); + delete this.expiration[orderHash]; } private pruneExpiredOrders(): void { const currentUnixTimestampMs = utils.getCurrentUnixTimestampMs(); while ( - this.orderHashHeapByExpiration.size() !== 0 && - this.expiration[this.orderHashHeapByExpiration.head()].lessThan( + this.orderHashRBTreeByExpiration.size !== 0 && + this.expiration[this.orderHashRBTreeByExpiration.min()].lessThan( currentUnixTimestampMs.plus(this.expirationMarginMs), ) && !_.isUndefined(this.callbackIfExists) ) { - const orderHash = this.orderHashHeapByExpiration.pop(); + const orderHash = this.orderHashRBTreeByExpiration.min(); + this.orderHashRBTreeByExpiration.remove(orderHash); delete this.expiration[orderHash]; this.callbackIfExists(orderHash); } diff --git a/packages/0x.js/src/order_watcher/order_state_watcher.ts b/packages/0x.js/src/order_watcher/order_state_watcher.ts index 3659fc6e2..975679f57 100644 --- a/packages/0x.js/src/order_watcher/order_state_watcher.ts +++ b/packages/0x.js/src/order_watcher/order_state_watcher.ts @@ -95,7 +95,6 @@ export class OrderStateWatcher { assert.isValidSignature(orderHash, signedOrder.ecSignature, signedOrder.maker); this._orderByOrderHash[orderHash] = signedOrder; this.addToDependentOrderHashes(signedOrder, orderHash); - // We don't remove orders from expirationWatcher because heap removal is linear. We just skip it later const expirationUnixTimestampMs = signedOrder.expirationUnixTimestampSec.times(1000); this._expirationWatcher.addOrder(orderHash, expirationUnixTimestampMs); } @@ -111,6 +110,7 @@ export class OrderStateWatcher { } delete this._orderByOrderHash[orderHash]; this.removeFromDependentOrderHashes(signedOrder.maker, signedOrder.makerTokenAddress, orderHash); + this._expirationWatcher.removeOrder(orderHash); } /** * Starts an orderStateWatcher subscription. The callback will be called every time a watched order's |