[folks] Folks.SmallSet: add and test
- From: Simon McVittie <smcv src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [folks] Folks.SmallSet: add and test
- Date: Thu, 4 Apr 2013 14:13:02 +0000 (UTC)
commit 87422afd3b6341703f3f4d8718ac5cec8374969a
Author: Simon McVittie <simon mcvittie collabora co uk>
Date: Thu Apr 4 12:58:50 2013 +0100
Folks.SmallSet: add and test
Bug: https://bugzilla.gnome.org/show_bug.cgi?id=687161
Reviewed-by: Philip Withnall <philip tecnocode co uk>
[squashed in responses to review -smcv]
Signed-off-by: Simon McVittie <simon mcvittie collabora co uk>
folks/Makefile.am | 6 +
folks/folks-generics.vapi | 45 ++
folks/small-set-internal.h | 85 ++++
folks/small-set.c | 954 ++++++++++++++++++++++++++++++++++++++++++++
folks/small-set.h | 73 ++++
tests/folks/Makefile.am | 7 +
tests/folks/small-set.vala | 421 +++++++++++++++++++
7 files changed, 1591 insertions(+), 0 deletions(-)
---
diff --git a/folks/Makefile.am b/folks/Makefile.am
index c4746b9..57c10f3 100644
--- a/folks/Makefile.am
+++ b/folks/Makefile.am
@@ -1,4 +1,5 @@
AM_CPPFLAGS = \
+ -I${top_srcdir} \
-include $(CONFIG_HEADER) \
-DPACKAGE_DATADIR=\"$(pkgdatadir)\" \
-DBACKEND_DIR=\"$(BACKEND_DIR)\" \
@@ -11,8 +12,13 @@ lib_LTLIBRARIES = libfolks.la
##################################################
# Internal library
##################################################
+
libfolks_internal_la_SOURCES = \
+ folks-generics.vapi \
internal.vala \
+ small-set.c \
+ small-set.h \
+ small-set-internal.h \
$(NULL)
libfolks_internal_la_VALAFLAGS = \
diff --git a/folks/folks-generics.vapi b/folks/folks-generics.vapi
new file mode 100644
index 0000000..cab90a0
--- /dev/null
+++ b/folks/folks-generics.vapi
@@ -0,0 +1,45 @@
+/*
+ * generics.vapi - generic Gee interfaces implemented in C
+ *
+ * Copyright © 2013 Intel Corporation
+ *
+ * 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
+ *
+ * Authors:
+ * Simon McVittie <simon mcvittie collabora co uk>
+ */
+
+/* Unfortunately, we have to do this as a .vapi because going from C to
+ * GIR to Vala loses the generic types. FIXME: GNOME #639908 would
+ * make it possible to go via GIR like tests/lib/telepathy/contactlist does. */
+
+namespace Folks
+{
+ [CCode (cheader_filename = "folks/small-set.h")]
+ internal class SmallSet<G> : Gee.AbstractSet<G>
+ {
+ internal static SmallSet<G> empty<G> ();
+
+ internal SmallSet (owned Gee.HashDataFunc<G>? item_hash = null,
+ owned Gee.EqualDataFunc<G>? item_equals = null);
+
+ internal static SmallSet<G> copy (Gee.Iterable<G> iterable,
+ owned Gee.HashDataFunc<G>? item_hash = null,
+ owned Gee.EqualDataFunc<G>? item_equals = null);
+ }
+}
+
+/* vim:set ft=vala: */
diff --git a/folks/small-set-internal.h b/folks/small-set-internal.h
new file mode 100644
index 0000000..aeda316
--- /dev/null
+++ b/folks/small-set-internal.h
@@ -0,0 +1,85 @@
+/*
+ * small-set - a set optimized for fast iteration when there are few items
+ *
+ * Copyright © 2013 Intel Corporation
+ *
+ * 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
+ *
+ * Authors:
+ * Simon McVittie <simon mcvittie collabora co uk>
+ */
+
+#ifndef FOLKS_SMALL_SET_INTERNAL_H
+#define FOLKS_SMALL_SET_INTERNAL_H
+
+#include <folks/small-set.h>
+
+G_BEGIN_DECLS
+
+typedef struct _FolksSmallSetIterator FolksSmallSetIterator;
+typedef struct _FolksSmallSetIteratorClass FolksSmallSetIteratorClass;
+
+GType folks_small_set_iterator_get_type (void);
+
+#define FOLKS_TYPE_SMALL_SET_ITERATOR \
+ (folks_small_set_iterator_get_type ())
+#define FOLKS_SMALL_SET_ITERATOR(obj) \
+ (G_TYPE_CHECK_INSTANCE_CAST ((obj), FOLKS_TYPE_SMALL_SET_ITERATOR, \
+ FolksSmallSetIterator))
+#define FOLKS_SMALL_SET_ITERATOR_CLASS(klass) \
+ (G_TYPE_CHECK_CLASS_CAST ((klass), FOLKS_TYPE_SMALL_SET_ITERATOR, \
+ FolksSmallSetIteratorClass))
+#define FOLKS_IS_SMALL_SET_ITERATOR(obj) \
+ (G_TYPE_CHECK_INSTANCE_TYPE ((obj), FOLKS_TYPE_SMALL_SET_ITERATOR))
+#define FOLKS_IS_SMALL_SET_ITERATOR_CLASS(klass) \
+ (G_TYPE_CHECK_CLASS_TYPE ((klass), FOLKS_TYPE_SMALL_SET_ITERATOR))
+#define FOLKS_SMALL_SET_ITERATOR_GET_CLASS(obj) \
+ (G_TYPE_INSTANCE_GET_CLASS ((obj), FOLKS_TYPE_SMALL_SET_ITERATOR, \
+ FolksSmallSetIteratorClass))
+
+typedef enum {
+ FOLKS_SMALL_SET_FLAG_READ_ONLY = (1 << 0),
+} FolksSmallSetFlags;
+
+/* This is in the (internal) header to allow inlining. */
+struct _FolksSmallSet {
+ /*<private>*/
+ GeeAbstractSet parent_instance;
+
+ GPtrArray *items;
+ GType item_type;
+ GBoxedCopyFunc item_dup;
+ GDestroyNotify item_free;
+ GeeHashDataFunc item_hash;
+ gpointer item_hash_data;
+ GDestroyNotify item_hash_data_free;
+ GeeEqualDataFunc item_equals;
+ gpointer item_equals_data;
+ GDestroyNotify item_equals_data_free;
+
+ FolksSmallSetFlags flags;
+ FolksSmallSet *rw_version;
+};
+
+FolksSmallSet *
+_folks_small_set_new_take_array (GPtrArray *arr,
+ GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free);
+
+G_END_DECLS
+
+#endif
diff --git a/folks/small-set.c b/folks/small-set.c
new file mode 100644
index 0000000..28ad754
--- /dev/null
+++ b/folks/small-set.c
@@ -0,0 +1,954 @@
+/*
+ * small-set - a set optimized for fast iteration when there are few items
+ *
+ * Copyright © 2013 Intel Corporation
+ *
+ * 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
+ *
+ * Authors:
+ * Simon McVittie <simon mcvittie collabora co uk>
+ */
+
+#include "folks/small-set.h"
+#include "folks/small-set-internal.h"
+
+/*
+ * FolksSmallSet:
+ *
+ * FolksSmallSet is a wrapper around an array, designed to be used for
+ * sets with zero or few items. If necessary, it can be used
+ * as a read-only, Gee-compatible wrapper around a separately-maintained
+ * GPtrArray.
+ *
+ * Memory efficiency: this is about as small as you're going to get, given
+ * the constraints of libgee.
+ *
+ * Performance: iteration is very fast, iterating over a read-only view is
+ * very fast, copying an existing set is quite fast, foreach is quite fast.
+ * Everything else scales up poorly with large numbers of elements:
+ * adding, removing and testing membership are all O(n). The intention is
+ * that if n can be large, you should use HashSet or something.
+ *
+ * The constructor takes a hash function but does not use it, making it
+ * a drop-in replacement for HashSet. In theory we could use the hash function
+ * for faster de-duplication when taking a union of sets, if that would be
+ * helpful.
+ */
+
+struct _FolksSmallSetClass {
+ /*<private>*/
+ GeeAbstractSetClass parent_class;
+};
+
+typedef enum {
+ /* Iteration has started (we called next() at least once).
+ * get() is valid, unless REMOVED is also set. */
+ ITER_STARTED = (1 << 0),
+ /* The item pointed to has been removed. get() is invalid
+ * until the next call to next(). */
+ ITER_REMOVED = (1 << 1),
+} IterFlags;
+
+struct _FolksSmallSetIterator {
+ GObject parent_instance;
+ FolksSmallSet *set;
+ guint i;
+ IterFlags flags;
+};
+
+struct _FolksSmallSetIteratorClass {
+ GObjectClass parent_class;
+};
+
+static void set_iface_init (GeeSetIface *iface);
+static void collection_iface_init (GeeCollectionIface *iface);
+static void iterable_iface_init (GeeIterableIface *iface);
+static void traversable_iface_init (GeeTraversableIface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (FolksSmallSet, folks_small_set,
+ GEE_TYPE_ABSTRACT_SET,
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_TRAVERSABLE, traversable_iface_init);
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_ITERABLE, NULL);
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_COLLECTION, NULL);
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_SET, NULL))
+
+/*
+ * Returns: (transfer none): self[i]
+ */
+static inline gconstpointer
+_get (FolksSmallSet *self,
+ guint i)
+{
+ return g_ptr_array_index (self->items, i);
+}
+
+/*
+ * Returns: (transfer full): self[i]
+ */
+static inline gpointer
+_dup (FolksSmallSet *self,
+ guint i)
+{
+ if (self->item_dup == NULL)
+ return (gpointer) _get (self, i);
+
+ return self->item_dup ((gpointer) _get (self, i));
+}
+
+/*
+ * @position: (out): i such that item_equals (self[i], item)
+ * Returns: %FALSE if there is no such i
+ */
+static inline gboolean
+_find (FolksSmallSet *self,
+ gconstpointer item,
+ guint *position)
+{
+ guint i;
+
+ /* If we're a read-only view of something with complicated comparator
+ * functions, we need to use that version's comparators, because we
+ * can't copy delegates */
+ if (self->rw_version != NULL)
+ {
+ g_assert (self->items == self->rw_version->items);
+ self = self->rw_version;
+ }
+
+ for (i = 0; i < self->items->len; i++)
+ {
+ gconstpointer candidate = _get (self, i);
+ gboolean equal;
+
+ if (self->item_equals == NULL ||
+ self->item_equals == (GeeEqualDataFunc) g_direct_equal)
+ equal = (candidate == item);
+ else
+ equal = self->item_equals (candidate, item, self->item_equals_data);
+
+ if (equal)
+ {
+ if (position != NULL)
+ *position = i;
+
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+static void
+folks_small_set_configure (FolksSmallSet *self,
+ GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free,
+ GeeHashDataFunc item_hash,
+ gpointer item_hash_data,
+ GDestroyNotify item_hash_data_free,
+ GeeEqualDataFunc item_equals,
+ gpointer item_equals_data,
+ GDestroyNotify item_equals_data_free)
+{
+ /* We bypass properties because this entire class exists for performance
+ * reasons, and it isn't intended to be subclassed or anything. */
+ self->item_type = item_type;
+ self->item_dup = item_dup;
+ self->item_free = item_free;
+
+ if (item_hash == NULL)
+ {
+ self->item_hash = gee_functions_get_hash_func_for (self->item_type,
+ &self->item_hash_data, &self->item_hash_data_free);
+ }
+ else
+ {
+ self->item_hash = item_hash;
+ self->item_hash_data = item_hash_data;
+ self->item_hash_data_free = item_hash_data_free;
+ }
+
+ if (item_equals == NULL)
+ {
+ self->item_equals = gee_functions_get_equal_func_for (self->item_type,
+ &self->item_equals_data, &self->item_equals_data_free);
+ }
+ else
+ {
+ self->item_equals = item_equals;
+ self->item_equals_data = item_equals_data;
+ self->item_equals_data_free = item_equals_data_free;
+ }
+}
+
+/*
+ * Returns: (transfer full): a new read-only view
+ */
+static FolksSmallSet *
+_read_only_view (FolksSmallSet *self)
+{
+ FolksSmallSet *other;
+
+ g_return_val_if_fail (FOLKS_IS_SMALL_SET (self), NULL);
+
+ /* if we're already read-only, we are our own read-only view */
+ if (self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY)
+ return g_object_ref (self);
+
+ /* if we're not, make a new one */
+ other = g_object_new (FOLKS_TYPE_SMALL_SET,
+ NULL);
+ other->items = g_ptr_array_ref (self->items);
+ other->flags = FOLKS_SMALL_SET_FLAG_READ_ONLY;
+
+ folks_small_set_configure (other, self->item_type, self->item_dup,
+ self->item_free, NULL, NULL, NULL, NULL, NULL, NULL);
+
+ if (self->item_hash_data == NULL &&
+ self->item_hash_data_free == NULL &&
+ self->item_equals_data == NULL &&
+ self->item_equals_data_free == NULL)
+ {
+ /* they're simple enough functions to be copied */
+ other->item_hash = self->item_hash;
+ other->item_equals = self->item_equals;
+ }
+ else
+ {
+ /* we need to use this one's comparator functions */
+ other->rw_version = g_object_ref (self);
+ }
+
+ /* FIXME: benchmark whether giving self a weak ref to other is a
+ * performance win or not */
+
+ return other;
+}
+
+/* Covariance? We've heard of it */
+#define abstract_set_get_read_only_view \
+ ((GeeSet * (*) (GeeAbstractSet *)) _read_only_view)
+#define abstract_collection_get_read_only_view \
+ ((GeeCollection * (*) (GeeAbstractCollection *)) _read_only_view)
+
+static gint
+folks_small_set_get_size (GeeAbstractCollection *collection)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+
+ g_return_val_if_fail (self != NULL, 0);
+ g_return_val_if_fail (self->items->len <= G_MAXINT, G_MAXINT);
+
+ return (gint) self->items->len;
+}
+
+static gboolean
+folks_small_set_get_read_only (GeeAbstractCollection *collection)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+
+ g_return_val_if_fail (self != NULL, TRUE);
+
+ return ((self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) != 0);
+}
+
+/*
+ * This is deliberately the same signature as HashSet(), even though
+ * we don't (currently) use the hashing function.
+ *
+ * Returns: (transfer full):
+ */
+FolksSmallSet *
+folks_small_set_new (GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free,
+ GeeHashDataFunc item_hash,
+ gpointer item_hash_data,
+ GDestroyNotify item_hash_data_free,
+ GeeEqualDataFunc item_equals,
+ gpointer item_equals_data,
+ GDestroyNotify item_equals_data_free)
+{
+ FolksSmallSet *self = g_object_new (FOLKS_TYPE_SMALL_SET,
+ NULL);
+
+ /* We bypass properties because this entire class exists for performance
+ * reasons, and it isn't intended to be subclassed or anything. */
+ folks_small_set_configure (self, item_type, item_dup, item_free,
+ item_hash, item_hash_data, item_hash_data_free,
+ item_equals, item_equals_data, item_equals_data_free);
+ self->items = g_ptr_array_new_full (0, item_free);
+ self->flags = 0;
+
+ return self;
+}
+
+/*
+ * Returns: (transfer full):
+ */
+FolksSmallSet *
+folks_small_set_empty (GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free)
+{
+ FolksSmallSet *self = g_object_new (FOLKS_TYPE_SMALL_SET,
+ NULL);
+
+ self->items = g_ptr_array_new_full (0, item_free);
+ self->item_type = item_type;
+ self->flags = FOLKS_SMALL_SET_FLAG_READ_ONLY;
+
+ return self;
+}
+
+/*
+ * @arr: (transfer container): must have @item_free as its free-function
+ * Returns: (transfer full):
+ */
+FolksSmallSet *
+_folks_small_set_new_take_array (GPtrArray *arr,
+ GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free)
+{
+ FolksSmallSet *self = g_object_new (FOLKS_TYPE_SMALL_SET,
+ NULL);
+
+ folks_small_set_configure (self, item_type, item_dup, item_free,
+ NULL, NULL, NULL,
+ NULL, NULL, NULL);
+ self->items = arr;
+ self->flags = FOLKS_SMALL_SET_FLAG_READ_ONLY;
+
+ return self;
+}
+
+/*
+ * Returns: (transfer full):
+ */
+FolksSmallSet *
+folks_small_set_copy (GeeIterable *iterable,
+ GeeHashDataFunc item_hash,
+ gpointer item_hash_data,
+ GDestroyNotify item_hash_data_free,
+ GeeEqualDataFunc item_equals,
+ gpointer item_equals_data,
+ GDestroyNotify item_equals_data_free)
+{
+ FolksSmallSet *self;
+ GeeIterator *iter;
+ GeeTraversableIface *traversable_iface;
+ GType item_type;
+ GBoxedCopyFunc item_dup;
+ GDestroyNotify item_free;
+
+ /* Deliberately not allowing for subclasses here: this class is not
+ * subclassable, and it's slower if we do check for subclasses. */
+ if (G_OBJECT_TYPE (iterable) == FOLKS_TYPE_SMALL_SET)
+ {
+ /* Fast path: copy the items directly from the other one. */
+ FolksSmallSet *other = (FolksSmallSet *) iterable;
+ guint i;
+
+ self = g_object_new (FOLKS_TYPE_SMALL_SET,
+ NULL);
+ folks_small_set_configure (self,
+ other->item_type, other->item_dup, other->item_free,
+ item_hash, item_hash_data, item_hash_data_free,
+ item_equals, item_equals_data, item_equals_data_free);
+ self->items = g_ptr_array_new_full (other->items->len,
+ other->item_free);
+ self->flags = 0;
+
+ for (i = 0; i < other->items->len; i++)
+ g_ptr_array_add (self->items, _dup (other, i));
+
+ return self;
+ }
+
+ traversable_iface = GEE_TRAVERSABLE_GET_INTERFACE (iterable);
+ g_assert (traversable_iface != NULL);
+ item_type = traversable_iface->get_g_type ((GeeTraversable *) iterable);
+ item_dup = traversable_iface->get_g_dup_func ((GeeTraversable *) iterable);
+ item_free = traversable_iface->get_g_destroy_func ((GeeTraversable *) iterable);
+
+ self = folks_small_set_new (item_type, item_dup, item_free,
+ item_hash, item_hash_data, item_hash_data_free,
+ item_equals, item_equals_data, item_equals_data_free);
+ iter = gee_iterable_iterator (iterable);
+
+ if (GEE_IS_SET (iterable))
+ {
+ /* If it's a set, then we don't need to worry about de-duplicating
+ * the items. Just copy them in. */
+ while (gee_iterator_next (iter))
+ {
+ g_ptr_array_add (self->items, gee_iterator_get (iter));
+ }
+ }
+ else
+ {
+ /* Do it the hard way: there might be duplicates. */
+ while (gee_iterator_next (iter))
+ {
+ gpointer item = gee_iterator_get (iter);
+
+ if (_find (self, item, NULL))
+ {
+ if (item_free != NULL)
+ item_free (item);
+ }
+ else
+ {
+ g_ptr_array_add (self->items, item);
+ }
+ }
+ }
+}
+
+enum {
+ PROP_0,
+ PROP_G_TYPE,
+ PROP_G_DUP_FUNC,
+ PROP_G_DESTROY_FUNC,
+ N_PROPERTIES
+};
+
+static void
+folks_small_set_init (FolksSmallSet *self)
+{
+}
+
+static void
+folks_small_set_dispose (GObject *obj)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (obj);
+
+ g_clear_object (&self->rw_version);
+
+ if ((self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) == 0)
+ g_ptr_array_set_size (self->items, 0);
+
+ ((GObjectClass *) folks_small_set_parent_class)->dispose (obj);
+}
+
+static void
+folks_small_set_finalize (GObject *obj)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (obj);
+
+ g_ptr_array_unref (self->items);
+
+ if (self->item_hash_data_free != NULL)
+ self->item_hash_data_free (self->item_hash_data);
+
+ if (self->item_equals_data_free != NULL)
+ self->item_equals_data_free (self->item_equals_data);
+
+ ((GObjectClass *) folks_small_set_parent_class)->finalize (obj);
+}
+
+/*
+ * Call @f for each element, until it returns %FALSE.
+ *
+ * Overridden because we can do better than allocating a new GObject,
+ * which is what Gee would do.
+ *
+ * Returns: %FALSE if @f returns %FALSE, or %TRUE if we reached the
+ * end of the set.
+ */
+static gboolean
+folks_small_set_foreach (GeeTraversable *traversable,
+ GeeForallFunc f,
+ gpointer user_data)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (traversable);
+ guint i;
+
+ g_return_val_if_fail (self != NULL, FALSE);
+
+ for (i = 0; i < self->items->len; i++)
+ {
+ /* Yes, GeeForallFunc receives a new copy/ref, astonishing though
+ * that may seem to C programmers. */
+ if (!f (_dup (self, i), user_data))
+ return FALSE;
+ }
+
+ return TRUE;
+}
+
+static void
+traversable_iface_init (GeeTraversableIface *iface)
+{
+ iface->foreach = folks_small_set_foreach;
+}
+
+static GeeIterator *
+folks_small_set_iterator (GeeAbstractCollection *collection)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+ FolksSmallSetIterator *iter;
+
+ g_return_val_if_fail (self != NULL, NULL);
+
+ iter = g_object_new (FOLKS_TYPE_SMALL_SET_ITERATOR,
+ NULL);
+
+ iter->set = g_object_ref (self);
+ iter->flags = 0;
+ return (GeeIterator *) iter;
+}
+
+static gboolean
+folks_small_set_contains (GeeAbstractCollection *collection,
+ gconstpointer item)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+
+ return _find (self, item, NULL);
+}
+
+/*
+ * Add @item.
+ *
+ * Returns: %TRUE if it was not already there.
+ */
+static gboolean
+folks_small_set_add (GeeAbstractCollection *collection,
+ gconstpointer item)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+ gpointer copy;
+
+ g_return_val_if_fail (self != NULL, FALSE);
+ g_return_val_if_fail ((self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) == 0, FALSE);
+
+ if (_find (self, item, NULL))
+ return FALSE;
+
+ if (self->item_dup == NULL)
+ copy = (gpointer) item;
+ else
+ copy = self->item_dup ((gpointer) item);
+
+ g_ptr_array_add (self->items, copy);
+ return TRUE;
+}
+
+/*
+ * Remove @item.
+ *
+ * Returns: %TRUE if it was previously there.
+ */
+static gboolean
+folks_small_set_remove (GeeAbstractCollection *collection,
+ gconstpointer item)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+ g_return_val_if_fail ((self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) == 0, FALSE);
+
+ if (self->item_equals == NULL ||
+ self->item_equals == (GeeEqualDataFunc) g_direct_equal)
+ {
+ if (g_ptr_array_remove_fast (self->items, (gpointer) item))
+ return TRUE;
+ }
+ else
+ {
+ guint pos;
+
+ if (_find (self, item, &pos))
+ {
+ g_ptr_array_remove_index_fast (self->items, pos);
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+/*
+ * Remove all items.
+ */
+static void
+folks_small_set_clear (GeeAbstractCollection *collection)
+{
+ FolksSmallSet *self = FOLKS_SMALL_SET (collection);
+
+ g_return_if_fail (self != NULL);
+ g_return_if_fail ((self->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) == 0);
+
+ g_ptr_array_set_size (self->items, 0);
+}
+
+static void
+folks_small_set_class_init (FolksSmallSetClass *cls)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (cls);
+ GeeAbstractSetClass *as_class = GEE_ABSTRACT_SET_CLASS (cls);
+ GeeAbstractCollectionClass *ac_class = GEE_ABSTRACT_COLLECTION_CLASS (cls);
+
+ object_class->finalize = folks_small_set_finalize;
+
+ ac_class->contains = folks_small_set_contains;
+ ac_class->add = folks_small_set_add;
+ ac_class->remove = folks_small_set_remove;
+ ac_class->clear = folks_small_set_clear;
+ ac_class->iterator = folks_small_set_iterator;
+ ac_class->get_size = folks_small_set_get_size;
+ ac_class->get_read_only = folks_small_set_get_read_only;
+ ac_class->get_read_only_view = abstract_collection_get_read_only_view;
+
+ as_class->get_read_only_view = abstract_set_get_read_only_view;
+}
+
+/* ==== The iterator ==== */
+
+static void iterator_iface_init (GeeIteratorIface *iface);
+static void iterator_traversable_iface_init (GeeTraversableIface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (FolksSmallSetIterator, folks_small_set_iterator,
+ G_TYPE_OBJECT,
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_TRAVERSABLE,
+ iterator_traversable_iface_init);
+ G_IMPLEMENT_INTERFACE (GEE_TYPE_ITERATOR, iterator_iface_init))
+
+enum {
+ ITER_PROP_0,
+ ITER_PROP_VALID,
+ ITER_PROP_READ_ONLY,
+ ITER_PROP_G_TYPE,
+ ITER_PROP_G_DUP_FUNC,
+ ITER_PROP_G_DESTROY_FUNC,
+ N_ITER_PROPERTIES
+};
+
+/*
+ * Returns: (transfer full): self.get()
+ */
+static inline gpointer
+_iterator_dup (FolksSmallSetIterator *self)
+{
+ return _dup (self->set, self->i);
+}
+
+static inline gboolean
+_iterator_flag (FolksSmallSetIterator *self,
+ IterFlags flag)
+{
+ return ((self->flags & flag) != 0);
+}
+
+static inline gboolean
+_iterator_is_valid (FolksSmallSetIterator *self)
+{
+ return (_iterator_flag (self, ITER_STARTED) &&
+ !_iterator_flag (self, ITER_REMOVED) &&
+ self->i < self->set->items->len);
+}
+
+static inline gboolean
+_iterator_has_next (FolksSmallSetIterator *self)
+{
+ if (_iterator_flag (self, ITER_STARTED))
+ return ((self->i + 1) < self->set->items->len);
+ else
+ return (self->set->items->len > 0);
+}
+
+static void
+folks_small_set_iterator_init (FolksSmallSetIterator *self)
+{
+ self->set = NULL; /* fixed up by FolksSmallSet */
+ self->flags = 0;
+ self->i = G_MAXUINT;
+}
+
+static void
+folks_small_set_iterator_get_property (GObject *obj,
+ guint prop_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (obj);
+
+ switch (prop_id)
+ {
+ case ITER_PROP_VALID:
+ g_value_set_boolean (value, _iterator_is_valid (self));
+ break;
+
+ case ITER_PROP_READ_ONLY:
+ g_value_set_boolean (value, ((self->set->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) != 0));
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (obj, prop_id, pspec);
+ }
+}
+
+static void
+folks_small_set_iterator_set_property (GObject *obj,
+ guint prop_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ switch (prop_id)
+ {
+ /* ignore useless construct-only property - we always use the set's */
+ case ITER_PROP_G_TYPE:
+ case ITER_PROP_G_DUP_FUNC:
+ case ITER_PROP_G_DESTROY_FUNC:
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (obj, prop_id, pspec);
+ }
+}
+
+static void
+folks_small_set_iterator_finalize (GObject *obj)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (obj);
+
+ g_object_unref (self->set);
+
+ ((GObjectClass *) folks_small_set_iterator_parent_class)->finalize (obj);
+}
+
+static void
+folks_small_set_iterator_class_init (FolksSmallSetIteratorClass *cls)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (cls);
+
+ object_class->get_property = folks_small_set_iterator_get_property;
+ object_class->set_property = folks_small_set_iterator_set_property;
+ object_class->finalize = folks_small_set_iterator_finalize;
+
+ g_object_class_install_property (object_class, ITER_PROP_VALID,
+ g_param_spec_boolean ("valid", "Valid?", "TRUE if get() is valid",
+ FALSE, G_PARAM_STATIC_STRINGS | G_PARAM_READABLE));
+
+ g_object_class_install_property (object_class, ITER_PROP_READ_ONLY,
+ g_param_spec_boolean ("read-only", "Read-only?", "TRUE if read-only",
+ FALSE, G_PARAM_STATIC_STRINGS | G_PARAM_READABLE));
+
+ g_object_class_install_property (object_class, ITER_PROP_G_TYPE,
+ g_param_spec_gtype ("g-type", "Item type", "GType of items", G_TYPE_NONE,
+ G_PARAM_STATIC_STRINGS | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
+
+ g_object_class_install_property (object_class, ITER_PROP_G_DUP_FUNC,
+ g_param_spec_pointer ("g-dup-func", "Item copy function",
+ "Copies or refs an item",
+ G_PARAM_STATIC_STRINGS | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
+
+ g_object_class_install_property (object_class, ITER_PROP_G_DESTROY_FUNC,
+ g_param_spec_pointer ("g-destroy-func", "Item free function",
+ "Frees or unrefs item",
+ G_PARAM_STATIC_STRINGS | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
+}
+
+/* ---- ... as Traversable ---- */
+
+static gboolean
+folks_small_set_iterator_foreach (GeeTraversable *traversable,
+ GeeForallFunc f,
+ gpointer user_data)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (traversable);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+ g_return_val_if_fail (self->set != NULL, FALSE);
+
+ if (!_iterator_flag (self, ITER_STARTED))
+ {
+ self->flags = ITER_STARTED;
+ /* we will wrap around to 0 when we advance (ISO C guarantees that
+ * unsigned arithmetic wraps around) */
+ self->i = G_MAXUINT;
+ }
+ else if (!_iterator_flag (self, ITER_REMOVED))
+ {
+ /* Look at the current item before we advance.
+ * Yes, GeeForallFunc receives a new copy/ref. */
+ if (!f (_iterator_dup (self), user_data))
+ return FALSE;
+ }
+
+ for (self->i++; self->i < self->set->items->len; self->i++)
+ {
+ /* back onto track, even if an item was removed */
+ self->flags &= ~ITER_REMOVED;
+
+ /* Yes, GeeForallFunc receives a new copy/ref. */
+ if (!f (_iterator_dup (self), user_data))
+ return FALSE;
+ }
+
+ return TRUE;
+}
+
+static GType
+folks_small_set_iterator_get_g_type (GeeTraversable *traversable)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (traversable);
+
+ g_return_val_if_fail (self != NULL, G_TYPE_INVALID);
+
+ return self->set->item_type;
+}
+
+static GBoxedCopyFunc
+folks_small_set_iterator_get_g_dup_func (GeeTraversable *traversable)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (traversable);
+
+ g_return_val_if_fail (self != NULL, NULL);
+
+ return self->set->item_dup;
+}
+
+static GDestroyNotify
+folks_small_set_iterator_get_g_destroy_func (GeeTraversable *traversable)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (traversable);
+
+ g_return_val_if_fail (self != NULL, NULL);
+
+ return self->set->item_free;
+}
+
+static void
+iterator_traversable_iface_init (GeeTraversableIface *iface)
+{
+ iface->foreach = folks_small_set_iterator_foreach;
+ iface->get_g_type = folks_small_set_iterator_get_g_type;
+ iface->get_g_dup_func = folks_small_set_iterator_get_g_dup_func;
+ iface->get_g_destroy_func = folks_small_set_iterator_get_g_destroy_func;
+}
+
+/* ---- ... as Iterator ---- */
+
+static gboolean
+folks_small_set_iterator_next (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+
+ if (!_iterator_has_next (self))
+ {
+ return FALSE;
+ }
+ if (_iterator_flag (self, ITER_STARTED))
+ {
+ /* back onto track, even if an item was removed */
+ self->flags &= ~ITER_REMOVED;
+ self->i++;
+ }
+ else
+ {
+ self->flags = ITER_STARTED;
+ self->i = 0;
+ }
+
+ g_assert (_iterator_is_valid (self));
+ return TRUE;
+}
+
+static gboolean
+folks_small_set_iterator_has_next (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+ return _iterator_has_next (self);
+}
+
+static gpointer
+folks_small_set_iterator_get (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_val_if_fail (self != NULL, NULL);
+ g_return_val_if_fail (_iterator_flag (self, ITER_STARTED), NULL);
+ g_return_val_if_fail (!_iterator_flag (self, ITER_REMOVED), NULL);
+
+ return _iterator_dup (self);
+}
+
+static void
+folks_small_set_iterator_remove (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_if_fail (self != NULL);
+ g_return_if_fail ((self->set->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) == 0);
+ g_return_if_fail (_iterator_flag (self, ITER_STARTED));
+ g_return_if_fail (!_iterator_flag (self, ITER_REMOVED));
+
+ /* Suppose self->i == 5, i.e. we are pointing at pdata[5] in a list
+ * of length 10. */
+
+ /* Move pdata[9] to overwrite pdata[5] */
+ g_ptr_array_remove_index_fast (self->set->items, self->i);
+
+ /* Next time we advance the iterator, we want it to move to pdata[5];
+ * so we need to move back one. i is unsigned, so it's OK if it underflows
+ * to all-ones - ISO C guarantees that unsigned arithmetic wraps around. */
+ self->i--;
+
+ /* We're not allowed to get() until we're back on track, though. */
+ self->flags |= ITER_REMOVED;
+}
+
+static gboolean
+folks_small_set_iterator_get_valid (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_val_if_fail (self != NULL, FALSE);
+
+ return _iterator_is_valid (self);
+}
+
+static gboolean
+folks_small_set_iterator_get_read_only (GeeIterator *iter)
+{
+ FolksSmallSetIterator *self = FOLKS_SMALL_SET_ITERATOR (iter);
+
+ g_return_val_if_fail (self != NULL, TRUE);
+
+ return ((self->set->flags & FOLKS_SMALL_SET_FLAG_READ_ONLY) != 0);
+}
+
+/* unfold, concat are inherited */
+
+static void
+iterator_iface_init (GeeIteratorIface *iface)
+{
+ iface->next = folks_small_set_iterator_next;
+ iface->has_next = folks_small_set_iterator_has_next;
+ iface->get = folks_small_set_iterator_get;
+ iface->remove = folks_small_set_iterator_remove;
+ iface->get_valid = folks_small_set_iterator_get_valid;
+ iface->get_read_only = folks_small_set_iterator_get_read_only;
+}
diff --git a/folks/small-set.h b/folks/small-set.h
new file mode 100644
index 0000000..1b2760d
--- /dev/null
+++ b/folks/small-set.h
@@ -0,0 +1,73 @@
+/*
+ * small-set - a set optimized for fast iteration when there are few items
+ *
+ * Copyright © 2013 Intel Corporation
+ *
+ * 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
+ *
+ * Authors:
+ * Simon McVittie <simon mcvittie collabora co uk>
+ */
+
+#ifndef FOLKS_SMALL_SET_H
+#define FOLKS_SMALL_SET_H
+
+#include <glib.h>
+#include <glib-object.h>
+#include <gee.h>
+
+G_BEGIN_DECLS
+
+typedef struct _FolksSmallSet FolksSmallSet;
+typedef struct _FolksSmallSetClass FolksSmallSetClass;
+
+GType folks_small_set_get_type (void);
+
+#define FOLKS_TYPE_SMALL_SET \
+ (folks_small_set_get_type ())
+#define FOLKS_SMALL_SET(obj) \
+ (G_TYPE_CHECK_INSTANCE_CAST ((obj), FOLKS_TYPE_SMALL_SET, \
+ FolksSmallSet))
+#define FOLKS_SMALL_SET_CLASS(klass) \
+ (G_TYPE_CHECK_CLASS_CAST ((klass), FOLKS_TYPE_SMALL_SET, \
+ FolksSmallSetClass))
+#define FOLKS_IS_SMALL_SET(obj) \
+ (G_TYPE_CHECK_INSTANCE_TYPE ((obj), FOLKS_TYPE_SMALL_SET))
+#define FOLKS_IS_SMALL_SET_CLASS(klass) \
+ (G_TYPE_CHECK_CLASS_TYPE ((klass), FOLKS_TYPE_SMALL_SET))
+#define FOLKS_SMALL_SET_GET_CLASS(obj) \
+ (G_TYPE_INSTANCE_GET_CLASS ((obj), FOLKS_TYPE_SMALL_SET, \
+ FolksSmallSetClass))
+
+FolksSmallSet *
+folks_small_set_new (GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free,
+ GeeHashDataFunc item_hash,
+ gpointer item_hash_data,
+ GDestroyNotify item_hash_data_free,
+ GeeEqualDataFunc item_equals,
+ gpointer item_equals_data,
+ GDestroyNotify item_equals_data_free);
+
+FolksSmallSet *
+folks_small_set_empty (GType item_type,
+ GBoxedCopyFunc item_dup,
+ GDestroyNotify item_free);
+
+G_END_DECLS
+
+#endif
diff --git a/tests/folks/Makefile.am b/tests/folks/Makefile.am
index f0c517e..ab09944 100644
--- a/tests/folks/Makefile.am
+++ b/tests/folks/Makefile.am
@@ -44,6 +44,7 @@ AM_VALAFLAGS += \
--pkg gio-2.0 \
--pkg gee-0.8 \
--pkg folks \
+ --pkg folks-generics \
--pkg folks-test \
--pkg kf-test \
--pkg tpf-test \
@@ -53,6 +54,7 @@ AM_VALAFLAGS += \
# in order from least to most complex
noinst_PROGRAMS = \
+ small-set \
abstract-field-details \
async-locking \
utils \
@@ -101,6 +103,10 @@ init_SOURCES = \
init.vala \
$(NULL)
+small_set_SOURCES = \
+ small-set.vala \
+ $(NULL)
+
CLEANFILES = \
*.pid \
*.address \
@@ -117,6 +123,7 @@ MAINTAINERCLEANFILES = \
avatar_cache_vala.stamp \
object_cache_vala.stamp \
init_vala.stamp \
+ small_set_vala.stamp \
$(NULL)
EXTRA_DIST = \
diff --git a/tests/folks/small-set.vala b/tests/folks/small-set.vala
new file mode 100644
index 0000000..c2d2e2b
--- /dev/null
+++ b/tests/folks/small-set.vala
@@ -0,0 +1,421 @@
+/*
+ * Copyright © 2013 Intel Corporation
+ *
+ * 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, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors:
+ * Simon McVittie <simon mcvittie collabora co uk>
+ */
+
+using Gee;
+using Folks;
+
+/* An object with no equality pseudo-operator. */
+public class DirectEq : Object
+{
+ public uint u;
+
+ public DirectEq (uint u)
+ {
+ this.u = u;
+ }
+}
+
+/* An object with an equality pseudo-operator. */
+public class UInt : Object
+{
+ public uint u;
+
+ public UInt (uint u)
+ {
+ this.u = u;
+ }
+
+ public static uint hash_static (UInt that)
+ {
+ return that.u;
+ }
+
+ public static bool equals_static (UInt left, UInt right)
+ {
+ return left.u == right.u;
+ }
+}
+
+public class SmallSetTests : Folks.TestCase
+{
+ public SmallSetTests ()
+ {
+ base ("SmallSet");
+ this.add_test ("objects_hash", () => this.test_objects (true));
+ this.add_test ("objects", () => this.test_objects (false));
+ this.add_test ("iter_hash", () => this.test_iter (true));
+ this.add_test ("iter", () => this.test_iter (false));
+ this.add_test ("readonly_hash", () => this.test_readonly (true));
+ this.add_test ("readonly", () => this.test_readonly (false));
+ this.add_test ("direct_hash", () => this.test_direct (true));
+ this.add_test ("direct", () => this.test_direct (false));
+ this.add_test ("string_hash", () => this.test_strings (true));
+ this.add_test ("string", () => this.test_strings (false));
+ }
+
+ public void test_objects (bool use_hash)
+ {
+ var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
+ var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
+
+ Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
+
+ assert (objects != null);
+ assert (!objects.read_only);
+ assert (objects.size == 0);
+ assert (objects.is_empty);
+
+ objects.add (new UInt (10000));
+ objects.add (new UInt (1));
+ objects.add (new UInt (10));
+ objects.add (new UInt (100));
+ objects.add (new UInt (1000));
+
+ assert (objects != null);
+ assert (!objects.read_only);
+ assert (!objects.is_empty);
+ assert (objects.size == 5);
+
+ uint sum = 0;
+ bool res = objects.foreach ((obj) =>
+ {
+ sum += obj.u;
+ return true;
+ });
+
+ /* FIXME: this used to be wrong in HashSet (GNOME #696710).
+ * Do this unconditionally when we depend on a Gee with that fixed */
+ if (!use_hash)
+ assert (res == true);
+
+ assert (sum == 11111);
+
+ sum = 0;
+ res = objects.foreach ((obj) =>
+ {
+ sum += obj.u;
+ return false;
+ });
+ assert (res == false);
+ assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 ||
+ sum == 10000);
+
+ var ten = new UInt (10);
+
+ objects.foreach ((obj) =>
+ {
+ /* It is not the same object as the one in the set... */
+ assert (ten != obj);
+ return true;
+ });
+
+ /* ... but it is equal, and that'll do */
+ assert (objects.contains (ten));
+ /* Vala syntactic sugar */
+ assert (ten in objects);
+ /* It's a set. Attempts to add a duplicate are ignored. */
+ res = objects.add (ten);
+ assert (res == false);
+ assert (objects.size == 5);
+ objects.foreach ((obj) =>
+ {
+ assert (ten != obj);
+ return true;
+ });
+
+ objects.remove (ten);
+
+ /* Vala syntactic sugar: behind the scenes, this uses an iterator */
+ sum = 0;
+ foreach (var obj in objects)
+ sum += obj.u;
+ assert (sum == 11101);
+
+ /* Put it back. */
+ res = objects.add (ten);
+ assert (res == true);
+
+ sum = 0;
+ foreach (var obj in objects)
+ sum += obj.u;
+ assert (sum == 11111);
+
+ objects.clear ();
+ assert (objects.size == 0);
+ assert (objects.is_empty);
+ foreach (var obj in objects)
+ assert_not_reached ();
+ }
+
+ public void test_iter (bool use_hash)
+ {
+ var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
+ var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
+
+ Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
+
+ var iter = objects.iterator (); /* points before 0 - invalid */
+ assert (!iter.valid);
+ assert (!iter.read_only);
+ assert (!iter.has_next ());
+ bool res = iter.next (); /* fails, remains pointing before 0 */
+ assert (!res);
+ assert (!iter.valid);
+ assert (!iter.has_next ());
+
+ objects.add (new UInt (1));
+ objects.add (new UInt (10));
+ objects.add (new UInt (100));
+ objects.add (new UInt (1000));
+ objects.add (new UInt (10000));
+ assert (objects.size == 5);
+
+ iter = objects.iterator (); /* points before 0 - invalid */
+
+ assert (!iter.valid);
+ assert (!iter.read_only);
+
+ assert (iter.has_next ());
+ res = iter.next (); /* points to 0 */
+ assert (res);
+ assert (iter.valid);
+ assert (iter.has_next ());
+
+ iter.next (); /* points to 1 */
+ iter.next (); /* points to 2 */
+ iter.next (); /* points to 3 */
+ assert (iter.valid);
+ assert (iter.has_next ());
+ iter.next (); /* points to 4 */
+ assert (iter.valid);
+ assert (!iter.has_next ());
+ res = iter.next (); /* fails, remains pointing to 4 */
+ assert (!res);
+ assert (iter.valid); /* still valid */
+ assert (!iter.has_next ());
+
+ iter = objects.iterator ();
+ uint sum = 0;
+ /* If the iterator has not been started then iter.foreach starts from
+ * the beginning, skipping any prior items. */
+ iter.foreach ((obj) =>
+ {
+ sum += obj.u;
+ return true;
+ });
+ assert (sum == 11111);
+
+ sum = 0;
+ iter = objects.iterator ();
+ res = iter.foreach ((obj) =>
+ {
+ sum += obj.u;
+ return false;
+ });
+ assert (res == false);
+ assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 ||
+ sum == 10000);
+
+ sum = 0;
+ iter = objects.iterator ();
+ iter.next ();
+ sum += iter.get ().u;
+ iter.next ();
+ sum += iter.get ().u;
+ iter.next ();
+ /* If iter.valid then iter.foreach starts from the current item,
+ * skipping any prior items. We already added the ones we expect to
+ * have skipped. */
+ iter.foreach ((obj) =>
+ {
+ sum += obj.u;
+ return true;
+ });
+ assert (sum == 11111);
+
+ sum = 0;
+ iter = objects.iterator ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ iter.foreach ((obj) =>
+ {
+ /* only run for the current == last item */
+ sum += 1;
+ return true;
+ });
+ assert (sum == 1);
+
+ /* Remove the first element. */
+ sum = 0;
+ iter = objects.iterator ();
+ iter.next ();
+ assert (iter.valid);
+ var removed = iter.get ();
+ iter.remove ();
+ sum += removed.u;
+ assert (!iter.valid);
+ while (iter.next ())
+ sum += iter.get ().u;
+ assert (sum == 11111);
+ /* Put it back. */
+ objects.add (removed);
+
+ /* Remove a middle element. */
+ sum = 0;
+ iter = objects.iterator ();
+ iter.next ();
+ sum += iter.get ().u;
+ iter.next ();
+ sum += iter.get ().u;
+ iter.next ();
+ assert (iter.valid);
+ removed = iter.get ();
+ iter.remove ();
+ sum += removed.u;
+ assert (!iter.valid);
+ while (iter.next ())
+ sum += iter.get ().u;
+ assert (sum == 11111);
+ /* Put it back. */
+ objects.add (removed);
+
+ /* Remove the last element. */
+ sum = 0;
+ iter = objects.iterator ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ iter.next ();
+ assert (iter.valid);
+ assert (!iter.has_next ());
+ removed = iter.get ();
+ iter.remove ();
+ sum += removed.u;
+ assert (!iter.valid);
+ assert (!iter.has_next ());
+ foreach (var obj in objects)
+ sum += obj.u;
+ assert (sum == 11111);
+ /* Put it back. */
+ objects.add (removed);
+ }
+
+ public void test_readonly (bool use_hash)
+ {
+ var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
+ var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
+
+ Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
+
+ var ro = objects.read_only_view;
+ assert (ro != null);
+ assert (ro != objects);
+ assert (ro.read_only);
+ assert (ro.size == 0);
+
+ objects.add (new UInt (23));
+ assert (objects.size == 1);
+ assert (ro.size == 1);
+
+ uint u = 0;
+ ro.foreach ((obj) =>
+ {
+ assert (u == 0);
+ u = obj.u;
+ return true;
+ });
+ assert (u == 23);
+
+ var iter = ro.iterator ();
+ assert (iter.read_only);
+ u = 0;
+ iter.foreach ((obj) =>
+ {
+ assert (u == 0);
+ u = obj.u;
+ return true;
+ });
+ assert (u == 23);
+
+ /* These are implementation details */
+ if (!use_hash)
+ {
+ /* A new read-only view of an object is not the same thing yet */
+ var ro2 = objects.read_only_view;
+ assert (ro != ro2);
+
+ /* The read-only view of a read-only view is itself */
+ ro2 = ro.read_only_view;
+ assert (ro == ro2);
+ }
+ }
+
+ public void test_direct (bool use_hash)
+ {
+ var small = new SmallSet<DirectEq> ();
+ var hash = new HashSet<DirectEq> ();
+
+ Set<DirectEq> objects = (use_hash ?
+ hash as Set<DirectEq> : small as Set<DirectEq>);
+
+ objects.add (new DirectEq (23));
+ objects.add (new DirectEq (23));
+ var fortytwo = new DirectEq (42);
+ objects.add (fortytwo);
+ objects.add (fortytwo);
+ assert (objects.size == 3);
+
+ uint sum = 0;
+ foreach (var obj in objects)
+ sum += obj.u;
+ assert (sum == 23 + 23 + 42);
+ }
+
+ public void test_strings (bool use_hash)
+ {
+ var small = new SmallSet<string> ();
+ var hash = new HashSet<string> ((Gee.HashDataFunc) str_hash,
+ (Gee.EqualDataFunc) str_equal);
+
+ Set<string> strings = (use_hash ?
+ hash as Set<string> : small as Set<string>);
+
+ strings.add ("cheese");
+ strings.add ("cheese");
+ strings.add ("ham");
+ assert (strings.size == 2);
+ }
+}
+
+public int main (string[] args)
+{
+ Test.init (ref args);
+
+ var tests = new SmallSetTests ();
+ tests.register ();
+ Test.run ();
+ tests.final_tear_down ();
+
+ return 0;
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
