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 780 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 784 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 782 of file vspace.h.

◆ V

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

Definition at line 783 of file vspace.h.

Constructor & Destructor Documentation

◆ VMap()

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

Definition at line 828 of file vspace.h.

828  {
829  using namespace internals;
830  _nbuckets = 8;
831  while (_nbuckets < size)
832  _nbuckets *= 2;
833  _buckets = vnew_array<VRef<Node> >(_nbuckets);
834  _locks = vnew_uninitialized_array<FastLock>(_nbuckets);
835  for (size_t i = 0; i < _nbuckets; i++)
836  _locks[i]
837  = FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
838 }
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:790
VRef< internals::FastLock > _locks
Definition: vspace.h:791
size_t _nbuckets
Definition: vspace.h:792
static const size_t METABLOCK_SIZE
Definition: vspace.h:87
internals::Mutex FastLock
Definition: vspace.h:1005

◆ ~VMap()

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

Definition at line 841 of file vspace.h.

841  {
842  for (size_t b = 0; b < _nbuckets; b++) {
843  _lock_bucket(b);
844  VRef<Node> node = _buckets[b];
845  while (node) {
846  Node *node_ptr = node.as_ptr();
847  VRef<Node> next = node_ptr->next;
848  Spec::free_key(node_ptr->key);
849  Spec::free_value(node_ptr->value);
850  node.free();
851  node = next;
852  }
853  _unlock_bucket(b);
854  }
855  _buckets.free();
856  _locks.free();
857 }
CanonicalForm b
Definition: cfModGcd.cc:4103
void _lock_bucket(size_t b)
Definition: vspace.h:794
void _unlock_bucket(size_t b)
Definition: vspace.h:797
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 794 of file vspace.h.

794  {
795  _locks[b].lock();
796  }

◆ _unlock_bucket()

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

Definition at line 797 of file vspace.h.

797  {
798  _locks[b].unlock();
799  }

◆ add() [1/2]

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

Definition at line 806 of file vspace.h.

806  {
807  VRef<K> oldkey;
808  VRef<V> oldvalue;
809  return add(key, value, oldkey, oldvalue, replace);
810  }
bool add(VRef< K > key, VRef< V > value, VRef< K > &oldkey, VRef< V > &oldvalue, bool replace=true)
Definition: vspace.h:860

◆ 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 860 of file vspace.h.

861  {
862  size_t hash = Spec::hash(key.as_ptr());
863  size_t b = hash & (_nbuckets - 1);
864  _lock_bucket(b);
865  VRef<Node> node = _buckets[b];
866  VRef<Node> last = vnull<Node>();
867  while (!node.is_null()) {
868  Node *node_ptr = node.as_ptr();
869  if (hash == node_ptr->hash
870  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
871  value = node_ptr->value;
872  if (!last.is_null()) {
873  // move to front
874  last->next = node_ptr->next;
875  node_ptr->next = _buckets[b];
876  _buckets[b] = node;
877  }
878  oldkey = node_ptr->key;
879  oldvalue = node_ptr->value;
880  if (replace) {
881  node_ptr->key = key;
882  node_ptr->value = value;
883  }
884  _unlock_bucket(b);
885  return false;
886  }
887  last = node;
888  node = node->next;
889  }
890  node = vnew<Node>();
891  Node *node_ptr = node.as_ptr();
892  node_ptr->hash = hash;
893  node_ptr->key = key;
894  node_ptr->value = value;
895  node_ptr->next = _buckets[b];
896  _buckets[b] = node;
897  oldkey = key;
898  oldvalue = value;
899  _unlock_bucket(b);
900  return true;
901 }
bool equal
Definition: cfModGcd.cc:4126
STATIC_VAR poly last
Definition: hdegree.cc:1151
T * as_ptr() const
Definition: vspace.h:444

◆ find() [1/2]

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

Definition at line 818 of file vspace.h.

818  {
819  VRef<V> value;
820  if (find(key, value))
821  return value;
822  else
823  return vnull<V>();
824  }
bool find(VRef< K > key, VRef< V > &value)
Definition: vspace.h:933

◆ find() [2/2]

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

Definition at line 933 of file vspace.h.

933  {
934  size_t hash = Spec::hash(key.as_ptr());
935  size_t b = hash & (_nbuckets - 1);
936  _lock_bucket(b);
937  VRef<Node> node = _buckets[b];
938  VRef<Node> last = vnull<Node>();
939  while (!node.is_null()) {
940  Node *node_ptr = node.as_ptr();
941  if (hash == node_ptr->hash
942  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
943  value = node_ptr->value;
944  // move to front
945  if (!last.is_null()) {
946  last->next = node_ptr->next;
947  node_ptr->next = _buckets[b];
948  }
949  _buckets[b] = node;
950  _unlock_bucket(b);
951  return true;
952  }
953  last = node;
954  node = node->next;
955  }
956  _unlock_bucket(b);
957  return false;
958 }

◆ remove() [1/2]

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

Definition at line 812 of file vspace.h.

812  {
813  VRef<K> oldkey;
814  VRef<V> oldvalue;
815  return remove(key, oldkey, oldvalue);
816  }
bool remove(VRef< K > key, VRef< K > &oldkey, VRef< V > &oldvalue)
Definition: vspace.h:904

◆ remove() [2/2]

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

Definition at line 904 of file vspace.h.

904  {
905  size_t hash = Spec::hash(key.as_ptr());
906  size_t b = hash & (_nbuckets - 1);
907  _lock_bucket(b);
908  VRef<Node> node = _buckets[b];
909  VRef<Node> last = vnull<Node>();
910  while (!node.is_null()) {
911  Node *node_ptr = node.as_ptr();
912  if (hash == node_ptr->hash
913  && Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
914  oldkey = node_ptr->key;
915  oldvalue = node_ptr->value;
916  // remove from list
917  if (last.is_null()) {
918  _buckets[b] = node_ptr->next;
919  } else {
920  last->next = node_ptr->next;
921  }
922  _unlock_bucket(b);
923  return true;
924  }
925  last = node;
926  node = node->next;
927  }
928  _unlock_bucket(b);
929  return false;
930 }

Field Documentation

◆ _buckets

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

Definition at line 790 of file vspace.h.

◆ _locks

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

Definition at line 791 of file vspace.h.

◆ _nbuckets

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

Definition at line 792 of file vspace.h.


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