Debian Codegraph @

bgzf/cache/cache.go

raw
1 // Copyright ©2015 The bíogo Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 // Package cache provides basic block cache types for the bgzf package.
6 package cache
7
8 import (
9 "sync"
10
11 "github.com/biogo/hts/bgzf"
12 )
13
14 var (
15 _ Cache = (*LRU)(nil)
16 _ Cache = (*FIFO)(nil)
17 _ Cache = (*Random)(nil)
18 )
19
20 // Free attempts to drop as many blocks from c as needed allow
21 // n successful Put calls on c. It returns a boolean indicating
22 // whether n slots were made available.
23 func Free(n int, c Cache) bool {
24 empty := c.Cap() - c.Len()
25 if n <= empty {
26 return true
27 }
28 c.Drop(n - empty)
29 return c.Cap()-c.Len() >= n
30 }
31
32 // Cache is an extension of bgzf.Cache that allows inspection
33 // and manipulation of the cache.
34 type Cache interface {
35 bgzf.Cache
36
37 // Len returns the number of elements held by
38 // the cache.
39 Len() int
40
41 // Cap returns the maximum number of elements
42 // that can be held by the cache.
43 Cap() int
44
45 // Resize changes the capacity of the cache to n,
46 // dropping excess blocks if n is less than the
47 // number of cached blocks.
48 Resize(n int)
49
50 // Drop evicts n elements from the cache according
51 // to the cache eviction policy.
52 Drop(n int)
53 }
54
55 func insertAfter(pos, n *node) {
56 n.prev = pos
57 pos.next, n.next, pos.next.prev = n, pos.next, n
58 }
59
60 func remove(n *node, table map[int64]*node) {
61 delete(table, n.b.Base())
62 n.prev.next = n.next
63 n.next.prev = n.prev
64 n.next = nil
65 n.prev = nil
66 }
67
68 // NewLRU returns an LRU cache with n slots. If n is less than 1
69 // a nil cache is returned.
70 func NewLRU(n int) Cache {
71 if n < 1 {
72 return nil
73 }
74 c := LRU{
75 table: make(map[int64]*node, n),
76 cap: n,
77 }
78 c.root.next = &c.root
79 c.root.prev = &c.root
80 return &c
81 }
82
83 // LRU satisfies the Cache interface with least recently used eviction
84 // behavior where Unused Blocks are preferentially evicted.
85 type LRU struct {
86 mu sync.RWMutex
87 root node
88 table map[int64]*node
89 cap int
90 }
91
92 type node struct {
93 b bgzf.Block
94
95 next, prev *node
96 }
97
98 // Len returns the number of elements held by the cache.
99 func (c *LRU) Len() int {
100 c.mu.RLock()
101 defer c.mu.RUnlock()
102
103 return len(c.table)
104 }
105
106 // Cap returns the maximum number of elements that can be held by the cache.
107 func (c *LRU) Cap() int {
108 c.mu.RLock()
109 defer c.mu.RUnlock()
110
111 return c.cap
112 }
113
114 // Resize changes the capacity of the cache to n, dropping excess blocks
115 // if n is less than the number of cached blocks.
116 func (c *LRU) Resize(n int) {
117 c.mu.Lock()
118 if n < len(c.table) {
119 c.drop(len(c.table) - n)
120 }
121 c.cap = n
122 c.mu.Unlock()
123 }
124
125 // Drop evicts n elements from the cache according to the cache eviction policy.
126 func (c *LRU) Drop(n int) {
127 c.mu.Lock()
128 c.drop(n)
129 c.mu.Unlock()
130 }
131
132 func (c *LRU) drop(n int) {
133 for ; n > 0 && c.Len() > 0; n-- {
134 remove(c.root.prev, c.table)
135 }
136 }
137
138 // Get returns the Block in the Cache with the specified base or a nil Block
139 // if it does not exist.
140 func (c *LRU) Get(base int64) bgzf.Block {
141 c.mu.Lock()
142 defer c.mu.Unlock()
143
144 n, ok := c.table[base]
145 if !ok {
146 return nil
147 }
148 remove(n, c.table)
149 return n.b
150 }
151
152 // Peek returns a boolean indicating whether a Block exists in the Cache for
153 // the given base offset and the expected offset for the subsequent Block in
154 // the BGZF stream.
155 func (c *LRU) Peek(base int64) (exist bool, next int64) {
156 c.mu.RLock()
157 defer c.mu.RUnlock()
158
159 n, exist := c.table[base]
160 if !exist {
161 return false, -1
162 }
163 next = n.b.NextBase()
164 return exist, next
165 }
166
167 // Put inserts a Block into the Cache, returning the Block that was evicted or
168 // nil if no eviction was necessary and the Block was retained. Unused Blocks
169 // are not retained but are returned if the Cache is full.
170 func (c *LRU) Put(b bgzf.Block) (evicted bgzf.Block, retained bool) {
171 c.mu.Lock()
172 defer c.mu.Unlock()
173
174 var d bgzf.Block
175 if _, ok := c.table[b.Base()]; ok {
176 return b, false
177 }
178 used := b.Used()
179 if len(c.table) == c.cap {
180 if !used {
181 return b, false
182 }
183 d = c.root.prev.b
184 remove(c.root.prev, c.table)
185 }
186 n := &node{b: b}
187 c.table[b.Base()] = n
188 if used {
189 insertAfter(&c.root, n)
190 } else {
191 insertAfter(c.root.prev, n)
192 }
193 return d, true
194 }
195
196 // NewFIFO returns a FIFO cache with n slots. If n is less than 1
197 // a nil cache is returned.
198 func NewFIFO(n int) Cache {
199 if n < 1 {
200 return nil
201 }
202 c := FIFO{
203 table: make(map[int64]*node, n),
204 cap: n,
205 }
206 c.root.next = &c.root
207 c.root.prev = &c.root
208 return &c
209 }
210
211 // FIFO satisfies the Cache interface with first in first out eviction
212 // behavior where Unused Blocks are preferentially evicted.
213 type FIFO struct {
214 mu sync.RWMutex
215 root node
216 table map[int64]*node
217 cap int
218 }
219
220 // Len returns the number of elements held by the cache.
221 func (c *FIFO) Len() int {
222 c.mu.RLock()
223 defer c.mu.RUnlock()
224
225 return len(c.table)
226 }
227
228 // Cap returns the maximum number of elements that can be held by the cache.
229 func (c *FIFO) Cap() int {
230 c.mu.RLock()
231 defer c.mu.RUnlock()
232
233 return c.cap
234 }
235
236 // Resize changes the capacity of the cache to n, dropping excess blocks
237 // if n is less than the number of cached blocks.
238 func (c *FIFO) Resize(n int) {
239 c.mu.Lock()
240 if n < len(c.table) {
241 c.drop(len(c.table) - n)
242 }
243 c.cap = n
244 c.mu.Unlock()
245 }
246
247 // Drop evicts n elements from the cache according to the cache eviction policy.
248 func (c *FIFO) Drop(n int) {
249 c.mu.Lock()
250 c.drop(n)
251 c.mu.Unlock()
252 }
253
254 func (c *FIFO) drop(n int) {
255 for ; n > 0 && c.Len() > 0; n-- {
256 remove(c.root.prev, c.table)
257 }
258 }
259
260 // Get returns the Block in the Cache with the specified base or a nil Block
261 // if it does not exist.
262 func (c *FIFO) Get(base int64) bgzf.Block {
263 c.mu.Lock()
264 defer c.mu.Unlock()
265
266 n, ok := c.table[base]
267 if !ok {
268 return nil
269 }
270 if !n.b.Used() {
271 remove(n, c.table)
272 }
273 return n.b
274 }
275
276 // Peek returns a boolean indicating whether a Block exists in the Cache for
277 // the given base offset and the expected offset for the subsequent Block in
278 // the BGZF stream.
279 func (c *FIFO) Peek(base int64) (exist bool, next int64) {
280 c.mu.RLock()
281 defer c.mu.RUnlock()
282
283 n, exist := c.table[base]
284 if !exist {
285 return false, -1
286 }
287 next = n.b.NextBase()
288 return exist, next
289 }
290
291 // Put inserts a Block into the Cache, returning the Block that was evicted or
292 // nil if no eviction was necessary and the Block was retained. Unused Blocks
293 // are not retained but are returned if the Cache is full.
294 func (c *FIFO) Put(b bgzf.Block) (evicted bgzf.Block, retained bool) {
295 c.mu.Lock()
296 defer c.mu.Unlock()
297
298 var d bgzf.Block
299 if _, ok := c.table[b.Base()]; ok {
300 return b, false
301 }
302 used := b.Used()
303 if len(c.table) == c.cap {
304 if !used {
305 return b, false
306 }
307 d = c.root.prev.b
308 remove(c.root.prev, c.table)
309 }
310 n := &node{b: b}
311 c.table[b.Base()] = n
312 if used {
313 insertAfter(&c.root, n)
314 } else {
315 insertAfter(c.root.prev, n)
316 }
317 return d, true
318 }
319
320 // NewRandom returns a random eviction cache with n slots. If n is less than 1
321 // a nil cache is returned.
322 func NewRandom(n int) Cache {
323 if n < 1 {
324 return nil
325 }
326 return &Random{
327 table: make(map[int64]bgzf.Block, n),
328 cap: n,
329 }
330 }
331
332 // Random satisfies the Cache interface with random eviction behavior
333 // where Unused Blocks are preferentially evicted.
334 type Random struct {
335 mu sync.RWMutex
336 table map[int64]bgzf.Block
337 cap int
338 }
339
340 // Len returns the number of elements held by the cache.
341 func (c *Random) Len() int {
342 c.mu.RLock()
343 defer c.mu.RUnlock()
344
345 return len(c.table)
346 }
347
348 // Cap returns the maximum number of elements that can be held by the cache.
349 func (c *Random) Cap() int {
350 c.mu.RLock()
351 defer c.mu.RUnlock()
352
353 return c.cap
354 }
355
356 // Resize changes the capacity of the cache to n, dropping excess blocks
357 // if n is less than the number of cached blocks.
358 func (c *Random) Resize(n int) {
359 c.mu.Lock()
360 if n < len(c.table) {
361 c.drop(len(c.table) - n)
362 }
363 c.cap = n
364 c.mu.Unlock()
365 }
366
367 // Drop evicts n elements from the cache according to the cache eviction policy.
368 func (c *Random) Drop(n int) {
369 c.mu.Lock()
370 c.drop(n)
371 c.mu.Unlock()
372 }
373
374 func (c *Random) drop(n int) {
375 if n < 1 {
376 return
377 }
378 for k, b := range c.table {
379 if b.Used() {
380 continue
381 }
382 delete(c.table, k)
383 if n--; n == 0 {
384 return
385 }
386 }
387 for k := range c.table {
388 delete(c.table, k)
389 if n--; n == 0 {
390 break
391 }
392 }
393 }
394
395 // Get returns the Block in the Cache with the specified base or a nil Block
396 // if it does not exist.
397 func (c *Random) Get(base int64) bgzf.Block {
398 c.mu.Lock()
399 defer c.mu.Unlock()
400
401 b, ok := c.table[base]
402 if !ok {
403 return nil
404 }
405 delete(c.table, base)
406 return b
407 }
408
409 // Peek returns a boolean indicating whether a Block exists in the Cache for
410 // the given base offset and the expected offset for the subsequent Block in
411 // the BGZF stream.
412 func (c *Random) Peek(base int64) (exist bool, next int64) {
413 c.mu.RLock()
414 defer c.mu.RUnlock()
415
416 n, exist := c.table[base]
417 if !exist {
418 return false, -1
419 }
420 next = n.NextBase()
421 return exist, next
422 }
423
424 // Put inserts a Block into the Cache, returning the Block that was evicted or
425 // nil if no eviction was necessary and the Block was retained. Unused Blocks
426 // are not retained but are returned if the Cache is full.
427 func (c *Random) Put(b bgzf.Block) (evicted bgzf.Block, retained bool) {
428 c.mu.Lock()
429 defer c.mu.Unlock()
430
431 var d bgzf.Block
432 if _, ok := c.table[b.Base()]; ok {
433 return b, false
434 }
435 if len(c.table) == c.cap {
436 if !b.Used() {
437 return b, false
438 }
439 for k, v := range c.table {
440 if v.Used() {
441 continue
442 }
443 delete(c.table, k)
444 d = v
445 goto done
446 }
447 for k, v := range c.table {
448 delete(c.table, k)
449 d = v
450 break
451 }
452 done:
453 }
454 c.table[b.Base()] = b
455 return d, true
456 }
457
458 // StatsRecorder allows a bgzf.Cache to capture cache statistics.
459 type StatsRecorder struct {
460 bgzf.Cache
461
462 mu sync.RWMutex
463 stats Stats
464 }
465
466 // Stats represents statistics of a bgzf.Cache.
467 type Stats struct {
468 Gets int // number of Get operations
469 Misses int // number of cache misses
470 Puts int // number of Put operations
471 Retains int // number of times a Put has resulted in Block retention
472 Evictions int // number of times a Put has resulted in a Block eviction
473 }
474
475 // Stats returns the current statistics for the cache.
476 func (s *StatsRecorder) Stats() Stats {
477 s.mu.RLock()
478 defer s.mu.RUnlock()
479 return s.stats
480 }
481
482 // Reset zeros the statistics kept by the StatsRecorder.
483 func (s *StatsRecorder) Reset() {
484 s.mu.Lock()
485 s.stats = Stats{}
486 s.mu.Unlock()
487 }
488
489 // Get returns the Block in the underlying Cache with the specified base or a nil
490 // Block if it does not exist. It updates the gets and misses statistics.
491 func (s *StatsRecorder) Get(base int64) bgzf.Block {
492 s.mu.Lock()
493 s.stats.Gets++
494 blk := s.Cache.Get(base)
495 if blk == nil {
496 s.stats.Misses++
497 }
498 s.mu.Unlock()
499 return blk
500 }
501
502 // Put inserts a Block into the underlying Cache, returning the Block and eviction
503 // status according to the underlying cache behavior. It updates the puts, retains and
504 // evictions statistics.
505 func (s *StatsRecorder) Put(b bgzf.Block) (evicted bgzf.Block, retained bool) {
506 s.mu.Lock()
507 s.stats.Puts++
508 blk, retained := s.Cache.Put(b)
509 if retained {
510 s.stats.Retains++
511 if blk != nil {
512 s.stats.Evictions++
513 }
514 }
515 s.mu.Unlock()
516 return blk, retained
517 }