Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type > Class Template Reference

#include <concurrent_lru_cache.h>

Inheritance diagram for tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >:
Collaboration diagram for tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >:

Classes

struct  aggregator_operation
 
class  handle_object
 
struct  map_value_type
 
struct  retrieve_aggregator_operation
 
struct  signal_end_of_usage_aggregator_operation
 

Public Types

typedef handle_object handle
 

Public Member Functions

 concurrent_lru_cache (value_function_type f, std::size_t number_of_lru_history_items)
 
handle_object operator[] (key_type k)
 

Private Types

typedef concurrent_lru_cache self_type
 
typedef value_functor_type value_function_type
 
typedef std::size_t ref_counter_type
 
typedef std::map< key_type, map_value_typemap_storage_type
 
typedef std::list< typename map_storage_type::iterator > lru_list_type
 
typedef aggregator_operation aggregated_operation_type
 
typedef tbb::internal::aggregating_functor< self_type, aggregated_operation_typeaggregator_function_type
 
typedef tbb::internal::aggregator< aggregator_function_type, aggregated_operation_typeaggregator_type
 

Private Member Functions

void signal_end_of_usage (typename map_storage_type::reference value_ref)
 
void handle_operations (aggregator_operation *op_list)
 
map_storage_type::reference retrieve_serial (key_type k, bool &is_new_value_needed)
 
void signal_end_of_usage_serial (typename map_storage_type::reference map_record_ref)
 

Private Attributes

value_function_type my_value_function
 
std::size_t const my_number_of_lru_history_items
 
map_storage_type my_map_storage
 
lru_list_type my_lru_list
 
aggregator_type my_aggregator
 

Friends

class tbb::internal::aggregating_functor< self_type, aggregated_operation_type >
 

Detailed Description

template<typename key_type, typename value_type, typename value_functor_type = value_type (*)(key_type)>
class tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >

Definition at line 41 of file concurrent_lru_cache.h.

Member Typedef Documentation

◆ aggregated_operation_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef aggregator_operation tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::aggregated_operation_type
private

Definition at line 62 of file concurrent_lru_cache.h.

◆ aggregator_function_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef tbb::internal::aggregating_functor<self_type,aggregated_operation_type> tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::aggregator_function_type
private

Definition at line 64 of file concurrent_lru_cache.h.

◆ aggregator_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef tbb::internal::aggregator<aggregator_function_type, aggregated_operation_type> tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::aggregator_type
private

Definition at line 66 of file concurrent_lru_cache.h.

◆ handle

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef handle_object tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::handle

Definition at line 76 of file concurrent_lru_cache.h.

◆ lru_list_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef std::list<typename map_storage_type::iterator> tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::lru_list_type
private

Definition at line 48 of file concurrent_lru_cache.h.

◆ map_storage_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef std::map<key_type, map_value_type> tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::map_storage_type
private

Definition at line 46 of file concurrent_lru_cache.h.

◆ ref_counter_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef std::size_t tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::ref_counter_type
private

Definition at line 45 of file concurrent_lru_cache.h.

◆ self_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef concurrent_lru_cache tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::self_type
private

Definition at line 43 of file concurrent_lru_cache.h.

◆ value_function_type

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
typedef value_functor_type tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::value_function_type
private

Definition at line 44 of file concurrent_lru_cache.h.

Constructor & Destructor Documentation

◆ concurrent_lru_cache()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::concurrent_lru_cache ( value_function_type  f,
std::size_t  number_of_lru_history_items 
)
inline

Definition at line 79 of file concurrent_lru_cache.h.

80  : my_value_function(f),my_number_of_lru_history_items(number_of_lru_history_items)
81  {
83  }
tbb::internal::aggregating_functor< self_type, aggregated_operation_type > aggregator_function_type

References tbb::interface6::internal::aggregator< handler_type, operation_type >::initialize_handler(), and tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_aggregator.

Here is the call graph for this function:

Member Function Documentation

◆ handle_operations()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
void tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::handle_operations ( aggregator_operation op_list)
inlineprivate

Definition at line 226 of file concurrent_lru_cache.h.

226  {
227  while(op_list){
228  op_list->cast_and_handle(*this);
229  aggregator_operation* tmp = op_list;
230  op_list=op_list->next;
231  tbb::internal::itt_store_word_with_release(tmp->status, uintptr_t(1));
232  }
233  }
void itt_store_word_with_release(tbb::atomic< T > &dst, U src)

References tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::aggregator_operation::cast_and_handle(), tbb::internal::itt_store_word_with_release(), tbb::interface6::internal::aggregated_operation< Derived >::next, and tbb::interface6::internal::aggregated_operation< Derived >::status.

Here is the call graph for this function:

◆ operator[]()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
handle_object tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::operator[] ( key_type  k)
inline

Definition at line 85 of file concurrent_lru_cache.h.

