hash_vec.hpp

Go to the documentation of this file.

/*
 * Copyright (C) Sergey P. Derevyago, 2008-2009.
 *
 * Permission to copy, use, modify, sell and distribute this software is granted
 * provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied warranty, and
 * with no claim as to its suitability for any purpose.
 *
 */

#ifndef __DERS__HASH_VEC_HPP__
#define __DERS__HASH_VEC_HPP__

#include <ders/config.hpp>
#include <algorithm>
#include <ders/text.hpp>

namespace ders {  // ::ders

using namespace std;

namespace detail {  // ::ders::detail

template<class Key, class Val>
struct hash_vec_nodes {
       struct node {
              Key key;
              Val val;
              int next;

              node(const Key& k, const Val& v) : key(k), val(v), next(-1) {}
       };

       int resd;
       int used;
       node* nodes;

       hash_vec_nodes(int rsrv);
       ~hash_vec_nodes();

       void create_at(int pos, const Key& k, const Val& v);
       void destroy_at(int pos);
       void move_to(int to, int from);
};

template<class Key, class Val>
hash_vec_nodes<Key, Val>::hash_vec_nodes(int rsrv) :
  resd(rsrv), used(0), nodes(0)
{
 assert(resd>0);
 nodes=static_cast<node*>(operator new(sizeof(node)*resd));
}

template<class Key, class Val>
hash_vec_nodes<Key, Val>::~hash_vec_nodes()
{
 for (int i=0; i<used; i++) destroy_at(i);
 operator delete(nodes);
}

template<class Key, class Val>
inline void hash_vec_nodes<Key, Val>::create_at(int pos, const Key& k, const
  Val& v)
{
 new(nodes+pos) node(k, v);
}

template<class Key, class Val>
inline void hash_vec_nodes<Key, Val>::destroy_at(int pos)
{
 nodes[pos].~node();
}

template<class Key, class Val>
inline void hash_vec_nodes<Key, Val>::move_to(int to, int from)
{
 memcpy(nodes+to, nodes+from, sizeof(*nodes));
}

size_t calc_hash(const void* ptr, int n);

}  // namespace ::ders::detail

template<class Key>
struct key_hash {
};

#define TRIVIAL_KEY_HASH(type)                       \
template<>                                           \
struct key_hash<type> {                              \
       size_t operator()(type k) const { return k; } \
}

TRIVIAL_KEY_HASH(char);
TRIVIAL_KEY_HASH(unsigned char);
TRIVIAL_KEY_HASH(signed char);
TRIVIAL_KEY_HASH(short);
TRIVIAL_KEY_HASH(unsigned short);
TRIVIAL_KEY_HASH(int);
TRIVIAL_KEY_HASH(unsigned int);
TRIVIAL_KEY_HASH(long);
TRIVIAL_KEY_HASH(unsigned long);

#undef TRIVIAL_KEY_HASH

template<class T>
struct key_hash<T*> {
       size_t operator()(T* k) const { return reinterpret_cast<size_t>(k); }
};

template<>
struct key_hash<sh_text> {
       size_t operator()(const sh_text& t) const
       { return detail::calc_hash(t->begin(), t->size()); }
};

template<class Key>
struct key_eql {
       bool operator()(const Key& key1, const Key& key2) const
       { return (key1==key2) ? true : false; }
};

template<class Key, class Val, class KeyHash=key_hash<Key>, class KeyEql=
  key_eql<Key> >
class hash_vec {
      typedef detail::hash_vec_nodes<Key, Val> nodes;

      KeyHash khash;
      KeyEql keql;
      int* hndx;
      nodes nds;

      int* root(const Key& k) const  { return hndx+khash(k)%nds.resd; }
      int* find(int* root, const Key& k) const;

      hash_vec(const hash_vec&);
      hash_vec& operator=(const hash_vec&);

 public:
      hash_vec(int rsrv, const KeyHash& kh=KeyHash(), const KeyEql& ke=
        KeyEql());
      ~hash_vec() { operator delete(hndx); }

