ders::hash_vec< Key, Val, KeyHash, KeyEql > Class Template Reference

Associative hash container. More...

#include <hash_vec.hpp>

List of all members.

Public Member Functions

 hash_vec (int rsrv, const KeyHash &kh=KeyHash(), const KeyEql &ke=KeyEql())
 ~hash_vec ()
int size () const
int capacity () const
void reserve (int n)
const Key & key (int pos) const
Val & val (int pos)
const Val & val (int pos) const
int insert (const Key &k, const Val &v)
int find (const Key &k) const
void erase (int pos)


Detailed Description

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
class ders::hash_vec< Key, Val, KeyHash, KeyEql >

Associative hash container.

Definition at line 140 of file hash_vec.hpp.


Constructor & Destructor Documentation

template<class Key, class Val, class KeyHash, class KeyEql>
ders::hash_vec< Key, Val, KeyHash, KeyEql >::hash_vec ( int  rsrv,
const KeyHash &  kh = KeyHash(),
const KeyEql &  ke = KeyEql() 
) [inline]

Definition at line 180 of file hash_vec.hpp.

00181               : khash(kh), keql(ke), hndx(0), nds(rsrv)
00182 {
00183  hndx=static_cast<int*>(operator new(sizeof(int)*nds.resd));
00184  fill_n(hndx, nds.resd, -1);
00185 }

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
ders::hash_vec< Key, Val, KeyHash, KeyEql >::~hash_vec (  )  [inline]

Definition at line 157 of file hash_vec.hpp.

00157 { operator delete(hndx); }


Member Function Documentation

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
int ders::hash_vec< Key, Val, KeyHash, KeyEql >::size (  )  const [inline]

Definition at line 159 of file hash_vec.hpp.

00159 { return nds.used; }

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
int ders::hash_vec< Key, Val, KeyHash, KeyEql >::capacity (  )  const [inline]

Definition at line 160 of file hash_vec.hpp.

00160 { return nds.resd; }

template<class Key, class Val, class KeyHash, class KeyEql>
void ders::hash_vec< Key, Val, KeyHash, KeyEql >::reserve ( int  n  )  [inline]

Definition at line 188 of file hash_vec.hpp.

00189 {
00190  assert(n>0);
00191  if (nds.resd>=n) return;
00192 
00193  int* hndx2=static_cast<int*>(operator new(sizeof(int)*n));
00194 
00195  typedef typename nodes::node node;
00196  node* nodes2;
00197  try { nodes2=static_cast<node*>(operator new(sizeof(node)*n)); }
00198  catch (...) {
00199        operator delete(hndx);
00200        throw;
00201  }
00202 
00203  fill_n(hndx2, n, -1);
00204 
00205  memcpy(nodes2, nds.nodes, sizeof(*nodes2)*nds.used);
00206  for (int i=0; i<nds.used; i++) nodes2[i].next=-1;
00207 
00208  for (int i=0; i<nds.used; i++) {
00209      int* pnode=hndx2+khash(nodes2[i].key)%n;
00210      nodes2[i].next=*pnode;
00211      *pnode=i;
00212  }
00213 
00214  operator delete(hndx);
00215  hndx=hndx2;
00216 
00217  operator delete(nds.nodes);
00218  nds.nodes=nodes2;
00219  nds.resd=n;
00220 }

template<class Key, class Val, class KeyHash, class KeyEql>
const Key & ders::hash_vec< Key, Val, KeyHash, KeyEql >::key ( int  pos  )  const [inline]

Definition at line 223 of file hash_vec.hpp.

00224 {
00225  assert(pos>=0 && pos<size());
00226  return nds.nodes[pos].key;
00227 }

template<class Key, class Val, class KeyHash, class KeyEql>
Val & ders::hash_vec< Key, Val, KeyHash, KeyEql >::val ( int  pos  )  [inline]

Definition at line 230 of file hash_vec.hpp.

00231 {
00232  assert(pos>=0 && pos<size());
00233  return nds.nodes[pos].val;
00234 }

template<class Key, class Val, class KeyHash, class KeyEql>
const Val & ders::hash_vec< Key, Val, KeyHash, KeyEql >::val ( int  pos  )  const [inline]

Definition at line 237 of file hash_vec.hpp.

00238 {
00239  assert(pos>=0 && pos<size());
00240  return nds.nodes[pos].val;
00241 }

template<class Key, class Val, class KeyHash, class KeyEql>
int ders::hash_vec< Key, Val, KeyHash, KeyEql >::insert ( const Key &  k,
const Val &  v 
) [inline]

Definition at line 244 of file hash_vec.hpp.

00245 {
00246  assert(nds.used<=nds.resd);
00247  if (nds.used==nds.resd) reserve(nds.resd*2+1);
00248 
00249  int* pnode=find(root(k), k);
00250  if (*pnode!=-1) return -1;
00251 
00252  nds.create_at(nds.used, k, v);
00253  return *pnode=nds.used++;
00254 }

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
int ders::hash_vec< Key, Val, KeyHash, KeyEql >::find ( const Key &  k  )  const [inline]

Definition at line 168 of file hash_vec.hpp.

00168 { return *find(root(k), k); }

template<class Key, class Val, class KeyHash, class KeyEql>
void ders::hash_vec< Key, Val, KeyHash, KeyEql >::erase ( int  pos  )  [inline]

Definition at line 257 of file hash_vec.hpp.

00258 {
00259  assert(pos>=0 && pos<size());
00260 
00261  const Key& k=nds.nodes[pos].key;
00262  int* pnode=find(root(k), k);
00263  assert(*pnode==pos);
00264 
00265  int tail=nds.nodes[pos].next;
00266 
00267  nds.destroy_at(pos);
00268  *pnode=-1;
00269 
00270  if (tail!=-1) {
00271     int* ptr=root(nds.nodes[tail].key);
00272     while (*ptr!=-1) ptr=&nds.nodes[*ptr].next;
00273 
00274     *ptr=tail;
00275  }
00276 
00277  int last=nds.used-1;
00278  if (pos!=last) {
00279     const Key& lkey=nds.nodes[last].key;
00280     int* nlast=find(root(lkey), lkey);
00281     assert(*nlast==last);
00282 
00283     nds.move_to(pos, last);
00284     *nlast=pos;
00285  }
00286 
00287  nds.used--;
00288 }


The documentation for this class was generated from the following file:

Generated on Tue Dec 8 11:35:33 2009 for derslib by  doxygen 1.5.5