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