concurrent_lru_cache.h

00001 /*
00002     Copyright 2005-2012 Intel Corporation.  All Rights Reserved.
00003 
00004     The source code contained or described herein and all documents related
00005     to the source code ("Material") are owned by Intel Corporation or its
00006     suppliers or licensors.  Title to the Material remains with Intel
00007     Corporation or its suppliers and licensors.  The Material is protected
00008     by worldwide copyright laws and treaty provisions.  No part of the
00009     Material may be used, copied, reproduced, modified, published, uploaded,
00010     posted, transmitted, distributed, or disclosed in any way without
00011     Intel's prior express written permission.
00012 
00013     No license under any patent, copyright, trade secret or other
00014     intellectual property right is granted to or conferred upon you by
00015     disclosure or delivery of the Materials, either expressly, by
00016     implication, inducement, estoppel or otherwise.  Any license under such
00017     intellectual property rights must be express and approved by Intel in
00018     writing.
00019 */
00020 
00021 #ifndef __TBB_concurrent_lru_cache_H
00022 #define __TBB_concurrent_lru_cache_H
00023 
00024 #if ! TBB_PREVIEW_CONCURRENT_LRU_CACHE
00025     #error Set TBB_PREVIEW_CONCURRENT_LRU_CACHE to include concurrent_lru_cache.h
00026 #endif
00027 
00028 #include <map>
00029 #include <list>
00030 
00031 #include "tbb_stddef.h"
00032 #include "atomic.h"
00033 #include "internal/_aggregator_impl.h"
00034 
00035 namespace tbb{
00036 namespace interface6 {
00037 
00038 
00039 template <typename key_type, typename value_type, typename value_functor_type = value_type (*)(key_type) >
00040 class concurrent_lru_cache : internal::no_assign{
00041 private:
00042     typedef concurrent_lru_cache self_type;
00043     typedef value_functor_type value_function_type;
00044     typedef std::size_t ref_counter_type;
00045     struct map_value_type;
00046     typedef std::map<key_type, map_value_type> map_storage_type;
00047     typedef std::list<typename map_storage_type::iterator> lru_list_type;
00048     struct map_value_type {
00049         value_type my_value;
00050         ref_counter_type my_ref_counter;
00051         typename lru_list_type::iterator my_lru_list_iterator;
00052         bool my_is_ready;
00053 
00054         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)
00055             : my_value(a_value), my_ref_counter(a_ref_counter), my_lru_list_iterator (a_lru_list_iterator), my_is_ready(a_is_ready)
00056         {}
00057     };
00058 
00059     class handle_object;
00060 
00061     struct aggregator_operation;
00062     typedef aggregator_operation aggregated_operation_type;
00063     typedef tbb::internal::aggregating_functor<self_type,aggregated_operation_type> aggregator_function_type;
00064     friend class tbb::internal::aggregating_functor<self_type,aggregated_operation_type>;
00065     typedef tbb::internal::aggregator<aggregator_function_type, aggregated_operation_type> aggregator_type;
00066 
00067 private:
00068     value_function_type my_value_function;
00069     std::size_t const my_number_of_lru_history_items;
00070     map_storage_type my_map_storage;
00071     lru_list_type my_lru_list;
00072     aggregator_type my_aggregator;
00073 
00074 public:
00075     typedef handle_object handle;
00076 
00077 public:
00078     concurrent_lru_cache(value_function_type f, std::size_t number_of_lru_history_items)
00079         : my_value_function(f),my_number_of_lru_history_items(number_of_lru_history_items)
00080     {
00081         my_aggregator.initialize_handler(aggregator_function_type(this));
00082     }
00083 
00084     handle_object operator[](key_type k){
00085         retrieve_aggregator_operation op(k);
00086         my_aggregator.execute(&op);
00087         if (op.is_new_value_needed()){
00088              op.result().second.my_value = my_value_function(k);
00089              __TBB_store_with_release(op.result().second.my_is_ready, true);
00090         }else{
00091             tbb::internal::spin_wait_while_eq(op.result().second.my_is_ready,false);
00092         }
00093         return handle_object(*this,op.result());
00094     }
00095 private:
00096     void signal_end_of_usage(typename map_storage_type::reference value_ref){
00097         signal_end_of_usage_aggregator_operation op(value_ref);
00098         my_aggregator.execute(&op);
00099     }
00100 
00101 private:
00102     struct handle_move_t:no_assign{
00103         concurrent_lru_cache & my_cache_ref;
00104         typename map_storage_type::reference my_map_record_ref;
00105         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) {};
00106     };
00107     class handle_object {
00108         concurrent_lru_cache * my_cache_pointer;
00109         typename map_storage_type::reference my_map_record_ref;
00110     public:
00111         handle_object(concurrent_lru_cache & cache_ref, typename map_storage_type::reference value_ref):my_cache_pointer(&cache_ref), my_map_record_ref(value_ref) {}
00112         handle_object(handle_move_t m):my_cache_pointer(&m.my_cache_ref), my_map_record_ref(m.my_map_record_ref){}
00113         operator handle_move_t(){ return move(*this);}
00114         value_type& value(){
00115             __TBB_ASSERT(my_cache_pointer,"get value from moved from object?");
00116             return my_map_record_ref.second.my_value;
00117         }
00118         ~handle_object(){
00119             if (my_cache_pointer){
00120                 my_cache_pointer->signal_end_of_usage(my_map_record_ref);
00121             }
00122         }
00123     private:
00124         friend handle_move_t move(handle_object& h){
00125             return handle_object::move(h);
00126         }
00127         static handle_move_t move(handle_object& h){
00128             __TBB_ASSERT(h.my_cache_pointer,"move from the same object twice ?");
00129             concurrent_lru_cache * cache_pointer = NULL;
00130             std::swap(cache_pointer,h.my_cache_pointer);
00131             return handle_move_t(*cache_pointer,h.my_map_record_ref);
00132         }
00133     private:
00134         void operator=(handle_object&);
00135         handle_object(handle_object &);
00136     };
00137 private:
00138     //TODO: looks like aggregator_operation is a perfect match for statically typed variant type
00139     struct aggregator_operation : tbb::internal::aggregated_operation<aggregator_operation>{
00140         enum e_op_type {op_retive, op_signal_end_of_usage};
00141         //TODO: try to use pointer to function apply_visitor here
00142         //TODO: try virtual functions and measure the difference
00143         e_op_type my_operation_type;
00144         aggregator_operation(e_op_type operation_type): my_operation_type(operation_type) {}
00145         void cast_and_handle(self_type& container ){
00146             if (my_operation_type==op_retive){
00147                 static_cast<retrieve_aggregator_operation*>(this)->handle(container);
00148             }else{
00149                 static_cast<signal_end_of_usage_aggregator_operation*>(this)->handle(container);
00150             }
00151         }
00152     };
00153     struct retrieve_aggregator_operation : aggregator_operation, private internal::no_assign {
00154         key_type my_key;
00155         typename map_storage_type::pointer my_result_map_record_pointer;
00156         bool my_is_new_value_needed;
00157         retrieve_aggregator_operation(key_type key):aggregator_operation(aggregator_operation::op_retive),my_key(key),my_is_new_value_needed(false){}
00158         void handle(self_type& container ){
00159             my_result_map_record_pointer = & container.retrieve_serial(my_key,my_is_new_value_needed);
00160         }
00161         typename map_storage_type::reference result(){ return * my_result_map_record_pointer; }
00162         bool is_new_value_needed(){return my_is_new_value_needed;}
00163     };
00164     struct signal_end_of_usage_aggregator_operation : aggregator_operation, private internal::no_assign {
00165         typename map_storage_type::reference my_map_record_ref;
00166         signal_end_of_usage_aggregator_operation(typename map_storage_type::reference map_record_ref):aggregator_operation(aggregator_operation::op_signal_end_of_usage),my_map_record_ref(map_record_ref){}
00167         void handle(self_type& container ){
00168             container.signal_end_of_usage_serial(my_map_record_ref);
00169         }
00170     };
00171 
00172 private:
00173    void handle_operations(aggregator_operation* op_list){
00174        while(op_list){
00175            op_list->cast_and_handle(*this);
00176            aggregator_operation* tmp = op_list;
00177            op_list=op_list->next;
00178            tbb::internal::itt_store_word_with_release(tmp->status, uintptr_t(1));
00179        }
00180    }
00181 
00182 private:
00183    typename map_storage_type::reference retrieve_serial(key_type k, bool& is_new_value_needed){
00184         typename map_storage_type::iterator it = my_map_storage.find(k);
00185         if (it == my_map_storage.end()){
00186             it = my_map_storage.insert(it,std::make_pair(k,map_value_type(value_type(),0,my_lru_list.end(),false)));
00187             is_new_value_needed = true;
00188         }else {
00189             typename lru_list_type::iterator list_it = it->second.my_lru_list_iterator;
00190             if (list_it!=my_lru_list.end()) {
00191                 __TBB_ASSERT(!it->second.my_ref_counter,"item to be evicted should not have a live references");
00192                 //item is going to be used. Therefore it is not a subject for eviction
00193                 //so - remove it from LRU history.
00194                 my_lru_list.erase(list_it);
00195                 it->second.my_lru_list_iterator= my_lru_list.end();
00196             }
00197         }
00198         ++(it->second.my_ref_counter);
00199         return *it;
00200     }
00201 
00202     void signal_end_of_usage_serial(typename map_storage_type::reference map_record_ref){
00203         typename map_storage_type::iterator it = my_map_storage.find(map_record_ref.first);
00204         __TBB_ASSERT(it!=my_map_storage.end(),"cache should not return past-end iterators to outer world");
00205         __TBB_ASSERT(&(*it) == &map_record_ref,"dangling reference has been returned to outside world? data race ?");
00206         __TBB_ASSERT( my_lru_list.end()== std::find(my_lru_list.begin(),my_lru_list.end(),it),
00207                 "object in use should not be in list of unused objects ");
00208         if (! --(it->second.my_ref_counter)){
00209             //it was the last reference so put it to the LRU history
00210             if (my_lru_list.size()>=my_number_of_lru_history_items){
00211                 //evict items in order to get a space
00212                 size_t number_of_elements_to_evict = 1 + my_lru_list.size() - my_number_of_lru_history_items;
00213                 for (size_t i=0; i<number_of_elements_to_evict; ++i){
00214                     typename map_storage_type::iterator it_to_evict = my_lru_list.back();
00215                     __TBB_ASSERT(!it_to_evict->second.my_ref_counter,"item to be evicted should not have a live references");
00216                     my_lru_list.pop_back();
00217                     my_map_storage.erase(it_to_evict);
00218                 }
00219             }
00220             my_lru_list.push_front(it);
00221             it->second.my_lru_list_iterator = my_lru_list.begin();
00222         }
00223     }
00224 };
00225 } // namespace interface6
00226 
00227 using interface6::concurrent_lru_cache;
00228 
00229 } // namespace tbb
00230 #endif //__TBB_concurrent_lru_cache_H

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