Implementing LRU cache














































Implementing LRU cache



#include<iostream>
using namespace std;
struct node
{
int data;
node *rlink,*llink;
}*t,*h,*n,*s;
class lru
{
int a,fsize,i,x;
public:
lru()
{
  cout<<"\nEnter total number of caches";
  cin>>a;
  cout<<"\nEnter the frame size";
  cin>>fsize;
  h = new node;
  h->rlink=NULL;
  h->llink=NULL;
  h->data=0;
  for(i=1;i<=a;i++)
  {
    cout<<"\nEnter the number";
    cin>>x;
    if(i>=fsize)
    {
       del_beg ();
       ins_end(x);
    }
    else 
    {
     ins_end(x);
    }
    cout<<"\n"<<x<<"is allocated";
  }
}
void ins_end(int x)
{
   s=h;
   while(s->rlink != NULL)
        s=s->rlink;
   n=new node;
   n->data=x;
   n->rlink=NULL;
   s->llink=n;
}
void del_beg()
{
  s=h->rlink;
  h->rlink=s->rlink;
  delete s;
}
void print()
{
  s=h->rlink;
  while(s != NULL)
  {
    cout<<s->data;
    s=s->rlink;
  }
}
};
int main()
{
lru r;
cout<<"\nAfter Inserting all caches";
r.print();
return 0;
}


More Articles of Ram Prasath:

Name Views Likes
Implementing LRU cache 111 1

Comments

  • Ram
    24-Oct-2019 08:37:42 PM
    LRU Cache Stands for Least Recently Used Cache. Which evict least recent used entry. As cache purpose is to provide fast and efficient way of retrieving data.
     
    Main Logic is using Double Linked List , If frame is not full the entry is inserted in the end else,first delete the first entry and insert the new entry at end.

    In my program,I use Double Linked List as Data Structure.

    I used a structure named 'node' used for creating node. 'data, rlink, llink' are the data members used for Entry, Right Link, Left Link respectively.

    A class named 'lru' is used to implement LRU. In that class a constructor is used. member functions 'ins_end(), del_beg() and print()' are used. Member functions 'n, fsize, i, x' for total number of caches, frame size, iteration, data respectively.

    In Constructor, First read 'n' then 'fsize'. Then, header node is created. Using 'for' loop 'n' entries are read one by one immediately inserted in the frame.

    This program read the inputs and give the output at last.

    Input and Output:
    Enter total number of caches 10
    Enter the frame size 3

    Enter the number 7
    7 is allocated
    Enter the number 0
    0 is allocated
    Enter the number 1
    1 is allocated
    Enter the number 2
    2 is allocated
    Enter the number 0
    0 is allocated
    Enter the number 3
    3 is allocated
    Enter the number 4
    4 is allocated
    Enter the number 2
    2 is allocated
    Enter the number 3
    3 is allocated
    Enter the number 0
    0 is allocated
    After inserting all caches
    2     3     0