1 #ifndef DOZERG_HASH_TABLE_H_20130327 2 #define DOZERG_HASH_TABLE_H_20130327 15 #include "tools/other.hh" 16 #include "tools/debug.hh" 17 #include "impl/hash_table_impl.hh" 30 void capacity(
size_t capa){capa_ = capa;}
31 size_t capacity()
const{
return capa_;}
33 void row(
int r){row_ = r;}
34 int row()
const{
return row_;}
36 void setBufSize(
size_t sz){sz_ = sz;}
37 size_t bufSize()
const{
return sz_;}
39 void setHeadBuf(std::vector<char> & buf){buf_.swap(buf);}
41 void upgrade(
char * buf)
const{
42 assert(buf && !buf_.empty());
43 std::copy(buf_.begin(), buf_.end(), buf);
46 std::vector<char> buf_;
68 template<
typename>
class HashKey =
CHashFn,
69 template<
typename>
class EqualKey = std::equal_to
75 typedef NS_IMPL::CMultiRowHashHead __Head;
77 typedef Value value_type;
78 typedef value_type * pointer;
79 typedef const value_type * const_pointer;
80 typedef value_type & reference;
81 typedef const value_type & const_reference;
82 typedef size_t size_type;
83 typedef ptrdiff_t difference_type;
84 typedef KeyOfValue extract_key;
85 typedef typename extract_key::result_type key_type;
86 typedef EmptyKey key_empty;
88 typename COmitCV<key_type>::result_type> hasher;
89 typedef EqualKey<key_type> key_equal;
90 typedef NS_IMPL::CMultiRowHashConstIterator<__Myt> const_iterator;
91 typedef NS_IMPL::CMultiRowHashIterator<__Myt> iterator;
93 typedef typename const_iterator::__Rows __Rows;
94 typedef typename const_iterator::__RowInfo __RowInfo;
95 typedef typename const_iterator::__Iter __Iter;
98 static const uint16_t kCurVersion = 0;
99 static const int kRowMax = 256;
106 static size_t CalcBufSize(
size_t capacity,
int row){
107 if(check(capacity, row)){
108 std::vector<uint32_t> cols;
109 size_t realCapa = tools::PrimesGenerator(capacity, row, cols);
110 if(realCapa >= capacity)
111 return bufSize(row, realCapa);
116 static bool isEmptyKey(const_reference value){
117 return key_empty().isEmpty(extract_key()(value));
135 CMultiRowHashTable(
char * buf,
size_t sz,
size_t capacity,
int row,
bool create =
false)
138 init(buf, sz, capacity, row, create);
143 bool init(
char * buf,
size_t sz){
144 return initAux(buf, sz,
false, 0, 0);
146 bool init(
char * buf,
size_t sz,
size_t capacity,
int row,
bool create =
false){
148 return this->create(buf, sz, capacity, row);
149 return initAux(buf, sz,
true, capacity, row);
157 bool valid()
const{
return (NULL != head_ && !rows_.empty());}
159 int rowSize()
const{
return (head_ ? head_->row_ : 0);}
161 size_t capacityOfRow(
int row)
const{
return rows_[row].capacity();}
163 size_t capacity()
const{
return (head_ ? head_->realCapa_ : 0);}
165 size_t sizeOfRow(
int row)
const{
return rows_[row].used();}
169 for(
int i = 0;i < rowSize();++i)
175 for(
int i = 0;i < rowSize();++i)
176 if(0 != sizeOfRow(i))
181 time_t createTime()
const{
return (head_ ? head_->creatTime_ : 0);}
183 time_t updateTime()
const{
return (head_ ? head_->modTime_ : 0);}
185 time_t upgradeTime()
const{
return (head_ ? head_->upgradeTime_ : 0);}
187 std::string toString(){
190 <<
" head="<<tools::ToStringPtr(head_)<<
'\n';
191 for(
int i = 0;i < rowSize();++i)
192 oss<<
" row["<<i<<
"]="<<rows_[i].toString(usedArray(head_))<<
'\n';
200 iterator find(
const key_type & key){
203 if(findAux(key, it, index,
false))
204 return iterator(it, index);
207 const_iterator find(
const key_type & key)
const{
210 if(findAux(key, it, index,
false))
211 return const_iterator(it, index);
218 iterator insert(const_reference value){
221 if(!findAux(extract_key()(value), it, index,
true))
223 it->setValue(index, value);
225 return iterator(it, index);
231 size_type erase(
const key_type & key){
234 if(!findAux(key, it, index,
false))
236 it->resetValue(index);
240 void erase(iterator it){
246 for(__Iter it = rows_.begin();it != rows_.end();++it)
251 iterator begin(){
return iterator(rows_.begin(), 0);}
252 iterator
end(){
return iterator(rows_.end(), 0);}
253 const_iterator begin()
const{
return const_iterator(rows_.begin(), 0);}
254 const_iterator
end()
const{
return const_iterator(rows_.end(), 0);}
278 const size_t newCapa = up.capacity();
280 if(!check(newCapa, row))
283 const uint32_t *
const colsp = colsArray(head_);
284 std::vector<uint32_t> cols(colsp, colsp + rowSize());
285 size_t realCapa = capacity();
287 if(newCapa <= realCapa){
288 for(;cols.size() > size_t(row);cols.pop_back()){
289 assert(!cols.empty());
290 if(realCapa < newCapa + cols.back())
292 realCapa -= cols.back();
294 assert(!cols.empty());
296 realCapa = tools::PrimesGenerator(newCapa, row, cols);
297 if(realCapa < newCapa)
303 std::vector<char> headBuf(headSize(row));
304 __Head & head = *
reinterpret_cast<__Head *
>(&headBuf[0]);
305 initHead(head, row, up.capacity(), realCapa,
false);
306 head.creatTime_ = createTime();
307 head.modTime_ = updateTime();
309 const uint32_t *
const oldUsed = usedArray(head_);
310 std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head));
312 std::copy(cols.begin(), cols.end(), colsArray(&head));
314 up.setBufSize(bufSize(row, realCapa));
315 up.setHeadBuf(headBuf);
324 init(buf, up.bufSize());
327 static bool check(
size_t capacity,
int row){
return (0 < row && row <= kRowMax &&
size_t(row) <= capacity);}
328 static bool check(
const __Head & head){
329 return (kCurVersion == head.version_
330 &&
sizeof(value_type) == head.valueSz_
331 && check(head.capacity_, head.row_)
332 && head.capacity_ <= head.realCapa_
333 && 0 < head.creatTime_
334 && head.modTime_ >= head.creatTime_);
336 static bool check(
const __Head & head,
size_t capacity,
int row){
337 return (capacity == head.capacity_ && row == head.row_);
339 static bool check(
const uint32_t * cols,
const uint32_t * used,
const __Head & head){
340 assert(cols && used);
342 for(uint16_t i = 0;i < head.row_;++i){
343 if(cols[i] < used[i])
347 return (total == head.realCapa_);
349 static size_t headSize(
int row){
return 4096;}
350 static size_t bufSize(
int row,
size_t realCapa){
return (headSize(row) +
sizeof(value_type) * realCapa);}
351 static uint32_t * usedArray(__Head * head){
353 return reinterpret_cast<uint32_t *
>(head + 1);
355 static const uint32_t * usedArray(
const __Head * head){
357 return reinterpret_cast<const uint32_t *
>(head + 1);
359 static uint32_t * colsArray(__Head * head){
361 return (usedArray(head) + kRowMax);
363 static const uint32_t * colsArray(
const __Head * head){
365 return (usedArray(head) + kRowMax);
367 static pointer dataArray(__Head * head){
369 return reinterpret_cast<pointer
>(
reinterpret_cast<char *
>(head) + headSize(head->row_));
371 static void initHead(__Head & head,
int row,
size_t capacity,
size_t realCapa,
bool create){
372 head.version_ = kCurVersion;
374 head.valueSz_ =
sizeof(value_type);
375 head.capacity_ = capacity;
376 head.realCapa_ = realCapa;
378 head.modTime_ = head.creatTime_ = tools::Time(NULL);
380 head.upgradeTime_ = tools::Time(NULL);
382 bool initAux(
char * buf,
size_t sz,
bool hasCR,
size_t capacity,
int row){
386 if(NULL == buf || sz <
sizeof(__Head))
388 __Head & head = *
reinterpret_cast<__Head *
>(buf);
391 if(hasCR && !check(head, capacity, row))
393 if(sz < bufSize(head.row_, head.realCapa_))
395 uint32_t *
const used = usedArray(&head);
396 uint32_t *
const cols = colsArray(&head);
397 if(!check(cols, used, head))
401 initRows(cols, used);
404 bool create(
char * buf,
size_t sz,
size_t capacity,
int row){
408 if(NULL == buf || sz <
sizeof(__Head))
410 if(!check(capacity, row))
412 __Head & head = *
reinterpret_cast<__Head *
>(buf);
413 std::vector<uint32_t> cols;
414 const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols);
415 if(realCapa < capacity ||
size_t(row) != cols.size())
417 if(sz < bufSize(row, realCapa))
423 initHead(head, row, capacity, realCapa,
true);
425 uint32_t *
const used = usedArray(head_);
427 uint32_t *
const colp = colsArray(head_);
428 std::sort(cols.begin(), cols.end(), std::greater<uint32_t>());
429 std::copy(cols.begin(), cols.end(), colp);
431 initRows(colp, used);
434 void initRows(uint32_t * cols, uint32_t * used){
435 assert(cols && used && head_ && rows_.empty());
436 pointer p = dataArray(head_);
437 rows_.reserve(head_->row_);
438 for(uint16_t i = 0;i < head_->row_;++i){
439 rows_.push_back(__RowInfo(cols[i], &used[i], p));
442 std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>());
444 bool findAux(
const key_type & key, __Iter & it, uint32_t & index,
bool forInsert)
const{
450 uint32_t hash = hasher()(key);
453 for(it = rows_.begin();it != rows_.end();++it){
454 index = it->indexOf(hash);
456 if(em.isEmpty(keyOf(it->valueOf(index))))
459 if(equal(key, keyOf(it->valueOf(index))))
470 mutable __Rows rows_;
Definition: to_string.hh:43
Definition: hash_table.hh:21
Definition: hash_table.hh:70
NS_IMPL::CManipulatorEnd< void, void > end()
End operations for CInByteStream, COutByteStreamStrRef, COutByteStreamVecRef.
Definition: data_stream.hh:929
Definition: template.hh:165
Definition: template.hh:174