KVStore/cache.cpp at master · Rajiv2605/KVStore · GitHub

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <bits/stdc++.h>
#include "storage.hpp"

using namespace std;

int Storage::check_hit(string key)
{
	for(int i=0;i<cache_set;i++)
	{
		if(LLC[i].key== key && LLC[i].valid==1){
			if (!policy.compare("lru"))
				llc_lru_update(i);
			else if (!policy.compare("lfu"))
				llc_lfu_update(i);
			return i;
		}

	}
	return -1;
}
int Storage::llc_lru_find_victim()
{
	for(int i=0;i<cache_set;i++)
		if(LLC[i].valid == 0)
			return i;
	for(int i=0;i<cache_set;i++)
	{
		if(LLC[i].lru == cache_set-1)
			return i;
	}

	assert(0);
}

int Storage::llc_lfu_find_victim()
{
	int min= 9999999,index;
	for(int i=0;i<cache_set;i++)
		if(LLC[i].valid == 0)
			return i;
	for(int i=0;i<cache_set;i++)
	{
		if(LLC[i].lfu <= min)
		{
			min = LLC[i].lfu;
			index = i;
		}
	}
	return index;

}

void Storage::llc_lru_update(int index)
{
	for(int i=0;i<cache_set;i++)
		if(LLC[i].lru < LLC[index].lru && LLC[i].valid == 1)
			 	LLC[i].lru++;
	LLC[index].lru=0;
}

void Storage::llc_lfu_update(int index)
{
	LLC[index].lfu++;
}

void Storage::fill_cache(string key,string value)
{
	int index;
	if(check_hit(key) > -1)
	{
		assert(0);
	}
	else
	{
		if(!policy.compare("lru"))
		{
			index = llc_lru_find_victim();
			LLC[index].valid=1;
			LLC[index].lru=(cache_set-1);
			llc_lru_update(index);
		}
		else if(!policy.compare("lfu"))
		{
			index = llc_lfu_find_victim();
			LLC[index].valid=1;
			LLC[index].lfu=0;
			llc_lfu_update(index);
		}
		LLC[index].valid=1;
		LLC[index].key=key;
		LLC[index].value=value;
	}
}
void Storage::print_cache()
{
	cout<<"\nCache state:\n";
	for(int i=0;i<cache_set;i++)
		if(LLC[i].valid == 1)
			cout<<"Set : "<<i<<" key: "<<LLC[i].key<<" value : "<<LLC[i].value<<" lru : "<<LLC[i].lru<<" lfu : " <<LLC[i].lfu<<endl;
}
/*int main()
{
string key;
string value;
int count =1;
while(count == 1){
	cout<<"Enter key  "<<endl;
	cin>>key;
	cout<<"Enter value  "<<endl;
	cin>>value;
	fill_cache(key,value);
	print_cache();
	cout<<"Do you want to enter more : ";
	cin>>count;
}
}*/