-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcache.h
184 lines (158 loc) · 6.6 KB
/
cache.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/*|========================|*
*|======| OVERVIEW |======|*
*|========================|*
*/
/*
MIT LICENSE
Copyright 2023 (c) Archer Pergande.
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the “Software”), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to
do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR
A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH
THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
--------------------------------------------------------------------------------------
ABOUT
This code is an implementation of a dynamically memory allocated linked list cache using
the least recently used algorithm. It is intended to be a proof of concept or template and not
directly used in projects. Those who wish to use this LRU cache are free to customize
the HASH macro to their desired implementation. The "value" or "key" fields
located in the lru_entry_t structure may be modified to reflect the data the
programmer wishes to cache and the identifier of that data. These changes however,
may need to be reflected in the cache.c file.
--------------------------------------------------------------------------------------
DEPENDENCIES
This code relies on the C Standard Library function "calloc" located in
the stdlib.h header file. Some low level implementations such as "lru_cache_pop" and
"lru_cache_push" do not rely on any Standard Library functions.
*/
/*|========================|*
*|======| HASHING |=======|*
*|========================|*
*/
/*
Hash calculation which determines what index a specific entry will
be stored at. This is a simple implementation and can easily be changed for
a more advanced hashing equation.
*/
#define HASH(key,size) key % size
/*|========================|*
*|====| STATUS CODES |====|*
*|========================|*
*/
#define LRU_SUCCESS 0 /* The operation completed successfully. */
#define LRU_ERROR_NULL 1 /* One of the parameters were NULL. */
#define LRU_ERROR_ALLOC 2 /* Space could not be allocated for cache. */
#define LRU_ERROR_NOT_FOUND 3 /* The entry was not found in the cache. */
#define LRU_ERROR_FULL 4 /* The cache is full and cannot be added to. */
/*|========================|*
*|=====| STRUCTURES |=====|*
*|========================|*
*/
/* A specific data set found in a lru cache. */
typedef struct _lru_entry_t {
int key; /* Special identifier unique to this data. */
int value; /* The data to be stored. */
struct _lru_entry_t *next; /* Pointer to the next data set. */
struct _lru_entry_t *prev; /* Pointer to the previous data set. */
struct _lru_entry_t *chain; /* Pointer to the next data set whose HASH is equivalent to this one. */
} lru_entry_t;
/* A data structure for caching using the LRU method. */
typedef struct _lru_cache_t {
lru_entry_t **bucket; /* An array of pointers to store linked lists. */
lru_entry_t *head; /* The most recently used data in the cache. */
lru_entry_t *tail; /* The least recently used data in the cache. */
int bucket_count; /* The size of the bucket array. */
int list_count; /* The current number of data sets in the cache. */
int list_limit; /* The maximum allowed number of data sets in the cache. */
} lru_cache_t;
/*|========================|*
*|=====| PROTOTYPES |=====|*
*|========================|*
*/
/**
* Allocates a lru cache structure.
*
* Parameters:
* - bucket_count: The number of indexes in the lru cache (number of entries that will have an access time of (0)1).
* - entry_max: The maximum number of entries allowed in the cache.
*
* Returns:
* - !=NULL: A pointer to the newly allocated cache.
* - ==NULL: Space could not be allocated for the cache.
*/
lru_cache_t *lru_cache_create(int bucket_count, int entry_max);
/**
* Removes an entry from a lru cache but does not free the data.
*
* Parameters:
* - lru - The cache to remove from.
* - entry - The entry to remove from the lru cache.
*
* Returns:
* - LRU_ERROR_NULL: One or more of the parameters are NULL.
* - LRU_ERROR_NOT_FOUND: The entry does not exist within the cache.
* - LRU_SUCCESS: The entry was successfully removed from the cache.
*/
char lru_cache_pop(lru_cache_t *lru, lru_entry_t *entry);
/**
* Adds an existing entry to a lru cache.
*
* Parameters:
* - lru: The cache to add to.
* - entry: The data to add to the cache.
*
* Returns:
* - LRU_ERROR_NULL: One or more of the parameters are NULL.
* - LRU_SUCCESS: The entry was successfully added to the cache.
*/
char lru_cache_push(lru_cache_t *lru, lru_entry_t *entry);
/**
* Searches a cache for an entry matching the specified key.
*
* Parameters:
* - lru: The cache to search in.
* - key: The value to search by.
*
* Returns:
* - !=NULL: The entry was found in the cache and a pointer was returned.
* - ==NULL: The entry was not found in the cache.
*/
lru_entry_t *lru_cache_search(lru_cache_t *lru, int key);
/**
* Adds a new entry to a lru cache.
*
* Parameters:
* - lru: The cache to add to.
* - key: The unique identifier associated with the entry.
* - value: The data to store.
*
* Returns:
* - LRU_ERROR_NULL: One or more of the parameters are NULL.
* - LRU_ERROR_ALLOC: Space could not be allocated for the new entry.
* - LRU_SUCCESS: The entry was successfully added to the cache.
*/
char lru_cache_add(lru_cache_t *lru, int key, int value);
/**
* Removes a entry from a lru cache.
*
* Parameters:
* - lru: The cache to remove from.
* - key: The unique identifier of the entry to remove.
*/
void lru_cache_remove(lru_cache_t *lru, int key);
/**
* Removes all entries from a lru cache and deletes it.
*
* Parameters:
* - lru: The cache to delete.
*/
void lru_cache_free(lru_cache_t *lru);