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-2008  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 Gee.HashMap<K,V> : CollectionObject, Map<K,V> {
  31         public 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 Set<K> get_keys () {
  70                 return new KeySet<K,V> (this);
  71         }
  72
  73         public 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 bool contains (K key) {
  87                 Node<K,V>** node = lookup_node (key);
  88                 return (*node != null);
  89         }
  90
  91         public 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 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 bool remove (K key) {
 114                 Node<K,V>** node = lookup_node (key);
 115                 if (*node != null) {
 116                         (*node)->key = null;
 117                         (*node)->value = null;
 118                         *node = (*node)->next;
 119                         _nnodes--;
 120                         resize ();
 121                         _stamp++;
 122                         return true;
 123                 }
 124                 return false;
 125         }
 126
 127         public void clear () {
 128                 for (int i = 0; i < _array_size; i++) {
 129                         Node<K,V> node = #_nodes[i];
 130                         while (node != null) {
 131                                 Node next = #node.next;
 132                                 node.key = null;
 133                                 node.value = null;
 134                                 node = #next;
 135                         }
 136                 }
 137                 _nnodes = 0;
 138                 resize ();
 139         }
 140
 141         private void resize () {
 142                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 143                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 144                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 145                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 146
 147                         Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
 148
 149                         for (int i = 0; i < _array_size; i++) {
 150                                 Node<K,V> node;
 151                                 Node<K,V> next;
 152                                 for (node = #_nodes[i]; node != null; node = #next) {
 153                                         next = #node.next;
 154                                         uint hash_val = node.key_hash % new_array_size;
 155                                         node.next = #new_nodes[hash_val];
 156                                         new_nodes[hash_val] = #node;
 157                                 }
 158                         }
 159                         _nodes = #new_nodes;
 160                         _array_size = new_array_size;
 161                 }
 162         }
 163
 164         ~HashSet () {
 165                 clear ();
 166         }
 167
 168         [Compact]
 169         private class Node<K,V> {
 170                 public K key;
 171                 public V value;
 172                 public Node<K,V> next;
 173                 public uint key_hash;
 174
 175                 public Node (K# k, V# v, uint hash) {
 176                         key = #k;
 177                         value = #v;
 178                         key_hash = hash;
 179                 }
 180         }
 181
 182         private class KeySet<K,V> : CollectionObject, Iterable<K>, Collection<K>, Set<K> {
 183                 public HashMap<K,V> map {
 184                         set { _map = value; }
 185                 }
 186
 187                 private HashMap<K,V> _map;
 188
 189                 public KeySet (HashMap map) {
 190                         this.map = map;
 191                 }
 192
 193                 public Type get_element_type () {
 194                         return typeof (K);
 195                 }
 196
 197                 public Iterator<K> iterator () {
 198                         return new KeyIterator<K,V> (_map);
 199                 }
 200
 201                 public int size {
 202                         get { return _map.size; }
 203                 }
 204
 205                 public bool add (K key) {
 206                         assert_not_reached ();
 207                 }
 208
 209                 public void clear () {
 210                         assert_not_reached ();
 211                 }
 212
 213                 public bool remove (K key) {
 214                         assert_not_reached ();
 215                 }
 216
 217                 public bool contains (K key) {
 218                         return _map.contains (key);
 219                 }
 220         }
 221
 222         private class KeyIterator<K,V> : CollectionObject, Iterator<K> {
 223                 public HashMap<K,V> map {
 224                         set {
 225                                 _map = value;
 226                                 _stamp = _map._stamp;
 227                         }
 228                 }
 229
 230                 private HashMap<K,V> _map;
 231                 private int _index = -1;
 232                 private weak Node<K,V> _node;
 233
 234                 // concurrent modification protection
 235                 private int _stamp;
 236
 237                 public KeyIterator (HashMap map) {
 238                         this.map = map;
 239                 }
 240
 241                 public bool next () {
 242                         if (_node != null) {
 243                                 _node = _node.next;
 244                         }
 245                         while (_node == null && _index + 1 < _map._array_size) {
 246                                 _index++;
 247                                 _node = _map._nodes[_index];
 248                         }
 249                         return (_node != null);
 250                 }
 251
 252                 public K? get () {
 253                         assert (_stamp == _map._stamp);
 254                         assert (_node != null);
 255                         return _node.key;
 256                 }
 257         }
 258
 259         private class ValueCollection<K,V> : CollectionObject, Iterable<V>, Collection<V> {
 260                 public HashMap<K,V> map {
 261                         set { _map = value; }
 262                 }
 263
 264                 private HashMap<K,V> _map;
 265
 266                 public ValueCollection (HashMap map) {
 267                         this.map = map;
 268                 }
 269
 270                 public Type get_element_type () {
 271                         return typeof (V);
 272                 }
 273
 274                 public Iterator<V> iterator () {
 275                         return new ValueIterator<K,V> (_map);
 276                 }
 277
 278                 public int size {
 279                         get { return _map.size; }
 280                 }
 281
 282                 public bool add (V value) {
 283                         assert_not_reached ();
 284                 }
 285
 286                 public void clear () {
 287                         assert_not_reached ();
 288                 }
 289
 290                 public bool remove (V value) {
 291                         assert_not_reached ();
 292                 }
 293
 294                 public bool contains (V value) {
 295                         Iterator<V> it = iterator ();
 296                         while (it.next ()) {
 297                                 if (_map._value_equal_func (it.get (), value)) {
 298                                         return true;
 299                                 }
 300                         }
 301                         return false;
 302                 }
 303         }
 304
 305         private class ValueIterator<K,V> : CollectionObject, Iterator<V> {
 306                 public HashMap<K,V> map {
 307                         set {
 308                                 _map = value;
 309                                 _stamp = _map._stamp;
 310                         }
 311                 }
 312
 313                 private HashMap<V,K> _map;
 314                 private int _index = -1;
 315                 private weak Node<K,V> _node;
 316
 317                 // concurrent modification protection
 318                 private int _stamp;
 319
 320                 public ValueIterator (HashMap map) {
 321                         this.map = map;
 322                 }
 323
 324                 public bool next () {
 325                         if (_node != null) {
 326                                 _node = _node.next;
 327                         }
 328                         while (_node == null && _index + 1 < _map._array_size) {
 329                                 _index++;
 330                                 _node = _map._nodes[_index];
 331                         }
 332                         return (_node != null);
 333                 }
 334
 335                 public V? get () {
 336                         assert (_stamp == _map._stamp);
 337                         assert (_node != null);
 338                         return _node.value;
 339                 }
 340         }
 341 }
 342