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-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 Set interface.
  29  */
  30 public class Gee.HashSet<G> : Object, Iterable<G>, Collection<G>, Set<G> {
  31         public int size {
  32                 get { return _nnodes; }
  33         }
  34
  35         public HashFunc hash_func {
  36                 set { _hash_func = value; }
  37         }
  38
  39         public EqualFunc 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 _hash_func;
  51         private EqualFunc _equal_func;
  52
  53         private const int MIN_SIZE = 11;
  54         private const int MAX_SIZE = 13845163;
  55
  56         public HashSet (HashFunc hash_func = GLib.direct_hash, EqualFunc equal_func = GLib.direct_equal) {
  57                 this.hash_func = hash_func;
  58                 this.equal_func = equal_func;
  59         }
  60
  61         construct {
  62                 _array_size = MIN_SIZE;
  63                 _nodes = new Node<G>[_array_size];
  64         }
  65
  66         private Node<G>** lookup_node (G key) {
  67                 uint hash_value = _hash_func (key);
  68                 Node<G>** node = &_nodes[hash_value % _array_size];
  69                 while ((*node) != null && (hash_value != (*node)->key_hash || !_equal_func ((*node)->key, key))) {
  70                         node = &((*node)->next);
  71                 }
  72                 return node;
  73         }
  74
  75         public bool contains (G key) {
  76                 Node<G>** node = lookup_node (key);
  77                 return (*node != null);
  78         }
  79
  80         public Type get_element_type () {
  81                 return typeof (G);
  82         }
  83
  84         public Gee.Iterator<G> iterator () {
  85                 return new Iterator<G> (this);
  86         }
  87
  88         public bool add (G key) {
  89                 Node<G>** node = lookup_node (key);
  90                 if (*node != null) {
  91                         return false;
  92                 } else {
  93                         uint hash_value = _hash_func (key);
  94                         *node = new Node<G> (key, hash_value);
  95                         _nnodes++;
  96                         resize ();
  97                         _stamp++;
  98                         return true;
  99                 }
 100         }
 101
 102         public bool remove (G key) {
 103                 Node<G>** node = lookup_node (key);
 104                 if (*node != null) {
 105                         (*node)->key = null;
 106                         *node = (*node)->next;
 107                         _nnodes--;
 108                         resize ();
 109                         _stamp++;
 110                         return true;
 111                 }
 112                 return false;
 113         }
 114
 115         public void clear () {
 116                 for (int i = 0; i < _array_size; i++) {
 117                         Node<G> node = #_nodes[i];
 118                         while (node != null) {
 119                                 Node next = #node.next;
 120                                 node.key = null;
 121                                 node = #next;
 122                         }
 123                 }
 124                 _nnodes = 0;
 125                 resize ();
 126         }
 127
 128         private void resize () {
 129                 if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
 130                     (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
 131                         int new_array_size = (int) SpacedPrimes.closest (_nnodes);
 132                         new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
 133
 134                         Node<G>[] new_nodes = new Node<G>[new_array_size];
 135
 136                         for (int i = 0; i < _array_size; i++) {
 137                                 Node<G> node;
 138                                 Node<G> next;
 139                                 for (node = #_nodes[i]; node != null; node = #next) {
 140                                         next = #node.next;
 141                                         uint hash_val = node.key_hash % new_array_size;
 142                                         node.next = #new_nodes[hash_val];
 143                                         new_nodes[hash_val] = #node;
 144                                 }
 145                         }
 146                         _nodes = #new_nodes;
 147                         _array_size = new_array_size;
 148                 }
 149         }
 150
 151         ~HashSet () {
 152                 clear ();
 153         }
 154
 155         [Compact]
 156         private class Node<G> {
 157                 public G key;
 158                 public Node<G> next;
 159                 public uint key_hash;
 160
 161                 public Node (G# k, uint hash) {
 162                         key = #k;
 163                         key_hash = hash;
 164                 }
 165         }
 166
 167         private class Iterator<G> : Object, Gee.Iterator<G> {
 168                 public HashSet<G> set {
 169                         set {
 170                                 _set = value;
 171                                 _stamp = _set._stamp;
 172                         }
 173                 }
 174
 175                 private HashSet<G> _set;
 176                 private int _index = -1;
 177                 private weak Node<G> _node;
 178
 179                 // concurrent modification protection
 180                 private int _stamp = 0;
 181
 182                 public Iterator (HashSet set) {
 183                         this.set = set;
 184                 }
 185
 186                 public bool next () {
 187                         if (_node != null) {
 188                                 _node = _node.next;
 189                         }
 190                         while (_node == null && _index + 1 < _set._array_size) {
 191                                 _index++;
 192                                 _node = _set._nodes[_index];
 193                         }
 194                         return (_node != null);
 195                 }
 196
 197                 public G? get () {
 198                         assert (_stamp == _set._stamp);
 199                         assert (_node != null);
 200                         return _node.key;
 201                 }
 202         }
 203 }
 204