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);
}

~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();
}

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.

                              {
    _locks[b].lock();
  }

_unlock_bucket()

template<typename Spec >

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

inlineprivate

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() [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;
}

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>();
  }

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);
  }

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