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

LFUCache. More...

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

Public Member Functions
	LFUCache (int _capacity)
	Constructor, Initialize with minFreq and _capacity.
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 true if the cache is empty, false otherwise.
	~LFUCache ()
	destructs the cache, iterates on the map and deletes every node present in the cache.

Private Member Functions
void	push (int freq, CacheNode< K, V > *node)
	push the node at first position in the linked list of given frequency
void	increase_frequency (std::pair< CacheNode< K, V > *, int > &p_node)
	increase the frequency of node and push it in the respective list.
void	pop ()
	pop the last node in the least frequently used linked list

Private Attributes
std::unordered_map< K, std::pair< CacheNode< K, V > *, int > >	node_map
	maps the key to the node address and frequency
std::unordered_map< int, std::pair< CacheNode< K, V > *, CacheNode< K, V > * > >	freq_map
	maps the frequency to doubly linked list
int	minFreq
	minimum frequency in the cache
int	_capacity
	maximum capacity of the cache

Detailed Description

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

LFUCache.

Template Parameters

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

Definition at line 64 of file lfu_cache.cpp.

Constructor & Destructor Documentation

LFUCache()

template<typename K, typename V>

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

inlineexplicit

Constructor, Initialize with minFreq and _capacity.

Parameters

_capacity

Total capacity of the cache.

Definition at line 78 of file lfu_cache.cpp.

: minFreq(0), _capacity(_capacity) {}

~LFUCache()

template<typename K, typename V>

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

inline

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

Definition at line 235 of file lfu_cache.cpp.

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

Member Function Documentation

capacity()

template<typename K, typename V>

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

inline

Returns the total capacity of the cache.

Returns

Total capacity of the cache

Definition at line 223 of file lfu_cache.cpp.

{ return _capacity; }

empty()

template<typename K, typename V>

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

inline

returns true if the cache is empty, false otherwise.

Returns

true if the cache is empty, false otherwise.

Definition at line 229 of file lfu_cache.cpp.

{ return node_map.empty(); }

get()

template<typename K, typename V>

V others::Cache::LFUCache< 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 202 of file lfu_cache.cpp.

                 {
        if (!node_map.count(key)) {
            throw std::runtime_error("key is not present in the cache");
        }
 
        // increase the frequency and return the value
        V value = node_map[key].first->data.second;
        increase_frequency(node_map[key]);
        return value;
    }

increase_frequency()

template<typename K, typename V>

void others::Cache::LFUCache< K, V >::increase_frequency ( std::pair< CacheNode< K, V > *, int > & p_node )

inlineprivate

increase the frequency of node and push it in the respective list.

Parameters

p_node

the node to be updated

Definition at line 109 of file lfu_cache.cpp.

                                                                     {
        CacheNode<K, V> *node = p_node.first;
        int freq = p_node.second;
 
        std::pair<CacheNode<K, V> *, CacheNode<K, V> *> &p = freq_map[freq];
 
        // if the given node is the only node in the list,
        // then erase the frequency from map
        // and increase minFreq by 1.
        if (p.first == node && p.second == node) {
            freq_map.erase(freq);
            if (minFreq == freq) {
                minFreq = freq + 1;
            }
        } else {
            // remove the given node from current freq linked list
            CacheNode<K, V> *prev = node->prev;
            CacheNode<K, V> *next = node->next;
            node->prev = nullptr;
            node->next = nullptr;
 
            if (prev) {
                prev->next = next;
            } else {
                p.first = next;
            }
 
            if (next) {
                next->prev = prev;
            } else {
                p.second = prev;
            }
        }
        push(freq + 1, node);
        ++p_node.second;
    }

pop()

template<typename K, typename V>

void others::Cache::LFUCache< K, V >::pop ( )

inlineprivate

pop the last node in the least frequently used linked list

Definition at line 149 of file lfu_cache.cpp.

               {
        std::pair<CacheNode<K, V> *, CacheNode<K, V> *> &p = freq_map[minFreq];
 
        // if there is only one node
        // remove the node and erase
        // the frequency from freq_map
        if (p.first == p.second) {
            delete p.first;
            freq_map.erase(minFreq);
            return;
        }
 
        // remove the last node in the linked list
        CacheNode<K, V> *temp = p.second;
        p.second = temp->prev;
        p.second->next = nullptr;
        delete temp;
    }

push()

template<typename K, typename V>

void others::Cache::LFUCache< K, V >::push ( int freq, CacheNode< K, V > * node )

inlineprivate

push the node at first position in the linked list of given frequency

Parameters

freq	the frequency mapping to the linked list where node should be pushed.
node	node to be pushed to the linked list.

Definition at line 88 of file lfu_cache.cpp.

                                               {
        // if freq is not present, then make a new list with node as the head as
        // well as tail.
        if (!freq_map.count(freq)) {
            freq_map[freq] = {node, node};
            return;
        }
 
        std::pair<CacheNode<K, V> *, CacheNode<K, V> *> &p = freq_map[freq];
 
        // insert the node at the beginning of the linked list and update the
        // head.
        p.first->prev = node;
        node->next = p.first;
        p.first = node;
    }

put()

template<typename K, typename V>

void others::Cache::LFUCache< 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 174 of file lfu_cache.cpp.

                             {
        // update the value if key already exists
        if (node_map.count(key)) {
            node_map[key].first->data.second = value;
            increase_frequency(node_map[key]);
            return;
        }
 
        // if the cache is full
        // remove the least frequently used item
        if (node_map.size() == _capacity) {
            node_map.erase(freq_map[minFreq].second->data.first);
            pop();
        }
 
        // insert the new node and set minFreq to 1
        CacheNode<K, V> *node = new CacheNode<K, V>({key, value});
        node_map[key] = {node, 1};
        minFreq = 1;
        push(1, node);
    }

size()

template<typename K, typename V>

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

inline

Returns the number of items present in the cache.

Returns

number of items in the cache

Definition at line 217 of file lfu_cache.cpp.

{ return node_map.size(); }

Member Data Documentation

_capacity

template<typename K, typename V>

int others::Cache::LFUCache< K, V >::_capacity

private

maximum capacity of the cache

Definition at line 71 of file lfu_cache.cpp.

freq_map

template<typename K, typename V>

std::unordered_map<int, std::pair<CacheNode<K, V> *, CacheNode<K, V> *> > others::Cache::LFUCache< K, V >::freq_map

private

maps the frequency to doubly linked list

Definition at line 68 of file lfu_cache.cpp.

minFreq

template<typename K, typename V>

int others::Cache::LFUCache< K, V >::minFreq

private

minimum frequency in the cache

Definition at line 70 of file lfu_cache.cpp.

node_map

template<typename K, typename V>

std::unordered_map<K, std::pair<CacheNode<K, V> *, int> > others::Cache::LFUCache< K, V >::node_map

private

maps the key to the node address and frequency

Definition at line 66 of file lfu_cache.cpp.

---

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

• others/lfu_cache.cpp