A simple cache simulator lib
We introduce an LRU 2C-array algorithm; it is an efficient method for implementing a cache eviction policy using a fixed-size array; it is particularly suitable for scenarios where memory constraints prevent the use of linked lists.
Abstract
We introduce an LRU 2C-array algorithm; it is an efficient method for implementing a cache eviction policy using a fixed-size array; it is particularly suitable for scenarios where memory constraints prevent the use of linked lists.
/*
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |x| |x| |x| | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
0 ^ ^
| head ->
tail ->
head points to first unoccupied entry
tail may point to empty entry
*/
- Instead of using a linked list, the algorithm keeps an array A of size 2C, where C represents the cache size.
- Array A stores items (e.g. pointers) in the cache and NULL values to indicate empty slots.
- Keeps a hash table H to store integer indexes of the items in A.
- ‘head’ points to the first unoccupied entry in A, and ‘tail’ points to the oldest item in A, might be NULL.
Available at GitHub.