All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
generalSimpleHashTable.tcc
Go to the documentation of this file.
1 /* generalSimpleHashTable.cc
2  */
4 #include "osl/hash/hashKey.h"
5 #include "osl/stl/hash_map.h"
6 #include "osl/config.h"
7 #ifdef USE_TBB_HASH
8 # include <cstring>
9 # include <tbb/concurrent_hash_map.h>
10 #endif
11 #ifdef OSL_SMP
12 # include "osl/misc/lightMutex.h"
13 # include <iostream>
14 #endif
15 
16 template <typename Record>
18 {
19 #ifdef USE_TBB_HASH
20  static const unsigned int DIVSIZE=1;
21  typedef tbb::concurrent_hash_map<HashKey, Record, TBBHashCompare> table_t;
22  typedef typename table_t::accessor accessor;
23 #else
24  typedef hash_map<HashKey, Record
25 # ifdef USE_BOOST_POOL_ALLOCATOR
27  , std::equal_to<HashKey>
28  , osl::stl::fast_pool_allocator<std::pair<const HashKey,Record> >
29 # endif
31  typedef typename table_t::const_iterator const_iterator;
32 # ifdef OSL_SMP
33  typedef osl::misc::LightMutex Mutex;
34  static const unsigned int DIVSIZE=16;
35  CArray<Mutex,DIVSIZE> mutex;
36 # else
37  static const unsigned int DIVSIZE=1;
38 # endif
39  // if you use USE_GPL_POOL_ALLOCATOR, take care of the object size.
40  // usually 256 is too large.
41 # ifdef USE_GPL_POOL_ALLOCATOR
42  BOOST_STATIC_ASSERT(sizeof(Record) <= 256);
43 # endif
44 #endif
45  CArray<table_t,DIVSIZE> tables;
46 
48  const size_t capacity;
49  int num_cache_hit, num_record_after_full;
50 
51  Table(size_t c)
52  : capacity(c), num_cache_hit(0), num_record_after_full(0)
53  {
54 #ifndef USE_TBB_HASH
55  for(size_t i=0;i<DIVSIZE;i++)
56  tables[i]=table_t(std::min(c, (size_t)3000000) /DIVSIZE); // keep reasonable size for initial capacity
57 #endif
58  }
60  {
61  }
62  void clear()
63  {
64  for(size_t i=0;i<DIVSIZE;i++){
65  tables[i].clear();
66  }
67  num_cache_hit = 0;
68  num_record_after_full = 0;
69  }
70  size_t size() const
71  {
72  size_t ret=0;
73  for(size_t i=0;i<DIVSIZE;i++)
74  ret+=tables[i].size();
75  return ret;
76  }
77 private:
78  Record *findInLock(const HashKey& key,int i)
79  {
80 #ifdef USE_TBB_HASH
81  accessor it;
82  if(!tables[i].find(it,key)) return 0;
83 # ifndef OSL_USE_RACE_DETECTOR
84  ++num_cache_hit;
85 # endif
86  return &(it->second);
87 #else
88  typename table_t::iterator pos = tables[i].find(key);
89  if (pos == tables[i].end())
90  return 0;
91 # ifndef OSL_USE_RACE_DETECTOR
92  ++num_cache_hit;
93 # endif
94  return &pos->second;
95 #endif
96  }
97  static int keyToIndex(const HashKey&
98 #ifndef USE_TBB_HASH
99  key
100 #endif
101  )
102  {
103 #ifdef USE_TBB_HASH
104  return 0;
105 #else
106  unsigned long val=key.signature();
107  return (val>>24)%DIVSIZE;
108 #endif
109  }
110 public:
111  Record *find(const HashKey& key)
112  {
113  int i=keyToIndex(key);
114 #if (defined OSL_SMP) && (! defined USE_TBB_HASH)
115  SCOPED_LOCK(lk,mutex[i]);
116 #endif
117  return findInLock(key,i);
118  }
119 
120  Record *allocate(const HashKey& key)
121  {
122  const int i=keyToIndex(key);
123 #if (defined OSL_SMP) && (! defined USE_TBB_HASH)
124  SCOPED_LOCK(lk,mutex[i]);
125 #endif
126  const size_t current_size = tables[i].size();
127  if (current_size < capacity/DIVSIZE)
128  {
129 #ifdef USE_TBB_HASH
130  accessor it;
131  tables[i].insert(it, key);
132  Record *record = &it->second;
133 #else
134  Record *record = &tables[i].operator[](key);
135 #endif
136 #ifndef OSL_USE_RACE_DETECTOR
137  if (current_size == tables[i].size())
138  ++num_cache_hit;
139 #endif
140  return record;
141  }
142  // サイズを増やさないように探す
143  Record *result = findInLock(key,i);
144  if ((result == 0) && capacity)
145  {
146 #ifdef OSL_SMP
147  if (capacity > 10000)
148  std::cerr << "table full " << size() << " " << capacity << "\n";
149  // SMP環境では全てのthreadに投げる必要がある
150  ++num_record_after_full;
151  throw TableFull();
152 #else
153  if (num_record_after_full++ == 0)
154  throw TableFull();
155 #endif
156  }
157  return result;
158  }
159 };
160 
161 
162 template <typename Record>
164 GeneralSimpleHashTable(size_t capacity)
165  : table(new Table(capacity))
166 {
167 }
168 
169 template <typename Record>
172 }
173 
174 template <typename Record>
177 {
178  table->clear();
179 }
180 
181 template <typename Record>
182 Record *
184 allocate(const HashKey& key)
185 {
186  return table->allocate(key);
187 }
188 
189 template <typename Record>
190 Record *
192 find(const HashKey& key)
193 {
194  return table->find(key);
195 }
196 
197 template <typename Record>
198 const Record *
200 find(const HashKey& key) const
201 {
202  return table->find(key);
203 }
204 
205 template <typename Record>
207 size() const
208 {
209  return table->size();
210 }
211 
212 template <typename Record>
214 capacity() const
215 {
216  return table->capacity;
217 }
218 
219 template <typename Record>
221 numCacheHit() const
222 {
223  return table->num_cache_hit;
224 }
225 
226 template <typename Record>
229 {
230  return table->num_record_after_full;
231 }
232 
233 template <typename Record>
235 divSize() const
236 {
237  return Table::DIVSIZE;
238 }
239 
240 /* ------------------------------------------------------------------------- */
241 // ;;; Local Variables:
242 // ;;; mode:c++
243 // ;;; c-basic-offset:2
244 // ;;; End: