v_hashmap< K, V > Class Template Reference

#include <v_hashmap.h>

Classes
struct	hash_elem

Public Member Functions
size_t	base_size ()
void	set_default_value (const V &def)
void	init_dat (size_t min_size, const V &def, bool(*eq)(void *, const K &, const K &), void *eq_dat=nullptr)
void	init (size_t min_size, const V &def, bool(*eq)(const K &, const K &))
void	init (size_t min_size, bool(*eq)(const K &, const K &))
	v_hashmap (size_t min_size, const V &def, bool(*eq)(void *, const K &, const K &), void *eq_dat=nullptr)
	v_hashmap (size_t min_size, V &def, bool(*eq)(const K &, const K &))
	v_hashmap ()
void	set_equivalent (bool(*eq)(void *, const K &, const K &), void *eq_dat=nullptr)
void	set_equivalent (bool(*eq)(const K &, const K &))
void	delete_v ()
	~v_hashmap ()
void	clear ()
void *	iterator_next (void *prev)
void *	iterator ()
V *	iterator_get_value (void *el)
void	iter (void(*func)(K, V))
void	put_after_get_nogrow (const K &key, uint64_t hash, const V &val)
void	double_size ()
bool	is_equivalent (const K &key, const K &key2)
V &	get (const K &key, uint64_t hash)
bool	contains (const K &key, size_t hash)
void	put_after_get (const K &key, uint64_t hash, const V &val)
void	put (const K &key, uint64_t hash, const V &val)
size_t	size ()

Public Attributes
bool(*	equivalent )(void *, const K &, const K &)
bool(*	equivalent_no_data )(const K &, const K &)
V	default_value
v_array< hash_elem >	dat
size_t	last_position
size_t	num_occupants
void *	eq_data

Detailed Description

template<class K, class V>
class v_hashmap< K, V >

Definition at line 14 of file v_hashmap.h.

Constructor & Destructor Documentation

v_hashmap() [1/3]

template<class K, class V>

v_hashmap< K, V >::v_hashmap ( size_t  min_size, const V &  def, bool(*)(void *, const K &, const K &)  eq, void *  eq_dat = nullptr  )

inline

Definition at line 83 of file v_hashmap.h.

  {
    init_dat(min_size, def, eq, eq_dat);
  }

v_hashmap() [2/3]

template<class K, class V>

v_hashmap< K, V >::v_hashmap ( size_t  min_size, V &  def, bool(*)(const K &, const K &)  eq  )

inline

Definition at line 87 of file v_hashmap.h.

{ init(min_size, def, eq); }

v_hashmap() [3/3]

template<class K, class V>

v_hashmap< K, V >::v_hashmap ( )

inline

Definition at line 88 of file v_hashmap.h.

{ init(1023, nullptr); }

~v_hashmap()

template<class K, class V>

v_hashmap< K, V >::~v_hashmap ( )

inline

Definition at line 105 of file v_hashmap.h.

{ delete_v(); }

Member Function Documentation

base_size()

template<class K, class V>

size_t v_hashmap< K, V >::base_size ( )

inline

Definition at line 35 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::clear(), v_hashmap< size_t, features >::contains(), v_hashmap< size_t, features >::double_size(), v_hashmap< size_t, features >::get(), and v_hashmap< size_t, features >::put_after_get().

{ return dat.end_array - dat.begin(); }

clear()

template<class K, class V>

void v_hashmap< K, V >::clear ( )

inline

Definition at line 107 of file v_hashmap.h.

Referenced by LabelDict::free_label_features().

  {
    if (num_occupants == 0)
      return;
    memset(dat.begin(), 0, base_size() * sizeof(hash_elem));
    last_position = 0;
    num_occupants = 0;
  }

contains()

template<class K, class V>

bool v_hashmap< K, V >::contains ( const K &  key, size_t  hash  )

inline

Definition at line 230 of file v_hashmap.h.

Referenced by LabelDict::set_label_features().

  {
    size_t sz = base_size();
    size_t first_position = hash % sz;
    last_position = first_position;
    while (true)
    {  // if there's nothing there, obviously we don't contain it
      if (!dat[last_position].occupied)
        return false;

      // there's something there: maybe it's us
      if ((dat[last_position].hash == hash) && is_equivalent(key, dat[last_position].key))
        return true;

      // there's something there that's NOT us -- advance pointer
      last_position++;
      if (last_position >= sz)
        last_position = 0;

      // check to make sure we haven't cycled around -- this is a bug!
      if (last_position == first_position)
        THROW("error: v_hashmap did not grow enough!");
    }
  }

delete_v()

template<class K, class V>

void v_hashmap< K, V >::delete_v ( )

inline

Definition at line 103 of file v_hashmap.h.

Referenced by LabelDict::free_label_features(), namedlabels::namedlabels(), namedlabels::~namedlabels(), and v_hashmap< size_t, features >::~v_hashmap().

{ dat.delete_v(); }

double_size()

template<class K, class V>

void v_hashmap< K, V >::double_size ( )

inline

