Loading...
Searching...
No Matches
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< V > | find (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.

{
using namespace internals;
_nbuckets = 8;
while (_nbuckets < size)
_nbuckets *= 2;
_buckets = vnew_array<VRef<Node> >(_nbuckets);
_locks = vnew_uninitialized_array<FastLock>(_nbuckets);
for (size_t i = 0; i < _nbuckets; i++)
_locks[i]
= FastLock(METABLOCK_SIZE + _locks.offset() + sizeof(FastLock) * i);
}
vspace::VMap
Definition vspace.h:2115
vspace::VMap::_buckets
VRef< VRef< Node > > _buckets
Definition vspace.h:2125
vspace::VMap::_locks
VRef< internals::FastLock > _locks
Definition vspace.h:2126
vspace::VMap::_nbuckets
size_t _nbuckets
Definition vspace.h:2127
vspace::vnew_uninitialized_array
VRef< T > vnew_uninitialized_array(size_t n)
Definition vspace.h:1895
vspace::FastLock
internals::Mutex FastLock
Definition vspace.h:2340

## ~VMap()

template<typename Spec>

vspace::VMap< Spec >::~VMap | ( |  | ) |

Definition at line 2176 of file vspace.h.

{
for (size_t b = 0; b < _nbuckets; b++) {
_lock_bucket(b);
VRef<Node> node = _buckets[b];
while (node) {
Node *node_ptr = node.as_ptr();
VRef<Node> next = node_ptr->next;
Spec::free_key(node_ptr->key);
Spec::free_value(node_ptr->value);
node.free();
node = next;
}
_unlock_bucket(b);
}
_buckets.free();
_locks.free();
}
vspace::VMap::_lock_bucket
void _lock_bucket(size_t b)
Definition vspace.h:2129
vspace::VMap::_unlock_bucket
void _unlock_bucket(size_t b)
Definition vspace.h:2132
vspace::VMap::Node
Definition vspace.h:2119

## Member Function Documentation

## _lock_bucket()

template<typename Spec>

void vspace::VMap< Spec >::_lock_bucket | ( | size_t | b | ) |

inline private

Definition at line 2129 of file vspace.h.

{
_locks[b].lock();
}

## _unlock_bucket()

template<typename Spec>

void vspace::VMap< Spec >::_unlock_bucket | ( | size_t | b | ) |

inline private

Definition at line 2132 of file vspace.h.

{
_locks[b].unlock();
}

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

{
VRef<K> oldkey;
VRef<V> oldvalue;
return add(key, value, oldkey, oldvalue, replace);
}
add
STATIC_VAR unsigned add[]
Definition misc_ip.cc:108

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

{
size_t hash = Spec::hash(key.as_ptr());
size_t b = hash & (_nbuckets - 1);
_lock_bucket(b);
VRef<Node> node = _buckets[b];
VRef<Node> last = vnull<Node>();
while (!node.is_null()) {
Node *node_ptr = node.as_ptr();
if (hash == node_ptr->hash
&& Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
value = node_ptr->value;
if (!last.is_null()) {
// move to front
last->next = node_ptr->next;
node_ptr->next = _buckets[b];
_buckets[b] = node;
}
oldkey = node_ptr->key;
oldvalue = node_ptr->value;
if (replace) {
node_ptr->key = key;
node_ptr->value = value;
}
_unlock_bucket(b);
return false;
}
last = node;
node = node->next;
}
node = vnew<Node>();
Node *node_ptr = node.as_ptr();
node_ptr->hash = hash;
node_ptr->key = key;
node_ptr->value = value;
node_ptr->next = _buckets[b];
_buckets[b] = node;
oldkey = key;
oldvalue = value;
_unlock_bucket(b);
return true;
}
vspace::vnew
VRef< T > vnew()
Definition vspace.h:1872
vspace::vnull
VRef< T > vnull()
Definition vspace.h:1867

## find() [1/2]

template<typename Spec>

VRef< V > vspace::VMap< Spec >::find | ( | VRef< K > | key | ) |

inline

Definition at line 2153 of file vspace.h.

{
VRef<V> value;
if (find(key, value))
return value;
else
return vnull<V>();
}
vspace::VMap::find
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.

{
size_t hash = Spec::hash(key.as_ptr());
size_t b = hash & (_nbuckets - 1);
_lock_bucket(b);
VRef<Node> node = _buckets[b];
VRef<Node> last = vnull<Node>();
while (!node.is_null()) {
Node *node_ptr = node.as_ptr();
if (hash == node_ptr->hash
&& Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
value = node_ptr->value;
// move to front
if (!last.is_null()) {
last->next = node_ptr->next;
node_ptr->next = _buckets[b];
}
_buckets[b] = node;
_unlock_bucket(b);
return true;
}
last = node;
node = node->next;
}
_unlock_bucket(b);
return false;
}

## remove() [1/2]

template<typename Spec>

bool vspace::VMap< Spec >::remove | ( | VRef< K > | key | ) |

inline

Definition at line 2147 of file vspace.h.

{
VRef<K> oldkey;
VRef<V> oldvalue;
return remove(key, oldkey, oldvalue);
}
vspace::VMap::remove
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.

{
size_t hash = Spec::hash(key.as_ptr());
size_t b = hash & (_nbuckets - 1);
_lock_bucket(b);
VRef<Node> node = _buckets[b];
VRef<Node> last = vnull<Node>();
while (!node.is_null()) {
Node *node_ptr = node.as_ptr();
if (hash == node_ptr->hash
&& Spec::equal(key.as_ptr(), node_ptr->key.as_ptr())) {
oldkey = node_ptr->key;
oldvalue = node_ptr->value;
// remove from list
if (last.is_null()) {
_buckets[b] = node_ptr->next;
} else {
last->next = node_ptr->next;
}
_unlock_bucket(b);
return true;
}
last = node;
node = node->next;
}
_unlock_bucket(b);
return false;
}

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

- kernel/oswrapper/vspace.h