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<K> key_hash_func {
  36                 set { _key_hash_func = value; }
  37         }
  38
  39         public EqualFunc<K> key_equal_func {
  40                 set { _key_equal_func = value; }
  41         }
  42
  43         public EqualFunc<V> 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<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         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                 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         public override Vala.MapIterator<K,V> map_iterator () {
  78                 return new MapIterator<K,V> (this);
  79         }
  80
  81         private Node<K,V>** lookup_node (K key) {
  82                 uint hash_value = _key_hash_func (key);
  83                 Node<K,V>** node = &_nodes[hash_value % _array_size];
  84                 while ((*node) != null && (hash_value != (*node)->key_hash || !_key_equal_func ((*node)->key, key))) {
  85                         node = &((*node)->next);
  86                 }
  87                 return node;
  88         }
  89
  90         public override bool contains (K key) {
  91                 Node<K,V>** node = lookup_node (key);
  92                 return (*node != null);
  93         }
  94
  95         public override V? get (K key) {
  96                 Node<K,V>* node = (*lookup_node (key));
  97                 if (node != null) {
  98                         return node->value;
  99                 } else {
 100                         return null;
 101                 }
 102         }
 103
 104         public override void set (K key, V value) {
 105                 Node<K,V>** node = lookup_node (key);
 106                 if (*node != null) {
 107                         (*node)->value = value;
 108                 } else {
 109                         uint hash_value = _key_hash_func (key);
 110                         *node = new Node<K,V> (key, value, hash_value);
 111                         _nnodes++;
 112                         resize ();
 113                 }
 114                 _stamp++;
 115         }
 116
 117         public override bool remove (K key) {
 118                 Node<K,V>** node = lookup_node (key);
 119                 if (*node != null) {
 120                         Node<K,V> next = (owned) (*node)->next;
 121
 122                         (*node)->key = null;
 123                         (*node)->value = null;
 124                         delete *node;
 125
 126                         *node = (owned) next;
 127
 128                         _nnodes--;
 129                         resize ();
 130                         _stamp++;
 131                         return true;
 132                 }
 133                 return false;
 134         }
 135
 136         public override void clear () {
 137                 for (int i = 0; i < _array_size; i++) {
 138                         Node<K,V> node = (owned) _nodes[i];
 139                         while (node != null) {
 140                                 Node next = (owned) node.next;
 141                                 node.key = null;
 142                                 node.value = null;
 143                                 node = (owned) next;
 144                         }
 145                 }
 146                 _nnodes = 0;
 147                 resize ();
 148         }
 149
 150         private void resize () {
 151                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 152                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 153                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 154                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 155
 156                         Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
 157
 158                         for (int i = 0; i < _array_size; i++) {
 159                                 Node<K,V> node;
 160                                 Node<K,V> next = null;
 161                                 for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
 162                                         next = (owned) node.next;
 163                                         uint hash_val = node.key_hash % new_array_size;
 164                                         node.next = (owned) new_nodes[hash_val];
 165                                         new_nodes[hash_val] = (owned) node;
 166                                 }
 167                         }
 168                         _nodes = (owned) new_nodes;
 169                         _array_size = new_array_size;
 170                 }
 171         }
 172
 173         ~HashMap () {
 174                 clear ();
 175         }
 176
 177         [Compact]
 178         private class Node<K,V> {
 179                 public K key;
 180                 public V value;
 181                 public Node<K,V> next;
 182                 public uint key_hash;
 183
 184                 public Node (owned K k, owned V v, uint hash) {
 185                         key = (owned) k;
 186                         value = (owned) v;
 187                         key_hash = hash;
 188                 }
 189         }
 190
 191         private class KeySet<K,V> : Set<K> {
 192                 public HashMap<K,V> map {
 193                         set { _map = value; }
 194                 }
 195
 196                 private HashMap<K,V> _map;
 197
 198                 public KeySet (HashMap map) {
 199                         this.map = map;
 200                 }
 201
 202                 public override Type get_element_type () {
 203                         return typeof (K);
 204                 }
 205
 206                 public override Iterator<K> iterator () {
 207                         return new KeyIterator<K,V> (_map);
 208                 }
 209
 210                 public override int size {
 211                         get { return _map.size; }
 212                 }
 213
 214                 public override bool add (K key) {
 215                         assert_not_reached ();
 216                 }
 217
 218                 public override void clear () {
 219                         assert_not_reached ();
 220                 }
 221
 222                 public override bool remove (K key) {
 223                         assert_not_reached ();
 224                 }
 225
 226                 public override bool contains (K key) {
 227                         return _map.contains (key);
 228                 }
 229         }
 230
 231         private class MapIterator<K,V> : Vala.MapIterator<K, V> {
 232                 public HashMap<K,V> map {
 233                         set {
 234                                 _map = value;
 235                                 _stamp = _map._stamp;
 236                         }
 237                 }
 238
 239                 private HashMap<K,V> _map;
 240                 private int _index = -1;
 241                 private weak Node<K,V> _node;
 242
 243                 // concurrent modification protection
 244                 private int _stamp;
 245
 246                 public MapIterator (HashMap map) {
 247                         this.map = map;
 248                 }
 249
 250                 public override bool next () {
 251                         if (_node != null) {
 252                                 _node = _node.next;
 253                         }
 254                         while (_node == null && _index + 1 < _map._array_size) {
 255                                 _index++;
 256                                 _node = _map._nodes[_index];
 257                         }
 258                         return (_node != null);
 259                 }
 260
 261                 public override K? get_key () {
 262                         assert (_stamp == _map._stamp);
 263                         assert (_node != null);
 264                         return _node.key;
 265                 }
 266
 267                 public override V? get_value () {
 268                         assert (_stamp == _map._stamp);
 269                         assert (_node != null);
 270                         return _node.value;
 271                 }
 272         }
 273
 274         private class KeyIterator<K,V> : Iterator<K> {
 275                 public HashMap<K,V> map {
 276                         set {
 277                                 _map = value;
 278                                 _stamp = _map._stamp;
 279                         }
 280                 }
 281
 282                 private HashMap<K,V> _map;
 283                 private int _index = -1;
 284                 private weak Node<K,V> _node;
 285
 286                 // concurrent modification protection
 287                 private int _stamp;
 288
 289                 public KeyIterator (HashMap map) {
 290                         this.map = map;
 291                 }
 292
 293                 public override bool next () {
 294                         if (_node != null) {
 295                                 _node = _node.next;
 296                         }
 297                         while (_node == null && _index + 1 < _map._array_size) {
 298                                 _index++;
 299                                 _node = _map._nodes[_index];
 300                         }
 301                         return (_node != null);
 302                 }
 303
 304                 public override K? get () {
 305                         assert (_stamp == _map._stamp);
 306                         assert (_node != null);
 307                         return _node.key;
 308                 }
 309         }
 310
 311         private class ValueCollection<K,V> : Collection<V> {
 312                 public HashMap<K,V> map {
 313                         set { _map = value; }
 314                 }
 315
 316                 private HashMap<K,V> _map;
 317
 318                 public ValueCollection (HashMap map) {
 319                         this.map = map;
 320                 }
 321
 322                 public override Type get_element_type () {
 323                         return typeof (V);
 324                 }
 325
 326                 public override Iterator<V> iterator () {
 327                         return new ValueIterator<K,V> (_map);
 328                 }
 329
 330                 public override int size {
 331                         get { return _map.size; }
 332                 }
 333
 334                 public override bool add (V value) {
 335                         assert_not_reached ();
 336                 }
 337
 338                 public override void clear () {
 339                         assert_not_reached ();
 340                 }
 341
 342                 public override bool remove (V value) {
 343                         assert_not_reached ();
 344                 }
 345
 346                 public override bool contains (V value) {
 347                         Iterator<V> it = iterator ();
 348                         while (it.next ()) {
 349                                 if (_map._value_equal_func (it.get (), value)) {
 350                                         return true;
 351                                 }
 352                         }
 353                         return false;
 354                 }
 355         }
 356
 357         private class ValueIterator<K,V> : Iterator<V> {
 358                 public HashMap<K,V> map {
 359                         set {
 360                                 _map = value;
 361                                 _stamp = _map._stamp;
 362                         }
 363                 }
 364
 365                 private HashMap<V,K> _map;
 366                 private int _index = -1;
 367                 private weak Node<K,V> _node;
 368
 369                 // concurrent modification protection
 370                 private int _stamp;
 371
 372                 public ValueIterator (HashMap map) {
 373                         this.map = map;
 374                 }
 375
 376                 public override bool next () {
 377                         if (_node != null) {
 378                                 _node = _node.next;
 379                         }
 380                         while (_node == null && _index + 1 < _map._array_size) {
 381                                 _index++;
 382                                 _node = _map._nodes[_index];
 383                         }
 384                         return (_node != null);
 385                 }
 386
 387                 public override V? get () {
 388                         assert (_stamp == _map._stamp);
 389                         assert (_node != null);
 390                         return _node.value;
 391                 }
 392         }
 393 }
 394