Definition at line 168 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::put_after_get().

  {  //    printf("doubling size!\n");
    // remember the old occupants
    v_array<hash_elem> tmp = v_array<hash_elem>();
    tmp.resize(num_occupants + 10);
    for (hash_elem* e = dat.begin(); e != dat.end_array; e++)
      if (e->occupied)
        tmp.push_back(*e);

    // double the size and clear
    // std::cerr<<"doubling to "<<(base_size()*2) << " units == " << (base_size()*2*sizeof(hash_elem)) << " bytes / " <<
    // ((size_t)-1)<<std::endl;
    dat.resize(base_size() * 2);
    memset(dat.begin(), 0, base_size() * sizeof(hash_elem));

    // re-insert occupants
    for (auto& e : tmp)
    {
      get(e.key, e.hash);
      //      std::cerr << "reinserting " << e->key << " at " << last_position << std::endl;
      put_after_get_nogrow(e.key, e.hash, e.val);
    }
    tmp.delete_v();
  }

get()

template<class K, class V>

V& v_hashmap< K, V >::get ( const K &  key, uint64_t  hash  )

inline

Definition at line 203 of file v_hashmap.h.

Referenced by LabelDict::add_example_namespace_from_memory(), LabelDict::del_example_namespace_from_memory(), namedlabels::get(), namedlabels::namedlabels(), and parse_dictionary_argument().

  {
    size_t sz = base_size();
    size_t first_position = hash % sz;
    last_position = first_position;
    while (true)
    {  // if there's nothing there, obviously we don't contain it
      if (!dat[last_position].occupied)
        return default_value;

      // there's something there: maybe it's us
      if ((dat[last_position].hash == hash) && is_equivalent(key, dat[last_position].key))
        return dat[last_position].val;

      // there's something there that's NOT us -- advance pointer
      // cerr << "+";
      // num_linear_steps++;
      last_position++;
      if (last_position >= sz)
        last_position = 0;

      // check to make sure we haven't cycled around -- this is a bug!
      if (last_position == first_position)
        THROW("error: v_hashmap did not grow enough!");
    }
  }

init() [1/2]

template<class K, class V>

void v_hashmap< K, V >::init ( size_t  min_size, const V &  def, bool(*)(const K &, const K &)  eq  )

inline

Definition at line 54 of file v_hashmap.h.

Referenced by namedlabels::namedlabels(), parse_dictionary_argument(), and v_hashmap< size_t, features >::v_hashmap().

  {
    if (min_size < 1023)
      min_size = 1023;
    dat.resize(min_size);  // resize sets to 0 ==> occupied=false

    default_value = def;
    equivalent = nullptr;
    equivalent_no_data = eq;
    eq_data = nullptr;

    last_position = 0;
    num_occupants = 0;
  }

init() [2/2]

template<class K, class V>

void v_hashmap< K, V >::init ( size_t  min_size, bool(*)(const K &, const K &)  eq  )

inline

Definition at line 69 of file v_hashmap.h.

  {
    if (min_size < 1023)
      min_size = 1023;
    dat.resize(min_size);  // resize sets to 0 ==> occupied=false

    equivalent = nullptr;
    equivalent_no_data = eq;
    eq_data = nullptr;

    last_position = 0;
    num_occupants = 0;
  }

init_dat()

template<class K, class V>

void v_hashmap< K, V >::init_dat ( size_t  min_size, const V &  def, bool(*)(void *, const K &, const K &)  eq, void *  eq_dat = nullptr  )

inline

Definition at line 39 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::v_hashmap().

  {
    if (min_size < 1023)
      min_size = 1023;
    dat.resize(min_size, true);  // resize sets to 0 ==> occupied=false

    default_value = def;
    equivalent = eq;
    equivalent_no_data = nullptr;
    eq_data = eq_dat;

    last_position = 0;
    num_occupants = 0;
  }

is_equivalent()

template<class K, class V>

bool v_hashmap< K, V >::is_equivalent ( const K &  key, const K &  key2  )

inline

Definition at line 193 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::contains(), and v_hashmap< size_t, features >::get().

  {
    if ((equivalent == nullptr) && (equivalent_no_data == nullptr))
      return true;
    else if (equivalent != nullptr)
      return equivalent(eq_data, key, key2);
    else
      return equivalent_no_data(key, key2);
  }

iter()

template<class K, class V>

void v_hashmap< K, V >::iter ( void(*)(K, V)  func )

inline

Definition at line 149 of file v_hashmap.h.

Referenced by namedlabels::~namedlabels().

  {  // for (size_t lp=0; lp<base_size(); lp++) {
    for (hash_elem* e = dat.begin(); e != dat.end_array; e++)
    {  // hash_elem* e = dat.begin()+lp;
      if (e->occupied)
      {  // printf("  [lp=%d\tocc=%d\thash=%llu]\n", lp, e->occupied, e->hash);
        func(e->key, e->val);
      }
    }
  }

iterator()

template<class K, class V>

void* v_hashmap< K, V >::iterator ( )

inline

Definition at line 131 of file v_hashmap.h.

