using GLib;
+namespace Gee {
+ public delegate uint HashDataFunc<T> (T v);
+ public delegate bool EqualDataFunc<T> (T a, T b);
+}
+
/**
- * Hash table implementation of the {@link Gee.Set} interface.
+ * Hash table implementation of the {@link Set} interface.
*
* This implementation is better fit for highly heterogenous values.
* In case of high value hashes redundancy or higher amount of data prefer using
- * tree implementation like {@link Gee.TreeSet}.
+ * tree implementation like {@link TreeSet}.
*
- * @see Gee.TreeSet
+ * @see TreeSet
*/
public class Gee.HashSet<G> : AbstractSet<G> {
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override int size {
get { return _nnodes; }
}
/**
+ * {@inheritDoc}
+ */
+ public override bool read_only {
+ get { return false; }
+ }
+
+ /**
* The elements' hash function.
*/
- public HashFunc hash_func { private set; get; }
+ [CCode (notify = false)]
+ public HashDataFunc<G> hash_func { private set; get; }
/**
* The elements' equality testing function.
*/
- public EqualFunc equal_func { private set; get; }
+ [CCode (notify = false)]
+ public EqualDataFunc<G> equal_func { private set; get; }
private int _array_size;
private int _nnodes;
/**
* Constructs a new, empty hash set.
*
- * @param hash_func an optional hash function.
- * @param equal_func an optional equality testing function.
+ * If not provided, the functions parameters are requested to the
+ * {@link Functions} function factory methods.
+ *
+ * @param hash_func an optional hash function
+ * @param equal_func an optional equality testing function
*/
- public HashSet (HashFunc? hash_func = null, EqualFunc? equal_func = null) {
+ public HashSet (owned HashDataFunc<G>? hash_func = null, owned EqualDataFunc<G>? equal_func = null) {
if (hash_func == null) {
hash_func = Functions.get_hash_func_for (typeof (G));
}
}
this.hash_func = hash_func;
this.equal_func = equal_func;
- }
-
- construct {
_array_size = MIN_SIZE;
_nodes = new Node<G>[_array_size];
}
}
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override bool contains (G key) {
Node<G>** node = lookup_node (key);
}
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override Gee.Iterator<G> iterator () {
return new Iterator<G> (this);
}
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override bool add (G key) {
Node<G>** node = lookup_node (key);
}
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override bool remove (G key) {
- Node<G>** node = lookup_node (key);
- if (*node != null) {
- Node<G> next = (owned) (*node)->next;
-
- (*node)->key = null;
- delete *node;
-
- *node = (owned) next;
-
- _nnodes--;
+ bool b = remove_helper(key);
+ if(b) {
resize ();
- _stamp++;
- return true;
}
- return false;
+ return b;
}
/**
- * @inheritDoc
+ * {@inheritDoc}
*/
public override void clear () {
for (int i = 0; i < _array_size; i++) {
resize ();
}
+ private inline bool remove_helper (G key) {
+ Node<G>** node = lookup_node (key);
+ if (*node != null) {
+ assert (*node != null);
+ Node<G> next = (owned) (*node)->next;
+
+ (*node)->key = null;
+ delete *node;
+
+ *node = (owned) next;
+
+ _nnodes--;
+ _stamp++;
+ return true;
+ }
+ return false;
+ }
+
private void resize () {
if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
(3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
}
}
- private class Iterator<G> : Object, Gee.Iterator<G> {
- public new HashSet<G> set {
- construct {
- _set = value;
- _stamp = _set._stamp;
- }
- }
-
+ private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
private HashSet<G> _set;
private int _index = -1;
private weak Node<G> _node;
private int _stamp = 0;
public Iterator (HashSet set) {
- this.set = set;
+ _set = set;
+ _stamp = _set._stamp;
}
public bool next () {
return (_next != null);
}
- public bool first () {
+ public new G get () {
assert (_stamp == _set._stamp);
- if (_set.size == 0) {
+ assert (_node != null);
+ return _node.key;
+ }
+
+ public void remove () {
+ assert (_stamp == _set._stamp);
+ assert (_node != null);
+ has_next ();
+ _set.remove_helper (_node.key);
+ _node = null;
+ _stamp = _set._stamp;
+ }
+
+ public bool read_only {
+ get {
return false;
}
- _index = -1;
- _next = null;
- return next ();
}
- public new G get () {
+ public bool valid {
+ get {
+ return _node != null;
+ }
+ }
+
+ public bool foreach (ForallFunc<G> f) {
assert (_stamp == _set._stamp);
- assert (_node != null);
- return _node.key;
+ unowned Node<G>? node = _node, next = _next, current = null, prev = null;
+ if (node != null) {
+ if (!f (node.key)) {
+ return false;
+ }
+ prev = node;
+ current = node.next;
+ }
+ if (next != null) {
+ if (!f (next.key)) {
+ _node = next;
+ _next = null;
+ return false;
+ }
+ prev = next;
+ current = next.next;
+ }
+ do {
+ while (current != null) {
+ if (!f (current.key)) {
+ _node = current;
+ _next = null;
+ return false;
+ }
+ prev = current;
+ current = current.next;
+ }
+ while (current == null && _index + 1 < _set._array_size) {
+ _index++;
+ current = _set._nodes[_index];
+ }
+ } while (current != null);
+ _node = prev;
+ _next = null;
+ return true;
}
}
}
projects / platform / upstream / libgee.git / blobdiff