Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 | 2x 2x 2x 2x 10x 10x 10x 10x 10x 10x 13x 13x 13x 13x 1x 13x 7x 7x 1x 6x 6x 6x 6x 4x 4x 4x 4x 3x 3x 1x 1x 2x 2x 1x 1x 1x 1x 1x 1x 5x 1x 1x 1x 1x 1x 1x 10x 1x 14x 14x 11x 3x 14x 14x 11x 6x 6x 6x 6x 6x 6x 6x 6x | import { RBTree } from 'bintrees';
import { compareAscending, IAgedQueue } from './IAgedQueue';
import { Logger } from '../shared/Logger';
export class FIFOAgedQueue<TKey> implements IAgedQueue<TKey> {
private readonly logger = Logger.get(FIFOAgedQueue.name);
private readonly ageLimit?: number;
private readonly ageTree: RBTree<number> = new RBTree(compareAscending);
private readonly ageMap = new Map<TKey, number>();
private readonly ageBuckets = new Map<number, Set<TKey>>();
/**
* @param maxEntries The maximum number of entries to store in the cache, undefined for no max
* @param ageLimit The maximum time to keep entries in minutes
*/
constructor(private readonly maxEntries?: number, ageLimit = 200) {
this.ageLimit = ageLimit * 1000 * 60;
}
/**
* @param key The key to add
* @param age The age if explicitly or default if undefined
*/
addOrReplace(key: TKey, age?: number): void {
const existingAge = this.ageMap.get(key);
const newAge = age ? age : this.getInitialAge(key);
this.ageMap.set(key, newAge);
if (existingAge !== undefined) {
this.deleteBucket(existingAge, key);
}
this.addBucket(newAge, key);
}
/**
* @return The next key in order or null if there is no key
*/
next(): TKey | null {
const minAge = this.ageTree.min();
if (!minAge) {
return null;
}
const minBucket = this.ageBuckets.get(minAge);
Iif (minBucket === undefined) {
return null;
}
const iterator = minBucket.values().next();
return iterator.value as TKey;
}
/**
* @param key The key to delete
*/
delete(key: TKey): void {
const age = this.ageMap.get(key);
Iif (age === undefined) {
return;
}
this.ageMap.delete(key);
this.deleteBucket(age, key);
}
/**
* @return True if the next key in order is expired and should be removed
*/
isNextExpired(): boolean {
Iif (!this.maxEntries && !this.ageLimit) {
return false;
}
if (this.maxEntries && this.ageMap.size > this.maxEntries) {
this.logger.debug(`Max Entries Exceeded: ${this.maxEntries}`);
return true;
}
const next = this.next();
if (next === null) {
return false;
}
if (this.ageLimit) {
const age = this.ageMap.get(next);
if (age !== undefined && age + this.ageLimit < Date.now()) {
this.logger.debug(`Age Limit Exceeded: age=${age},limit=${this.ageLimit}`);
return true;
}
}
return false;
}
/**
* @param key The key we want a default for
* @return The default age that will very by algorithm
*/
getInitialAge(_key: TKey): number {
return Date.now();
}
/**
* @param key Advance the age of the specified key
*/
updateAge(key: TKey): void {
const oldAge = this.ageMap.get(key);
Iif (oldAge === undefined) {
return;
}
const newAge = Date.now();
this.ageMap.set(key, newAge);
this.deleteBucket(oldAge, key);
this.addBucket(newAge, key);
}
/**
* @param ageA The first age to compare
* @param ageB The second age to compare
* @return 0 if same order, positive if ageA after ageB, negative if ageA before ageB
*/
compare = compareAscending;
/**
* @return The number of keys in the queue
*/
size(): number {
return this.ageMap.size;
}
private addBucket(age: number, key: TKey): void {
const bucket = this.ageBuckets.get(age);
if (bucket === undefined) {
this.ageBuckets.set(age, new Set([key]));
} else {
bucket.add(key);
}
const found = this.ageTree.find(age);
if (found === null) {
this.ageTree.insert(age);
}
}
private deleteBucket(age: number, key: TKey): void {
const bucket = this.ageBuckets.get(age);
Iif (bucket === undefined) {
return;
}
bucket.delete(key);
Iif (bucket.size > 0) {
return;
}
this.ageBuckets.delete(age);
const found = this.ageTree.find(age);
if (found !== null) {
this.ageTree.remove(age);
}
}
}
|