      int size() const { return nds.used; }
      int capacity() const { return nds.resd; }
      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 { return *find(root(k), k); }
      void erase(int pos);
};

template<class Key, class Val, class KeyHash, class KeyEql>
int* hash_vec<Key, Val, KeyHash, KeyEql>::find(int* root, const Key& k) const
{
 for (int* ptr=root; ; ptr=&nds.nodes[*ptr].next)
     if (*ptr==-1 || keql(nds.nodes[*ptr].key, k)) return ptr;
}

template<class Key, class Val, class KeyHash, class KeyEql>
hash_vec<Key, Val, KeyHash, KeyEql>::hash_vec(int rsrv, const KeyHash& kh, const
  KeyEql& ke) : khash(kh), keql(ke), hndx(0), nds(rsrv)
{
 hndx=static_cast<int*>(operator new(sizeof(int)*nds.resd));
 fill_n(hndx, nds.resd, -1);
}

template<class Key, class Val, class KeyHash, class KeyEql>
void hash_vec<Key, Val, KeyHash, KeyEql>::reserve(int n)
{
 assert(n>0);
 if (nds.resd>=n) return;

 int* hndx2=static_cast<int*>(operator new(sizeof(int)*n));

 typedef typename nodes::node node;
 node* nodes2;
 try { nodes2=static_cast<node*>(operator new(sizeof(node)*n)); }
 catch (...) {
       operator delete(hndx);
       throw;
 }

 fill_n(hndx2, n, -1);

 memcpy(nodes2, nds.nodes, sizeof(*nodes2)*nds.used);
 for (int i=0; i<nds.used; i++) nodes2[i].next=-1;

 for (int i=0; i<nds.used; i++) {
     int* pnode=hndx2+khash(nodes2[i].key)%n;
     nodes2[i].next=*pnode;
     *pnode=i;
 }

 operator delete(hndx);
 hndx=hndx2;

 operator delete(nds.nodes);
 nds.nodes=nodes2;
 nds.resd=n;
}

template<class Key, class Val, class KeyHash, class KeyEql>
inline const Key& hash_vec<Key, Val, KeyHash, KeyEql>::key(int pos) const
{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].key;
}

template<class Key, class Val, class KeyHash, class KeyEql>
inline Val& hash_vec<Key, Val, KeyHash, KeyEql>::val(int pos)
{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].val;
}

template<class Key, class Val, class KeyHash, class KeyEql>
inline const Val& hash_vec<Key, Val, KeyHash, KeyEql>::val(int pos) const
{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].val;
}

template<class Key, class Val, class KeyHash, class KeyEql>
int hash_vec<Key, Val, KeyHash, KeyEql>::insert(const Key& k, const Val& v)
{
 assert(nds.used<=nds.resd);
 if (nds.used==nds.resd) reserve(nds.resd*2+1);

 int* pnode=find(root(k), k);
 if (*pnode!=-1) return -1;

 nds.create_at(nds.used, k, v);
 return *pnode=nds.used++;
}

template<class Key, class Val, class KeyHash, class KeyEql>
void hash_vec<Key, Val, KeyHash, KeyEql>::erase(int pos)
{
 assert(pos>=0 && pos<size());

 const Key& k=nds.nodes[pos].key;
 int* pnode=find(root(k), k);
 assert(*pnode==pos);

 int tail=nds.nodes[pos].next;

 nds.destroy_at(pos);
 *pnode=-1;

 if (tail!=-1) {
    int* ptr=root(nds.nodes[tail].key);
    while (*ptr!=-1) ptr=&nds.nodes[*ptr].next;

    *ptr=tail;
 }

 int last=nds.used-1;
 if (pos!=last) {
    const Key& lkey=nds.nodes[last].key;
    int* nlast=find(root(lkey), lkey);
    assert(*nlast==last);

    nds.move_to(pos, last);
    *nlast=pos;
 }

 nds.used--;
}

}  // namespace ::ders

#endif  // __DERS__HASH_VEC_HPP__

---