Vowpal Wabbit
Classes | Public Member Functions | Public Attributes | List of all members
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 &)
 
default_value
 
v_array< hash_elemdat
 
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.

84  {
85  init_dat(min_size, def, eq, eq_dat);
86  }
void init_dat(size_t min_size, const V &def, bool(*eq)(void *, const K &, const K &), void *eq_dat=nullptr)
Definition: v_hashmap.h:39

◆ 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.

87 { init(min_size, def, eq); }
void init(size_t min_size, const V &def, bool(*eq)(const K &, const K &))
Definition: v_hashmap.h:54

◆ 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.

88 { init(1023, nullptr); }
void init(size_t min_size, const V &def, bool(*eq)(const K &, const K &))
Definition: v_hashmap.h:54

◆ ~v_hashmap()

template<class K, class V>
v_hashmap< K, V >::~v_hashmap ( )
inline

Definition at line 105 of file v_hashmap.h.

105 { delete_v(); }
void delete_v()
Definition: v_hashmap.h:103

Member Function Documentation

◆ base_size()

template<class K, class V>
size_t v_hashmap< K, V >::base_size ( )
inline

◆ 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().

108  {
109  if (num_occupants == 0)
110  return;
111  memset(dat.begin(), 0, base_size() * sizeof(hash_elem));
112  last_position = 0;
113  num_occupants = 0;
114  }
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
size_t base_size()
Definition: v_hashmap.h:35

◆ 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().

231  {
232  size_t sz = base_size();
233  size_t first_position = hash % sz;
234  last_position = first_position;
235  while (true)
236  { // if there's nothing there, obviously we don't contain it
237  if (!dat[last_position].occupied)
238  return false;
239 
240  // there's something there: maybe it's us
241  if ((dat[last_position].hash == hash) && is_equivalent(key, dat[last_position].key))
242  return true;
243 
244  // there's something there that's NOT us -- advance pointer
245  last_position++;
246  if (last_position >= sz)
247  last_position = 0;
248 
249  // check to make sure we haven't cycled around -- this is a bug!
250  if (last_position == first_position)
251  THROW("error: v_hashmap did not grow enough!");
252  }
253  }
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
bool is_equivalent(const K &key, const K &key2)
Definition: v_hashmap.h:193
size_t base_size()
Definition: v_hashmap.h:35
#define THROW(args)
Definition: vw_exception.h:181

◆ delete_v()

template<class K, class V>
void v_hashmap< K, V >::delete_v ( )
inline

◆ 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().

169  { // printf("doubling size!\n");
170  // remember the old occupants
172  tmp.resize(num_occupants + 10);
173  for (hash_elem* e = dat.begin(); e != dat.end_array; e++)
174  if (e->occupied)
175  tmp.push_back(*e);
176 
177  // double the size and clear
178  // std::cerr<<"doubling to "<<(base_size()*2) << " units == " << (base_size()*2*sizeof(hash_elem)) << " bytes / " <<
179  // ((size_t)-1)<<std::endl;
180  dat.resize(base_size() * 2);
181  memset(dat.begin(), 0, base_size() * sizeof(hash_elem));
182 
183  // re-insert occupants
184  for (auto& e : tmp)
185  {
186  get(e.key, e.hash);
187  // std::cerr << "reinserting " << e->key << " at " << last_position << std::endl;
188  put_after_get_nogrow(e.key, e.hash, e.val);
189  }
190  tmp.delete_v();
191  }
void resize(size_t length)
Definition: v_array.h:69
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
void push_back(const T &new_ele)
Definition: v_array.h:107
void put_after_get_nogrow(const K &key, uint64_t hash, const V &val)
Definition: v_hashmap.h:160
size_t base_size()
Definition: v_hashmap.h:35

◆ 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().

204  {
205  size_t sz = base_size();
206  size_t first_position = hash % sz;
207  last_position = first_position;
208  while (true)
209  { // if there's nothing there, obviously we don't contain it
210  if (!dat[last_position].occupied)
211  return default_value;
212 
213  // there's something there: maybe it's us
214  if ((dat[last_position].hash == hash) && is_equivalent(key, dat[last_position].key))
215  return dat[last_position].val;
216 
217  // there's something there that's NOT us -- advance pointer
218  // cerr << "+";
219  // num_linear_steps++;
220  last_position++;
221  if (last_position >= sz)
222  last_position = 0;
223 
224  // check to make sure we haven't cycled around -- this is a bug!
225  if (last_position == first_position)
226  THROW("error: v_hashmap did not grow enough!");
227  }
228  }
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
V default_value
Definition: v_hashmap.h:28
bool is_equivalent(const K &key, const K &key2)
Definition: v_hashmap.h:193
size_t base_size()
Definition: v_hashmap.h:35
#define THROW(args)
Definition: vw_exception.h:181

◆ 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().

