My Project
Data Structures | Public Member Functions | Private Types | Private Member Functions | Private Attributes
vspace::VMap< Spec > Class Template Reference

#include <vspace.h>

Data Structures

struct  Node
 

Public Member Functions

 VMap (size_t size=1024)
 
 ~VMap ()
 
bool add (VRef< K > key, VRef< V > value, VRef< K > &oldkey, VRef< V > &oldvalue, bool replace=true)
 
bool add (VRef< K > key, VRef< V > value, bool replace=true)
 
bool remove (VRef< K > key, VRef< K > &oldkey, VRef< V > &oldvalue)
 
bool remove (VRef< K > key)
 
bool find (VRef< K > key, VRef< V > &value)
 
VRef< Vfind (VRef< K > key)
 

Private Types

typedef Spec::Key K
 
typedef Spec::Value V
 

Private Member Functions

void _lock_bucket (size_t b)
 
void _unlock_bucket (size_t b)
 

Private Attributes

VRef< VRef< Node > > _buckets
 
VRef< internals::FastLock_locks
 
size_t _nbuckets
 

Detailed Description

template<typename Spec>
class vspace::VMap< Spec >

Definition at line 2115 of file vspace.h.


Data Structure Documentation

◆ vspace::VMap::Node

struct vspace::VMap::Node

template<typename Spec>
struct vspace::VMap< Spec >::Node

Definition at line 2119 of file vspace.h.

Data Fields
size_t hash
VRef< K > key
VRef< Node > next
VRef< V > value

Member Typedef Documentation

◆ K

template<typename Spec >
typedef Spec::Key vspace::VMap< Spec >::K
private

Definition at line 2117 of file vspace.h.

◆ V

template<typename Spec >
typedef Spec::Value vspace::VMap< Spec >::V
private

Definition at line 2118 of file vspace.h.

Constructor & Destructor Documentation

◆ VMap()

template<typename Spec >
vspace::VMap< Spec >::VMap ( size_t  size = 1024)

Definition at line 2163 of file vspace.h.

2163  {
2164  using namespace internals;
2165  _nbuckets = 8;
2166  while (_nbuckets < size)
2167  _nbuckets *= 2;
2168  _buckets = vnew_array<VRef<Node> >(_nbuckets);
2169  _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
2170  for (size_t i = 0; i < _nbuckets; i++)
2171  _locks[i]
2172  = FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
2173 }
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int i
Definition: cfEzgcd.cc:132
VRef< VRef< Node > > _buckets
Definition: vspace.h:2125
VRef< internals::FastLock > _locks
Definition: vspace.h:2126
size_t _nbuckets
Definition: vspace.h:2127
static const size_t METABLOCK_SIZE
Definition: vspace.h:1420
internals::Mutex FastLock
Definition: vspace.h:2340

◆ ~VMap()

template<typename Spec >
vspace::VMap< Spec >::~VMap

Definition at line 2176 of file vspace.h.

2176  {
2177  for (size_t b = 0; b < _nbuckets; b++) {
2178  _lock_bucket(b);
2179  VRef<Node> node = _buckets[b];
2180  while (node) {
2181  Node *node_ptr = node.as_ptr();
2182  VRef<Node> next = node_ptr->next;
2183  Spec::free_key(node_ptr->key);
2184  Spec::free_value(node_ptr->value);
2185  node.free();
2186  node = next;
2187  }
2188  _unlock_bucket(b);
2189  }
2190  _buckets.free();
2191  _locks.free();
2192 }
CanonicalForm b
Definition: cfModGcd.cc:4103
void _lock_bucket(size_t b)
Definition: vspace.h:2129
void _unlock_bucket(size_t b)
Definition: vspace.h:2132
ListNode * next
Definition: janet.h:31

Member Function Documentation

◆ _lock_bucket()

template<typename Spec >
void vspace::VMap< Spec >::_lock_bucket ( size_t  b)
inlineprivate

Definition at line 2129 of file vspace.h.

2129  {
2130  _locks[b].lock();
2131  }

◆ _unlock_bucket()

template<typename Spec >
void vspace::VMap< Spec >::_unlock_bucket ( size_t  b)
inlineprivate

Definition at line 2132 of file vspace.h.

2132  {
2133  _locks[b].unlock();
2134  }

◆ add() [1/2]

template<typename Spec >
bool vspace::VMap< Spec >::add ( VRef< K key,
VRef< V value,
bool  replace = true 
)
inline

Definition at line 2141 of file vspace.h.

2141  {
2142  VRef<K> oldkey;
2143  VRef<V> oldvalue;
2144  return add(key, value, oldkey, oldvalue, replace);
2145  }
bool add(VRef< K > key, VRef< V > value, VRef< K > &oldkey, VRef< V > &oldvalue, bool replace=true)
Definition: vspace.h:2195

◆ add() [2/2]

template<typename Spec >
bool vspace::VMap< Spec >::add ( VRef< K key,
VRef< V value,
VRef< K > &  oldkey,
VRef< V > &  oldvalue,
bool  replace = true 
)

Definition at line 2195 of file vspace.h.

