1/*
2 * Copyright 2010-2018 Amazon.com, Inc. or its affiliates. All Rights Reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License").
5 * You may not use this file except in compliance with the License.
6 * A copy of the License is located at
7 *
8 * http://aws.amazon.com/apache2.0
9 *
10 * or in the "license" file accompanying this file. This file is distributed
11 * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
12 * express or implied. See the License for the specific language governing
13 * permissions and limitations under the License.
14 */
15#include <aws/common/lru_cache.h>
16
17struct cache_node {
18 struct aws_linked_list_node node;
19 struct aws_lru_cache *cache;
20 const void *key;
21 void *value;
22};
23
24static void s_element_destroy(void *value) {
25 struct cache_node *cache_node = value;
26
27 if (cache_node->cache->user_on_value_destroy) {
28 cache_node->cache->user_on_value_destroy(cache_node->value);
29 }
30
31 aws_linked_list_remove(&cache_node->node);
32 aws_mem_release(cache_node->cache->allocator, cache_node);
33}
34
35int aws_lru_cache_init(
36 struct aws_lru_cache *cache,
37 struct aws_allocator *allocator,
38 aws_hash_fn *hash_fn,
39 aws_hash_callback_eq_fn *equals_fn,
40 aws_hash_callback_destroy_fn *destroy_key_fn,
41 aws_hash_callback_destroy_fn *destroy_value_fn,
42 size_t max_items) {
43 AWS_ASSERT(allocator);
44 AWS_ASSERT(max_items);
45
46 cache->allocator = allocator;
47 cache->max_items = max_items;
48 cache->user_on_value_destroy = destroy_value_fn;
49
50 aws_linked_list_init(&cache->list);
51 return aws_hash_table_init(
52 &cache->table, allocator, max_items, hash_fn, equals_fn, destroy_key_fn, s_element_destroy);
53}
54
55void aws_lru_cache_clean_up(struct aws_lru_cache *cache) {
56 /* clearing the table will remove all elements. That will also deallocate
57 * any cache entries we currently have. */
58 aws_hash_table_clean_up(&cache->table);
59 AWS_ZERO_STRUCT(*cache);
60}
61
62int aws_lru_cache_find(struct aws_lru_cache *cache, const void *key, void **p_value) {
63
64 struct aws_hash_element *cache_element = NULL;
65 int err_val = aws_hash_table_find(&cache->table, key, &cache_element);
66
67 if (err_val || !cache_element) {
68 *p_value = NULL;
69 return err_val;
70 }
71
72 struct cache_node *cache_node = cache_element->value;
73 *p_value = cache_node->value;
74
75 /* on access, remove from current place in list and move it to the head. */
76 aws_linked_list_remove(&cache_node->node);
77 aws_linked_list_push_front(&cache->list, &cache_node->node);
78
79 return AWS_OP_SUCCESS;
80}
81
82int aws_lru_cache_put(struct aws_lru_cache *cache, const void *key, void *p_value) {
83
84 struct cache_node *cache_node = aws_mem_acquire(cache->allocator, sizeof(struct cache_node));
85
86 if (!cache_node) {
87 return AWS_OP_ERR;
88 }
89
90 struct aws_hash_element *element = NULL;
91 int was_added = 0;
92 int err_val = aws_hash_table_create(&cache->table, key, &element, &was_added);
93
94 if (err_val) {
95 aws_mem_release(cache->allocator, cache_node);
96 return err_val;
97 }
98
99 if (element->value) {
100 s_element_destroy(element->value);
101 }
102
103 cache_node->value = p_value;
104 cache_node->key = key;
105 cache_node->cache = cache;
106 element->value = cache_node;
107
108 aws_linked_list_push_front(&cache->list, &cache_node->node);
109
110 /* we only want to manage the space if we actually added a new element. */
111 if (was_added && aws_hash_table_get_entry_count(&cache->table) > cache->max_items) {
112
113 /* we're over the cache size limit. Remove whatever is in the back of
114 * the list. */
115 struct aws_linked_list_node *node_to_remove = aws_linked_list_back(&cache->list);
116 AWS_ASSUME(node_to_remove);
117 struct cache_node *entry_to_remove = AWS_CONTAINER_OF(node_to_remove, struct cache_node, node);
118 /*the callback will unlink and deallocate the node */
119 aws_hash_table_remove(&cache->table, entry_to_remove->key, NULL, NULL);
120 }
121
122 return AWS_OP_SUCCESS;
123}
124
125int aws_lru_cache_remove(struct aws_lru_cache *cache, const void *key) {
126 /* allocated cache memory and the linked list entry will be removed in the
127 * callback. */
128 return aws_hash_table_remove(&cache->table, key, NULL, NULL);
129}
130
131void aws_lru_cache_clear(struct aws_lru_cache *cache) {
132 /* clearing the table will remove all elements. That will also deallocate
133 * any cache entries we currently have. */
134 aws_hash_table_clear(&cache->table);
135}
136
137void *aws_lru_cache_use_lru_element(struct aws_lru_cache *cache) {
138 if (aws_linked_list_empty(&cache->list)) {
139 return NULL;
140 }
141
142 struct aws_linked_list_node *lru_node = aws_linked_list_back(&cache->list);
143
144 aws_linked_list_remove(lru_node);
145 aws_linked_list_push_front(&cache->list, lru_node);
146 struct cache_node *lru_element = AWS_CONTAINER_OF(lru_node, struct cache_node, node);
147 return lru_element->value;
148}
149
150void *aws_lru_cache_get_mru_element(const struct aws_lru_cache *cache) {
151 if (aws_linked_list_empty(&cache->list)) {
152 return NULL;
153 }
154
155 struct aws_linked_list_node *mru_node = aws_linked_list_front(&cache->list);
156
157 struct cache_node *mru_element = AWS_CONTAINER_OF(mru_node, struct cache_node, node);
158 return mru_element->value;
159}
160
161size_t aws_lru_cache_get_element_count(const struct aws_lru_cache *cache) {
162 return aws_hash_table_get_entry_count(&cache->table);
163}
164