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
|
LRU Design
==========
This got slightly complex, because I tried to be clever. But the concept is easy, a
list and an unordered map keeps the LRU state.
+-----------------------+ +----------------------------------+
| LRUList | | LRUMap |
| ------- | | ------ |
|+---------------------+| |+--------------------------------+|
+---------------------+ +---------------------+ || LRUEntry <+----+| {LRUHash *, LRUList::iterator} ||
| LRUHash | | LRUEntry | |+---------------------+| |+--------------------------------+|
| -------- |<--+ -------- |<--+| LRUEntry <+----+| {LRUHash *, LRUList::iterator} ||
| u_char _hash[20] | | <LRUHash, unsigned> | |+---------------------+| |+--------------------------------+|
+---------------------+ +---------------------+ || LRUEntry <+----+| {LRUHash *, LRUList::iterator} ||
+-----------------+ |+---------------------+| |+--------------------------------+|
| first = LRUHash | | | | |
|second = unsigned| | * | | * |
+-----------------+ | * | | * |
| * | | * |
| | | |
|+---------------------+| |+--------------------------------+|
|| LRUEntry || || {LRUHash *, LRUList::iterator} ||
|+---------------------+| |+--------------------------------+|
+-----------------------+ +----------------------------------+
+--------------------------+
| first = LRUHash* |
|second = LRUList::iterator|
+--------------------------+
|
