/usr/include/freefem++/HashTable.hpp is in libfreefem++-dev 3.47+dfsg1-2build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | template<typename T,int N>
struct SortArray {
};
template<typename T>
struct SortArray<T,1> {
T v[1];
SortArray(T *a)
{
v[0]=a[0];
}
SortArray(const T& a0)
{
v[0]=a0;
}
SortArray(){}
bool operator == (const SortArray<T,1> & t) const
{ return v[0] == t.v[0] ;}
bool operator<(const SortArray<T,1> & t) const
{ return v[0] < t.v[0] ;}
size_t hash() const {return (size_t) v[0];}
};
template<typename T>
struct SortArray<T,2> {
// using std::swap;
T v[2];
SortArray(T *a)
{
v[0]=a[0];
v[1]=a[1];
if(v[0]>v[1]) swap(v[0],v[1]);
}
SortArray(const T& a0,const T &a1)
{
v[0]=a0;
v[1]=a1;
if(v[0]>v[1]) swap(v[0],v[1]);
}
SortArray(){}
bool operator == (const SortArray<T,2> & t) const
{ return v[0] == t.v[0] && v[1] == t.v[1] ;}
bool operator<(const SortArray<T,2> & t) const
{ return v[0] != t.v[0] ? v[0] < t.v[0] : v[1] < t.v[1] ;}
size_t hash() const {return (size_t) v[0];}
};
template<typename T>
struct SortArray<T,3> {
T v[3];
SortArray(T *a)
{
v[0]=a[0];
v[1]=a[1];
v[2]=a[2];
if(v[0]>v[1]) swap(v[0],v[1]);
if(v[1]>v[2]) {
swap(v[1],v[2]);
if(v[0]>v[1]) swap(v[0],v[1]);
ASSERTION(v[0] <= v[1] && v[1] <= v[2] );
}
}
SortArray(){}
bool operator == (const SortArray<T,3> & t) const
{ return v[0] == t.v[0] && v[1] == t.v[1] && v[2] == t.v[2] ;}
bool operator<(const SortArray<T,3> & t) const
{ return v[0] != t.v[0] ? v[0] < t.v[0] :
( v[1] != t.v[1] ? v[1] < t.v[1] : v[2] < t.v[2] );}
size_t hash() const {return (size_t) v[0];}
};
template<typename T,int N>
ostream & operator<<(ostream & f,const SortArray<T,N> & item)
{
for (int i=0;i<N;++i) f << " " << item.v[i];
return f;
}
template<class K,class V>
class HashTable {
public:
struct nKV { size_t next; K k; V v;
nKV(){} };
typedef nKV *iterator;
size_t n,nx,nk,ncol,nfind;
size_t * head;
nKV * t;
static const size_t endhash= (size_t) -1;
HashTable(size_t nnx,size_t nnk)
: n(0),nx(nnx),nk(nnk),ncol(0),nfind(0),
head(new size_t[nk]),t(new nKV[nx])
{ reset();}
void reset()
{
n=0;
ncol=0;
for (size_t j=0;j<nk;++j)
head[j]=endhash;
}
nKV * find(const K & key)
{
nfind++;
for (size_t k=head[key.hash() %nk];k!=endhash;k=t[k].next)
{
++ncol;
if(key == t[k].k) return t+k;
}
return 0;
}
// add FH 21 avril 2009
size_t operator()(nKV * p) { return p ? p-t : n;}
iterator end(){ return t+n;}
iterator begin(){ return t;}
nKV *add(const K & key,const V & v)
{
size_t k =key.hash()%nk;
assert(n<nx);
t[n].v = v;
t[n].k = key;
t[n].next=head[k];
head[k]=n;
return t+ n++;
}
V & operator[](const K & key)
{
nKV *p = find(key);
if(p) return p->v;
else return t[add(key,V())].v;
}
~HashTable()
{
if(nfind && verbosity>4)
cout << " ~HashTable: Cas moyen : " << (double) ncol/ nfind << endl;
delete [] head;
delete [] t;
}
// pas de copie ....
private:
HashTable(const HashTable&);
void operator=(const HashTable&);
};
|