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++) {
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 }
854 }
855 _buckets.free();
856 _locks.free();
857}
CanonicalForm b
Definition: cfModGcd.cc:4105
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);
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 }
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;
900 return true;
901}
bool equal
Definition: cfModGcd.cc:4128
STATIC_VAR poly last
Definition: hdegree.cc:1150

◆ 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);
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;
951 return true;
952 }
953 last = node;
954 node = node->next;
955 }
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);
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 }
923 return true;
924 }
925 last = node;
926 node = node->next;
927 }
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: