00001 /* generalSimpleHashTable.cc 00002 */ 00003 #include "osl/container/generalSimpleHashTable.h" 00004 #include "osl/hash/hashKey.h" 00005 #include "osl/stl/hash_map.h" 00006 #ifdef OSL_SMP 00007 # include "osl/misc/lightMutex.h" 00008 # include <iostream> 00009 #endif 00010 00011 template <typename Record> 00012 struct osl::container::GeneralSimpleHashTable<Record>::Table 00013 { 00014 typedef hash_map<HashKey, Record> table_t; 00015 typedef typename table_t::const_iterator const_iterator; 00016 #ifdef OSL_SMP 00017 static const unsigned int DIVSIZE=16; 00018 #else 00019 static const unsigned int DIVSIZE=1; 00020 #endif 00021 CArray<table_t,DIVSIZE> tables; 00022 00023 #ifdef OSL_SMP 00024 typedef osl::misc::LightMutex Mutex; 00025 CArray<Mutex,DIVSIZE> mutex; 00026 #endif 00027 00029 const unsigned int capacity; 00030 int num_cache_hit, num_record_after_full; 00031 00032 // if you use USE_GPL_POOL_ALLOCATOR, take care of the object size. 00033 // usually 256 is too large. 00034 BOOST_STATIC_ASSERT(sizeof(Record) <= 256); 00035 00036 Table(unsigned int c) 00037 : capacity(c), num_cache_hit(0), num_record_after_full(0) 00038 { 00039 for(size_t i=0;i<DIVSIZE;i++) 00040 tables[i]=table_t(c/DIVSIZE); 00041 } 00042 ~Table() 00043 { 00044 } 00045 void clear() 00046 { 00047 for(size_t i=0;i<DIVSIZE;i++){ 00048 #ifdef OSL_SMP 00049 Mutex::scoped_lock lk(mutex[i]); 00050 #endif 00051 tables[i].clear(); 00052 } 00053 num_cache_hit = 0; 00054 num_record_after_full = 0; 00055 } 00056 size_t size() const 00057 { 00058 size_t ret=0; 00059 for(size_t i=0;i<DIVSIZE;i++) 00060 ret+=tables[i].size(); 00061 return ret; 00062 } 00063 private: 00064 Record *findInLock(const HashKey& key,int i) 00065 { 00066 typename table_t::iterator pos = tables[i].find(key); 00067 if (pos == tables[i].end()) 00068 return 0; 00069 00070 ++num_cache_hit; 00071 return &pos->second; 00072 } 00073 static int keyToIndex(const HashKey& key) 00074 { 00075 unsigned long val=key.getSignature(); 00076 return (val>>24)%DIVSIZE; 00077 } 00078 public: 00079 Record *find(const HashKey& key) 00080 { 00081 int i=keyToIndex(key); 00082 #ifdef OSL_SMP 00083 Mutex::scoped_lock lk(mutex[i]); 00084 #endif 00085 return findInLock(key,i); 00086 } 00087 00088 Record *allocate(const HashKey& key) 00089 { 00090 int i=keyToIndex(key); 00091 #ifdef OSL_SMP 00092 Mutex::scoped_lock lk(mutex[i]); 00093 #endif 00094 const size_t current_size = tables[i].size(); 00095 if (current_size < capacity/DIVSIZE) 00096 { 00097 Record *record = &tables[i].operator[](key); 00098 if (current_size == tables[i].size()) 00099 ++num_cache_hit; 00100 return record; 00101 } 00102 // 䤵ʤ褦õ 00103 Record *result = findInLock(key,i); 00104 if ((result == 0) && capacity) 00105 { 00106 #ifdef OSL_SMP 00107 if (capacity > 10000) 00108 std::cerr << "table full " << size() << " " << capacity << "\n"; 00109 // SMPĶǤƤthreadꤲɬפ 00110 ++num_record_after_full; 00111 throw TableFull(); 00112 #else 00113 if (num_record_after_full++ == 0) 00114 throw TableFull(); 00115 #endif 00116 } 00117 return result; 00118 } 00119 }; 00120 00121 00122 template <typename Record> 00123 osl::container::GeneralSimpleHashTable<Record>:: 00124 GeneralSimpleHashTable(unsigned int capacity) 00125 : table(new Table(capacity)) 00126 { 00127 } 00128 00129 template <typename Record> 00130 osl::container::GeneralSimpleHashTable<Record>:: 00131 ~GeneralSimpleHashTable() { 00132 } 00133 00134 template <typename Record> 00135 void osl::container::GeneralSimpleHashTable<Record>:: 00136 clear() 00137 { 00138 table->clear(); 00139 } 00140 00141 template <typename Record> 00142 Record * 00143 osl::container::GeneralSimpleHashTable<Record>:: 00144 allocate(const HashKey& key) 00145 { 00146 return table->allocate(key); 00147 } 00148 00149 template <typename Record> 00150 Record * 00151 osl::container::GeneralSimpleHashTable<Record>:: 00152 find(const HashKey& key) 00153 { 00154 return table->find(key); 00155 } 00156 00157 template <typename Record> 00158 const Record * 00159 osl::container::GeneralSimpleHashTable<Record>:: 00160 find(const HashKey& key) const 00161 { 00162 return table->find(key); 00163 } 00164 00165 template <typename Record> 00166 unsigned int osl::container::GeneralSimpleHashTable<Record>:: 00167 size() const 00168 { 00169 return table->size(); 00170 } 00171 00172 template <typename Record> 00173 unsigned int osl::container::GeneralSimpleHashTable<Record>:: 00174 capacity() const 00175 { 00176 return table->capacity; 00177 } 00178 00179 template <typename Record> 00180 int osl::container::GeneralSimpleHashTable<Record>:: 00181 numCacheHit() const 00182 { 00183 return table->num_cache_hit; 00184 } 00185 00186 template <typename Record> 00187 int osl::container::GeneralSimpleHashTable<Record>:: 00188 numRecordAfterFull() const 00189 { 00190 return table->num_record_after_full; 00191 } 00192 00193 template <typename Record> 00194 int osl::container::GeneralSimpleHashTable<Record>:: 00195 divSize() const 00196 { 00197 return Table::DIVSIZE; 00198 } 00199 00200 /* ------------------------------------------------------------------------- */ 00201 // ;;; Local Variables: 00202 // ;;; mode:c++ 00203 // ;;; c-basic-offset:2 00204 // ;;; End: