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 | |
17 | struct cache_node { |
18 | struct aws_linked_list_node node; |
19 | struct aws_lru_cache *cache; |
20 | const void *key; |
21 | void *value; |
22 | }; |
23 | |
24 | static 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 | |
35 | int 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 | |
55 | void 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 | |
62 | int 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 | |
82 | int 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 | |
125 | int 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 | |
131 | void 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 | |
137 | void *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 | |
150 | void *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 | |
161 | size_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 | |