1
2 /******************************************************************************
3 * MODULE : hashmap.cpp
4 * DESCRIPTION: fixed size hashmaps with reference counting
5 * COPYRIGHT : (C) 1999 Joris van der Hoeven
6 *******************************************************************************
7 * This software falls under the GNU general public license version 3 or later.
8 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
9 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
10 ******************************************************************************/
11
12 #ifndef HASHMAP_CC
13 #define HASHMAP_CC
14 #include "hashmap.hpp"
15 #define TMPL template<class T, class U>
16 #define H hashentry<T,U>
17
18 /******************************************************************************
19 * Hashmap entries
20 ******************************************************************************/
21
hashentry(int code2,T key2,U im2)22 TMPL H::hashentry (int code2, T key2, U im2):
23 code (code2), key (key2), im (im2) {}
24
operator tree()25 TMPL H::operator tree () {
26 return tree (ASSOCIATE, as_tree(key), as_tree(im)); }
27
28 TMPL tm_ostream&
operator <<(tm_ostream & out,H h)29 operator << (tm_ostream& out, H h) {
30 out << h.key << "->" << h.im;
31 return out;
32 }
33
34 TMPL bool
operator ==(H h1,H h2)35 operator == (H h1, H h2) {
36 return (h1.code==h2.code) && (h1.key==h2.key) && (h1.im==h2.im);
37 }
38
39 TMPL bool
operator !=(H h1,H h2)40 operator != (H h1, H h2) {
41 return (h1.code!=h2.code) || (h1.key!=h2.key) || (h1.im!=h2.im);
42 }
43
44 /******************************************************************************
45 * Routines for hashmaps
46 ******************************************************************************/
47
48 TMPL void
resize(int n2)49 hashmap_rep<T,U>::resize (int n2) {
50 int i;
51 int oldn= n;
52 list<hashentry<T,U> >* olda= a;
53 n= n2;
54 a= tm_new_array<list<hashentry<T,U> > > (n);
55 for (i=0; i<oldn; i++) {
56 list<hashentry<T,U> > l(olda[i]);
57 while (!is_nil (l)) {
58 list<hashentry<T,U> >& newl= a[hash(l->item.key)&(n-1)];
59 newl= list<hashentry<T,U> > (l->item, newl);
60 l=l->next;
61 }
62 }
63 tm_delete_array (olda);
64 }
65
66 TMPL bool
contains(T x)67 hashmap_rep<T,U>::contains (T x) {
68 register int hv= hash (x);
69 list<hashentry<T,U> > l (a [hv & (n-1)]);
70 while (!is_nil (l)) {
71 if (l->item.code == hv && l->item.key == x)
72 return true;
73 l= l->next;
74 }
75 return false;
76 }
77
78 TMPL bool
empty()79 hashmap_rep<T,U>::empty () {
80 return size==0;
81 }
82
83 TMPL U&
bracket_rw(T x)84 hashmap_rep<T,U>::bracket_rw (T x) {
85 register int hv= hash (x);
86 list<hashentry<T,U> > l (a [hv & (n-1)]);
87 while (!is_nil (l)) {
88 if (l->item.code == hv && l->item.key == x)
89 return l->item.im;
90 l= l->next;
91 }
92 if (size >= n*max) resize (n<<1);
93 list<hashentry<T,U> >& rl= a [hv & (n-1)];
94 rl= list<hashentry<T,U> > (H (hv, x, init), rl);
95 size ++;
96 return rl->item.im;
97 }
98
99 TMPL U
bracket_ro(T x)100 hashmap_rep<T,U>::bracket_ro (T x) {
101 register int hv= hash (x);
102 list<hashentry<T,U> > l (a [hv & (n-1)]);
103 while (!is_nil (l)) {
104 if (l->item.code == hv && l->item.key == x)
105 return l->item.im;
106 l= l->next;
107 }
108 return init;
109 }
110
111 TMPL void
reset(T x)112 hashmap_rep<T,U>::reset (T x) {
113 register int hv= hash (x);
114 list<hashentry<T,U> > *l= &(a [hv & (n-1)]);
115 while (!is_nil (*l)) {
116 if ((*l)->item.code == hv && (*l)->item.key == x) {
117 *l= (*l)->next;
118 size --;
119 if (size < (n>>1) * max) resize (n>>1);
120 return;
121 }
122 l= &((*l)->next);
123 }
124 }
125
126 TMPL void
generate(void (* routine)(T))127 hashmap_rep<T,U>::generate (void (*routine) (T)) {
128 int i;
129 for (i=0; i<n; i++) {
130 list<hashentry<T,U> > l (a[i]);
131 while (!is_nil (l)) {
132 routine (l->item.key);
133 l=l->next;
134 }
135 }
136 }
137
138 TMPL tm_ostream&
operator <<(tm_ostream & out,hashmap<T,U> h)139 operator << (tm_ostream& out, hashmap<T,U> h) {
140 int i= 0, j= 0, n= h->n, size= h->size;
141 out << "{ ";
142 for (; i<n; i++) {
143 list<hashentry<T,U> > l= h->a[i];
144 for (; !is_nil (l); l= l->next, j++) {
145 out << l->item;
146 if (j != size-1) out << ", ";
147 }
148 }
149 out << " }";
150 return out;
151 }
152
operator tree()153 TMPL hashmap<T,U>::operator tree () {
154 int i=0, j=0, n=rep->n, size=rep->size;
155 tree t (COLLECTION, size);
156 for (; i<n; i++) {
157 list<hashentry<T,U> > l= rep->a[i];
158 for (; !is_nil (l); l= l->next, j++)
159 t[j]= (tree) l->item;
160 }
161 return t;
162 }
163
164 TMPL void
join(hashmap<T,U> h)165 hashmap_rep<T,U>::join (hashmap<T,U> h) {
166 int i= 0, n= h->n;
167 for (; i<n; i++) {
168 list<hashentry<T,U> > l= h->a[i];
169 for (; !is_nil(l); l= l->next)
170 bracket_rw (l->item.key)= copy (l->item.im);
171 }
172 }
173
174 TMPL bool
operator ==(hashmap<T,U> h1,hashmap<T,U> h2)175 operator == (hashmap<T,U> h1, hashmap<T,U> h2) {
176 if (h1->size != h2->size) return false;
177 int i= 0, n= h1->n;
178 for (; i<n; i++) {
179 list<hashentry<T,U> > l= h1->a[i];
180 for (; !is_nil(l); l=l->next)
181 if (h2[l->item.key] != l->item.im) return false;
182 }
183 return true;
184 }
185
186 TMPL bool
operator !=(hashmap<T,U> h1,hashmap<T,U> h2)187 operator != (hashmap<T,U> h1, hashmap<T,U> h2) {
188 return !(h1 == h2);
189 }
190
191 #undef H
192 #undef TMPL
193 #endif // defined HASHMAP_CC
194