top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to implement Least Recently Used Algorithm using C/C++ ??

+4 votes
1,476 views

How to implement least recent use for the numbers displayed on phone screen ??

posted Oct 17, 2013 by Vikas Upadhyay

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
It would be identical to least recently used page replacement algorithm, the only difference would be that you may need to change the page with phone number.
LRU can be implemented by using Doubly linked list with nodes also inserted in Hash. Whenever an element is used, use the hash table to get the address of the Node in the linked list, remove it from the doubly linked list and insert at first place. To get the recently used element access first node. To insert new element which is not present in Hash, insert the element at the beginning of the list and then update Hash Table accordingly.

1 Answer

0 votes

Following is the code for LRU cache in C++, let me know if you need C implementation also.

#include <iostream>
#include <vector>
#include <hash_map>

using namespace std;
using namespace stdext;

template<class K, class T>
struct LRUCacheEntry
{
    K key;
    T data;
    LRUCacheEntry* prev;
    LRUCacheEntry* next;
};

template<class K, class T>
class LRUCache
{
private:
    hash_map< K, LRUCacheEntry<K,T>* >  _mapping;
    vector< LRUCacheEntry<K,T>* >       _freeEntries;
    LRUCacheEntry<K,T> *            head;
    LRUCacheEntry<K,T> *            tail;
    LRUCacheEntry<K,T> *            entries;
public:
    LRUCache(size_t size){
        entries = new LRUCacheEntry<K,T>[size];
        for (int i=0; i<size; i++)
            _freeEntries.push_back(entries+i);
        head = new LRUCacheEntry<K,T>;
        tail = new LRUCacheEntry<K,T>;
        head->prev = NULL;
        head->next = tail;
        tail->next = NULL;
        tail->prev = head;
    }
    ~LRUCache()
    {
        delete head;
        delete tail;
        delete [] entries;
    }
    void put(K key, T data)
    {
        LRUCacheEntry<K,T>* node = _mapping[key];
        if(node)
        {
            // refresh the link list
            detach(node);
            node->data = data;
            attach(node);
        }
        else{
            if ( _freeEntries.empty() )
            {
                node = tail->prev;
                detach(node);
                _mapping.erase(node->key);
                node->data = data;
                node->key = key;
                attach(node);
            }
            else{
                node = _freeEntries.back();
                _freeEntries.pop_back();
                node->key = key;
                node->data = data;
                _mapping[key] = node;
                attach(node);
            }
        }
    }

    T get(K key)
    {
        LRUCacheEntry<K,T>* node = _mapping[key];
        if(node)
        {
            detach(node);
            attach(node);
            return node->data;
        }
        else return NULL;
    }

private:
    void detach(LRUCacheEntry<K,T>* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void attach(LRUCacheEntry<K,T>* node)
    {
        node->next = head->next;
        node->prev = head;
        head->next = node;
        node->next->prev = node;
    }
};
answer Oct 18, 2013 by Luv Kumar
Similar Questions
+1 vote

JVM provides garbage collector. Can we do in C ? And what are the efficient ways to implement it in C lang ?

+4 votes

Say you have only this structure only to implement Doubly LL

struct Node
{
   int val;
   Node* p;
};
+7 votes

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11      

0       16      23      31      16      7

67      5       4       23      21      19

Answer

1       6       8       9       0  ----> 3
                                         |
4       9       -5      5       11      13
                                         |
8       9       44      23      15      -20
                                         |
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11     
|
0       16      23      31      16        7

67      5       4       23      21       19
+2 votes

using adjacency matrix representation of graph?

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...