Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
concurrent_lru_cache.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
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  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #ifndef __TBB_concurrent_lru_cache_H
22 #define __TBB_concurrent_lru_cache_H
23 
24 #if ! TBB_PREVIEW_CONCURRENT_LRU_CACHE
25  #error Set TBB_PREVIEW_CONCURRENT_LRU_CACHE to include concurrent_lru_cache.h
26 #endif
27 
28 #include "tbb_stddef.h"
29 
30 #include <map>
31 #include <list>
32 #include <algorithm> // std::find
33 #if __TBB_CPP11_RVALUE_REF_PRESENT
34 #include <utility> // std::move
35 #endif
36 
37 #include "atomic.h"
39 
40 namespace tbb{
41 namespace interface6 {
42 
43 
44 template <typename key_type, typename value_type, typename value_functor_type = value_type (*)(key_type) >
45 class concurrent_lru_cache : internal::no_assign{
46 private:
48  typedef value_functor_type value_function_type;
49  typedef std::size_t ref_counter_type;
51  typedef std::map<key_type, map_value_type> map_storage_type;
52  typedef std::list<typename map_storage_type::iterator> lru_list_type;
53  struct map_value_type {
54  value_type my_value;
56  typename lru_list_type::iterator my_lru_list_iterator;
58 
59  map_value_type (value_type const& a_value, ref_counter_type a_ref_counter, typename lru_list_type::iterator a_lru_list_iterator, bool a_is_ready)
60  : my_value(a_value), my_ref_counter(a_ref_counter), my_lru_list_iterator (a_lru_list_iterator), my_is_ready(a_is_ready)
61  {}
62  };
63 
64  class handle_object;
65 
71 
72 private:
74  std::size_t const my_number_of_lru_history_items;
78 
79 public:
81 
82 public:
83  concurrent_lru_cache(value_function_type f, std::size_t number_of_lru_history_items)
84  : my_value_function(f),my_number_of_lru_history_items(number_of_lru_history_items)
85  {
87  }
88 
92  if (op.is_new_value_needed()){
93  op.result().second.my_value = my_value_function(k);
94  __TBB_store_with_release(op.result().second.my_is_ready, true);
95  }else{
96  tbb::internal::spin_wait_while_eq(op.result().second.my_is_ready,false);
97  }
98  return handle_object(*this,op.result());
99  }
100 private:
101  void signal_end_of_usage(typename map_storage_type::reference value_ref){
103  my_aggregator.execute(&op);
104  }
105 
106 private:
107 #if !__TBB_CPP11_RVALUE_REF_PRESENT
108  struct handle_move_t:no_assign{
109  concurrent_lru_cache & my_cache_ref;
110  typename map_storage_type::reference my_map_record_ref;
111  handle_move_t(concurrent_lru_cache & cache_ref, typename map_storage_type::reference value_ref):my_cache_ref(cache_ref),my_map_record_ref(value_ref) {};
112  };
113 #endif
116  typename map_storage_type::pointer my_map_record_ptr;
117  public:
119  handle_object(concurrent_lru_cache& cache_ref, typename map_storage_type::reference value_ref) : my_cache_pointer(&cache_ref), my_map_record_ptr(&value_ref) {}
120  operator bool() const {
122  }
123 #if __TBB_CPP11_RVALUE_REF_PRESENT
124  // TODO: add check for double moved objects by special dedicated field
126  __TBB_ASSERT((src.my_cache_pointer && src.my_map_record_ptr) || (!src.my_cache_pointer && !src.my_map_record_ptr), "invalid state of moving object?");
127  src.my_cache_pointer = NULL;
128  src.my_map_record_ptr = NULL;
129  }
131  __TBB_ASSERT((src.my_cache_pointer && src.my_map_record_ptr) || (!src.my_cache_pointer && !src.my_map_record_ptr), "invalid state of moving object?");
132  if (my_cache_pointer) {
134  }
135  my_cache_pointer = src.my_cache_pointer;
136  my_map_record_ptr = src.my_map_record_ptr;
137  src.my_cache_pointer = NULL;
138  src.my_map_record_ptr = NULL;
139  return *this;
140  }
141 #else
142  handle_object(handle_move_t m) : my_cache_pointer(&m.my_cache_ref), my_map_record_ptr(&m.my_map_record_ref) {}
143  handle_object& operator=(handle_move_t m) {
144  if (my_cache_pointer) {
146  }
147  my_cache_pointer = &m.my_cache_ref;
148  my_map_record_ptr = &m.my_map_record_ref;
149  return *this;
150  }
151  operator handle_move_t(){
152  return move(*this);
153  }
154 #endif // __TBB_CPP11_RVALUE_REF_PRESENT
155  value_type& value(){
156  __TBB_ASSERT(my_cache_pointer,"get value from already moved object?");
157  __TBB_ASSERT(my_map_record_ptr,"get value from an invalid or already moved object?");
158  return my_map_record_ptr->second.my_value;
159  }
161  if (my_cache_pointer){
163  }
164  }
165  private:
166 #if __TBB_CPP11_RVALUE_REF_PRESENT
167  // For source compatibility with C++03
169  return std::move(h);
170  }
171 #else
172  friend handle_move_t move(handle_object& h){
173  return handle_object::move(h);
174  }
175  // TODO: add check for double moved objects by special dedicated field
176  static handle_move_t move(handle_object& h){
177  __TBB_ASSERT((h.my_cache_pointer && h.my_map_record_ptr) || (!h.my_cache_pointer && !h.my_map_record_ptr), "invalid state of moving object?");
178  concurrent_lru_cache * cache_pointer = h.my_cache_pointer;
179  typename map_storage_type::pointer map_record_ptr = h.my_map_record_ptr;
180  h.my_cache_pointer = NULL;
181  h.my_map_record_ptr = NULL;
182  return handle_move_t(*cache_pointer, *map_record_ptr);
183  }
184 #endif // __TBB_CPP11_RVALUE_REF_PRESENT
185  private:
186  void operator=(handle_object&);
187 #if __SUNPRO_CC
188  // Presumably due to a compiler error, private copy constructor
189  // breaks expressions like handle h = cache[key];
190  public:
191 #endif
193  };
194 private:
195  //TODO: looks like aggregator_operation is a perfect match for statically typed variant type
198  //TODO: try to use pointer to function apply_visitor here
199  //TODO: try virtual functions and measure the difference
201  aggregator_operation(e_op_type operation_type): my_operation_type(operation_type) {}
202  void cast_and_handle(self_type& container ){
204  static_cast<retrieve_aggregator_operation*>(this)->handle(container);
205  }else{
206  static_cast<signal_end_of_usage_aggregator_operation*>(this)->handle(container);
207  }
208  }
209  };
210  struct retrieve_aggregator_operation : aggregator_operation, private internal::no_assign {
211  key_type my_key;
212  typename map_storage_type::pointer my_result_map_record_pointer;
215  void handle(self_type& container ){
217  }
218  typename map_storage_type::reference result(){ return * my_result_map_record_pointer; }
220  };
221  struct signal_end_of_usage_aggregator_operation : aggregator_operation, private internal::no_assign {
222  typename map_storage_type::reference my_map_record_ref;
224  void handle(self_type& container ){
226  }
227  };
228 
229 private:
231  while(op_list){
232  op_list->cast_and_handle(*this);
233  aggregator_operation* tmp = op_list;
234  op_list=op_list->next;
236  }
237  }
238 
239 private:
240  typename map_storage_type::reference retrieve_serial(key_type k, bool& is_new_value_needed){
241  typename map_storage_type::iterator it = my_map_storage.find(k);
242  if (it == my_map_storage.end()){
243  it = my_map_storage.insert(it,std::make_pair(k,map_value_type(value_type(),0,my_lru_list.end(),false)));
244  is_new_value_needed = true;
245  }else {
246  typename lru_list_type::iterator list_it = it->second.my_lru_list_iterator;
247  if (list_it!=my_lru_list.end()) {
248  __TBB_ASSERT(!it->second.my_ref_counter,"item to be evicted should not have a live references");
249  //item is going to be used. Therefore it is not a subject for eviction
250  //so - remove it from LRU history.
251  my_lru_list.erase(list_it);
252  it->second.my_lru_list_iterator= my_lru_list.end();
253  }
254  }
255  ++(it->second.my_ref_counter);
256  return *it;
257  }
258 
259  void signal_end_of_usage_serial(typename map_storage_type::reference map_record_ref){
260  typename map_storage_type::iterator it = my_map_storage.find(map_record_ref.first);
261  __TBB_ASSERT(it!=my_map_storage.end(),"cache should not return past-end iterators to outer world");
262  __TBB_ASSERT(&(*it) == &map_record_ref,"dangling reference has been returned to outside world? data race ?");
263  __TBB_ASSERT( my_lru_list.end()== std::find(my_lru_list.begin(),my_lru_list.end(),it),
264  "object in use should not be in list of unused objects ");
265  if (! --(it->second.my_ref_counter)){
266  //it was the last reference so put it to the LRU history
268  //evict items in order to get a space
269  size_t number_of_elements_to_evict = 1 + my_lru_list.size() - my_number_of_lru_history_items;
270  for (size_t i=0; i<number_of_elements_to_evict; ++i){
271  typename map_storage_type::iterator it_to_evict = my_lru_list.back();
272  __TBB_ASSERT(!it_to_evict->second.my_ref_counter,"item to be evicted should not have a live references");
273  my_lru_list.pop_back();
274  my_map_storage.erase(it_to_evict);
275  }
276  }
277  my_lru_list.push_front(it);
278  it->second.my_lru_list_iterator = my_lru_list.begin();
279  }
280  }
281 };
282 } // namespace interface6
283 
284 using interface6::concurrent_lru_cache;
285 
286 } // namespace tbb
287 #endif //__TBB_concurrent_lru_cache_H
std::map< key_type, map_value_type > map_storage_type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
concurrent_lru_cache(value_function_type f, std::size_t number_of_lru_history_items)
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
handle_object(concurrent_lru_cache &cache_ref, typename map_storage_type::reference value_ref)
friend handle_object && move(handle_object &h)
map_storage_type::reference retrieve_serial(key_type k, bool &is_new_value_needed)
signal_end_of_usage_aggregator_operation(typename map_storage_type::reference map_record_ref)
Base class for types that should not be assigned.
Definition: tbb_stddef.h:324
void signal_end_of_usage_serial(typename map_storage_type::reference map_record_ref)
The graph class.
void signal_end_of_usage(typename map_storage_type::reference value_ref)
void spin_wait_while_eq(const volatile T &location, U value)
Spin WHILE the value of the variable is equal to a given value.
Definition: tbb_machine.h:395
tbb::internal::aggregating_functor< self_type, aggregated_operation_type > aggregator_function_type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
std::list< typename map_storage_type::iterator > lru_list_type
tbb::internal::aggregator< aggregator_function_type, aggregated_operation_type > aggregator_type
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:309
map_value_type(value_type const &a_value, ref_counter_type a_ref_counter, typename lru_list_type::iterator a_lru_list_iterator, bool a_is_ready)
uintptr_t status
Zero value means "wait" status, all other values are "user" specified values and are defined into the...
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:717
void handle_operations(aggregator_operation *op_list)

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.