gee/hashset.vala

   1 /* hashset.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 namespace Gee {
  28         public delegate uint HashDataFunc<T> (T v);
  29         public delegate bool EqualDataFunc<T> (T a, T b);
  30 }
  31
  32 /**
  33  * Hash table implementation of the {@link Set} interface.
  34  *
  35  * This implementation is better fit for highly heterogenous values.
  36  * In case of high value hashes redundancy or higher amount of data prefer using
  37  * tree implementation like {@link TreeSet}.
  38  *
  39  * @see TreeSet
  40  */
  41 public class Gee.HashSet<G> : AbstractSet<G> {
  42         /**
  43          * {@inheritDoc}
  44          */
  45         public override int size {
  46                 get { return _nnodes; }
  47         }
  48
  49         /**
  50          * {@inheritDoc}
  51          */
  52         public override bool read_only {
  53                 get { return false; }
  54         }
  55
  56         /**
  57          * The elements' hash function.
  58          */
  59         [CCode (notify = false)]
  60         public HashDataFunc<G> hash_func { private set; get; }
  61
  62         /**
  63          * The elements' equality testing function.
  64          */
  65         [CCode (notify = false)]
  66         public EqualDataFunc<G> equal_func { private set; get; }
  67
  68         private int _array_size;
  69         private int _nnodes;
  70         private Node<G>[] _nodes;
  71
  72         // concurrent modification protection
  73         private int _stamp = 0;
  74
  75         private const int MIN_SIZE = 11;
  76         private const int MAX_SIZE = 13845163;
  77
  78         /**
  79          * Constructs a new, empty hash set.
  80          *
  81          * If not provided, the functions parameters are requested to the
  82          * {@link Functions} function factory methods.
  83          *
  84          * @param hash_func an optional hash function
  85          * @param equal_func an optional equality testing function
  86          */
  87         public HashSet (owned HashDataFunc? hash_func = null, owned EqualDataFunc? equal_func = null) {
  88                 if (hash_func == null) {
  89                         hash_func = Functions.get_hash_func_for (typeof (G));
  90                 }
  91                 if (equal_func == null) {
  92                         equal_func = Functions.get_equal_func_for (typeof (G));
  93                 }
  94                 this.hash_func = hash_func;
  95                 this.equal_func = equal_func;
  96                 _array_size = MIN_SIZE;
  97                 _nodes = new Node<G>[_array_size];
  98         }
  99
 100         private Node<G>** lookup_node (G key) {
 101                 uint hash_value = hash_func (key);
 102                 Node<G>** node = &_nodes[hash_value % _array_size];
 103                 while ((*node) != null && (hash_value != (*node)->key_hash || !equal_func ((*node)->key, key))) {
 104                         node = &((*node)->next);
 105                 }
 106                 return node;
 107         }
 108
 109         /**
 110          * {@inheritDoc}
 111          */
 112         public override bool contains (G key) {
 113                 Node<G>** node = lookup_node (key);
 114                 return (*node != null);
 115         }
 116
 117         /**
 118          * {@inheritDoc}
 119          */
 120         public override Gee.Iterator<G> iterator () {
 121                 return new Iterator<G> (this);
 122         }
 123
 124         /**
 125          * {@inheritDoc}
 126          */
 127         public override bool add (G key) {
 128                 Node<G>** node = lookup_node (key);
 129                 if (*node != null) {
 130                         return false;
 131                 } else {
 132                         uint hash_value = hash_func (key);
 133                         *node = new Node<G> (key, hash_value);
 134                         _nnodes++;
 135                         resize ();
 136                         _stamp++;
 137                         return true;
 138                 }
 139         }
 140
 141         /**
 142          * {@inheritDoc}
 143          */
 144         public override bool remove (G key) {
 145                 bool b = remove_helper(key);
 146                 if(b) {
 147                         resize ();
 148                 }
 149                 return b;
 150         }
 151
 152         /**
 153          * {@inheritDoc}
 154          */
 155         public override void clear () {
 156                 for (int i = 0; i < _array_size; i++) {
 157                         Node<G> node = (owned) _nodes[i];
 158                         while (node != null) {
 159                                 Node next = (owned) node.next;
 160                                 node.key = null;
 161                                 node = (owned) next;
 162                         }
 163                 }
 164                 _nnodes = 0;
 165                 resize ();
 166         }
 167
 168         private inline bool remove_helper (G key) {
 169                 Node<G>** node = lookup_node (key);
 170                 if (*node != null) {
 171                         assert (*node != null);
 172                         Node<G> next = (owned) (*node)->next;
 173
 174                         (*node)->key = null;
 175                         delete *node;
 176
 177                         *node = (owned) next;
 178
 179                         _nnodes--;
 180                         _stamp++;
 181                         return true;
 182                 }
 183                 return false;
 184         }
 185
 186         private void resize () {
 187                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 188                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 189                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 190                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 191
 192                         Node<G>[] new_nodes = new Node<G>[new_array_size];
 193
 194                         for (int i = 0; i < _array_size; i++) {
 195                                 Node<G> node;
 196                                 Node<G> next = null;
 197                                 for (node = (owned) _nodes[i]; node != null; node = (owned) next) {
 198                                         next = (owned) node.next;
 199                                         uint hash_val = node.key_hash % new_array_size;
 200                                         node.next = (owned) new_nodes[hash_val];
 201                                         new_nodes[hash_val] = (owned) node;
 202                                 }
 203                         }
 204                         _nodes = (owned) new_nodes;
 205                         _array_size = new_array_size;
 206                 }
 207         }
 208
 209         ~HashSet () {
 210                 clear ();
 211         }
 212
 213         [Compact]
 214         private class Node<G> {
 215                 public G key;
 216                 public Node<G> next;
 217                 public uint key_hash;
 218
 219                 public Node (owned G k, uint hash) {
 220                         key = (owned) k;
 221                         key_hash = hash;
 222                 }
 223         }
 224
 225         private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
 226                 private HashSet<G> _set;
 227                 private int _index = -1;
 228                 private weak Node<G> _node;
 229                 private weak Node<G> _next;
 230
 231                 // concurrent modification protection
 232                 private int _stamp = 0;
 233
 234                 public Iterator (HashSet set) {
 235                         _set = set;
 236                         _stamp = _set._stamp;
 237                 }
 238
 239                 public bool next () {
 240                         assert (_stamp == _set._stamp);
 241                         if (!has_next ()) {
 242                                 return false;
 243                         }
 244                         _node = _next;
 245                         _next = null;
 246                         return (_node != null);
 247                 }
 248
 249                 public bool has_next () {
 250                         assert (_stamp == _set._stamp);
 251                         if (_next == null) {
 252                                 _next = _node;
 253                                 if (_next != null) {
 254                                         _next = _next.next;
 255                                 }
 256                                 while (_next == null && _index + 1 < _set._array_size) {
 257                                         _index++;
 258                                         _next = _set._nodes[_index];
 259                                 }
 260                         }
 261                         return (_next != null);
 262                 }
 263
 264                 public new G get () {
 265                         assert (_stamp == _set._stamp);
 266                         assert (_node != null);
 267                         return _node.key;
 268                 }
 269
 270                 public void remove () {
 271                         assert (_stamp == _set._stamp);
 272                         assert (_node != null);
 273                         has_next ();
 274                         _set.remove_helper (_node.key);
 275                         _node = null;
 276                         _stamp = _set._stamp;
 277                 }
 278
 279                 public bool read_only {
 280                         get {
 281                                 return false;
 282                         }
 283                 }
 284
 285                 public bool valid {
 286                         get {
 287                                 return _node != null;
 288                         }
 289                 }
 290
 291                 public bool foreach (ForallFunc<G> f) {
 292                         assert (_stamp == _set._stamp);
 293                         if (_node != null) {
 294                                 if (!f (_node.key)) {
 295                                         return false;
 296                                 }
 297                         }
 298                         while (_index + 1 < _set._array_size || _next != null) {
 299                                 if (_next != null) {
 300                                         _node = _next;
 301                                         if (!f (_node.key)) {
 302                                                 return false;
 303                                         }
 304                                         _next = _node.next;
 305                                 } else {
 306                                         _index++;
 307                                         _next = _set._nodes[_index];
 308                                 }
 309                         }
 310                         return false;
 311                 }
 312         }
 313 }
 314