1371835425

Build Type

github

Committed by GitHub

Commit Message

Merge 31765f006 into e37f6fa7c

Pull Request Pull Request #371: fix(bg-flamegraph): ignore comment lines

Run Details

1032 of 2611 branches covered (39.53%)

Branch coverage included in aggregate %.

1 of 1 new or added line in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

2408 of 5765 relevant lines covered (41.77%)

6013.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.68

/src/lib/lru-cache.ts

class ListNode<V> {
  prev: ListNode<V> | null = null
  next: ListNode<V> | null = null
  constructor(readonly data: V) {}
}

export class List<V> {
  private head: ListNode<V> | null = null
  private tail: ListNode<V> | null = null
  private size: number = 0
  constructor() {}

  getHead(): ListNode<V> | null {
    return this.head
  }
  getTail(): ListNode<V> | null {
    return this.tail
  }
  getSize(): number {
    return this.size
  }

  append(node: ListNode<V>): void {
    if (!this.tail) {
      this.head = this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }
    this.size++
  }

  prepend(node: ListNode<V>): ListNode<V> {
    if (!this.head) {
      this.head = this.tail = node
    } else {
      this.head.prev = node
      node.next = this.head
      this.head = node
    }
    this.size++
    return node
  }

  pop(): ListNode<V> | null {
    if (!this.tail) {
      return null
    } else {
      const ret = this.tail
      if (ret.prev) {
        this.tail = ret.prev
        this.tail.next = null
      } else {
        this.head = this.tail = null
      }
      this.size--
      ret.prev = null
      return ret
    }
  }

  dequeue(): ListNode<V> | null {
    if (!this.head) {
      return null
    } else {
      const ret = this.head
      if (ret.next) {
        this.head = ret.next
        this.head.prev = null
      } else {
        this.head = this.tail = null
      }
      this.size--
      ret.next = null
      return ret
    }
  }

  remove(node: ListNode<V>): void {
    if (node.prev == null) {
      this.dequeue()
    } else if (node.next == null) {
      this.pop()
    } else {
      // Neither first nor last, should be safe to just link
      // neighbours.
      node.next.prev = node.prev
      node.prev.next = node.next
      node.next = null
      node.prev = null
      this.size--
    }
  }
}

interface LRUCacheNode<K, V> {
  value: V
  listNode: ListNode<K>
}

export class LRUCache<K, V> {
  private list = new List<K>()
  private map = new Map<K, LRUCacheNode<K, V>>()

  constructor(private capacity: number) {}

  has(key: K): boolean {
    return this.map.has(key)
  }

  get(key: K): V | null {
    const node = this.map.get(key)
    if (!node) {
      return null
    }
    // Bring node to the front of the list
    this.list.remove(node.listNode)
    this.list.prepend(node.listNode)

    return node ? node.value : null
  }

  getSize() {
    return this.list.getSize()
  }

  getCapacity() {
    return this.capacity
  }

  insert(key: K, value: V) {
    const node = this.map.get(key)
    if (node) {
      this.list.remove(node.listNode)
    }
    // Evict old entries when out of capacity
    while (this.list.getSize() >= this.capacity) {
      this.map.delete(this.list.pop()!.data)
    }
    const listNode = this.list.prepend(new ListNode(key))
    this.map.set(key, {value, listNode})
  }

  getOrInsert(key: K, f: (key: K) => V): V {
    let value = this.get(key)
    if (value == null) {
      value = f(key)
      this.insert(key, value)
    }
    return value
  }

  removeLRU(): [K, V] | null {
    const oldest = this.list.pop()
    if (!oldest) return null
    const key = oldest.data
    const value = this.map.get(key)!.value
    this.map.delete(key)
    return [key, value]
  }

  clear() {
    this.list = new List<K>()
    this.map = new Map<K, LRUCacheNode<K, V>>()
  }
}