2196  {
2197  size_t hash = Spec::hash(key.as_ptr());
2198  size_t b = hash & (_nbuckets - 1);
2199  _lock_bucket(b);
2200  VRef<Node> node = _buckets[b];
2201  VRef<Node> last = vnull<Node>();
2202  while (!node.is_null()) {
2203  Node *node_ptr = node.as_ptr();
2204  if (hash == node_ptr->hash
2205  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2206  value = node_ptr->value;
2207  if (!last.is_null()) {
2208  // move to front
2209  last->next = node_ptr->next;
2210  node_ptr->next = _buckets[b];
2211  _buckets[b] = node;
2212  }
2213  oldkey = node_ptr->key;
2214  oldvalue = node_ptr->value;
2215  if (replace) {
2216  node_ptr->key = key;
2217  node_ptr->value = value;
2218  }
2219  _unlock_bucket(b);
2220  return false;
2221  }
2222  last = node;
2223  node = node->next;
2224  }
2225  node = vnew<Node>();
2226  Node *node_ptr = node.as_ptr();
2227  node_ptr->hash = hash;
2228  node_ptr->key = key;
2229  node_ptr->value = value;
2230  node_ptr->next = _buckets[b];
2231  _buckets[b] = node;
2232  oldkey = key;
2233  oldvalue = value;
2234  _unlock_bucket(b);
2235  return true;
2236 }
bool equal
Definition: cfModGcd.cc:4126
STATIC_VAR poly last
Definition: hdegree.cc:1151
T * as_ptr() const
Definition: vspace.h:1779

◆ find() [1/2]

template<typename Spec >
VRef<V> vspace::VMap< Spec >::find ( VRef< K key)
inline

Definition at line 2153 of file vspace.h.

2153  {
2154  VRef<V> value;
2155  if (find(key, value))
2156  return value;
2157  else
2158  return vnull<V>();
2159  }
bool find(VRef< K > key, VRef< V > &value)
Definition: vspace.h:2268

◆ find() [2/2]

template<typename Spec >
bool vspace::VMap< Spec >::find ( VRef< K key,
VRef< V > &  value 
)

Definition at line 2268 of file vspace.h.

2268  {
2269  size_t hash = Spec::hash(key.as_ptr());
2270  size_t b = hash & (_nbuckets - 1);
2271  _lock_bucket(b);
2272  VRef<Node> node = _buckets[b];
2273  VRef<Node> last = vnull<Node>();
2274  while (!node.is_null()) {
2275  Node *node_ptr = node.as_ptr();
2276  if (hash == node_ptr->hash
2277  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2278  value = node_ptr->value;
2279  // move to front
2280  if (!last.is_null()) {
2281  last->next = node_ptr->next;
2282  node_ptr->next = _buckets[b];
2283  }
2284  _buckets[b] = node;
2285  _unlock_bucket(b);
2286  return true;
2287  }
2288  last = node;
2289  node = node->next;
2290  }
2291  _unlock_bucket(b);
2292  return false;
2293 }

◆ remove() [1/2]

template<typename Spec >
bool vspace::VMap< Spec >::remove ( VRef< K key)
inline

Definition at line 2147 of file vspace.h.

2147  {
2148  VRef<K> oldkey;
2149  VRef<V> oldvalue;
2150  return remove(key, oldkey, oldvalue);
2151  }
bool remove(VRef< K > key, VRef< K > &oldkey, VRef< V > &oldvalue)
Definition: vspace.h:2239

◆ remove() [2/2]

template<typename Spec >
bool vspace::VMap< Spec >::remove ( VRef< K key,
VRef< K > &  oldkey,
VRef< V > &  oldvalue 
)

Definition at line 2239 of file vspace.h.

2239  {
2240  size_t hash = Spec::hash(key.as_ptr());
2241  size_t b = hash & (_nbuckets - 1);
2242  _lock_bucket(b);
2243  VRef<Node> node = _buckets[b];
2244  VRef<Node> last = vnull<Node>();
2245  while (!node.is_null()) {
2246  Node *node_ptr = node.as_ptr();
2247  if (hash == node_ptr->hash
2248  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
2249  oldkey = node_ptr->key;
2250  oldvalue = node_ptr->value;
2251  // remove from list
2252  if (last.is_null()) {
2253  _buckets[b] = node_ptr->next;
2254  } else {
2255  last->next = node_ptr->next;
2256  }
2257  _unlock_bucket(b);
2258  return true;
2259  }
2260  last = node;
2261  node = node->next;
2262  }
2263  _unlock_bucket(b);
2264  return false;
2265 }

Field Documentation

◆ _buckets

template<typename Spec >
VRef<VRef<Node> > vspace::VMap< Spec >::_buckets
private

Definition at line 2125 of file vspace.h.

◆ _locks

template<typename Spec >
VRef<internals::FastLock> vspace::VMap< Spec >::_locks
private

Definition at line 2126 of file vspace.h.

◆ _nbuckets

template<typename Spec >
size_t vspace::VMap< Spec >::_nbuckets
private

Definition at line 2127 of file vspace.h.


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