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-2020 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 #ifndef __TBB_concurrent_lru_cache_H
18 #define __TBB_concurrent_lru_cache_H
19 
20 #define __TBB_concurrent_lru_cache_H_include_area
22 
23 #if ! TBB_PREVIEW_CONCURRENT_LRU_CACHE
24  #error Set TBB_PREVIEW_CONCURRENT_LRU_CACHE to include concurrent_lru_cache.h
25 #endif
26 
27 #include "tbb_stddef.h"
28 
29 #include <map>
30 #include <list>
31 #include <algorithm> // std::find
32 #if __TBB_CPP11_RVALUE_REF_PRESENT
33 #include <utility> // std::move
34 #endif
35 
36 #include "atomic.h"
38 
39 namespace tbb{
40 namespace interface6 {
41 
42 
43 template <typename key_type, typename value_type, typename value_functor_type = value_type (*)(key_type) >
45 private:
47  typedef value_functor_type value_function_type;
48  typedef std::size_t ref_counter_type;
50  typedef std::map<key_type, map_value_type> map_storage_type;
51  typedef std::list<typename map_storage_type::iterator> lru_list_type;
52  struct map_value_type {
53  value_type my_value;
55  typename lru_list_type::iterator my_lru_list_iterator;
57 
58  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)
59  : my_value(a_value), my_ref_counter(a_ref_counter), my_lru_list_iterator (a_lru_list_iterator), my_is_ready(a_is_ready)
60  {}
61  };
62 
63  class handle_object;
64 
70 
71 private:
73  std::size_t const my_number_of_lru_history_items;
77 
78 public:
80 
81 public:
82  concurrent_lru_cache(value_function_type f, std::size_t number_of_lru_history_items)
83  : my_value_function(f),my_number_of_lru_history_items(number_of_lru_history_items)
84  {
86  }
87 
91  if (op.is_new_value_needed()){
92  op.result().second.my_value = my_value_function(k);
93  __TBB_store_with_release(op.result().second.my_is_ready, true);
94  }else{
95  tbb::internal::spin_wait_while_eq(op.result().second.my_is_ready,false);
96  }
97  return handle_object(*this,op.result());
98  }
99 private:
100  void signal_end_of_usage(typename map_storage_type::reference value_ref){
102  my_aggregator.execute(&op);
103  }
104 
105 private:
106 #if !__TBB_CPP11_RVALUE_REF_PRESENT
107  struct handle_move_t:no_assign{
108  concurrent_lru_cache & my_cache_ref;
109  typename map_storage_type::reference my_map_record_ref;
110  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) {};
111  };
112 #endif
115  typename map_storage_type::pointer my_map_record_ptr;
116  public:
118  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) {}
119  operator bool() const {
121  }
122 #if __TBB_CPP11_RVALUE_REF_PRESENT
123  // TODO: add check for double moved objects by special dedicated field
125  __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?");
126  src.my_cache_pointer = NULL;
127  src.my_map_record_ptr = NULL;
128  }
130  __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?");
131  if (my_cache_pointer) {
133  }
134  my_cache_pointer = src.my_cache_pointer;
135  my_map_record_ptr = src.my_map_record_ptr;
136  src.my_cache_pointer = NULL;
137  src.my_map_record_ptr = NULL;
138  return *this;
139  }
140 #else
141  handle_object(handle_move_t m) : my_cache_pointer(&m.my_cache_ref), my_map_record_ptr(&m.my_map_record_ref) {}
142  handle_object& operator=(handle_move_t m) {
143  if (my_cache_pointer) {
145  }
146  my_cache_pointer = &m.my_cache_ref;
147  my_map_record_ptr = &m.my_map_record_ref;
148  return *this;
149  }
150  operator handle_move_t(){
151  return move(*this);
152  }
153 #endif // __TBB_CPP11_RVALUE_REF_PRESENT
154  value_type& value(){
155  __TBB_ASSERT(my_cache_pointer,"get value from already moved object?");
156  __TBB_ASSERT(my_map_record_ptr,"get value from an invalid or already moved object?");
157  return my_map_record_ptr->second.my_value;
158  }
160  if (my_cache_pointer){
162  }
163  }
164  private:
165 #if __TBB_CPP11_RVALUE_REF_PRESENT
166  // For source compatibility with C++03
168  return std::move(h);
169  }
170 #else
171  friend handle_move_t move(handle_object& h){
172  return handle_object::move(h);
173  }
174  // TODO: add check for double moved objects by special dedicated field
175  static handle_move_t move(handle_object& h){
176  __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?");
177  concurrent_lru_cache * cache_pointer = h.my_cache_pointer;
178  typename map_storage_type::pointer map_record_ptr = h.my_map_record_ptr;
179  h.my_cache_pointer = NULL;
180  h.my_map_record_ptr = NULL;
181  return handle_move_t(*cache_pointer, *map_record_ptr);
182  }
183 #endif // __TBB_CPP11_RVALUE_REF_PRESENT
184  private:
185  void operator=(handle_object&);
186 #if __SUNPRO_CC
187  // Presumably due to a compiler error, private copy constructor
188  // breaks expressions like handle h = cache[key];
189  public:
190 #endif
192  };
193 private:
194  //TODO: looks like aggregator_operation is a perfect match for statically typed variant type
197  //TODO: try to use pointer to function apply_visitor here
198  //TODO: try virtual functions and measure the difference
200  aggregator_operation(e_op_type operation_type): my_operation_type(operation_type) {}
201  void cast_and_handle(self_type& container ){
203  static_cast<retrieve_aggregator_operation*>(this)->handle(container);
204  }else{
205  static_cast<signal_end_of_usage_aggregator_operation*>(this)->handle(container);
206  }
207  }
208  };
210  key_type my_key;
211  typename map_storage_type::pointer my_result_map_record_pointer;
214  void handle(self_type& container ){
216  }
217  typename map_storage_type::reference result(){ return * my_result_map_record_pointer; }
219  };
221  typename map_storage_type::reference my_map_record_ref;
223  void handle(self_type& container ){
225  }
226  };
227 
228 private:
230  while(op_list){
231  op_list->cast_and_handle(*this);
232  aggregator_operation* tmp = op_list;
233  op_list=op_list->next;
235  }
236  }
237 
238 private:
239  typename map_storage_type::reference retrieve_serial(key_type k, bool& is_new_value_needed){
240  typename map_storage_type::iterator it = my_map_storage.find(k);
241  if (it == my_map_storage.end()){
242  it = my_map_storage.insert(it,std::make_pair(k,map_value_type(value_type(),0,my_lru_list.end(),false)));
243  is_new_value_needed = true;
244  }else {
245  typename lru_list_type::iterator list_it = it->second.my_lru_list_iterator;
246  if (list_it!=my_lru_list.end()) {
247  __TBB_ASSERT(!it->second.my_ref_counter,"item to be evicted should not have a live references");
248  //item is going to be used. Therefore it is not a subject for eviction
249  //so - remove it from LRU history.
250  my_lru_list.erase(list_it);
251  it->second.my_lru_list_iterator= my_lru_list.end();
252  }
253  }
254  ++(it->second.my_ref_counter);
255  return *it;
256  }
257 
258  void signal_end_of_usage_serial(typename map_storage_type::reference map_record_ref){
259  typename map_storage_type::iterator it = my_map_storage.find(map_record_ref.first);
260  __TBB_ASSERT(it!=my_map_storage.end(),"cache should not return past-end iterators to outer world");
261  __TBB_ASSERT(&(*it) == &map_record_ref,"dangling reference has been returned to outside world? data race ?");
262  __TBB_ASSERT( my_lru_list.end()== std::find(my_lru_list.begin(),my_lru_list.end(),it),
263  "object in use should not be in list of unused objects ");
264  if (! --(it->second.my_ref_counter)){
265  //it was the last reference so put it to the LRU history
267  //evict items in order to get a space
268  size_t number_of_elements_to_evict = 1 + my_lru_list.size() - my_number_of_lru_history_items;
269  for (size_t i=0; i<number_of_elements_to_evict; ++i){
270  typename map_storage_type::iterator it_to_evict = my_lru_list.back();
271  __TBB_ASSERT(!it_to_evict->second.my_ref_counter,"item to be evicted should not have a live references");
272  my_lru_list.pop_back();
273  my_map_storage.erase(it_to_evict);
274  }
275  }
276  my_lru_list.push_front(it);
277  it->second.my_lru_list_iterator = my_lru_list.begin();
278  }
279  }
280 };
281 } // namespace interface6
282 
283 using interface6::concurrent_lru_cache;
284 
285 } // namespace tbb
286 
288 #undef __TBB_concurrent_lru_cache_H_include_area
289 
290 #endif //__TBB_concurrent_lru_cache_H
tbb::interface6::concurrent_lru_cache::handle_object::my_cache_pointer
concurrent_lru_cache * my_cache_pointer
Definition: concurrent_lru_cache.h:114
tbb::interface6::concurrent_lru_cache::map_storage_type
std::map< key_type, map_value_type > map_storage_type
Definition: concurrent_lru_cache.h:49
_aggregator_impl.h
tbb::interface6::concurrent_lru_cache::retrieve_serial
map_storage_type::reference retrieve_serial(key_type k, bool &is_new_value_needed)
Definition: concurrent_lru_cache.h:239
tbb::interface6::concurrent_lru_cache::signal_end_of_usage
void signal_end_of_usage(typename map_storage_type::reference value_ref)
Definition: concurrent_lru_cache.h:100
tbb::interface6::concurrent_lru_cache::signal_end_of_usage_aggregator_operation::signal_end_of_usage_aggregator_operation
signal_end_of_usage_aggregator_operation(typename map_storage_type::reference map_record_ref)
Definition: concurrent_lru_cache.h:222
tbb::interface6::concurrent_lru_cache::handle_operations
void handle_operations(aggregator_operation *op_list)
Definition: concurrent_lru_cache.h:229
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::interface6::concurrent_lru_cache::map_value_type::my_is_ready
bool my_is_ready
Definition: concurrent_lru_cache.h:56
tbb::internal::no_assign
Base class for types that should not be assigned.
Definition: tbb_stddef.h:322
tbb::internal::itt_store_word_with_release
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)
Definition: tbb_profiling.h:157
tbb::interface6::concurrent_lru_cache::map_value_type::my_value
value_type my_value
Definition: concurrent_lru_cache.h:53
tbb::interface6::concurrent_lru_cache::handle_object::value
value_type & value()
Definition: concurrent_lru_cache.h:154
tbb::interface6::concurrent_lru_cache::handle_object::handle_object
handle_object(handle_object &&src)
Definition: concurrent_lru_cache.h:124
tbb::interface6::internal::aggregating_functor
Definition: _aggregator_impl.h:160
tbb::interface6::concurrent_lru_cache::my_number_of_lru_history_items
const std::size_t my_number_of_lru_history_items
Definition: concurrent_lru_cache.h:73
tbb::interface6::internal::aggregated_operation::next
Derived * next
Definition: _aggregator_impl.h:38
tbb::interface6::internal::aggregated_operation
aggregated_operation base class
Definition: _aggregator_impl.h:33
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::handle
void handle(self_type &container)
Definition: concurrent_lru_cache.h:214
tbb::interface6::concurrent_lru_cache::aggregator_function_type
tbb::internal::aggregating_functor< self_type, aggregated_operation_type > aggregator_function_type
Definition: concurrent_lru_cache.h:67
tbb::interface6::concurrent_lru_cache::handle
handle_object handle
Definition: concurrent_lru_cache.h:79
tbb::interface6::internal::aggregator::execute
void execute(operation_type *op)
Definition: _aggregator_impl.h:152
tbb::interface6::concurrent_lru_cache::aggregator_operation::e_op_type
e_op_type
Definition: concurrent_lru_cache.h:196
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation
Definition: concurrent_lru_cache.h:209
tbb::internal::spin_wait_while_eq
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:391
tbb::interface6::concurrent_lru_cache::map_value_type
Definition: concurrent_lru_cache.h:52
tbb::interface6::concurrent_lru_cache::handle_object::handle_object
handle_object()
Definition: concurrent_lru_cache.h:117
tbb::interface6::concurrent_lru_cache::my_aggregator
aggregator_type my_aggregator
Definition: concurrent_lru_cache.h:76
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::result
map_storage_type::reference result()
Definition: concurrent_lru_cache.h:217
tbb::interface6::concurrent_lru_cache::aggregator_operation::aggregator_operation
aggregator_operation(e_op_type operation_type)
Definition: concurrent_lru_cache.h:200
tbb::interface6::concurrent_lru_cache::map_value_type::my_lru_list_iterator
lru_list_type::iterator my_lru_list_iterator
Definition: concurrent_lru_cache.h:55
tbb::interface6::concurrent_lru_cache::handle_object::my_map_record_ptr
map_storage_type::pointer my_map_record_ptr
Definition: concurrent_lru_cache.h:115
tbb::interface6::concurrent_lru_cache::handle_object::move
friend handle_object && move(handle_object &h)
Definition: concurrent_lru_cache.h:167
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::is_new_value_needed
bool is_new_value_needed()
Definition: concurrent_lru_cache.h:218
tbb::interface6::concurrent_lru_cache::my_map_storage
map_storage_type my_map_storage
Definition: concurrent_lru_cache.h:74
tbb::interface6::concurrent_lru_cache::aggregator_operation::op_retive
@ op_retive
Definition: concurrent_lru_cache.h:196
tbb::interface6::concurrent_lru_cache::handle_object::operator=
handle_object & operator=(handle_object &&src)
Definition: concurrent_lru_cache.h:129
tbb::interface6::concurrent_lru_cache::signal_end_of_usage_aggregator_operation::my_map_record_ref
map_storage_type::reference my_map_record_ref
Definition: concurrent_lru_cache.h:221
tbb::move
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
tbb::interface6::concurrent_lru_cache::signal_end_of_usage_serial
void signal_end_of_usage_serial(typename map_storage_type::reference map_record_ref)
Definition: concurrent_lru_cache.h:258
key
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
Definition: ittnotify_static.h:198
tbb::internal::__TBB_store_with_release
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713
tbb::interface6::concurrent_lru_cache::ref_counter_type
std::size_t ref_counter_type
Definition: concurrent_lru_cache.h:48
tbb::interface6::internal::aggregated_operation::status
uintptr_t status
Zero value means "wait" status, all other values are "user" specified values and are defined into the...
Definition: _aggregator_impl.h:36
tbb::interface6::concurrent_lru_cache::aggregated_operation_type
aggregator_operation aggregated_operation_type
Definition: concurrent_lru_cache.h:65
atomic.h
tbb::interface6::concurrent_lru_cache::aggregator_operation
Definition: concurrent_lru_cache.h:195
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::my_is_new_value_needed
bool my_is_new_value_needed
Definition: concurrent_lru_cache.h:212
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::my_result_map_record_pointer
map_storage_type::pointer my_result_map_record_pointer
Definition: concurrent_lru_cache.h:211
tbb::interface6::concurrent_lru_cache::aggregator_operation::op_signal_end_of_usage
@ op_signal_end_of_usage
Definition: concurrent_lru_cache.h:196
tbb::interface6::concurrent_lru_cache::aggregator_operation::cast_and_handle
void cast_and_handle(self_type &container)
Definition: concurrent_lru_cache.h:201
tbb::interface6::internal::aggregator::initialize_handler
void initialize_handler(handler_type h)
Definition: _aggregator_impl.h:150
tbb::interface6::concurrent_lru_cache::handle_object::handle_object
handle_object(concurrent_lru_cache &cache_ref, typename map_storage_type::reference value_ref)
Definition: concurrent_lru_cache.h:118
_warning_suppress_disable_notice.h
tbb::interface6::concurrent_lru_cache::signal_end_of_usage_aggregator_operation
Definition: concurrent_lru_cache.h:220
tbb::interface6::concurrent_lru_cache::handle_object
Definition: concurrent_lru_cache.h:113
tbb::interface6::concurrent_lru_cache::concurrent_lru_cache
concurrent_lru_cache(value_function_type f, std::size_t number_of_lru_history_items)
Definition: concurrent_lru_cache.h:82
tbb::interface6::concurrent_lru_cache::map_value_type::my_ref_counter
ref_counter_type my_ref_counter
Definition: concurrent_lru_cache.h:54
tbb::interface6::concurrent_lru_cache::map_value_type::map_value_type
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)
Definition: concurrent_lru_cache.h:58
tbb::interface6::concurrent_lru_cache::handle_object::~handle_object
~handle_object()
Definition: concurrent_lru_cache.h:159
tbb::interface6::concurrent_lru_cache::value_function_type
value_functor_type value_function_type
Definition: concurrent_lru_cache.h:47
tbb::interface6::internal::aggregator
Definition: _aggregator_impl.h:144
tbb::interface6::concurrent_lru_cache::operator[]
handle_object operator[](key_type k)
Definition: concurrent_lru_cache.h:88
tbb::interface6::concurrent_lru_cache
Definition: concurrent_lru_cache.h:44
tbb::interface6::concurrent_lru_cache::aggregator_operation::my_operation_type
e_op_type my_operation_type
Definition: concurrent_lru_cache.h:199
tbb::interface6::concurrent_lru_cache::lru_list_type
std::list< typename map_storage_type::iterator > lru_list_type
Definition: concurrent_lru_cache.h:51
tbb_stddef.h
_warning_suppress_enable_notice.h
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::my_key
key_type my_key
Definition: concurrent_lru_cache.h:210
tbb::interface6::concurrent_lru_cache::my_value_function
value_function_type my_value_function
Definition: concurrent_lru_cache.h:72
tbb::interface6::concurrent_lru_cache::aggregator_type
tbb::internal::aggregator< aggregator_function_type, aggregated_operation_type > aggregator_type
Definition: concurrent_lru_cache.h:69
tbb::interface6::concurrent_lru_cache::my_lru_list
lru_list_type my_lru_list
Definition: concurrent_lru_cache.h:75
tbb::interface6::concurrent_lru_cache::self_type
concurrent_lru_cache self_type
Definition: concurrent_lru_cache.h:46
h
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
Definition: ittnotify_static.h:159
tbb::interface6::concurrent_lru_cache::retrieve_aggregator_operation::retrieve_aggregator_operation
retrieve_aggregator_operation(key_type key)
Definition: concurrent_lru_cache.h:213
tbb::interface6::concurrent_lru_cache::signal_end_of_usage_aggregator_operation::handle
void handle(self_type &container)
Definition: concurrent_lru_cache.h:223

Copyright © 2005-2020 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.