Line data Source code
1 : /* hashmap.vala
2 : *
3 : * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 : * Copyright (C) 1997-2000 GLib Team and others
5 : * Copyright (C) 2007-2009 Jürg Billeter
6 : *
7 : * This library is free software; you can redistribute it and/or
8 : * modify it under the terms of the GNU Lesser General Public
9 : * License as published by the Free Software Foundation; either
10 : * version 2.1 of the License, or (at your option) any later version.
11 :
12 : * This library is distributed in the hope that it will be useful,
13 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : * Lesser General Public License for more details.
16 :
17 : * You should have received a copy of the GNU Lesser General Public
18 : * License along with this library; if not, write to the Free Software
19 : * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 : *
21 : * Author:
22 : * Jürg Billeter <j@bitron.ch>
23 : */
24 :
25 : using GLib;
26 :
27 : /**
28 : * Hashtable implementation of the Map interface.
29 : */
30 1538 : public class Vala.HashMap<K,V> : Map<K,V> {
31 : public override int size {
32 8530 : get { return _nnodes; }
33 : }
34 :
35 : public HashFunc<K> key_hash_func {
36 16603171 : set { _key_hash_func = value; }
37 : }
38 :
39 : public EqualFunc<K> key_equal_func {
40 16603171 : set { _key_equal_func = value; }
41 : }
42 :
43 : public EqualFunc<V> value_equal_func {
44 16603171 : set { _value_equal_func = value; }
45 : }
46 :
47 : private int _array_size;
48 : private int _nnodes;
49 33203242 : private Node<K,V>[] _nodes;
50 :
51 : // concurrent modification protection
52 16603171 : private int _stamp = 0;
53 :
54 : private HashFunc<K> _key_hash_func;
55 : private EqualFunc<K> _key_equal_func;
56 : private EqualFunc<V> _value_equal_func;
57 :
58 : private const int MIN_SIZE = 11;
59 : private const int MAX_SIZE = 13845163;
60 :
61 33206342 : public HashMap (HashFunc<K> key_hash_func = GLib.direct_hash, EqualFunc<K> key_equal_func = GLib.direct_equal, EqualFunc<V> value_equal_func = GLib.direct_equal) {
62 16603171 : this.key_hash_func = key_hash_func;
63 16603171 : this.key_equal_func = key_equal_func;
64 16603171 : this.value_equal_func = value_equal_func;
65 16603171 : _array_size = MIN_SIZE;
66 16603171 : _nodes = new Node<K,V>[_array_size];
67 : }
68 :
69 4913562 : public override Set<K> get_keys () {
70 4913562 : return new KeySet<K,V> (this);
71 : }
72 :
73 3 : public override Collection<V> get_values () {
74 3 : return new ValueCollection<K,V> (this);
75 : }
76 :
77 1662 : public override Vala.MapIterator<K,V> map_iterator () {
78 1662 : return new MapIterator<K,V> (this);
79 : }
80 :
81 139347525 : private Node<K,V>** lookup_node (K key) {
82 139347525 : uint hash_value = _key_hash_func (key);
83 139347525 : Node<K,V>** node = &_nodes[hash_value % _array_size];
84 225798686 : while ((*node) != null && (hash_value != (*node)->key_hash || !_key_equal_func ((*node)->key, key))) {
85 86451161 : node = &((*node)->next);
86 : }
87 : return node;
88 : }
89 :
90 1388808 : public override bool contains (K key) {
91 1388808 : Node<K,V>** node = lookup_node (key);
92 1388808 : return (*node != null);
93 : }
94 :
95 98411206 : public override V? get (K key) {
96 98411206 : Node<K,V>* node = (*lookup_node (key));
97 98411206 : if (node != null) {
98 33158322 : return node->value;
99 : } else {
100 98411206 : return null;
101 : }
102 : }
103 :
104 39547408 : public override void set (K key, V value) {
105 39547408 : Node<K,V>** node = lookup_node (key);
106 39547408 : if (*node != null) {
107 787698 : (*node)->value = value;
108 : } else {
109 38759710 : uint hash_value = _key_hash_func (key);
110 38759710 : *node = new Node<K,V> (key, value, hash_value);
111 38759710 : _nnodes++;
112 38759710 : resize ();
113 : }
114 39547408 : _stamp++;
115 : }
116 :
117 103 : public override bool remove (K key) {
118 103 : Node<K,V>** node = lookup_node (key);
119 103 : if (*node != null) {
120 103 : Node<K,V> next = (owned) (*node)->next;
121 :
122 103 : (*node)->key = null;
123 103 : (*node)->value = null;
124 103 : delete *node;
125 :
126 103 : *node = (owned) next;
127 :
128 103 : _nnodes--;
129 103 : resize ();
130 103 : _stamp++;
131 103 : return true;
132 : }
133 103 : return false;
134 : }
135 :
136 16609460 : public override void clear () {
137 202922372 : for (int i = 0; i < _array_size; i++) {
138 186312912 : Node<K,V> node = (owned) _nodes[i];
139 225072507 : while (node != null) {
140 38759595 : Node<K,V> next = (owned) node.next;
141 38759595 : node.key = null;
142 38759595 : node.value = null;
143 38759595 : node = (owned) next;
144 : }
145 : }
146 16609460 : _nnodes = 0;
147 16609460 : resize ();
148 : }
149 :
150 55369273 : private void resize () {
151 98031757 : if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
152 12793496 : (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
153 42662484 : int new_array_size = (int) SpacedPrimes.closest (_nnodes);
154 42662484 : new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
155 :
156 42662484 : Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
157 :
158 989361600 : for (int i = 0; i < _array_size; i++) {
159 : Node<K,V> node;
160 473349558 : Node<K,V> next = null;
161 562319898 : for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
162 44485170 : next = (owned) node.next;
163 44485170 : uint hash_val = node.key_hash % new_array_size;
164 44485170 : node.next = (owned) new_nodes[hash_val];
165 44485170 : new_nodes[hash_val] = (owned) node;
166 : }
167 : }
168 42662484 : _nodes = (owned) new_nodes;
169 42662484 : _array_size = new_array_size;
170 : }
171 : }
172 :
173 : ~HashMap () {
174 16601621 : clear ();
175 : }
176 :
177 : [Compact]
178 38759698 : private class Node<K,V> {
179 : public K key;
180 : public V value;
181 38759698 : public Node<K,V> next;
182 : public uint key_hash;
183 :
184 38759710 : public Node (owned K k, owned V v, uint hash) {
185 38759710 : key = (owned) k;
186 38759710 : value = (owned) v;
187 38759710 : key_hash = hash;
188 : }
189 : }
190 :
191 4914533 : private class KeySet<K,V> : Set<K> {
192 : public HashMap<K,V> map {
193 9828792 : set { _map = value; }
194 : }
195 :
196 4913562 : private HashMap<K,V> _map;
197 :
198 14740686 : public KeySet (HashMap<K,V> map) {
199 4913562 : this.map = map;
200 : }
201 :
202 0 : public override Type get_element_type () {
203 0 : return typeof (K);
204 : }
205 :
206 4913562 : public override Iterator<K> iterator () {
207 4913562 : return new KeyIterator<K,V> (_map);
208 : }
209 :
210 : public override int size {
211 0 : get { return _map.size; }
212 : }
213 :
214 0 : public override bool add (K key) {
215 0 : assert_not_reached ();
216 : }
217 :
218 0 : public override void clear () {
219 0 : assert_not_reached ();
220 : }
221 :
222 0 : public override bool remove (K key) {
223 0 : assert_not_reached ();
224 : }
225 :
226 0 : public override bool contains (K key) {
227 0 : return _map.contains (key);
228 : }
229 : }
230 :
231 3200 : private class MapIterator<K,V> : Vala.MapIterator<K, V> {
232 : public HashMap<K,V> map {
233 1662 : set {
234 3324 : _map = value;
235 1662 : _stamp = _map._stamp;
236 : }
237 : }
238 :
239 1662 : private HashMap<K,V> _map;
240 1662 : private int _index = -1;
241 : private weak Node<K,V> _node;
242 :
243 : // concurrent modification protection
244 : private int _stamp;
245 :
246 4986 : public MapIterator (HashMap<K,V> map) {
247 1662 : this.map = map;
248 : }
249 :
250 1666 : public override bool next () {
251 1666 : if (_node != null) {
252 4 : _node = _node.next;
253 : }
254 19948 : while (_node == null && _index + 1 < _map._array_size) {
255 18282 : _index++;
256 18282 : _node = _map._nodes[_index];
257 : }
258 1666 : return (_node != null);
259 : }
260 :
261 4 : public override K get_key () {
262 4 : assert (_stamp == _map._stamp);
263 4 : assert (_node != null);
264 4 : return _node.key;
265 : }
266 :
267 3 : public override V get_value () {
268 3 : assert (_stamp == _map._stamp);
269 3 : assert (_node != null);
270 3 : return _node.value;
271 : }
272 : }
273 :
274 4914533 : private class KeyIterator<K,V> : Iterator<K> {
275 : public HashMap<K,V> map {
276 4913562 : set {
277 9827124 : _map = value;
278 4913562 : _stamp = _map._stamp;
279 : }
280 : }
281 :
282 4913562 : private HashMap<K,V> _map;
283 4913562 : private int _index = -1;
284 : private weak Node<K,V> _node;
285 : private weak Node<K,V> _next;
286 :
287 : // concurrent modification protection
288 : private int _stamp;
289 :
290 14740686 : public KeyIterator (HashMap<K,V> map) {
291 4913562 : this.map = map;
292 : }
293 :
294 11800312 : public override bool next () {
295 11800312 : assert (_stamp == _map._stamp);
296 11800312 : if (!has_next ()) {
297 11800312 : return false;
298 : }
299 6894188 : _node = _next;
300 6894188 : _next = null;
301 6894188 : return (_node != null);
302 : }
303 :
304 11800312 : public override bool has_next () {
305 11800312 : assert (_stamp == _map._stamp);
306 11800312 : if (_next == null) {
307 11800312 : _next = _node;
308 11800312 : if (_next != null) {
309 6886750 : _next = _next.next;
310 : }
311 65808300 : while (_next == null && _index + 1 < _map._array_size) {
312 54007988 : _index++;
313 54007988 : _next = _map._nodes[_index];
314 : }
315 : }
316 11800312 : return (_next != null);
317 : }
318 :
319 6894188 : public override K? get () {
320 6894188 : assert (_stamp == _map._stamp);
321 6894188 : assert (_node != null);
322 6894188 : return _node.key;
323 : }
324 :
325 0 : public override void remove () {
326 0 : assert_not_reached ();
327 : }
328 :
329 : public override bool valid {
330 0 : get {
331 0 : return _node != null;
332 : }
333 : }
334 : }
335 :
336 6 : private class ValueCollection<K,V> : Collection<V> {
337 : public HashMap<K,V> map {
338 6 : set { _map = value; }
339 : }
340 :
341 3 : private HashMap<K,V> _map;
342 :
343 9 : public ValueCollection (HashMap<K,V> map) {
344 3 : this.map = map;
345 : }
346 :
347 0 : public override Type get_element_type () {
348 0 : return typeof (V);
349 : }
350 :
351 3 : public override Iterator<V> iterator () {
352 3 : return new ValueIterator<K,V> (_map);
353 : }
354 :
355 : public override int size {
356 0 : get { return _map.size; }
357 : }
358 :
359 0 : public override bool add (V value) {
360 0 : assert_not_reached ();
361 : }
362 :
363 0 : public override void clear () {
364 0 : assert_not_reached ();
365 : }
366 :
367 0 : public override bool remove (V value) {
368 0 : assert_not_reached ();
369 : }
370 :
371 0 : public override bool contains (V value) {
372 0 : Iterator<V> it = iterator ();
373 0 : while (it.next ()) {
374 0 : if (_map._value_equal_func (it.get (), value)) {
375 0 : return true;
376 : }
377 : }
378 0 : return false;
379 : }
380 : }
381 :
382 6 : private class ValueIterator<K,V> : Iterator<V> {
383 : public HashMap<K,V> map {
384 3 : set {
385 6 : _map = value;
386 3 : _stamp = _map._stamp;
387 : }
388 : }
389 :
390 3 : private HashMap<K,V> _map;
391 3 : private int _index = -1;
392 : private weak Node<K,V> _node;
393 : private weak Node<K,V> _next;
394 :
395 : // concurrent modification protection
396 : private int _stamp;
397 :
398 9 : public ValueIterator (HashMap<K,V> map) {
399 3 : this.map = map;
400 : }
401 :
402 61 : public override bool next () {
403 61 : assert (_stamp == _map._stamp);
404 61 : if (!has_next ()) {
405 61 : return false;
406 : }
407 58 : _node = _next;
408 58 : _next = null;
409 58 : return (_node != null);
410 : }
411 :
412 61 : public override bool has_next () {
413 61 : assert (_stamp == _map._stamp);
414 61 : if (_next == null) {
415 61 : _next = _node;
416 61 : if (_next != null) {
417 58 : _next = _next.next;
418 : }
419 120 : while (_next == null && _index + 1 < _map._array_size) {
420 59 : _index++;
421 59 : _next = _map._nodes[_index];
422 : }
423 : }
424 61 : return (_next != null);
425 : }
426 :
427 58 : public override V? get () {
428 58 : assert (_stamp == _map._stamp);
429 58 : assert (_node != null);
430 58 : return _node.value;
431 : }
432 :
433 0 : public override void remove () {
434 0 : assert_not_reached ();
435 : }
436 :
437 : public override bool valid {
438 0 : get {
439 0 : return _node != null;
440 : }
441 : }
442 : }
443 : }
444 :
|