Marine Library  1.0
C++ library for Linux Networking Development
hash_table.hh
1 #ifndef DOZERG_HASH_TABLE_H_20130327
2 #define DOZERG_HASH_TABLE_H_20130327
3 
4 /*
5  多阶Hash表,线程不安全
6  CMultiRowHashTable 多阶hash表,支持定长key+value
7  CMultiRowHashUpgrade 多阶hash表升级辅助类
8  TODO:
9  增加create/upgrade seq,避免访问过程中hash表被意外create或upgrade
10 */
11 
12 #include <algorithm> //std::copy, std::sort
13 #include <functional> //std::greater, std::equal_to
14 #include <cstring>
15 #include "tools/other.hh" //PrimesGenerator
16 #include "tools/debug.hh" //ToStringPtr
17 #include "impl/hash_table_impl.hh"
18 
19 NS_SERVER_BEGIN
20 
22 {
23 public:
24  explicit CMultiRowHashUpgrade(size_t capacity = 0, int row = 0)
25  : capa_(capacity)
26  , sz_(0)
27  , row_(row)
28  {}
29  //设置/获取容量
30  void capacity(size_t capa){capa_ = capa;}
31  size_t capacity() const{return capa_;}
32  //设置/获取行数
33  void row(int r){row_ = r;}
34  int row() const{return row_;}
35  //设置/获取数据内存字节大小
36  void setBufSize(size_t sz){sz_ = sz;}
37  size_t bufSize() const{return sz_;}
38  //设置head
39  void setHeadBuf(std::vector<char> & buf){buf_.swap(buf);}
40  //修改hash表 void upgrade(char * buf) const{ assert(buf && !buf_.empty()); std::copy(buf_.begin(), buf_.end(), buf); } private: std::vector<char> buf_; size_t capa_; size_t sz_; int row_; }; //Value: 元素类型,必须是POD或者C struct类型 //KeyOfValue: 至少实现以下成员 // typedef key_type result_type; //key的类型 // key_type & operator ()(value_type & v) const; //从元素中取出key // const key_type & operator()(const value_type & v) const; //从元素中取出key //EmptyKey: 至少实现以下成员函数 // bool isEmpty(const key_type & key) const; //判断key是否未使用 // void resetKey(key_type * key) const; //将key设置成未使用 //HashKey: 至少实现以下成员函数 // size_t operator ()(const key_type & key) const; //计算key对应的hash值 //EqualKey: 至少实现以下成员函数 // bool operator ()(const key_type & key1, const key_type & key2) const; //判断2个key是否相等 template< typename Value, class EmptyKey, class KeyOfValue = CIdentity<Value>, template<typename>class HashKey = CHashFn, template<typename>class EqualKey = std::equal_to >class CMultiRowHashTable { private: //typedefs typedef CMultiRowHashTable<Value, EmptyKey, KeyOfValue, HashKey, EqualKey> __Myt; typedef NS_IMPL::CMultiRowHashHead __Head; public: typedef Value value_type; typedef value_type * pointer; typedef const value_type * const_pointer; typedef value_type & reference; typedef const value_type & const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef KeyOfValue extract_key; typedef typename extract_key::result_type key_type; typedef EmptyKey key_empty; typedef HashKey< typename COmitCV<key_type>::result_type> hasher; typedef EqualKey<key_type> key_equal; typedef NS_IMPL::CMultiRowHashConstIterator<__Myt> const_iterator; typedef NS_IMPL::CMultiRowHashIterator<__Myt> iterator; private: typedef typename const_iterator::__Rows __Rows; typedef typename const_iterator::__RowInfo __RowInfo; typedef typename const_iterator::__Iter __Iter; public: //constants static const uint16_t kCurVersion = 0; //当前version static const int kRowMax = 256; //允许的最多行数 //根据capacity和row计算需要的内存字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
41  void upgrade(char * buf) const{
42  assert(buf && !buf_.empty());
43  std::copy(buf_.begin(), buf_.end(), buf);
44  }
45 private:
46  std::vector<char> buf_;
47  size_t capa_;
48  size_t sz_;
49  int row_;
50 };
51 
52 //Value: 元素类型,必须是POD或者C struct类型
53 //KeyOfValue: 至少实现以下成员
54 // typedef key_type result_type; //key的类型// key_type & operator ()(value_type & v) const; //从元素中取出key // const key_type & operator()(const value_type & v) const; //从元素中取出key //EmptyKey: 至少实现以下成员函数 // bool isEmpty(const key_type & key) const; //判断key是否未使用 // void resetKey(key_type * key) const; //将key设置成未使用 //HashKey: 至少实现以下成员函数 // size_t operator ()(const key_type & key) const; //计算key对应的hash值 //EqualKey: 至少实现以下成员函数 // bool operator ()(const key_type & key1, const key_type & key2) const; //判断2个key是否相等 template< typename Value, class EmptyKey, class KeyOfValue = CIdentity<Value>, template<typename>class HashKey = CHashFn, template<typename>class EqualKey = std::equal_to >class CMultiRowHashTable { private: //typedefs typedef CMultiRowHashTable<Value, EmptyKey, KeyOfValue, HashKey, EqualKey> __Myt; typedef NS_IMPL::CMultiRowHashHead __Head; public: typedef Value value_type; typedef value_type * pointer; typedef const value_type * const_pointer; typedef value_type & reference; typedef const value_type & const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef KeyOfValue extract_key; typedef typename extract_key::result_type key_type; typedef EmptyKey key_empty; typedef HashKey< typename COmitCV<key_type>::result_type> hasher; typedef EqualKey<key_type> key_equal; typedef NS_IMPL::CMultiRowHashConstIterator<__Myt> const_iterator; typedef NS_IMPL::CMultiRowHashIterator<__Myt> iterator; private: typedef typename const_iterator::__Rows __Rows; typedef typename const_iterator::__RowInfo __RowInfo; typedef typename const_iterator::__Iter __Iter; public: //constants static const uint16_t kCurVersion = 0; //当前version static const int kRowMax = 256; //允许的最多行数 //根据capacity和row计算需要的内存字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
55 // key_type & operator ()(value_type & v) const; //从元素中取出key
56 // const key_type & operator()(const value_type & v) const; //从元素中取出key
57 //EmptyKey: 至少实现以下成员函数
58 // bool isEmpty(const key_type & key) const; //判断key是否未使用
59 // void resetKey(key_type * key) const; //将key设置成未使用
60 //HashKey: 至少实现以下成员函数
61 // size_t operator ()(const key_type & key) const; //计算key对应的hash值
62 //EqualKey: 至少实现以下成员函数
63 // bool operator ()(const key_type & key1, const key_type & key2) const; //判断2个key是否相等template< typename Value, class EmptyKey, class KeyOfValue = CIdentity<Value>, template<typename>class HashKey = CHashFn, template<typename>class EqualKey = std::equal_to >class CMultiRowHashTable { private: //typedefs typedef CMultiRowHashTable<Value, EmptyKey, KeyOfValue, HashKey, EqualKey> __Myt; typedef NS_IMPL::CMultiRowHashHead __Head; public: typedef Value value_type; typedef value_type * pointer; typedef const value_type * const_pointer; typedef value_type & reference; typedef const value_type & const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef KeyOfValue extract_key; typedef typename extract_key::result_type key_type; typedef EmptyKey key_empty; typedef HashKey< typename COmitCV<key_type>::result_type> hasher; typedef EqualKey<key_type> key_equal; typedef NS_IMPL::CMultiRowHashConstIterator<__Myt> const_iterator; typedef NS_IMPL::CMultiRowHashIterator<__Myt> iterator; private: typedef typename const_iterator::__Rows __Rows; typedef typename const_iterator::__RowInfo __RowInfo; typedef typename const_iterator::__Iter __Iter; public: //constants static const uint16_t kCurVersion = 0; //当前version static const int kRowMax = 256; //允许的最多行数 //根据capacity和row计算需要的内存字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
64 template<
65  typename Value,
66  class EmptyKey,
67  class KeyOfValue = CIdentity<Value>,
68  template<typename>class HashKey = CHashFn,
69  template<typename>class EqualKey = std::equal_to
71 {
72 private:
73  //typedefs
75  typedef NS_IMPL::CMultiRowHashHead __Head;
76 public:
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;
87  typedef HashKey<
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;
92 private:
93  typedef typename const_iterator::__Rows __Rows;
94  typedef typename const_iterator::__RowInfo __RowInfo;
95  typedef typename const_iterator::__Iter __Iter;
96 public:
97  //constants
98  static const uint16_t kCurVersion = 0; //当前version
99  static const int kRowMax = 256; //允许的最多行数 //根据capacity和row计算需要的内存字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
100  //根据capacity和row计算需要的内存字节大小
101  //capacity: 需要容纳的元素个数 //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
102  //row: hash表的行数 //return: // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
103  //return:
104  // 0 失败 // 其他 需要的内存字节大小 static size_t CalcBufSize(size_t capacity, int row){ if(check(capacity, row)){ std::vector<uint32_t> cols; size_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa >= capacity) return bufSize(row, realCapa); } return 0; } //判断value的key是否未使用 static bool isEmptyKey(const_reference value){ return key_empty().isEmpty(extract_key()(value)); } //构造/初始化 //buf: 数据内存,由调用者保证有效性 //sz: buf的字节大小 //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
105  // 其他 需要的内存字节大小
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);
112  }
113  return 0;
114  }
115  //判断value的key是否未使用
116  static bool isEmptyKey(const_reference value){
117  return key_empty().isEmpty(extract_key()(value));
118  }
119  //构造/初始化
120  //buf: 数据内存,由调用者保证有效性
121  //sz: buf的字节大小
122  //capacity: 需要容纳的元素个数 //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
123  //row: hash表的行数 //create: // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
124  //create:
125  // true 创建hash表,清空旧数据 // false 使用已有hash表,检查buf内容的有效性 CMultiRowHashTable() : head_(NULL) {} CMultiRowHashTable(char * buf, size_t sz) : head_(NULL) { init(buf, sz); } CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false) : head_(NULL) { init(buf, sz, capacity, row, create); } //return: // true 成功 // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
126  // false 使用已有hash表,检查buf内容的有效性
128  : head_(NULL)
129  {}
130  CMultiRowHashTable(char * buf, size_t sz)
131  : head_(NULL)
132  {
133  init(buf, sz);
134  }
135  CMultiRowHashTable(char * buf, size_t sz, size_t capacity, int row, bool create = false)
136  : head_(NULL)
137  {
138  init(buf, sz, capacity, row, create);
139  }
140  //return:
141  // true 成功
142  // false 失败 bool init(char * buf, size_t sz){ return initAux(buf, sz, false, 0, 0); } bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){ if(create) return this->create(buf, sz, capacity, row); return initAux(buf, sz, true, capacity, row); } //重置当前对象,hash表数据不受影响 void uninit(){ head_ = NULL; rows_.clear(); } //是否初始化 bool valid() const{return (NULL != head_ && !rows_.empty());} //获取行数 int rowSize() const{return (head_ ? head_->row_ : 0);} //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
143  bool init(char * buf, size_t sz){
144  return initAux(buf, sz, false, 0, 0);
145  }
146  bool init(char * buf, size_t sz, size_t capacity, int row, bool create = false){
147  if(create)
148  return this->create(buf, sz, capacity, row);
149  return initAux(buf, sz, true, capacity, row);
150  }
151  //重置当前对象,hash表数据不受影响
152  void uninit(){
153  head_ = NULL;
154  rows_.clear();
155  }
156  //是否初始化
157  bool valid() const{return (NULL != head_ && !rows_.empty());}
158  //获取行数
159  int rowSize() const{return (head_ ? head_->row_ : 0);}
160  //获取每行可容纳的元素个数 size_t capacityOfRow(int row) const{return rows_[row].capacity();} //获取可容纳的元素总数 size_t capacity() const{return (head_ ? head_->realCapa_ : 0);} //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
161  size_t capacityOfRow(int row) const{return rows_[row].capacity();}
162  //获取可容纳的元素总数
163  size_t capacity() const{return (head_ ? head_->realCapa_ : 0);}
164  //获取每行已使用的元素个数 size_t sizeOfRow(int row) const{return rows_[row].used();} //获取已使用的元素总数 size_t size() const{ size_t ret = 0; for(int i = 0;i < rowSize();++i) ret += sizeOfRow(i); return ret; } //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
165  size_t sizeOfRow(int row) const{return rows_[row].used();}
166  //获取已使用的元素总数
167  size_t size() const{
168  size_t ret = 0;
169  for(int i = 0;i < rowSize();++i)
170  ret += sizeOfRow(i);
171  return ret;
172  }
173  //是否为空 bool empty() const{ for(int i = 0;i < rowSize();++i) if(0 != sizeOfRow(i)) return false; return true; } //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
174  bool empty() const{
175  for(int i = 0;i < rowSize();++i)
176  if(0 != sizeOfRow(i))
177  return false;
178  return true;
179  }
180  //获取创建时间 time_t createTime() const{return (head_ ? head_->creatTime_ : 0);} //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
181  time_t createTime() const{return (head_ ? head_->creatTime_ : 0);}
182  //获取最近修改时间 time_t updateTime() const{return (head_ ? head_->modTime_ : 0);} //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
183  time_t updateTime() const{return (head_ ? head_->modTime_ : 0);}
184  //获取最近升级时间 time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);} //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
185  time_t upgradeTime() const{return (head_ ? head_->upgradeTime_ : 0);}
186  //输出hash表可读描述 std::string toString(){ CToString oss; oss<<"{\n" <<" head="<<tools::ToStringPtr(head_)<<'\n'; for(int i = 0;i < rowSize();++i) oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n'; oss<<"}"; return oss.str(); } //搜索元素 //return: // end() 没有找到 // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
187  std::string toString(){
188  CToString oss;
189  oss<<"{\n"
190  <<" head="<<tools::ToStringPtr(head_)<<'\n';
191  for(int i = 0;i < rowSize();++i)
192  oss<<" row["<<i<<"]="<<rows_[i].toString(usedArray(head_))<<'\n';
193  oss<<"}";
194  return oss.str();
195  }
196  //搜索元素
197  //return:
198  // end() 没有找到
199  // 其他 元素对应的迭代器 iterator find(const key_type & key){ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return iterator(it, index); return end(); } const_iterator find(const key_type & key) const{ __Iter it; uint32_t index; if(findAux(key, it, index, false)) return const_iterator(it, index); return end(); } //插入元素 //return: // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
200  iterator find(const key_type & key){
201  __Iter it;
202  uint32_t index;
203  if(findAux(key, it, index, false))
204  return iterator(it, index);
205  return end();
206  }
207  const_iterator find(const key_type & key) const{
208  __Iter it;
209  uint32_t index;
210  if(findAux(key, it, index, false))
211  return const_iterator(it, index);
212  return end();
213  }
214  //插入元素
215  //return:
216  // end() 插入失败 // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
217  // 其他 插入成功,元素对应的迭代器 iterator insert(const_reference value){ __Iter it; uint32_t index; if(!findAux(extract_key()(value), it, index, true)) return end(); it->setValue(index, value); update(); return iterator(it, index); } //删除元素 //key: 要删除的元素key //it: 要删除的iterator //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
218  iterator insert(const_reference value){
219  __Iter it;
220  uint32_t index;
221  if(!findAux(extract_key()(value), it, index, true))
222  return end();
223  it->setValue(index, value);
224  update();
225  return iterator(it, index);
226  }
227  //删除元素
228  //key: 要删除的元素key
229  //it: 要删除的iterator
230  //return: 实际删除的元素个数 size_type erase(const key_type & key){ __Iter it; uint32_t index; if(!findAux(key, it, index, false)) return 0; it->resetValue(index); update(); return 1; } void erase(iterator it){ it.resetValue(); update(); } //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
231  size_type erase(const key_type & key){
232  __Iter it;
233  uint32_t index;
234  if(!findAux(key, it, index, false))
235  return 0;
236  it->resetValue(index);
237  update();
238  return 1;
239  }
240  void erase(iterator it){
241  it.resetValue();
242  update();
243  }
244  //清空hash表 void clear(){ for(__Iter it = rows_.begin();it != rows_.end();++it) it->clear(); update(); } //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
245  void clear(){
246  for(__Iter it = rows_.begin();it != rows_.end();++it)
247  it->clear();
248  update();
249  }
250  //获取迭代器 iterator begin(){return iterator(rows_.begin(), 0);} iterator end(){return iterator(rows_.end(), 0);} const_iterator begin() const{return const_iterator(rows_.begin(), 0);} const_iterator end() const{return const_iterator(rows_.end(), 0);} //----hash表升级流程---- //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
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);}
255 
256  //----hash表升级流程----
257  //1. 设置升级后的容量和行数 // CMultiRowHashUpgrade up(newCapa, newRow); //2. 模拟升级 // if(!ht.upgradeCalc(up)) // cerr<<"ht cannot upgrade to newCapa and newRow!"; //3. 伸缩数据内存(伪码) // if(!expandOrShrink(buf, up.bufSize())) // cerr<<"expand or shrink buf to newSize failed!"; //4. 真正升级 // ht.upgradeCommit(buf, sz, up); //---------完成--------- //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
258  // CMultiRowHashUpgrade up(newCapa, newRow);
259  //2. 模拟升级
260  // if(!ht.upgradeCalc(up))
261  // cerr<<"ht cannot upgrade to newCapa and newRow!";
262  //3. 伸缩数据内存(伪码)
263  // if(!expandOrShrink(buf, up.bufSize()))
264  // cerr<<"expand or shrink buf to newSize failed!";
265  //4. 真正升级
266  // ht.upgradeCommit(buf, sz, up);
267  //---------完成---------
268 
269  //将当前hash表模拟升级,不改变hash表数据 //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade; //return: // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
270  //up: 升级的所有参数和计算结果,详见class CMultiRowHashUpgrade;
271  //return:
272  // false 失败 // true 成功 bool upgradeCalc(CMultiRowHashUpgrade & up) const{ //check if(!valid()) return false; const size_t newCapa = up.capacity(); int row = up.row(); if(!check(newCapa, row)) return false; //calc new cols const uint32_t * const colsp = colsArray(head_); std::vector<uint32_t> cols(colsp, colsp + rowSize()); size_t realCapa = capacity(); assert(colsp); if(newCapa <= realCapa){ //shrink for(;cols.size() > size_t(row);cols.pop_back()){ assert(!cols.empty()); if(realCapa < newCapa + cols.back()) break; realCapa -= cols.back(); } assert(!cols.empty()); }else{ //expand realCapa = tools::PrimesGenerator(newCapa, row, cols); if(realCapa < newCapa) return false; } //calc new head //head row = cols.size(); std::vector<char> headBuf(headSize(row)); __Head & head = *reinterpret_cast<__Head *>(&headBuf[0]); initHead(head, row, up.capacity(), realCapa, false); head.creatTime_ = createTime(); head.modTime_ = updateTime(); //used const uint32_t * const oldUsed = usedArray(head_); std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head)); //cols std::copy(cols.begin(), cols.end(), colsArray(&head)); //save head up.setBufSize(bufSize(row, realCapa)); up.setHeadBuf(headBuf); return true; } //将当前hash表真正升级 //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小 //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
273  // true 成功
274  bool upgradeCalc(CMultiRowHashUpgrade & up) const{
275  //check
276  if(!valid())
277  return false;
278  const size_t newCapa = up.capacity();
279  int row = up.row();
280  if(!check(newCapa, row))
281  return false;
282  //calc new cols
283  const uint32_t * const colsp = colsArray(head_);
284  std::vector<uint32_t> cols(colsp, colsp + rowSize());
285  size_t realCapa = capacity();
286  assert(colsp);
287  if(newCapa <= realCapa){ //shrink
288  for(;cols.size() > size_t(row);cols.pop_back()){
289  assert(!cols.empty());
290  if(realCapa < newCapa + cols.back())
291  break;
292  realCapa -= cols.back();
293  }
294  assert(!cols.empty());
295  }else{ //expand
296  realCapa = tools::PrimesGenerator(newCapa, row, cols);
297  if(realCapa < newCapa)
298  return false;
299  }
300  //calc new head
301  //head
302  row = cols.size();
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();
308  //used
309  const uint32_t * const oldUsed = usedArray(head_);
310  std::copy(oldUsed, oldUsed + kRowMax, usedArray(&head));
311  //cols
312  std::copy(cols.begin(), cols.end(), colsArray(&head));
313  //save head
314  up.setBufSize(bufSize(row, realCapa));
315  up.setHeadBuf(headBuf);
316  return true;
317  }
318  //将当前hash表真正升级
319  //buf: 升级后hash表的数据内存,调用者保证有效性和字节大小
320  //up: 升级的所有参数和计算结果,必须是经过upgradeCalc()处理的 void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){ up.upgrade(buf); uninit(); init(buf, up.bufSize()); } private: static bool check(size_t capacity, int row){return (0 < row && row <= kRowMax && size_t(row) <= capacity);} static bool check(const __Head & head){ return (kCurVersion == head.version_ && sizeof(value_type) == head.valueSz_ && check(head.capacity_, head.row_) && head.capacity_ <= head.realCapa_ && 0 < head.creatTime_ && head.modTime_ >= head.creatTime_); } static bool check(const __Head & head, size_t capacity, int row){ return (capacity == head.capacity_ && row == head.row_); } static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){ assert(cols && used); size_t total = 0; for(uint16_t i = 0;i < head.row_;++i){ if(cols[i] < used[i]) return false; total += cols[i]; } return (total == head.realCapa_); } static size_t headSize(int row){return 4096;} static size_t bufSize(int row, size_t realCapa){return (headSize(row) + sizeof(value_type) * realCapa);} static uint32_t * usedArray(__Head * head){ assert(head); return reinterpret_cast<uint32_t *>(head + 1); } static const uint32_t * usedArray(const __Head * head){ assert(head); return reinterpret_cast<const uint32_t *>(head + 1); } static uint32_t * colsArray(__Head * head){ assert(head); return (usedArray(head) + kRowMax); } static const uint32_t * colsArray(const __Head * head){ assert(head); return (usedArray(head) + kRowMax); } static pointer dataArray(__Head * head){ assert(head); return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_)); } static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){ head.version_ = kCurVersion; head.row_ = row; head.valueSz_ = sizeof(value_type); head.capacity_ = capacity; head.realCapa_ = realCapa; if(create) head.modTime_ = head.creatTime_ = tools::Time(NULL); else head.upgradeTime_ = tools::Time(NULL); } bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); if(!check(head)) return false; if(hasCR && !check(head, capacity, row)) return false; if(sz < bufSize(head.row_, head.realCapa_)) return false; uint32_t * const used = usedArray(&head); uint32_t * const cols = colsArray(&head); if(!check(cols, used, head)) return false; //set head_ = &head; initRows(cols, used); return true; } bool create(char * buf, size_t sz, size_t capacity, int row){ //check if(valid()) return false; if(NULL == buf || sz < sizeof(__Head)) return false; if(!check(capacity, row)) return false; __Head & head = *reinterpret_cast<__Head *>(buf); std::vector<uint32_t> cols; const uint64_t realCapa = tools::PrimesGenerator(capacity, row, cols); if(realCapa < capacity || size_t(row) != cols.size()) return false; if(sz < bufSize(row, realCapa)) return false; //set memset(buf, 0, sz); //head head_ = &head; initHead(head, row, capacity, realCapa, true); //used uint32_t * const used = usedArray(head_); //cols uint32_t * const colp = colsArray(head_); std::sort(cols.begin(), cols.end(), std::greater<uint32_t>()); std::copy(cols.begin(), cols.end(), colp); //rows initRows(colp, used); return true; } void initRows(uint32_t * cols, uint32_t * used){ assert(cols && used && head_ && rows_.empty()); pointer p = dataArray(head_); rows_.reserve(head_->row_); for(uint16_t i = 0;i < head_->row_;++i){ rows_.push_back(__RowInfo(cols[i], &used[i], p)); p += cols[i]; } std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>()); } bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{ if(!valid()) return false; key_empty em; if(em.isEmpty(key)) return false; uint32_t hash = hasher()(key); extract_key keyOf; key_equal equal; for(it = rows_.begin();it != rows_.end();++it){ index = it->indexOf(hash); if(forInsert){ if(em.isEmpty(keyOf(it->valueOf(index)))) return true; }else{ if(equal(key, keyOf(it->valueOf(index)))) return true; } } return false; } void update(){ if(head_) head_->update(); } //fields mutable __Rows rows_; //每行的信息 __Head * head_; //hash表头 }; NS_SERVER_END #endif
321  void upgradeCommit(char * buf, const CMultiRowHashUpgrade & up){
322  up.upgrade(buf);
323  uninit();
324  init(buf, up.bufSize());
325  }
326 private:
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_);
335  }
336  static bool check(const __Head & head, size_t capacity, int row){
337  return (capacity == head.capacity_ && row == head.row_);
338  }
339  static bool check(const uint32_t * cols, const uint32_t * used, const __Head & head){
340  assert(cols && used);
341  size_t total = 0;
342  for(uint16_t i = 0;i < head.row_;++i){
343  if(cols[i] < used[i])
344  return false;
345  total += cols[i];
346  }
347  return (total == head.realCapa_);
348  }
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){
352  assert(head);
353  return reinterpret_cast<uint32_t *>(head + 1);
354  }
355  static const uint32_t * usedArray(const __Head * head){
356  assert(head);
357  return reinterpret_cast<const uint32_t *>(head + 1);
358  }
359  static uint32_t * colsArray(__Head * head){
360  assert(head);
361  return (usedArray(head) + kRowMax);
362  }
363  static const uint32_t * colsArray(const __Head * head){
364  assert(head);
365  return (usedArray(head) + kRowMax);
366  }
367  static pointer dataArray(__Head * head){
368  assert(head);
369  return reinterpret_cast<pointer>(reinterpret_cast<char *>(head) + headSize(head->row_));
370  }
371  static void initHead(__Head & head, int row, size_t capacity, size_t realCapa, bool create){
372  head.version_ = kCurVersion;
373  head.row_ = row;
374  head.valueSz_ = sizeof(value_type);
375  head.capacity_ = capacity;
376  head.realCapa_ = realCapa;
377  if(create)
378  head.modTime_ = head.creatTime_ = tools::Time(NULL);
379  else
380  head.upgradeTime_ = tools::Time(NULL);
381  }
382  bool initAux(char * buf, size_t sz, bool hasCR, size_t capacity, int row){
383  //check
384  if(valid())
385  return false;
386  if(NULL == buf || sz < sizeof(__Head))
387  return false;
388  __Head & head = *reinterpret_cast<__Head *>(buf);
389  if(!check(head))
390  return false;
391  if(hasCR && !check(head, capacity, row))
392  return false;
393  if(sz < bufSize(head.row_, head.realCapa_))
394  return false;
395  uint32_t * const used = usedArray(&head);
396  uint32_t * const cols = colsArray(&head);
397  if(!check(cols, used, head))
398  return false;
399  //set
400  head_ = &head;
401  initRows(cols, used);
402  return true;
403  }
404  bool create(char * buf, size_t sz, size_t capacity, int row){
405  //check
406  if(valid())
407  return false;
408  if(NULL == buf || sz < sizeof(__Head))
409  return false;
410  if(!check(capacity, row))
411  return false;
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())
416  return false;
417  if(sz < bufSize(row, realCapa))
418  return false;
419  //set
420  memset(buf, 0, sz);
421  //head
422  head_ = &head;
423  initHead(head, row, capacity, realCapa, true);
424  //used
425  uint32_t * const used = usedArray(head_);
426  //cols
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);
430  //rows
431  initRows(colp, used);
432  return true;
433  }
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));
440  p += cols[i];
441  }
442  std::sort(rows_.begin(), rows_.end(), std::greater<__RowInfo>());
443  }
444  bool findAux(const key_type & key, __Iter & it, uint32_t & index, bool forInsert) const{
445  if(!valid())
446  return false;
447  key_empty em;
448  if(em.isEmpty(key))
449  return false;
450  uint32_t hash = hasher()(key);
451  extract_key keyOf;
452  key_equal equal;
453  for(it = rows_.begin();it != rows_.end();++it){
454  index = it->indexOf(hash);
455  if(forInsert){
456  if(em.isEmpty(keyOf(it->valueOf(index))))
457  return true;
458  }else{
459  if(equal(key, keyOf(it->valueOf(index))))
460  return true;
461  }
462  }
463  return false;
464  }
465  void update(){
466  if(head_)
467  head_->update();
468  }
469  //fields
470  mutable __Rows rows_; //每行的信息
471  __Head * head_; //hash表头
472 };
473 
474 NS_SERVER_END
475 
476 #endif
477 
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