#include "data_structure/hash_map.hpp"
#pragma once #include<tuple> /** * @brief HashMap */ template<typename T,typename E,typename F=std::hash<T>> struct hash_map{ struct node{ T key;E val; unsigned long b; node():key(T()),val(E()),b(0){} node(T key,E val):key(key),val(val),b(0){} static node* alc; static size_t cnt; static size_t alc_sz; void* operator new(size_t){ if(alc_sz==cnt){ alc_sz*=2; alc=(node*)malloc(alc_sz*sizeof(node)); cnt=0; } return alc+cnt++; } }; size_t sz; node* point; constexpr static size_t mod_list[24]={37,67,131,257,521,1031,2053,4099,8209,16411,32771,65537,131101,262147,524309,1048583,2097169,4194319,8388617,16777259,33554467,67108879,134217757,268435459}; node** table; F op; hash_map(F op=F()):sz(15),op(op){ table=new node*[mod_list[sz]](); } node** _realloc(){ const size_t old_sz=sz; while(1){ sz++; bool fail=0; node** tmp=new node*[mod_list[sz]](); for(node** itr=table;itr<table+mod_list[old_sz];++itr){ if(*itr==0)continue; const size_t ha=op((*itr)->key)%mod_list[sz]; (*itr)->b=0; if(insert(tmp,*itr,ha).first==0){fail=1;break;} } if(fail){ delete[] tmp; } else { delete[] table; table=tmp; break; } } return table; } std::pair<bool,node*> insert(node** table,node* t,size_t tmp){ if(!table[tmp])return {true,table[tmp]=t}; size_t k=0; unsigned long tt=~table[tmp]->b; const size_t pre=tmp; unsigned long x=1; while(tt){ tmp+=(k=__builtin_ctzl(tt)+1); x<<=k; tt>>=k; tmp%=mod_list[sz]; if(!table[tmp]){ table[tmp]=t; table[pre]->b|=x>>1; return {true,table[tmp]}; } } return {false,nullptr}; } std::pair<bool,node*> search(T key,size_t tmp){ int k=0; if(!table[tmp])return {false,nullptr}; if(table[tmp]->key==key)return {true,table[tmp]}; unsigned long t=table[tmp]->b; while(t){ tmp+=(k=__builtin_ctzl(t)+1); tmp%=mod_list[sz]; t>>=k; if(table[tmp]->key==key)return {true,table[tmp]}; } return {false,nullptr}; } E& operator[](T key){ size_t ha=op(key)%mod_list[sz]; auto res=search(key,ha); if(res.first)return res.second->val; else { while(1){ auto res=insert(table,new node(key,E()),ha); if(res.first)return res.second->val; _realloc(); ha=op(key)%mod_list[sz]; } } } }; template<typename T,typename E,typename F=std::hash<T>>typename hash_map<T,E,F>::node* hash_map<T,E,F>::node::alc=(node*)malloc(sizeof(node)); template<typename T,typename E,typename F=std::hash<T>>size_t hash_map<T,E,F>::node::cnt=0; template<typename T,typename E,typename F=std::hash<T>>size_t hash_map<T,E,F>::node::alc_sz=1;
#line 2 "data_structure/hash_map.hpp" #include<tuple> /** * @brief HashMap */ template<typename T,typename E,typename F=std::hash<T>> struct hash_map{ struct node{ T key;E val; unsigned long b; node():key(T()),val(E()),b(0){} node(T key,E val):key(key),val(val),b(0){} static node* alc; static size_t cnt; static size_t alc_sz; void* operator new(size_t){ if(alc_sz==cnt){ alc_sz*=2; alc=(node*)malloc(alc_sz*sizeof(node)); cnt=0; } return alc+cnt++; } }; size_t sz; node* point; constexpr static size_t mod_list[24]={37,67,131,257,521,1031,2053,4099,8209,16411,32771,65537,131101,262147,524309,1048583,2097169,4194319,8388617,16777259,33554467,67108879,134217757,268435459}; node** table; F op; hash_map(F op=F()):sz(15),op(op){ table=new node*[mod_list[sz]](); } node** _realloc(){ const size_t old_sz=sz; while(1){ sz++; bool fail=0; node** tmp=new node*[mod_list[sz]](); for(node** itr=table;itr<table+mod_list[old_sz];++itr){ if(*itr==0)continue; const size_t ha=op((*itr)->key)%mod_list[sz]; (*itr)->b=0; if(insert(tmp,*itr,ha).first==0){fail=1;break;} } if(fail){ delete[] tmp; } else { delete[] table; table=tmp; break; } } return table; } std::pair<bool,node*> insert(node** table,node* t,size_t tmp){ if(!table[tmp])return {true,table[tmp]=t}; size_t k=0; unsigned long tt=~table[tmp]->b; const size_t pre=tmp; unsigned long x=1; while(tt){ tmp+=(k=__builtin_ctzl(tt)+1); x<<=k; tt>>=k; tmp%=mod_list[sz]; if(!table[tmp]){ table[tmp]=t; table[pre]->b|=x>>1; return {true,table[tmp]}; } } return {false,nullptr}; } std::pair<bool,node*> search(T key,size_t tmp){ int k=0; if(!table[tmp])return {false,nullptr}; if(table[tmp]->key==key)return {true,table[tmp]}; unsigned long t=table[tmp]->b; while(t){ tmp+=(k=__builtin_ctzl(t)+1); tmp%=mod_list[sz]; t>>=k; if(table[tmp]->key==key)return {true,table[tmp]}; } return {false,nullptr}; } E& operator[](T key){ size_t ha=op(key)%mod_list[sz]; auto res=search(key,ha); if(res.first)return res.second->val; else { while(1){ auto res=insert(table,new node(key,E()),ha); if(res.first)return res.second->val; _realloc(); ha=op(key)%mod_list[sz]; } } } }; template<typename T,typename E,typename F=std::hash<T>>typename hash_map<T,E,F>::node* hash_map<T,E,F>::node::alc=(node*)malloc(sizeof(node)); template<typename T,typename E,typename F=std::hash<T>>size_t hash_map<T,E,F>::node::cnt=0; template<typename T,typename E,typename F=std::hash<T>>size_t hash_map<T,E,F>::node::alc_sz=1;