85  {
86  retrieve_aggregator_operation op(k);
88  if (op.is_new_value_needed()){
89  op.result().second.my_value = my_value_function(k);
90  __TBB_store_with_release(op.result().second.my_is_ready, true);
91  }else{
92  tbb::internal::spin_wait_while_eq(op.result().second.my_is_ready,false);
93  }
94  return handle_object(*this,op.result());
95  }
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
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713

References tbb::internal::__TBB_store_with_release(), tbb::interface6::internal::aggregator< handler_type, operation_type >::execute(), tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::retrieve_aggregator_operation::is_new_value_needed(), tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_aggregator, tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_value_function, tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::retrieve_aggregator_operation::result(), and tbb::internal::spin_wait_while_eq().

Here is the call graph for this function:

◆ retrieve_serial()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
map_storage_type::reference tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::retrieve_serial ( key_type  k,
bool &  is_new_value_needed 
)
inlineprivate

Definition at line 236 of file concurrent_lru_cache.h.

236  {
237  typename map_storage_type::iterator it = my_map_storage.find(k);
238  if (it == my_map_storage.end()){
239  it = my_map_storage.insert(it,std::make_pair(k,map_value_type(value_type(),0,my_lru_list.end(),false)));
240  is_new_value_needed = true;
241  }else {
242  typename lru_list_type::iterator list_it = it->second.my_lru_list_iterator;
243  if (list_it!=my_lru_list.end()) {
244  __TBB_ASSERT(!it->second.my_ref_counter,"item to be evicted should not have a live references");
245  //item is going to be used. Therefore it is not a subject for eviction
246  //so - remove it from LRU history.
247  my_lru_list.erase(list_it);
248  it->second.my_lru_list_iterator= my_lru_list.end();
249  }
250  }
251  ++(it->second.my_ref_counter);
252  return *it;
253  }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165

References __TBB_ASSERT, tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_lru_list, and tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_map_storage.

Referenced by tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::retrieve_aggregator_operation::handle().

Here is the caller graph for this function:

◆ signal_end_of_usage()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
void tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::signal_end_of_usage ( typename map_storage_type::reference  value_ref)
inlineprivate

Definition at line 97 of file concurrent_lru_cache.h.

97  {
98  signal_end_of_usage_aggregator_operation op(value_ref);
100  }

References tbb::interface6::internal::aggregator< handler_type, operation_type >::execute(), and tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_aggregator.

Referenced by tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::handle_object::operator=(), and tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::handle_object::~handle_object().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ signal_end_of_usage_serial()

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
void tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::signal_end_of_usage_serial ( typename map_storage_type::reference  map_record_ref)
inlineprivate

Definition at line 255 of file concurrent_lru_cache.h.

255  {
256  typename map_storage_type::iterator it = my_map_storage.find(map_record_ref.first);
257  __TBB_ASSERT(it!=my_map_storage.end(),"cache should not return past-end iterators to outer world");
258  __TBB_ASSERT(&(*it) == &map_record_ref,"dangling reference has been returned to outside world? data race ?");
259  __TBB_ASSERT( my_lru_list.end()== std::find(my_lru_list.begin(),my_lru_list.end(),it),
260  "object in use should not be in list of unused objects ");
261  if (! --(it->second.my_ref_counter)){
262  //it was the last reference so put it to the LRU history
264  //evict items in order to get a space
265  size_t number_of_elements_to_evict = 1 + my_lru_list.size() - my_number_of_lru_history_items;
266  for (size_t i=0; i<number_of_elements_to_evict; ++i){
267  typename map_storage_type::iterator it_to_evict = my_lru_list.back();
268  __TBB_ASSERT(!it_to_evict->second.my_ref_counter,"item to be evicted should not have a live references");
269  my_lru_list.pop_back();
270  my_map_storage.erase(it_to_evict);
271  }
272  }
273  my_lru_list.push_front(it);
274  it->second.my_lru_list_iterator = my_lru_list.begin();
275  }
276  }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165

References __TBB_ASSERT, tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_lru_list, tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_map_storage, and tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_number_of_lru_history_items.

Referenced by tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::signal_end_of_usage_aggregator_operation::handle().

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ tbb::internal::aggregating_functor< self_type, aggregated_operation_type >

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
friend class tbb::internal::aggregating_functor< self_type, aggregated_operation_type >
friend

Definition at line 65 of file concurrent_lru_cache.h.

Member Data Documentation

◆ my_aggregator

◆ my_lru_list

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
lru_list_type tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_lru_list
private

◆ my_map_storage

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
map_storage_type tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_map_storage
private

◆ my_number_of_lru_history_items

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
std::size_t const tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_number_of_lru_history_items
private

◆ my_value_function

template<typename key_type , typename value_type , typename value_functor_type = value_type (*)(key_type)>
value_function_type tbb::interface6::concurrent_lru_cache< key_type, value_type, value_functor_type >::my_value_function
private

The documentation for this class was generated from the following file:

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.