[vala/wip/gee: 101/103] Update internal gee from libgee 0.18.1
- From: Rico Tzschichholz <ricotz src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [vala/wip/gee: 101/103] Update internal gee from libgee 0.18.1
- Date: Wed, 3 May 2017 08:25:30 +0000 (UTC)
commit b7148f8c267a7eddc3a2ab9e8c894c9160c375af
Author: Rico Tzschichholz <ricotz ubuntu com>
Date: Tue Sep 20 23:56:04 2016 +0200
Update internal gee from libgee 0.18.1
https://bugzilla.gnome.org/show_bug.cgi?id=704754
configure.ac | 2 +-
gee/Makefile.am | 26 +-
gee/abstractbidirlist.vala | 12 +-
gee/abstractbidirsortedmap.vala | 12 +-
gee/abstractbidirsortedset.vala | 12 +-
gee/abstractcollection.vala | 12 +-
gee/abstractlist.vala | 12 +-
gee/abstractmap.vala | 12 +-
gee/abstractmultimap.vala | 22 +-
gee/abstractmultiset.vala | 16 +
gee/abstractset.vala | 12 +-
gee/abstractsortedmap.vala | 13 +-
gee/abstractsortedset.vala | 12 +-
gee/arraylist.vala | 243 ++++++-
gee/arrayqueue.vala | 50 ++-
gee/bidirlistiterator.vala | 6 +-
gee/collection.vala | 491 +++++++++++++-
gee/comparable.vala | 12 +
gee/concurrentlist.vala | 92 ++-
gee/concurrentset.vala | 1446 +++++++++++++++++++++++++++++++++++++++
gee/functions.vala | 35 +-
gee/future.vala | 256 +++++++
gee/hashable.vala | 19 +-
gee/hashmap.vala | 177 ++++--
gee/hashmultimap.vala | 31 +-
gee/hashmultiset.vala | 8 +-
gee/hashset.vala | 112 +++-
gee/hazardpointer.vala | 101 ++--
gee/iterator.vala | 7 +-
gee/lazy.vala | 110 +++
gee/lightmapfuture.vala | 62 ++
gee/linkedlist.vala | 310 ++++++----
gee/listiterator.vala | 5 +-
gee/map.vala | 60 +--
gee/mapiterator.vala | 14 +-
gee/multimap.vala | 8 +-
gee/multiset.vala | 19 +
gee/priorityqueue.vala | 93 ++-
gee/promise.vala | 217 ++++++
gee/queue.vala | 4 +-
gee/readonlycollection.vala | 25 +-
gee/readonlymap.vala | 8 +-
gee/readonlymultimap.vala | 131 ++++
gee/readonlymultiset.vala | 57 ++
gee/streamiterator.vala | 183 +++++
gee/task.vala | 95 +++
gee/teeiterator.vala | 116 ++++
gee/timsort.vala | 6 +-
gee/traversable.vala | 203 ++++--
gee/treemap.vala | 188 +++++-
gee/treemultimap.vala | 17 +-
gee/treemultiset.vala | 6 +-
gee/treeset.vala | 96 +++-
gee/unrolledlinkedlist.vala | 1152 +++++++++++++++++++++++++++++++
gee/utils/assume.h | 33 +
gee/utils/async.h | 31 +
gee/utils/free.h | 30 +
gee/utils/misc.h | 30 +
gee/utils/utils.vapi | 20 +
59 files changed, 6007 insertions(+), 583 deletions(-)
---
diff --git a/configure.ac b/configure.ac
index a448018..8398ef3 100644
--- a/configure.ac
+++ b/configure.ac
@@ -86,7 +86,7 @@ AC_SUBST(COVERAGE_LIBS)
GLIB_REQUIRED=2.32.0
-PKG_CHECK_MODULES(GLIB, glib-2.0 >= $GLIB_REQUIRED gobject-2.0 >= $GLIB_REQUIRED)
+PKG_CHECK_MODULES(GLIB, glib-2.0 >= $GLIB_REQUIRED gobject-2.0 >= $GLIB_REQUIRED gio-2.0 >= $GLIB_REQUIRED)
AC_SUBST(GLIB_CFLAGS)
AC_SUBST(GLIB_LIBS)
diff --git a/gee/Makefile.am b/gee/Makefile.am
index d1ddc68..ee4a0c9 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -5,6 +5,7 @@ NULL =
AM_CPPFLAGS = \
$(COVERAGE_CFLAGS) \
$(GLIB_CFLAGS) \
+ -I$(srcdir)/utils \
$(NULL)
BUILT_SOURCES = gee.vala.stamp
@@ -37,8 +38,10 @@ libgee_la_VALASOURCES = \
collection.vala \
comparable.vala \
concurrentlist.vala \
+ concurrentset.vala \
deque.vala \
functions.vala \
+ future.vala \
hashable.vala \
hashmap.vala \
hashmultimap.vala \
@@ -48,6 +51,7 @@ libgee_la_VALASOURCES = \
iterable.vala \
iterator.vala \
lazy.vala \
+ lightmapfuture.vala \
linkedlist.vala \
listiterator.vala \
list.vala \
@@ -56,6 +60,7 @@ libgee_la_VALASOURCES = \
multimap.vala \
multiset.vala \
priorityqueue.vala \
+ promise.vala \
queue.vala \
readonlybidirlist.vala \
readonlybidirsortedmap.vala \
@@ -63,12 +68,17 @@ libgee_la_VALASOURCES = \
readonlycollection.vala \
readonlylist.vala \
readonlymap.vala \
+ readonlymultimap.vala \
+ readonlymultiset.vala \
readonlyset.vala \
readonlysortedmap.vala \
readonlysortedset.vala \
set.vala \
sortedmap.vala \
sortedset.vala \
+ streamiterator.vala \
+ task.vala \
+ teeiterator.vala \
timsort.vala \
traversable.vala \
treemap.vala \
@@ -76,6 +86,7 @@ libgee_la_VALASOURCES = \
treemultiset.vala \
treeset.vala \
unfolditerator.vala \
+ unrolledlinkedlist.vala \
$(NULL)
libgee_la_SOURCES = \
@@ -94,7 +105,8 @@ gee.vapi gee.vala.stamp: $(libgee_la_VALASOURCES)
$(COVERAGE_VALAFLAGS) \
$(VALAFLAGS) \
-C \
- --vapidir $(top_srcdir)/vapi --pkg gobject-2.0 \
+ --vapidir $(srcdir)/utils --pkg utils \
+ --vapidir $(top_srcdir)/vapi --pkg gobject-2.0 --pkg gio-2.0 \
--use-header \
-H valagee.h \
--library gee \
@@ -106,7 +118,17 @@ libgee_la_LIBADD = \
$(GLIB_LIBS) \
$(NULL)
-EXTRA_DIST = $(libgee_la_VALASOURCES) gee.vapi gee.vala.stamp valagee.h
+EXTRA_DIST = \
+ $(libgee_la_VALASOURCES) \
+ gee.vapi \
+ gee.vala.stamp \
+ valagee.h \
+ utils/assume.h \
+ utils/async.h \
+ utils/free.h \
+ utils/utils.vapi \
+ utils/misc.h \
+ $(NULL)
MAINTAINERCLEANFILES = \
gee.vapi \
diff --git a/gee/abstractbidirlist.vala b/gee/abstractbidirlist.vala
index 41040f5..81e9bf1 100644
--- a/gee/abstractbidirlist.vala
+++ b/gee/abstractbidirlist.vala
@@ -26,18 +26,20 @@ public abstract class Vala.AbstractBidirList<G> : AbstractList<G>, BidirList<G>
*/
public abstract BidirListIterator<G> bidir_list_iterator ();
- private weak BidirList<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new BidirList<G> read_only_view {
owned get {
- BidirList<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ BidirList<G>? instance = (BidirList<G>?)_read_only_view.get();
+ if (instance == null) {
instance = new ReadOnlyBidirList<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractbidirsortedmap.vala b/gee/abstractbidirsortedmap.vala
index 2290c17..d2d345f 100644
--- a/gee/abstractbidirsortedmap.vala
+++ b/gee/abstractbidirsortedmap.vala
@@ -33,18 +33,20 @@ public abstract class Vala.AbstractBidirSortedMap<K,V> : Vala.AbstractSortedMap<
*/
public abstract BidirMapIterator<K,V> bidir_map_iterator ();
- private weak BidirSortedMap<K,V> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new BidirSortedMap<K,V> read_only_view {
owned get {
- BidirSortedMap<K,V> instance = _read_only_view;
- if (_read_only_view == null) {
+ BidirSortedMap<K,V>? instance = (BidirSortedMap<K,V>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlyBidirSortedMap<K,V> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractbidirsortedset.vala b/gee/abstractbidirsortedset.vala
index 219664a..5956f90 100644
--- a/gee/abstractbidirsortedset.vala
+++ b/gee/abstractbidirsortedset.vala
@@ -33,18 +33,20 @@ public abstract class Vala.AbstractBidirSortedSet<G> : Vala.AbstractSortedSet<G>
*/
public abstract BidirIterator<G> bidir_iterator ();
- private weak BidirSortedSet<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new BidirSortedSet<G> read_only_view {
owned get {
- BidirSortedSet<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ BidirSortedSet<G>? instance = (BidirSortedSet<G>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlyBidirSortedSet<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractcollection.vala b/gee/abstractcollection.vala
index a2421ce..a11ec4f 100644
--- a/gee/abstractcollection.vala
+++ b/gee/abstractcollection.vala
@@ -70,18 +70,20 @@ public abstract class Vala.AbstractCollection<G> : Object, Traversable<G>, Itera
return iterator ().foreach (f);
}
- private weak Collection<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual Collection<G> read_only_view {
owned get {
- Collection<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ Collection<G>? instance = (Collection<G>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlyCollection<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractlist.vala b/gee/abstractlist.vala
index 581ad7f..184b21c 100644
--- a/gee/abstractlist.vala
+++ b/gee/abstractlist.vala
@@ -66,18 +66,20 @@ public abstract class Vala.AbstractList<G> : Vala.AbstractCollection<G>, List<G>
*/
public abstract List<G>? slice (int start, int stop);
- private weak List<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new List<G> read_only_view {
owned get {
- List<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ List<G>? instance = (List<G>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlyList<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractmap.vala b/gee/abstractmap.vala
index bc24604..b5ece89 100644
--- a/gee/abstractmap.vala
+++ b/gee/abstractmap.vala
@@ -91,18 +91,20 @@ public abstract class Vala.AbstractMap<K,V> : Object, Traversable<Map.Entry<K,V>
*/
public abstract void clear ();
- private weak Map<K,V> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual Map<K,V> read_only_view {
owned get {
- Map<K,V> instance = _read_only_view;
- if (_read_only_view == null) {
+ Map<K,V>? instance = (Map<K,V>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlyMap<K,V> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractmultimap.vala b/gee/abstractmultimap.vala
index 9c96c70..0e60e01 100644
--- a/gee/abstractmultimap.vala
+++ b/gee/abstractmultimap.vala
@@ -162,7 +162,7 @@ public abstract class Vala.AbstractMultiMap<K,V> : Object, MultiMap<K,V> {
_multi_map = multi_map;
}
- public override Vala.Iterator<K> iterator () {
+ public override Vala.Iterator<V> iterator () {
return new ValueIterator<K, V> (_multi_map._storage_map.map_iterator ());
}
@@ -179,11 +179,11 @@ public abstract class Vala.AbstractMultiMap<K,V> : Object, MultiMap<K,V> {
return false;
}
- public override bool add (V key) {
+ public override bool add (V value) {
assert_not_reached ();
}
- public override bool remove (V item) {
+ public override bool remove (V value) {
assert_not_reached ();
}
@@ -308,4 +308,20 @@ public abstract class Vala.AbstractMultiMap<K,V> : Object, MultiMap<K,V> {
public bool mutable { get { return false; } }
}
+
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
+
+ public virtual new MultiMap<K, V> read_only_view {
+ owned get {
+ MultiMap<K, V>? instance = (MultiMap<K, V>?)_read_only_view.get ();
+ if (instance == null) {
+ instance = new ReadOnlyMultiMap<K, V> (this);
+ _read_only_view.set (instance);
+ }
+ return instance;
+ }
+ }
}
diff --git a/gee/abstractmultiset.vala b/gee/abstractmultiset.vala
index 4d2f781..4145ea3 100644
--- a/gee/abstractmultiset.vala
+++ b/gee/abstractmultiset.vala
@@ -92,6 +92,22 @@ public abstract class Vala.AbstractMultiSet<G> : AbstractCollection<G>, MultiSet
_nitems = 0;
}
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
+
+ public virtual new MultiSet<G> read_only_view {
+ owned get {
+ MultiSet<G>? instance = (MultiSet<G>?)_read_only_view.get ();
+ if (instance == null) {
+ instance = new ReadOnlyMultiSet<G> (this);
+ _read_only_view.set (instance);
+ }
+ return instance;
+ }
+ }
+
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G> {
private AbstractMultiSet<G> _set;
diff --git a/gee/abstractset.vala b/gee/abstractset.vala
index 71effc5..7a83d06 100644
--- a/gee/abstractset.vala
+++ b/gee/abstractset.vala
@@ -31,18 +31,20 @@
*/
public abstract class Vala.AbstractSet<G> : Vala.AbstractCollection<G>, Set<G> {
- private weak Set<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new Set<G> read_only_view {
owned get {
- Set<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ Set<G>? instance = (Set<G>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlySet<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractsortedmap.vala b/gee/abstractsortedmap.vala
index 876a4c3..58d7f04 100644
--- a/gee/abstractsortedmap.vala
+++ b/gee/abstractsortedmap.vala
@@ -46,17 +46,20 @@ public abstract class Vala.AbstractSortedMap<K, V> : AbstractMap<K,V>, SortedMap
*/
public abstract SortedSet<Map.Entry<K,V>> ascending_entries { owned get; }
- private weak SortedMap<K,V> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
+
/**
* The read-only view this map.
*/
public new SortedMap<K,V> read_only_view {
owned get {
- SortedMap<K,V> instance = _read_only_view;
- if (_read_only_view == null) {
+ SortedMap<K,V>? instance = (SortedMap<K,V>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlySortedMap<K,V> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/abstractsortedset.vala b/gee/abstractsortedset.vala
index 03f02f3..830bb2d 100644
--- a/gee/abstractsortedset.vala
+++ b/gee/abstractsortedset.vala
@@ -78,18 +78,20 @@ public abstract class Vala.AbstractSortedSet<G> : Vala.AbstractSet<G>, SortedSet
*/
public abstract SortedSet<G> sub_set (G from, G to);
- private weak SortedSet<G> _read_only_view;
+ private WeakRef _read_only_view;
+ construct {
+ _read_only_view = WeakRef(null);
+ }
/**
* {@inheritDoc}
*/
public virtual new SortedSet<G> read_only_view {
owned get {
- SortedSet<G> instance = _read_only_view;
- if (_read_only_view == null) {
+ SortedSet<G>? instance = (SortedSet<G>?)_read_only_view.get ();
+ if (instance == null) {
instance = new ReadOnlySortedSet<G> (this);
- _read_only_view = instance;
- instance.add_weak_pointer ((void**) (&_read_only_view));
+ _read_only_view.set (instance);
}
return instance;
}
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index 4bcb3e0..51a0a1d 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -4,6 +4,7 @@
* Copyright (C) 2005 David Waite
* Copyright (C) 2007-2008 Jürg Billeter
* Copyright (C) 2009 Didier Villevalois
+ * Copyright (C) 2010-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -24,7 +25,7 @@
* Didier 'Ptitjes Villevalois <ptitjes free fr>
*/
-using GLib;
+using Vala.Utils.Assume;
/**
* Resizable array implementation of the {@link List} interface.
@@ -56,10 +57,16 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
* The elements' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<G> equal_func { private set; get; }
+ public EqualDataFunc<G> equal_func {
+ private set {}
+ get {
+ return _equal_func.func;
+ }
+ }
- internal G[] _items = new G[4];
+ internal G[] _items;
internal int _size;
+ private Functions.EqualDataFuncClosure<G> _equal_func;
// concurrent modification protection
private int _stamp = 0;
@@ -76,7 +83,33 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
if (equal_func == null) {
equal_func = Functions.get_equal_func_for (typeof (G));
}
- this.equal_func = equal_func;
+ _equal_func = new Functions.EqualDataFuncClosure<G>((owned)equal_func);
+ _items = new G[4];
+ _size = 0;
+ }
+
+ /**
+ * Constructs a new array list based on provided array.
+ *
+ * If not provided, the function parameter is requested to the
+ * {@link Functions} function factory methods.
+ *
+ * @param items initial items to be put into array
+ * @param equal_func an optional element equality testing function
+ */
+ public ArrayList.wrap (owned G[] items, owned EqualDataFunc<G>? equal_func = null) {
+ if (equal_func == null) {
+ equal_func = Functions.get_equal_func_for (typeof (G));
+ }
+ _equal_func = new Functions.EqualDataFuncClosure<G>((owned)equal_func);
+ _size = items.length;
+ _items = do_wrap<G> ((owned)items);
+ }
+
+ internal ArrayList.with_closure (owned Functions.EqualDataFuncClosure<G> equal_func) {
+ _equal_func = equal_func;
+ _items = new G[4];
+ _size = 0;
}
/**
@@ -226,7 +259,7 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
return_val_if_fail (start >= 0, null);
return_val_if_fail (stop <= _size, null);
- var slice = new ArrayList<G> (this.equal_func);
+ var slice = new ArrayList<G>.with_closure (_equal_func);
for (int i = start; i < stop; i++) {
slice.add (this[i]);
}
@@ -249,9 +282,15 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
}
private void shift (int start, int delta) {
+#if !DISABLE_INTERNAL_ASSERTS
assert (start >= 0);
assert (start <= _size);
assert (start >= -delta);
+#else
+ assume (start >= 0);
+ assume (start <= _size);
+ assume (start >= -delta);
+#endif
_items.move (start, start + delta, _size - start);
@@ -259,7 +298,11 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
}
private void grow_if_needed (int new_count) {
+#if !DISABLE_INTERNAL_ASSERTS
assert (new_count >= 0);
+#else
+ assume (new_count >= 0);
+#endif
int minimum_size = _size + new_count;
if (minimum_size > _items.length) {
@@ -269,24 +312,26 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
}
private void set_capacity (int value) {
+#if !DISABLE_INTERNAL_ASSERTS
assert (value >= _size);
+#endif
_items.resize (value);
}
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G>, BidirIterator<G>,
ListIterator<G>, BidirListIterator<G> {
- private ArrayList<G> _list;
- private int _index = -1;
- private bool _removed = false;
-
- // concurrent modification protection
- private int _stamp = 0;
-
- public Iterator (ArrayList list) {
+ public Iterator (ArrayList<G> list) {
_list = list;
_stamp = _list._stamp;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _list = iter._list;
+ _index = iter._index;
+ _removed = iter._removed;
+ _stamp = iter._stamp;
+ }
+
public bool next () {
assert (_stamp == _list._stamp);
if (_index + 1 < _list._size) {
@@ -314,17 +359,24 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
public new G get () {
assert (_stamp == _list._stamp);
+ assert (! _removed);
assert (_index >= 0);
+#if !DISABLE_INTERNAL_ASSERTS
assert (_index < _list._size);
- assert (! _removed);
+#else
+ assume (_index < _list._size);
+#endif
return _list._items[_index];
}
public void remove () {
assert (_stamp == _list._stamp);
- assert (_index >= 0);
+ assert (! _removed && _index >= 0);
+#if !DISABLE_INTERNAL_ASSERTS
assert (_index < _list._size);
- assert (! _removed);
+#else
+ assume (_index < _list._size);
+#endif
_list.remove_at (_index);
_index--;
_removed = true;
@@ -333,6 +385,10 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
public bool previous () {
assert (_stamp == _list._stamp);
+ if (_removed && _index >= 0) {
+ _removed = false;
+ return true;
+ }
if (_index > 0) {
_index--;
return true;
@@ -342,7 +398,7 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
public bool has_previous () {
assert (_stamp == _list._stamp);
- return (_index - 1 >= 0);
+ return (_index > 0 || (_removed && _index >= 0));
}
public bool last () {
@@ -356,27 +412,39 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
public new void set (G item) {
assert (_stamp == _list._stamp);
+ assert (! _removed);
assert (_index >= 0);
+#if !DISABLE_INTERNAL_ASSERTS
assert (_index < _list._size);
+#else
+ assume (_index < _list._size);
+#endif
_list._items[_index] = item;
_stamp = ++_list._stamp;
}
public void insert (G item) {
assert (_stamp == _list._stamp);
- assert (_index >= 0);
assert (_index < _list._size);
- _list.insert (_index, item);
+ if (_index == -1) {
+ _list.insert (0, item);
+ _removed = true;
+ }
+ if (_removed) {
+ _list.insert (_index + 1, item);
+ } else {
+ _list.insert (_index, item);
+ }
_index++;
_stamp = _list._stamp;
}
public void add (G item) {
assert (_stamp == _list._stamp);
- assert (_index >= 0);
assert (_index < _list._size);
_list.insert (_index + 1, item);
_index++;
+ _removed = false;
_stamp = _list._stamp;
}
@@ -413,6 +481,141 @@ public class Vala.ArrayList<G> : AbstractBidirList<G> {
_index = _list._size - 1;
return true;
}
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected ArrayList<G> _list;
+ protected int _index = -1;
+ protected bool _removed = false;
+ protected int _stamp = 0;
+ }
+
+ private static G[] do_wrap<G> (owned G[] data) {
+ var t = typeof (G);
+ if (t == typeof (bool)) {
+ return wrap_bool<G> ((bool[])data);
+ } else if (t == typeof (char)) {
+ return wrap_char<G> ((char[])data);
+ } else if (t == typeof (uchar)) {
+ return wrap_uchar<G> ((uchar[])data);
+ } else if (t == typeof (int)) {
+ return wrap_int<G> ((int[])data);
+ } else if (t == typeof (uint)) {
+ return wrap_uint<G> ((uint[])data);
+ } else if (t == typeof (int64)) {
+ return wrap_int64<G> ((int64[])data);
+ } else if (t == typeof (uint64)) {
+ return wrap_uint64<G> ((uint64[])data);
+ } else if (t == typeof (long)) {
+ return wrap_long<G> ((long[])data);
+ } else if (t == typeof (ulong)) {
+ return wrap_ulong<G> ((ulong[])data);
+ } else if (t == typeof (float)) {
+ return wrap_float<G> ((float?[])data);
+ } else if (t == typeof (double)) {
+ return wrap_double<G> ((double?[])data);
+ } else {
+ return (owned)data;
+ }
+ }
+
+ private static G[] wrap_bool<G> (bool[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_char<G> (char[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_uchar<G> (uchar[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_int<G> (int[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_uint<G> (uint[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_int64<G> (int64[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_uint64<G> (uint64[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_long<G> (long[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_ulong<G> (ulong[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_float<G> (float?[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
+ }
+
+ private static G[] wrap_double<G> (double?[] data) {
+ G[] arr = new G[data.length];
+ for (uint i = 0; i < data.length; i++) {
+ arr[i] = data[i];
+ }
+ return arr;
}
}
diff --git a/gee/arrayqueue.vala b/gee/arrayqueue.vala
index 9eac3e6..25c4721 100644
--- a/gee/arrayqueue.vala
+++ b/gee/arrayqueue.vala
@@ -1,6 +1,6 @@
/* arrayqueue.vala
*
- * Copyright (C) 2012 Maciej Piechotka
+ * Copyright (C) 2012-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -44,12 +44,17 @@ public class Vala.ArrayQueue<G> : Vala.AbstractQueue<G>, Deque<G> {
if (equal_func == null) {
equal_func = Functions.get_equal_func_for (typeof (G));
}
- this.equal_func = equal_func;
+ _equal_func = (owned)equal_func;
this._items = new G[10];
}
[CCode (notify = false)]
- public EqualDataFunc<G> equal_func { private set; get; }
+ public EqualDataFunc<G> equal_func {
+ private set {}
+ get { return _equal_func; }
+ }
+
+ private EqualDataFunc<G> _equal_func;
/**
* {@inheritDoc}
@@ -127,6 +132,18 @@ public class Vala.ArrayQueue<G> : Vala.AbstractQueue<G>, Deque<G> {
/**
* {@inheritDoc}
*/
+ public override bool foreach (ForallFunc<G> f) {
+ for (int i = 0; i < _length; i++) {
+ if (!f (_items[(_start + i) % _items.length])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
public override G? peek () {
return peek_head ();
}
@@ -277,6 +294,12 @@ public class Vala.ArrayQueue<G> : Vala.AbstractQueue<G>, Deque<G> {
_queue = queue;
_stamp = _queue._stamp;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _queue = iter._queue;
+ _stamp = iter._stamp;
+ _offset = iter._offset;
+ _removed = iter._removed;
+ }
public bool next () {
assert (_queue._stamp == _stamp);
@@ -328,10 +351,23 @@ public class Vala.ArrayQueue<G> : Vala.AbstractQueue<G>, Deque<G> {
return true;
}
- private ArrayQueue _queue;
- private int _stamp;
- private int _offset = -1;
- private bool _removed = false;
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected ArrayQueue _queue;
+ protected int _stamp;
+ protected int _offset = -1;
+ protected bool _removed = false;
}
private G[] _items;
diff --git a/gee/bidirlistiterator.vala b/gee/bidirlistiterator.vala
index 094a5f7..10f524b 100644
--- a/gee/bidirlistiterator.vala
+++ b/gee/bidirlistiterator.vala
@@ -23,7 +23,11 @@
public interface Vala.BidirListIterator<G> : Vala.BidirIterator<G>, Vala.ListIterator<G> {
/**
* Inserts the specified item before the current item in the iteration. The
- * cursor is let to point to the current item.
+ * iterator points to the same element as before.
+ *
+ * Please note that if iterator points in-between elements the element
+ * is added between neighbouring elements and the iterator point between
+ * added element and the next one.
*/
public abstract void insert (G item);
}
diff --git a/gee/collection.vala b/gee/collection.vala
index 112e6ac..cd9c6ea 100644
--- a/gee/collection.vala
+++ b/gee/collection.vala
@@ -28,17 +28,20 @@ public interface Vala.Collection<G> : Iterable<G> {
/**
* The number of items in this collection.
*/
+ [CCode (ordering = 9)]
public abstract int size { get; }
/**
* Specifies whether this collection is empty.
*/
+ [CCode (ordering = 10)]
public virtual bool is_empty { get { return size == 0; } }
/**
* Specifies whether this collection can change - i.e. wheather {@link add},
* {@link remove} etc. are legal operations.
*/
+ [CCode (ordering = 11)]
public abstract bool read_only { get; }
/**
@@ -48,6 +51,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if item is found, ``false`` otherwise
*/
+ [CCode (ordering = 0)]
public abstract bool contains (G item);
/**
@@ -58,6 +62,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 1)]
public abstract bool add (G item);
/**
@@ -68,12 +73,14 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 2)]
public abstract bool remove (G item);
/**
* Removes all items from this collection. Must not be called on
* read-only collections.
*/
+ [CCode (ordering = 3)]
public abstract void clear ();
/**
@@ -84,6 +91,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 4)]
public virtual bool add_all (Collection<G> collection) {
return collection.fold<bool> ((item, changed) => changed | add (item), false);
}
@@ -97,6 +105,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 5)]
public virtual bool contains_all (Collection<G> collection) {
return collection.foreach ((item) => contains (item));
}
@@ -112,6 +121,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 6)]
public virtual bool remove_all (Collection<G> collection) {
return collection.fold<bool> ((item, changed) => changed | remove (item), false);
}
@@ -126,6 +136,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return ``true`` if the collection has been changed, ``false`` otherwise
*/
+ [CCode (ordering = 7)]
public virtual bool retain_all (Collection<G> collection) {
bool changed = false;
for (Iterator<G> iter = iterator(); iter.next ();) {
@@ -143,6 +154,7 @@ public interface Vala.Collection<G> : Iterable<G> {
*
* @return an array containing all of items from this collection
*/
+ [CCode (ordering = 8)]
public virtual G[] to_array () {
var t = typeof (G);
if (t == typeof (bool)) {
@@ -171,12 +183,182 @@ public interface Vala.Collection<G> : Iterable<G> {
G[] array = new G[size];
int index = 0;
foreach (G element in this) {
- array[index++] = element;
+ array[index++] = (owned)element;
}
return array;
}
}
+ /**
+ * Adds all items in the input array to this collection.
+ *
+ * @param array the array which items will be added to this
+ * collection.
+ *
+ * @return ``true`` if the collection has been changed, ``false`` otherwise
+ */
+ [CCode (ordering = 13)]
+ public virtual bool add_all_array (G[] array) {
+ var t = typeof (G);
+ if (t == typeof (bool)) {
+ return add_all_bool_array ((Collection<bool>) this, (bool [])array);
+ } else if (t == typeof (char)) {
+ return add_all_char_array ((Collection<char>) this, (char [])array);
+ } else if (t == typeof (uchar)) {
+ return add_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
+ } else if (t == typeof (int)) {
+ return add_all_int_array ((Collection<int>) this, (int [])array);
+ } else if (t == typeof (uint)) {
+ return add_all_uint_array ((Collection<uint>) this, (uint [])array);
+ } else if (t == typeof (int64)) {
+ return add_all_int64_array ((Collection<int64?>) this, (int64? [])array);
+ } else if (t == typeof (uint64)) {
+ return add_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
+ } else if (t == typeof (long)) {
+ return add_all_long_array ((Collection<long>) this, (long [])array);
+ } else if (t == typeof (ulong)) {
+ return add_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
+ } else if (t == typeof (float)) {
+ return add_all_float_array ((Collection<float>) this, (float? [])array);
+ } else if (t == typeof (double)) {
+ return add_all_double_array ((Collection<double>) this, (double? [])array);
+ } else {
+ bool changed = false;
+ foreach (unowned G item in array) {
+ changed |= add (item);
+ }
+ return changed;
+ }
+ }
+
+ /**
+ * Returns ``true`` it this collection contains all items as the input
+ * array.
+ *
+ * @param array the array which items will be compared with
+ * this collection.
+ *
+ * @return ``true`` if the collection has been changed, ``false`` otherwise
+ */
+ [CCode (ordering = 14)]
+ public virtual bool contains_all_array (G[] array) {
+ var t = typeof (G);
+ if (t == typeof (bool)) {
+ return contains_all_bool_array ((Collection<bool>) this, (bool [])array);
+ } else if (t == typeof (char)) {
+ return contains_all_char_array ((Collection<char>) this, (char [])array);
+ } else if (t == typeof (uchar)) {
+ return contains_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
+ } else if (t == typeof (int)) {
+ return contains_all_int_array ((Collection<int>) this, (int [])array);
+ } else if (t == typeof (uint)) {
+ return contains_all_uint_array ((Collection<uint>) this, (uint [])array);
+ } else if (t == typeof (int64)) {
+ return contains_all_int64_array ((Collection<int64?>) this, (int64? [])array);
+ } else if (t == typeof (uint64)) {
+ return contains_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
+ } else if (t == typeof (long)) {
+ return contains_all_long_array ((Collection<long>) this, (long [])array);
+ } else if (t == typeof (ulong)) {
+ return contains_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
+ } else if (t == typeof (float)) {
+ return contains_all_float_array ((Collection<float>) this, (float? [])array);
+ } else if (t == typeof (double)) {
+ return contains_all_double_array ((Collection<double>) this, (double? [])array);
+ } else {
+ foreach (unowned G item in array) {
+ if (!contains (item)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+
+ /**
+ * Removes the subset of items in this collection corresponding to the
+ * elments in the input array. If there is several occurrences of
+ * the same value in this collection they are decremented of the number
+ * of occurrences in the input array.
+ *
+ * @param array the array which items will be compared with
+ * this collection.
+ *
+ * @return ``true`` if the collection has been changed, ``false`` otherwise
+ */
+ [CCode (ordering = 15)]
+ public virtual bool remove_all_array (G[] array) {
+ var t = typeof (G);
+ if (t == typeof (bool)) {
+ return remove_all_bool_array ((Collection<bool>) this, (bool [])array);
+ } else if (t == typeof (char)) {
+ return remove_all_char_array ((Collection<char>) this, (char [])array);
+ } else if (t == typeof (uchar)) {
+ return remove_all_uchar_array ((Collection<uchar>) this, (uchar [])array);
+ } else if (t == typeof (int)) {
+ return remove_all_int_array ((Collection<int>) this, (int [])array);
+ } else if (t == typeof (uint)) {
+ return remove_all_uint_array ((Collection<uint>) this, (uint [])array);
+ } else if (t == typeof (int64)) {
+ return remove_all_int64_array ((Collection<int64?>) this, (int64? [])array);
+ } else if (t == typeof (uint64)) {
+ return remove_all_uint64_array ((Collection<uint64?>) this, (uint64? [])array);
+ } else if (t == typeof (long)) {
+ return remove_all_long_array ((Collection<long>) this, (long [])array);
+ } else if (t == typeof (ulong)) {
+ return remove_all_ulong_array ((Collection<ulong>) this, (ulong [])array);
+ } else if (t == typeof (float)) {
+ return remove_all_float_array ((Collection<float>) this, (float? [])array);
+ } else if (t == typeof (double)) {
+ return remove_all_double_array ((Collection<double>) this, (double? [])array);
+ } else {
+ bool changed = false;
+ foreach (unowned G item in array) {
+ changed |= remove (item);
+ }
+ return changed;
+ }
+ }
+
+ [CCode (ordering = 16)]
+ public virtual bool add_all_iterator (Iterator<G> iter) {
+ bool changed = false;
+ iter.foreach ((val) => {
+ changed |= add (val);
+ return true;
+ });
+ return changed;
+ }
+
+ [CCode (ordering = 17)]
+ public virtual bool contains_all_iterator (Iterator<G> iter) {
+ return iter.foreach ((val) => {return contains (val);});
+ }
+
+ [CCode (ordering = 18)]
+ public virtual bool remove_all_iterator (Iterator<G> iter) {
+ bool changed = false;
+ return iter.foreach ((val) => {
+ changed |= remove (val);
+ return true;
+ });
+ }
+
+ /**
+ * The read-only view of this collection.
+ */
+ [CCode (ordering = 12)]
+ public abstract Collection<G> read_only_view { owned get; }
+
+ /**
+ * Returns an immutable empty collection.
+ *
+ * @return an immutable empty collection
+ */
+ public static Collection<G> empty<G> () {
+ return new HashSet<G> ().read_only_view;
+ }
+
private static bool[] to_bool_array (Collection<bool> coll) {
bool[] array = new bool[coll.size];
int index = 0;
@@ -222,20 +404,20 @@ public interface Vala.Collection<G> : Iterable<G> {
return array;
}
- private static int64[] to_int64_array (Collection<int64?> coll) {
- int64[] array = new int64[coll.size];
+ private static int64?[] to_int64_array (Collection<int64?> coll) {
+ int64?[] array = new int64?[coll.size];
int index = 0;
- foreach (int64 element in coll) {
- array[index++] = element;
+ foreach (int64? element in coll) {
+ array[index++] = (owned)element;
}
return array;
}
- private static uint64[] to_uint64_array (Collection<uint64?> coll) {
- uint64[] array = new uint64[coll.size];
+ private static uint64?[] to_uint64_array (Collection<uint64?> coll) {
+ uint64?[] array = new uint64?[coll.size];
int index = 0;
- foreach (uint64 element in coll) {
- array[index++] = element;
+ foreach (uint64? element in coll) {
+ array[index++] = (owned)element;
}
return array;
}
@@ -261,8 +443,8 @@ public interface Vala.Collection<G> : Iterable<G> {
private static float?[] to_float_array (Collection<float?> coll) {
float?[] array = new float?[coll.size];
int index = 0;
- foreach (float element in coll) {
- array[index++] = element;
+ foreach (float? element in coll) {
+ array[index++] = (owned)element;
}
return array;
}
@@ -270,24 +452,285 @@ public interface Vala.Collection<G> : Iterable<G> {
private static double?[] to_double_array (Collection<double?> coll) {
double?[] array = new double?[coll.size];
int index = 0;
- foreach (double element in coll) {
- array[index++] = element;
+ foreach (double? element in coll) {
+ array[index++] = (owned)element;
}
return array;
}
- /**
- * The read-only view of this collection.
- */
- public abstract Collection<G> read_only_view { owned get; }
+ private static bool add_all_bool_array (Collection<bool> coll, bool[] arr) {
+ bool changed = false;
+ foreach (bool el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
- /**
- * Returns an immutable empty collection.
- *
- * @return an immutable empty collection
- */
- public static Collection<G> empty<G> () {
- return new HashSet<G> ().read_only_view;
+ private static bool add_all_char_array (Collection<char> coll, char[] arr) {
+ bool changed = false;
+ foreach (char el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
+ bool changed = false;
+ foreach (uchar el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_int_array (Collection<int> coll, int[] arr) {
+ bool changed = false;
+ foreach (int el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_uint_array (Collection<uint> coll, uint[] arr) {
+ bool changed = false;
+ foreach (uint el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_int64_array (Collection<int64?> coll, int64?[] arr) {
+ bool changed = false;
+ foreach (unowned int64? el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
+ bool changed = false;
+ foreach (unowned uint64? el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_long_array (Collection<long> coll, long[] arr) {
+ bool changed = false;
+ foreach (long el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
+ bool changed = false;
+ foreach (ulong el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_float_array (Collection<float?> coll, float?[] arr) {
+ bool changed = false;
+ foreach (unowned float? el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool add_all_double_array (Collection<double?> coll, double?[] arr) {
+ bool changed = false;
+ foreach (unowned double? el in arr) {
+ changed |= coll.add (el);
+ }
+ return changed;
+ }
+
+ private static bool contains_all_bool_array (Collection<bool> coll, bool[] arr) {
+ foreach (bool el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_char_array (Collection<char> coll, char[] arr) {
+ foreach (char el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
+ foreach (uchar el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_int_array (Collection<int> coll, int[] arr) {
+ foreach (int el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_uint_array (Collection<uint> coll, uint[] arr) {
+ foreach (uint el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_int64_array (Collection<int64?> coll, int64?[] arr) {
+ foreach (unowned int64? el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
+ foreach (unowned uint64? el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_long_array (Collection<long> coll, long[] arr) {
+ foreach (long el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
+ foreach (ulong el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_float_array (Collection<float?> coll, float?[] arr) {
+ foreach (unowned float? el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool contains_all_double_array (Collection<double?> coll, double?[] arr) {
+ foreach (unowned double? el in arr) {
+ if (!coll.contains (el)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ private static bool remove_all_bool_array (Collection<bool> coll, bool[] arr) {
+ bool changed = false;
+ foreach (bool el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_char_array (Collection<char> coll, char[] arr) {
+ bool changed = false;
+ foreach (char el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_uchar_array (Collection<uchar> coll, uchar[] arr) {
+ bool changed = false;
+ foreach (uchar el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_int_array (Collection<int> coll, int[] arr) {
+ bool changed = false;
+ foreach (int el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_uint_array (Collection<uint> coll, uint[] arr) {
+ bool changed = false;
+ foreach (uint el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_int64_array (Collection<int64?> coll, int64?[] arr) {
+ bool changed = false;
+ foreach (unowned int64? el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_uint64_array (Collection<uint64?> coll, uint64?[] arr) {
+ bool changed = false;
+ foreach (unowned uint64? el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_long_array (Collection<long> coll, long[] arr) {
+ bool changed = false;
+ foreach (long el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_ulong_array (Collection<ulong> coll, ulong[] arr) {
+ bool changed = false;
+ foreach (ulong el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_float_array (Collection<float?> coll, float?[] arr) {
+ bool changed = false;
+ foreach (unowned float? el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
+ }
+
+ private static bool remove_all_double_array (Collection<double?> coll, double?[] arr) {
+ bool changed = false;
+ foreach (unowned double? el in arr) {
+ changed |= coll.remove (el);
+ }
+ return changed;
}
}
diff --git a/gee/comparable.vala b/gee/comparable.vala
index 489a7c8..8520ad2 100644
--- a/gee/comparable.vala
+++ b/gee/comparable.vala
@@ -24,6 +24,18 @@
* This interface defines a total ordering among instances of each class
* implementing it.
*
+ * In other words:
+ *
+ * * It's irreflexive: For all `a` it holds that `a.compare_to(a) == 0`
+ * * It's transitive: For all `a`, `b` and `c` if `a.compare_to(b) < 0` and
+ * `b.compare_to(c) < 0` then `a.compare_to(c) < 0`.
+ * * It's trichotomous: For all `a` and `b` it holds that
+ * `a.compare_to(b) = -b.compare_to(a)`.
+ *
+ * Note: The relationship must be immutable. In other words if at one point of
+ * program `a.compare_to(b)` had certain value then call `a.compare_to(b)`
+ * //must always// return the original value until end of `a` and `b` lifetime.
+ *
* @see Hashable
*/
public interface Vala.Comparable<G> : Object {
diff --git a/gee/concurrentlist.vala b/gee/concurrentlist.vala
index 485e2d2..e020375 100644
--- a/gee/concurrentlist.vala
+++ b/gee/concurrentlist.vala
@@ -1,6 +1,6 @@
/* concurrentlist.vala
*
- * Copyright (C) 2011 Maciej Piechotka
+ * Copyright (C) 2011-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -25,7 +25,7 @@
* [[http://www.cse.yorku.ca/~ruppert/papers/lfll.pdf|Mikhail Fomitchev and Eric Ruppert paper ]].
*
* Many threads are allowed to operate on the same structure as well as modification
- * of structure during iteration is allowed. However the change may not be immidiatly
+ * of structure during iteration is allowed. However the change may not be immediately
* visible to other threads.
*/
public class Vala.ConcurrentList<G> : AbstractList<G> {
@@ -33,7 +33,12 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
* The elements' equality testing function.
*/
[CCode (notify = false)]
- public Vala.EqualDataFunc<G> equal_func { private set; get; }
+ public Vala.EqualDataFunc<G> equal_func {
+ private set {}
+ get {
+ return _equal_func.func;
+ }
+ }
/**
* Construct new, empty single linked list
@@ -44,15 +49,23 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
* @param equal_func an optional element equality testing function
*/
public ConcurrentList (owned Vala.EqualDataFunc<G>? equal_func = null) {
- if (equal_func == null)
+ if (equal_func == null) {
equal_func = Vala.Functions.get_equal_func_for (typeof (G));
- this.equal_func = (owned)equal_func;
+ }
+ _equal_func = new Functions.EqualDataFuncClosure<G>((owned)equal_func);
+ _head = new Node<G>.head ();
+ HazardPointer.set_pointer<Node<G>> (&_tail, _head);
+ }
+
+ internal ConcurrentList.with_closure (owned Functions.EqualDataFuncClosure<G> equal_func) {
+ _equal_func = (owned)equal_func;
_head = new Node<G>.head ();
HazardPointer.set_pointer<Node<G>> (&_tail, _head);
}
~ConcurrentList () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
_head = null;
HazardPointer.set_pointer<Node<G>?> (&_tail, null);
}
@@ -72,6 +85,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
public override int size {
get {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
int result = 0;
for (var iter = iterator (); iter.next ();)
result++;
@@ -93,6 +107,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override bool contains (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
for (var iter = iterator (); iter.next ();)
if (equal_func (item, iter.get ()))
return true;
@@ -104,6 +119,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override bool add (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
Node<G> node = new Node<G> (item);
node.insert (get_tail (), null);
return true;
@@ -114,6 +130,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override bool remove (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
Vala.Iterator<G> iter = iterator ();
while (iter.next ()) {
if (equal_func (item, iter.get ())) {
@@ -129,6 +146,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override void clear () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
var iter = iterator ();
while (iter.next ())
iter.remove ();
@@ -154,6 +172,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override G? get (int index) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (index >= 0);
for (var iterator = iterator (); iterator.next ();)
if (index-- == 0)
@@ -166,6 +185,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override void set (int index, G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (index >= 0);
for (var iterator = list_iterator (); iterator.next ();) {
if (index-- == 0) {
@@ -181,6 +201,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override int index_of (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
int index = 0;
for (var iterator = list_iterator (); iterator.next (); index++)
if (equal_func (item, iterator.get ()))
@@ -193,6 +214,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override void insert (int index, G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (index >= 0);
if (index == 0) {
var prev = _head;
@@ -215,6 +237,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override G remove_at (int index) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
for (var iterator = list_iterator (); iterator.next ();) {
if (index-- == 0) {
G data = iterator.get ();
@@ -230,9 +253,10 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
*/
public override List<G>? slice (int start, int end) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (0 <= start);
assert (start <= end);
- var list = new ConcurrentList<G> (equal_func);
+ var list = new ConcurrentList<G>.with_closure (_equal_func);
var iterator = iterator ();
int idx = 0;
for (; iterator.next (); idx++)
@@ -258,25 +282,32 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
private Node<G> _head;
private Node<G> *_tail;
+ private Functions.EqualDataFuncClosure<G> _equal_func;
private class Iterator<G> : Object, Vala.Traversable<G>, Vala.Iterator<G>, ListIterator<G> {
public Iterator (Node<G> head) {
- _started = false;
_removed = false;
_index = -1;
_prev = null;
_curr = head;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _removed = iter._removed;
+ _index = iter._index;
+ _prev = iter._prev;
+ _curr = iter._curr;
+ }
+
public bool next () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
Node<G>? _old_prev = _removed ? _prev : null;
bool success = Node.proceed<G> (ref _prev, ref _curr);
if (success) {
if (_removed)
- _prev = _old_prev;
+ _prev = (owned)_old_prev;
_removed = false;
- _started = true;
_index++;
}
return success;
@@ -284,19 +315,22 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
public bool has_next () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
Node<G>? prev = _prev;
- Node<G>? curr = _curr;
+ Node<G> curr = _curr;
return Node.proceed<G> (ref prev, ref curr);
}
public new G get () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (valid);
return HazardPointer.get_pointer<G> (&_curr._data);
}
public new void set (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (valid);
#if DEBUG
G item_copy = item;
@@ -309,6 +343,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
public void remove () {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (valid);
_curr.remove (_prev);
_removed = true;
@@ -316,7 +351,10 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
}
public bool valid {
- get { return _started && !_removed && _curr != null; }
+ get {
+ assert (_curr != null);
+ return _prev != null && !_removed;
+ }
}
public bool read_only { get { return false; } }
@@ -328,6 +366,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
public void add (G item) {
HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
assert (valid);
if (!Node.proceed<G> (ref _prev, ref _curr)) {
_prev = (owned)_curr;
@@ -337,11 +376,13 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
new_node.insert (_prev, _curr);
_curr = (owned)new_node;
_index++;
+ _removed = false;
}
public new bool foreach (ForallFunc<G> f) {
HazardPointer.Context ctx = new HazardPointer.Context ();
- if (_started && !_removed) {
+ Utils.Misc.unused (ctx);
+ if (_prev != null && !_removed) {
if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
return false;
}
@@ -349,9 +390,8 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
Node<G>? _old_prev = _removed ? _prev : null;
while (Node.proceed<G> (ref _prev, ref _curr)) {
if (_removed)
- _prev = _old_prev;
+ _prev = (owned)_old_prev;
_removed = false;
- _started = true;
_index++;
if (!f (HazardPointer.get_pointer<G> (&_curr._data))) {
return false;
@@ -360,11 +400,23 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
return true;
}
- private bool _started;
- private bool _removed;
- private int _index;
- private Node<G> _prev;
- private Node<G>? _curr;
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected bool _removed;
+ protected int _index;
+ protected Node<G>? _prev;
+ protected Node<G> _curr;
}
private class Node<G> {
@@ -463,7 +515,7 @@ public class Vala.ConcurrentList<G> : AbstractList<G> {
}
search_for<G> (next, ref prev);
}
-
+
}
public inline void help_flagged (Node<G> prev) {
diff --git a/gee/concurrentset.vala b/gee/concurrentset.vala
new file mode 100644
index 0000000..bbf784f
--- /dev/null
+++ b/gee/concurrentset.vala
@@ -0,0 +1,1446 @@
+/* concurrentset.vala
+ *
+ * Copyright (C) 2012-2014 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+/**
+ * A skip-linked list. This implementation is based on
+ * [[http://www.cse.yorku.ca/~ruppert/Mikhail.pdf|Mikhail Fomitchev Master Thesis]].
+ *
+ * Many threads are allowed to operate on the same structure as well as modification
+ * of structure during iteration is allowed. However the change may not be immidiatly
+ * visible to other threads.
+ */
+public class Vala.ConcurrentSet<G> : AbstractSortedSet<G> {
+ public ConcurrentSet (owned CompareDataFunc<G>? compare_func = null) {
+ if (compare_func == null) {
+ compare_func = Functions.get_compare_func_for (typeof (G));
+ }
+ _cmp = (owned)compare_func;
+ _head = new Tower<G>.head ();
+ }
+
+ ~ConcurrentSet () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ _head = null;
+ }
+
+ public override int size { get { return GLib.AtomicInt.get (ref _size); } }
+
+ public override bool read_only { get { return false; } }
+
+ public override Vala.Iterator<G> iterator () {
+ return new Iterator<G> (this, _head);
+ }
+
+ public override bool contains (G key) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _head;
+ return Tower.search<G> (_cmp, key, ref prev, null);
+ }
+
+ public override bool add (G key) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Rand *rnd = rand.get ();
+ if (rnd == null) {
+ rand.set (rnd = new Rand ());
+ }
+ uint32 rand_int = rnd->int_range (0, int32.MAX);
+ uint8 height = 1 + (uint8)GLib.Bit.nth_lsf (~rand_int, -1);
+ TowerIter<G> prev = TowerIter<G>();
+ prev._iter[height - 1] = _head;
+ if (Tower.search<G> (_cmp, key, ref prev._iter[height - 1], null, height - 1)) {
+ return false;
+ }
+ for (int i = height - 2; i >= 0; i--) {
+ prev._iter[i] = prev._iter[height - 1];
+ }
+ Tower<G>? result = Tower.insert<G> (_cmp, ref prev, key, height - 1);
+ if (result != null) {
+ GLib.AtomicInt.inc (ref _size);
+ }
+ return result != null;
+ }
+
+ public override bool remove (G item) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ TowerIter<G> prev = TowerIter<G>();
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ prev._iter[i] = _head;
+ }
+ bool result = Tower.remove_key<G> (_cmp, ref prev, item);
+ if (result) {
+ GLib.AtomicInt.dec_and_test (ref _size);
+ }
+ return result;
+ }
+
+ public override void clear () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? first;
+ while ((first = _head.get_next (0)) != null) {
+ remove (first._data);
+ }
+ }
+
+ public override G first () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? prev = null;
+ Tower<G> curr = _head;
+ if (Tower.proceed<G> (_cmp, ref prev, ref curr, 0)) {
+ return curr._data;
+ } else {
+ return null;
+ }
+ }
+
+ public override G last () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? prev = null;
+ Tower<G> curr = _head;
+ bool found = false;
+ for (int i = _MAX_HEIGHT; i >= 0; i--) {
+ while (Tower.proceed<G> (_cmp, ref prev, ref curr, 0)) {
+ found = true;
+ }
+ }
+ if (!found) {
+ return null;
+ }
+ return curr._data;
+ }
+
+ public override Vala.Iterator<G>? iterator_at (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ TowerIter<G> prev = TowerIter<G> ();
+ TowerIter<G> curr;
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ prev._iter[i] = _head;
+ }
+ if (!Tower.search_from_bookmark<G> (_cmp, element, ref prev, out curr)) {
+ return null;
+ }
+ return new Iterator<G>.point_at (this, ref prev, curr._iter[0]);
+ }
+
+ public override G? lower (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _head;
+ Tower.search<G> (_cmp, element, ref prev);
+ if (prev == _head) {
+ return null;
+ }
+ return prev._data;
+ }
+
+ public override G? higher (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _head;
+ Tower<G>? next;
+ if (Tower.search<G> (_cmp, element, ref prev, out next)) {
+ if (!Tower.proceed<G> (_cmp, ref prev, ref next, 0)) {
+ return null;
+ }
+ }
+ if (next == null) {
+ return null;
+ }
+ return next._data;
+ }
+
+ public override G? floor (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _head;
+ Tower<G>? next;
+ if (Tower.search<G> (_cmp, element, ref prev, out next)) {
+ return next._data;
+ } else if (prev != _head) {
+ return prev._data;
+ } else {
+ return null;
+ }
+ }
+
+ public override G? ceil (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _head;
+ Tower<G>? next;
+ Tower.search<G> (_cmp, element, ref prev, out next);
+ if (next == null) {
+ return null;
+ }
+ return next._data;
+ }
+
+ public override SortedSet<G> head_set (G before) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (new Range<G>.head (this, before));
+ }
+
+ public override SortedSet<G> tail_set (G after) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (new Range<G>.tail (this, after));
+ }
+ public override SortedSet<G> sub_set (G from, G to) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (new Range<G> (this, from, to));
+ }
+
+ private unowned G max (G a, G b, out bool changed = null) {
+ changed = _cmp (a, b) < 0;
+ return changed ? b : a;
+ }
+
+ private unowned G min (G a, G b, out bool changed = null) {
+ changed = _cmp (a, b) > 0;
+ return changed ? b : a;
+ }
+
+#if DEBUG
+ public void dump () {
+ for (int i = _MAX_HEIGHT - 1; i >= 0; i--) {
+ bool printed = false;
+ Tower<G>? curr = _head;
+ State state;
+ while ((curr = curr.get_succ (out state, (uint8)i)) != null) {
+ if (!printed) {
+ stderr.printf("Level %d\n", i);
+ printed = true;
+ }
+ stderr.printf(" Node %p%s - %s\n", curr, state == State.NONE ? "" : state
== State.MARKED ? " (MARKED)" : " (FLAGGED)", (string)curr._data);
+ assert (curr._height > i);
+ }
+ }
+ }
+#endif
+
+ private int _size = 0;
+ private Tower<G> _head;
+ private CompareDataFunc<G>? _cmp;
+ private const int _MAX_HEIGHT = 31;
+ private static Private rand = new Private((ptr) => {
+ Rand *rnd = (Rand *)ptr;
+ delete rnd;
+ });
+
+ private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G> {
+ public Iterator (ConcurrentSet cset, Tower<G> head) {
+ _curr = head;
+ _set = cset;
+ assert (_curr != null);
+ }
+
+ public Iterator.point_at (ConcurrentSet cset, ref TowerIter<G> prev, Tower<G> curr) {
+ _curr = curr;
+ _set = cset;
+ _prev = prev;
+ assert (_curr != null);
+ }
+
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _curr = iter._curr;
+ _set = iter._set;
+ _prev = iter._prev;
+ _removed = iter._removed;
+ }
+
+ public new bool foreach (ForallFunc<G> f) {
+ assert (_curr != null);
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (_prev._iter[0] != null && !_removed) {
+ if (!f (_curr._data)) {
+ assert (_curr != null);
+ return false;
+ }
+ }
+ Tower<G> new_prev = _prev._iter[0];
+ Tower<G>? new_curr = _curr;
+ while (Tower.proceed<G> (_set._cmp, ref new_prev, ref new_curr, 0)) {
+ assert (_curr != null);
+ if (!_removed) {
+ //FIXME: Help mark/delete on the way
+ _prev._iter[0] = new_prev;
+ int prev_height = _prev._iter[0].get_height();
+ for (int i = 1; i < prev_height; i++) {
+ _prev._iter[i] = _prev._iter[0];
+ }
+ }
+ _curr = new_curr;
+ _removed = false;
+ if (!f (_curr._data)) {
+ assert (_curr != null);
+ return false;
+ }
+ }
+ assert (_curr != null);
+ return true;
+ }
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ public bool next () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? new_prev = _prev._iter[0];
+ Tower<G>? new_curr = _curr;
+ bool success = Tower.proceed<G> (_set._cmp, ref new_prev, ref new_curr, 0);
+ if (success) {
+ if (!_removed) {
+ //FIXME: Help mark/delete on the way
+ _prev._iter[0] = (owned)new_prev;
+ int prev_height = _prev._iter[0].get_height();
+ for (int i = 1; i < prev_height; i++) {
+ _prev._iter[i] = _prev._iter[0];
+ }
+ }
+ _curr = (owned)new_curr;
+ _removed = false;
+ }
+ assert (_curr != null);
+ return success;
+ }
+
+ public bool has_next () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G> prev = _prev._iter[0];
+ Tower<G>? curr = _curr;
+ return Tower.proceed<G> (_set._cmp, ref prev, ref curr, 0);
+ }
+
+ public new G get () {
+ assert (valid);
+ return _curr._data;
+ }
+
+ public void remove () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ assert (valid);
+ if (Tower.remove<G> (_set._cmp, ref _prev, _curr)) {
+ AtomicInt.dec_and_test (ref _set._size);
+ }
+ _removed = true;
+ }
+
+ public bool valid { get { return _prev._iter[0] != null && !_removed; } }
+
+ public bool read_only { get { return true; } }
+
+ protected bool _removed = false;
+ protected ConcurrentSet<G> _set;
+ protected TowerIter<G> _prev;
+ protected Tower<G> _curr;
+ }
+
+ private class SubSet<G> : AbstractSortedSet<G> {
+ public override int size {
+ get {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? curr;
+ Range.improve_bookmark<G> (_range, out curr);
+ if (curr != null) {
+ int acc = 1;
+ Tower<G>? prev = HazardPointer.get_pointer<Tower<G>>
(&_range._bookmark._iter[0]);
+ while (Range.proceed<G> (_range, ref prev, ref curr, 0)) {
+ acc++;
+ }
+ return acc;
+ } else {
+ return 0;
+ }
+ }
+ }
+
+ public bool is_empty {
+ get {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? curr;
+ Range.improve_bookmark<G> (_range, out curr);
+ return curr != null;
+ }
+ }
+
+ public override bool read_only { get { return false; } }
+
+ public SubSet (Range<G> range) {
+ _range = range;
+ }
+
+ public override Vala.Iterator<G> iterator () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubIterator<G> (_range);
+ }
+
+ public override bool contains (G item) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (!Range.inside<G> (_range, item)) {
+ return false;
+ }
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ return Tower.search_from_bookmark<G> (_range._set._cmp, item, ref prev);
+ }
+
+ public override bool add (G key) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (!Range.inside<G> (_range, key)) {
+ return false;
+ }
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ Rand *rnd = ConcurrentSet.rand.get ();
+ if (rnd == null) {
+ rand.set (rnd = new Rand ());
+ }
+ uint32 rand_int = rnd->int_range (0, int32.MAX);
+ uint8 height = 1 + (uint8)GLib.Bit.nth_lsf (~rand_int, -1);
+ if (Tower.search_from_bookmark<G> (_range._set._cmp, key, ref prev, null, height -
1)) {
+ return false;
+ }
+ for (int i = height - 2; i >= 0; i--) {
+ prev._iter[i] = prev._iter[height - 1];
+ }
+ Tower<G>? result = Tower.insert<G> (_range._set._cmp, ref prev, key, height - 1);
+ if (result != null) {
+ GLib.AtomicInt.inc (ref _range._set._size);
+ }
+ return result != null;
+ }
+
+ public override bool remove (G key) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (!Range.inside<G> (_range, key)) {
+ return false;
+ }
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ // FIXME: Use full bookmark
+ bool result = Tower.remove_key<G> (_range._set._cmp, ref prev, key);
+ if (result) {
+ GLib.AtomicInt.dec_and_test (ref _range._set._size);
+ }
+ return result;
+ }
+
+ public override void clear () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ TowerIter<G> prev;
+ Tower<G>? first;
+ Range.improve_bookmark<G> (_range, out first, out prev);
+ while (first != null) {
+ Tower.remove<G> (_range._set._cmp, ref prev, first);
+ Range.improve_bookmark<G> (_range, out first, out prev);
+ }
+ }
+
+ public override G? first () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ Tower<G>? first;
+ Range.improve_bookmark<G> (_range, out first);
+ if (first == null) {
+ return null;
+ }
+ return first._data;
+ }
+
+ public override G? last () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ Tower<G>? curr = null;
+ for (int i = _MAX_HEIGHT - 1; i >= 0; i--) {
+ if (curr == null) {
+ curr = prev._iter[i].get_next ((uint8)i);
+ if (curr == null || !Range.inside<G> (_range, curr._data)) {
+ curr = null;
+ continue;
+ }
+ }
+ bool improved = false;
+ while (Range.proceed<G> (_range, ref prev._iter[i], ref curr, (uint8)i)) {
+ improved = true;
+ }
+ if (improved && i > 0) {
+ prev._iter[i - 1] = prev._iter[i];
+ }
+ }
+ if (curr == null) {
+ return null;
+ }
+ return curr._data;
+ }
+
+ public override Vala.Iterator<G>? iterator_at (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (!Range.inside<G> (_range, element)) {
+ return null;
+ }
+ TowerIter<G> prev;
+ TowerIter<G> next;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ if (!Tower.search_from_bookmark<G> (_range._set._cmp, element, ref prev, out next)) {
+ return null;
+ }
+ return new SubIterator<G>.point_at (_range, ref prev, next._iter[0]);
+ }
+
+ public override G? lower (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ switch (Range.cmp<G> (_range, element)) {
+ case Range.Position.BEFORE:
+ case Range.Position.EMPTY:
+ return null;
+ case Range.Position.INSIDE:
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ Tower.search_from_bookmark<G> (_range._set._cmp, element, ref prev);
+ if (prev._iter[0] == _range._set._head || !Range.inside (_range,
prev._iter[0]._data)) {
+ return null;
+ }
+ return prev._iter[0]._data;
+ case Range.Position.AFTER:
+ return last ();
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public override G? higher (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ switch (Range.cmp<G> (_range, element)) {
+ case Range.Position.BEFORE:
+ return first ();
+ case Range.Position.INSIDE:
+ TowerIter<G> prev;
+ TowerIter<G> curr;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ if (Tower.search_from_bookmark<G> (_range._set._cmp, element, ref prev, out
curr)) {
+ if (!Tower.proceed<G> (_range._set._cmp, ref prev._iter[0], ref
curr._iter[0], 0)) {
+ return null;
+ }
+ }
+ if (curr._iter[0] == null || !Range.inside(_range, curr._iter[0]._data)) {
+ return null;
+ }
+ return curr._iter[0]._data;
+ case Range.Position.AFTER:
+ case Range.Position.EMPTY:
+ return null;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public override G? floor (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ switch (Range.cmp<G> (_range, element)) {
+ case Range.Position.BEFORE:
+ case Range.Position.EMPTY:
+ return null;
+ case Range.Position.INSIDE:
+ TowerIter<G> curr;
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ if (!Tower.search_from_bookmark<G> (_range._set._cmp, element, ref prev, out
curr)) {
+ curr._iter[0] = (owned)prev._iter[0];
+ }
+ if (curr._iter[0] == null || curr._iter[0].is_head () ||
!Range.inside(_range, curr._iter[0]._data)) {
+ return null;
+ }
+ return curr._iter[0]._data;
+ case Range.Position.AFTER:
+ return last ();
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public override G? ceil (G element) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ switch (Range.cmp<G> (_range, element)) {
+ case Range.Position.BEFORE:
+ return first ();
+ case Range.Position.INSIDE:
+ TowerIter<G> curr;
+ TowerIter<G> prev;
+ Range.improve_bookmark<G> (_range, null, out prev);
+ Tower.search_from_bookmark<G> (_range._set._cmp, element, ref prev, out curr);
+ if (curr._iter[0] == null || !Range.inside(_range, curr._iter[0]._data)) {
+ return null;
+ }
+ return curr._iter[0]._data;
+ case Range.Position.AFTER:
+ case Range.Position.EMPTY:
+ return null;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public override SortedSet<G> head_set (G before) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (Range.cut_tail (_range, before));
+ }
+
+ public override SortedSet<G> tail_set (G after) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (Range.cut_head (_range, after));
+ }
+
+ public override SortedSet<G> sub_set (G from, G to) {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ return new SubSet<G> (Range.cut (_range, from, to));
+ }
+
+ private Range<G> _range;
+ }
+
+ private class SubIterator<G> : Object, Traversable<G>, Vala.Iterator<G> {
+ public SubIterator (Range<G> range) {
+ Range.improve_bookmark<G> (range);
+ _range = range;
+ }
+
+ public SubIterator.point_at (Range<G> range, ref TowerIter<G> prev, owned Tower<G> curr) {
+ Range.improve_bookmark<G> (range);
+ _range = range;
+ _prev = prev;
+ _curr = curr;
+ }
+
+ public SubIterator.from_iterator (SubIterator<G> iter) {
+ Range.improve_bookmark<G> (iter._range);
+ _range = iter._range;
+ _prev = iter._prev;
+ _curr = iter._curr;
+ _removed = iter._removed;
+ }
+
+ public new bool foreach (ForallFunc<G> f) {
+ assert (_curr != null);
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (!begin ()) {
+ return true;
+ }
+ if (_prev._iter[0] != null && !_removed) {
+ if (!f (_curr._data)) {
+ assert (_curr != null);
+ return false;
+ }
+ }
+ Tower<G> new_prev = _prev._iter[0];
+ Tower<G>? new_curr = _curr;
+ while (Range.proceed<G> (_range, ref new_prev, ref new_curr, 0)) {
+ assert (_curr != null);
+ if (!f (_curr._data)) {
+ assert (_curr != null);
+ return false;
+ }
+ if (!_removed) {
+ //FIXME: Help mark/delete on the way
+ _prev._iter[0] = (owned)new_prev;
+ int prev_height = _prev._iter[0].get_height();
+ for (int i = 1; i < prev_height; i++) {
+ _prev._iter[i] = _prev._iter[0];
+ }
+ }
+ _curr = (owned)new_curr;
+ _removed = false;
+ }
+ assert (_curr != null);
+ return true;
+ }
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new SubIterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ public bool next () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (_prev._iter[0] == null) {
+ return begin ();
+ } else {
+ Tower<G> new_prev = _prev._iter[0];
+ Tower<G> new_curr = _curr;
+ if (Range.proceed<G> (_range, ref new_prev, ref new_curr, 0)) {
+ if (!_removed) {
+ //FIXME: Help mark/delete on the way
+ _prev._iter[0] = (owned)new_prev;
+ int prev_height = _prev._iter[0].get_height();
+ for (int i = 1; i < prev_height; i++) {
+ _prev._iter[i] = _prev._iter[0];
+ }
+ }
+ _curr = (owned)new_curr;
+ _removed = false;
+ return true;
+ } else {
+ return false;
+ }
+ }
+ }
+
+ public bool has_next () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ if (_prev._iter[0] == null) {
+ Tower<G> next;
+ Range.improve_bookmark<G> (_range, out next);
+ if (next != null && Range.beyond<G> (_range, next)) {
+ next = null;
+ }
+ return next != null;
+ } else {
+ Tower<G> new_prev = _prev._iter[0];
+ Tower<G> new_curr = _curr;
+ return Range.proceed<G> (_range, ref new_prev, ref new_curr, 0);
+ }
+ }
+
+ public new G get () {
+ assert (valid);
+ return _curr._data;
+ }
+
+ public void remove () {
+ HazardPointer.Context ctx = new HazardPointer.Context ();
+ Utils.Misc.unused (ctx);
+ assert (valid);
+ if (Tower.remove<G> (_range._set._cmp, ref _prev, _curr)) {
+ AtomicInt.dec_and_test (ref _range._set._size);
+ }
+ _removed = true;
+ }
+
+ public bool valid {
+ get {
+ bool is_valid = _prev._iter[0] != null && !_removed;
+ assert (!is_valid || _curr != null);
+ return is_valid;
+ }
+ }
+
+ public bool read_only { get { return false; } }
+
+ private bool begin () {
+ if (_prev._iter[0] != null) {
+ return true;
+ }
+ Range.improve_bookmark<G> (_range, out _curr, out _prev);
+ if (_curr == null) {
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ _prev._iter[i] = null;
+ }
+ }
+ return _curr != null;
+ }
+
+ protected Range<G> _range;
+ protected TowerIter<G> _prev;
+ protected Tower<G>? _curr = null;
+ protected bool _removed = false;
+ }
+
+ private class Range<G> {
+ public G? _start;
+ public G? _end;
+ public RangeType _type;
+ public TowerIter<G> _bookmark;
+ public ConcurrentSet<G> _set;
+
+ public Range (ConcurrentSet<G> cset, G start, G end) {
+ _start = start;
+ _end = end;
+ if (cset._cmp(start, end) < 0) {
+ _type = RangeType.BOUNDED;
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ _bookmark._iter[i] = cset._head;
+ }
+ } else {
+ _type = RangeType.EMPTY;
+ }
+ _set = cset;
+ }
+
+ public Range.head (ConcurrentSet<G> cset, G end) {
+ _end = end;
+ _type = RangeType.HEAD;
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ _bookmark._iter[i] = cset._head;
+ }
+ _set = cset;
+ }
+
+ public Range.tail (ConcurrentSet<G> cset, G start) {
+ _start = start;
+ _type = RangeType.TAIL;
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ _bookmark._iter[i] = cset._head;
+ }
+ _set = cset;
+ }
+
+ public Range.empty (ConcurrentSet<G> cset) {
+ _type = RangeType.EMPTY;
+ _set = cset;
+ }
+
+ private void copy_bookmark (Range<G> range) {
+ for (int i = 0; i < _MAX_HEIGHT; i++) {
+ _bookmark._iter[i] = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[i]);
+ }
+ }
+
+ public static Range<G> cut_head<G> (Range<G> from, G start) {
+ Range<G> result = new Range<G>.empty (from._set);
+ switch (from._type) {
+ case RangeType.HEAD:
+ if (from._set._cmp (start, from._end) < 0) {
+ result._start = start;
+ result._end = from._end;
+ result._type = RangeType.BOUNDED;
+ } else {
+ result._type = RangeType.EMPTY;
+ }
+ break;
+ case RangeType.TAIL:
+ result._start = from._set.max (from._start, start);
+ result._type = RangeType.TAIL;
+ break;
+ case RangeType.BOUNDED:
+ if (from._set._cmp (from._start, start) < 0) {
+ result._start = from._set.max (from._start, start);
+ result._end = from._end;
+ result._type = RangeType.BOUNDED;
+ } else {
+ result._type = RangeType.EMPTY;
+ }
+ break;
+ case RangeType.EMPTY:
+ result._type = RangeType.EMPTY;
+ break;
+ default:
+ assert_not_reached ();
+ }
+ if (result._type != RangeType.EMPTY) {
+ improve_bookmark<G> (from);
+ result.copy_bookmark (from);
+ improve_bookmark<G> (result);
+ }
+ return result;
+ }
+
+ public static Range<G> cut_tail<G> (Range<G> from, G end) {
+ Range<G> result = new Range<G>.empty (from._set);
+ switch (from._type) {
+ case RangeType.HEAD:
+ result._end = from._set.min (from._end, end);
+ result._type = RangeType.HEAD;
+ break;
+ case RangeType.TAIL:
+ if (from._set._cmp (from._start, end) < 0) {
+ result._start = from._start;
+ result._end = end;
+ result._type = RangeType.BOUNDED;
+ } else {
+ result._type = RangeType.EMPTY;
+ }
+ break;
+ case RangeType.BOUNDED:
+ if (from._set._cmp (from._start, end) < 0) {
+ result._start = from._start;
+ result._end = from._set.min (from._end, end);
+ result._type = RangeType.BOUNDED;
+ } else {
+ result._type = RangeType.EMPTY;
+ }
+ break;
+ case RangeType.EMPTY:
+ result._type = RangeType.EMPTY;
+ break;
+ default:
+ assert_not_reached ();
+ }
+ if (result._type != RangeType.EMPTY) {
+ improve_bookmark<G> (from);
+ result.copy_bookmark (from);
+ improve_bookmark<G> (result);
+ }
+ return result;
+ }
+
+ public static Range<G> cut<G> (Range<G> from, G start, G end) {
+ Range<G> result = new Range<G>.empty (from._set);
+ result._type = RangeType.BOUNDED;
+ switch (from._type) {
+ case RangeType.HEAD:
+ end = from._set.min (from._end, end);
+ break;
+ case RangeType.TAIL:
+ start = from._set.max (from._start, start);
+ break;
+ case RangeType.BOUNDED:
+ start = from._set.max (from._start, start);
+ end = from._set.min (from._end, end);
+ break;
+ case RangeType.EMPTY:
+ result._type = RangeType.EMPTY;
+ break;
+ default:
+ assert_not_reached ();
+ }
+ if (result._type != RangeType.EMPTY && from._set._cmp (start, end) < 0) {
+ result._start = start;
+ result._end = end;
+ result._type = RangeType.BOUNDED;
+ } else {
+ result._type = RangeType.EMPTY;
+ }
+ if (result._type != RangeType.EMPTY) {
+ improve_bookmark<G> (from);
+ result.copy_bookmark (from);
+ improve_bookmark<G> (result);
+ }
+ return result;
+ }
+
+ public static void improve_bookmark<G> (Range<G> range, out Tower<G>? out_curr = null, out
TowerIter<G> prev = null) {
+ prev = TowerIter<G>();
+ out_curr = null;
+ switch (range._type) {
+ case RangeType.HEAD:
+ if (&out_curr != null) {
+ out_curr = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[0]);
+ if (&prev != null) {
+ prev._iter[0] = (owned)out_curr;
+ out_curr = prev._iter[0].get_next (0);
+ } else {
+ out_curr = out_curr.get_next (0);
+ }
+ }
+ if (&prev != null) {
+ for (int i = &out_curr != null ? 1 : 0; i < _MAX_HEIGHT; i++) {
+ prev._iter[i] = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[i]);
+ }
+ }
+ break;
+ case RangeType.EMPTY:
+ out_curr = null;
+ break;
+ case RangeType.TAIL:
+ case RangeType.BOUNDED:
+ Tower<G>? last_best = null;
+ for (int i = _MAX_HEIGHT - 1; i >= 0; i--) {
+ Tower<G> curr = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[i]);
+ Tower<G> curr_old = curr;
+ assert (curr != null);
+ Tower.backtrace<G> (ref curr, (uint8)i);
+ if (last_best != null && last_best != curr && Tower.compare<G>
(range._set._cmp, curr, last_best) < 0) {
+ curr = last_best;
+ }
+ if (curr != curr_old) {
+ if (!HazardPointer.compare_and_exchange_pointer<Tower<G>>
(&range._bookmark._iter[i], curr_old, curr)) {
+ curr = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[i]);
+ }
+ }
+ Tower<G> next = curr.get_next ((uint8)i);
+ if (&out_curr != null && i == 0) {
+ out_curr = next;
+ }
+ while (next != null && Tower.compare_data<G> (range._set._cmp, next,
range._start) < 0) {
+ Tower.proceed<G> (range._set._cmp, ref curr, ref next,
(uint8)i, true);
+ if (&curr != null && i == 0 && next != null) {
+ out_curr = next;
+ }
+ if (Tower.compare_data<G> (range._set._cmp, curr,
range._start) < 0) {
+ if
(!HazardPointer.compare_and_exchange_pointer<Tower<G>> (&range._bookmark._iter[i], curr_old, curr)) {
+ curr = HazardPointer.get_pointer<Tower<G>>
(&range._bookmark._iter[i]);
+ }
+ curr_old = curr;
+ } else {
+ break;
+ }
+ }
+ if (&prev != null) {
+ prev._iter[i] = curr;
+ }
+ last_best = (owned)curr;
+ }
+ break;
+ default:
+ assert_not_reached ();
+ }
+ if (&out_curr != null && out_curr != null && Range.beyond<G> (range, out_curr)) {
+ out_curr = null;
+ }
+#if DEBUG
+ stderr.printf("Bookmark after:\n");
+ for (int i = _MAX_HEIGHT - 1; i >= 0; i--) {
+ stderr.printf(" Level %d:\n", i);
+ Tower<string>? t = HazardPointer.get_pointer<Tower<string>>
(&range._bookmark._iter[i]);
+ assert (t == null || t.get_height () > i);
+ while (t != null) {
+ stderr.printf(" %s\n", t.is_head () ? "<<head>>" : t._data);
+ t = t.get_next ((uint8)i);
+ assert (t == null || t.get_height () > i);
+ }
+ }
+#endif
+ }
+
+ public static bool proceed<G> (Range<G> range, ref Tower<G>? prev, ref Tower<G> curr, uint8
level) {
+ switch (range._type) {
+ case RangeType.EMPTY:
+ return false;
+ case RangeType.TAIL:
+ return Tower.proceed<G> (range._set._cmp, ref prev, ref curr, level);
+ case RangeType.HEAD:
+ case RangeType.BOUNDED:
+ Tower<G>? tmp_prev = prev;
+ Tower<G>? tmp_curr = curr;
+ if (!Tower.proceed<G> (range._set._cmp, ref tmp_prev, ref tmp_curr, level)) {
+ return false;
+ } else if (Tower.compare_data<G> (range._set._cmp, tmp_curr, range._end) >=
0) {
+ return false;
+ } else {
+ prev = (owned)tmp_prev;
+ curr = (owned)tmp_curr;
+ return true;
+ }
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public static bool inside<G> (Range<G> range, G val) {
+ switch (range._type) {
+ case RangeType.HEAD:
+ return range._set._cmp (val, range._end) < 0;
+ case RangeType.TAIL:
+ return range._set._cmp (val, range._start) >= 0;
+ case RangeType.BOUNDED:
+ return range._set._cmp (val, range._start) >= 0 && range._set._cmp (val,
range._end) < 0;
+ case RangeType.EMPTY:
+ return false;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public static bool beyond<G> (Range<G> range, Tower<G> tw) {
+ switch (range._type) {
+ case RangeType.EMPTY:
+ return true;
+ case RangeType.TAIL:
+ return false;
+ case RangeType.HEAD:
+ case RangeType.BOUNDED:
+ return Tower.compare_data<G> (range._set._cmp, tw, range._end) >= 0;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public static int cmp<G> (Range<G> range, G val) {
+ switch (range._type) {
+ case RangeType.HEAD:
+ return range._set._cmp (val, range._end) < 0 ? Position.INSIDE :
Position.AFTER;
+ case RangeType.TAIL:
+ return range._set._cmp (val, range._start) >= 0 ? Position.INSIDE :
Position.BEFORE;
+ case RangeType.BOUNDED:
+ return range._set._cmp (val, range._start) >= 0 ? (range._set._cmp (val,
range._end) < 0 ? Position.INSIDE : Position.AFTER) : Position.BEFORE;
+ case RangeType.EMPTY:
+ return Position.EMPTY;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ enum Position {
+ BEFORE = -1,
+ INSIDE = 0,
+ AFTER = 1,
+ EMPTY
+ }
+ }
+
+ public enum RangeType {
+ HEAD,
+ TAIL,
+ BOUNDED,
+ EMPTY
+ }
+
+ private class Tower<G> {
+ public inline Tower (G data, uint8 height) {
+ _nodes = new TowerNode<G>[height];
+ _data = data;
+ _height = 0;
+ AtomicPointer.set (&_nodes[0]._backlink, null); // FIXME: This should be memory
barrier
+ }
+
+ public inline Tower.head () {
+ _nodes = new TowerNode<G>[_MAX_HEIGHT];
+ _height = -1;
+#if DEBUG
+ _data = (G)"<<head>>";
+#endif
+ }
+
+ inline ~Tower () {
+ int height = get_height();
+ for (uint8 i = 0; i < height; i++) {
+ set_succ (null, State.NONE, i);
+ set_backlink (null, i);
+ }
+ _nodes = null;
+ }
+
+ public static inline bool search<G> (CompareDataFunc<G>? cmp, G key, ref Tower<G> prev, out
Tower<G>? next = null, uint8 to_level = 0, uint8 from_level = (uint8)_MAX_HEIGHT - 1) {
+ assert (from_level >= to_level);
+ bool res = false;
+ next = null;
+ for (int i = from_level; i >= to_level; i--) {
+ res = search_helper<G> (cmp, key, ref prev, out next, (uint8)i);
+ }
+ return res;
+ }
+
+ public static inline bool search_from_bookmark<G> (CompareDataFunc<G>? cmp, G key, ref
TowerIter<G> prev, out TowerIter<G> next = null, uint8 to_level = 0, uint8 from_level = (uint8)_MAX_HEIGHT -
1) {
+ assert (from_level >= to_level);
+ next = TowerIter<G>();
+ bool res = false;
+ for (int i = from_level; i >= to_level; i--) {
+ unowned Tower<G> tmp_prev = prev._iter[i]; // Should be treated as NULL-like
value
+ Tower<G> tmp_next;
+ res = search_helper<G> (cmp, key, ref prev._iter[i], out tmp_next, (uint8)i);
+ if (&next != null) {
+ next._iter[i] = (owned)tmp_next;
+ }
+ if (prev._iter[i] != tmp_prev) {
+ prev._iter[i] = prev._iter[i];
+ if (i > to_level && compare<G> (cmp, prev._iter[i - 1],
prev._iter[i]) <= 0) {
+ prev._iter[i - 1] = prev._iter[i];
+ }
+ }
+ }
+ return res;
+ }
+
+ private static inline bool search_helper<G> (CompareDataFunc<G>? cmp, G key, ref Tower<G>?
prev, out Tower<G>? next, uint8 level) {
+ next = prev.get_next (level);
+ while (next != null && compare_data<G> (cmp, next, key) < 0 && proceed<G> (cmp, ref
prev, ref next, level, true));
+ return next != null && cmp(key, next._data) == 0;
+ }
+
+ public static inline Tower<G>? insert<G> (CompareDataFunc<G>? cmp, ref TowerIter<G> prev, G
key, uint8 chosen_level) {
+ return insert_helper<G> (cmp, ref prev, key, chosen_level, chosen_level);
+ }
+
+ private static inline Tower<G>? insert_helper<G> (CompareDataFunc<G>? cmp, ref TowerIter<G>
prev, G key, uint8 chosen_level, uint8 level) {
+ Tower<G>? new_tower;
+ Tower<G>? next;
+ if (search_helper (cmp, key, ref prev._iter[level], out next, level)) {
+ return null;
+ }
+ if (level > 0) {
+ if (compare<G> (cmp, prev._iter[level], prev._iter[level - 1]) >= 0) {
+ prev._iter[level - 1] = prev._iter[level];
+ }
+ new_tower = insert_helper<G> (cmp, ref prev, key, chosen_level, level - 1);
+ } else {
+ new_tower = new Tower<G> (key, chosen_level + 1);
+ }
+ if (new_tower == null) {
+ return null;
+ }
+ while (true) {
+ State prev_state;
+ Tower<G>? prev_next = prev._iter[level].get_succ (out prev_state, level);
+ if (prev_state == State.FLAGGED) {
+ prev_next.help_flagged (prev._iter[level], level);
+ } else {
+ new_tower.set_succ (next, State.NONE, level);
+ bool result = prev._iter[level].compare_and_exchange (next,
State.NONE, new_tower, State.NONE, level);
+ if (result)
+ break;
+ prev_next = prev._iter[level].get_succ (out prev_state, level);
+ if (prev_state == State.FLAGGED) {
+ prev_next.help_flagged (prev._iter[level], level);
+ }
+ backtrace<G> (ref prev._iter[level], level);
+ }
+ if (search_helper (cmp, key, ref prev._iter[level], null, level)) {
+ return null;
+ }
+ }
+ GLib.AtomicInt.inc (ref new_tower._height);
+ if (new_tower.get_state (0) == State.MARKED) {
+ remove_level (cmp, ref prev._iter[level], new_tower, level);
+ return null;
+ }
+ return new_tower;
+ }
+
+ public static inline bool remove_key<G> (CompareDataFunc<G>? cmp, ref TowerIter<G> prev, G
key, uint8 from_level = (uint8)_MAX_HEIGHT - 1) {
+ for (int i = from_level; i >= 1; i--) {
+ Tower<G> next;
+ search_helper<G> (cmp, key, ref prev._iter[i], out next, (uint8)i);
+ if (compare<G> (cmp, prev._iter[i - 1], prev._iter[i]) < 0) {
+ prev._iter[i - 1] = prev._iter[i];
+ }
+ }
+ Tower<G>? curr;
+ if (search_helper<G> (cmp, key, ref prev._iter[0], out curr, 0)) {
+ return remove<G> (cmp, ref prev, curr);
+ } else {
+ return false;
+ }
+ }
+
+ public static inline bool remove<G> (CompareDataFunc<G>? cmp, ref TowerIter<G> prev, Tower<G>
curr) {
+ bool removed = remove_level (cmp, ref prev._iter[0], curr, 0);
+ for (int i = 1; i < _MAX_HEIGHT; i++) {
+ remove_level (cmp, ref prev._iter[i], curr, (uint8)i);
+ }
+ return removed;
+ }
+
+ private static inline bool remove_level (CompareDataFunc<G>? cmp, ref Tower<G> prev, Tower<G>
curr, uint8 level) {
+ bool status;
+ bool flagged = curr.try_flag (cmp, ref prev, out status, level);
+ if (status) {
+ curr.help_flagged (prev, level);
+ }
+ return flagged;
+ }
+
+ public static inline bool proceed<G> (CompareDataFunc<G>? cmp, ref Tower<G>? arg_prev, ref
Tower<G> arg_curr, uint8 level, bool force = false) {
+ Tower<G> curr = arg_curr;
+ Tower<G>? next = curr.get_next (level);
+ if (next != null) {
+ while (next != null && next.get_state (0) == State.MARKED) {
+ bool status;
+ next.try_flag (cmp, ref curr, out status, level);
+ if (status) {
+ next.help_flagged (curr, level);
+ }
+ next = curr.get_next (level);
+ }
+ }
+ bool success = next != null;
+ if (success || force) {
+ arg_prev = (owned)curr;
+ arg_curr = (owned)next;
+ }
+ return success;
+ }
+
+ public inline void help_marked (Tower<G> prev_tower, uint8 level) {
+ prev_tower.compare_and_exchange (this, State.FLAGGED, get_next (level), State.NONE,
level);
+ }
+
+ public inline void help_flagged (Tower<G> prev, uint8 level) {
+ set_backlink (prev, level);
+ if (get_state (level) != State.MARKED)
+ try_mark (level);
+ help_marked (prev, level);
+ }
+
+ public inline void try_mark (uint8 level) {
+ do {
+ Tower<G>? next_tower = get_next (level);
+ bool result = compare_and_exchange (next_tower, State.NONE, next_tower,
State.MARKED, level);
+ if (!result) {
+ State state;
+ next_tower = get_succ (out state, level);
+ if (state == State.FLAGGED)
+ help_flagged (next_tower, level);
+ }
+ } while (get_state (level) != State.MARKED);
+ }
+
+ public inline bool try_flag (CompareDataFunc<G>? cmp, ref Tower<G> prev_tower, out bool
status, uint8 level) {
+ while (true) {
+ if (prev_tower.compare_succ (this, State.FLAGGED, level)) {
+ status = true;
+ return false;
+ }
+ bool result = prev_tower.compare_and_exchange (this, State.NONE, this,
State.FLAGGED, level);
+ if (result) {
+ status = true;
+ return true;
+ }
+ State result_state;
+ Tower<G>? result_tower = prev_tower.get_succ (out result_state, level);
+ if (result_tower == this && result_state == State.FLAGGED) {
+ status = true;
+ return false;
+ }
+ backtrace<G> (ref prev_tower, level);
+ if (!search_helper (cmp, _data, ref prev_tower, null, level)) {
+ status = false;
+ return false;
+ }
+ }
+ }
+
+ public static inline void backtrace<G> (ref Tower<G>? curr, uint8 level) {
+ while (curr.get_state (level) == State.MARKED)
+ curr = curr.get_backlink (level);
+ }
+
+ public inline bool compare_and_exchange (Tower<G>? old_tower, State old_state, Tower<G>?
new_tower, State new_state, uint8 level) {
+ return HazardPointer.compare_and_exchange_pointer<Tower<G>?> (&_nodes[level]._succ,
old_tower, new_tower, 3, (size_t)old_state, (size_t)new_state);
+ }
+
+ public inline bool compare_succ (Tower<G>? next, State state, uint8 level) {
+ size_t cur = (size_t)AtomicPointer.get (&_nodes[level]._succ);
+ return cur == ((size_t)next | (size_t)state);
+ }
+
+ public inline Tower<G>? get_next (uint8 level) {
+ return get_succ (null, level);
+ }
+
+ public inline State get_state (uint8 level) {
+ return (State)((size_t)AtomicPointer.get (&_nodes[level]._succ) & 3);
+ }
+
+ public inline Tower<G>? get_succ (out State state, uint8 level) {
+ size_t rstate;
+ Tower<G>? succ = HazardPointer.get_pointer<Tower<G>> (&_nodes[level]._succ, 3, out
rstate);
+ state = (State)rstate;
+ return (owned)succ;
+ }
+
+ public inline void set_succ (Tower<G>? next, State state, uint8 level) {
+ HazardPointer.set_pointer<Tower<G>> (&_nodes[level]._succ, next, 3, (size_t)state);
+ }
+
+ public inline Tower<G>? get_backlink (uint8 level) {
+ return HazardPointer.get_pointer<Tower<G>> (&_nodes[level]._backlink);
+ }
+
+ public inline void set_backlink (Tower<G>? backlink, uint8 level) {
+ HazardPointer.compare_and_exchange_pointer<Tower<G>?> (&_nodes[level]._backlink,
null, backlink);
+ }
+
+ public inline int get_height () {
+ int height = GLib.AtomicInt.get (ref _height);
+ return height != -1 ? height : _MAX_HEIGHT;
+ }
+
+ public inline bool is_head () {
+ int height = GLib.AtomicInt.get (ref _height);
+ return height == -1;
+ }
+
+ public inline static int compare<G> (CompareDataFunc<G>? cmp, Tower<G> a, Tower<G> b) {
+ bool ah = GLib.AtomicInt.get (ref a._height) == -1;
+ bool bh = GLib.AtomicInt.get (ref b._height) == -1;
+ return ah ? (bh ? 0 : -1) : (bh ? 1 : cmp(a._data, b._data));
+ }
+
+ public inline static int compare_data<G> (CompareDataFunc<G>? cmp, Tower<G> a, G b) {
+ bool ah = GLib.AtomicInt.get (ref a._height) == -1;
+ return ah ? -1 : cmp(a._data, b);
+ }
+
+ [CCode (array_length = false)]
+ public TowerNode<G>[] _nodes;
+ public G _data;
+ public int _height;
+ }
+
+ private struct TowerNode<G> {
+ public Tower<G> *_succ;
+ public Tower<G> *_backlink;
+ }
+
+ private struct TowerIter<G> {
+ [CCode (array_length = false)]
+ public Tower<G>? _iter[31 /*_MAX_HEIGHT*/];
+ }
+
+
+ private enum State {
+ NONE = 0,
+ MARKED = 1,
+ FLAGGED = 2
+ }
+}
+
diff --git a/gee/functions.vala b/gee/functions.vala
index a805bc8..00c7ca3 100644
--- a/gee/functions.vala
+++ b/gee/functions.vala
@@ -66,7 +66,7 @@ namespace Vala {
return ((Hashable<Hashable>) a).equal_to ((Hashable) b);
};
} else if (t.is_a (typeof (Comparable))) {
- return (a, b) => {
+ return (a, b) => {
if (a == b)
return true;
else if (a == null || b == null)
@@ -148,5 +148,38 @@ namespace Vala {
};
}
}
+
+ [CCode (simple_generics = true)]
+ internal class EqualDataFuncClosure<G> {
+ public EqualDataFuncClosure(owned EqualDataFunc<G> func) {
+ this.func = (owned)func;
+ }
+ public EqualDataFunc<G> func;
+ public EqualDataFunc<G> clone_func () {
+ return (a, b) => {return func (a, b);};
+ }
+ }
+
+ [CCode (simple_generics = true)]
+ internal class HashDataFuncClosure<G> {
+ public HashDataFuncClosure(owned HashDataFunc<G> func) {
+ this.func = (owned)func;
+ }
+ public HashDataFunc<G> func;
+ public HashDataFunc<G> clone_func () {
+ return (a) => {return func (a);};
+ }
+ }
+
+ [CCode (simple_generics = true)]
+ internal class CompareDataFuncClosure<G> {
+ public CompareDataFuncClosure(owned CompareDataFunc<G> func) {
+ this.func = (owned)func;
+ }
+ public CompareDataFunc<G> func;
+ public CompareDataFunc<G> clone_func () {
+ return (a, b) => {return func (a, b);};
+ }
+ }
}
}
diff --git a/gee/future.vala b/gee/future.vala
new file mode 100644
index 0000000..c4c351a
--- /dev/null
+++ b/gee/future.vala
@@ -0,0 +1,256 @@
+/* future.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Future is a value which might not yet be computed - for example it is calculated
+ * in different thread or depends on I/O value.
+ *
+ * All methods can be called from many threads as part of interface.
+ *
+ * Note: Statement that call does not block does not mean that it is lock-free.
+ * Internally the implementation is allowed to take mutex but it should guarantee
+ * that it is not for a long time (including blocking on anything else, I/O calls
+ * or callbacks).
+ *
+ * @see Promise
+ * @see Lazy
+ * @see task
+ * @see async_task
+ */
+[GenericAccessors]
+public interface Vala.Future<G> : Object {
+ /**
+ * The value associated with Future. If value is not ready getting value
+ * will block until value is ready.
+ *
+ * Returned value is always the same and it is alive at least as long
+ * as the future.
+ */
+ [CCode (ordering = 7)]
+ public virtual new G? value {
+ get {
+ try {
+ return wait ();
+ } catch (FutureError ex) {
+ return null;
+ }
+ }
+ }
+
+ /**
+ * Checks if value is ready. If it is calls to {@link wait} and
+ * {@link wait_until} will not block and value is returned immidiatly.
+ */
+ [CCode (ordering = 8)]
+ public abstract bool ready {get;}
+
+ /**
+ * Checks the exception that have been set. I.e. if the computation
+ * has thrown the exception it should be set here and the {@link wait},
+ * {@link wait_until} and {@link wait_async} should throw
+ * {@link FutureError.EXCEPTION}.
+ */
+ [CCode (ordering = 9)]
+ public abstract GLib.Error? exception {get;}
+
+ /**
+ * Waits until the value is ready.
+ *
+ * @return The {@link value} associated with future
+ * @see ready
+ * @see wait_until
+ * @see wait_async
+ */
+ [CCode (ordering = 0)]
+ public abstract unowned G wait () throws Vala.FutureError;
+
+ /**
+ * Waits until the value is ready or deadline have passed.
+ *
+ * @param end_time The time when the wait should finish
+ * @param value The {@link value} associated with future if the wait was successful
+ * @return ``true`` if the value was ready within deadline or ``false`` otherwise
+ * @see ready
+ * @see wait
+ * @see wait_async
+ */
+ [CCode (ordering = 1)]
+ public abstract bool wait_until (int64 end_time, out unowned G? value = null) throws Vala.FutureError;
+
+ /**
+ * Reschedules the callback until the {@link value} is available.
+ *
+ * @return The {@link value} associated with future
+ * @see ready
+ * @see wait
+ * @see wait_until
+ */
+ [CCode (ordering = 2)]
+ public abstract async unowned G wait_async () throws Vala.FutureError;
+ public delegate A MapFunc<A, G> (G value);
+
+ /**
+ * Maps a future value to another value by a function and returns the
+ * another value in future.
+ *
+ * Note: As time taken by function might not contribute to
+ * {@link wait_until} and the implementation is allowed to compute
+ * value eagerly by {@link wait_async} it is recommended to use
+ * {@link task} and {@link flat_map} for longer computation.
+ *
+ * @param func Function applied to {@link value}
+ * @return Value returned by function
+ *
+ * @see flat_map
+ * @see light_map
+ */
+ [CCode (ordering = 3)]
+ public virtual Future<A> map<A> (owned MapFunc<A, G> func) {
+ Promise<A> promise = new Promise<A> ();
+ wait_async.begin ((obj, res) => {
+ try {
+ promise.set_value (func (wait_async.end (res)));
+ } catch (Error ex) {
+ promise.set_exception ((owned)ex);
+ }
+ });
+ return promise.future;
+ }
+
+ public delegate unowned A LightMapFunc<A, G> (G value);
+
+ /**
+ * Maps a future value to another value by a function and returns the
+ * another value in future.
+ *
+ * Note: The function may be reevaluated at any time and it might
+ * be called lazily. Therefore it is recommended for it to be
+ * idempotent. If the function needs to be called eagerly or have
+ * side-effects it is recommended to use {@link map}.
+ *
+ * Note: As time taken by function does not contribute to
+ * {@link wait_until} and the implementation is allowed to compute
+ * value eagerly by {@link wait_async} it is recommended to use
+ * {@link task} and {@link flat_map} for longer computation.
+ *
+ * @param func Function applied to {@link value}
+ * @return Value returned by function
+ *
+ * @see flat_map
+ * @see map
+ */
+ [CCode (ordering = 10, cname = "gee_future_light_map_fixed", vfunc_name = "light_map_fixed")]
+ public virtual Future<A> light_map<A> (owned LightMapFunc<A, G> func) {
+ return new LightMapFuture<A, G> (this, func);
+ }
+
+ [CCode (ordering = 4, cname = "gee_future_light_map", vfunc_name = "light_map")]
+ public virtual Future<A> light_map_broken<A> (LightMapFunc<A, G> func) {
+ return light_map<A> (func);
+ }
+
+ [CCode (scope = "async")]
+ public delegate C ZipFunc<A, B, C>(A a, B b);
+
+ /**
+ * Combines values of two futures using a function returning the combined
+ * value in future (call does not block).
+ *
+ * Note: As time taken by function does not contribute to
+ * {@link wait_until} and the implementation is allowed to compute
+ * value eagerly by {@link wait_async} it is recommended to return a
+ * future from {@link task} and use {@link flat_map} for longer computation.
+ *
+ * @param zip_func Function applied to values
+ * @param second Second parameter
+ * @return A combine value
+ */
+ [CCode (ordering = 5)]
+ public virtual Future<B> zip<A, B> (owned ZipFunc<G, A, B> zip_func, Future<A> second) {
+ Promise<B> promise = new Promise<B> ();
+ do_zip.begin<G, A, B> ((owned) zip_func, this, second, promise, (obj, res) => {do_zip.end<G,
A, B> (res);});
+ return promise.future;
+ }
+
+ private static async void do_zip<A, B, C> (owned ZipFunc<A, B, C> zip_func, Future<A> first,
Future<B> second, Promise<C> result) {
+ try {
+ A left = yield first.wait_async ();
+ B right = yield second.wait_async ();
+ result.set_value (zip_func (left, right));
+ } catch (Error ex) {
+ result.set_exception ((owned)ex);
+ }
+ }
+
+ public delegate Vala.Future<A> FlatMapFunc<A, G>(G value);
+
+ /**
+ * Maps a future value to another future value which is returned (call does not block).
+ *
+ * Note: As time taken by function does not contribute to
+ * {@link wait_until} and the implementation is allowed to compute
+ * value eagerly by {@link wait_async} it is recommended to put the
+ * larger computation inside the returned future for example by
+ * {@link task}
+ *
+ * @param func Function applied to {@link value}
+ * @return Value of a future returned by function
+ *
+ * @see map
+ */
+ [CCode (ordering = 6)]
+ public virtual Vala.Future<A> flat_map<A>(owned FlatMapFunc<A, G> func) {
+ Promise<A> promise = new Promise<A> ();
+ do_flat_map.begin<G, A> ((owned)func, this, promise, (obj, res) => {do_flat_map.end<G, A>
(res);});
+ return promise.future;
+ }
+
+ private static async void do_flat_map<A, B> (owned FlatMapFunc<B, A> func, Future<A> future,
Promise<B> promise) {
+ try {
+ A input = yield future.wait_async ();
+ B output = yield func (input).wait_async ();
+ promise.set_value ((owned)output);
+ } catch (Error ex) {
+ promise.set_exception ((owned)ex);
+ }
+ }
+
+ internal struct SourceFuncArrayElement {
+ public SourceFuncArrayElement (owned SourceFunc func) {
+ this.func = (owned)func;
+ }
+ public SourceFunc func;
+ }
+}
+
+public errordomain Vala.FutureError {
+ /**
+ * The promise have been abandon - this indicates an error in program.
+ */
+ ABANDON_PROMISE,
+ /**
+ * Exception field has been set.
+ */
+ EXCEPTION
+}
diff --git a/gee/hashable.vala b/gee/hashable.vala
index 9b806f1..f89a035 100644
--- a/gee/hashable.vala
+++ b/gee/hashable.vala
@@ -29,15 +29,30 @@
public interface Vala.Hashable<G> : Object {
/**
* Computes hash for an objects. Two hashes of equal objects have to be
- * equal. Hash have to not change during lifetime of object.
+ * equal.
+ *
+ * Note: Hash //must not// change during lifetime of an object.
*
* @return hash of an object
*/
public abstract uint hash ();
/**
- * Compares this object with the specifed object.
+ * Compares this object with the specifed object. This defines the
+ * equivalence relation between them.
+ *
+ * In other words:
+ *
+ * * It must be reflexive: for all objects `a` it holds that
+ * `a.equal_to(a)`.
+ * * It must be symmetric: for all objects `a` and `b` if
+ * `a.equal_to(b)` then `b.equal_to(a)`.
+ * * It must be transitive: if `a.equal_to(b)` and `b.equal_to(c)` then
+ * `a.equal_to(c)`.
+ *
+ * Note: Relationship //must not// change during lifetime of an object.
*
+ * @param object Object this objest is compared with
* @return true if objects are equal
*/
public abstract bool equal_to (G object);
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 158e787..ca6767a 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -3,6 +3,7 @@
* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
* Copyright (C) 1997-2000 GLib Team and others
* Copyright (C) 2007-2009 Jürg Billeter
+ * Copyright (C) 2009-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -97,23 +98,42 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
* The keys' hash function.
*/
[CCode (notify = false)]
- public HashDataFunc<K> key_hash_func { private set; get; }
+ public HashDataFunc<K> key_hash_func {
+ private set {}
+ get {
+ return _key_hash_func.func;
+ }
+ }
/**
* The keys' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<K> key_equal_func { private set; get; }
+ public EqualDataFunc<K> key_equal_func {
+ private set {}
+ get {
+ return _key_equal_func.func;
+ }
+ }
/**
* The values' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<V> value_equal_func { private set; get; }
+ public EqualDataFunc<V> value_equal_func {
+ private set {}
+ get {
+ return _value_equal_func.func;
+ }
+ }
private int _array_size;
private int _nnodes;
private Node<K,V>[] _nodes;
+ private Functions.HashDataFuncClosure<K> _key_hash_func;
+ private Functions.EqualDataFuncClosure<K> _key_equal_func;
+ private Functions.EqualDataFuncClosure<V> _value_equal_func;
+
private weak Set<K> _keys;
private weak Collection<V> _values;
@@ -145,9 +165,18 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
if (value_equal_func == null) {
value_equal_func = Functions.get_equal_func_for (typeof (V));
}
- this.key_hash_func = key_hash_func;
- this.key_equal_func = key_equal_func;
- this.value_equal_func = value_equal_func;
+ _key_hash_func = new Functions.HashDataFuncClosure<K> ((owned)key_hash_func);
+ _key_equal_func = new Functions.EqualDataFuncClosure<K> ((owned)key_equal_func);
+ _value_equal_func = new Functions.EqualDataFuncClosure<V> ((owned)value_equal_func);
+
+ _array_size = MIN_SIZE;
+ _nodes = new Node<K,V>[_array_size];
+ }
+
+ internal HashMap.with_closures (owned Functions.HashDataFuncClosure<K> key_hash_func, owned
Functions.EqualDataFuncClosure<K> key_equal_func, owned Functions.EqualDataFuncClosure<V> value_equal_func) {
+ _key_hash_func = key_hash_func;
+ _key_equal_func = key_equal_func;
+ _value_equal_func = value_equal_func;
_array_size = MIN_SIZE;
_nodes = new Node<K,V>[_array_size];
@@ -241,6 +270,14 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
return new MapIterator<K,V> (this);
}
+ internal Functions.HashDataFuncClosure<K> get_key_hash_func_closure () {
+ return _key_hash_func;
+ }
+
+ internal Functions.EqualDataFuncClosure<K> get_key_equal_func_closure () {
+ return _key_equal_func;
+ }
+
private inline bool unset_helper (K key, out V? value = null) {
Node<K,V>** node = lookup_node (key);
if (*node != null) {
@@ -304,6 +341,12 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
key_hash = hash;
entry = null;
}
+
+ ~Node () {
+ if (entry != null) {
+ entry.remove_weak_pointer ((void**) (&entry));
+ }
+ }
}
private class Entry<K,V> : Map.Entry<K,V> {
@@ -367,19 +410,6 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
public override bool contains (K key) {
return _map.has_key (key);
}
-
- public bool add_all (Collection<K> collection) {
- assert_not_reached ();
- }
-
- public bool remove_all (Collection<K> collection) {
- assert_not_reached ();
- }
-
- public bool retain_all (Collection<K> collection) {
- assert_not_reached ();
- }
-
}
private class ValueCollection<K,V> : AbstractCollection<V> {
@@ -422,18 +452,6 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
return false;
}
-
- public bool add_all (Collection<V> collection) {
- assert_not_reached ();
- }
-
- public bool remove_all (Collection<V> collection) {
- assert_not_reached ();
- }
-
- public bool retain_all (Collection<V> collection) {
- assert_not_reached ();
- }
}
private class EntrySet<K,V> : AbstractSet<Map.Entry<K, V>> {
@@ -470,34 +488,22 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
public override bool contains (Map.Entry<K, V> entry) {
return _map.has (entry.key, entry.value);
}
-
- public bool add_all (Collection<Map.Entry<K, V>> entries) {
- assert_not_reached ();
- }
-
- public bool remove_all (Collection<Map.Entry<K, V>> entries) {
- assert_not_reached ();
- }
-
- public bool retain_all (Collection<Map.Entry<K, V>> entries) {
- assert_not_reached ();
- }
}
private abstract class NodeIterator<K,V> : Object {
- protected HashMap<K,V> _map;
- protected int _index = -1;
- protected weak Node<K,V> _node;
- protected weak Node<K,V> _next;
-
- // concurrent modification protection
- protected int _stamp;
-
public NodeIterator (HashMap map) {
_map = map;
_stamp = _map._stamp;
}
+ public NodeIterator.from_iterator (NodeIterator<K,V> iter) {
+ _map = iter._map;
+ _index = iter._index;
+ _node = iter._node;
+ _next = iter._next;
+ _stamp = iter._stamp;
+ }
+
public bool next () {
assert (_stamp == _map._stamp);
if (!has_next ()) {
@@ -522,18 +528,24 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
return (_next != null);
}
-
+
public virtual bool read_only {
get {
return true;
}
}
-
+
public bool valid {
get {
return _node != null;
}
}
+
+ protected HashMap<K,V> _map;
+ protected int _index = -1;
+ protected weak Node<K,V> _node;
+ protected weak Node<K,V> _next;
+ protected int _stamp;
}
private class KeyIterator<K,V> : NodeIterator<K,V>, Traversable<K>, Iterator<K> {
@@ -541,6 +553,10 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
base (map);
}
+ public KeyIterator.from_iterator (KeyIterator<K,V> iter) {
+ base.from_iterator (iter);
+ }
+
public new K get () {
assert (_stamp == _map._stamp);
assert (_node != null);
@@ -575,6 +591,19 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
} while(true);
}
+
+ public Vala.Iterator<K>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<K>[0];
+ } else {
+ Vala.Iterator<K>[] result = new Vala.Iterator<K>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new KeyIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class MapIterator<K,V> : NodeIterator<K,V>, Vala.MapIterator<K,V> {
@@ -609,13 +638,13 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
_map.set (_node.key, value);
_stamp = _map._stamp;
}
-
+
public bool mutable {
get {
return true;
}
}
-
+
public override bool read_only {
get {
return false;
@@ -624,10 +653,14 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Iterator<V> {
- public ValueIterator (HashMap map) {
+ public ValueIterator (HashMap<K,V> map) {
base (map);
}
+ public ValueIterator.from_iterator (ValueIterator<K,V> iter) {
+ base.from_iterator (iter);
+ }
+
public new V get () {
assert (_stamp == _map._stamp);
assert (_node != null);
@@ -662,13 +695,30 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
} while(true);
}
+
+ public Vala.Iterator<K>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<K>[0];
+ } else {
+ Vala.Iterator<K>[] result = new Vala.Iterator<K>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new ValueIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K,V>>,
Iterator<Map.Entry<K,V>> {
- public EntryIterator (HashMap map) {
+ public EntryIterator (HashMap<K,V> map) {
base (map);
}
+ public EntryIterator.from_iterator (EntryIterator<K,V> iter) {
+ base.from_iterator (iter);
+ }
+
public new Map.Entry<K,V> get () {
assert (_stamp == _map._stamp);
assert (_node != null);
@@ -703,6 +753,19 @@ public class Vala.HashMap<K,V> : Vala.AbstractMap<K,V> {
}
} while(true);
}
+
+ public Iterator<Map.Entry<K,V>>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<Map.Entry<K,V>>[0];
+ } else {
+ Iterator<Map.Entry<K,V>>[] result = new Iterator<Map.Entry<K,V>>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new EntryIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
}
diff --git a/gee/hashmultimap.vala b/gee/hashmultimap.vala
index ca57fb8..46764ef 100644
--- a/gee/hashmultimap.vala
+++ b/gee/hashmultimap.vala
@@ -33,10 +33,20 @@ public class Vala.HashMultiMap<K,V> : AbstractMultiMap<K,V> {
}
[CCode (notify = false)]
- public HashDataFunc<V> value_hash_func { private set; get; }
+ public HashDataFunc<V> value_hash_func {
+ private set {}
+ get {
+ return _value_hash_func.func;
+ }
+ }
[CCode (notify = false)]
- public EqualDataFunc<V> value_equal_func { private set; get; }
+ public EqualDataFunc<V> value_equal_func {
+ private set {}
+ get {
+ return _value_equal_func.func;
+ }
+ }
/**
* Constructs a new, empty hash multimap.
@@ -51,26 +61,29 @@ public class Vala.HashMultiMap<K,V> : AbstractMultiMap<K,V> {
*/
public HashMultiMap (owned HashDataFunc<K>? key_hash_func = null, owned EqualDataFunc<K>?
key_equal_func = null,
owned HashDataFunc<V>? value_hash_func = null, owned EqualDataFunc<V>?
value_equal_func = null) {
- base (new HashMap<K, Set<V>> (key_hash_func, key_equal_func, Functions.get_equal_func_for
(typeof (Set))));
+ base (new HashMap<K, Set<V>> ((owned)key_hash_func, (owned)key_equal_func,
Functions.get_equal_func_for (typeof (Set))));
if (value_hash_func == null) {
value_hash_func = Functions.get_hash_func_for (typeof (V));
}
if (value_equal_func == null) {
value_equal_func = Functions.get_equal_func_for (typeof (V));
}
- this.value_hash_func = value_hash_func;
- this.value_equal_func = value_equal_func;
+ _value_hash_func = new Functions.HashDataFuncClosure<V> ((owned)value_hash_func);
+ _value_equal_func = new Functions.EqualDataFuncClosure<V> ((owned)value_equal_func);
}
protected override Collection<V> create_value_storage () {
- return new HashSet<V> (_value_hash_func, _value_equal_func);
+ return new HashSet<V>.with_closures (_value_hash_func, _value_equal_func);
}
protected override MultiSet<K> create_multi_key_set () {
- return new HashMultiSet<K> (key_hash_func, key_equal_func);
+ return new HashMultiSet<K>.with_closures (((HashMap<K, Set<V>>)
_storage_map).get_key_hash_func_closure (), ((HashMap<K, Set<V>>) _storage_map).get_key_equal_func_closure
());
}
- protected override EqualDataFunc get_value_equal_func () {
- return _value_equal_func;
+ protected override EqualDataFunc<V> get_value_equal_func () {
+ return _value_equal_func.clone_func ();
}
+
+ private Functions.HashDataFuncClosure<V> _value_hash_func;
+ private Functions.EqualDataFuncClosure<V> _value_equal_func;
}
diff --git a/gee/hashmultiset.vala b/gee/hashmultiset.vala
index 78b8500..f8c8dcd 100644
--- a/gee/hashmultiset.vala
+++ b/gee/hashmultiset.vala
@@ -41,7 +41,11 @@ public class Vala.HashMultiSet<G> : AbstractMultiSet<G> {
* @param hash_func an optional element hash function
* @param equal_func an optional element equality testing function
*/
- public HashMultiSet (HashDataFunc<G>? hash_func = null, EqualDataFunc<G>? equal_func = null) {
- base (new HashMap<G, int> (hash_func, equal_func));
+ public HashMultiSet (owned HashDataFunc<G>? hash_func = null, owned EqualDataFunc<G>? equal_func =
null) {
+ base (new HashMap<G, int> ((owned)hash_func, (owned)equal_func));
+ }
+
+ internal HashMultiSet.with_closures (owned Functions.HashDataFuncClosure<G> hash_func, owned
Functions.EqualDataFuncClosure<G> equal_func) {
+ base (new HashMap<G, int>.with_closures ((owned)hash_func, (owned)equal_func, new
Functions.EqualDataFuncClosure<int> (Functions.get_equal_func_for (typeof (int)))));
}
}
diff --git a/gee/hashset.vala b/gee/hashset.vala
index e4821d7..67bdd5a 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -3,6 +3,7 @@
* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
* Copyright (C) 1997-2000 GLib Team and others
* Copyright (C) 2007-2009 Jürg Billeter
+ * Copyright (C) 2009-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -25,7 +26,41 @@
using GLib;
namespace Vala {
+ /**
+ * A function producing a hash for an object. Two hashes of equal
+ * objects (as specified by corresponding {@link EqualDataFunc}) have to
+ * be equal.
+ *
+ * Note: Hash for a given object //must not// change during the lifetime
+ * of delegate.
+ *
+ * @param v Hashed value
+ * @return Hash for given value
+ *
+ * @see Hashable
+ */
public delegate uint HashDataFunc<T> (T v);
+ /**
+ * A function comparing two object defining equivalence relationship.
+ *
+ * In other words if `equal_to` is `EqualDataFunc` then:
+ *
+ * * It must be reflexive: for all objects `a` it holds that
+ * `equal_to(a, a)`.
+ * * It must be symmetric: for all objects `a` and `b` if
+ * `equal_to(a, b)` then `equal_to(b, a)`.
+ * * It must be transitive: if `equal_to(a, b)` and `equal_to(b, c)`
+ * then `equal_to(a, c)`
+ *
+ * Note: The relationship //must not// change during lifetime of the
+ * delegate.
+ *
+ * @param a First value
+ * @param b Second value
+ * @return Whether values are equal
+ *
+ * @see Hashable
+ */
public delegate bool EqualDataFunc<T> (T a, T b);
}
@@ -57,17 +92,29 @@ public class Vala.HashSet<G> : AbstractSet<G> {
* The elements' hash function.
*/
[CCode (notify = false)]
- public HashDataFunc<G> hash_func { private set; get; }
+ public HashDataFunc<G> hash_func {
+ private set {}
+ get {
+ return _hash_func.func;
+ }
+ }
/**
* The elements' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<G> equal_func { private set; get; }
+ public EqualDataFunc<G> equal_func {
+ private set {}
+ get {
+ return _equal_func.func;
+ }
+ }
private int _array_size;
private int _nnodes;
private Node<G>[] _nodes;
+ private Functions.HashDataFuncClosure<G> _hash_func;
+ private Functions.EqualDataFuncClosure<G> _equal_func;
// concurrent modification protection
private int _stamp = 0;
@@ -91,8 +138,15 @@ public class Vala.HashSet<G> : AbstractSet<G> {
if (equal_func == null) {
equal_func = Functions.get_equal_func_for (typeof (G));
}
- this.hash_func = hash_func;
- this.equal_func = equal_func;
+ _hash_func = new Functions.HashDataFuncClosure<G> ((owned)hash_func);
+ _equal_func = new Functions.EqualDataFuncClosure<G> ((owned)equal_func);
+ _array_size = MIN_SIZE;
+ _nodes = new Node<G>[_array_size];
+ }
+
+ internal HashSet.with_closures (owned Functions.HashDataFuncClosure<G> hash_func, owned
Functions.EqualDataFuncClosure<G> equal_func) {
+ _hash_func = hash_func;
+ _equal_func = equal_func;
_array_size = MIN_SIZE;
_nodes = new Node<G>[_array_size];
}
@@ -165,6 +219,20 @@ public class Vala.HashSet<G> : AbstractSet<G> {
resize ();
}
+ /**
+ * {@inheritDoc}
+ */
+ public override bool foreach (ForallFunc<G> f) {
+ for (int i = 0; i < _array_size; i++) {
+ for (unowned Node<G>? current = _nodes[i]; current != null; current = current.next) {
+ if (!f (current.key)) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
private inline bool remove_helper (G key) {
Node<G>** node = lookup_node (key);
if (*node != null) {
@@ -223,19 +291,18 @@ public class Vala.HashSet<G> : AbstractSet<G> {
}
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G> {
- private HashSet<G> _set;
- private int _index = -1;
- private weak Node<G> _node;
- private weak Node<G> _next;
-
- // concurrent modification protection
- private int _stamp = 0;
-
- public Iterator (HashSet set) {
+ public Iterator (HashSet<G> set) {
_set = set;
_stamp = _set._stamp;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _set = iter._set;
+ _index = iter._index;
+ _node = iter._node;
+ _next = iter._next;
+ }
+
public bool next () {
assert (_stamp == _set._stamp);
if (!has_next ()) {
@@ -326,6 +393,25 @@ public class Vala.HashSet<G> : AbstractSet<G> {
_next = null;
return true;
}
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[0] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected HashSet<G> _set;
+ protected int _index = -1;
+ protected weak Node<G> _node;
+ protected weak Node<G> _next;
+ protected int _stamp = 0;
}
}
diff --git a/gee/hazardpointer.vala b/gee/hazardpointer.vala
index a26fbeb..1fac2b5 100644
--- a/gee/hazardpointer.vala
+++ b/gee/hazardpointer.vala
@@ -165,8 +165,10 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
public static void set_pointer<G> (G **aptr, owned G? new_ptr, size_t mask = 0, size_t new_mask = 0) {
HazardPointer<G>? ptr = exchange_hazard_pointer<G> (aptr, new_ptr, mask, new_mask, null);
if (ptr != null) {
- DestroyNotify<G> notify = get_destroy_notify<G> ();
- ptr.release ((owned)notify);
+ DestroyNotify? notify = Utils.Free.get_destroy_notify<G> ();
+ if (notify != null) {
+ ptr.release ((owned)notify);
+ }
}
}
@@ -202,8 +204,8 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
void *old_rptr = (void *)((size_t)(old_ptr) | (mask & old_mask));
bool success = AtomicPointer.compare_and_exchange((void **)aptr, old_rptr, new_rptr);
if (success) {
- DestroyNotify<G> notify = get_destroy_notify<G> ();
- if (old_ptr != null) {
+ DestroyNotify? notify = Utils.Free.get_destroy_notify<G> ();
+ if (old_ptr != null && notify != null) {
Context.get_current_context ()->release_ptr (old_ptr, (owned)notify);
}
} else if (new_ptr != null) {
@@ -400,38 +402,37 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
* @param to_free List containing elements to free.
* @return Non-empty list of not freed elements or ``null`` if all elements have been
disposed.
*/
- internal ArrayList<FreeNode *>? perform (owned ArrayList<FreeNode *> to_free) {
+ internal bool perform (ref ArrayList<FreeNode *> to_free) {
switch (this.to_concrete ()) {
case TRY_FREE:
- return try_free (to_free) ? (owned) to_free : null;
+ return try_free (to_free);
case FREE:
while (try_free (to_free)) {
Thread.yield ();
}
- return null;
+ break;
case TRY_RELEASE:
ReleasePolicy.ensure_start ();
if (_queue_mutex.trylock ()) {
_queue.offer ((owned) to_free);
_queue_mutex.unlock ();
- return null;
+ return true;
} else {
- return (owned) to_free;
+ return false;
}
case RELEASE:
ReleasePolicy.ensure_start ();
_queue_mutex.lock ();
_queue.offer ((owned) to_free);
_queue_mutex.unlock ();
- return null;
+ return true;
default:
assert_not_reached ();
}
+ return false;
}
}
- public delegate void DestroyNotify (void *ptr);
-
/**
* Release policy determines what happens with object freed by Policy.TRY_RELEASE
* and Policy.RELEASE.
@@ -451,20 +452,26 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
private static void start (ReleasePolicy self) { // FIXME: Make it non-static [bug 659778]
switch (self) {
case HELPER_THREAD:
- try {
- new Thread<bool> ("<<libgee hazard pointer>>", () => {
- while (true) {
- Thread.yield ();
- attempt_free ();
+ new Thread<bool> ("<<libgee hazard pointer>>", () => {
+ Context ctx = new Context (Policy.TRY_FREE);
+ while (true) {
+ Thread.yield ();
+ pull_from_queue (ctx._to_free, ctx._to_free.is_empty);
+ ctx.try_free ();
+ if (ctx._to_free.is_empty) {
+ GLib.Thread.usleep (100000);
}
- });
- } catch (ThreadError error) {
- assert_not_reached ();
- }
+ }
+ });
break;
case MAIN_LOOP:
+ _global_to_free = new ArrayList<FreeNode *> ();
Idle.add (() => {
- attempt_free ();
+ Context ctx = new Context (Policy.TRY_FREE);
+ swap (ref _global_to_free, ref ctx._to_free);
+ pull_from_queue (ctx._to_free, false);
+ ctx.try_free ();
+ swap (ref _global_to_free, ref ctx._to_free);
return true;
}, Priority.LOW);
break;
@@ -473,6 +480,12 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
}
}
+ private static void swap<T>(ref T a, ref T b) {
+ T tmp = (owned)a;
+ a = (owned)b;
+ b = (owned)tmp;
+ }
+
/**
* Ensures that helper methods are started.
*/
@@ -485,21 +498,26 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
if ((policy & (1 << (sizeof(int) * 8 - 1))) == 0) {
_queue = new LinkedList<ArrayList<FreeNode *>> ();
// Hack to not lie about successfull setting policy
- policy = AtomicInt.exchange_and_add (ref release_policy, (int)(1 <<
(sizeof(int) * 8 - 1)));
+ policy = AtomicInt.add (ref release_policy, (int)(1 << (sizeof(int) *
8 - 1)));
start ((ReleasePolicy) policy);
}
_queue_mutex.unlock ();
}
}
- private static inline void attempt_free () {
- if (_queue_mutex.trylock ()) {
+ private static inline void pull_from_queue (Collection<FreeNode *> to_free, bool do_lock) {
+ bool locked = do_lock;
+ if (do_lock) {
+ _queue_mutex.lock ();
+ } else {
+ locked = _queue_mutex.trylock ();
+ }
+ if (locked) {
Collection<ArrayList<FreeNode *>> temp = new ArrayList<ArrayList<FreeNode *>>
();
_queue.drain (temp);
_queue_mutex.unlock ();
- temp.foreach ((x) => {_global_to_free.add_all (x); return true;});
+ temp.foreach ((x) => {to_free.add_all (x); return true;});
}
- try_free (_global_to_free);
}
}
@@ -547,15 +565,12 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
int size = _to_free.size;
bool clean_parent = false;
if (size > 0) {
- ArrayList<FreeNode *>? remaining;
- if (_parent == null || size >= THRESHOLD)
- remaining = _policy.perform ((owned) _to_free);
- else
- remaining = (owned) _to_free;
- if (remaining != null) {
- assert (_parent != null);
- _parent->_to_free.add_all (remaining);
- clean_parent = true;
+ if (_parent == null || size >= THRESHOLD) {
+ if (!_policy.perform (ref _to_free)) {
+ assert (_parent != null && _to_free != null);
+ _parent->_to_free.add_all (_to_free);
+ clean_parent = true;
+ }
}
}
#if DEBUG
@@ -621,10 +636,6 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
return _current_context.get ();
}
- private inline bool _should_free () {
- return (_parent == null && _to_free.size > 0) || _to_free.size >= THRESHOLD;
- }
-
internal Context *_parent;
internal ArrayList<FreeNode *> _to_free;
internal Policy? _policy;
@@ -706,14 +717,6 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
internal static ArrayList<FreeNode *> _global_to_free;
- internal static DestroyNotify get_destroy_notify<G> () {
- return (ptr) => {
- G *gptr = ptr;
- G obj = (owned)gptr;
- obj = null;
- };
- }
-
[Compact]
internal class FreeNode {
public void *pointer;
@@ -729,7 +732,7 @@ public class Vala.HazardPointer<G> { // FIXME: Make it a struct
AtomicPointer.set (&_hazard, null);
AtomicInt.set (ref _active, 1);
}
-
+
inline ~Node () {
delete _next;
}
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 8064e96..79d7824 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -32,8 +32,13 @@
* item has been removed, until the next call to {@link next}.
*
* Please note that when the iterator is out of track, neither {@link get} nor
- * {@link remove} are defined and both will fail. After the next call to
+ * {@link remove} are defined and both might fail. After the next call to
* {@link next}, they will be defined again.
+ *
+ * Please also note that, unless specified otherwise, iterators before iteration
+ * started should behave as if after deletion of the first element. Whenever
+ * documentation states about the iterator 'out of track', 'invalid' or
+ * 'in-between elements' this refers to the same concept.
*/
public interface Vala.Iterator<G> : Object, Traversable<G> {
/**
diff --git a/gee/lazy.vala b/gee/lazy.vala
index ed1ac3c..3d55848 100644
--- a/gee/lazy.vala
+++ b/gee/lazy.vala
@@ -26,6 +26,8 @@ namespace Vala {
/**
* Represents a lazy value. I.e. value that is computed on demand.
+ *
+ * This class is not thread-safe.
*/
public class Vala.Lazy<G> {
public Lazy (owned LazyFunc<G> func) {
@@ -55,6 +57,114 @@ public class Vala.Lazy<G> {
}
}
+ /**
+ * Provides a future for a lazy value.
+ *
+ * Note: The future can be requested only once and all access must be
+ * done through it.
+ */
+ public Vala.Future<G>? future {
+ owned get {
+ return new Future<G> (this);
+ }
+ }
+
private LazyFunc<G>? _func;
private G? _value;
+
+ private class Future<G> : Object, Vala.Future<G> {
+ public Future (Lazy<G> lazy) {
+ _lazy = lazy;
+ _when_done = new Vala.Future.SourceFuncArrayElement<G>[0];
+ }
+
+ public bool ready {
+ get {
+ _mutex.lock ();
+ bool result = _lazy._func == null;
+ _mutex.unlock ();
+ return result;
+ }
+ }
+
+ public GLib.Error? exception {get {return null;}}
+
+ public unowned G wait () throws Vala.FutureError {
+ _mutex.lock ();
+ if (_lazy._func != null) {
+ if (_state == State.EVAL) {
+ _eval.wait (_mutex);
+ _mutex.unlock ();
+ } else {
+ do_eval ();
+ }
+ } else {
+ _mutex.unlock ();
+ }
+ return _lazy._value;
+ }
+
+ public unowned bool wait_until (int64 end_time, out unowned G? value = null) throws
Vala.FutureError {
+ _mutex.lock ();
+ if (_lazy._func != null) {
+ if (_state == State.EVAL) {
+ bool res = _eval.wait_until (_mutex, end_time);
+ _mutex.unlock ();
+ if (!res) {
+ value = null;
+ return false;
+ }
+ } else {
+ do_eval ();
+ }
+ } else {
+ _mutex.unlock ();
+ }
+ value = _lazy._value;
+ return true;
+ }
+
+ public async unowned G wait_async () throws Vala.FutureError {
+ _mutex.lock ();
+ if (_lazy._func != null) {
+ if (_state == State.EVAL) {
+ _when_done += SourceFuncArrayElement(wait_async.callback);
+ yield Vala.Utils.Async.yield_and_unlock (_mutex);
+ } else {
+ do_eval ();
+ }
+ } else {
+ _mutex.unlock ();
+ }
+ return _lazy.value;
+ }
+
+ private void do_eval () {
+ _state = State.EVAL;
+ _mutex.unlock ();
+
+ _lazy._value = _lazy._func ();
+
+ _mutex.lock ();
+ _lazy._func = null;
+ _state = State.UNLOCK;
+ _eval.broadcast ();
+ _mutex.unlock ();
+
+ Vala.Future.SourceFuncArrayElement<G>[] when_done = (owned)_when_done;
+ for (int i = 0; i < when_done.length; i++) {
+ when_done[i].func ();
+ }
+ }
+
+ private Mutex _mutex = Mutex ();
+ private Cond _eval = Cond ();
+ private Lazy<G> _lazy;
+ private State _state = State.UNLOCK;
+ private Vala.Future.SourceFuncArrayElement<G>[]? _when_done;
+ private enum State {
+ UNLOCK,
+ EVAL
+ }
+ }
}
diff --git a/gee/lightmapfuture.vala b/gee/lightmapfuture.vala
new file mode 100644
index 0000000..3bbcad2
--- /dev/null
+++ b/gee/lightmapfuture.vala
@@ -0,0 +1,62 @@
+/* lightmapfuture.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+internal class Vala.LightMapFuture<A, G> : Object, Future<A> {
+ public LightMapFuture (Future<G> base_future, owned Future.LightMapFunc<A, G> func) {
+ _base = base_future;
+ _func = (owned)func;
+ }
+
+ public bool ready {
+ get {
+ return _base.ready;
+ }
+ }
+
+ public GLib.Error exception {
+ get {
+ return _base.exception;
+ }
+ }
+
+ public unowned A wait () throws Vala.FutureError {
+ return _func (_base.wait ());
+ }
+
+ public bool wait_until (int64 end_time, out unowned A? value = null) throws Vala.FutureError {
+ unowned G arg;
+ bool result;
+ value = null;
+ if ((result = _base.wait_until (end_time, out arg))) {
+ value = _func (arg);
+ }
+ return result;
+ }
+
+ public async unowned A wait_async () throws Vala.FutureError {
+ unowned G arg = yield _base.wait_async ();
+ return _func (arg);
+ }
+
+ private Future<G> _base;
+ private Future.LightMapFunc<A, G> _func;
+}
+
diff --git a/gee/linkedlist.vala b/gee/linkedlist.vala
index 16d82da..742e88b 100644
--- a/gee/linkedlist.vala
+++ b/gee/linkedlist.vala
@@ -4,6 +4,7 @@
* Copyright (C) 2005 David Waite
* Copyright (C) 2007-2008 Jürg Billeter
* Copyright (C) 2009 Mark Lee, Didier Villevalois
+ * Copyright (C) 2010-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -24,6 +25,8 @@
* Didier 'Ptitjes Villevalois <ptitjes free fr>
*/
+using Vala.Utils.Assume;
+
/**
* Doubly-linked list implementation of the {@link List} interface.
*
@@ -37,12 +40,18 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
private int _stamp = 0;
private Node<G>? _head = null;
private weak Node<G>? _tail = null;
+ private Functions.EqualDataFuncClosure<G> _equal_func;
/**
* The elements' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<G> equal_func { private set; get; }
+ public EqualDataFunc<G> equal_func {
+ private set {}
+ get {
+ return _equal_func.func;
+ }
+ }
/**
* Constructs a new, empty linked list.
@@ -56,7 +65,11 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
if (equal_func == null) {
equal_func = Functions.get_equal_func_for (typeof (G));
}
- this.equal_func = equal_func;
+ _equal_func = new Functions.EqualDataFuncClosure<G> ((owned)equal_func);
+ }
+
+ private LinkedList.with_closures (owned Functions.EqualDataFuncClosure<G> equal_func) {
+ _equal_func = equal_func;
}
~LinkedList () {
@@ -173,7 +186,9 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
assert (index < this._size);
unowned Node<G>? n = this._get_node_at (index);
+#if !DISABLE_INTERNAL_ASSERTS
assert (n != null);
+#endif
return n.data;
}
@@ -243,7 +258,9 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
assert (index < this._size);
unowned Node<G>? n = this._get_node_at (index);
+#if !DISABLE_INTERNAL_ASSERTS
assert (n != null);
+#endif
G element = n.data;
this._remove_node (n);
return element;
@@ -257,7 +274,7 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
return_val_if_fail (start >= 0, null);
return_val_if_fail (stop <= this._size, null);
- List<G> slice = new LinkedList<G> (this.equal_func);
+ List<G> slice = new LinkedList<G>.with_closures (_equal_func);
weak Node<G> n = this._get_node_at (start);
for (int i = start; i < stop; i++) {
slice.add (n.data);
@@ -430,188 +447,229 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
}
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G>, BidirIterator<G>,
ListIterator<G>, BidirListIterator<G> {
- private bool started = false;
- private bool removed = false;
- private unowned Node<G>? position;
- private int _stamp;
- private LinkedList<G> _list;
- private int _index;
-
public Iterator (LinkedList<G> list) {
this._list = list;
- this.position = null;
+ this._position = null;
this._index = -1;
this._stamp = list._stamp;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _removed = iter._removed;
+ _position = iter._position;
+ _stamp = iter._stamp;
+ _list = iter._list;
+ _index = iter._index;
+ }
+
public bool next () {
assert (this._stamp == this._list._stamp);
- if (this.removed) {
- if (this.position != null) {
- this.removed = false;
+ if (GLib.unlikely (_position == null)) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!_removed);
+#else
+ assume (!_removed);
+#endif
+ if (_list._head != null) {
+ _position = _list._head;
+ _index = 0;
return true;
} else {
return false;
}
- } else if (!this.started) {
- if (this._list._head != null) {
- this.started = true;
- this.position = this._list._head;
- this._index++;
- return true;
- } else {
- return false;
- }
- } else if (this.position != null) {
- if (this.position.next != null) {
- this.position = this.position.next;
- this._index++;
+ } else {
+ if (_position.next != null) {
+ _position = _position.next;
+ _index++;
+ _removed = false;
return true;
} else {
return false;
}
}
- return false;
}
public bool has_next () {
- assert (this._stamp == this._list._stamp);
+ assert (_stamp == _list._stamp);
- if (this.removed) {
- return this.position != null;
- } else if (!this.started) {
- return this._list._head != null;
- } else if (this.position != null) {
- return this.position.next != null;
+ if (GLib.unlikely (_position == null)) {
+ return _list._head != null;
+ } else {
+ return _position.next != null;
}
- return false;
}
public bool first () {
- assert (this._stamp == this._list._stamp);
- if (this._list.size == 0) {
+ assert (_stamp == _list._stamp);
+
+ if (_list.size == 0) {
return false;
}
- this.position = this._list._head;
- this.started = true;
- this._index = 0;
- this.removed = false;
- return this.position != null;
+ _position = _list._head;
+ _index = 0;
+ _removed = false;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_position != null);
+#endif
+ return true;
}
public new G get () {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
+ assert (_position != null && !_removed);
- return this.position.data;
+ return _position.data;
}
public void remove () {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
+ assert (_position != null && !_removed);
- unowned Node<G>? new_position = this.position.next;
- if (new_position == null) {
- started = false;
+ unowned Node<G>? new_position = _position.prev;
+ _list._remove_node (_position);
+ _position = new_position;
+ if (_position != null) {
+ _removed = true;
}
- _list._remove_node (this.position);
- this.position = new_position;
- this.removed = true;
- this._stamp = this._list._stamp;
+ _index--;
+ _stamp = _list._stamp;
}
public bool previous () {
- assert (this._stamp == this._list._stamp);
+ assert (_stamp == _list._stamp);
- if (!this.started) {
- this.position = null;
+ if (GLib.likely (_position != null)) {
+ if (GLib.unlikely (_removed)) {
+ _removed = false;
+ return true;
+ } else if (GLib.likely(_position.prev != null)) {
+ _position = _position.prev;
+ _index--;
+ return true;
+ } else {
+ return false;
+ }
+ } else {
return false;
- } else if (this.position != null && this.position.prev != null) {
- this.position = this.position.prev;
- this._index--;
- return true;
}
- return false;
}
public bool has_previous () {
- assert (this._stamp == this._list._stamp);
+ assert (_stamp == _list._stamp);
- if (!this.started) {
+ if (GLib.likely (_position != null)) {
+ if (GLib.unlikely (_removed)) {
+ return true;
+ } else {
+ return _position.prev != null;
+ }
+ } else {
return false;
- } else if (this.position != null) {
- return this.position.prev != null;
}
- return false;
}
public bool last () {
- assert (this._stamp == this._list._stamp);
+ assert (_stamp == _list._stamp);
- if (this._list.size == 0) {
+ if (_list.size == 0) {
return false;
}
- this.position = this._list._tail;
- this.started = true;
- this._index = this._list._size - 1;
- return this.position != null;
+ _position = _list._tail;
+ _index = _list._size - 1;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_position != null);
+#endif
+ return true;
}
public new void set (G item) {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
+ assert (_position != null && !_removed);
- this.position.data = item;
+ _position.data = item;
}
public void insert (G item) {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
Node<G> n = new Node<G> (item);
- if (this.position.prev != null) {
- Node<G> position = (owned) this.position.prev.next;
- n.prev = position.prev;
- position.prev = n;
- n.next = (owned) position;
- weak Node<G> _n = n;
- _n.prev.next = (owned) n;
+ unowned Node<G> n_ref = n;
+ if (_position == null) {
+ Node<G>? position = (owned)_list._head;
+ if (position != null) {
+ position.prev = n;
+ n.next = (owned)position;
+ } else {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_list._tail == null);
+#endif
+ _list._tail = n;
+ }
+ if (_position == null) {
+ _position = n_ref;
+ }
+ _list._head = (owned)n;
} else {
- Node<G> position = (owned) this._list._head;
- position.prev = n;
- n.next = (owned) position;
- this._list._head = (owned) n;
+ if (_removed) {
+ if (_position.next != null) {
+ n.next = (owned)_position.next;
+ n.next.prev = n;
+ } else {
+ _list._tail = n;
+ }
+ n.prev = _position;
+ _position.next = (owned)n;
+ _position = n_ref;
+ } else {
+ n.prev = _position.prev;
+ _position.prev = n;
+ if (n.prev != null) {
+ n.next = (owned)n.prev.next;
+ n.prev.next = (owned)n;
+ } else {
+ n.next = (owned)_list._head;
+ _list._head = (owned)n;
+ }
+ }
}
- this._list._size++;
- this._index++;
+ _list._size++;
+ _index++;
_stamp = _list._stamp;
}
public void add (G item) {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
Node<G> n = new Node<G> (item);
- if (this.position.next != null) {
- this.position.next.prev = n;
- n.next = (owned) this.position.next;
+ unowned Node<G> n_ref = n;
+ if (_position == null) {
+ Node<G> position = (owned)_list._head;
+ position.prev = n;
+ n.next = (owned)position;
+ _list._head = (owned) n;
} else {
- this._list._tail = n;
+ if (_position.next != null) {
+ _position.next.prev = n;
+ n.next = (owned)_position.next;
+ } else {
+ _list._tail = n;
+ }
+ _position.next = (owned)n;
+ _position.next.prev = _position;
}
- this.position.next = (owned) n;
- this.position.next.prev = this.position;
- this.position = this.position.next;
- this._list._size++;
- this._index++;
+ _position = n_ref;
+ _removed = false;
+ _list._size++;
+ _index++;
_stamp = _list._stamp;
}
public int index () {
- assert (this._stamp == this._list._stamp);
- assert (this.position != null);
+ assert (_stamp == _list._stamp);
+ assert (_position != null && !_removed);
- return this._index;
+ return _index;
}
public bool read_only {
@@ -622,27 +680,47 @@ public class Vala.LinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
public bool valid {
get {
- return !this.removed && this.position != null;
+ return !_removed && _position != null;
}
}
public bool foreach (ForallFunc<G> f) {
assert (_stamp == _list._stamp);
- if (!started) {
- position = _list._head;
- if (position != null)
- started = true;
+ if (_position == null) {
+ _position = _list._head;
+ }
+ if (_removed) {
+ _position = _position.next;
+ _removed = false;
}
- removed = false;
- while (position != null) {
- if (!f (position.data)) {
+ while (_position != null) {
+ if (!f (_position.data)) {
return false;
}
- position = position.next;
+ _position = _position.next;
}
- position = _list._tail;
+ _position = _list._tail;
return true;
}
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected bool _removed = false;
+ protected unowned Node<G>? _position;
+ protected int _stamp;
+ protected LinkedList<G> _list;
+ protected int _index;
}
private unowned Node<G>? _get_node_at (int index) {
diff --git a/gee/listiterator.vala b/gee/listiterator.vala
index a57a7df..e1f62f3 100644
--- a/gee/listiterator.vala
+++ b/gee/listiterator.vala
@@ -31,7 +31,10 @@ public interface Vala.ListIterator<G> : Vala.Iterator<G> {
/**
* Adds the specified item after the current item in the iteration. The
- * cursor is moved to point to the new added item.
+ * iterator is moved to the point of the new added item.
+ *
+ * Please note that if iterator points in-between elements the element
+ * is added after the current element and iterator point on it.
*/
public abstract void add (G item);
diff --git a/gee/map.vala b/gee/map.vala
index e48cb8a..33da2f2 100644
--- a/gee/map.vala
+++ b/gee/map.vala
@@ -34,7 +34,7 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
* Specifies whether this map is empty.
*/
public virtual bool is_empty { get { return size == 0; } }
-
+
/**
* Specifies whether this collection can change - i.e. wheather {@link set},
* {@link remove} etc. are legal operations.
@@ -71,7 +71,7 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
public abstract V value { get; set; }
/**
- * ``true'' if the setting value is permitted.
+ * ``true`` if the setting value is permitted.
*/
public abstract bool read_only { get; }
}
@@ -86,20 +86,6 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
public abstract bool has_key (K key);
/**
- * Determines whether this map contains the specified key.
- *
- * @param key the key to locate in the map
- *
- * @return ``true`` if key is found, ``false`` otherwise
- *
- * @deprecated Use {@link has_key} method instead.
- */
- [Version (deprecated = true)]
- public bool contains (K key) {
- return has_key(key);
- }
-
- /**
* Determines whether this map has the specified key/value entry.
*
* @param key the key to locate in the map
@@ -138,21 +124,6 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
public abstract bool unset (K key, out V? value = null);
/**
- * Removes the specified key from this map.
- *
- * @param key the key to remove from the map
- * @param value the receiver variable for the removed value
- *
- * @return ``true`` if the map has been changed, ``false`` otherwise
- *
- * @deprecated Use {@link unset} method instead.
- */
- [Version (deprecated = true)]
- public bool remove (K key, out V? value = null) {
- return unset (key, out value);
- }
-
- /**
* Removes all items from this collection. Must not be called on
* read-only collections.
*/
@@ -187,20 +158,7 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
foreach (K key in map.keys) {
changed = changed | unset (key);
}
- return changed;
- }
-
- /**
- * Removes all items from this map that are common to the input map
- * and this map.
- *
- * @param map the map which common items are deleted from this map
- *
- * @deprecated Use {@link unset_all} method instead.
- */
- [Version (deprecated = true)]
- public bool remove_all (Map<K,V> map) {
- return unset_all (map);
+ return changed;
}
/**
@@ -218,18 +176,6 @@ public interface Vala.Map<K,V> : Object, Iterable<Map.Entry<K,V>> {
}
/**
- * Returns ``true`` it this map contains all items as the input map.
- *
- * @param map the map which items will be compared with this map
- *
- * @deprecated Use {@link has_all} method instead.
- */
- [Version (deprecated = true)]
- public bool contains_all (Map<K,V> map) {
- return has_all (map);
- }
-
- /**
* The read-only view this map.
*/
public abstract Map<K,V> read_only_view { owned get; }
diff --git a/gee/mapiterator.vala b/gee/mapiterator.vala
index 2ad5890..6d575ef 100644
--- a/gee/mapiterator.vala
+++ b/gee/mapiterator.vala
@@ -82,28 +82,28 @@ public interface Vala.MapIterator<K,V> : Object {
* {@link next}).
*/
public abstract void unset ();
-
+
/**
- * Determines wheather the call to {@link get_key}, {@link get_value} and
+ * Determines wheather the call to {@link get_key}, {@link get_value} and
* {@link set_value} is legal. It is false at the beginning and after
* {@link unset} call and true otherwise.
*/
public abstract bool valid { get; }
-
+
/**
* Determines wheather the call to {@link set_value} is legal assuming the
* iterator is valid. The value must not change in runtime hence the user
* of iterator may cache it.
*/
public abstract bool mutable { get; }
-
+
/**
* Determines wheather the call to {@link unset} is legal assuming the
* iterator is valid. The value must not change in runtime hence the user
* of iterator may cache it.
*/
public abstract bool read_only { get; }
-
+
/**
* Standard aggragation function.
*
@@ -121,9 +121,9 @@ public interface Vala.MapIterator<K,V> : Object {
seed = f (get_key (), get_value (), (owned) seed);
return (owned) seed;
}
-
+
/**
- * Apply function to each element returned by iterator.
+ * Apply function to each element returned by iterator.
*
* Operation moves the iterator to last element in iteration. If iterator
* points at some element it will be included in iteration.
diff --git a/gee/multimap.vala b/gee/multimap.vala
index 6c1748b..88bcb72 100644
--- a/gee/multimap.vala
+++ b/gee/multimap.vala
@@ -29,7 +29,7 @@ public interface Vala.MultiMap<K,V> : Object {
* The number of key/value pairs in this map.
*/
public abstract int size { get; }
-
+
/**
* Specifies whether this collection can change - i.e. wheather {@link set},
* {@link remove} etc. are legal operations.
@@ -124,4 +124,10 @@ public interface Vala.MultiMap<K,V> : Object {
* The type of the values in this multimap.
*/
public Type value_type { get { return typeof (V); } }
+
+ public virtual MultiMap<K, V> read_only_view {
+ owned get {
+ return new ReadOnlyMultiMap<K, V> (this);
+ }
+ }
}
diff --git a/gee/multiset.vala b/gee/multiset.vala
index 7b9f774..b984e17 100644
--- a/gee/multiset.vala
+++ b/gee/multiset.vala
@@ -33,4 +33,23 @@ public interface Vala.MultiSet<G> : Collection<G> {
* @return the number of occurences of the item in this multiset.
*/
public abstract int count (G item);
+
+ /**
+ * The read-only view of this set.
+ */
+ public virtual new MultiSet<G> read_only_view {
+ owned get {
+ return new ReadOnlyMultiSet<G> (this);
+ }
+ }
+
+ /**
+ * Returns an immutable empty set.
+ *
+ * @return an immutable empty set
+ */
+ public static Set<G> empty<G> () {
+ return new HashSet<G> ().read_only_view;
+ }
}
+
diff --git a/gee/priorityqueue.vala b/gee/priorityqueue.vala
index 04d0a00..6f19e22 100644
--- a/gee/priorityqueue.vala
+++ b/gee/priorityqueue.vala
@@ -1,7 +1,7 @@
/* priorityqueue.vala
*
* Copyright (C) 2009 Didier Villevalois
- * Copyright (C) 2012 Maciej Piechotka
+ * Copyright (C) 2012-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -46,7 +46,12 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
* The elements' comparator function.
*/
[CCode (notify = false)]
- public CompareDataFunc<G> compare_func { private set; get; }
+ public CompareDataFunc<G> compare_func {
+ private set {}
+ get {
+ return _compare_func;
+ }
+ }
private int _size = 0;
private int _stamp = 0;
@@ -55,14 +60,15 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
private Type2Node<G>? _lm_head = null;
private Type2Node<G>? _lm_tail = null;
private Type1Node<G>? _p = null;
- private Type1Node<G>?[] _a = new Type1Node<G>?[0];
+ private Type1Node<G>?[] _a;
private NodePair<G>? _lp_head = null;
- private NodePair<G>? _lp_tail = null;
+ private unowned NodePair<G>? _lp_tail = null;
private bool[] _b = new bool[0];
private Type1Node<G>? _ll_head = null;
private Type1Node<G>? _ll_tail = null;
private unowned Node<G> _iter_head = null;
private unowned Node<G> _iter_tail = null;
+ private CompareDataFunc<G> _compare_func;
/**
* Constructs a new, empty priority queue.
@@ -76,7 +82,8 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
if (compare_func == null) {
compare_func = Functions.get_compare_func_for (typeof (G));
}
- this.compare_func = compare_func;
+ _compare_func = (owned)compare_func;
+ _a = new Type1Node<G>?[0];
}
/**
@@ -343,7 +350,11 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
_lm_head = null;
_lm_tail = null;
_p = null;
+#if VALA_0_16
_a = new Type1Node<G>?[0];
+#else
+ _a = new Type1Node<G>[0];
+#endif
_lp_head = null;
_lp_tail = null;
_b = new bool[0];
@@ -360,6 +371,18 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
return new Iterator<G> (this);
}
+ /**
+ * {@inheritDoc}
+ */
+ public override bool foreach (ForallFunc<G> f) {
+ for (unowned Node<G>? current = _iter_head; current != null; current = current.iter_next) {
+ if (!f (current.data)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
private inline int _compare (Node<G> node1, Node<G> node2) {
// Assume there can't be two nodes pending drop
if (node1.pending_drop) {
@@ -434,7 +457,7 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
#if DEBUG
_dump ("After swap: %p(%s) %p(%s)".printf(node1, (string)node1.data, node2,
(string)node2.data));
- #endif
+ #endif
}
private inline void _move_data (Node<G> target, Node<G> source) {
@@ -525,7 +548,7 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
#endif
if (_lp_head != null) {
- NodePair<G> pair = _lp_head;
+ unowned NodePair<G> pair = _lp_head;
_link (pair.node1, pair.node2);
return true;
}
@@ -697,12 +720,12 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
node.brothers_next.pair = pair;
node.pair = pair;
if (_lp_head == null) {
- _lp_head = pair;
_lp_tail = pair;
+ _lp_head = (owned)pair;
} else {
pair.lp_prev = _lp_tail;
- _lp_tail.lp_next = pair;
- _lp_tail = pair;
+ _lp_tail.lp_next = (owned)pair;
+ _lp_tail = _lp_tail.lp_next;
}
// There is now an even number of child of such degree
_b[degree] = false;
@@ -820,20 +843,20 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
// Maintain LP
if (node.pair != null) {
- NodePair<G> pair = node.pair;
+ unowned NodePair<G> pair = node.pair;
Type1Node<G> other = (pair.node1 == node ? pair.node2 : pair.node1);
node.pair = null;
other.pair = null;
- if (pair.lp_prev != null) {
- pair.lp_prev.lp_next = pair.lp_next;
- } else {
- _lp_head = pair.lp_next;
- }
if (pair.lp_next != null) {
pair.lp_next.lp_prev = pair.lp_prev;
} else {
_lp_tail = pair.lp_prev;
}
+ if (pair.lp_prev != null) {
+ pair.lp_prev.lp_next = (owned)pair.lp_next;
+ } else {
+ _lp_head = (owned)pair.lp_next;
+ }
}
}
@@ -1101,11 +1124,12 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
#endif
}
+ [Compact]
private class NodePair<G> {
- public weak NodePair<G>? lp_prev = null;
+ public unowned NodePair<G>? lp_prev = null;
public NodePair<G>? lp_next = null;
- public Type1Node<G> node1 = null;
- public Type1Node<G> node2 = null;
+ public unowned Type1Node<G> node1 = null;
+ public unowned Type1Node<G> node2 = null;
public NodePair (Type1Node<G> node1, Type1Node<G> node2) {
this.node1 = node1;
@@ -1114,11 +1138,6 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
}
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G> {
- private PriorityQueue<G> queue;
- private unowned Node<G>? position;
- private unowned Node<G>? previous;
- private int stamp;
-
public Iterator (PriorityQueue<G> queue) {
this.queue = queue;
this.position = null;
@@ -1126,6 +1145,13 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
this.stamp = queue._stamp;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ queue = iter.queue;
+ position = iter.position;
+ previous = iter.previous;
+ stamp = iter.stamp;
+ }
+
public bool next () {
unowned Node<G>? next = _get_next_node ();
if (next != null) {
@@ -1203,5 +1229,24 @@ public class Vala.PriorityQueue<G> : Vala.AbstractQueue<G> {
}
return true;
}
+
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected PriorityQueue<G> queue;
+ protected unowned Node<G>? position;
+ protected unowned Node<G>? previous;
+ protected int stamp;
}
}
diff --git a/gee/promise.vala b/gee/promise.vala
new file mode 100644
index 0000000..077f45b
--- /dev/null
+++ b/gee/promise.vala
@@ -0,0 +1,217 @@
+/* promise.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Promise allows to set a value with associated {@link Future}. Please note that
+ * value can be stored only once.
+ *
+ * Typically the producer will create promise and return {@link future} while
+ * keeping the promise to itself. Then when value is ready it can call {@link set_value}.
+ *
+ * @see Future
+ * @see task
+ */
+public class Vala.Promise<G> {
+ public Promise () {
+ _future = new Future<G> ();
+ }
+
+ ~Promise () {
+ _future.abandon ();
+ }
+
+ /**
+ * {@link Future} value of this promise
+ */
+ public Vala.Future<G> future {
+ get {
+ return _future;
+ }
+ }
+
+ /**
+ * Sets the value of the future.
+ *
+ * @param value Value of future
+ */
+ public void set_value (owned G value) {
+ _future.set_value ((owned)value);
+ }
+
+ /**
+ * Sets the exception.
+ *
+ * @param exception Exception thrown
+ */
+ public void set_exception (owned GLib.Error exception) {
+ _future.set_exception ((owned)exception);
+ }
+
+ private class Future<G> : Object, Vala.Future<G> {
+ public Future () {
+ _when_done = new Vala.Future.SourceFuncArrayElement<G>[0];
+ }
+
+ public bool ready {
+ get {
+ _mutex.lock ();
+ bool result = _state != State.INIT;
+ _mutex.unlock ();
+ return result;
+ }
+ }
+
+ public GLib.Error? exception {
+ get {
+ return _exception;
+ }
+ }
+
+ public unowned G wait () throws FutureError {
+ _mutex.lock ();
+ State state = _state;
+ if (_state == State.INIT) {
+ _set.wait (_mutex);
+ state = _state;
+ }
+ assert (state != State.INIT);
+ _mutex.unlock ();
+ switch (state) {
+ case State.ABANDON:
+ throw new FutureError.ABANDON_PROMISE ("Promise has been abandon");
+ case State.EXCEPTION:
+ throw new FutureError.EXCEPTION ("Exception has been thrown");
+ case State.READY:
+ return _value;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public bool wait_until (int64 end_time, out unowned G? value = null) throws FutureError {
+ _mutex.lock ();
+ State state = _state;
+ if (state == State.INIT) {
+ _set.wait_until (_mutex, end_time);
+ state = _state;
+ }
+ _mutex.unlock ();
+ switch (state) {
+ case State.INIT:
+ value = null;
+ return false;
+ case State.ABANDON:
+ throw new FutureError.ABANDON_PROMISE ("Promise has been abandon");
+ case State.EXCEPTION:
+ throw new FutureError.EXCEPTION ("Exception has been thrown");
+ case State.READY:
+ value = _value;
+ return true;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ public async unowned G wait_async () throws Vala.FutureError {
+ _mutex.lock ();
+ State state = _state;
+ if (state == State.INIT) {
+ _when_done += SourceFuncArrayElement(wait_async.callback);
+ yield Vala.Utils.Async.yield_and_unlock (_mutex);
+ state = _state;
+ } else {
+ _mutex.unlock ();
+ }
+ assert (state != State.INIT);
+ switch (state) {
+ case State.ABANDON:
+ throw new FutureError.ABANDON_PROMISE ("Promise has been abandon");
+ case State.EXCEPTION:
+ throw new FutureError.EXCEPTION ("Exception has been thrown");
+ case State.READY:
+ return _value;
+ default:
+ assert_not_reached ();
+ }
+ }
+
+ internal void set_value (owned G value) {
+ _mutex.lock ();
+ assert (_state == State.INIT);
+ _state = State.READY;
+ _value = (owned)value;
+ _set.broadcast ();
+ _mutex.unlock ();
+ Vala.Future.SourceFuncArrayElement<G>[] when_done = (owned)_when_done;
+ for (int i = 0; i < when_done.length; i++) {
+ when_done[i].func ();
+ }
+ }
+
+ internal void set_exception (owned GLib.Error? exception) {
+ _mutex.lock ();
+ assert (_state == State.INIT);
+ _state = State.EXCEPTION;
+ _exception = (owned)exception;
+ _set.broadcast ();
+ _mutex.unlock ();
+ Vala.Future.SourceFuncArrayElement<G>[] when_done = (owned)_when_done;
+ for (int i = 0; i < when_done.length; i++) {
+ when_done[i].func ();
+ }
+ }
+
+ internal void abandon () {
+ _mutex.lock ();
+ if (_state != State.INIT) {
+ _mutex.unlock ();
+ return;
+ }
+ assert (_state == State.INIT);
+ _state = State.ABANDON;
+ _set.broadcast ();
+ _mutex.unlock ();
+ Vala.Future.SourceFuncArrayElement<G>[] when_done = (owned)_when_done;
+ for (int i = 0; i < when_done.length; i++) {
+ when_done[i].func ();
+ }
+ }
+
+ private Mutex _mutex = Mutex ();
+ private Cond _set = Cond ();
+ private State _state;
+ private G? _value;
+ private GLib.Error? _exception;
+ private Vala.Future.SourceFuncArrayElement<G>[]? _when_done;
+
+ private enum State {
+ INIT,
+ ABANDON,
+ EXCEPTION,
+ READY
+ }
+ }
+ private Future<G> _future;
+}
+
diff --git a/gee/queue.vala b/gee/queue.vala
index df678d1..938d29e 100644
--- a/gee/queue.vala
+++ b/gee/queue.vala
@@ -52,12 +52,12 @@ public interface Vala.Queue<G> : Collection<G> {
public const int UNBOUNDED_CAPACITY = -1;
/**
- * The capacity of this queue (or ``null`` if capacity is not bound).
+ * The capacity of this queue (or ``UNBOUNDED_CAPACITY`` if capacity is not bound).
*/
public abstract int capacity { get; }
/**
- * The remaining capacity of this queue (or ``null`` if capacity is not
+ * The remaining capacity of this queue (or ``UNBOUNDED_CAPACITY`` if capacity is not
* bound).
*/
public abstract int remaining_capacity { get; }
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
index f810f20..92138f0 100644
--- a/gee/readonlycollection.vala
+++ b/gee/readonlycollection.vala
@@ -1,6 +1,7 @@
/* readonlycollection.vala
*
* Copyright (C) 2007-2008 Jürg Billeter
+ * Copyright (C) 2010-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -46,7 +47,7 @@ internal class Vala.ReadOnlyCollection<G> : Object, Traversable<G>, Iterable<G>,
public bool is_empty {
get { return _collection.is_empty; }
}
-
+
/**
* {@inheritDoc}
*/
@@ -76,7 +77,7 @@ internal class Vala.ReadOnlyCollection<G> : Object, Traversable<G>, Iterable<G>,
/**
* {@inheritDoc}
*/
- public Vala.Iterator<A> stream<A> (owned StreamFunc<A> f) {
+ public Vala.Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
return _collection.stream<A> ((owned)f);
}
@@ -214,7 +215,7 @@ internal class Vala.ReadOnlyCollection<G> : Object, Traversable<G>, Iterable<G>,
return _iter.foreach (f);
}
- public Vala.Iterator<A> stream<A> (owned StreamFunc<A, G> f) {
+ public Vala.Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
return _iter.stream<A> ((owned)f);
}
@@ -225,6 +226,24 @@ internal class Vala.ReadOnlyCollection<G> : Object, Traversable<G>, Iterable<G>,
public Vala.Iterator<G> chop (int offset, int length = -1) {
return _iter.chop ( offset, length);
}
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] iters = _iter.tee (forks);
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ if (iters[0] == _iter) {
+ result[0] = this;
+ } else {
+ result[0] = new Iterator<G> (iters[0]);
+ }
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G> (iters[i]);
+ }
+ return result;
+ }
+ }
}
public virtual Collection<G> read_only_view {
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
index c14ebbe..1307fd3 100644
--- a/gee/readonlymap.vala
+++ b/gee/readonlymap.vala
@@ -244,7 +244,7 @@ internal class Vala.ReadOnlyMap<K,V> : Object, Traversable<Map.Entry<K,V>>, Iter
return _map.chop (offset, length);
}
- protected class MapIterator<K,V> : Object, Vala.MapIterator<K,V> {
+ internal class MapIterator<K,V> : Object, Vala.MapIterator<K,V> {
protected Vala.MapIterator<K,V> _iter;
public MapIterator (Vala.MapIterator<K,V> iterator) {
@@ -274,19 +274,19 @@ internal class Vala.ReadOnlyMap<K,V> : Object, Traversable<Map.Entry<K,V>>, Iter
public void unset () {
assert_not_reached ();
}
-
+
public bool read_only {
get {
return true;
}
}
-
+
public bool mutable {
get {
return false;
}
}
-
+
public bool valid {
get {
return _iter.valid;
diff --git a/gee/readonlymultimap.vala b/gee/readonlymultimap.vala
new file mode 100644
index 0000000..a7d51bc
--- /dev/null
+++ b/gee/readonlymultimap.vala
@@ -0,0 +1,131 @@
+/* readonlymultimap.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Read-only view for {@link MultiMap} collections.
+ *
+ * This class decorates any class which implements the {@link MultiMap}
+ * interface by making it read only. Any method which normally modify data will
+ * throw an error.
+ *
+ * @see MultiMap
+ */
+internal class Vala.ReadOnlyMultiMap<K, V> : Object, MultiMap<K, V> {
+ /**
+ * Constructs a read-only multi-set that mirrors the content of the specified
+ * list.
+ *
+ * @param multiset the multi-set to decorate.
+ */
+ public ReadOnlyMultiMap (MultiMap<K, V> multimap) {
+ this._multimap = multimap;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int size { get { return _multimap.size; } }
+
+ /**
+ * {@inheritDoc}
+ */
+ public bool read_only { get { return true; } }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Set<K> get_keys () {
+ return _multimap.get_keys ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public MultiSet<K> get_all_keys () {
+ return _multimap.get_all_keys ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public Collection<V> get_values () {
+ return _multimap.get_values ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public bool contains (K key) {
+ return _multimap.contains (key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public new Collection<V> get (K key) {
+ return _multimap.get (key);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public new void set (K key, V value) {
+ assert_not_reached ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public bool remove (K key, V value) {
+ assert_not_reached ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public bool remove_all (K key) {
+ assert_not_reached ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public void clear () {
+ assert_not_reached ();
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public MapIterator<K, V> map_iterator () {
+ return new ReadOnlyMap.MapIterator<K, V> (_multimap.map_iterator ());
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public virtual new MultiMap<K, V> read_only_view { owned get { return this; } }
+
+ private MultiMap<K, V> _multimap;
+}
diff --git a/gee/readonlymultiset.vala b/gee/readonlymultiset.vala
new file mode 100644
index 0000000..f5cd2c1
--- /dev/null
+++ b/gee/readonlymultiset.vala
@@ -0,0 +1,57 @@
+/* readonlymultiset.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+using GLib;
+
+/**
+ * Read-only view for {@link MultiSet} collections.
+ *
+ * This class decorates any class which implements the {@link Collection}
+ * interface by making it read only. Any method which normally modify data will
+ * throw an error.
+ *
+ * @see MultiSet
+ */
+internal class Vala.ReadOnlyMultiSet<G> : Vala.ReadOnlyCollection<G>, MultiSet<G> {
+ /**
+ * Constructs a read-only multi-set that mirrors the content of the specified
+ * list.
+ *
+ * @param multiset the multi-set to decorate.
+ */
+ public ReadOnlyMultiSet (MultiSet<G> multiset) {
+ base (multiset);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public int count (G item) {
+ return ((Vala.MultiSet<G>) _collection).count (item);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ public virtual new MultiSet<G> read_only_view { owned get { return this; } }
+}
+
diff --git a/gee/streamiterator.vala b/gee/streamiterator.vala
new file mode 100644
index 0000000..06d8c2b
--- /dev/null
+++ b/gee/streamiterator.vala
@@ -0,0 +1,183 @@
+/* streamiterator.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+internal class Vala.StreamIterator<A, G> : GLib.Object, Traversable<A>, Iterator<A> {
+ public StreamIterator (Iterator<G> outer, owned StreamFunc<A, G> func) {
+ _outer = outer;
+ _func = (owned)func;
+ _current = null;
+ _need_next = true;
+ _finished = false;
+
+ _state = _func (Traversable.Stream.YIELD, null, out _current);
+ switch (_state) {
+ case Traversable.Stream.WAIT:
+ case Traversable.Stream.YIELD:
+ _need_next = !_outer.valid;
+ break;
+ case Traversable.Stream.CONTINUE:
+ if (_outer.valid) {
+ _state = _func (_state, new Lazy<G> (() => {
+ return _outer.get ();
+ }), out _current);
+ switch (_state) {
+ case Traversable.Stream.YIELD:
+ case Traversable.Stream.CONTINUE:
+ case Traversable.Stream.WAIT:
+ break;
+ case Traversable.Stream.END:
+ _finished = true;
+ return;
+ default:
+ assert_not_reached ();
+ }
+ }
+ break;
+ case Traversable.Stream.END:
+ _finished = true;
+ return;
+ }
+ }
+
+ public bool foreach (ForallFunc<A> f) {
+ Lazy<G>? current = null;
+ if (_current != null) {
+ if (!f (_current.value)) {
+ return false;
+ }
+ }
+ if (_next != null) {
+ current = (owned)_next;
+ if (!f (current.value)) {
+ return false;
+ }
+ } else if (_finished) {
+ return true;
+ }
+ unowned Iterator<G> outer = _outer;
+ unowned StreamFunc<A, G> func = _func;
+ Traversable.Stream state = _state;
+ bool need_next = _need_next;
+ bool result = true;
+ Lazy<A>? next_current;
+ Lazy<G>? outer_value = _outer_value;
+ while ((next_current = yield_next<A, G>(outer, func, ref state, ref need_next, ref
outer_value)) != null) {
+ current = (owned)next_current;
+ if (!f (current.value)) {
+ result = false;
+ break;
+ }
+ }
+ _state = state;
+ _need_next = need_next;
+ _finished = result;
+ _current = (owned)current;
+ _outer_value = (owned)outer_value;
+ return result;
+ }
+
+ public bool next () {
+ if (has_next ()) {
+ if (_current != null) {
+ _current.eval ();
+ }
+ _current = (owned)_next;
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ public bool has_next () {
+ if (_finished) {
+ return false;
+ }
+ if (_next != null) {
+ return true;
+ }
+ _next = yield_next<A, G> (_outer, _func, ref _state, ref _need_next, ref _outer_value);
+ _finished = _next == null;
+ return !_finished;
+ }
+
+ public new A get () {
+ assert (_current != null);
+ return _current.value;
+ }
+
+ public void remove () {
+ assert_not_reached ();
+ }
+
+ public bool valid { get { return _current != null; } }
+ public bool read_only { get { return true; } }
+
+ private static inline Lazy<A>? yield_next<A, G> (Iterator<G> outer, StreamFunc<A, G> func, ref
Traversable.Stream state, ref bool need_next, ref Lazy<G>? outer_value) {
+ Lazy<A>? value = null;
+ if (state != Traversable.Stream.CONTINUE)
+ state = func (state, null, out value);
+ while (true) {
+ switch (state) {
+ case Traversable.Stream.YIELD:
+ return value;
+ case Traversable.Stream.CONTINUE:
+ if (outer_value != null) {
+ outer_value.eval ();
+ }
+ if (need_next) {
+ if (!outer.has_next ()) {
+ state = func (Traversable.Stream.END, null, out value);
+ continue;
+ }
+ outer_value = new Lazy<G> (() => {
+ assert (outer.next ());
+ return outer.get ();
+ });
+ } else {
+ need_next = true;
+ outer_value = new Lazy<G> (() => {
+ return outer.get ();
+ });
+ }
+ state = func (state, outer_value, out value);
+ break;
+ case Traversable.Stream.WAIT:
+ state = func (state, null, out value);
+ break;
+ case Traversable.Stream.END:
+ return null;
+ default:
+ assert_not_reached ();
+ }
+ }
+ }
+
+ private Iterator<G> _outer;
+ private StreamFunc<A, G> _func;
+ private Lazy<G>? _outer_value;
+ private Lazy<A>? _current;
+ private Lazy<A>? _next;
+ private Traversable.Stream _state;
+ private bool _need_next;
+ private bool _finished;
+}
+
diff --git a/gee/task.vala b/gee/task.vala
new file mode 100644
index 0000000..70d5be9
--- /dev/null
+++ b/gee/task.vala
@@ -0,0 +1,95 @@
+/* task.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+namespace Vala {
+ [CCode (scope = "async")]
+ public delegate G Task<G>();
+
+ /**
+ * Schedules a task to execute asynchroniously. Internally one
+ * of threads from pool will execute the task.
+ *
+ * Note: There is limited number of threads unless environment variable
+ * ``GEE_NUM_THREADS`` is set to -1. It is not adviced to call I/O or
+ * block inside the taks. If necessary it is possible to create a new one
+ * by anyther call.
+ *
+ * @param task Task to be executed
+ * @return Future value returned by task
+ * @see async_task
+ */
+ public Future<G> task<G>(owned Task<G> task) throws GLib.ThreadError {
+ TaskData<G> tdata = new TaskData<G>();
+ tdata.function = (owned)task;
+ tdata.promise = new Promise<G>();
+ Future<G> result = tdata.promise.future;
+ TaskData.get_async_pool ().add ((owned)tdata);
+ return result;
+ }
+
+ /**
+ * Continues the execution asynchroniously in helper thread. Internally
+ * one of threads from pool will execute the task.
+ *
+ * Note: There is limited number of threads unless environment variable
+ * ``GEE_NUM_THREADS`` is set to -1. It is not adviced to call I/O or
+ * block inside the taks. If necessary it is possible to create a new one
+ * by anyther call.
+ *
+ * @see task
+ */
+ public async void async_task() throws GLib.ThreadError {
+ task<bool>(async_task.callback);
+ }
+
+ [CCode (cheader_filename = "sys/sysinfo.h", cname = "get_nprocs")]
+ private extern static int get_nprocs ();
+
+ [Compact]
+ internal class TaskData<G> {
+ public Task<G> function;
+ public Promise<G> promise;
+ public void run() {
+ promise.set_value(function());
+ }
+ private static GLib.Once<ThreadPool<TaskData>> async_pool;
+ internal static unowned ThreadPool<TaskData> get_async_pool () {
+ return async_pool.once(() => {
+ int num_threads = get_nprocs ();
+ string? gee_num_threads_str = Environment.get_variable("GEE_NUM_THREADS");
+ if (gee_num_threads_str != null) {
+ int64 result;
+ if (int64.try_parse (gee_num_threads_str, out result)) {
+ num_threads = (int)result;
+ }
+ }
+ try {
+ return new ThreadPool<TaskData>.with_owned_data((tdata) => {
+ tdata.run();
+ }, num_threads, false);
+ } catch (ThreadError err) {
+ Process.abort ();
+ }
+ });
+ }
+ }
+}
+
diff --git a/gee/teeiterator.vala b/gee/teeiterator.vala
new file mode 100644
index 0000000..b2c30d8
--- /dev/null
+++ b/gee/teeiterator.vala
@@ -0,0 +1,116 @@
+/* teeiterator.vala
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+internal class Vala.TeeIterator<G> : Object, Traversable<G>, Iterator<G> {
+ internal TeeIterator (Node<G>? head, bool valid) {
+ _head = head;
+ _valid = valid;
+ }
+
+ public bool foreach (ForallFunc<G> f) {
+ Node<G> head = (owned)_head;
+ bool valid = _valid;
+ if (valid) {
+ if (!f (head._data.get ())) {
+ return false;
+ }
+ }
+ unowned Node<G>? next_head = head._next.value;
+ while (next_head != null) {
+ head = next_head;
+ valid = true;
+ if (!f (head._data.get ())) {
+ _head = (owned)head;
+ _valid = valid;
+ return false;
+ }
+ }
+ _head = (owned)head;
+ _valid = valid;
+ return true;
+ }
+
+ public Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<G>[0];
+ } else {
+ Iterator<G>[] result = new Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new TeeIterator<G> (_head, _valid);
+ }
+ return result;
+ }
+ }
+
+ public bool next () {
+ unowned Node<G>? next = _head._next.value;
+ if (next != null) {
+ _head = next;
+ _valid = true;
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ public bool has_next () {
+ return _head._next.get () != null;
+ }
+
+ public new G get () {
+ return _head._data.get ();
+ }
+
+ public void remove () {
+ assert_not_reached ();
+ }
+
+ public bool valid { get { return _valid; } }
+
+ public bool read_only { get { return true; } }
+
+ private Node<G> _head;
+ private bool _valid;
+
+ internal static Lazy<Node<G>?> create_nodes<G> (Iterator<G> iterator, Lazy<G> dependent) {
+ return new Lazy<Node<G>?>(() => {
+ dependent.eval ();
+ if (!iterator.next ())
+ return null;
+ Lazy<G> data = new Lazy<G> (() => {return iterator.get ();});
+ Lazy<Node<G>?> next = create_nodes<G> (iterator, data);
+ return new Node<G> ((owned)data, (owned)next);
+ });
+ }
+
+ internal class Node<G> {
+ public Node (owned Lazy<G> data, owned Lazy<Node<G>?> next) {
+ _data = (owned)data;
+ _next = (owned)next;
+ }
+ public Lazy<G> _data;
+ public Lazy<Node<G>?> _next;
+ }
+
+}
+
diff --git a/gee/timsort.vala b/gee/timsort.vala
index 5d1a862..4dca2ba 100644
--- a/gee/timsort.vala
+++ b/gee/timsort.vala
@@ -94,7 +94,7 @@ internal class Vala.TimSort<G> : Object {
private int size;
private Slice<G>[] pending;
private int minimum_gallop;
- private CompareDataFunc<G> compare;
+ private unowned CompareDataFunc<G> compare;
private void do_sort () {
if (size < 2) {
@@ -278,7 +278,7 @@ internal class Vala.TimSort<G> : Object {
#endif
Slice<G> a = (owned) pending[index];
Slice<G> b = (owned) pending[index + 1];
-
+
assert (a.length > 0);
assert (b.length > 0);
assert (a.index + a.length == b.index);
@@ -648,7 +648,7 @@ internal class Vala.TimSort<G> : Object {
this.index = index;
this.length = length;
}
-
+
~Slice () {
if (new_list != null)
free (new_list);
diff --git a/gee/traversable.vala b/gee/traversable.vala
index 5589622..f046d68 100644
--- a/gee/traversable.vala
+++ b/gee/traversable.vala
@@ -47,7 +47,6 @@ namespace Vala {
* var x = iterable.iterator ().function(args);
* }}}
*
- * @since 0.7.0
*/
[GenericAccessors]
public interface Vala.Traversable<G> : Object {
@@ -59,9 +58,12 @@ public interface Vala.Traversable<G> : Object {
* to last element in iteration or the first element that returned ''false''.
* If iterator points at some element it will be included in iteration.
*
+ * @param f function applied to every element of the collection
+ *
* @return ''false'' if the argument returned ''false'' at last invocation and
* ''true'' otherwise.
*/
+ [CCode (ordering = 0)]
public new abstract bool foreach (ForallFunc<G> f);
/**
@@ -84,13 +86,17 @@ public interface Vala.Traversable<G> : Object {
* 1. {@link Stream.CONTINUE}. It means that the function needs to be
* called with next element or with {@link Stream.END} if it is
* end of stream). If the state element was Stream.END during the
- * current iteration function ''must not'' return {@link Stream.CONTINUE}
- * 1. Stream.END. It means that the last argument was yielded.
+ * current iteration function ''must not'' return {@link Stream.CONTINUE}.
+ * 1. {@link Stream.WAIT}. Simply denotes that iterator should skip an element.
+ * Usually the function is called once again with {@link Stream.WAIT} as
+ * state however it do affect the initial validity of iterator.
+ * 1. {@link Stream.END}. It means that the last argument was yielded.
*
* If the function yields the value immediately then the returning iterator
* is {@link Iterator.valid} and points to this value as well as in case when the
* parent iterator is {@link Iterator.valid} and function yields
- * after consuming 1 input. In other case returned iterator is invalid.
+ * after consuming 1 input. In other case returned iterator is invalid including
+ * when the first value returned is {@link Stream.WAIT}.
*
* Note: In {@link Iterator} implementation: if iterator is
* {@link Iterator.valid} the current value should be fed
@@ -102,64 +108,13 @@ public interface Vala.Traversable<G> : Object {
* @param f function generating stream
* @return iterator containing values yielded by stream
*/
+ [CCode (ordering = 1)]
public virtual Iterator<A> stream<A> (owned StreamFunc<G, A> f) {
- Iterator<G>? self;
- Iterable<G>? iself;
+ unowned Iterator<G>? self;
+ unowned Iterable<G>? iself;
// Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
if ((self = this as Iterator<G>) != null) {
- Traversable.Stream str;
- Lazy<A>? initial = null;
- bool need_next = true;
- str = f (Stream.YIELD, null, out initial);
- switch (str) {
- case Stream.CONTINUE:
- if (self.valid) {
- str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}),
out initial);
- switch (str) {
- case Stream.YIELD:
- case Stream.CONTINUE:
- break;
- case Stream.END:
- return Iterator.unfold<A> (() => {return null;});
- default:
- assert_not_reached ();
- }
- }
- break;
- case Stream.YIELD:
- if (self.valid)
- need_next = false;
- break;
- case Stream.END:
- return Iterator.unfold<A> (() => {return null;});
- default:
- assert_not_reached ();
- }
- return Iterator.unfold<A> (() => {
- Lazy<A>? val = null;
- if (str != Stream.CONTINUE)
- str = f (Traversable.Stream.YIELD, null, out val);
- while (str == Stream.CONTINUE) {
- if (need_next) {
- if (!self.next ()) {
- str = f (Traversable.Stream.END, null, out val);
- assert (str != Traversable.Stream.CONTINUE);
- break;
- }
- } else {
- need_next = true;
- }
- str = f (Stream.CONTINUE, new Lazy<G> (() => {return self.get ();}),
out val);
- }
- switch (str) {
- case Stream.YIELD:
- return val;
- case Stream.END:
- return null;
- default:
- assert_not_reached ();
- }
- }, initial);
+ return new StreamIterator<A, G> (self, (owned)f);
} else if ((iself = this as Iterable<G>) != null) {
return iself.iterator().stream<A> ((owned) f);
} else {
@@ -181,6 +136,7 @@ public interface Vala.Traversable<G> : Object {
* as well.
*
*/
+ [CCode (ordering = 2)]
public virtual A fold<A> (FoldFunc<A, G> f, owned A seed)
{
this.foreach ((item) => {seed = f ((owned) item, (owned) seed); return true; });
@@ -205,6 +161,7 @@ public interface Vala.Traversable<G> : Object {
* @param f Mapping function
* @return Iterator listing mapped value
*/
+ [CCode (ordering = 3)]
public virtual Iterator<A> map<A> (MapFunc<A, G> f) {
return stream<A>((state, item, out val) => {
switch (state) {
@@ -245,6 +202,7 @@ public interface Vala.Traversable<G> : Object {
* @param seed original seed value
* @return Iterator containing values of subsequent values of seed
*/
+ [CCode (ordering = 4)]
public virtual Iterator<A> scan<A> (FoldFunc<A, G> f, owned A seed) {
bool seed_emitted = false;
return stream<A>((state, item, out val) => {
@@ -286,9 +244,10 @@ public interface Vala.Traversable<G> : Object {
* iterator is {@link Iterator.valid} and value it is pointing on
* fullfills the predicate.
*
- * @param f Folding function
+ * @param pred predicate to check should the value be retained
* @return Iterator containing values of subsequent values of seed
*/
+ [CCode (ordering = 5)]
public virtual Iterator<G> filter (owned Predicate<G> pred) {
return stream<G> ((state, item, out val) => {
switch (state) {
@@ -329,6 +288,7 @@ public interface Vala.Traversable<G> : Object {
* @param length maximum number of elements iterator may return. Negative
* value means that the number is unbounded
*/
+ [CCode (ordering = 6)]
public virtual Iterator<G> chop (int offset, int length = -1) {
assert (offset >= 0);
return stream<G> ((state, item, out val) => {
@@ -363,17 +323,136 @@ public interface Vala.Traversable<G> : Object {
});
}
-
/**
* The type of the elements in this collection.
*/
+ [CCode (ordering = 7)]
public virtual Type element_type { get { return typeof (G); } }
+ /**
+ * A fused concatinate and map. The function is applied to each element
+ * of iteration and the resulting values are concatinated.
+ *
+ * The iterator is lazy evaluated but value is force-evaluated when
+ * iterator is moved to next value.
+ *
+ * Note: Default implementation uses {@link stream}.
+ *
+ * Note: In {@link Iterator} implementation if the parent iterator is
+ * {@link Iterator.valid} and function returns a valid iterator the
+ * resulting iterator is also valid. Using the parent iterator is not
+ * allowed before the inner iterator {@link Iterator.next}
+ * return false and then it points on its last element.
+ *
+ * @param f mapping function
+ * @return Iterator over returned values
+ */
+ [CCode (ordering = 8)]
+ public virtual Iterator<A> flat_map<A>(owned FlatMapFunc<A, G> f) {
+ Iterator<A>? current = null;
+ return stream<A> ((state, item, out val) => {
+ switch (state) {
+ case Stream.YIELD:
+ if (current == null || !current.next ()) {
+ val = null;
+ return Stream.CONTINUE;
+ } else {
+ val = new Lazy<A> (() => {return current.get ();});
+ return Stream.YIELD;
+ }
+ case Stream.CONTINUE:
+ current = f (item.get ());
+ if (current.valid) {
+ val = new Lazy<A> (() => {return current.get ();});
+ return Stream.YIELD;
+ } else {
+ val = null;
+ return Stream.WAIT;
+ }
+ case Stream.WAIT:
+ if (current.next()) {
+ val = new Lazy<A> (() => {return current.get ();});
+ return Stream.YIELD;
+ } else {
+ val = null;
+ return Stream.CONTINUE;
+ }
+ case Stream.END:
+ val = null;
+ return Stream.END;
+ default:
+ assert_not_reached ();
+ }
+ });
+ }
+
+ /**
+ * Splits the traversable into multiple ones, caching the result if needed.
+ *
+ * Note: In {@link Iterator} implementation using the parent iterator is
+ * not allowed. However if any of the forked iterators {@link next}
+ * return false then it is treated as if the parent iterator
+ * {@link next} returned false.
+ *
+ * Note: The returned arrey might contain parent iterator if it is allowed
+ * by implementation. For example the iteration over collection does
+ * not need to generate and cache the results.
+ * In such case it is recommended to return the value as the first element
+ * of the array. This allows the consumer to check just the first element
+ * if it can perform optimizations for such case. However it //must// not
+ * depend on the order (that's for optimization only).
+ *
+ * Note: The resulting iterators does not need to be thread safe.
+ *
+ * @param forks Number of iterators in array
+ * @return An array with created iterators
+ */
+ [CCode (ordering = 9)]
+ public virtual Iterator<G>[] tee (uint forks) {
+ unowned Iterator<G>? self;
+ unowned Iterable<G>? iself;
+ // Yes - I've heard of polimorphism ;) but I don't want users to need to implement the method.
+ if ((self = this as Iterator<G>) != null) {
+ if (forks == 0) {
+ return new Iterator<G>[0];
+ } else if (forks == 1) {
+ return new Iterator<G>[1]{self};
+ } else {
+ Iterator<G>[] result = new Iterator<G>[forks];
+ Lazy<G>? data;
+ bool is_valid = self.valid;
+ if (is_valid) {
+ data = new Lazy<G>(() => {return self.get ();});
+ } else {
+ data = new Lazy<G>.from_value (null);
+ }
+ var head = new TeeIterator.Node<G> (data, TeeIterator.create_nodes<G> (self,
data));
+ for (uint i = 0; i < forks; i++) {
+ result[i] = new TeeIterator<G> (head, is_valid);
+ }
+ return result;
+ }
+ } else if ((iself = this as Iterable<G>) != null) {
+ var result = new Iterator<G>[forks];
+ for (uint i = 0; i < forks; i++) {
+ result[i] = iself.iterator ();
+ }
+ return result;
+ } else {
+ assert_not_reached ();
+ }
+ }
+
public enum Stream {
YIELD,
CONTINUE,
- END
+ END,
+ WAIT
}
+}
+namespace Vala {
+ // Placed here to workaround bug #703710
+ public delegate Iterator<A> FlatMapFunc<A, G>(owned G g);
}
diff --git a/gee/treemap.vala b/gee/treemap.vala
index bba4809..7d32de8 100644
--- a/gee/treemap.vala
+++ b/gee/treemap.vala
@@ -1,6 +1,6 @@
/* treemap.vala
*
- * Copyright (C) 2009-2011 Maciej Piechotka
+ * Copyright (C) 2009-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -38,7 +38,7 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
public override int size {
get { return _size; }
}
-
+
public override bool read_only {
get { return false; }
}
@@ -92,19 +92,31 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
* The keys' comparator function.
*/
[CCode (notify = false)]
- public CompareDataFunc<K> key_compare_func { private set; get; }
+ public CompareDataFunc<K> key_compare_func {
+ private set {}
+ get {
+ return _key_compare_func.func;
+ }
+ }
/**
* The values' equality testing function.
*/
[CCode (notify = false)]
- public EqualDataFunc<V> value_equal_func { private set; get; }
+ public EqualDataFunc<V> value_equal_func {
+ private set {}
+ get {
+ return _value_equal_func.func;
+ }
+ }
private int _size = 0;
private weak SortedSet<K> _keys;
private weak Collection<V> _values;
private weak SortedSet<Map.Entry<K,V>> _entries;
+ private Functions.CompareDataFuncClosure<K> _key_compare_func;
+ private Functions.EqualDataFuncClosure<V> _value_equal_func;
/**
* Constructs a new, empty tree map sorted according to the specified
@@ -123,8 +135,13 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
if (value_equal_func == null) {
value_equal_func = Functions.get_equal_func_for (typeof (V));
}
- this.key_compare_func = key_compare_func;
- this.value_equal_func = value_equal_func;
+ _key_compare_func = new Functions.CompareDataFuncClosure<K> ((owned)key_compare_func);
+ _value_equal_func = new Functions.EqualDataFuncClosure<V> ((owned)value_equal_func);
+ }
+
+ internal TreeMap.with_closures (owned Functions.CompareDataFuncClosure<K> key_compare_func, owned
Functions.EqualDataFuncClosure<V> value_equal_func) {
+ _key_compare_func = key_compare_func;
+ _value_equal_func = value_equal_func;
}
~TreeMap () {
@@ -442,14 +459,14 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
return entries;
}
}
-
+
/**
* {@inheritDoc}
*/
public override Vala.MapIterator<K,V> map_iterator () {
return new MapIterator<K,V> (this);
}
-
+
/**
* {@inheritDoc}
*/
@@ -457,6 +474,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
return new MapIterator<K,V> (this);
}
+ internal Functions.CompareDataFuncClosure<K> get_key_compare_func_closure () {
+ return _key_compare_func;
+ }
+
[Compact]
private class Node<K, V> {
public enum Color {
@@ -486,6 +507,12 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
}
+ ~Node () {
+ if (entry != null) {
+ entry.remove_weak_pointer ((void**) (&entry));
+ }
+ }
+
public void flip () {
color = color.flip ();
if (left != null) {
@@ -788,8 +815,8 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
}
- private weak SortedSet<Entry<K,V>>? _entries;
- public override Set<Entry<K,V>> entries {
+ private weak SortedSet<Map.Entry<K,V>>? _entries;
+ public override Set<Map.Entry<K,V>> entries {
owned get {
var entries = _entries;
if (_entries == null) {
@@ -833,11 +860,11 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
for (var iterator = map_iterator (); iterator.next ();)
iterator.unset ();
}
-
+
public override Vala.MapIterator<K,V> map_iterator () {
return new SubMapIterator<K,V> (map, range);
}
-
+
public override BidirMapIterator<K,V> bidir_map_iterator () {
return new SubMapIterator<K,V> (map, range);
}
@@ -866,7 +893,7 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
}
- public override SortedSet<K> ascending_entries {
+ public override SortedSet<Map.Entry<K, V>> ascending_entries {
owned get {
var entries = _entries;
if (_entries == null) {
@@ -1241,7 +1268,7 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
return new SubEntrySet<K,V> (_map, new Range<K,V>.tail (_map, after.key));
}
- public override SortedSet<K> sub_set (Map.Entry<K, V> after, Map.Entry<K, V> before) {
+ public override SortedSet<Map.Entry<K, V>> sub_set (Map.Entry<K, V> after, Map.Entry<K, V>
before) {
return new SubEntrySet<K,V> (_map, new Range<K,V> (_map, after.key, before.key));
}
@@ -1322,7 +1349,7 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
return range.in_range(entry.key) && map.has (entry.key, entry.value);
}
- public override BidirIterator<K> bidir_iterator () {
+ public override BidirIterator<Map.Entry<K, V>> bidir_iterator () {
return new SubEntryIterator<K,V> (map, range);
}
@@ -1338,15 +1365,15 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
return Entry.entry_for<K,V> (_last);
}
- public override SortedSet<K> head_set (Map.Entry<K,V> before) {
+ public override SortedSet<Map.Entry<K, V>> head_set (Map.Entry<K,V> before) {
return new SubEntrySet<K,V> (map, range.cut_tail (before.key));
}
- public override SortedSet<K> tail_set (Map.Entry<K,V> after) {
+ public override SortedSet<Map.Entry<K, V>> tail_set (Map.Entry<K,V> after) {
return new SubEntrySet<K,V> (map, range.cut_head (after.key));
}
- public override SortedSet<K> sub_set (Map.Entry<K,V> after, Map.Entry<K,V> before) {
+ public override SortedSet<Map.Entry<K, V>> sub_set (Map.Entry<K,V> after, Map.Entry<K,V>
before) {
return new SubEntrySet<K,V> (map, range.cut (after.key, before.key));
}
@@ -1415,6 +1442,15 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
this.current = current;
}
+ public NodeIterator.from_iterator (NodeIterator<K, V> iter) {
+ _map = iter._map;
+ stamp = iter.stamp;
+ started = iter.started;
+ current = iter.current;
+ _next = iter._next;
+ _prev = iter._prev;
+ }
+
public bool next () {
assert (stamp == _map.stamp);
if (current != null) {
@@ -1539,6 +1575,12 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
this.iterator = new NodeIterator<K,V>.pointing (_map, node);
}
+ public SubNodeIterator.from_iterator (SubNodeIterator<K,V> iter) {
+ _map = iter._map;
+ range = iter.range;
+ iterator = new NodeIterator<K,V>.from_iterator (iter.iterator);
+ }
+
public bool next () {
if (iterator != null) {
weak Node<K,V>? node= iterator.safe_next_get ();
@@ -1637,6 +1679,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, current);
}
+ public KeyIterator.from_iterator (KeyIterator<K, V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new K get () {
assert (stamp == _map.stamp);
assert (current != null);
@@ -1666,6 +1712,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<K>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<K>[0];
+ } else {
+ Vala.Iterator<K>[] result = new Vala.Iterator<K>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new KeyIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class SubKeyIterator<K,V> : SubNodeIterator<K,V>, Traversable<K>, Vala.Iterator<K>,
BidirIterator<K> {
@@ -1677,6 +1736,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, range, node);
}
+ public SubKeyIterator.from_iterator (SubKeyIterator<K, V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new K get () {
assert (valid);
return iterator.current.key;
@@ -1695,6 +1758,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<K>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<K>[0];
+ } else {
+ Vala.Iterator<K>[] result = new Vala.Iterator<K>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new SubKeyIterator<K,V>.from_iterator(this);
+ }
+ return result;
+ }
+ }
}
private class ValueIterator<K,V> : NodeIterator<K,V>, Traversable<V>, Vala.Iterator<V>,
Vala.BidirIterator<V> {
@@ -1706,6 +1782,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, current);
}
+ public ValueIterator.from_iterator (ValueIterator<K,V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new V get () {
assert (stamp == _map.stamp);
assert (valid);
@@ -1735,6 +1815,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<V>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<V>[0];
+ } else {
+ Vala.Iterator<V>[] result = new Vala.Iterator<V>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new ValueIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class SubValueIterator<K,V> : SubNodeIterator<K,V>, Traversable<V>, Vala.Iterator<V>,
BidirIterator<V> {
@@ -1746,6 +1839,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, range, node);
}
+ public SubValueIterator.from_iterator (SubValueIterator<K,V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new V get () {
assert (valid);
return iterator.current.value;
@@ -1764,6 +1861,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<V>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<V>[0];
+ } else {
+ Vala.Iterator<V>[] result = new Vala.Iterator<V>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new SubValueIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class EntryIterator<K,V> : NodeIterator<K,V>, Traversable<Map.Entry<K, V>>,
Vala.Iterator<Map.Entry<K,V>>, Vala.BidirIterator<Map.Entry<K,V>> {
@@ -1775,6 +1885,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, node);
}
+ public EntryIterator.from_iterator (EntryIterator<K,V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new Map.Entry<K,V> get () {
assert (stamp == _map.stamp);
assert (valid);
@@ -1808,6 +1922,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<Map.Entry<K,V>>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<Map.Entry<K,V>>[0];
+ } else {
+ Vala.Iterator<Map.Entry<K,V>>[] result = new
Vala.Iterator<Map.Entry<K,V>>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new EntryIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class SubEntryIterator<K,V> : SubNodeIterator<K,V>, Traversable<Map.Entry<K, V>>,
Vala.Iterator<Map.Entry<K,V>>, Vala.BidirIterator<Map.Entry<K,V>> {
@@ -1819,6 +1946,10 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
base.pointing (map, range, node);
}
+ public SubEntryIterator.from_iterator (SubEntryIterator<K,V> iterator) {
+ base.from_iterator (iterator);
+ }
+
public new Map.Entry<K,V> get () {
assert (iterator != null);
return Entry.entry_for<K,V> (iterator.current);
@@ -1841,6 +1972,19 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
}
return true;
}
+
+ public Vala.Iterator<Map.Entry<K,V>>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Iterator<Map.Entry<K,V>>[0];
+ } else {
+ Vala.Iterator<Map.Entry<K,V>>[] result = new
Vala.Iterator<Map.Entry<K,V>>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new SubEntryIterator<K,V>.from_iterator (this);
+ }
+ return result;
+ }
+ }
}
private class MapIterator<K,V> : NodeIterator<K,V>, Vala.MapIterator<K,V>, BidirMapIterator<K,V> {
@@ -1865,13 +2009,13 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
assert (valid);
current.value = value;
}
-
+
public override bool read_only {
get {
return false;
}
}
-
+
public bool mutable {
get {
return true;
@@ -1898,13 +2042,13 @@ public class Vala.TreeMap<K,V> : Vala.AbstractBidirSortedMap<K,V> {
assert (valid);
iterator.current.value = value;
}
-
+
public override bool read_only {
get {
return false;
}
}
-
+
public bool mutable {
get {
return true;
diff --git a/gee/treemultimap.vala b/gee/treemultimap.vala
index 452dd97..97d2915 100644
--- a/gee/treemultimap.vala
+++ b/gee/treemultimap.vala
@@ -30,7 +30,12 @@ public class Vala.TreeMultiMap<K,V> : AbstractMultiMap<K,V> {
}
[CCode (notify = false)]
- public CompareDataFunc<V> value_compare_func { private set; get; }
+ public CompareDataFunc<V> value_compare_func {
+ private set {}
+ get {
+ return _value_compare_func.func;
+ }
+ }
/**
* Constructs a new, empty tree multimap.
@@ -42,22 +47,24 @@ public class Vala.TreeMultiMap<K,V> : AbstractMultiMap<K,V> {
* @param value_compare_func an optional value comparator function
*/
public TreeMultiMap (owned CompareDataFunc<K>? key_compare_func = null, owned CompareDataFunc<V>?
value_compare_func = null) {
- base (new TreeMap<K, Set<V>> (key_compare_func, Functions.get_equal_func_for (typeof (Set))));
+ base (new TreeMap<K, Set<V>> ((owned)key_compare_func, Functions.get_equal_func_for (typeof
(Set))));
if (value_compare_func == null) {
value_compare_func = Functions.get_compare_func_for (typeof (V));
}
- this.value_compare_func = value_compare_func;
+ _value_compare_func = new Functions.CompareDataFuncClosure<V> ((owned)value_compare_func);
}
protected override Collection<V> create_value_storage () {
- return new TreeSet<V> (_value_compare_func);
+ return new TreeSet<V>.with_closures (_value_compare_func);
}
protected override MultiSet<K> create_multi_key_set () {
- return new TreeMultiSet<K> (key_compare_func);
+ return new TreeMultiSet<K>.with_closures (((TreeMap<K, Set<V>>)
_storage_map).get_key_compare_func_closure ());
}
protected override EqualDataFunc<V> get_value_equal_func () {
return Functions.get_equal_func_for (typeof (V));
}
+
+ private Functions.CompareDataFuncClosure<V> _value_compare_func;
}
diff --git a/gee/treemultiset.vala b/gee/treemultiset.vala
index 992d96d..00cb640 100644
--- a/gee/treemultiset.vala
+++ b/gee/treemultiset.vala
@@ -38,6 +38,10 @@ public class Vala.TreeMultiSet<G> : AbstractMultiSet<G> {
* @param compare_func an optional element comparator function
*/
public TreeMultiSet (owned CompareDataFunc<G>? compare_func = null) {
- base (new TreeMap<G, int> (compare_func));
+ base (new TreeMap<G, int> ((owned)compare_func));
+ }
+
+ internal TreeMultiSet.with_closures (owned Functions.CompareDataFuncClosure<G> compare_func) {
+ base (new TreeMap<G, int>.with_closures ((owned)compare_func, new
Functions.EqualDataFuncClosure<int> (Functions.get_equal_func_for (typeof (int)))));
}
}
diff --git a/gee/treeset.vala b/gee/treeset.vala
index 0ea02aa..084c0e5 100644
--- a/gee/treeset.vala
+++ b/gee/treeset.vala
@@ -1,6 +1,6 @@
/* treeset.vala
*
- * Copyright (C) 2009-2011 Maciej Piechotka
+ * Copyright (C) 2009-2014 Maciej Piechotka
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -39,7 +39,7 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
public override int size {
get {return _size;}
}
-
+
/**
* {@inheritDoc}
*/
@@ -51,7 +51,12 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
* The elements' comparator function.
*/
[CCode (notify = false)]
- public CompareDataFunc<G> compare_func { private set; get; }
+ public CompareDataFunc<G> compare_func {
+ private set {}
+ get {
+ return _compare_func.func;
+ }
+ }
private int _size = 0;
@@ -68,7 +73,11 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
if (compare_func == null) {
compare_func = Functions.get_compare_func_for (typeof (G));
}
- this.compare_func = compare_func;
+ _compare_func = new Functions.CompareDataFuncClosure<G> ((owned)compare_func);
+ }
+
+ internal TreeSet.with_closures (owned Functions.CompareDataFuncClosure<G> compare_func) {
+ _compare_func = (owned)compare_func;
}
~TreeSet () {
@@ -345,6 +354,18 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
/**
* {@inheritDoc}
*/
+ public override bool foreach (ForallFunc<G> f) {
+ for (unowned Node<G> node = _first; node != null; node = node.next) {
+ if (!f (node.key)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
public override Vala.Iterator<G> iterator () {
return new Iterator<G> (this);
}
@@ -578,11 +599,6 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
}
private class Iterator<G> : Object, Traversable<G>, Vala.Iterator<G>, BidirIterator<G> {
- private TreeSet<G> _set;
-
- // concurrent modification protection
- private int stamp;
-
public Iterator (TreeSet<G> set) {
_set = set;
stamp = _set.stamp;
@@ -595,6 +611,15 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
this.started = true;
}
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _set = iter._set;
+ stamp = iter.stamp;
+ _current = iter._current;
+ _next = iter._next;
+ _prev = iter._prev;
+ started = iter.started;
+ }
+
public bool next () {
assert (stamp == _set.stamp);
if (_current != null) {
@@ -752,10 +777,25 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
return true;
}
- private weak Node<G>? _current = null;
- private weak Node<G>? _next = null;
- private weak Node<G>? _prev = null;
- private bool started = false;
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected TreeSet<G> _set;
+ protected int stamp;
+ protected weak Node<G>? _current = null;
+ protected weak Node<G>? _next = null;
+ protected weak Node<G>? _prev = null;
+ protected bool started = false;
}
private inline G min (G a, G b) {
@@ -1040,8 +1080,8 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
return h != null && range.in_range (h) ? h : null;
}
- private new TreeSet<G> set;
- private Range<G> range;
+ protected new TreeSet<G> set;
+ protected Range<G> range;
}
private class SubIterator<G> : Object, Traversable<G>, Vala.Iterator<G>, BidirIterator<G> {
@@ -1056,6 +1096,12 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
this.iterator = new Iterator<G>.pointing (set, node);
}
+ public SubIterator.from_iterator (SubIterator<G> iter) {
+ set = iter.set;
+ range = iter.range;
+ iterator = new Iterator<G>.from_iterator (iter.iterator);
+ }
+
public bool next () {
if (iterator != null) {
G next;
@@ -1150,13 +1196,27 @@ public class Vala.TreeSet<G> : AbstractBidirSortedSet<G> {
return true;
}
- private new TreeSet<G> set;
- private Range<G> range;
- private Iterator<G>? iterator = null;
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new SubIterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ protected new TreeSet<G> set;
+ protected Range<G> range;
+ protected Iterator<G>? iterator = null;
}
private Node<G>? root = null;
private weak Node<G>? _first = null;
private weak Node<G>? _last = null;
private int stamp = 0;
+ private Functions.CompareDataFuncClosure<G> _compare_func;
}
diff --git a/gee/unrolledlinkedlist.vala b/gee/unrolledlinkedlist.vala
new file mode 100644
index 0000000..a316207
--- /dev/null
+++ b/gee/unrolledlinkedlist.vala
@@ -0,0 +1,1152 @@
+/* unrolledlinkedlist.vala
+ *
+ * Copyright (C) 2013-2014 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+
+using Vala.Utils.Assume;
+
+/**
+ * Unrolled doubly-linked list implementation of the {@link List} interface.
+ *
+ * The unrolled doubly-linked list combines the advantages and disadvantages
+ * of the {@link ArrayList} and {@link LinkedList} and is usually suitable when
+ * modifications and read operations are balanced.
+ *
+ * Please note that in our benchmarks the speed of most operations (insertion,
+ * deletion, sequential read) was on par or better then {@link ArrayList} and
+ * {@link LinkedList} except the prepending operation.
+ *
+ * @see ArrayList
+ * @see LinkedList
+ */
+public class Vala.UnrolledLinkedList<G> : AbstractBidirList<G>, Queue<G>, Deque<G> {
+ /**
+ * The elements' equality testing function.
+ */
+ [CCode (notify = false)]
+ public EqualDataFunc<G> equal_func {
+ private set {}
+ get {
+ return _equal_func.func;
+ }
+ }
+
+ /**
+ * Constructs a new, empty linked list.
+ *
+ * If not provided, the function parameter is requested to the
+ * {@link Functions} function factory methods.
+ *
+ * @param equal_func an optional element equality testing function
+ */
+ public UnrolledLinkedList (owned EqualDataFunc<G>? equal_func = null) {
+ if (equal_func == null) {
+ equal_func = Functions.get_equal_func_for (typeof (G));
+ }
+ _equal_func = new Functions.EqualDataFuncClosure<G> ((owned)equal_func);
+ }
+
+ private UnrolledLinkedList.with_closures (owned Functions.EqualDataFuncClosure<G> equal_func) {
+ _equal_func = equal_func;
+ }
+
+ ~UnrolledLinkedList () {
+ this.clear ();
+ }
+
+ public override bool foreach (ForallFunc<G> f) {
+#if DUMP
+ stdout.printf ("FOREACH BEGIN %p\n", this);
+ dump ();
+ try {
+#endif
+ for (unowned Node<G>? node = _head; node != null; node = node._next) {
+ for (int pos = 0; pos < node._size; pos++) {
+ if (! f(node._data[pos])) {
+ return false;
+ }
+ }
+ }
+ return true;
+#if DUMP
+ } finally {
+ dump();
+ stdout.printf ("FOREACH END\n");
+ }
+#endif
+ }
+
+ public override int size { get {return _size;} }
+ public override bool read_only { get {return false;} }
+
+ public override Vala.Iterator<G> iterator () {
+ return new Iterator<G> (this);
+ }
+
+ public override bool contains (G item) {
+ return find_node (item) != null;
+ }
+
+ public override bool add (G item) {
+#if DUMP
+ stdout.printf ("ADD BEGIN %p (%s)\n", item, (string)item);
+ dump ();
+#endif
+ if (_tail == null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_head == null);
+#else
+ assume (_head == null);
+#endif
+ _tail = _head = new Node<G>();
+ }
+ add_to_node (_tail, item, _tail._size);
+#if DUMP
+ dump ();
+ stdout.printf ("ADD END\n");
+#endif
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return true;
+ }
+ public override bool remove (G item) {
+ int pos;
+ unowned Node<G>? node = find_node (item, out pos);
+ if (node != null) {
+ remove_from_node (node, pos);
+ }
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return node != null;
+ }
+
+ public override void clear () {
+ for (Node<G>? node = (owned)_head; node != null; node = (owned)node._next) {
+ for (uint pos = 0; pos < node._size; pos++) {
+ node._data[pos] = null;
+ }
+ }
+ _head = null;
+ _tail = null;
+ _stamp++;
+ _size = 0;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ }
+
+ public override ListIterator<G> list_iterator () {
+ return new Iterator<G> (this);
+ }
+
+ public override G? get (int index) {
+ assert (index >= 0);
+ assert (index < this._size);
+
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+
+ int pos;
+ unowned Node<G>? node = find_node_by_idx (index, out pos);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node != null);
+#endif
+ return node._data[pos];
+ }
+
+ public override void set (int index, G item) {
+ assert (index >= 0);
+ assert (index < this._size);
+
+ int pos;
+ unowned Node<G>? node = find_node_by_idx (index, out pos);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node != null);
+#endif
+ node._data[pos] = item;
+ }
+
+ public override int index_of (G item) {
+ int idx;
+ if (find_node (item, null, out idx) != null) {
+ return idx;
+ } else {
+ return -1;
+ }
+ }
+
+ public override void insert (int index, G item) {
+#if DUMP
+ stdout.printf ("INSERT BEGIN %p (%s)\n", item, (string)item);
+ dump ();
+#endif
+ assert (index >= 0);
+ assert (index <= this._size);
+
+ if (index != this._size) {
+ int pos;
+ unowned Node<G>? node = find_node_by_idx (index, out pos);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node != null);
+#endif
+ add_to_node (node, item, pos);
+ } else {
+ if (index == 0) {
+
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_head == null && _tail == null);
+#else
+ assume (_head == null && _tail == null);
+#endif
+ _tail = _head = new Node<G>();
+ }
+ add_to_node (_tail, item, _tail._size);
+ }
+#if DUMP
+ dump ();
+ stdout.printf ("INSERT END\n");
+#endif
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ }
+
+ public override G remove_at (int index) {
+ assert (index >= 0);
+ assert (index < this._size);
+
+ int pos;
+ unowned Node<G>? node = find_node_by_idx (index, out pos);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node != null);
+#endif
+ return remove_from_node (node, pos);
+ }
+
+ public override List<G>? slice (int start, int stop) {
+ assert (0 <= start && start <= stop && stop <= _size);
+
+ UnrolledLinkedList<G> slice = new UnrolledLinkedList<G>.with_closures (_equal_func);
+ slice._size = stop - start;
+ unowned Node<G>? copy = slice._head = new Node<G> ();
+
+ int orig_pos;
+ unowned Node<G>? orig = find_node_by_idx (start, out orig_pos);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (orig != null);
+#endif
+
+ int i = 0;
+ while (true) {
+ int j = 0;
+ while (j < NODE_SIZE && i < stop - start) {
+ copy._data[j] = orig._data[orig_pos];
+ i++;
+ j++;
+ orig_pos++;
+ if (unlikely (orig_pos == orig._size)) {
+ orig = orig._next;
+ orig_pos = 0;
+ }
+
+ }
+ copy._size = j;
+ if (unlikely (!(i < stop - start))) {
+ break;
+ }
+ copy._next = new Node<G> ();
+ copy._next._prev = copy;
+ copy = copy._next;
+ }
+ slice._tail = copy;
+#if CONSISTENCY_CHECKS
+ slice.check ();
+#endif
+ return slice;
+ }
+
+ public override BidirListIterator<G> bidir_list_iterator () {
+ return new Iterator<G> (this);
+ }
+
+ public int capacity { get { return Queue.UNBOUNDED_CAPACITY; } }
+
+ public int remaining_capacity { get { return Queue.UNBOUNDED_CAPACITY; } }
+
+ public bool is_full { get { return false; } }
+
+ public bool offer (G element) {
+ if (_tail == null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_head == null);
+#else
+ assume (_head == null);
+#endif
+ _tail = _head = new Node<G>();
+ }
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_head != null && _tail != null);
+#else
+ assume (_head != null && _tail != null);
+#endif
+ add_to_node (_tail, element, _tail._size);
+ return true;
+ }
+
+ public G? peek () {
+ if (_head != null) {
+ return _head._data[0];
+ } else {
+ return null;
+ }
+ }
+
+ public G? poll () {
+ if (_head != null) {
+ return remove_from_node (_head, 0);
+ } else {
+ return null;
+ }
+ }
+
+ public int drain (Collection<G> recipient, int amount = -1) {
+ int drained = 0;
+ if (amount < 0) {
+ for (Node<G>? node = (owned)_head; node != null; node = (owned)node._next) {
+ for (int i = 0; i < node._size; i++) {
+ G data = (owned)node._data[i];
+ recipient.add (data);
+ }
+ }
+ drained = _size;
+ _tail = null;
+ _size = 0;
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ } else {
+ Node<G>? node;
+ for (node = (owned)_head; node != null; node = (owned)node._next) {
+ if (likely (node._size <= amount)) {
+ for (int i = 0; i < node._size; i++) {
+ G data = (owned)node._data[i];
+ recipient.add (data);
+ }
+ amount -= node._size;
+ drained += node._size;
+ _size -= node._size;
+ } else {
+ for (int i = 0; i < amount; i++) {
+ G data = (owned)node._data[i];
+ recipient.add (data);
+ }
+ Memory.move(node._data, &node._data[amount], sizeof(G) * (node._size
- amount));
+ drained += amount;
+ _size -= amount;
+ node._size -= amount;
+ unowned Node<G>? n = node;
+ _head = (owned)node;
+ if (likely (n._next != null) && unlikely (n._size + n._next._size <
MERGE_THRESHOLD)) {
+ merge_with_next (node);
+ }
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ }
+ }
+ _tail = null;
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ }
+ }
+
+ public bool offer_head (G element) {
+ if (_head == null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_tail == null);
+#else
+ assume (_tail == null);
+#endif
+ _tail = _head = new Node<G>();
+ }
+ add_to_node (_head, element, 0);
+ return true;
+ }
+
+ public G? peek_head () {
+ return peek ();
+ }
+
+ public G? poll_head () {
+ return poll ();
+ }
+
+ public int drain_head (Collection<G> recipient, int amount = -1) {
+ return drain (recipient, amount);
+ }
+
+ public bool offer_tail (G element) {
+ return offer (element);
+ }
+
+ public G? peek_tail () {
+ if (_tail != null) {
+ return _tail._data[_tail._size - 1];
+ } else {
+ return null;
+ }
+ }
+
+ public G? poll_tail () {
+ if (_head != null) {
+ return remove_from_node (_tail, _tail._size - 1);
+ } else {
+ return null;
+ }
+ }
+
+ public int drain_tail (Collection<G> recipient, int amount = -1) {
+ int drained = 0;
+ if (amount < 0) {
+ for (unowned Node<G>? node = _tail; node != null; node = node._prev) {
+ for (int i = node._size; i-- > 0;) {
+ G data = (owned)node._data[i];
+ recipient.add (data);
+ }
+ node._next = null;
+ }
+ drained = _size;
+ _head = null;
+ _tail = null;
+ _size = 0;
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ } else {
+ for (unowned Node<G>? node = _tail; node != null;) {
+ if (node._size <= amount) {
+ for (int i = node._size; i-- > 0;) {
+ G data = (owned)node._data[i];
+ recipient.add (data);
+ }
+ amount -= node._size;
+ drained += node._size;
+ _size -= node._size;
+ node = node._prev;
+ if (node != null) {
+ node._next = null;
+ }
+ } else {
+ for (int i = 0; i < amount; i++) {
+ G data = (owned)node._data[node._size - i - 1];
+ recipient.add (data);
+ }
+ drained += amount;
+ _size -= amount;
+ node._size -= amount;
+ _tail = node;
+ if (likely (node._prev != null) && unlikely (node._size +
node._prev._size < MERGE_THRESHOLD)) {
+ merge_with_next (node._prev);
+ }
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ }
+ }
+ _head = null;
+ _tail = null;
+ _stamp++;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return drained;
+ }
+ }
+
+ private unowned Node<G>? find_node (G item, out int pos = null, out int idx = null) {
+ idx = 0;
+ for (unowned Node<G>? node = _head; node != null; node = node._next) {
+ for (pos = 0; pos < node._size; pos++, idx++) {
+ if (this.equal_func (item, node._data[pos])) {
+ return node;
+ }
+ }
+ }
+ pos = -1;
+ return null;
+ }
+
+ private unowned Node<G>? find_node_by_idx (int idx, out int? pos = null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= idx && idx < _size);
+#else
+ assume (0 <= idx && idx < _size);
+#endif
+ if (idx <= size/2) {
+ for (unowned Node<G>? node = _head; node != null; node = node._next) {
+ if (idx < node._size) {
+ pos = idx;
+ return node;
+ }
+ idx -= node._size;
+ }
+ }
+ else {
+ int start_of_node = _size;
+ int count = 0;
+ for (unowned Node<G>? node = _tail; node != null; node = node._prev) {
+ start_of_node -= node._size;
+ count += node._size;
+ if (idx >= start_of_node) {
+ pos = idx - start_of_node;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= pos && pos < node._size);
+#else
+ assume (0 <= pos && pos < node._size);
+#endif
+ return node;
+ }
+ }
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (start_of_node == 0);
+#endif
+ }
+#if !DISABLE_INTERNAL_ASSERTS
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ assert_not_reached ();
+#else
+ assume (false);
+ pos = -1;
+ return null;
+#endif
+ }
+
+ private void add_to_node (Node<G> node, G item, int pos, out unowned Node<G>? new_node = null, out
int new_pos = null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= pos && pos <= node._size && node._size <= NODE_SIZE);
+#else
+ assume (0 <= pos && pos <= node._size && node._size <= NODE_SIZE);
+#endif
+ if (node._size == NODE_SIZE) {
+ Node<G> next = new Node<G> ();
+ next._next = (owned)node._next;
+ next._prev = node;
+ if (GLib.unlikely (next._next == null)) {
+ _tail = next;
+ } else {
+ next._next._prev = next;
+ }
+ Memory.copy(next._data, &node._data[SPLIT_POS], sizeof(G) * (NODE_SIZE - SPLIT_POS));
+ node._size = SPLIT_POS;
+ next._size = NODE_SIZE - SPLIT_POS;
+ node._next = (owned)next;
+ if (pos > SPLIT_POS) {
+ node = node._next;
+ pos = pos - SPLIT_POS;
+ }
+ }
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= pos && pos <= node._size && node._size < NODE_SIZE);
+#else
+ assume (0 <= pos && pos <= node._size && node._size < NODE_SIZE);
+#endif
+ Memory.move(&node._data[pos + 1], &node._data[pos], sizeof(G) * (node._size - pos));
+ Memory.set(&node._data[pos], 0, sizeof(G));
+ node._data[pos] = item;
+ node._size++;
+ _size++;
+ _stamp++;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node._size <= NODE_SIZE);
+#else
+ assume (node._size <= NODE_SIZE);
+#endif
+ new_node = node;
+ new_pos = pos;
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ }
+
+ private G remove_from_node (Node<G> node, int pos, out unowned Node<G>? new_node = null, out int
new_pos = null) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert ((0 <= pos && pos <= node._size) && pos <= NODE_SIZE);
+#else
+ assume ((0 <= pos && pos <= node._size) && pos <= NODE_SIZE);
+#endif
+ G item = (owned)node._data[pos];
+ Memory.move(&node._data[pos], &node._data[pos + 1], sizeof(G) * (node._size - (pos + 1)));
+ node._size--;
+ _size--;
+ _stamp++;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node._size >= 0);
+ assert (_size >= 0);
+#else
+ assume (node._size >= 0);
+ assume (_size >= 0);
+#endif
+ if (unlikely (node._size == 0)) {
+ new_node = node._prev;
+ if (likely (node._prev != null)) {
+ new_pos = node._prev._size - 1;
+ } else {
+ new_pos = -1;
+ }
+ delete_node (node);
+ } else if (likely (node._prev != null) && unlikely (node._size + node._prev._size <
MERGE_THRESHOLD)) {
+ new_node = node._prev;
+ new_pos = node._prev._size + pos - 1;
+ merge_with_next (node._prev);
+ } else if (likely (node._next != null) && unlikely (node._size + node._next._size <
MERGE_THRESHOLD)) {
+ merge_with_next (node);
+ new_node = node;
+ new_pos = pos - 1;
+ } else {
+ if (pos != 0) {
+ new_node = node;
+ new_pos = pos - 1;
+ } else {
+ new_node = node._prev;
+ if (likely (node._prev != null)) {
+ new_pos = node._prev._size - 1;
+ } else {
+ new_pos = -1;
+ }
+ }
+ }
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ return item;
+ }
+
+ private void merge_with_next (Node<G>? node) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node._next != null);
+ assert (node._size + node._next._size <= NODE_SIZE);
+#else
+ assume (node._next != null);
+ assume (node._size + node._next._size <= NODE_SIZE);
+#endif
+ unowned Node<G> next = node._next;
+ Memory.copy(&node._data[node._size], next._data, sizeof(G) * next._size);
+ node._size += next._size;
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (node._size <= NODE_SIZE);
+#else
+ assume (node._size <= NODE_SIZE);
+#endif
+ delete_node (next);
+#if CONSISTENCY_CHECKS
+ check ();
+#endif
+ }
+
+ private void delete_node (Node<G>? node) {
+ if (likely (node._next != null)) {
+ node._next._prev = node._prev;
+ } else {
+ _tail = node._prev;
+ }
+ if (GLib.likely (node._prev != null)) {
+ node._prev._next = (owned)node._next;
+ } else {
+ _head = (owned)node._next;
+ }
+ }
+
+#if DUMP
+ private void dump () {
+ stdout.printf ("UnrolledLinkedList %p\n Size %d\n", this, _size);
+ for (unowned Node<G>? node = _head; node != null; node = node._next) {
+ stdout.printf (" Node %p\n Prev %p\n Next %p\n", node, node._prev, node._next);
+ for (int i = 0; i < node._size; i++) {
+ stdout.printf (" %d: %p (\"%s\")\n", i, node._data[i],
(string)node._data[i]);
+ }
+ }
+ }
+#endif
+#if CONSISTENCY_CHECKS
+ private void check () {
+ int size = 0;
+ for (unowned Node<G>? node = _head; node != null; node = node._next) {
+ size += node._size;
+ }
+ assert (size == _size);
+ size = 0;
+ for (unowned Node<G>? node = _tail; node != null; node = node._prev) {
+ size += node._size;
+ }
+ assert (size == _size);
+ }
+#endif
+
+ private int _size = 0;
+ private int _stamp = 0;
+ private Node<G>? _head = null;
+ private unowned Node<G>? _tail = null;
+ private Functions.EqualDataFuncClosure<G> _equal_func;
+ private const int NODE_SIZE = 29; // Chosen for node to be multiply cache line (4 on 64 bit and 2 on
32 bit)
+ private const int SPLIT_POS = (NODE_SIZE - 1)/2 + 1;
+ private const int MERGE_THRESHOLD = (NODE_SIZE * 4)/5;
+
+ private class Iterator<G> : Object, Vala.Traversable<G>, Vala.Iterator<G>, ListIterator<G>,
BidirIterator<G>, BidirListIterator<G> {
+ public Iterator (UnrolledLinkedList<G> list) {
+ this._list = list;
+ this._stamp = list._stamp;
+ }
+
+ public Iterator.from_iterator (Iterator<G> iter) {
+ _list = iter._list;
+ _stamp = iter._stamp;
+ _current = iter._current;
+ _pos = iter._pos;
+ _deleted = iter._deleted;
+ _index = iter._index;
+ }
+
+ public new bool foreach (ForallFunc<G> f) {
+#if DUMP
+ stdout.printf ("FOREACH BEGIN [%p -> %p %d]\n", this, _current, _pos);
+ _list.dump ();
+ try {
+#endif
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ unowned Node<G>? current = _current;
+ unowned Node<G>? prev = null;
+ int pos = _pos;
+ int prev_pos = -1;
+ int index = _index;
+ int prev_index = -1;
+ bool deleted = _deleted;
+ if (current == null) {
+ current = _list._head;
+ pos = 0;
+ deleted = false;
+ index = 0;
+ if (unlikely (current == null)) {
+ return true;
+ }
+ } else if (unlikely (deleted)) {
+ if (unlikely(_current._size == _pos + 1)) {
+ if (unlikely (_current._next != null)) {
+ return true;
+ }
+ prev = current;
+ current = _current._next;
+ prev_pos = pos;
+ pos = 0;
+ deleted = false;
+ prev_index = index++;
+ } else {
+ prev = current;
+ prev_pos = pos++;
+ deleted = false;
+ prev_index = index++;
+ }
+ }
+ for (; current != null; prev = current, current = current._next, pos = 0) {
+ int size = current._size;
+ for (; pos < size; prev = current, prev_pos = pos++, prev_index = index++) {
+ deleted = false;
+ if (!f (current._data[pos])) {
+ _current = current;
+ _pos = pos;
+ _deleted = deleted;
+ _index = index;
+ return false;
+ }
+ }
+ }
+ _current = prev;
+ _pos = prev_pos;
+ _deleted = deleted;
+ _index = prev_index;
+ return true;
+#if DUMP
+ } finally {
+ _list.dump ();
+ stdout.printf ("FOREACH END [%p -> %p %d]\n", this, _current, _pos);
+ }
+#endif
+ }
+
+ public Vala.Iterator<G>[] tee (uint forks) {
+ if (forks == 0) {
+ return new Vala.Iterator<G>[0];
+ } else {
+ Vala.Iterator<G>[] result = new Vala.Iterator<G>[forks];
+ result[0] = this;
+ for (uint i = 1; i < forks; i++) {
+ result[i] = new Iterator<G>.from_iterator (this);
+ }
+ return result;
+ }
+ }
+
+ public bool next () {
+#if DUMP
+ stdout.printf ("NEXT BEGIN [%p -> %p %d]\n", this, _current, _pos);
+ _list.dump ();
+ try {
+#endif
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ if (unlikely (_current == null)) {
+ _current = _list._head;
+ if (_current != null) {
+ _pos = 0;
+ _deleted = false;
+ _index = 0;
+ }
+ return _current != null;
+ } else if (unlikely(_current._size == _pos + 1)) {
+ if (likely (_current._next != null)) {
+ _current = _current._next;
+ _pos = 0;
+ _deleted = false;
+ _index++;
+ return true;
+ } else {
+ return false;
+ }
+ } else {
+ _pos++;
+ _deleted = false;
+ _index++;
+ return true;
+ }
+#if DUMP
+ } finally {
+ _list.dump ();
+ stdout.printf ("NEXT END [%p -> %p %d]\n", this, _current, _pos);
+ }
+#endif
+ }
+
+ public bool has_next () {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ if (unlikely (_current == null)) {
+ return _list._head != null;
+ } else if (unlikely(_current._size == _pos + 1)) {
+ return _current._next != null;
+ } else {
+ return true;
+ }
+ }
+
+ public new G get () {
+ assert (_list._stamp == _stamp);
+ assert (_current != null && !_deleted);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= _pos && _pos < _current._size);
+#else
+ assume (0 <= _pos && _pos < _current._size);
+#endif
+ return _current._data[_pos];
+ }
+
+ public void remove () {
+#if DUMP
+ stdout.printf ("REMOVE BEGIN [%p -> %p %d]\n", this, _current, _pos);
+ _list.dump ();
+#endif
+ assert (_list._stamp == _stamp);
+ assert (_current != null && !_deleted);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= _pos && _pos <= _current._size);
+#else
+ assume (0 <= _pos && _pos <= _current._size);
+#endif
+ _list.remove_from_node (_current, _pos, out _current, out _pos);
+ _deleted = true;
+ _index--;
+ _stamp++;
+#if DUMP
+ _list.dump ();
+ stdout.printf ("REMOVE END [%p -> %p %d]\n", this, _current, _pos);
+#endif
+ }
+
+ public bool valid {
+ get {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ return _current != null && !_deleted;
+ }
+ }
+
+ public bool read_only { get { return false; } }
+
+ public bool previous () {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ if (unlikely (_deleted)) {
+ _deleted = false;
+ return _current != null;
+ } else if (unlikely (_current == null)) {
+ return false;
+ } else if (unlikely (_pos == 0)) {
+ if (likely (_current._prev != null)) {
+ _current = _current._prev;
+ _pos = _current._size - 1;
+ _index--;
+ return true;
+ } else {
+ return false;
+ }
+ } else {
+ _pos--;
+ _index--;
+ return true;
+ }
+ }
+
+ public bool has_previous () {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ if (unlikely (_deleted)) {
+ return _current != null;
+ } else if (unlikely (_current == null)) {
+ return false;
+ } else if (unlikely (_pos == 0)) {
+ return _current._prev != null;
+ } else {
+ return true;
+ }
+ }
+
+ public bool first () {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ _current = _list._head;
+ _deleted = false;
+ if (_current != null) {
+ _pos = 0;
+ } else {
+ _pos = -1;
+ }
+ _index = 0;
+ return _current != null;
+ }
+
+ public bool last () {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ _current = _list._tail;
+ _deleted = false;
+ if (_current != null) {
+ _pos = _current._size - 1;
+ } else {
+ _pos = -1;
+ }
+ _index = _list._size - 1;
+ return _current != null;
+ }
+
+ public new void set (G item) {
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ _current._data[_pos] = item;
+ _list._stamp++;
+ _stamp++;
+ }
+
+ public void add (G item) {
+#if DUMP
+ stdout.printf ("ADD BEGIN %p (%s) [%p -> %p %d]\n", item, (string)item, this,
_current, _pos);
+ _list.dump ();
+#endif
+ assert (_list._stamp == _stamp);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (!(_current == null) || _pos == -1);
+ assert (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#else
+ assume (!(_current == null) || _pos == -1);
+ assume (!(_current != null) || (0 <= _pos && _pos <= _current._size));
+#endif
+ if (likely (_current != null)) {
+ _list.add_to_node (_current, item, _pos + 1, out _current, out _pos);
+ } else {
+ if (likely (_list._head != null)) {
+ _current = _list._head;
+ } else {
+ _current = _list._tail = _list._head = new Node<G>();
+ }
+ _list.add_to_node (_current, item, 0);
+ _pos = 0;
+ }
+ _stamp++;
+ _index++;
+ _deleted = false;
+#if DUMP
+ _list.dump ();
+ stdout.printf ("ADD END [%p -> %p %d]\n", this, _current, _pos);
+#endif
+ }
+
+ public int index () {
+ assert (_list._stamp == _stamp);
+ assert (_current != null);
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (0 <= _pos && _pos <= _current._size);
+#else
+ assume (0 <= _pos && _pos <= _current._size);
+#endif
+ return _index;
+ }
+
+ public void insert (G item) {
+#if DUMP
+ stdout.printf ("INSERT BEGIN %p (%s) [%p -> %p %d]\n", item, (string)item, this,
_current, _pos);
+ _list.dump ();
+#endif
+ assert (_list._stamp == _stamp);
+
+ if (unlikely (_deleted)) {
+ if (unlikely (_current == null)) {
+ if (likely (_list._head != null)) {
+ _current = _list._head;
+ _pos = -1;
+ } else {
+ _current = _list._tail = _list._head = new Node<G>();
+ _pos = -1;
+ }
+ }
+ _list.add_to_node (_current, item, _pos + 1, out _current, out _pos);
+ if (unlikely (_pos == 0)) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_current._prev != null);
+#endif
+ _current = _current._prev;
+ _pos = _current._prev._size - 1;
+ } else {
+ _pos--;
+ }
+ } else {
+ _list.add_to_node (_current, item, _pos, out _current, out _pos);
+ if (unlikely (_pos + 1 == _current._size)) {
+#if !DISABLE_INTERNAL_ASSERTS
+ assert (_current._next != null);
+#endif
+ _current = _current._next;
+ _pos = 0;
+ } else {
+ _pos++;
+ }
+ }
+ _stamp++;
+ _index++;
+#if DUMP
+ _list.dump ();
+ stdout.printf ("INSERT END [%p -> %p %d]\n", this, _current, _pos);
+#endif
+ }
+
+ private UnrolledLinkedList<G>? _list;
+ private int _stamp;
+ private unowned Node<G>? _current = null;
+ private int _pos = -1;
+ private bool _deleted = false;
+ private int _index = -1;
+ }
+
+ [Compact]
+ private class Node<G> {
+ public unowned Node<G>? _prev = null;
+ public Node<G>? _next = null;
+ public int _size = 0;
+ public G _data[29 /* NODE_SIZE */];
+ }
+}
+
diff --git a/gee/utils/assume.h b/gee/utils/assume.h
new file mode 100644
index 0000000..3ec100b
--- /dev/null
+++ b/gee/utils/assume.h
@@ -0,0 +1,33 @@
+/* assume.h
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+#ifndef VALA_UTILS_ASSUME
+#define VALA_UTILS_ASSUME
+
+#if __GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__ >= 40500
+#define vala_utils_assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
+#elif defined(_MSC_VER)
+#define vala_utils_assume(cond) __assume(cond)
+#else
+#define vala_utils_assume(cond) NULL
+#endif
+
+#endif
diff --git a/gee/utils/async.h b/gee/utils/async.h
new file mode 100644
index 0000000..9aa3a5a
--- /dev/null
+++ b/gee/utils/async.h
@@ -0,0 +1,31 @@
+/* async.h
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+#ifndef VALA_UTILS_ASYNC
+#define VALA_UTILS_ASYNC
+
+#include <glib.h>
+
+#define vala_utils_async_yield_and_unlock(mutex, callback, user_data) g_mutex_unlock (mutex)
+#define vala_utils_async_yield_and_unlock_finish(arg) do {} while (0)
+
+#endif
+
diff --git a/gee/utils/free.h b/gee/utils/free.h
new file mode 100644
index 0000000..586d212
--- /dev/null
+++ b/gee/utils/free.h
@@ -0,0 +1,30 @@
+/* free.h
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+#ifndef VALA_UTILS_ASYNC
+#define VALA_UTILS_ASYNC
+
+#include <glib.h>
+
+#define vala_utils_free_get_destroy_notify(type, dup, destroy) (destroy)
+
+#endif
+
diff --git a/gee/utils/misc.h b/gee/utils/misc.h
new file mode 100644
index 0000000..7ebb312
--- /dev/null
+++ b/gee/utils/misc.h
@@ -0,0 +1,30 @@
+/* async.h
+ *
+ * Copyright (C) 2013 Maciej Piechotka
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author:
+ * Maciej Piechotka <uzytkownik2 gmail com>
+ */
+#ifndef VALA_UTILS_MISC
+#define VALA_UTILS_MISC
+
+#include <glib.h>
+
+#define vala_utils_misc_unused(par) (void)par
+
+#endif
+
diff --git a/gee/utils/utils.vapi b/gee/utils/utils.vapi
new file mode 100644
index 0000000..85346a4
--- /dev/null
+++ b/gee/utils/utils.vapi
@@ -0,0 +1,20 @@
+namespace Vala {
+ namespace Utils {
+ namespace Assume {
+ [CCode (cheader_filename = "assume.h", cname = "vala_utils_assume")]
+ public void assume (bool cond);
+ }
+ namespace Async {
+ [CCode (cheader_filename = "async.h")]
+ public async void yield_and_unlock (GLib.Mutex mutex);
+ }
+ namespace Free {
+ [CCode (cheader_filename = "free.h")]
+ public GLib.DestroyNotify? get_destroy_notify<G> ();
+ }
+ namespace Misc {
+ [CCode (cheader_filename = "misc.h", simple_generics = true)]
+ public void unused<G> (G unused);
+ }
+ }
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