1	class ListNode<V> {
2	prev: ListNode<V> \| null = null	3,106✔
3	next: ListNode<V> \| null = null	3,106✔
4	constructor(readonly data: V) {}	3,106✔
5	}
6
7	export class List<V> {	3✔
8	private head: ListNode<V> \| null = null	3,003✔
9	private tail: ListNode<V> \| null = null	3,003✔
10	private size: number = 0	3,003✔
11	constructor() {}
12
13	getHead(): ListNode<V> \| null {
14	return this.head	×
15	}
16	getTail(): ListNode<V> \| null {
17	return this.tail	×
18	}
19	getSize(): number {
20	return this.size	4,691✔
21	}
22
23	append(node: ListNode<V>): void {
24	if (!this.tail) {	×
25	this.head = this.tail = node	×
26	} else {
27	this.tail.next = node	×
28	node.prev = this.tail	×
29	this.tail = node	×
30	}
31	this.size++	×
32	}
33
34	prepend(node: ListNode<V>): ListNode<V> {
35	if (!this.head) {	3,284✔
36	this.head = this.tail = node	2,255✔
37	} else {
38	this.head.prev = node	1,029✔
39	node.next = this.head	1,029✔
40	this.head = node	1,029✔
41	}
42	this.size++	3,284✔
43	return node	3,284✔
44	}
45
46	pop(): ListNode<V> \| null {
47	if (!this.tail) {	1,602✔
48	return null	1,029✔
49	} else {
50	const ret = this.tail	573✔
51	if (ret.prev) {	573✔
52	this.tail = ret.prev	178✔
53	this.tail.next = null	178✔
54	} else {
55	this.head = this.tail = null	395✔
56	}
57	this.size--	573✔
58	ret.prev = null	573✔
59	return ret	573✔
60	}
61	}
62
63	dequeue(): ListNode<V> \| null {
64	if (!this.head) {	204!
65	return null	×
66	} else {
67	const ret = this.head	204✔
68	if (ret.next) {	204✔
69	this.head = ret.next	57✔
70	this.head.prev = null	57✔
71	} else {
72	this.head = this.tail = null	147✔
73	}
74	this.size--	204✔
75	ret.next = null	204✔
76	return ret	204✔
77	}
78	}
79
80	remove(node: ListNode<V>): void {
81	if (node.prev == null) {	264✔
82	this.dequeue()	204✔
83	} else if (node.next == null) {	60✔
84	this.pop()	50✔
85	} else {
86	// Neither first nor last, should be safe to just link
87	// neighbours.
88	node.next.prev = node.prev	10✔
89	node.prev.next = node.next	10✔
90	node.next = null	10✔
91	node.prev = null	10✔
92	this.size--	10✔
93	}
94	}
95	}
96
97	interface LRUCacheNode<K, V> {
98	value: V
99	listNode: ListNode<K>
100	}
101
102	export class LRUCache<K, V> {	3✔
103	private list = new List<K>()	3,003✔
104	private map = new Map<K, LRUCacheNode<K, V>>()	3,003✔
105
106	constructor(private capacity: number) {}	3,003✔
107
108	has(key: K): boolean {
109	return this.map.has(key)	1,603✔
110	}
111
112	get(key: K): V \| null {
113	const node = this.map.get(key)	3,084✔
114	if (!node) {	3,084✔
115	return null	2,906✔
116	}
117	// Bring node to the front of the list
118	this.list.remove(node.listNode)	178✔
119	this.list.prepend(node.listNode)	178✔
120
121	return node ? node.value : null	178!
122	}
123
124	getSize() {
125	return this.list.getSize()	1,585✔
126	}
127
128	getCapacity() {
129	return this.capacity	×
130	}
131
132	insert(key: K, value: V) {
133	const node = this.map.get(key)	3,106✔
134	if (node) {	3,106✔
135	this.list.remove(node.listNode)	86✔
136	}
137	// Evict old entries when out of capacity
138	while (this.list.getSize() >= this.capacity) {	3,106✔
UNCOV 139	this.map.delete(this.list.pop()!.data)	×
140	}
141	const listNode = this.list.prepend(new ListNode(key))	3,106✔
142	this.map.set(key, {value, listNode})	3,106✔
143	}
144
145	getOrInsert(key: K, f: (key: K) => V): V {
146	let value = this.get(key)	1,570✔
147	if (value == null) {	1,570✔
148	value = f(key)	1,490✔
149	this.insert(key, value)	1,490✔
150	}
151	return value	1,570✔
152	}
153
154	removeLRU(): [K, V] \| null {
155	const oldest = this.list.pop()	1,552✔
156	if (!oldest) return null	1,552✔
157	const key = oldest.data	523✔
158	const value = this.map.get(key)!.value	523✔
159	this.map.delete(key)	523✔
160	return [key, value]	523✔
161	}
162
163	clear() {
164	this.list = new List<K>()	×
165	this.map = new Map<K, LRUCacheNode<K, V>>()	×
166	}
167	}

jlfwong / speedscope / 1371835425

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous