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