lru.c File Reference

implementation of the lru cache More...

#include <stdlib.h>
#include <errno.h>
#include <assert.h>
#include "include/log.h"
#include "include/lru.h"

Include dependency graph for lru.c:

Functions
struct lru_cache *	lru_init (const size_t capacity, lru_dealloc_fn deallocate)
	initialize the LRU cache data strcture More...
static struct lru_node *	lru_alloc_node (const uint64_t key, uintptr_t value)
	allocate the single node More...
static void	lru_dealloc_node (struct lru_node *node)
	deallcate the allocated node More...
static int	lru_delete_node (struct lru_node *head, struct lru_node *deleted)
	delete the node from the list More...
static int	__lru_do_evict (struct lru_cache *cache)
	implementation of the LRU eviction function More...
static int	lru_do_evict (struct lru_cache *cache, const uint64_t nr_evict)
	interfaces for execute the eviction process More...
static void	lru_node_insert (struct lru_node *node, struct lru_node *newnode)
	insert the lru node to the list More...
int	lru_put (struct lru_cache *cache, const uint64_t key, uintptr_t value)
	inser the key, value to the LRU cache More...
static struct lru_node *	lru_find_node (struct lru_cache *cache, const uint64_t key)
	find the node based on the key More...
uintptr_t	lru_get (struct lru_cache *cache, const uint64_t key)
	get data from the LRU cache More...
int	lru_free (struct lru_cache *cache)
	deallocate the LRU cache structure More...

Detailed Description

implementation of the lru cache

Author

Gijun Oh

Version

0.1

Date

2021-09-30

Function Documentation

__lru_do_evict()

static int __lru_do_evict ( struct lru_cache *  cache )

static

implementation of the LRU eviction function

Parameters

cache

LRU cache data structure pointer

Returns

0 for successfully evict

Here is the call graph for this function:

lru_alloc_node()

static struct lru_node* lru_alloc_node ( const uint64_t  key, uintptr_t  value  )

static

allocate the single node

Parameters

key	key for identify the node
value	value for data in the node

Returns

allocated node structure pointer

lru_dealloc_node()

static void lru_dealloc_node ( struct lru_node *  node )

static

deallcate the allocated node

Parameters

node	node which wants to deallocate

lru_delete_node()

static int lru_delete_node ( struct lru_node *  head, struct lru_node *  deleted  )

static

delete the node from the list

Parameters

head	list's head pointer
deleted	target which wants to delete

Returns

0 for successfully delete, -EINVAL means there is no data in list

Note

This function doesn't deallocate the node and its data

lru_do_evict()

static int lru_do_evict ( struct lru_cache *  cache, const uint64_t  nr_evict  )

static

interfaces for execute the eviction process

Parameters

cache	LRU cache data structure pointer
nr_evict	number of the entries to evict

Returns

0 for successfully evict

Here is the call graph for this function:

lru_find_node()

static struct lru_node* lru_find_node ( struct lru_cache *  cache, const uint64_t  key  )

static

find the node based on the key

Parameters

cache	LRU cache data structure pointer
key	key which identifies the node

Returns

pointer of the node

lru_free()

int lru_free

(

struct lru_cache *

cache

)

deallocate the LRU cache structure

Parameters

cache

LRU cache data structure pointer

Returns

0 to success

lru_get()

uintptr_t lru_get	(	struct lru_cache *	cache,
		const uint64_t	key
	)

get data from the LRU cache

Parameters

cache	LRU cache data structrue pointer
key	key which identifies the node

Returns

data in the node's value

Here is the call graph for this function:

lru_init()

struct lru_cache* lru_init	(	const size_t	capacity,
		lru_dealloc_fn	deallocate
	)

initialize the LRU cache data strcture

Parameters

capacity	number of the entries to insert the LRU
deallocate	deallcation function for LRU's value

Returns

initialized LRU cache data structure pointer

Here is the call graph for this function:

lru_node_insert()

static void lru_node_insert ( struct lru_node *  node, struct lru_node *  newnode  )

static

insert the lru node to the list

Parameters

node	pointer of the node, node->next will indicate the newnode
newnode	newly allocated node to insert

lru_put()

int lru_put	(	struct lru_cache *	cache,
		const uint64_t	key,
		uintptr_t	value
	)

inser the key, value to the LRU cache

Parameters

cache	LRU cache data structure pointer
key	key which identifies the node
value	value which contains the data

Returns

0 to success

Here is the call graph for this function: