Lolly 1.4.27
Loading...
Searching...
No Matches
Public Member Functions | Private Attributes | Friends | List of all members
hashmap_rep< T, U > Class Template Reference

#include <hashmap.hpp>

Inheritance diagram for hashmap_rep< T, U >:
Inheritance graph
[legend]
Collaboration diagram for hashmap_rep< T, U >:
Collaboration graph
[legend]

Public Member Functions

 hashmap_rep (U init2, int n2=1, int max2=1)
 Constructor for the hashmap_rep class.
 
 ~hashmap_rep ()
 Destructor for the hashmap_rep class.
 
void resize (int n)
 Resizes the hashmap and rehashes all existing keys.
 
void reset (T x)
 Remove a specific key from the hashmap, if it exists.
 
void generate (void(*routine)(T))
 Applies a given routine to each key in the hashmap.
 
bool contains (T x)
 
bool empty ()
 
U bracket_ro (T x)
 
U & bracket_rw (T x)
 
U & bracket_rw_debug (T x)
 
void join (hashmap< T, U > H)
 Joins another hashmap into the current hashmap.
 
void write_back (T x, hashmap< T, U > base)
 Writes back a key-value pair into the current hashmap using a base hashmap as a reference.
 
void pre_patch (hashmap< T, U > patch, hashmap< T, U > base)
 Applies a patch to the current hashmap using another hashmap as a base reference.
 
void post_patch (hashmap< T, U > patch, hashmap< T, U > base)
 Applies a post-patch to the current hashmap using another hashmap as a base reference.
 

Private Attributes

int size
 
int n
 
int max
 
U init
 
list< hashentry< T, U > > * a
 
- Private Attributes inherited from concrete_struct
int ref_count
 The reference count for the concrete object.
 

Friends

class hashmap< T, U >
 
class rel_hashmap< T, U >
 
class rel_hashmap_rep< T, U >
 
class hashmap_iterator_rep< T, U >
 
class edit_env_rep
 
int N LESSGTR (hashmap< T, U > h)
 
tm_ostream & operator<<LESSGTR (tm_ostream &out, hashmap< T, U > h)
 
hashmap< T, U > copy LESSGTR (hashmap< T, U > h)
 
hashmap< T, U > changes LESSGTR (hashmap< T, U > patch, hashmap< T, U > base)
 
hashmap< T, U > invert LESSGTR (hashmap< T, U > patch, hashmap< T, U > base)
 
bool operator==LESSGTR (hashmap< T, U > h1, hashmap< T, U > h2)
 
bool operator!=LESSGTR (hashmap< T, U > h1, hashmap< T, U > h2)
 

Additional Inherited Members

- Private Member Functions inherited from concrete_struct
 concrete_struct ()
 Default constructor for the concrete object. Increments the reference count.
 
virtual ~concrete_struct ()
 Virtual destructor for the concrete object. Decrements the reference count.
 

Detailed Description

template<class T, class U>
class hashmap_rep< T, U >

Definition at line 47 of file hashmap.hpp.

Constructor & Destructor Documentation

◆ hashmap_rep()

template<class T , class U >
hashmap_rep< T, U >::hashmap_rep ( U init2,
int n2 = 1,
int max2 = 1 )
inline

Constructor for the hashmap_rep class.

Template Parameters
TType of the keys in the hash map.
UType of the values in the hash map.
Parameters
init2Initial value for hash entries. *
n2Initial size of the hash table array.
max2Maximum allowable size for dynamic resizing.

Definition at line 52 of file hashmap.hpp.

65 : size (0), n (n2), max (max2), init (init2),
66 a (tm_new_array<list<hashentry<T, U>>> (n)) {}
hashmap_rep::max
int max
Definition hashmap.hpp:50
hashmap_rep::n
int n
Definition hashmap.hpp:49
hashmap_rep::size
int size
Definition hashmap.hpp:48
hashmap_rep::init
U init
Definition hashmap.hpp:51
hashmap_rep::a
list< hashentry< T, U > > * a
Definition hashmap.hpp:52
list
The list class represents a linked list.
Definition list.hpp:48
tm_new_array
C * tm_new_array(int n)
Definition fast_alloc.hpp:408

◆ ~hashmap_rep()

template<class T , class U >
hashmap_rep< T, U >::~hashmap_rep ( )
inline

Destructor for the hashmap_rep class.

Template Parameters
TType of the keys in the hash map.
UType of the values in the hash map.

Definition at line 52 of file hashmap.hpp.

74{ tm_delete_array (a); }
tm_delete_array
void tm_delete_array(C *Ptr)
Definition fast_alloc.hpp:435

Member Function Documentation

◆ resize()

template<class T , class U >
void hashmap_rep< T, U >::resize ( int n)

Resizes the hashmap and rehashes all existing keys.

Parameters
nThe new size of the hashmap.
Note
This operation could be costly as it rehashes all keys.

Definition at line 48 of file hashmap.ipp.

48 {
49 int i;
50 int oldn= n;
51 list<hashentry<T, U>>* olda= a;
52 n = n2;
53 a = tm_new_array<list<hashentry<T, U>>> (n);
54 for (i= 0; i < oldn; i++) {
55 list<hashentry<T, U>> l (olda[i]);
56 while (!is_nil (l)) {
57 list<hashentry<T, U>>& newl= a[hash (l->item.key) & (n - 1)];
58 newl = list<hashentry<T, U>> (l->item, newl);
59 l = l->next;
60 }
61 }
62 tm_delete_array (olda);
63}
hash
int hash(pointer ptr)
Computes a hash value for a pointer.
Definition basic.cpp:17
is_nil
bool is_nil(blackbox x)
Definition blackbox.hpp:29

◆ reset()

template<class T , class U >
void hashmap_rep< T, U >::reset ( T x)

Remove a specific key from the hashmap, if it exists.

Template Parameters
TThe type of the key in the hashmap.
Parameters
xThe key to be removed from the hashmap.

Definition at line 108 of file hashmap.ipp.

108 {
109 int hv= hash (x);
110 list<hashentry<T, U>>* l = &(a[hv & (n - 1)]);
111 while (!is_nil (*l)) {
112 if ((*l)->item.code == hv && (*l)->item.key == x) {
113 *l= (*l)->next;
114 size--;
115 if (size < (n >> 1) * max) resize (n >> 1);
116 return;
117 }
118 l= &((*l)->next);
119 }
120}
hashmap_rep::resize
void resize(int n)
Resizes the hashmap and rehashes all existing keys.
Definition hashmap.ipp:48

◆ generate()

template<class T , class U >
void hashmap_rep< T, U >::generate ( void(*)(T) routine)

Applies a given routine to each key in the hashmap.

Template Parameters
TThe type of the key in the hashmap.
Parameters
routineThe function pointer to the routine to be applied to each key in the hashmap.

Definition at line 123 of file hashmap.ipp.

123 {
124 int i;
125 for (i= 0; i < n; i++) {
126 list<hashentry<T, U>> l (a[i]);
127 while (!is_nil (l)) {
128 routine (l->item.key);
129 l= l->next;
130 }
131 }
132}
routine
void routine(int key)
Definition hashmap_test.cpp:31

◆ contains()

template<class T , class U >
bool hashmap_rep< T, U >::contains ( T x)

Definition at line 66 of file hashmap.ipp.

66 {
67 int hv= hash (x);
68 list<hashentry<T, U>> l (a[hv & (n - 1)]);
69 while (!is_nil (l)) {
70 if (l->item.code == hv && l->item.key == x) return true;
71 l= l->next;
72 }
73 return false;
74}

◆ empty()

template<class T , class U >
bool hashmap_rep< T, U >::empty ( )

Definition at line 77 of file hashmap.ipp.

77 {
78 return size == 0;
79}

◆ bracket_ro()

template<class T , class U >
U hashmap_rep< T, U >::bracket_ro ( T x)

Definition at line 97 of file hashmap.ipp.

97 {
98 int hv= hash (x);
99 list<hashentry<T, U>> l (a[hv & (n - 1)]);
100 while (!is_nil (l)) {
101 if (l->item.code == hv && l->item.key == x) return l->item.im;
102 l= l->next;
103 }
104 return init;
105}

◆ bracket_rw()

template<class T , class U >
U & hashmap_rep< T, U >::bracket_rw ( T x)

Definition at line 82 of file hashmap.ipp.

82 {
83 int hv= hash (x);
84 list<hashentry<T, U>> l (a[hv & (n - 1)]);
85 while (!is_nil (l)) {
86 if (l->item.code == hv && l->item.key == x) return l->item.im;
87 l= l->next;
88 }
89 if (size >= n * max) resize (n << 1);
90 list<hashentry<T, U>>& rl= a[hv & (n - 1)];
91 rl = list<hashentry<T, U>> (H (hv, x, init), rl);
92 size++;
93 return rl->item.im;
94}
H
#define H
Definition hashmap.ipp:17

◆ bracket_rw_debug()

template<class T , class U >
U & hashmap_rep< T, U >::bracket_rw_debug ( T x)

◆ join()

template<class T , class U >
void hashmap_rep< T, U >::join ( hashmap< T, U > H)

Joins another hashmap into the current hashmap.

Template Parameters
TThe type of the key in the hashmap.
UThe type of the value in the hashmap.
Parameters
hThe hashmap to be joined into the current hashmap.

Definition at line 150 of file hashmap.ipp.

150 {
151 int i= 0, n= h->n;
152 for (; i < n; i++) {
153 list<hashentry<T, U>> l= h->a[i];
154 for (; !is_nil (l); l= l->next)
155 bracket_rw (l->item.key)= copy (l->item.im);
156 }
157}
hashmap_rep::bracket_rw
U & bracket_rw(T x)
Definition hashmap.ipp:82
copy
hashmap< T, U > copy(hashmap< T, U > h)
Definition hashmap_extra.ipp:81

◆ write_back()

template<class T , class U >
void hashmap_rep< T, U >::write_back ( T x,
hashmap< T, U > base )

Writes back a key-value pair into the current hashmap using a base hashmap as a reference.

Template Parameters
TThe type of the key in the hashmap.
UThe type of the value in the hashmap.
Parameters
xThe key to be inserted or updated in the current hashmap.
baseThe base hashmap used as a reference for the value of the key.

Definition at line 20 of file hashmap_extra.ipp.

20 {
21 int hv= hash (x);
22 list<hashentry<T, U>> l (a[hv & (n - 1)]);
23 while (!is_nil (l)) {
24 if (l->item.code == hv && l->item.key == x) return;
25 l= l->next;
26 }
27 if (size >= n * max) resize (n << 1);
28 list<hashentry<T, U>>& rl= a[hv & (n - 1)];
29 rl = list<hashentry<T, U>> (H (hv, x, init), rl);
30 size++;
31
32 list<hashentry<T, U>> bl (base->a[hv & (base->n - 1)]);
33 while (!is_nil (bl)) {
34 if (bl->item.code == hv && bl->item.key == x) {
35 rl->item.im= bl->item.im;
36 return;
37 }
38 bl= bl->next;
39 }
40 rl->item.im= base->init;
41}
list::init
static list< T > init
A static list object used for initializing new list objects.
Definition list.hpp:100

◆ pre_patch()

template<class T , class U >
void hashmap_rep< T, U >::pre_patch ( hashmap< T, U > patch,
hashmap< T, U > base )

Applies a patch to the current hashmap using another hashmap as a base reference.

Template Parameters
TThe type of the key in the hashmap.
UThe type of the value in the hashmap.
Parameters
patchThe hashmap containing the key-value pairs that serve as the patch.
baseThe base hashmap used as a reference for the patching process.

Definition at line 44 of file hashmap_extra.ipp.

