others::Cache::LRUCache< K, V > Class Template Reference

LRUCache. More...

Collaboration diagram for others::Cache::LRUCache< K, V >:

Public Member Functions
	LRUCache (int _capacity)
	Constructor, Initialize the head and tail pointers to nullptr and initialize the _capacity of the cache.
void	put (K key, V value)
	upsert a key-value pair
V	get (K key)
	get the value of the key-value pair if exists
int	size () const
	Returns the number of items present in the cache.
int	capacity () const
	Returns the total capacity of the cache.
bool	empty () const
	returns whether the cache is empty or not
	~LRUCache ()
	destructs the cache, iterates on the map and deletes every node present in the cache.

Private Member Functions
void	push_front (CacheNode< K, V > *node_ptr)
	push the node to the front of the linked list.
void	make_recent (CacheNode< K, V > *node_ptr)
	move the existing node in the list to the beginning of the list.
void	pop_back ()
	pop the last node in the linked list.

Private Attributes
CacheNode< K, V > *	head
	head of the doubly linked list
CacheNode< K, V > *	tail
	tail of the doubly linked list
std::uint32_t	_capacity
	maximum capacity of the cache
std::unordered_map< K, CacheNode< K, V > * >	node_map
	maps the key to the node address

Detailed Description

template<typename K, typename V>
class others::Cache::LRUCache< K, V >

LRUCache.

Template Parameters

K	type of key in the LRU
V	type of value in the LRU

Definition at line 61 of file lru_cache2.cpp.

Constructor & Destructor Documentation

LRUCache()

template<typename K, typename V>

others::Cache::LRUCache< K, V >::LRUCache ( int _capacity )

inlineexplicit

Constructor, Initialize the head and tail pointers to nullptr and initialize the _capacity of the cache.

Parameters

_capacity

Total capacity of the cache

Definition at line 75 of file lru_cache2.cpp.

        : head(nullptr), tail(nullptr), _capacity(_capacity) {}

~LRUCache()

template<typename K, typename V>

others::Cache::LRUCache< K, V >::~LRUCache ( )

inline

destructs the cache, iterates on the map and deletes every node present in the cache.

Definition at line 205 of file lru_cache2.cpp.

                {
        auto it = node_map.begin();
        while (it != node_map.end()) {
            delete it->second;
            ++it;
        }
    }

Member Function Documentation

capacity()

template<typename K, typename V>

int others::Cache::LRUCache< K, V >::capacity ( ) const

inline

Returns the total capacity of the cache.

Returns

Total capacity of the cache

Definition at line 193 of file lru_cache2.cpp.

{ return _capacity; }

empty()

template<typename K, typename V>

bool others::Cache::LRUCache< K, V >::empty ( ) const

inline

returns whether the cache is empty or not

Returns

true if the cache is empty, false otherwise.

Definition at line 199 of file lru_cache2.cpp.

{ return node_map.empty(); }

get()

template<typename K, typename V>

V others::Cache::LRUCache< K, V >::get ( K key )

inline

get the value of the key-value pair if exists

Parameters

key	key of the key-value pair

Returns

the value mapped to the given key

Exceptions

exception

is thrown if the key is not present in the cache

Definition at line 172 of file lru_cache2.cpp.

                 {
        if (!node_map.count(key)) {
            throw std::runtime_error("key is not present in the cache");
        }
 
        // move node to the beginning of the list
        V value = node_map[key]->data.second;
        make_recent(node_map[key]);
        return value;
    }

make_recent()

template<typename K, typename V>

void others::Cache::LRUCache< K, V >::make_recent ( CacheNode< K, V > * node_ptr )

inlineprivate

move the existing node in the list to the beginning of the list.

Parameters

node_ptr

node to be moved to the beginning.

Definition at line 99 of file lru_cache2.cpp.

                                                {
        if (head == node_ptr) {
            return;
        }
 
        CacheNode<K, V> *prev = node_ptr->prev;
        CacheNode<K, V> *next = node_ptr->next;
 
        prev->next = next;
        if (next) {
            next->prev = prev;
        } else {
            tail = prev;
        }
 
        node_ptr->prev = nullptr;
        node_ptr->next = nullptr;
        push_front(node_ptr);
    }

pop_back()

template<typename K, typename V>

void others::Cache::LRUCache< K, V >::pop_back ( )

inlineprivate

pop the last node in the linked list.

Definition at line 122 of file lru_cache2.cpp.

                    {
        if (!head) {
            return;
        }
        if (head == tail) {
            delete head;
            head = nullptr;
            tail = nullptr;
            return;
        }
 
        CacheNode<K, V> *temp = tail;
        tail = tail->prev;
        tail->next = nullptr;
        delete temp;
    }

push_front()

template<typename K, typename V>

void others::Cache::LRUCache< K, V >::push_front ( CacheNode< K, V > * node_ptr )

inlineprivate

push the node to the front of the linked list.

Parameters

node_ptr

the node to be pushed

Definition at line 83 of file lru_cache2.cpp.

                                               {
        if (!head) {
            head = node_ptr;
            tail = node_ptr;
            return;
        }
 
        node_ptr->next = head;
        head->prev = node_ptr;
        head = node_ptr;
    }

put()

template<typename K, typename V>

void others::Cache::LRUCache< K, V >::put ( K key, V value )

inline

upsert a key-value pair

Parameters

key	key of the key-value pair
value	value of the key-value pair

Definition at line 145 of file lru_cache2.cpp.

                             {
        // update the value if key already exists
        if (node_map.count(key)) {
            node_map[key]->data.second = value;
            make_recent(node_map[key]);
            return;
        }
 
        // if the cache is full
        // remove the least recently used item
        if (node_map.size() == _capacity) {
            node_map.erase(tail->data.first);
            pop_back();
        }
 
        CacheNode<K, V> *newNode = new CacheNode<K, V>({key, value});
 
        node_map[key] = newNode;
        push_front(newNode);
    }

size()

template<typename K, typename V>

int others::Cache::LRUCache< K, V >::size ( ) const

inline

Returns the number of items present in the cache.

Returns

number of items in the cache

Definition at line 187 of file lru_cache2.cpp.

{ return node_map.size(); }

Member Data Documentation

_capacity

template<typename K, typename V>

std::uint32_t others::Cache::LRUCache< K, V >::_capacity

private

maximum capacity of the cache

Definition at line 64 of file lru_cache2.cpp.

head

template<typename K, typename V>

CacheNode<K, V>* others::Cache::LRUCache< K, V >::head

private

head of the doubly linked list

Definition at line 62 of file lru_cache2.cpp.

node_map

template<typename K, typename V>

std::unordered_map<K, CacheNode<K, V> *> others::Cache::LRUCache< K, V >::node_map

private

maps the key to the node address

Definition at line 67 of file lru_cache2.cpp.

tail

template<typename K, typename V>

CacheNode<K, V>* others::Cache::LRUCache< K, V >::tail

private

tail of the doubly linked list

Definition at line 63 of file lru_cache2.cpp.

---

The documentation for this class was generated from the following file:

• others/lru_cache2.cpp