Referenced by LabelDict::free_label_features().

  {
    hash_elem* e = dat.begin();
    while (e != dat.end_array)
    {
      if (e->occupied)
        return e;
      e++;
    }
    return nullptr;
  }

iterator_get_value()

template<class K, class V>

V* v_hashmap< K, V >::iterator_get_value ( void *  el )

inline

Definition at line 143 of file v_hashmap.h.

Referenced by LabelDict::free_label_features().

  {
    hash_elem* e = (hash_elem*)el;
    return &e->val;
  }

iterator_next()

template<class K, class V>

void* v_hashmap< K, V >::iterator_next ( void *  prev )

inline

Definition at line 116 of file v_hashmap.h.

Referenced by LabelDict::free_label_features().

  {
    hash_elem* e = (hash_elem*)prev;
    if (e == nullptr)
      return nullptr;
    e++;
    while (e != dat.end_array)
    {
      if (e->occupied)
        return e;
      e++;
    }
    return nullptr;
  }

put()

template<class K, class V>

void v_hashmap< K, V >::put ( const K &  key, uint64_t  hash, const V &  val  )

inline

Definition at line 275 of file v_hashmap.h.

Referenced by namedlabels::namedlabels(), and parse_dictionary_argument().

  {
    get(key, hash);
    put_after_get(key, hash, val);
  }

put_after_get()

template<class K, class V>

void v_hashmap< K, V >::put_after_get ( const K &  key, uint64_t  hash, const V &  val  )

inline

Definition at line 259 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::put(), and LabelDict::set_label_features().

  {
    if (!dat[last_position].occupied)
    {
      num_occupants++;
      if (num_occupants * 4 >= base_size())  // grow when we're a quarter full
      {
        double_size();
        get(key, hash);  // probably should change last_position-- this is the lazy man's way to do it
      }
    }

    // now actually insert it
    put_after_get_nogrow(key, hash, val);
  }

put_after_get_nogrow()

template<class K, class V>

void v_hashmap< K, V >::put_after_get_nogrow ( const K &  key, uint64_t  hash, const V &  val  )

inline

Definition at line 160 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::double_size(), and v_hashmap< size_t, features >::put_after_get().

  {  // printf("++[lp=%d\tocc=%d\thash=%llu]\n", last_position, dat[last_position].occupied, hash);
    dat[last_position].occupied = true;
    dat[last_position].key = key;
    dat[last_position].val = val;
    dat[last_position].hash = hash;
  }

set_default_value()

template<class K, class V>

void v_hashmap< K, V >::set_default_value ( const V &  def )

inline

Definition at line 37 of file v_hashmap.h.

{ default_value = def; }

set_equivalent() [1/2]

template<class K, class V>

void v_hashmap< K, V >::set_equivalent ( bool(*)(void *, const K &, const K &)  eq, void *  eq_dat = nullptr  )

inline

Definition at line 90 of file v_hashmap.h.

  {
    equivalent = eq;
    eq_data = eq_dat;
    equivalent_no_data = nullptr;
  }

set_equivalent() [2/2]

template<class K, class V>

void v_hashmap< K, V >::set_equivalent ( bool(*)(const K &, const K &)  eq )

inline

Definition at line 96 of file v_hashmap.h.

  {
    equivalent_no_data = eq;
    eq_data = nullptr;
    equivalent = nullptr;
  }

size()

template<class K, class V>

size_t v_hashmap< K, V >::size ( )

inline

Definition at line 281 of file v_hashmap.h.

Referenced by parse_dictionary_argument().

{ return num_occupants; }

Member Data Documentation

dat

template<class K, class V>

v_array<hash_elem> v_hashmap< K, V >::dat

Definition at line 29 of file v_hashmap.h.

default_value

template<class K, class V>

V v_hashmap< K, V >::default_value

Definition at line 28 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::get().

eq_data

template<class K, class V>

void* v_hashmap< K, V >::eq_data

Definition at line 32 of file v_hashmap.h.

equivalent

template<class K, class V>

bool(* v_hashmap< K, V >::equivalent) (void *, const K &, const K &)

Definition at line 25 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::init(), v_hashmap< size_t, features >::init_dat(), v_hashmap< size_t, features >::is_equivalent(), and v_hashmap< size_t, features >::set_equivalent().

equivalent_no_data

template<class K, class V>

bool(* v_hashmap< K, V >::equivalent_no_data) (const K &, const K &)

Definition at line 26 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::init(), v_hashmap< size_t, features >::init_dat(), v_hashmap< size_t, features >::is_equivalent(), and v_hashmap< size_t, features >::set_equivalent().

last_position

template<class K, class V>

size_t v_hashmap< K, V >::last_position

Definition at line 30 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::get(), and v_hashmap< size_t, features >::put_after_get_nogrow().

num_occupants

template<class K, class V>

size_t v_hashmap< K, V >::num_occupants

Definition at line 31 of file v_hashmap.h.

Referenced by v_hashmap< size_t, features >::size().

---

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

• /mnt/c/w/linux/vowpal_wabbit/vowpalwabbit/v_hashmap.h