55  {
56  if (min_size < 1023)
57  min_size = 1023;
58  dat.resize(min_size); // resize sets to 0 ==> occupied=false
59 
60  default_value = def;
61  equivalent = nullptr;
62  equivalent_no_data = eq;
63  eq_data = nullptr;
64 
65  last_position = 0;
66  num_occupants = 0;
67  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
V default_value
Definition: v_hashmap.h:28
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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.

70  {
71  if (min_size < 1023)
72  min_size = 1023;
73  dat.resize(min_size); // resize sets to 0 ==> occupied=false
74 
75  equivalent = nullptr;
76  equivalent_no_data = eq;
77  eq_data = nullptr;
78 
79  last_position = 0;
80  num_occupants = 0;
81  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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().

40  {
41  if (min_size < 1023)
42  min_size = 1023;
43  dat.resize(min_size, true); // resize sets to 0 ==> occupied=false
44 
45  default_value = def;
46  equivalent = eq;
47  equivalent_no_data = nullptr;
48  eq_data = eq_dat;
49 
50  last_position = 0;
51  num_occupants = 0;
52  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
V default_value
Definition: v_hashmap.h:28
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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().

194  {
195  if ((equivalent == nullptr) && (equivalent_no_data == nullptr))
196  return true;
197  else if (equivalent != nullptr)
198  return equivalent(eq_data, key, key2);
199  else
200  return equivalent_no_data(key, key2);
201  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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().

150  { // for (size_t lp=0; lp<base_size(); lp++) {
151  for (hash_elem* e = dat.begin(); e != dat.end_array; e++)
152  { // hash_elem* e = dat.begin()+lp;
153  if (e->occupied)
154  { // printf(" [lp=%d\tocc=%d\thash=%llu]\n", lp, e->occupied, e->hash);
155  func(e->key, e->val);
156  }
157  }
158  }
v_array< hash_elem > dat
Definition: v_hashmap.h:29

◆ 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().

132  {
133  hash_elem* e = dat.begin();
134  while (e != dat.end_array)
135  {
136  if (e->occupied)
137  return e;
138  e++;
139  }
140  return nullptr;
141  }
v_array< hash_elem > dat
Definition: v_hashmap.h:29

◆ 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().

144  {
145  hash_elem* e = (hash_elem*)el;
146  return &e->val;
147  }

◆ 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().

117  {
118  hash_elem* e = (hash_elem*)prev;
119  if (e == nullptr)
120  return nullptr;
121  e++;
122  while (e != dat.end_array)
123  {
124  if (e->occupied)
125  return e;
126  e++;
127  }
128  return nullptr;
129  }
v_array< hash_elem > dat
Definition: v_hashmap.h:29

◆ 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().

276  {
277  get(key, hash);
278  put_after_get(key, hash, val);
279  }
void put_after_get(const K &key, uint64_t hash, const V &val)
Definition: v_hashmap.h:259

◆ 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().

260  {
261  if (!dat[last_position].occupied)
262  {
263  num_occupants++;
264  if (num_occupants * 4 >= base_size()) // grow when we're a quarter full
265  {
266  double_size();
267  get(key, hash); // probably should change last_position-- this is the lazy man's way to do it
268  }
269  }
270 
271  // now actually insert it
272  put_after_get_nogrow(key, hash, val);
273  }
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29
size_t num_occupants
Definition: v_hashmap.h:31
void put_after_get_nogrow(const K &key, uint64_t hash, const V &val)
Definition: v_hashmap.h:160
size_t base_size()
Definition: v_hashmap.h:35
void double_size()
Definition: v_hashmap.h:168

◆ 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().

161  { // printf("++[lp=%d\tocc=%d\thash=%llu]\n", last_position, dat[last_position].occupied, hash);
162  dat[last_position].occupied = true;
163  dat[last_position].key = key;
164  dat[last_position].val = val;
165  dat[last_position].hash = hash;
166  }
size_t last_position
Definition: v_hashmap.h:30
v_array< hash_elem > dat
Definition: v_hashmap.h:29

◆ 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.

37 { default_value = def; }
V default_value
Definition: v_hashmap.h:28

◆ 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.

91  {
92  equivalent = eq;
93  eq_data = eq_dat;
94  equivalent_no_data = nullptr;
95  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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.

97  {
98  equivalent_no_data = eq;
99  eq_data = nullptr;
100  equivalent = nullptr;
101  }
bool(* equivalent)(void *, const K &, const K &)
Definition: v_hashmap.h:25
bool(* equivalent_no_data)(const K &, const K &)
Definition: v_hashmap.h:26
void * eq_data
Definition: v_hashmap.h:32

◆ 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().

281 { return num_occupants; }
size_t num_occupants
Definition: v_hashmap.h:31

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 &)

◆ equivalent_no_data

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

◆ last_position

template<class K, class V>
size_t v_hashmap< K, V >::last_position

◆ 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: