Firstly, it's just interesting. Secondly, this is the first practice task on C++ based course by K.I.Vladimirov.
Main structure of cache represents realisation of structure from this source. But LFUDA decision suppose include a technology of dynamic aging, which needed of sorted list of weights (for more information check this article). For this sorting it's be suggested to use red-black-tree from std::map.
- Filling the hashmap from input by hash pair: key and iterator to the list with number of position element with the key in requests (FP = position in the future).
- Cache space is a map (rbtree) which contains number of nodes less than cache's capacity. The nodes are placed by first future position (from left to right = from the nearest to the farest).
- PUSH:
- Cache is full. We need to evict the farest nodes in the future - access to the last element in the map, erase it from the hashmap by its key, erase it from the map and decrease the size of cache
- For requested page we access to it's node by key in hashmap and find the FP. After that there are 2 cases: if FP is more than other FP in the cache (we do not need in eviction - in this cace we do not even need to evict a node if cache is full), and if FP belong to diapazon of cache FPs - insert in rbtree execute for O(log N)
That is all about algorithm in general ideas
- First of all, clone repo:
git clone https://github.com/BileyHarryCopter/LFUDA_BELADY_CACHE.git
cd LFUDA_BELADY_CACHE/
- After that you can make:
cmake -B build
cd build/[cache]
cmake --build .
Where [cache] can be lfuda or belady.
- Congratulations! Now you have executable file which call [./cache]
- From root directory move to test and write down:
./test.sh [cache] [mode]
Where [cache] can be lfuda or belady. [mode] can be two variants: [based] (launch basic test for cache) or any positive integer number [N] (launch test generation of [N] tests)
It is still not ready, because I wanna do it special
* M - capacity of cache