44 {
45 int i= 0, n= patch->n;
46 for (; i < n; i++) {
47 list<hashentry<T, U>> l= patch->a[i];
48 for (; !is_nil (l); l= l->next) {
49 T x= l->item.key;
50 U y= contains (x) ? bracket_ro (x) : l->item.im;
51 if (base[x] == y) reset (x);
52 else bracket_rw (x)= y;
53 }
54 }
55}
hashmap_rep::reset
void reset(T x)
Remove a specific key from the hashmap, if it exists.
Definition hashmap.ipp:108
hashmap_rep::contains
bool contains(T x)
Definition hashmap.ipp:66
hashmap_rep::bracket_ro
U bracket_ro(T x)
Definition hashmap.ipp:97

◆ post_patch()

template<class T , class U >
void hashmap_rep< T, U >::post_patch ( hashmap< T, U > patch,
hashmap< T, U > base )

Applies a post-patch to the current hashmap using another hashmap as a base reference.

Template Parameters
TThe type of the key in the hashmap.
UThe type of the value in the hashmap.
Parameters
patchThe hashmap containing the key-value pairs that serve as the post-patch.
baseThe base hashmap used as a reference for the post-patching process.

Definition at line 58 of file hashmap_extra.ipp.

58 {
59 int i= 0, n= patch->n;
60 for (; i < n; i++) {
61 list<hashentry<T, U>> l= patch->a[i];
62 for (; !is_nil (l); l= l->next) {
63 T x= l->item.key;
64 U y= l->item.im;
65 if (base[x] == y) reset (x);
66 else bracket_rw (x)= y;
67 }
68 }
69}

Friends And Related Symbol Documentation

◆ hashmap< T, U >

template<class T , class U >
friend class hashmap< T, U >
friend

Definition at line 114 of file hashmap.hpp.

◆ rel_hashmap< T, U >

template<class T , class U >
friend class rel_hashmap< T, U >
friend

Definition at line 114 of file hashmap.hpp.

◆ rel_hashmap_rep< T, U >

template<class T , class U >
friend class rel_hashmap_rep< T, U >
friend

Definition at line 114 of file hashmap.hpp.

◆ hashmap_iterator_rep< T, U >

template<class T , class U >
friend class hashmap_iterator_rep< T, U >
friend

Definition at line 114 of file hashmap.hpp.

◆ edit_env_rep

template<class T , class U >
friend class edit_env_rep
friend

Definition at line 164 of file hashmap.hpp.

◆ LESSGTR [1/4]

template<class T , class U >
int N LESSGTR ( hashmap< T, U > h)
friend

◆ operator<<LESSGTR

template<class T , class U >
tm_ostream & operator<<LESSGTR ( tm_ostream & out,
hashmap< T, U > h )
friend

◆ LESSGTR [2/4]

template<class T , class U >
hashmap< T, U > copy LESSGTR ( hashmap< T, U > h)
friend

◆ LESSGTR [3/4]

template<class T , class U >
hashmap< T, U > changes LESSGTR ( hashmap< T, U > patch,
hashmap< T, U > base )
friend

◆ LESSGTR [4/4]

template<class T , class U >
hashmap< T, U > invert LESSGTR ( hashmap< T, U > patch,
hashmap< T, U > base )
friend

◆ operator==LESSGTR

template<class T , class U >
bool operator==LESSGTR ( hashmap< T, U > h1,
hashmap< T, U > h2 )
friend

◆ operator!=LESSGTR

template<class T , class U >
bool operator!=LESSGTR ( hashmap< T, U > h1,
hashmap< T, U > h2 )
friend

Member Data Documentation

◆ size

template<class T , class U >
int hashmap_rep< T, U >::size
private

Definition at line 48 of file hashmap.hpp.

◆ n

template<class T , class U >
int hashmap_rep< T, U >::n
private

Definition at line 49 of file hashmap.hpp.

◆ max

template<class T , class U >
int hashmap_rep< T, U >::max
private

Definition at line 50 of file hashmap.hpp.

◆ init

template<class T , class U >
U hashmap_rep< T, U >::init
private

Definition at line 51 of file hashmap.hpp.

◆ a

template<class T , class U >
list<hashentry<T, U> >* hashmap_rep< T, U >::a
private

Definition at line 52 of file hashmap.hpp.

The documentation for this class was generated from the following files:
Generated by doxygen 1.10.0