r3926 - in trunk: . sfi sfi/tests
- From: timj svn gnome org
- To: svn-commits-list gnome org
- Subject: r3926 - in trunk: . sfi sfi/tests
- Date: Tue, 3 Oct 2006 11:29:16 -0400 (EDT)
Author: timj
Date: 2006-10-03 11:28:27 -0400 (Tue, 03 Oct 2006)
New Revision: 3926
Added:
trunk/sfi/sfiring.c
trunk/sfi/sfiring.h
trunk/sfi/tests/
trunk/sfi/tests/Makefile.am
trunk/sfi/tests/dummy.cc
trunk/sfi/tests/ring.c
Modified:
trunk/configure.in
trunk/sfi/ChangeLog
trunk/sfi/Makefile.am
trunk/sfi/sfi.h
trunk/sfi/sficomport.h
trunk/sfi/sficomwire.h
trunk/sfi/sfifilecrawler.h
trunk/sfi/sfiglue.h
trunk/sfi/sfiprimitives.c
trunk/sfi/sfiprimitives.h
trunk/sfi/sfistore.h
trunk/sfi/sfitime.c
trunk/sfi/sfitypes.h
Log:
Tue Oct 3 17:21:08 2006 Tim Janik <timj gtk org>
* sfiring.h, sfiring.c: moved BirnetRing here, renamed to Sfi.
* sfiprimitives.h, sfiprimitives.c: removed obsolete Ring code.
* tests/ring.c: test SfiRing thoroughly.
moved here from birnet/tests/ring.cc, renamed to use SfiRing.
* tests/Makefile.am:
* Makefile.am: build and integrate sfi/tests/.
Modified: trunk/configure.in
===================================================================
--- trunk/configure.in 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/configure.in 2006-10-03 15:28:27 UTC (rev 3926)
@@ -597,6 +597,7 @@
birnet/Makefile
birnet/tests/Makefile
sfi/Makefile
+sfi/tests/Makefile
bse/bseconfig.h
bse/Makefile
bse/icons/Makefile
Modified: trunk/sfi/ChangeLog
===================================================================
--- trunk/sfi/ChangeLog 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/ChangeLog 2006-10-03 15:28:27 UTC (rev 3926)
@@ -1,3 +1,15 @@
+Tue Oct 3 17:21:08 2006 Tim Janik <timj gtk org>
+
+ * sfiring.h, sfiring.c: moved BirnetRing here, renamed to Sfi.
+
+ * sfiprimitives.h, sfiprimitives.c: removed obsolete Ring code.
+
+ * tests/ring.c: test SfiRing thoroughly.
+ moved here from birnet/tests/ring.cc, renamed to use SfiRing.
+
+ * tests/Makefile.am:
+ * Makefile.am: build and integrate sfi/tests/.
+
Fri Jul 7 02:10:42 2006 Tim Janik <timj gtk org>
* sfifilecrawler.[hc]: removed sfi_file_check() and sfi_file_equals()
Modified: trunk/sfi/Makefile.am
===================================================================
--- trunk/sfi/Makefile.am 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/Makefile.am 2006-10-03 15:28:27 UTC (rev 3926)
@@ -4,6 +4,7 @@
## GNU Lesser General Public License version 2 or any later version.
include $(top_srcdir)/Makefile.decl
+SUBDIRS = . tests
INCLUDES += -I$(top_srcdir) -I$(top_builddir) $(SFI_CFLAGS)
DEFS += -DG_LOG_DOMAIN=\"SFI\" -DG_DISABLE_CONST_RETURNS
@@ -13,7 +14,7 @@
sfivmarshal.h sfiglue.h sfigluecodec.h sfiglueproxy.h \
sfinote.h sfiparams.h sfiprimitives.h sfiserial.h \
sfitime.h sfitypes.h sfivalues.h sfiustore.h \
- sficxx.hh sfimemory.h sficomport.h \
+ sficxx.hh sfiring.h sfimemory.h sficomport.h \
sfi.h \
)
sfi_all_sources = $(strip \
@@ -22,7 +23,7 @@
sfivmarshal.c sfiglue.c sfigluecodec.c sfiglueproxy.c \
sfinote.c sfiparams.c sfiprimitives.c sfiserial.c \
sfitime.c sfitypes.c sfivalues.c sfiustore.c \
- sficxx.cc sfimemory.c sficomport.c \
+ sficxx.cc sfiring.c sfimemory.c sficomport.c \
$(conditional_toyprof_sources) \
)
sfi_extra_sources = $(strip \
Modified: trunk/sfi/sfi.h
===================================================================
--- trunk/sfi/sfi.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfi.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -29,6 +29,7 @@
#include <sfi/sfinote.h>
#include <sfi/sfiparams.h>
#include <sfi/sfiprimitives.h>
+#include <sfi/sfiring.h>
/* #include <sfi/sfisclock.h> */
#include <sfi/sfiserial.h>
/* no bin-compat: #include <sfi/sfistore.h> */
Modified: trunk/sfi/sficomport.h
===================================================================
--- trunk/sfi/sficomport.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sficomport.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -20,6 +20,7 @@
#define __SFI_COM_PORT_H__
#include <sfi/sfitypes.h>
+#include <sfi/sfiring.h>
G_BEGIN_DECLS
Modified: trunk/sfi/sficomwire.h
===================================================================
--- trunk/sfi/sficomwire.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sficomwire.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -20,6 +20,7 @@
#define __SFI_COM_WIRE_H__
#include <sfi/sfitypes.h>
+#include <sfi/sfiring.h>
#ifdef __cplusplus
extern "C" {
Modified: trunk/sfi/sfifilecrawler.h
===================================================================
--- trunk/sfi/sfifilecrawler.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfifilecrawler.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -20,6 +20,7 @@
#define __SFI_FILE_CRAWLER_H__
#include <sfi/sfitypes.h>
+#include <sfi/sfiring.h>
G_BEGIN_DECLS
Modified: trunk/sfi/sfiglue.h
===================================================================
--- trunk/sfi/sfiglue.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfiglue.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -20,6 +20,7 @@
#define __SFI_GLUE_H__
#include <sfi/sfiprimitives.h>
+#include <sfi/sfiring.h>
#include <sfi/sfiparams.h>
G_BEGIN_DECLS
Modified: trunk/sfi/sfiprimitives.c
===================================================================
--- trunk/sfi/sfiprimitives.c 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfiprimitives.c 2006-10-03 15:28:27 UTC (rev 3926)
@@ -1311,996 +1311,3 @@
return sfi_value_get_proxy (v);
return 0;
}
-
-
-/* --- basic comparisons --- */
-gint
-sfi_pointer_cmp (gconstpointer value1,
- gconstpointer value2,
- gpointer dummy)
-{
- const char *p1 = value1;
- const char *p2 = value2;
- return p1 < p2 ? -1 : p1 != p2;
-}
-
-
-/* --- ring (circular-list) --- */
-static inline SfiRing*
-sfi_ring_prepend_link_i (SfiRing *head,
- SfiRing *ring)
-{
- if (!head)
- {
- ring->prev = ring;
- ring->next = ring;
- }
- else
- {
- ring->prev = head->prev;
- ring->next = head;
- head->prev->next = ring;
- head->prev = ring;
- }
- return ring;
-}
-
-static inline SfiRing*
-sfi_ring_prepend_i (SfiRing *head,
- gpointer data)
-{
- SfiRing *ring = sfi_new_struct (SfiRing, 1);
-
- ring->data = data;
- return sfi_ring_prepend_link_i (head, ring);
-}
-
-static inline SfiRing*
-sfi_ring_append_link_i (SfiRing *head,
- SfiRing *ring)
-{
- sfi_ring_prepend_link_i (head, ring);
- return head ? head : ring;
-}
-
-SfiRing*
-sfi_ring_prepend (SfiRing *head,
- gpointer data)
-{
- return sfi_ring_prepend_i (head, data);
-}
-
-SfiRing*
-sfi_ring_prepend_uniq (SfiRing *head,
- gpointer data)
-{
- SfiRing *ring;
- for (ring = head; ring; ring = sfi_ring_walk (ring, head))
- if (ring->data == data)
- return head;
- return sfi_ring_prepend_i (head, data);
-}
-
-SfiRing*
-sfi_ring_append (SfiRing *head,
- gpointer data)
-{
- SfiRing *ring = sfi_ring_prepend_i (head, data);
- return head ? head : ring;
-}
-
-SfiRing*
-sfi_ring_append_uniq (SfiRing *head,
- gpointer data)
-{
- SfiRing *ring;
- for (ring = head; ring; ring = sfi_ring_walk (ring, head))
- if (ring->data == data)
- return head;
- ring = sfi_ring_prepend_i (head, data);
- return head ? head : ring;
-}
-
-SfiRing*
-sfi_ring_insert_before (SfiRing *head,
- SfiRing *sibling,
- gpointer data)
-{
- if (!sibling)
- return sfi_ring_append (head, data);
- SfiRing *node = sfi_ring_prepend (sibling, data);
- return sibling == head ? node : head;
-}
-
-SfiRing*
-sfi_ring_insert (SfiRing *head,
- gpointer data,
- gint position)
-{
- if (position < 0)
- return sfi_ring_append (head, data);
- else if (position == 0)
- return sfi_ring_prepend (head, data);
- SfiRing *node = sfi_ring_nth (head, position);
- if (node)
- return sfi_ring_insert_before (head, node, data);
- else
- return sfi_ring_append (head, data);
-}
-
-gint
-sfi_ring_position (const SfiRing *head,
- const SfiRing *node)
-{
- guint i = 0;
- const SfiRing *ring;
- for (ring = head; ring; ring = sfi_ring_walk (ring, head), i++)
- if (ring == node)
- return i;
- return -1;
-}
-
-gint
-sfi_ring_index (const SfiRing *head,
- gconstpointer data)
-{
- guint i = 0;
- const SfiRing *ring;
- for (ring = head; ring; ring = sfi_ring_walk (ring, head), i++)
- if (ring->data == data)
- return i;
- return -1;
-}
-
-SfiRing*
-sfi_ring_copy (const SfiRing *head)
-{
- const SfiRing *walk;
- SfiRing *dest = NULL;
- for (walk = head; walk; walk = sfi_ring_walk (walk, head))
- dest = sfi_ring_append (dest, walk->data);
- return dest;
-}
-
-SfiRing*
-sfi_ring_copy_deep (const SfiRing *head,
- SfiRingDataFunc copy,
- gpointer func_data)
-{
- const SfiRing *walk;
- SfiRing *dest = NULL;
- for (walk = head; walk; walk = sfi_ring_walk (walk, head))
- dest = sfi_ring_append (dest, copy (walk->data, func_data));
- return dest;
-}
-
-SfiRing*
-sfi_ring_copy_rest (const SfiRing *ring,
- const SfiRing *head)
-{
- const SfiRing *walk;
- SfiRing *dest = NULL;
- for (walk = ring; walk; walk = sfi_ring_walk (walk, head))
- dest = sfi_ring_append (dest, walk->data);
- return dest;
-}
-
-SfiRing*
-sfi_ring_concat (SfiRing *head1,
- SfiRing *head2)
-{
- SfiRing *tail1, *tail2;
-
- if (!head1)
- return head2;
- if (!head2)
- return head1;
- tail1 = head1->prev;
- tail2 = head2->prev;
- head1->prev = tail2;
- tail2->next = head1;
- head2->prev = tail1;
- tail1->next = head2;
-
- return head1;
-}
-
-/**
- * @param head1 a non-empty ring
- * @param head2 a ring node different from @a head1 contained in @a head1
- * @param returns @a head2 for convenience
- *
- * Split a ring into two parts, starting the second ring with @a head2.
- * @a head2 must therefore be non-NULL and must be contained in the ring
- * formed by @a head1.
- */
-SfiRing*
-sfi_ring_split (SfiRing *head1,
- SfiRing *head2)
-{
- SfiRing *tail1, *tail2;
-
- g_return_val_if_fail (head1 != NULL, NULL);
- g_return_val_if_fail (head2 != NULL, NULL);
- g_return_val_if_fail (head1 != head2, NULL);
-
- tail1 = head2->prev;
- tail2 = head1->prev;
- head2->prev = tail2;
- tail2->next = head2;
- head1->prev = tail1;
- tail1->next = head1;
- return head2;
-}
-
-static inline SfiRing*
-sfi_ring_unlink_node_dangling (SfiRing *head,
- SfiRing *node)
-{
- g_assert (head && node);
- /* special case one item ring */
- if (head->prev == head)
- return NULL;
- /* unlink */
- node->next->prev = node->prev;
- node->prev->next = node->next;
- if (head == node)
- head = node->next;
- /* node->prev and node->next are dangling now */
- return head;
-}
-
-SfiRing*
-sfi_ring_remove_node (SfiRing *head,
- SfiRing *node)
-{
- if (!head)
- g_return_val_if_fail (head == NULL && node == NULL, NULL);
- if (!head || !node)
- return NULL;
-
- /* special case one item ring */
- if (head->prev == head)
- {
- g_return_val_if_fail (node == head, head);
-
- sfi_delete_struct (SfiRing, node);
- return NULL;
- }
- g_return_val_if_fail (node != node->next, head); /* node can't be a one item ring here */
-
- node->next->prev = node->prev;
- node->prev->next = node->next;
- if (head == node)
- head = node->next;
- sfi_delete_struct (SfiRing, node);
-
- return head;
-}
-
-SfiRing*
-sfi_ring_reverse (SfiRing *head)
-{
- if (head)
- {
- SfiRing *ring = head = head->prev;
- do
- {
- SfiRing *tmp = ring;
- ring = tmp->next;
- tmp->next = tmp->prev;
- tmp->prev = ring;
- }
- while (ring != head);
- }
- return head;
-}
-
-SfiRing*
-sfi_ring_remove (SfiRing *head,
- gpointer data)
-{
- SfiRing *walk;
-
- if (!head)
- return NULL;
-
- /* make tail data removal an O(1) operation */
- if (head->prev->data == data)
- return sfi_ring_remove_node (head, head->prev);
-
- for (walk = head; walk; walk = sfi_ring_walk (walk, head))
- if (walk->data == data)
- return sfi_ring_remove_node (head, walk);
-
- /* g_warning (G_STRLOC ": couldn't find data item (%p) to remove from ring (%p)", data, head); */
-
- return head;
-}
-
-guint
-sfi_ring_length (const SfiRing *head)
-{
- const SfiRing *ring;
- guint i = 0;
-
- for (ring = head; ring; ring = sfi_ring_walk (ring, head))
- i++;
-
- return i;
-}
-
-gint /* essentially compute length(ring) - test_length, clamped to -1..+1 */
-sfi_ring_cmp_length (const SfiRing *head,
- guint test_length)
-{
- const SfiRing *ring = head;
-
- while (test_length && ring)
- {
- test_length--;
- ring = sfi_ring_walk (ring, head);
- }
-
- return test_length > 0 ? -1 : ring != NULL;
-}
-
-SfiRing*
-sfi_ring_find (const SfiRing*head,
- gconstpointer data)
-{
- const SfiRing *ring;
- for (ring = head; ring; ring = sfi_ring_walk (ring, head))
- if (ring->data == (gpointer) data)
- return (SfiRing*) ring;
- return NULL;
-}
-
-SfiRing*
-sfi_ring_nth (const SfiRing *head,
- guint n)
-{
- const SfiRing *ring = head;
- while (n-- && ring)
- ring = sfi_ring_walk (ring, head);
- return (SfiRing*) ring;
-}
-
-gpointer
-sfi_ring_nth_data (const SfiRing *head,
- guint n)
-{
- const SfiRing *ring = head;
-
- while (n-- && ring)
- ring = sfi_ring_walk (ring, head);
-
- return ring ? ring->data : NULL;
-}
-
-void
-sfi_ring_free_deep (SfiRing *head,
- GDestroyNotify data_destroy)
-{
- while (head)
- {
- gpointer data = sfi_ring_pop_head (&head);
- data_destroy (data);
- data = sfi_ring_pop_head (&head);
- }
-}
-
-void
-sfi_ring_free (SfiRing *head)
-{
- if (head)
- {
- head->prev->next = NULL;
- _sfi_free_node_list (head, sizeof (*head));
- }
-}
-
-gpointer
-sfi_ring_pop_head (SfiRing **head_p)
-{
- gpointer data;
-
- g_return_val_if_fail (head_p != NULL, NULL);
-
- if (!*head_p)
- return NULL;
- data = (*head_p)->data;
- *head_p = sfi_ring_remove_node (*head_p, *head_p);
-
- return data;
-}
-
-gpointer
-sfi_ring_pop_tail (SfiRing **head_p)
-{
- gpointer data;
-
- g_return_val_if_fail (head_p != NULL, NULL);
-
- if (!*head_p)
- return NULL;
- data = (*head_p)->prev->data;
- *head_p = sfi_ring_remove_node (*head_p, (*head_p)->prev);
-
- return data;
-}
-
-SfiRing*
-sfi_ring_from_list (GList *list)
-{
- SfiRing *ring = NULL;
- for (; list; list = list->next)
- ring = sfi_ring_append (ring, list->data);
- return ring;
-}
-
-SfiRing*
-sfi_ring_from_list_and_free (GList *list)
-{
- SfiRing *ring = NULL;
- GList *free_list = list;
- for (; list; list = list->next)
- ring = sfi_ring_append (ring, list->data);
- g_list_free (free_list);
- return ring;
-}
-
-SfiRing*
-sfi_ring_from_slist (GSList *slist)
-{
- SfiRing *ring = NULL;
- for (; slist; slist = slist->next)
- ring = sfi_ring_append (ring, slist->data);
- return ring;
-}
-
-SfiRing*
-sfi_ring_from_slist_and_free (GSList *slist)
-{
- SfiRing *ring = NULL;
- GSList *free_slist = slist;
- for (; slist; slist = slist->next)
- ring = sfi_ring_append (ring, slist->data);
- g_slist_free (free_slist);
- return ring;
-}
-
-SfiRing*
-sfi_ring_insert_sorted (SfiRing *head,
- gpointer insertion_data,
- SfiCompareFunc cmp,
- gpointer cmp_data)
-{
- g_return_val_if_fail (cmp != NULL, head);
- if (!head)
- return sfi_ring_prepend (head, insertion_data);
-
- /* implement stable sorting by inserting insertion_data *after* equal nodes */
-
- if (cmp (insertion_data, head->data, cmp_data) >= 0) /* insert after head */
- {
- SfiRing *tmp, *tail = head->prev;
-
- /* make appending an O(1) operation */
- if (head == tail || cmp (insertion_data, tail->data, cmp_data) >= 0)
- return sfi_ring_append (head, insertion_data);
-
- /* walk forward while data >= tmp (skipping equal nodes) */
- for (tmp = head->next; tmp != tail; tmp = tmp->next)
- if (cmp (insertion_data, tmp->data, cmp_data) < 0)
- break;
-
- /* insert before sibling which is greater than insertion_data */
- sfi_ring_prepend (tmp, insertion_data); /* keep current head */
- return head;
- }
- else /* cmp < 0 */
- return sfi_ring_prepend (head, insertion_data);
-}
-
-SfiRing*
-sfi_ring_merge_sorted (SfiRing *head1,
- SfiRing *head2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- /* implement stable sorting by inserting head2 members *after* equal nodes from head1 */
-
- if (head1 && head2)
- {
- SfiRing *tail1 = head1->prev;
- SfiRing *tail2 = head2->prev;
- SfiRing *tmp, *ring = NULL;
- /* NULL terminate rings */
- tail1->next = NULL;
- tail2->next = NULL;
- while (head1 && head2)
- {
- gint c = cmp (head1->data, head2->data, data);
- if (c <= 0)
- {
- tmp = head1;
- head1 = head1->next;
- }
- else
- {
- tmp = head2;
- head2 = head2->next;
- }
- ring = sfi_ring_append_link_i (ring, tmp);
- }
- /* reform valid rings, concat sorted rest */
- if (head1)
- {
- tail1->next = head1;
- head1->prev = tail1;
- return sfi_ring_concat (ring, head1);
- }
- if (head2)
- {
- tail2->next = head2;
- head2->prev = tail2;
- return sfi_ring_concat (ring, head2);
- }
- return ring;
- }
- else
- return sfi_ring_concat (head1, head2);
-}
-
-SfiRing*
-sfi_ring_sort (SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data)
-{
- g_return_val_if_fail (cmp != NULL, head);
-
- /* stable sorting guaranteed by sfi_ring_merge_sorted() */
-
- if (head && head->next != head)
- {
- SfiRing *ring, *tmp, *tail = head->prev;
- /* find middle node to get log2 recursion depth */
- ring = tmp = head->next;
- while (tmp != tail && tmp->next != tail)
- {
- ring = ring->next;
- tmp = tmp->next->next;
- }
- sfi_ring_split (head, ring);
- return sfi_ring_merge_sorted (sfi_ring_sort (head, cmp, data),
- sfi_ring_sort (ring, cmp, data),
- cmp, data);
- }
- return head;
-}
-
-SfiRing* /* eliminates duplicate nodes */
-sfi_ring_uniq (SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data)
-{
- /* always preserves the first of a sublist of consequtive equal elements */
- SfiRing *r1 = sorted_ring1;
- SfiRing *r2 = NULL;
- if (r1)
- {
- SfiRing *last = r1;
- r1 = sfi_ring_unlink_node_dangling (r1, last);
- r2 = last->next = last->prev = last; /* form new ring */
- while (r1)
- {
- SfiRing *node = r1;
- r1 = sfi_ring_unlink_node_dangling (r1, node);
- if (cmp (last->data, node->data, data))
- {
- last = node;
- r2 = sfi_ring_append_link_i (r2, last);
- }
- else
- sfi_delete_struct (SfiRing, node);
- }
- }
- return r2;
-}
-
-SfiRing* /* eliminates duplicate nodes */
-sfi_ring_uniq_free_deep (SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data,
- GDestroyNotify data_destroy)
-{
- /* always preserves the first of a sublist of consequtive equal elements */
- if (!data_destroy)
- return sfi_ring_uniq (sorted_ring1, cmp, data);
- SfiRing *r1 = sorted_ring1;
- SfiRing *r2 = NULL;
- if (r1)
- {
- SfiRing *last = r1;
- r1 = sfi_ring_unlink_node_dangling (r1, last);
- r2 = last->next = last->prev = last; /* form new ring */
- while (r1)
- {
- SfiRing *node = r1;
- r1 = sfi_ring_unlink_node_dangling (r1, node);
- if (cmp (last->data, node->data, data))
- {
- last = node;
- r2 = sfi_ring_append_link_i (r2, last);
- }
- else
- {
- data_destroy (node->data);
- sfi_delete_struct (SfiRing, node);
- }
- }
- }
- return r2;
-}
-
-SfiRing* /* eliminates duplicate nodes */
-sfi_ring_copy_deep_uniq (const SfiRing *sorted_ring1,
- SfiRingDataFunc copy,
- gpointer copy_data,
- SfiCompareFunc cmp,
- gpointer cmp_data)
-{
- /* always preserves the first of a sublist of consequtive equal elements */
- if (!copy)
- return sfi_ring_copy_uniq (sorted_ring1, cmp, cmp_data);
- const SfiRing *r1 = sorted_ring1;
- SfiRing *r2 = NULL;
- if (r1)
- {
- gpointer last_data = r1->data;
- r2 = sfi_ring_append (r2, copy (last_data, copy_data));
- for (r1 = sfi_ring_walk (r1, sorted_ring1); r1; r1 = sfi_ring_walk (r1, sorted_ring1))
- if (cmp (last_data, r1->data, cmp_data))
- {
- last_data = r1->data;
- r2 = sfi_ring_append (r2, copy (last_data, copy_data));
- }
- }
- return r2;
-}
-
-SfiRing* /* eliminates duplicate nodes */
-sfi_ring_copy_uniq (const SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data)
-{
- /* always preserves the first of a sublist of consequtive equal elements */
- const SfiRing *r1 = sorted_ring1;
- SfiRing *r2 = NULL;
- if (r1)
- {
- gpointer last_data = r1->data;
- r2 = sfi_ring_append (r2, last_data);
- for (r1 = sfi_ring_walk (r1, sorted_ring1); r1; r1 = sfi_ring_walk (r1, sorted_ring1))
- if (cmp (last_data, r1->data, data))
- {
- last_data = r1->data;
- r2 = sfi_ring_append (r2, last_data);
- }
- }
- return r2;
-}
-
-SfiRing* /* merges rings without dups */
-sfi_ring_union (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- /* for two equal elements from both sets, the element from sorted_set1 is picked, the one from sorted_set2 discarded */
- const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
- SfiRing *d = NULL;
- while (r1 && r2)
- {
- gint c = cmp (r1->data, r2->data, data);
- if (c < 0)
- {
- d = sfi_ring_append (d, r1->data);
- r1 = sfi_ring_walk (r1, sorted_set1);
- }
- else if (c > 0)
- {
- d = sfi_ring_append (d, r2->data);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- else
- {
- d = sfi_ring_append (d, r1->data);
- r1 = sfi_ring_walk (r1, sorted_set1);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- }
- return sfi_ring_concat (d, sfi_ring_copy_rest (r1 ? r1 : r2, r1 ? sorted_set1 : sorted_set2));
-}
-
-SfiRing* /* returns nodes contained in both rings */
-sfi_ring_intersection (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- /* for two equal elements from both sets, only elements from sorted_set1 are picked */
- const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
- SfiRing *d = NULL;
- while (r1 && r2)
- {
- gint c = cmp (r1->data, r2->data, data);
- if (c < 0)
- r1 = sfi_ring_walk (r1, sorted_set1);
- else if (c > 0)
- r2 = sfi_ring_walk (r2, sorted_set2);
- else
- {
- d = sfi_ring_append (d, r1->data);
- r1 = sfi_ring_walk (r1, sorted_set1);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- }
- return d;
-}
-
-SfiRing* /* produces set1 without the elements of set2 */
-sfi_ring_difference (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
- SfiRing *d = NULL;
- while (r1 && r2)
- {
- gint c = cmp (r1->data, r2->data, data);
- if (c < 0)
- {
- d = sfi_ring_append (d, r1->data);
- r1 = sfi_ring_walk (r1, sorted_set1);
- }
- else if (c > 0)
- r2 = sfi_ring_walk (r2, sorted_set2);
- else
- {
- r1 = sfi_ring_walk (r1, sorted_set1);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- }
- return sfi_ring_concat (d, sfi_ring_copy_rest (r1, sorted_set1));
-}
-
-SfiRing* /* prduces difference (set1, set2) + difference (set2, set1) */
-sfi_ring_symmetric_difference (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
- SfiRing *d = NULL;
- while (r1 && r2)
- {
- gint c = cmp (r1->data, r2->data, data);
- if (c < 0)
- {
- d = sfi_ring_append (d, r1->data);
- r1 = sfi_ring_walk (r1, sorted_set1);
- }
- else if (c > 0)
- {
- d = sfi_ring_append (d, r2->data);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- else
- {
- r1 = sfi_ring_walk (r1, sorted_set1);
- r2 = sfi_ring_walk (r2, sorted_set2);
- }
- }
- return sfi_ring_concat (d, sfi_ring_copy_rest (r1 ? r1 : r2, r1 ? sorted_set1 : sorted_set2));
-}
-
-static inline int
-pointerloccmp (const void *pp1,
- const void *pp2)
-{
- const gpointer *p1 = pp1;
- const gpointer *p2 = pp2;
- return *p1 < *p2 ? -1 : *p1 != *p2;
-}
-
-static inline gboolean
-ring_reorder_lookup (guint n_items,
- gpointer *items,
- gpointer key,
- guint *indexp)
-{
- guint offset = 0, n = n_items;
- while (offset < n)
- {
- guint i = (offset + n) >> 1;
- gint cmp = key < items[i] ? -1 : key != items[i];
- if (cmp < 0)
- n = i;
- else if (cmp > 0)
- offset = i + 1;
- else /* match */
- {
- *indexp = i;
- return TRUE;
- }
- }
- return FALSE;
-}
-
-SfiRing* /* reproduce all elements from unordered_ring in the order new_ring_order */
-sfi_ring_reorder (SfiRing *unordered_ring,
- const SfiRing *new_ring_order)
-{
- if (!unordered_ring || !new_ring_order)
- return unordered_ring;
- const SfiRing *ring;
-
- /* construct a sorted array for faster lookups */
- gpointer *items = NULL;
- guint i, n_items = 0, n_alloced = 0;
- for (ring = unordered_ring; ring; ring = sfi_ring_walk (ring, unordered_ring))
- {
- i = n_items++;
- if (n_items > n_alloced)
- {
- n_alloced = sfi_alloc_upper_power2 (MAX (n_items, 32));
- items = g_renew (gpointer, items, n_alloced);
- }
- items[i] = ring->data;
- }
- sfi_ring_free (unordered_ring);
- unordered_ring = NULL;
- qsort (items, n_items, sizeof (items[0]), pointerloccmp);
-
- /* collapse duplicates */
- guint j = 0, *counts = g_new0 (guint, n_items);
- for (i = 0; i < n_items; i++)
- if (items[j] != items[i])
- {
- if (++j != i)
- items[j] = items[i];
- counts[j] = 1;
- }
- else /* catch dups */
- counts[j]++;
- n_items = j + 1; /* shrink to number of different items */
-
- /* pick unordered_ring members in the order given by new_ring_order */
- for (ring = new_ring_order; ring; ring = sfi_ring_walk (ring, new_ring_order))
- if (ring_reorder_lookup (n_items, items, ring->data, &i) && counts[i])
- {
- counts[i]--;
- unordered_ring = sfi_ring_append (unordered_ring, ring->data);
- }
-
- /* append left-over members from sorted_ring */
- for (i = 0; i < n_items; i++)
- while (counts[i]--)
- unordered_ring = sfi_ring_append (unordered_ring, items[i]);
-
- g_free (items);
- g_free (counts);
- return unordered_ring;
-}
-
-gboolean
-sfi_ring_includes (const SfiRing *sorted_super_set,
- const SfiRing *sorted_sub_set,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *r1 = sorted_super_set, *r2 = sorted_sub_set;
- while (r1 && r2)
- {
- gint c = cmp (r1->data, r2->data, data);
- if (c > 0)
- return FALSE;
- else if (c == 0)
- r2 = sfi_ring_walk (r2, sorted_sub_set);
- r1 = sfi_ring_walk (r1, sorted_super_set);
- }
- return !r2;
-}
-
-gboolean
-sfi_ring_equals (const SfiRing *sorted_ring1,
- const SfiRing *sorted_ring2,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *r1 = sorted_ring1, *r2 = sorted_ring2;
- while (r1 && r2)
- {
- if (cmp (r1->data, r2->data, data))
- return FALSE;
- r1 = sfi_ring_walk (r1, sorted_ring1);
- r2 = sfi_ring_walk (r2, sorted_ring2);
- }
- return r1 == r2; /* both need to be NULL */
-}
-
-gboolean
-sfi_ring_mismatch (SfiRing **sorted_ring1_p,
- SfiRing **sorted_ring2_p,
- SfiCompareFunc cmp,
- gpointer data)
-{
- SfiRing *head1 = *sorted_ring1_p, *head2 = *sorted_ring2_p;
- SfiRing *r1 = head1, *r2 = head2;
- while (r1 && r2)
- {
- if (cmp (r1->data, r2->data, data))
- goto mismatch;
- r1 = sfi_ring_walk (r1, head1);
- r2 = sfi_ring_walk (r2, head2);
- }
- if (r1 == r2) /* both are NULL */
- return FALSE;
- mismatch:
- *sorted_ring1_p = r1;
- *sorted_ring2_p = r2;
- return TRUE;
-}
-
-SfiRing*
-sfi_ring_min_node (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *ring = head, *last = NULL;
- if (ring)
- {
- last = ring;
- for (ring = sfi_ring_walk (ring, head); ring; ring = sfi_ring_walk (ring, head))
- if (cmp (last->data, ring->data, data) > 0)
- last = ring;
- }
- return (SfiRing*) last;
-}
-
-SfiRing*
-sfi_ring_max_node (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data)
-{
- const SfiRing *ring = head, *last = NULL;
- if (ring)
- {
- last = ring;
- for (ring = sfi_ring_walk (ring, head); ring; ring = sfi_ring_walk (ring, head))
- if (cmp (last->data, ring->data, data) < 0)
- last = ring;
- }
- return (SfiRing*) last;
-}
-
-gpointer
-sfi_ring_min (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data)
-{
- SfiRing *ring = sfi_ring_min_node (head, cmp, data);
- return ring ? ring->data : NULL;
-}
-
-gpointer
-sfi_ring_max (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data)
-{
- SfiRing *ring = sfi_ring_max_node (head, cmp, data);
- return ring ? ring->data : NULL;
-}
Modified: trunk/sfi/sfiprimitives.h
===================================================================
--- trunk/sfi/sfiprimitives.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfiprimitives.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -246,155 +246,6 @@
SfiProxy sfi_rec_get_proxy (SfiRec *rec,
const gchar *field_name);
-
-/* --- basic comparisons --- */
-typedef gint (*SfiCompareFunc) (gconstpointer value1,
- gconstpointer value2,
- gpointer data);
-gint sfi_pointer_cmp (gconstpointer value1,
- gconstpointer value2,
- gpointer dummy);
-
-
-/* --- ring (circular-list) --- */
-typedef gpointer (*SfiRingDataFunc) (gpointer data,
- gpointer func_data);
-struct _SfiRing // FIXME: move SfiRing into its own object file
-{
- gpointer data;
- SfiRing *next;
- SfiRing *prev;
-};
-SfiRing* sfi_ring_prepend (SfiRing *head,
- gpointer data);
-SfiRing* sfi_ring_prepend_uniq (SfiRing *head,
- gpointer data);
-SfiRing* sfi_ring_append (SfiRing *head,
- gpointer data);
-SfiRing* sfi_ring_append_uniq (SfiRing *head,
- gpointer data);
-SfiRing* sfi_ring_insert (SfiRing *head,
- gpointer data,
- gint position);
-SfiRing* sfi_ring_insert_before (SfiRing *head,
- SfiRing *sibling,
- gpointer data);
-gint sfi_ring_position (const SfiRing *head,
- const SfiRing *node);
-gint sfi_ring_index (const SfiRing *head,
- gconstpointer data);
-SfiRing* sfi_ring_nth (const SfiRing *head,
- guint n);
-gpointer sfi_ring_nth_data (const SfiRing *head,
- guint n);
-SfiRing* sfi_ring_find (const SfiRing *head,
- gconstpointer data);
-SfiRing* sfi_ring_remove_node (SfiRing *head,
- SfiRing *node);
-SfiRing* sfi_ring_remove (SfiRing *head,
- gpointer data);
-guint sfi_ring_length (const SfiRing *head);
-gint sfi_ring_cmp_length (const SfiRing *head,
- guint test_length);
-SfiRing* sfi_ring_copy (const SfiRing *head);
-SfiRing* sfi_ring_copy_deep (const SfiRing *head,
- SfiRingDataFunc copy,
- gpointer func_data);
-SfiRing* sfi_ring_copy_rest (const SfiRing *ring,
- const SfiRing *head);
-SfiRing* sfi_ring_concat (SfiRing *head1,
- SfiRing *head2);
-SfiRing* sfi_ring_split (SfiRing *head1,
- SfiRing *head2);
-SfiRing* sfi_ring_reverse (SfiRing *head);
-gpointer sfi_ring_pop_head (SfiRing **head);
-gpointer sfi_ring_pop_tail (SfiRing **head);
-#define sfi_ring_push_head sfi_ring_prepend
-#define sfi_ring_push_tail sfi_ring_append
-void sfi_ring_free (SfiRing *head);
-void sfi_ring_free_deep (SfiRing *head,
- GDestroyNotify data_destroy);
-#define sfi_ring_tail(head) ((head) ? (head)->prev : NULL)
-#define sfi_ring_walk(node,head_bound) ((node)->next != (head_bound) ? (node)->next : NULL)
-#define sfi_ring_next sfi_ring_walk
-
-SfiRing* sfi_ring_from_list (GList *list);
-SfiRing* sfi_ring_from_list_and_free (GList *list);
-SfiRing* sfi_ring_from_slist (GSList *slist);
-SfiRing* sfi_ring_from_slist_and_free (GSList *slist);
-
-/* ring-modifying cmp-based operations */
-SfiRing* sfi_ring_insert_sorted (SfiRing *head,
- gpointer insertion_data,
- SfiCompareFunc cmp,
- gpointer cmp_data);
-SfiRing* sfi_ring_merge_sorted (SfiRing *head1,
- SfiRing *head2,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_sort (SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_uniq (SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_uniq_free_deep (SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data,
- GDestroyNotify data_destroy);
-SfiRing* sfi_ring_reorder (SfiRing *unordered_ring,
- const SfiRing *new_ring_order);
-/* ring-copying cmp-based operations */
-SfiRing* sfi_ring_copy_deep_uniq (const SfiRing *sorted_ring1,
- SfiRingDataFunc copy,
- gpointer copy_data,
- SfiCompareFunc cmp,
- gpointer cmp_data);
-SfiRing* sfi_ring_copy_uniq (const SfiRing *sorted_ring1,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_union (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_intersection (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_difference (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_symmetric_difference (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data);
-/* const-result cmp-based operations */
-gboolean sfi_ring_includes (const SfiRing *sorted_super_set,
- const SfiRing *sorted_sub_set,
- SfiCompareFunc cmp,
- gpointer data);
-gboolean sfi_ring_mismatch (SfiRing **sorted_ring1_p,
- SfiRing **sorted_ring2_p,
- SfiCompareFunc cmp,
- gpointer data);
-gboolean sfi_ring_equals (const SfiRing *sorted_set1,
- const SfiRing *sorted_set2,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_min_node (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data);
-SfiRing* sfi_ring_max_node (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data);
-gpointer sfi_ring_min (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data);
-gpointer sfi_ring_max (const SfiRing *head,
- SfiCompareFunc cmp,
- gpointer data);
-
G_END_DECLS
#endif /* __SFI_PRIMITIVES_H__ */
Copied: trunk/sfi/sfiring.c (from rev 3925, trunk/birnet/birnetring.c)
===================================================================
--- trunk/birnet/birnetring.c 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfiring.c 2006-10-03 15:28:27 UTC (rev 3926)
@@ -0,0 +1,1175 @@
+/* SfiRing
+ * Copyright (C) 2002-2006 Tim Janik
+ *
+ * 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 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., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+#include "sfiring.h"
+#include "sfimemory.h"
+#include <stdlib.h>
+#include <string.h>
+
+#define HAVE_GSLICE GLIB_CHECK_VERSION (2, 9, 7)
+
+/* --- memory handling --- */
+static inline SfiRing*
+node_alloc (void)
+{
+#if HAVE_GSLICE
+ return g_slice_new (SfiRing);
+#else
+ return (SfiRing*) g_list_alloc();
+#endif
+}
+
+static inline void
+node_free (SfiRing *node)
+{
+#if HAVE_GSLICE
+ g_slice_free (SfiRing, node);
+#else
+ g_list_free_1 ((GList*) node);
+#endif
+}
+
+static inline void
+free_node_list (SfiRing *start)
+{
+ /* NULL terminated list of ->next pointers */
+#if HAVE_GSLICE
+ g_slice_free_chain (SfiRing, start, next);
+#else
+ g_list_free ((GList*) start);
+#endif
+}
+
+/* --- basic comparisons --- */
+gint
+sfi_pointer_cmp (gconstpointer value1,
+ gconstpointer value2,
+ gpointer dummy)
+{
+ const char *p1 = value1;
+ const char *p2 = value2;
+ return p1 < p2 ? -1 : p1 != p2;
+}
+
+
+/* --- ring (circular-list) --- */
+static inline SfiRing*
+sfi_ring_prepend_link_i (SfiRing *head,
+ SfiRing *ring)
+{
+ if (!head)
+ {
+ ring->prev = ring;
+ ring->next = ring;
+ }
+ else
+ {
+ ring->prev = head->prev;
+ ring->next = head;
+ head->prev->next = ring;
+ head->prev = ring;
+ }
+ return ring;
+}
+
+static inline SfiRing*
+sfi_ring_prepend_i (SfiRing *head,
+ gpointer data)
+{
+ SfiRing *ring = node_alloc();
+
+ ring->data = data;
+ return sfi_ring_prepend_link_i (head, ring);
+}
+
+static inline SfiRing*
+sfi_ring_append_link_i (SfiRing *head,
+ SfiRing *ring)
+{
+ sfi_ring_prepend_link_i (head, ring);
+ return head ? head : ring;
+}
+
+SfiRing*
+sfi_ring_prepend (SfiRing *head,
+ gpointer data)
+{
+ return sfi_ring_prepend_i (head, data);
+}
+
+SfiRing*
+sfi_ring_prepend_uniq (SfiRing *head,
+ gpointer data)
+{
+ SfiRing *ring;
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head))
+ if (ring->data == data)
+ return head;
+ return sfi_ring_prepend_i (head, data);
+}
+
+SfiRing*
+sfi_ring_append (SfiRing *head,
+ gpointer data)
+{
+ SfiRing *ring = sfi_ring_prepend_i (head, data);
+ return head ? head : ring;
+}
+
+SfiRing*
+sfi_ring_append_uniq (SfiRing *head,
+ gpointer data)
+{
+ SfiRing *ring;
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head))
+ if (ring->data == data)
+ return head;
+ ring = sfi_ring_prepend_i (head, data);
+ return head ? head : ring;
+}
+
+SfiRing*
+sfi_ring_insert_before (SfiRing *head,
+ SfiRing *sibling,
+ gpointer data)
+{
+ if (!sibling)
+ return sfi_ring_append (head, data);
+ SfiRing *node = sfi_ring_prepend (sibling, data);
+ return sibling == head ? node : head;
+}
+
+SfiRing*
+sfi_ring_insert (SfiRing *head,
+ gpointer data,
+ gint position)
+{
+ if (position < 0)
+ return sfi_ring_append (head, data);
+ else if (position == 0)
+ return sfi_ring_prepend (head, data);
+ SfiRing *node = sfi_ring_nth (head, position);
+ if (node)
+ return sfi_ring_insert_before (head, node, data);
+ else
+ return sfi_ring_append (head, data);
+}
+
+gint
+sfi_ring_position (const SfiRing *head,
+ const SfiRing *node)
+{
+ guint i = 0;
+ const SfiRing *ring;
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head), i++)
+ if (ring == node)
+ return i;
+ return -1;
+}
+
+gint
+sfi_ring_index (const SfiRing *head,
+ gconstpointer data)
+{
+ guint i = 0;
+ const SfiRing *ring;
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head), i++)
+ if (ring->data == data)
+ return i;
+ return -1;
+}
+
+SfiRing*
+sfi_ring_copy (const SfiRing *head)
+{
+ const SfiRing *walk;
+ SfiRing *dest = NULL;
+ for (walk = head; walk; walk = sfi_ring_walk (walk, head))
+ dest = sfi_ring_append (dest, walk->data);
+ return dest;
+}
+
+SfiRing*
+sfi_ring_copy_deep (const SfiRing *head,
+ SfiRingDataFunc copy,
+ gpointer func_data)
+{
+ const SfiRing *walk;
+ SfiRing *dest = NULL;
+ for (walk = head; walk; walk = sfi_ring_walk (walk, head))
+ dest = sfi_ring_append (dest, copy (walk->data, func_data));
+ return dest;
+}
+
+SfiRing*
+sfi_ring_copy_rest (const SfiRing *ring,
+ const SfiRing *head)
+{
+ const SfiRing *walk;
+ SfiRing *dest = NULL;
+ for (walk = ring; walk; walk = sfi_ring_walk (walk, head))
+ dest = sfi_ring_append (dest, walk->data);
+ return dest;
+}
+
+SfiRing*
+sfi_ring_concat (SfiRing *head1,
+ SfiRing *head2)
+{
+ SfiRing *tail1, *tail2;
+
+ if (!head1)
+ return head2;
+ if (!head2)
+ return head1;
+ tail1 = head1->prev;
+ tail2 = head2->prev;
+ head1->prev = tail2;
+ tail2->next = head1;
+ head2->prev = tail1;
+ tail1->next = head2;
+
+ return head1;
+}
+
+/**
+ * @param head1 a non-empty ring
+ * @param head2 a ring node different from @a head1 contained in @a head1
+ * @param returns @a head2 for convenience
+ *
+ * Split a ring into two parts, starting the second ring with @a head2.
+ * @a head2 must therefore be non-NULL and must be contained in the ring
+ * formed by @a head1.
+ */
+SfiRing*
+sfi_ring_split (SfiRing *head1,
+ SfiRing *head2)
+{
+ SfiRing *tail1, *tail2;
+
+ g_return_val_if_fail (head1 != NULL, NULL);
+ g_return_val_if_fail (head2 != NULL, NULL);
+ g_return_val_if_fail (head1 != head2, NULL);
+
+ tail1 = head2->prev;
+ tail2 = head1->prev;
+ head2->prev = tail2;
+ tail2->next = head2;
+ head1->prev = tail1;
+ tail1->next = head1;
+ return head2;
+}
+
+static inline SfiRing*
+sfi_ring_unlink_node_dangling (SfiRing *head,
+ SfiRing *node)
+{
+ g_assert (head && node);
+ /* special case one item ring */
+ if (head->prev == head)
+ return NULL;
+ /* unlink */
+ node->next->prev = node->prev;
+ node->prev->next = node->next;
+ if (head == node)
+ head = node->next;
+ /* node->prev and node->next are dangling now */
+ return head;
+}
+
+SfiRing*
+sfi_ring_remove_node (SfiRing *head,
+ SfiRing *node)
+{
+ if (!head)
+ g_return_val_if_fail (head == NULL && node == NULL, NULL);
+ if (!head || !node)
+ return NULL;
+
+ /* special case one item ring */
+ if (head->prev == head)
+ {
+ g_return_val_if_fail (node == head, head);
+
+ node_free (node);
+ return NULL;
+ }
+ g_return_val_if_fail (node != node->next, head); /* node can't be a one item ring here */
+
+ node->next->prev = node->prev;
+ node->prev->next = node->next;
+ if (head == node)
+ head = node->next;
+ node_free (node);
+
+ return head;
+}
+
+SfiRing*
+sfi_ring_reverse (SfiRing *head)
+{
+ if (head)
+ {
+ SfiRing *ring = head = head->prev;
+ do
+ {
+ SfiRing *tmp = ring;
+ ring = tmp->next;
+ tmp->next = tmp->prev;
+ tmp->prev = ring;
+ }
+ while (ring != head);
+ }
+ return head;
+}
+
+SfiRing*
+sfi_ring_remove (SfiRing *head,
+ gpointer data)
+{
+ SfiRing *walk;
+
+ if (!head)
+ return NULL;
+
+ /* make tail data removal an O(1) operation */
+ if (head->prev->data == data)
+ return sfi_ring_remove_node (head, head->prev);
+
+ for (walk = head; walk; walk = sfi_ring_walk (walk, head))
+ if (walk->data == data)
+ return sfi_ring_remove_node (head, walk);
+
+ /* g_warning (G_STRLOC ": couldn't find data item (%p) to remove from ring (%p)", data, head); */
+
+ return head;
+}
+
+guint
+sfi_ring_length (const SfiRing *head)
+{
+ const SfiRing *ring;
+ guint i = 0;
+
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head))
+ i++;
+
+ return i;
+}
+
+gint /* essentially compute length(ring) - test_length, clamped to -1..+1 */
+sfi_ring_cmp_length (const SfiRing *head,
+ guint test_length)
+{
+ const SfiRing *ring = head;
+
+ while (test_length && ring)
+ {
+ test_length--;
+ ring = sfi_ring_walk (ring, head);
+ }
+
+ return test_length > 0 ? -1 : ring != NULL;
+}
+
+SfiRing*
+sfi_ring_find (const SfiRing *head,
+ gconstpointer data)
+{
+ const SfiRing *ring;
+ for (ring = head; ring; ring = sfi_ring_walk (ring, head))
+ if (ring->data == (gpointer) data)
+ return (SfiRing*) ring;
+ return NULL;
+}
+
+SfiRing*
+sfi_ring_nth (const SfiRing *head,
+ guint n)
+{
+ const SfiRing *ring = head;
+ while (n-- && ring)
+ ring = sfi_ring_walk (ring, head);
+ return (SfiRing*) ring;
+}
+
+gpointer
+sfi_ring_nth_data (const SfiRing *head,
+ guint n)
+{
+ const SfiRing *ring = head;
+
+ while (n-- && ring)
+ ring = sfi_ring_walk (ring, head);
+
+ return ring ? ring->data : NULL;
+}
+
+void
+sfi_ring_free_deep (SfiRing *head,
+ GDestroyNotify data_destroy)
+{
+ while (head)
+ {
+ gpointer data = sfi_ring_pop_head (&head);
+ data_destroy (data);
+ data = sfi_ring_pop_head (&head);
+ }
+}
+
+void
+sfi_ring_free (SfiRing *head)
+{
+ if (head)
+ {
+ head->prev->next = NULL;
+ free_node_list (head);
+ }
+}
+
+gpointer
+sfi_ring_pop_head (SfiRing **head_p)
+{
+ gpointer data;
+
+ g_return_val_if_fail (head_p != NULL, NULL);
+
+ if (!*head_p)
+ return NULL;
+ data = (*head_p)->data;
+ *head_p = sfi_ring_remove_node (*head_p, *head_p);
+
+ return data;
+}
+
+gpointer
+sfi_ring_pop_tail (SfiRing **head_p)
+{
+ gpointer data;
+
+ g_return_val_if_fail (head_p != NULL, NULL);
+
+ if (!*head_p)
+ return NULL;
+ data = (*head_p)->prev->data;
+ *head_p = sfi_ring_remove_node (*head_p, (*head_p)->prev);
+
+ return data;
+}
+
+SfiRing*
+sfi_ring_from_list (GList *list)
+{
+ SfiRing *ring = NULL;
+ for (; list; list = list->next)
+ ring = sfi_ring_append (ring, list->data);
+ return ring;
+}
+
+SfiRing*
+sfi_ring_from_list_and_free (GList *list)
+{
+ SfiRing *ring = NULL;
+ GList *free_list = list;
+ for (; list; list = list->next)
+ ring = sfi_ring_append (ring, list->data);
+ g_list_free (free_list);
+ return ring;
+}
+
+SfiRing*
+sfi_ring_from_slist (GSList *slist)
+{
+ SfiRing *ring = NULL;
+ for (; slist; slist = slist->next)
+ ring = sfi_ring_append (ring, slist->data);
+ return ring;
+}
+
+SfiRing*
+sfi_ring_from_slist_and_free (GSList *slist)
+{
+ SfiRing *ring = NULL;
+ GSList *free_slist = slist;
+ for (; slist; slist = slist->next)
+ ring = sfi_ring_append (ring, slist->data);
+ g_slist_free (free_slist);
+ return ring;
+}
+
+SfiRing*
+sfi_ring_insert_sorted (SfiRing *head,
+ gpointer insertion_data,
+ SfiCompareFunc cmp,
+ gpointer cmp_data)
+{
+ g_return_val_if_fail (cmp != NULL, head);
+ if (!head)
+ return sfi_ring_prepend (head, insertion_data);
+
+ /* implement stable sorting by inserting insertion_data *after* equal nodes */
+
+ if (cmp (insertion_data, head->data, cmp_data) >= 0) /* insert after head */
+ {
+ SfiRing *tmp, *tail = head->prev;
+
+ /* make appending an O(1) operation */
+ if (head == tail || cmp (insertion_data, tail->data, cmp_data) >= 0)
+ return sfi_ring_append (head, insertion_data);
+
+ /* walk forward while data >= tmp (skipping equal nodes) */
+ for (tmp = head->next; tmp != tail; tmp = tmp->next)
+ if (cmp (insertion_data, tmp->data, cmp_data) < 0)
+ break;
+
+ /* insert before sibling which is greater than insertion_data */
+ sfi_ring_prepend (tmp, insertion_data); /* keep current head */
+ return head;
+ }
+ else /* cmp < 0 */
+ return sfi_ring_prepend (head, insertion_data);
+}
+
+SfiRing*
+sfi_ring_merge_sorted (SfiRing *head1,
+ SfiRing *head2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ /* implement stable sorting by inserting head2 members *after* equal nodes from head1 */
+
+ if (head1 && head2)
+ {
+ SfiRing *tail1 = head1->prev;
+ SfiRing *tail2 = head2->prev;
+ SfiRing *tmp, *ring = NULL;
+ /* NULL terminate rings */
+ tail1->next = NULL;
+ tail2->next = NULL;
+ while (head1 && head2)
+ {
+ gint c = cmp (head1->data, head2->data, data);
+ if (c <= 0)
+ {
+ tmp = head1;
+ head1 = head1->next;
+ }
+ else
+ {
+ tmp = head2;
+ head2 = head2->next;
+ }
+ ring = sfi_ring_append_link_i (ring, tmp);
+ }
+ /* reform valid rings, concat sorted rest */
+ if (head1)
+ {
+ tail1->next = head1;
+ head1->prev = tail1;
+ return sfi_ring_concat (ring, head1);
+ }
+ if (head2)
+ {
+ tail2->next = head2;
+ head2->prev = tail2;
+ return sfi_ring_concat (ring, head2);
+ }
+ return ring;
+ }
+ else
+ return sfi_ring_concat (head1, head2);
+}
+
+SfiRing*
+sfi_ring_sort (SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ g_return_val_if_fail (cmp != NULL, head);
+
+ /* stable sorting guaranteed by sfi_ring_merge_sorted() */
+
+ if (head && head->next != head)
+ {
+ SfiRing *ring, *tmp, *tail = head->prev;
+ /* find middle node to get log2 recursion depth */
+ ring = tmp = head->next;
+ while (tmp != tail && tmp->next != tail)
+ {
+ ring = ring->next;
+ tmp = tmp->next->next;
+ }
+ sfi_ring_split (head, ring);
+ return sfi_ring_merge_sorted (sfi_ring_sort (head, cmp, data),
+ sfi_ring_sort (ring, cmp, data),
+ cmp, data);
+ }
+ return head;
+}
+
+SfiRing* /* eliminates duplicate nodes */
+sfi_ring_uniq (SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ /* always preserves the first of a sublist of consequtive equal elements */
+ SfiRing *r1 = sorted_ring1;
+ SfiRing *r2 = NULL;
+ if (r1)
+ {
+ SfiRing *last = r1;
+ r1 = sfi_ring_unlink_node_dangling (r1, last);
+ r2 = last->next = last->prev = last; /* form new ring */
+ while (r1)
+ {
+ SfiRing *node = r1;
+ r1 = sfi_ring_unlink_node_dangling (r1, node);
+ if (cmp (last->data, node->data, data))
+ {
+ last = node;
+ r2 = sfi_ring_append_link_i (r2, last);
+ }
+ else
+ node_free (node);
+ }
+ }
+ return r2;
+}
+
+SfiRing* /* eliminates duplicate nodes */
+sfi_ring_uniq_free_deep (SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data,
+ GDestroyNotify data_destroy)
+{
+ /* always preserves the first of a sublist of consequtive equal elements */
+ if (!data_destroy)
+ return sfi_ring_uniq (sorted_ring1, cmp, data);
+ SfiRing *r1 = sorted_ring1;
+ SfiRing *r2 = NULL;
+ if (r1)
+ {
+ SfiRing *last = r1;
+ r1 = sfi_ring_unlink_node_dangling (r1, last);
+ r2 = last->next = last->prev = last; /* form new ring */
+ while (r1)
+ {
+ SfiRing *node = r1;
+ r1 = sfi_ring_unlink_node_dangling (r1, node);
+ if (cmp (last->data, node->data, data))
+ {
+ last = node;
+ r2 = sfi_ring_append_link_i (r2, last);
+ }
+ else
+ {
+ data_destroy (node->data);
+ node_free (node);
+ }
+ }
+ }
+ return r2;
+}
+
+SfiRing* /* eliminates duplicate nodes */
+sfi_ring_copy_deep_uniq (const SfiRing *sorted_ring1,
+ SfiRingDataFunc copy,
+ gpointer copy_data,
+ SfiCompareFunc cmp,
+ gpointer cmp_data)
+{
+ /* always preserves the first of a sublist of consequtive equal elements */
+ if (!copy)
+ return sfi_ring_copy_uniq (sorted_ring1, cmp, cmp_data);
+ const SfiRing *r1 = sorted_ring1;
+ SfiRing *r2 = NULL;
+ if (r1)
+ {
+ gpointer last_data = r1->data;
+ r2 = sfi_ring_append (r2, copy (last_data, copy_data));
+ for (r1 = sfi_ring_walk (r1, sorted_ring1); r1; r1 = sfi_ring_walk (r1, sorted_ring1))
+ if (cmp (last_data, r1->data, cmp_data))
+ {
+ last_data = r1->data;
+ r2 = sfi_ring_append (r2, copy (last_data, copy_data));
+ }
+ }
+ return r2;
+}
+
+SfiRing* /* eliminates duplicate nodes */
+sfi_ring_copy_uniq (const SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ /* always preserves the first of a sublist of consequtive equal elements */
+ const SfiRing *r1 = sorted_ring1;
+ SfiRing *r2 = NULL;
+ if (r1)
+ {
+ gpointer last_data = r1->data;
+ r2 = sfi_ring_append (r2, last_data);
+ for (r1 = sfi_ring_walk (r1, sorted_ring1); r1; r1 = sfi_ring_walk (r1, sorted_ring1))
+ if (cmp (last_data, r1->data, data))
+ {
+ last_data = r1->data;
+ r2 = sfi_ring_append (r2, last_data);
+ }
+ }
+ return r2;
+}
+
+/**
+ * @param sorted_set1 Sorted ring 1
+ * @param sorted_set2 Sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Newly created (or empty) ring
+ *
+ * Return a newly created ring that contains all data items from @a sorted_set1
+ * and @a sorted_set2, omitting duplicates.
+ * Items are considered equal according to the cmp() function.
+ * For two equal items contained in both sets, the data pointer from
+ * @a sorted_set1 will be added to the resulting set.
+ * In mathematical terms, the returned ring is the union (sorted_set1, sorted_set2).
+ * The complexity is O(MAX (length (sorted_set1), length (sorted_set2))).
+ */
+SfiRing* /* merges rings without dups */
+sfi_ring_union (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ /* for two equal elements from both sets, the element from sorted_set1 is picked, the one from sorted_set2 ignored */
+ const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
+ SfiRing *d = NULL;
+ while (r1 && r2)
+ {
+ gint c = cmp (r1->data, r2->data, data);
+ if (c < 0)
+ {
+ d = sfi_ring_append (d, r1->data);
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ }
+ else if (c > 0)
+ {
+ d = sfi_ring_append (d, r2->data);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ else
+ {
+ d = sfi_ring_append (d, r1->data);
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ }
+ return sfi_ring_concat (d, sfi_ring_copy_rest (r1 ? r1 : r2, r1 ? sorted_set1 : sorted_set2));
+}
+
+/**
+ * @param sorted_set1 Sorted ring 1
+ * @param sorted_set2 Sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Newly created (or empty) ring
+ *
+ * Return a newly created ring that contains all data items which are contained
+ * in both sets, @a sorted_set1 and @a sorted_set2.
+ * Items are considered equal according to the cmp() function.
+ * For two equal items contained in both sets, the data pointer from
+ * @a sorted_set1 will be added to the resulting set.
+ * In mathematical terms, the returned ring is the intersection (sorted_set1, sorted_set2).
+ * The complexity is O(MAX (length (sorted_set1), length (sorted_set2))).
+ */
+SfiRing* /* returns nodes contained in both rings */
+sfi_ring_intersection (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ /* for two equal elements from both sets, only elements from sorted_set1 are picked */
+ const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
+ SfiRing *d = NULL;
+ while (r1 && r2)
+ {
+ gint c = cmp (r1->data, r2->data, data);
+ if (c < 0)
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ else if (c > 0)
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ else
+ {
+ d = sfi_ring_append (d, r1->data);
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ }
+ return d;
+}
+
+/**
+ * @param sorted_set1 Sorted ring 1
+ * @param sorted_set2 Sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Newly created (or empty) ring
+ *
+ * Collect and return all data items from @a sorted_set1 which are not contained in
+ * @a sorted_set2, according to the cmp() function.
+ * In mathematical terms, the returned ring is the difference (sorted_set1, sorted_set2).
+ * The complexity is O(MAX (length (sorted_set1), length (sorted_set2))).
+ */
+SfiRing*
+sfi_ring_difference (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
+ SfiRing *d = NULL;
+ while (r1 && r2)
+ {
+ gint c = cmp (r1->data, r2->data, data);
+ if (c < 0)
+ {
+ d = sfi_ring_append (d, r1->data);
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ }
+ else if (c > 0)
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ else
+ {
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ }
+ return sfi_ring_concat (d, sfi_ring_copy_rest (r1, sorted_set1));
+}
+
+/**
+ * @param sorted_set1 Sorted ring 1
+ * @param sorted_set2 Sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Newly created (or empty) ring
+ *
+ * Collect and return all data items from @a sorted_set1 which are not contained in
+ * @a sorted_set2, and all data items from @a sorted_set2 which are not contained in
+ * @a sorted_set1, according to the cmp() function.
+ * In mathematical terms, the returned ring is the union (difference (sorted_set1, sorted_set2)
+ * + difference (sorted_set2, sorted_set1)).
+ * The complexity is O(MAX (length (sorted_set1), length (sorted_set2))).
+ */
+SfiRing*
+sfi_ring_symmetric_difference (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *r1 = sorted_set1, *r2 = sorted_set2;
+ SfiRing *d = NULL;
+ while (r1 && r2)
+ {
+ gint c = cmp (r1->data, r2->data, data);
+ if (c < 0)
+ {
+ d = sfi_ring_append (d, r1->data);
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ }
+ else if (c > 0)
+ {
+ d = sfi_ring_append (d, r2->data);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ else
+ {
+ r1 = sfi_ring_walk (r1, sorted_set1);
+ r2 = sfi_ring_walk (r2, sorted_set2);
+ }
+ }
+ return sfi_ring_concat (d, sfi_ring_copy_rest (r1 ? r1 : r2, r1 ? sorted_set1 : sorted_set2));
+}
+
+static inline int
+pointerloccmp (const void *pp1,
+ const void *pp2)
+{
+ const gpointer *p1 = pp1;
+ const gpointer *p2 = pp2;
+ return *p1 < *p2 ? -1 : *p1 != *p2;
+}
+
+static inline gboolean
+ring_reorder_lookup (guint n_items,
+ gpointer *items,
+ gpointer key,
+ guint *indexp)
+{
+ guint offset = 0, n = n_items;
+ while (offset < n)
+ {
+ guint i = (offset + n) >> 1;
+ gint cmp = key < items[i] ? -1 : key != items[i];
+ if (cmp < 0)
+ n = i;
+ else if (cmp > 0)
+ offset = i + 1;
+ else /* match */
+ {
+ *indexp = i;
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+/**
+ * @param unordered_ring Unsorted ring
+ * @param new_ring_order Ring with arbitrary order
+ * @return Reordered version of @a unordered_ring
+ *
+ * Reorders the data pointers of @a unordered_ring according to the order
+ * as given by @a new_ring_order.
+ * The complexity involves roughly 3 * length(unordered_ring) + qsort(unordered_ring) + length(new_ring_order) * bsearch(unordered_ring)),
+ * i.e. it is at worst O(length(unordered_ring) * log (length(unordered_ring)) * length(new_ring_order)).
+ */
+SfiRing* /* reproduce all elements from unordered_ring in the order new_ring_order */
+sfi_ring_reorder (SfiRing *unordered_ring,
+ const SfiRing *new_ring_order)
+{
+ if (!unordered_ring || !new_ring_order)
+ return unordered_ring;
+ const SfiRing *ring;
+
+ /* construct a sorted array for faster lookups; O(length(unordered_ring)) */
+ gpointer *items = NULL;
+ guint i, n_items = 0, n_alloced = 0;
+ for (ring = unordered_ring; ring; ring = sfi_ring_walk (ring, unordered_ring))
+ {
+ i = n_items++;
+ if (n_items > n_alloced)
+ {
+ n_alloced = sfi_alloc_upper_power2 (MAX (n_items, 32));
+ items = g_renew (gpointer, items, n_alloced);
+ }
+ items[i] = ring->data;
+ }
+ sfi_ring_free (unordered_ring);
+ unordered_ring = NULL;
+ qsort (items, n_items, sizeof (items[0]), pointerloccmp);
+
+ /* collapse duplicates; O(length(unordered_ring)) */
+ guint j = 0, *counts = g_new0 (guint, n_items);
+ for (i = 0; i < n_items; i++)
+ if (items[j] != items[i])
+ {
+ if (++j != i)
+ items[j] = items[i];
+ counts[j] = 1;
+ }
+ else /* catch dups */
+ counts[j]++;
+ n_items = j + 1; /* shrink to number of different items */
+
+ /* pick unordered_ring members in the order given by new_ring_order;
+ * O(length(new_ring_order) * O(bsearch(unordered_ring)))
+ */
+ for (ring = new_ring_order; ring; ring = sfi_ring_walk (ring, new_ring_order))
+ if (ring_reorder_lookup (n_items, items, ring->data, &i) && counts[i])
+ {
+ counts[i]--;
+ unordered_ring = sfi_ring_append (unordered_ring, ring->data);
+ }
+
+ /* append left-over members from sorted_ring; O(length(unordered_ring)) */
+ for (i = 0; i < n_items; i++)
+ while (counts[i]--)
+ unordered_ring = sfi_ring_append (unordered_ring, items[i]);
+
+ g_free (items);
+ g_free (counts);
+ return unordered_ring;
+}
+
+gboolean
+sfi_ring_includes (const SfiRing *sorted_super_set,
+ const SfiRing *sorted_sub_set,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *r1 = sorted_super_set, *r2 = sorted_sub_set;
+ while (r1 && r2)
+ {
+ gint c = cmp (r1->data, r2->data, data);
+ if (c > 0)
+ return FALSE;
+ else if (c == 0)
+ r2 = sfi_ring_walk (r2, sorted_sub_set);
+ // FIXME: misses backtracking to find "abc" in "aabc"
+ r1 = sfi_ring_walk (r1, sorted_super_set);
+ }
+ return !r2;
+}
+
+/**
+ * @param sorted_ring1 Sorted ring 1
+ * @param sorted_ring2 Sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return TRUE for equal rings, FALSE otherwise
+ *
+ * Compare two rings according to the cmp() function. Return FALSE as
+ * soon as a mismatch is found, returns TRUE for rings which are equal according to cmp().
+ * The complexity is at most O(MIN (length (sorted_ring1), length (sorted_ring2))).
+ */
+gboolean
+sfi_ring_equals (const SfiRing *sorted_ring1,
+ const SfiRing *sorted_ring2,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *r1 = sorted_ring1, *r2 = sorted_ring2;
+ while (r1 && r2)
+ {
+ if (cmp (r1->data, r2->data, data))
+ return FALSE;
+ r1 = sfi_ring_walk (r1, sorted_ring1);
+ r2 = sfi_ring_walk (r2, sorted_ring2);
+ }
+ return r1 == r2; /* both need to be NULL */
+}
+
+/**
+ * @param sorted_ring1_p Pointer to sorted ring 1
+ * @param sorted_ring2_p Pointer to sorted ring 2
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return TRUE for mismatching rings, FALSE otherwise
+ *
+ * Compare two rings according to the cmp() function. For mismatching rings,
+ * @a sorted_ring1_p and @a sorted_ring2_p are set to point to the mismatching nodes.
+ * The complexity is at most O(MIN (length (sorted_ring1), length (sorted_ring2))).
+ */
+gboolean
+sfi_ring_mismatch (SfiRing **sorted_ring1_p,
+ SfiRing **sorted_ring2_p,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ SfiRing *head1 = *sorted_ring1_p, *head2 = *sorted_ring2_p;
+ SfiRing *r1 = head1, *r2 = head2;
+ while (r1 && r2)
+ {
+ if (cmp (r1->data, r2->data, data))
+ goto mismatch;
+ r1 = sfi_ring_walk (r1, head1);
+ r2 = sfi_ring_walk (r2, head2);
+ }
+ if (r1 == r2) /* both are NULL */
+ return FALSE;
+ mismatch:
+ *sorted_ring1_p = r1;
+ *sorted_ring2_p = r2;
+ return TRUE;
+}
+
+/**
+ * @param head Head node of a ring or NULL for an empty ring
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Node with minimum data argument or NULL for empty rings
+ *
+ * Find and return the node holding the minimum data pointer of a ring, measured by evaluating cmp().
+ * The complexity is O(length (head)).
+ */
+SfiRing*
+sfi_ring_min_node (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *ring = head, *last = NULL;
+ if (ring)
+ {
+ last = ring;
+ for (ring = sfi_ring_walk (ring, head); ring; ring = sfi_ring_walk (ring, head))
+ if (cmp (last->data, ring->data, data) > 0)
+ last = ring;
+ }
+ return (SfiRing*) last;
+}
+
+/**
+ * @param head Head node of a ring or NULL for an empty ring
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Node with maximum data argument or NULL for empty rings
+ *
+ * Find and return the node holding the maximum data pointer of a ring, measured by evaluating cmp().
+ * The complexity is O(length (head)).
+ */
+SfiRing*
+sfi_ring_max_node (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ const SfiRing *ring = head, *last = NULL;
+ if (ring)
+ {
+ last = ring;
+ for (ring = sfi_ring_walk (ring, head); ring; ring = sfi_ring_walk (ring, head))
+ if (cmp (last->data, ring->data, data) < 0)
+ last = ring;
+ }
+ return (SfiRing*) last;
+}
+
+/**
+ * @param head Head node of a ring or NULL for an empty ring
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Minimum data argument or NULL for empty rings
+ *
+ * Find and return the minimum data pointer of a ring, measured by evaluating cmp().
+ * The complexity is O(length (head)).
+ */
+gpointer
+sfi_ring_min (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ SfiRing *ring = sfi_ring_min_node (head, cmp, data);
+ return ring ? ring->data : NULL;
+}
+
+/**
+ * @param head Head node of a ring or NULL for an empty ring
+ * @param cmp Compare function for node data
+ * @param data Data argument passed into the cmp() function
+ * @return Maximum data argument or NULL for empty rings
+ *
+ * Find and return the maximum data pointer of a ring, measured by evaluating cmp().
+ * The complexity is O(length (head)).
+ */
+gpointer
+sfi_ring_max (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data)
+{
+ SfiRing *ring = sfi_ring_max_node (head, cmp, data);
+ return ring ? ring->data : NULL;
+}
Copied: trunk/sfi/sfiring.h (from rev 3925, trunk/birnet/birnetring.h)
===================================================================
--- trunk/birnet/birnetring.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfiring.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -0,0 +1,181 @@
+/* SfiRing
+ * Copyright (C) 2002-2006 Tim Janik
+ *
+ * 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 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., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+#ifndef __SFI_RING_H__
+#define __SFI_RING_H__
+
+#include <sfi/sfitypes.h>
+
+G_BEGIN_DECLS;
+
+
+/* --- basic comparisons --- */
+typedef gint (*SfiCompareFunc) (gconstpointer value1,
+ gconstpointer value2,
+ gpointer data);
+gint sfi_pointer_cmp (gconstpointer value1,
+ gconstpointer value2,
+ gpointer dummy);
+
+
+/* --- ring (circular-list) --- */
+typedef gpointer (*SfiRingDataFunc) (gpointer data,
+ gpointer func_data);
+typedef struct SfiRing SfiRing;
+struct SfiRing
+{
+ gpointer data;
+ SfiRing *next;
+ SfiRing *prev;
+};
+SfiRing* sfi_ring_prepend (SfiRing *head,
+ gpointer data);
+SfiRing* sfi_ring_prepend_uniq (SfiRing *head,
+ gpointer data);
+SfiRing* sfi_ring_append (SfiRing *head,
+ gpointer data);
+SfiRing* sfi_ring_append_uniq (SfiRing *head,
+ gpointer data);
+SfiRing* sfi_ring_insert (SfiRing *head,
+ gpointer data,
+ gint position);
+SfiRing* sfi_ring_insert_before (SfiRing *head,
+ SfiRing *sibling,
+ gpointer data);
+gint sfi_ring_position (const SfiRing *head,
+ const SfiRing *node);
+gint sfi_ring_index (const SfiRing *head,
+ gconstpointer data);
+SfiRing* sfi_ring_nth (const SfiRing *head,
+ guint n);
+gpointer sfi_ring_nth_data (const SfiRing *head,
+ guint n);
+SfiRing* sfi_ring_find (const SfiRing *head,
+ gconstpointer data);
+SfiRing* sfi_ring_remove_node (SfiRing *head,
+ SfiRing *node);
+SfiRing* sfi_ring_remove (SfiRing *head,
+ gpointer data);
+guint sfi_ring_length (const SfiRing *head);
+gint sfi_ring_cmp_length (const SfiRing *head,
+ guint test_length);
+SfiRing* sfi_ring_copy (const SfiRing *head);
+SfiRing* sfi_ring_copy_deep (const SfiRing *head,
+ SfiRingDataFunc copy,
+ gpointer func_data);
+SfiRing* sfi_ring_copy_rest (const SfiRing *ring,
+ const SfiRing *head);
+SfiRing* sfi_ring_concat (SfiRing *head1,
+ SfiRing *head2);
+SfiRing* sfi_ring_split (SfiRing *head1,
+ SfiRing *head2);
+SfiRing* sfi_ring_reverse (SfiRing *head);
+gpointer sfi_ring_pop_head (SfiRing **head);
+gpointer sfi_ring_pop_tail (SfiRing **head);
+#define sfi_ring_push_head sfi_ring_prepend
+#define sfi_ring_push_tail sfi_ring_append
+void sfi_ring_free (SfiRing *head);
+void sfi_ring_free_deep (SfiRing *head,
+ GDestroyNotify data_destroy);
+
+SfiRing* sfi_ring_from_list (GList *list);
+SfiRing* sfi_ring_from_list_and_free (GList *list);
+SfiRing* sfi_ring_from_slist (GSList *slist);
+SfiRing* sfi_ring_from_slist_and_free (GSList *slist);
+#define sfi_ring_tail(head) ((head) ? (head)->prev : NULL)
+#define sfi_ring_walk(node,head_bound) ((node)->next != (head_bound) ? (node)->next : NULL)
+#define sfi_ring_next(node,head_bound) sfi_ring_walk (node, head_bound)
+
+
+/* ring-modifying cmp-based operations */
+SfiRing* sfi_ring_insert_sorted (SfiRing *head,
+ gpointer insertion_data,
+ SfiCompareFunc cmp,
+ gpointer cmp_data);
+SfiRing* sfi_ring_merge_sorted (SfiRing *head1,
+ SfiRing *head2,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_sort (SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_uniq (SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_uniq_free_deep (SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data,
+ GDestroyNotify data_destroy);
+SfiRing* sfi_ring_reorder (SfiRing *unordered_ring,
+ const SfiRing *new_ring_order);
+/* ring-copying cmp-based operations */
+SfiRing* sfi_ring_copy_deep_uniq (const SfiRing *sorted_ring1,
+ SfiRingDataFunc copy,
+ gpointer copy_data,
+ SfiCompareFunc cmp,
+ gpointer cmp_data);
+SfiRing* sfi_ring_copy_uniq (const SfiRing *sorted_ring1,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_union (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_intersection (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_difference (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_symmetric_difference (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data);
+/* const-result cmp-based operations */
+gboolean sfi_ring_includes (const SfiRing *sorted_super_set,
+ const SfiRing *sorted_sub_set,
+ SfiCompareFunc cmp,
+ gpointer data);
+gboolean sfi_ring_mismatch (SfiRing **sorted_ring1_p,
+ SfiRing **sorted_ring2_p,
+ SfiCompareFunc cmp,
+ gpointer data);
+gboolean sfi_ring_equals (const SfiRing *sorted_set1,
+ const SfiRing *sorted_set2,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_min_node (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data);
+SfiRing* sfi_ring_max_node (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data);
+gpointer sfi_ring_min (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data);
+gpointer sfi_ring_max (const SfiRing *head,
+ SfiCompareFunc cmp,
+ gpointer data);
+
+G_END_DECLS;
+
+#endif /* __SFI_RING_H__ */
+
+/* vim:set ts=8 sts=2 sw=2: */
Modified: trunk/sfi/sfistore.h
===================================================================
--- trunk/sfi/sfistore.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfistore.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -20,6 +20,7 @@
#define __SFI_STORE_H__
#include <sfi/sfivalues.h>
+#include <sfi/sfiring.h>
G_BEGIN_DECLS
Modified: trunk/sfi/sfitime.c
===================================================================
--- trunk/sfi/sfitime.c 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfitime.c 2006-10-03 15:28:27 UTC (rev 3926)
@@ -18,6 +18,7 @@
*/
#include "topconfig.h"
#include "sfitime.h"
+#include "sfiring.h"
#include "sfiprimitives.h"
#include <sys/time.h>
#include <string.h>
Modified: trunk/sfi/sfitypes.h
===================================================================
--- trunk/sfi/sfitypes.h 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/sfitypes.h 2006-10-03 15:28:27 UTC (rev 3926)
@@ -55,7 +55,6 @@
typedef struct _SfiSeq SfiSeq;
typedef struct _SfiRec SfiRec;
typedef GType /* pointer */ SfiProxy;
-typedef struct _SfiRing SfiRing;
typedef struct {
guint n_fields;
GParamSpec **fields;
Added: trunk/sfi/tests/Makefile.am
===================================================================
--- trunk/sfi/tests/Makefile.am 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/tests/Makefile.am 2006-10-03 15:28:27 UTC (rev 3926)
@@ -0,0 +1,17 @@
+# Birnet
+# Copyright (C) 2006 Tim Janik
+#
+## GNU Lesser General Public License version 2 or any later version.
+include $(top_srcdir)/Makefile.decl
+
+INCLUDES += -I$(top_srcdir) -I$(top_builddir) -I. $(SFI_CFLAGS)
+DEFS += -DG_LOG_DOMAIN='"$(basename $(@F))"' -DPARANOID # -DG_DISABLE_CONST_RETURNS
+
+TESTS =
+noinst_PROGRAMS = $(TESTS)
+progs_ldadd = $(top_builddir)/birnet/libbirnet.o $(top_builddir)/sfi/libsfi.o $(SFI_LIBS) -lm
+
+# ring
+TESTS += ring
+ring_SOURCES = ring.c dummy.cc
+ring_LDADD = $(progs_ldadd)
Copied: trunk/sfi/tests/dummy.cc (from rev 3925, trunk/sfi/dummy.cc)
Copied: trunk/sfi/tests/ring.c (from rev 3925, trunk/birnet/tests/ring.cc)
===================================================================
--- trunk/birnet/tests/ring.cc 2006-10-03 11:19:35 UTC (rev 3925)
+++ trunk/sfi/tests/ring.c 2006-10-03 15:28:27 UTC (rev 3926)
@@ -0,0 +1,232 @@
+/* Birnet
+ * Copyright (C) 2006 Tim Janik
+ *
+ * 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 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., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+// #define TEST_VERBOSE
+#include <birnet/birnettests.h>
+#include <sfi/sfi.h>
+
+static void
+print_ring_ints (SfiRing *ring)
+{
+ g_print ("SfiRing(%p): {", ring);
+ SfiRing *node;
+ for (node = ring; node; node = sfi_ring_walk (node, ring))
+ g_print (" %d,", (ptrdiff_t) node->data);
+ g_print (" };");
+}
+
+static void
+print_rings_side_by_side (SfiRing *ring1,
+ SfiRing *ring2)
+{
+ SfiRing *r1 = ring1, *r2 = ring2;
+ g_printerr ("\nRing=%p Ring=%p\n", r1, r2);
+ while (r1 || r2)
+ {
+ if (r1 && r2)
+ g_printerr (" %10p %10p\n", r1->data, r2->data);
+ else if (r1)
+ g_printerr (" %10p\n", r1->data);
+ else
+ g_printerr (" %10p\n", r2->data);
+ if (r1)
+ r1 = sfi_ring_walk (r1, ring1);
+ if (r2)
+ r2 = sfi_ring_walk (r2, ring2);
+ }
+}
+
+static void
+test_sfi_ring (void)
+{
+ TSTART ("RingBasics");
+ (void) print_ring_ints;
+
+ SfiRing *r1 = NULL, *r2 = NULL, *d = NULL;
+
+ r1= sfi_ring_append (r1, (void*) 3);
+ r1= sfi_ring_append (r1, (void*) 7);
+ r1= sfi_ring_append (r1, (void*) 8);
+ r1= sfi_ring_append (r1, (void*) 13);
+ r1= sfi_ring_append (r1, (void*) 18);
+ TASSERT (sfi_ring_length (r1) == 5);
+ TASSERT (sfi_ring_equals (r1, r1, sfi_pointer_cmp, NULL));
+
+ d = sfi_ring_append (d, (void*) 13);
+ d = sfi_ring_append (d, (void*) 7);
+ d = sfi_ring_append (d, (void*) 18);
+ d = sfi_ring_append (d, (void*) 3);
+ d = sfi_ring_append (d, (void*) 8);
+ TASSERT (sfi_ring_equals (d, d, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_min (d, sfi_pointer_cmp, NULL) == (void*) 3);
+ TASSERT (sfi_ring_max (d, sfi_pointer_cmp, NULL) == (void*) 18);
+
+ TASSERT (sfi_ring_equals (r1, d, sfi_pointer_cmp, NULL) == FALSE);
+ d = sfi_ring_sort (d, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_equals (r1, d, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_includes (r1, d, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_includes (d, r1, sfi_pointer_cmp, NULL));
+ sfi_ring_free (d);
+
+ r2 = sfi_ring_append (r2, (void*) 4);
+ r2 = sfi_ring_append (r2, (void*) 7);
+ r2 = sfi_ring_append (r2, (void*) 13);
+ TASSERT (sfi_ring_length (r2) == 3);
+ d = sfi_ring_sort (sfi_ring_copy (r2), sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_equals (r2, d, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_equals (r1, r2, sfi_pointer_cmp, NULL) == FALSE);
+ TASSERT (sfi_ring_includes (r1, r2, sfi_pointer_cmp, NULL) == FALSE);
+ sfi_ring_free (d);
+
+ TDONE ();
+ TSTART ("RingMath");
+
+ d = sfi_ring_difference (r1, r2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 3);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 8);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 18);
+ TASSERT (d == NULL);
+
+ d = sfi_ring_symmetric_difference (r1, r2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 3);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 4);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 8);
+ TASSERT (sfi_ring_pop_head (&d) == (void*) 18);
+ TASSERT (d == NULL);
+
+ SfiRing *t1 = sfi_ring_symmetric_difference (r1, r2, sfi_pointer_cmp, NULL);
+ SfiRing *t2 = sfi_ring_intersection (r1, r2, sfi_pointer_cmp, NULL);
+ d = sfi_ring_intersection (t1, t2, sfi_pointer_cmp, NULL);
+ TASSERT (d == NULL);
+ d = sfi_ring_union (t1, t2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_includes (d, t1, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_includes (d, t2, sfi_pointer_cmp, NULL));
+ sfi_ring_free (t1);
+ sfi_ring_free (t2);
+ TASSERT (sfi_ring_includes (d, r1, sfi_pointer_cmp, NULL));
+ TASSERT (sfi_ring_includes (d, r2, sfi_pointer_cmp, NULL));
+
+ d = sfi_ring_union (r1, r2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_length (d) == 6);
+ t1 = r1, t2 = d;
+ sfi_ring_mismatch (&t1, &t2, sfi_pointer_cmp, NULL);
+ TASSERT (t1->data == (void*) 7);
+ TASSERT (t2->data == (void*) 4);
+ t2 = sfi_ring_concat (sfi_ring_copy (r1), sfi_ring_copy (r2));
+ TASSERT (sfi_ring_length (t2) == 8);
+ t2 = sfi_ring_sort (t2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_length (t2) == 8);
+ t1 = sfi_ring_copy_uniq (t2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_length (t1) == 6);
+ TASSERT (sfi_ring_equals (d, t1, sfi_pointer_cmp, NULL));
+ sfi_ring_free (t1);
+ t1 = sfi_ring_uniq (t2, sfi_pointer_cmp, NULL);
+ TASSERT (sfi_ring_length (t1) == 6);
+ TASSERT (sfi_ring_equals (d, t1, sfi_pointer_cmp, NULL));
+ sfi_ring_free (t1);
+ sfi_ring_free (d);
+
+ sfi_ring_free (r1);
+ sfi_ring_free (r2);
+
+ TDONE ();
+ TSTART ("RingReorder");
+
+ r1 = NULL;
+ r1 = sfi_ring_append (r1, (void*) 5);
+ r1 = sfi_ring_append (r1, (void*) 7);
+ r1 = sfi_ring_append (r1, (void*) 4);
+ r1 = sfi_ring_append (r1, (void*) 8);
+ r1 = sfi_ring_append (r1, (void*) 1);
+ r2 = sfi_ring_sort (sfi_ring_copy (r1), sfi_pointer_cmp, NULL);
+ t1 = sfi_ring_reorder (sfi_ring_copy (r2), r1);
+ if (0)
+ print_rings_side_by_side (t1, r1);
+ TASSERT (sfi_ring_equals (t1, r1, sfi_pointer_cmp, NULL));
+ sfi_ring_free (t1);
+ r2 = sfi_ring_remove (r2, (void*) 4);
+ r2 = sfi_ring_append (r2, (void*) 9);
+ t1 = sfi_ring_reorder (sfi_ring_copy (r2), r1);
+ r1 = sfi_ring_remove (r1, (void*) 4);
+ r1 = sfi_ring_append (r1, (void*) 9);
+ if (0)
+ print_rings_side_by_side (t1, r1);
+ TASSERT (sfi_ring_equals (t1, r1, sfi_pointer_cmp, NULL));
+ sfi_ring_free (r1);
+ sfi_ring_free (r2);
+ sfi_ring_free (t1);
+ r1 = NULL;
+ r2 = NULL;
+ r1 = sfi_ring_append (r1, (void*) 0x75);
+ r1 = sfi_ring_append (r1, (void*) 0x4c);
+ r1 = sfi_ring_append (r1, (void*) 0x5e);
+ r2 = sfi_ring_append (r2, (void*) 0x4c);
+ r2 = sfi_ring_append (r2, (void*) 0x5e);
+ r2 = sfi_ring_append (r2, (void*) 0x68);
+ r2 = sfi_ring_append (r2, (void*) 0x68);
+ r2 = sfi_ring_reorder (r2, r1);
+ if (0)
+ print_rings_side_by_side (r2, r1);
+ TASSERT (sfi_ring_pop_head (&r2) == (void*) 0x4c);
+ TASSERT (sfi_ring_pop_head (&r2) == (void*) 0x5e);
+ TASSERT (sfi_ring_pop_head (&r2) == (void*) 0x68);
+ TASSERT (sfi_ring_pop_head (&r2) == (void*) 0x68);
+ TASSERT (r2 == NULL);
+ sfi_ring_free (r1);
+
+ r1 = NULL;
+ r1 = sfi_ring_append (r1, (void*) 0x11);
+ r1 = sfi_ring_append (r1, (void*) 0x16);
+ r1 = sfi_ring_append (r1, (void*) 0x15);
+ r1 = sfi_ring_append (r1, (void*) 0x14);
+ r1 = sfi_ring_append (r1, (void*) 0x13);
+ r1 = sfi_ring_append (r1, (void*) 0x12);
+ r1 = sfi_ring_append (r1, (void*) 0x03);
+ r1 = sfi_ring_append (r1, (void*) 0x02);
+ r1 = sfi_ring_append (r1, (void*) 0x01);
+ r2 = NULL;
+ r2 = sfi_ring_append (r2, (void*) 0x16);
+ r2 = sfi_ring_append (r2, (void*) 0x15);
+ r2 = sfi_ring_append (r2, (void*) 0x14);
+ r2 = sfi_ring_append (r2, (void*) 0x13);
+ r2 = sfi_ring_append (r2, (void*) 0x12);
+ r2 = sfi_ring_append (r2, (void*) 0x11);
+ r2 = sfi_ring_append (r2, (void*) 0x01);
+ r2 = sfi_ring_append (r2, (void*) 0x02);
+ r2 = sfi_ring_append (r2, (void*) 0x03);
+ r1 = sfi_ring_reorder (r1, r2);
+ TASSERT (sfi_ring_equals (r1, r2, sfi_pointer_cmp, NULL));
+ sfi_ring_free (r1);
+ sfi_ring_free (r2);
+
+ TDONE ();
+}
+
+
+int
+main (int argc,
+ char *argv[])
+{
+ birnet_init_test (&argc, &argv);
+
+ test_sfi_ring();
+
+ return 0;
+}
+
+/* vim:set ts=8 sts=2 sw=2: */
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
