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