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  * Hash table implementation of the {@link Map} interface.
  29  *
  30  * This implementation is better fit for highly heterogenous key values.
  31  * In case of high key hashes redundancy or higher amount of data prefer using
  32  * tree implementation like {@link TreeMap}.
  33  *
  34  * @see TreeMap
  35  */
  36 public class Gee.HashMap<K,V> : Gee.AbstractMap<K,V> {
  37         /**
  38          * {@inheritDoc}
  39          */
  40         public override int size {
  41                 get { return _nnodes; }
  42         }
  43
  44         /**
  45          * {@inheritDoc}
  46          */
  47         public override bool read_only {
  48                 get { return false; }
  49         }
  50
  51         /**
  52          * {@inheritDoc}
  53          */
  54         public override Set<K> keys {
  55                 owned get {
  56                         Set<K> keys = _keys;
  57                         if (_keys == null) {
  58                                 keys = new KeySet<K,V> (this);
  59                                 _keys = keys;
  60                                 keys.add_weak_pointer ((void**) (&_keys));
  61                         }
  62                         return keys;
  63                 }
  64         }
  65
  66         /**
  67          * {@inheritDoc}
  68          */
  69         public override Collection<V> values {
  70                 owned get {
  71                         Collection<K> values = _values;
  72                         if (_values == null) {
  73                                 values = new ValueCollection<K,V> (this);
  74                                 _values = values;
  75                                 values.add_weak_pointer ((void**) (&_values));
  76                         }
  77                         return values;
  78                 }
  79         }
  80
  81         /**
  82          * {@inheritDoc}
  83          */
  84         public override Set<Map.Entry<K,V>> entries {
  85                 owned get {
  86                         Set<Map.Entry<K,V>> entries = _entries;
  87                         if (_entries == null) {
  88                                 entries = new EntrySet<K,V> (this);
  89                                 _entries = entries;
  90                                 entries.add_weak_pointer ((void**) (&_entries));
  91                         }
  92                         return entries;
  93                 }
  94         }
  95
  96         /**
  97          * The keys' hash function.
  98          */
  99         [CCode (notify = false)]
 100         public HashDataFunc<K> key_hash_func { private set; get; }
 101
 102         /**
 103          * The keys' equality testing function.
 104          */
 105         [CCode (notify = false)]
 106         public EqualDataFunc<K> key_equal_func { private set; get; }
 107
 108         /**
 109          * The values' equality testing function.
 110          */
 111         [CCode (notify = false)]
 112         public EqualDataFunc<V> value_equal_func { private set; get; }
 113
 114         private int _array_size;
 115         private int _nnodes;
 116         private Node<K,V>[] _nodes;
 117
 118         private weak Set<K> _keys;
 119         private weak Collection<V> _values;
 120         private weak Set<Map.Entry<K,V>> _entries;
 121
 122         // concurrent modification protection
 123         private int _stamp = 0;
 124
 125         private const int MIN_SIZE = 11;
 126         private const int MAX_SIZE = 13845163;
 127
 128         /**
 129          * Constructs a new, empty hash map.
 130          *
 131          * If not provided, the functions parameters are requested to the
 132          * {@link Functions} function factory methods.
 133          *
 134          * @param key_hash_func an optional key hash function
 135          * @param key_equal_func an optional key equality testing function
 136          * @param value_equal_func an optional value equality testing function
 137          */
 138         public HashMap (owned HashDataFunc<K>? key_hash_func = null, owned EqualDataFunc<K>? key_equal_func = null, owned EqualDataFunc<V>? value_equal_func = null) {
 139                 if (key_hash_func == null) {
 140                         key_hash_func = Functions.get_hash_func_for (typeof (K));
 141                 }
 142                 if (key_equal_func == null) {
 143                         key_equal_func = Functions.get_equal_func_for (typeof (K));
 144                 }
 145                 if (value_equal_func == null) {
 146                         value_equal_func = Functions.get_equal_func_for (typeof (V));
 147                 }
 148                 this.key_hash_func = key_hash_func;
 149                 this.key_equal_func = key_equal_func;
 150                 this.value_equal_func = value_equal_func;
 151
 152                 _array_size = MIN_SIZE;
 153                 _nodes = new Node<K,V>[_array_size];
 154         }
 155
 156         private Node<K,V>** lookup_node (K key) {
 157                 uint hash_value = key_hash_func (key);
 158                 Node<K,V>** node = &_nodes[hash_value % _array_size];
 159                 while ((*node) != null && (hash_value != (*node)->key_hash || !key_equal_func ((*node)->key, key))) {
 160                         node = &((*node)->next);
 161                 }
 162                 return node;
 163         }
 164
 165         /**
 166          * {@inheritDoc}
 167          */
 168         public override bool has_key (K key) {
 169                 Node<K,V>** node = lookup_node (key);
 170                 return (*node != null);
 171         }
 172
 173         /**
 174          * {@inheritDoc}
 175          */
 176         public override bool has (K key, V value) {
 177                 Node<K,V>** node = lookup_node (key);
 178                 return (*node != null && value_equal_func ((*node)->value, value));
 179         }
 180
 181         /**
 182          * {@inheritDoc}
 183          */
 184         public override V? get (K key) {
 185                 Node<K,V>* node = (*lookup_node (key));
 186                 if (node != null) {
 187                         return node->value;
 188                 } else {
 189                         return null;
 190                 }
 191         }
 192
 193         /**
 194          * {@inheritDoc}
 195          */
 196         public override void set (K key, V value) {
 197                 Node<K,V>** node = lookup_node (key);
 198                 if (*node != null) {
 199                         (*node)->value = value;
 200                 } else {
 201                         uint hash_value = key_hash_func (key);
 202                         *node = new Node<K,V> (key, value, hash_value);
 203                         _nnodes++;
 204                         resize ();
 205                 }
 206                 _stamp++;
 207         }
 208
 209         /**
 210          * {@inheritDoc}
 211          */
 212         public override bool unset (K key, out V? value = null) {
 213                 bool b = unset_helper (key, out value);
 214                 if(b) {
 215                         resize();
 216                 }
 217                 return b;
 218         }
 219
 220         /**
 221          * {@inheritDoc}
 222          */
 223         public override void clear () {
 224                 for (int i = 0; i < _array_size; i++) {
 225                         Node<K,V> node = (owned) _nodes[i];
 226                         while (node != null) {
 227                                 Node next = (owned) node.next;
 228                                 node.key = null;
 229                                 node.value = null;
 230                                 node = (owned) next;
 231                         }
 232                 }
 233                 _nnodes = 0;
 234                 resize ();
 235         }
 236
 237         /**
 238          * {@inheritDoc}
 239          */
 240         public override Gee.MapIterator<K,V> map_iterator () {
 241                 return new MapIterator<K,V> (this);
 242         }
 243
 244         private inline bool unset_helper (K key, out V? value = null) {
 245                 Node<K,V>** node = lookup_node (key);
 246                 if (*node != null) {
 247                         Node<K,V> next = (owned) (*node)->next;
 248
 249                         value = (owned) (*node)->value;
 250
 251                         (*node)->key = null;
 252                         (*node)->value = null;
 253                         delete *node;
 254
 255                         *node = (owned) next;
 256
 257                         _nnodes--;
 258                         _stamp++;
 259                         return true;
 260                 } else {
 261                         value = null;
 262                 }
 263                 return false;
 264         }
 265
 266         private inline void resize () {
 267                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 268                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 269                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 270                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 271
 272                         Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
 273
 274                         for (int i = 0; i < _array_size; i++) {
 275                                 Node<K,V> node;
 276                                 Node<K,V> next = null;
 277                                 for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
 278                                         next = (owned) node.next;
 279                                         uint hash_val = node.key_hash % new_array_size;
 280                                         node.next = (owned) new_nodes[hash_val];
 281                                         new_nodes[hash_val] = (owned) node;
 282                                 }
 283                         }
 284                         _nodes = (owned) new_nodes;
 285                         _array_size = new_array_size;
 286                 }
 287         }
 288
 289         ~HashSet () {
 290                 clear ();
 291         }
 292
 293         [Compact]
 294         private class Node<K,V> {
 295                 public K key;
 296                 public V value;
 297                 public Node<K,V> next;
 298                 public uint key_hash;
 299                 public unowned Map.Entry<K,V>? entry;
 300
 301                 public Node (owned K k, owned V v, uint hash) {
 302                         key = (owned) k;
 303                         value = (owned) v;
 304                         key_hash = hash;
 305                          entry = null;
 306                 }
 307         }
 308
 309         private class Entry<K,V> : Map.Entry<K,V> {
 310                 private unowned Node<K,V> _node;
 311
 312                 public static Map.Entry<K,V> entry_for<K,V> (Node<K,V> node) {
 313                         Map.Entry<K,V> result = node.entry;
 314                         if (node.entry == null) {
 315                                 result = new Entry<K,V> (node);
 316                                 node.entry = result;
 317                                 result.add_weak_pointer ((void**) (&node.entry));
 318                         }
 319                         return result;
 320                 }
 321
 322                 public Entry (Node<K,V> node) {
 323                         _node = node;
 324                 }
 325
 326                 public override K key { get { return _node.key; } }
 327
 328                 public override V value {
 329                         get { return _node.value; }
 330                         set { _node.value = value; }
 331                 }
 332
 333                 public override bool read_only { get { return false; } }
 334         }
 335
 336         private class KeySet<K,V> : AbstractSet<K> {
 337                 private HashMap<K,V> _map;
 338
 339                 public KeySet (HashMap map) {
 340                         _map = map;
 341                 }
 342
 343                 public override Iterator<K> iterator () {
 344                         return new KeyIterator<K,V> (_map);
 345                 }
 346
 347                 public override int size {
 348                         get { return _map.size; }
 349                 }
 350
 351                 public override bool read_only {
 352                         get { return true; }
 353                 }
 354
 355                 public override bool add (K key) {
 356                         assert_not_reached ();
 357                 }
 358
 359                 public override void clear () {
 360                         assert_not_reached ();
 361                 }
 362
 363                 public override bool remove (K key) {
 364                         assert_not_reached ();
 365                 }
 366
 367                 public override bool contains (K key) {
 368                         return _map.has_key (key);
 369                 }
 370
 371                 public bool add_all (Collection<K> collection) {
 372                         assert_not_reached ();
 373                 }
 374
 375                 public bool remove_all (Collection<K> collection) {
 376                         assert_not_reached ();
 377                 }
 378
 379                 public bool retain_all (Collection<K> collection) {
 380                         assert_not_reached ();
 381                 }
 382
 383         }
 384
 385         private class ValueCollection<K,V> : AbstractCollection<V> {
 386                 private HashMap<K,V> _map;
 387
 388                 public ValueCollection (HashMap map) {
 389                         _map = map;
 390                 }
 391
 392                 public override Iterator<V> iterator () {
 393                         return new ValueIterator<K,V> (_map);
 394                 }
 395
 396                 public override int size {
 397                         get { return _map.size; }
 398                 }
 399
 400                 public override bool read_only {
 401                         get { return true; }
 402                 }
 403
 404                 public override bool add (V value) {
 405                         assert_not_reached ();
 406                 }
 407
 408                 public override void clear () {
 409                         assert_not_reached ();
 410                 }
 411
 412                 public override bool remove (V value) {
 413                         assert_not_reached ();
 414                 }
 415
 416                 public override bool contains (V value) {
 417                         Iterator<V> it = iterator ();
 418                         while (it.next ()) {
 419                                 if (_map.value_equal_func (it.get (), value)) {
 420                                         return true;
 421                                 }
 422                         }
 423                         return false;
 424                 }
 425
 426                 public bool add_all (Collection<V> collection) {
 427                         assert_not_reached ();
 428                 }
 429
 430                 public bool remove_all (Collection<V> collection) {
 431                         assert_not_reached ();
 432                 }
 433
 434                 public bool retain_all (Collection<V> collection) {
 435                         assert_not_reached ();
 436                 }
 437         }
 438
 439         private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
 440                 private HashMap<K,V> _map;
 441
 442                 public EntrySet (HashMap<K,V> map) {
 443                         _map = map;
 444                 }
 445
 446                 public override Iterator<Map.Entry<K, V>> iterator () {
 447                         return new EntryIterator<K,V> (_map);
 448                 }
 449
 450                 public override int size {
 451                         get { return _map.size; }
 452                 }
 453
 454                 public override bool read_only {
 455                         get { return true; }
 456                 }
 457
 458                 public override bool add (Map.Entry<K, V> entry) {
 459                         assert_not_reached ();
 460                 }
 461
 462                 public override void clear () {
 463                         assert_not_reached ();
 464                 }
 465
 466                 public override bool remove (Map.Entry<K, V> entry) {
 467                         assert_not_reached ();
 468                 }
 469
 470                 public override bool contains (Map.Entry<K, V> entry) {
 471                         return _map.has (entry.key, entry.value);
 472                 }
 473
 474                 public bool add_all (Collection<Map.Entry<K, V>> entries) {
 475                         assert_not_reached ();
 476                 }
 477
 478                 public bool remove_all (Collection<Map.Entry<K, V>> entries) {
 479                         assert_not_reached ();
 480                 }
 481
 482                 public bool retain_all (Collection<Map.Entry<K, V>> entries) {
 483                         assert_not_reached ();
 484                 }
 485         }
 486
 487         private abstract class NodeIterator<K,V> : Object {
 488                 protected HashMap<K,V> _map;
 489                 protected int _index = -1;
 490                 protected weak Node<K,V> _node;
 491                 protected weak Node<K,V> _next;
 492
 493                 // concurrent modification protection
 494                 protected int _stamp;
 495
 496                 public NodeIterator (HashMap map) {
 497                         _map = map;
 498                         _stamp = _map._stamp;
 499                 }
 500
 501                 public bool next () {
 502                         assert (_stamp == _map._stamp);
 503                         if (!has_next ()) {
 504                                 return false;
 505                         }
 506                         _node = _next;
 507                         _next = null;
 508                         return (_node != null);
 509                 }
 510
 511                 public bool has_next () {
 512                         assert (_stamp == _map._stamp);
 513                         if (_next == null) {
 514                                 _next = _node;
 515                                 if (_next != null) {
 516                                         _next = _next.next;
 517                                 }
 518                                 while (_next == null && _index + 1 < _map._array_size) {
 519                                         _index++;
 520                                         _next = _map._nodes[_index];
 521                                 }
 522                         }
 523                         return (_next != null);
 524                 }
 525
 526                 public virtual bool read_only {
 527                         get {
 528                                 return true;
 529                         }
 530                 }
 531
 532                 public bool valid {
 533                         get {
 534                                 return _node != null;
 535                         }
 536                 }
 537         }
 538
 539         private class KeyIterator<K,V> : NodeIterator<K,V>, Traversable<K>, Iterator<K> {
 540                 public KeyIterator (HashMap map) {
 541                         base (map);
 542                 }
 543
 544                 public new K get () {
 545                         assert (_stamp == _map._stamp);
 546                         assert (_node != null);
 547                         return _node.key;
 548                 }
 549
 550                 public void remove () {
 551                         assert_not_reached ();
 552                 }
 553
 554                 public bool foreach(ForallFunc<K> f) {
 555                         if (_node != null) {
 556                                 if (!f(_node.key)) {
 557                                         return false;
 558                                 }
 559                                 if(_next == null) {
 560                                         _next = _node.next;
 561                                 }
 562                         }
 563                         do {
 564                                 while(_next != null) {
 565                                         _node = _next;
 566                                         if (!f(_node.key)) {
 567                                                 return false;
 568                                         }
 569                                         _next = _next.next;
 570                                 }
 571                                 if (_index + 1 < _map._array_size) {
 572                                         _next = _map._nodes[++_index];
 573                                 } else {
 574                                         return true;
 575                                 }
 576                         } while(true);
 577                 }
 578         }
 579
 580         private class MapIterator<K,V> : NodeIterator<K,V>, Gee.MapIterator<K,V> {
 581                 public MapIterator (HashMap map) {
 582                         base (map);
 583                 }
 584
 585                 public new K get_key () {
 586                         assert (_stamp == _map._stamp);
 587                         assert (_node != null);
 588                         return _node.key;
 589                 }
 590
 591                 public void unset () {
 592                         assert (_stamp == _map._stamp);
 593                         assert (_node != null);
 594                         has_next ();
 595                         _map.unset_helper (_node.key);
 596                         _node = null;
 597                         _stamp = _map._stamp;
 598                 }
 599
 600                 public V get_value () {
 601                         assert (_stamp == _map._stamp);
 602                         assert (_node != null);
 603                         return _node.value;
 604                 }
 605
 606                 public void set_value (V value) {
 607                         assert (_stamp == _map._stamp);
 608                         assert (_node != null);
 609                         _map.set (_node.key, value);
 610                         _stamp = _map._stamp;
 611                 }
 612
 613                 public bool mutable {
 614                         get {
 615                                 return true;
 616                         }
 617                 }
 618
 619                 public override bool read_only {
 620                         get {
 621                                 return false;
 622                         }
 623                 }
 624         }
 625
 626         private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Iterator<V> {
 627                 public ValueIterator (HashMap map) {
 628                         base (map);
 629                 }
 630
 631                 public new V get () {
 632                         assert (_stamp == _map._stamp);
 633                         assert (_node != null);
 634                         return _node.value;
 635                 }
 636
 637                 public void remove () {
 638                         assert_not_reached ();
 639                 }
 640
 641                 public bool foreach(ForallFunc<V> f) {
 642                         if (_node != null) {
 643                                 if (!f(_node.value)) {
 644                                         return false;
 645                                 }
 646                                 if(_next == null) {
 647                                         _next = _node.next;
 648                                 }
 649                         }
 650                         do {
 651                                 while(_next != null) {
 652                                         _node = _next;
 653                                         if (!f(_node.value)) {
 654                                                 return false;
 655                                         }
 656                                         _next = _next.next;
 657                                 }
 658                                 if (_index + 1 < _map._array_size) {
 659                                         _next = _map._nodes[++_index];
 660                                 } else {
 661                                         return true;
 662                                 }
 663                         } while(true);
 664                 }
 665         }
 666
 667         private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
 668                 public EntryIterator (HashMap map) {
 669                         base (map);
 670                 }
 671
 672                 public new Map.Entry<K,V> get () {
 673                         assert (_stamp == _map._stamp);
 674                         assert (_node != null);
 675                         return Entry<K,V>.entry_for<K,V> (_node);
 676                 }
 677
 678                 public void remove () {
 679                         assert_not_reached ();
 680                 }
 681
 682                 public bool foreach(ForallFunc<Map.Entry<K,V>> f) {
 683                         if (_node != null) {
 684                                 if (!f(Entry<K,V>.entry_for<K,V> (_node))) {
 685                                         return false;
 686                                 }
 687                                 if(_next == null) {
 688                                         _next = _node.next;
 689                                 }
 690                         }
 691                         do {
 692                                 while(_next != null) {
 693                                         _node = _next;
 694                                         if (!f(Entry<K,V>.entry_for<K,V> (_node))) {
 695                                                 return false;
 696                                         }
 697                                         _next = _next.next;
 698                                 }
 699                                 if (_index + 1 < _map._array_size) {
 700                                         _next = _map._nodes[++_index];
 701                                 } else {
 702                                         return true;
 703                                 }
 704                         } while(true);
 705                 }
 706         }
 707 }
 708