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                 private weak Node<K,V> _next;
 286
 287                 // concurrent modification protection
 288                 private int _stamp;
 289
 290                 public KeyIterator (HashMap map) {
 291                         this.map = map;
 292                 }
 293
 294                 public override bool next () {
 295                         assert (_stamp == _map._stamp);
 296                         if (!has_next ()) {
 297                                 return false;
 298                         }
 299                         _node = _next;
 300                         _next = null;
 301                         return (_node != null);
 302                 }
 303
 304                 public override bool has_next () {
 305                         assert (_stamp == _map._stamp);
 306                         if (_next == null) {
 307                                 _next = _node;
 308                                 if (_next != null) {
 309                                         _next = _next.next;
 310                                 }
 311                                 while (_next == null && _index + 1 < _map._array_size) {
 312                                         _index++;
 313                                         _next = _map._nodes[_index];
 314                                 }
 315                         }
 316                         return (_next != null);
 317                 }
 318
 319                 public override K? get () {
 320                         assert (_stamp == _map._stamp);
 321                         assert (_node != null);
 322                         return _node.key;
 323                 }
 324
 325                 public override void remove () {
 326                         assert_not_reached ();
 327                 }
 328
 329                 public override bool valid {
 330                         get {
 331                                 return _node != null;
 332                         }
 333                 }
 334         }
 335
 336         private class ValueCollection<K,V> : Collection<V> {
 337                 public HashMap<K,V> map {
 338                         set { _map = value; }
 339                 }
 340
 341                 private HashMap<K,V> _map;
 342
 343                 public ValueCollection (HashMap map) {
 344                         this.map = map;
 345                 }
 346
 347                 public override Type get_element_type () {
 348                         return typeof (V);
 349                 }
 350
 351                 public override Iterator<V> iterator () {
 352                         return new ValueIterator<K,V> (_map);
 353                 }
 354
 355                 public override int size {
 356                         get { return _map.size; }
 357                 }
 358
 359                 public override bool add (V value) {
 360                         assert_not_reached ();
 361                 }
 362
 363                 public override void clear () {
 364                         assert_not_reached ();
 365                 }
 366
 367                 public override bool remove (V value) {
 368                         assert_not_reached ();
 369                 }
 370
 371                 public override bool contains (V value) {
 372                         Iterator<V> it = iterator ();
 373                         while (it.next ()) {
 374                                 if (_map._value_equal_func (it.get (), value)) {
 375                                         return true;
 376                                 }
 377                         }
 378                         return false;
 379                 }
 380         }
 381
 382         private class ValueIterator<K,V> : Iterator<V> {
 383                 public HashMap<K,V> map {
 384                         set {
 385                                 _map = value;
 386                                 _stamp = _map._stamp;
 387                         }
 388                 }
 389
 390                 private HashMap<V,K> _map;
 391                 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                 public ValueIterator (HashMap map) {
 399                         this.map = map;
 400                 }
 401
 402                 public override bool next () {
 403                         assert (_stamp == _map._stamp);
 404                         if (!has_next ()) {
 405                                 return false;
 406                         }
 407                         _node = _next;
 408                         _next = null;
 409                         return (_node != null);
 410                 }
 411
 412                 public override bool has_next () {
 413                         assert (_stamp == _map._stamp);
 414                         if (_next == null) {
 415                                 _next = _node;
 416                                 if (_next != null) {
 417                                         _next = _next.next;
 418                                 }
 419                                 while (_next == null && _index + 1 < _map._array_size) {
 420                                         _index++;
 421                                         _next = _map._nodes[_index];
 422                                 }
 423                         }
 424                         return (_next != null);
 425                 }
 426
 427                 public override V? get () {
 428                         assert (_stamp == _map._stamp);
 429                         assert (_node != null);
 430                         return _node.value;
 431                 }
 432
 433                 public override void remove () {
 434                         assert_not_reached ();
 435                 }
 436
 437                 public override bool valid {
 438                         get {
 439                                 return _node != null;
 440                         }
 441                 }
 442         }
 443 }
 444