gee/hashmap.vala

   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 public class Vala.HashMap<K,V> : Map<K,V> {
  31         public override int size {
  32                 get { return _nnodes; }
  33         }
  34
  35         public HashFunc key_hash_func {
  36                 set { _key_hash_func = value; }
  37         }
  38
  39         public EqualFunc key_equal_func {
  40                 set { _key_equal_func = value; }
  41         }
  42
  43         public EqualFunc value_equal_func {
  44                 set { _value_equal_func = value; }
  45         }
  46
  47         private int _array_size;
  48         private int _nnodes;
  49         private Node<K,V>[] _nodes;
  50
  51         // concurrent modification protection
  52         private int _stamp = 0;
  53
  54         private HashFunc _key_hash_func;
  55         private EqualFunc _key_equal_func;
  56         private EqualFunc _value_equal_func;
  57
  58         private const int MIN_SIZE = 11;
  59         private const int MAX_SIZE = 13845163;
  60
  61         public HashMap (HashFunc key_hash_func = GLib.direct_hash, EqualFunc key_equal_func = GLib.direct_equal, EqualFunc value_equal_func = GLib.direct_equal) {
  62                 this.key_hash_func = key_hash_func;
  63                 this.key_equal_func = key_equal_func;
  64                 this.value_equal_func = value_equal_func;
  65                 _array_size = MIN_SIZE;
  66                 _nodes = new Node<K,V>[_array_size];
  67         }
  68
  69         public override Set<K> get_keys () {
  70                 return new KeySet<K,V> (this);
  71         }
  72
  73         public override Collection<V> get_values () {
  74                 return new ValueCollection<K,V> (this);
  75         }
  76
  77         private Node<K,V>** lookup_node (K key) {
  78                 uint hash_value = _key_hash_func (key);
  79                 Node<K,V>** node = &_nodes[hash_value % _array_size];
  80                 while ((*node) != null && (hash_value != (*node)->key_hash || !_key_equal_func ((*node)->key, key))) {
  81                         node = &((*node)->next);
  82                 }
  83                 return node;
  84         }
  85
  86         public override bool contains (K key) {
  87                 Node<K,V>** node = lookup_node (key);
  88                 return (*node != null);
  89         }
  90
  91         public override V? get (K key) {
  92                 Node<K,V>* node = (*lookup_node (key));
  93                 if (node != null) {
  94                         return node->value;
  95                 } else {
  96                         return null;
  97                 }
  98         }
  99
 100         public override void set (K key, V value) {
 101                 Node<K,V>** node = lookup_node (key);
 102                 if (*node != null) {
 103                         (*node)->value = value;
 104                 } else {
 105                         uint hash_value = _key_hash_func (key);
 106                         *node = new Node<K,V> (key, value, hash_value);
 107                         _nnodes++;
 108                         resize ();
 109                 }
 110                 _stamp++;
 111         }
 112
 113         public override bool remove (K key) {
 114                 Node<K,V>** node = lookup_node (key);
 115                 if (*node != null) {
 116                         Node<K,V> next = (owned) (*node)->next;
 117
 118                         (*node)->key = null;
 119                         (*node)->value = null;
 120                         delete *node;
 121
 122                         *node = (owned) next;
 123
 124                         _nnodes--;
 125                         resize ();
 126                         _stamp++;
 127                         return true;
 128                 }
 129                 return false;
 130         }
 131
 132         public override void clear () {
 133                 for (int i = 0; i < _array_size; i++) {
 134                         Node<K,V> node = (owned) _nodes[i];
 135                         while (node != null) {
 136                                 Node next = (owned) node.next;
 137                                 node.key = null;
 138                                 node.value = null;
 139                                 node = (owned) next;
 140                         }
 141                 }
 142                 _nnodes = 0;
 143                 resize ();
 144         }
 145
 146         private void resize () {
 147                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 148                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 149                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 150                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 151
 152                         Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
 153
 154                         for (int i = 0; i < _array_size; i++) {
 155                                 Node<K,V> node;
 156                                 Node<K,V> next = null;
 157                                 for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
 158                                         next = (owned) node.next;
 159                                         uint hash_val = node.key_hash % new_array_size;
 160                                         node.next = (owned) new_nodes[hash_val];
 161                                         new_nodes[hash_val] = (owned) node;
 162                                 }
 163                         }
 164                         _nodes = (owned) new_nodes;
 165                         _array_size = new_array_size;
 166                 }
 167         }
 168
 169         ~HashSet () {
 170                 clear ();
 171         }
 172
 173         [Compact]
 174         private class Node<K,V> {
 175                 public K key;
 176                 public V value;
 177                 public Node<K,V> next;
 178                 public uint key_hash;
 179
 180                 public Node (owned K k, owned V v, uint hash) {
 181                         key = (owned) k;
 182                         value = (owned) v;
 183                         key_hash = hash;
 184                 }
 185         }
 186
 187         private class KeySet<K,V> : Set<K> {
 188                 public HashMap<K,V> map {
 189                         set { _map = value; }
 190                 }
 191
 192                 private HashMap<K,V> _map;
 193
 194                 public KeySet (HashMap map) {
 195                         this.map = map;
 196                 }
 197
 198                 public override Type get_element_type () {
 199                         return typeof (K);
 200                 }
 201
 202                 public override Iterator<K> iterator () {
 203                         return new KeyIterator<K,V> (_map);
 204                 }
 205
 206                 public override int size {
 207                         get { return _map.size; }
 208                 }
 209
 210                 public override bool add (K key) {
 211                         assert_not_reached ();
 212                 }
 213
 214                 public override void clear () {
 215                         assert_not_reached ();
 216                 }
 217
 218                 public override bool remove (K key) {
 219                         assert_not_reached ();
 220                 }
 221
 222                 public override bool contains (K key) {
 223                         return _map.contains (key);
 224                 }
 225         }
 226
 227         private class KeyIterator<K,V> : Iterator<K> {
 228                 public HashMap<K,V> map {
 229                         set {
 230                                 _map = value;
 231                                 _stamp = _map._stamp;
 232                         }
 233                 }
 234
 235                 private HashMap<K,V> _map;
 236                 private int _index = -1;
 237                 private weak Node<K,V> _node;
 238
 239                 // concurrent modification protection
 240                 private int _stamp;
 241
 242                 public KeyIterator (HashMap map) {
 243                         this.map = map;
 244                 }
 245
 246                 public override bool next () {
 247                         if (_node != null) {
 248                                 _node = _node.next;
 249                         }
 250                         while (_node == null && _index + 1 < _map._array_size) {
 251                                 _index++;
 252                                 _node = _map._nodes[_index];
 253                         }
 254                         return (_node != null);
 255                 }
 256
 257                 public override K? get () {
 258                         assert (_stamp == _map._stamp);
 259                         assert (_node != null);
 260                         return _node.key;
 261                 }
 262         }
 263
 264         private class ValueCollection<K,V> : Collection<V> {
 265                 public HashMap<K,V> map {
 266                         set { _map = value; }
 267                 }
 268
 269                 private HashMap<K,V> _map;
 270
 271                 public ValueCollection (HashMap map) {
 272                         this.map = map;
 273                 }
 274
 275                 public override Type get_element_type () {
 276                         return typeof (V);
 277                 }
 278
 279                 public override Iterator<V> iterator () {
 280                         return new ValueIterator<K,V> (_map);
 281                 }
 282
 283                 public override int size {
 284                         get { return _map.size; }
 285                 }
 286
 287                 public override bool add (V value) {
 288                         assert_not_reached ();
 289                 }
 290
 291                 public override void clear () {
 292                         assert_not_reached ();
 293                 }
 294
 295                 public override bool remove (V value) {
 296                         assert_not_reached ();
 297                 }
 298
 299                 public override bool contains (V value) {
 300                         Iterator<V> it = iterator ();
 301                         while (it.next ()) {
 302                                 if (_map._value_equal_func (it.get (), value)) {
 303                                         return true;
 304                                 }
 305                         }
 306                         return false;
 307                 }
 308         }
 309
 310         private class ValueIterator<K,V> : Iterator<V> {
 311                 public HashMap<K,V> map {
 312                         set {
 313                                 _map = value;
 314                                 _stamp = _map._stamp;
 315                         }
 316                 }
 317
 318                 private HashMap<V,K> _map;
 319                 private int _index = -1;
 320                 private weak Node<K,V> _node;
 321
 322                 // concurrent modification protection
 323                 private int _stamp;
 324
 325                 public ValueIterator (HashMap map) {
 326                         this.map = map;
 327                 }
 328
 329                 public override bool next () {
 330                         if (_node != null) {
 331                                 _node = _node.next;
 332                         }
 333                         while (_node == null && _index + 1 < _map._array_size) {
 334                                 _index++;
 335                                 _node = _map._nodes[_index];
 336                         }
 337                         return (_node != null);
 338                 }
 339
 340                 public override V? get () {
 341                         assert (_stamp == _map._stamp);
 342                         assert (_node != null);
 343                         return _node.value;
 344                 }
 345         }
 346 }
 347