Beast - Music Synthesizer and Composer  0.11.1+10.g2da35
sfiring.cc File Reference
#include "sfiring.hh"
#include "sfimemory.hh"
#include <stdlib.h>
#include <string.h>
Include dependency graph for sfiring.cc:

Macros

#define HAVE_GSLICE
 

Functions

gint sfi_pointer_cmp (gconstpointer value1, gconstpointer value2, gpointer dummy)
 
SfiRingsfi_ring_prepend (SfiRing *head, gpointer data)
 
SfiRingsfi_ring_prepend_uniq (SfiRing *head, gpointer data)
 
SfiRingsfi_ring_append (SfiRing *head, gpointer data)
 
SfiRingsfi_ring_append_uniq (SfiRing *head, gpointer data)
 
SfiRingsfi_ring_insert_before (SfiRing *head, SfiRing *sibling, gpointer data)
 
SfiRingsfi_ring_insert (SfiRing *head, gpointer data, gint position)
 
gint sfi_ring_position (const SfiRing *head, const SfiRing *node)
 
gint sfi_ring_index (const SfiRing *head, gconstpointer data)
 
SfiRingsfi_ring_copy (const SfiRing *head)
 
SfiRingsfi_ring_copy_deep (const SfiRing *head, SfiRingDataFunc copy, gpointer func_data)
 
SfiRingsfi_ring_copy_rest (const SfiRing *ring, const SfiRing *head)
 
SfiRingsfi_ring_concat (SfiRing *head1, SfiRing *head2)
 
SfiRingsfi_ring_split (SfiRing *head1, SfiRing *head2)
 
SfiRingsfi_ring_remove_node (SfiRing *head, SfiRing *node)
 
SfiRingsfi_ring_reverse (SfiRing *head)
 
SfiRingsfi_ring_remove (SfiRing *head, gpointer data)
 
guint sfi_ring_length (const SfiRing *head)
 
gint sfi_ring_cmp_length (const SfiRing *head, guint test_length)
 
SfiRingsfi_ring_find (const SfiRing *head, gconstpointer data)
 
SfiRingsfi_ring_nth (const SfiRing *head, guint n)
 
gpointer sfi_ring_nth_data (const SfiRing *head, guint n)
 
void sfi_ring_free_deep (SfiRing *head, GDestroyNotify data_destroy)
 
void sfi_ring_free (SfiRing *head)
 
gpointer sfi_ring_pop_head (SfiRing **head_p)
 
gpointer sfi_ring_pop_tail (SfiRing **head_p)
 
SfiRingsfi_ring_from_list (GList *list)
 
SfiRingsfi_ring_from_list_and_free (GList *list)
 
SfiRingsfi_ring_from_slist (GSList *slist)
 
SfiRingsfi_ring_from_slist_and_free (GSList *slist)
 
SfiRingsfi_ring_insert_sorted (SfiRing *head, gpointer insertion_data, SfiCompareFunc cmp, gpointer cmp_data)
 
SfiRingsfi_ring_merge_sorted (SfiRing *head1, SfiRing *head2, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_sort (SfiRing *head, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_uniq (SfiRing *sorted_ring1, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_uniq_free_deep (SfiRing *sorted_ring1, SfiCompareFunc cmp, gpointer data, GDestroyNotify data_destroy)
 
SfiRingsfi_ring_copy_deep_uniq (const SfiRing *sorted_ring1, SfiRingDataFunc copy, gpointer copy_data, SfiCompareFunc cmp, gpointer cmp_data)
 
SfiRingsfi_ring_copy_uniq (const SfiRing *sorted_ring1, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_union (const SfiRing *sorted_set1, const SfiRing *sorted_set2, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_intersection (const SfiRing *sorted_set1, const SfiRing *sorted_set2, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_difference (const SfiRing *sorted_set1, const SfiRing *sorted_set2, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_symmetric_difference (const SfiRing *sorted_set1, const SfiRing *sorted_set2, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_reorder (SfiRing *unordered_ring, const SfiRing *new_ring_order)
 
gboolean sfi_ring_includes (const SfiRing *sorted_super_set, const SfiRing *sorted_sub_set, SfiCompareFunc cmp, gpointer data)
 
gboolean sfi_ring_equals (const SfiRing *sorted_ring1, const SfiRing *sorted_ring2, SfiCompareFunc cmp, gpointer data)
 
gboolean sfi_ring_mismatch (SfiRing **sorted_ring1_p, SfiRing **sorted_ring2_p, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_ring_min_node (const SfiRing *head, SfiCompareFunc cmp, gpointer data)
 
SfiRingsfi_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)
 

Function Documentation

SfiRing* sfi_ring_difference ( const SfiRing sorted_set1,
const SfiRing sorted_set2,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_set1Sorted ring 1
sorted_set2Sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
Newly created (or empty) ring

Collect and return all data items from sorted_set1 which are not contained in 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))).

gboolean sfi_ring_equals ( const SfiRing sorted_ring1,
const SfiRing sorted_ring2,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_ring1Sorted ring 1
sorted_ring2Sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
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))).

SfiRing* sfi_ring_intersection ( const SfiRing sorted_set1,
const SfiRing sorted_set2,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_set1Sorted ring 1
sorted_set2Sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
Newly created (or empty) ring

Return a newly created ring that contains all data items which are contained in both sets, sorted_set1 and sorted_set2. Items are considered equal according to the cmp() function. For two equal items contained in both sets, the data pointer from 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))).

gpointer sfi_ring_max ( const SfiRing head,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
headHead node of a ring or NULL for an empty ring
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
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)).

Here is the call graph for this function:

SfiRing* sfi_ring_max_node ( const SfiRing head,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
headHead node of a ring or NULL for an empty ring
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
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)).

Referenced by sfi_ring_max().

Here is the caller graph for this function:

gpointer sfi_ring_min ( const SfiRing head,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
headHead node of a ring or NULL for an empty ring
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
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)).

Here is the call graph for this function:

SfiRing* sfi_ring_min_node ( const SfiRing head,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
headHead node of a ring or NULL for an empty ring
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
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)).

Referenced by sfi_ring_min().

Here is the caller graph for this function:

gboolean sfi_ring_mismatch ( SfiRing **  sorted_ring1_p,
SfiRing **  sorted_ring2_p,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_ring1_pPointer to sorted ring 1
sorted_ring2_pPointer to sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
TRUE for mismatching rings, FALSE otherwise

Compare two rings according to the cmp() function. For mismatching rings, sorted_ring1_p and sorted_ring2_p are set to point to the mismatching nodes. The complexity is at most O(MIN (length (sorted_ring1), length (sorted_ring2))).

SfiRing* sfi_ring_reorder ( SfiRing unordered_ring,
const SfiRing new_ring_order 
)
Parameters
unordered_ringUnsorted ring
new_ring_orderRing with arbitrary order
Returns
Reordered version of unordered_ring

Reorders the data pointers of unordered_ring according to the order as given by 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)).

Referenced by gsl_data_handle_get_state_length().

Here is the call graph for this function:

Here is the caller graph for this function:

SfiRing* sfi_ring_split ( SfiRing head1,
SfiRing head2 
)
Parameters
head1a non-empty ring
head2a ring node different from head1 contained in head1
returnshead2 for convenience

Split a ring into two parts, starting the second ring with head2. head2 must therefore be non-NULL and must be contained in the ring formed by head1.

Referenced by sfi_ring_split().

Here is the call graph for this function:

Here is the caller graph for this function:

SfiRing* sfi_ring_symmetric_difference ( const SfiRing sorted_set1,
const SfiRing sorted_set2,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_set1Sorted ring 1
sorted_set2Sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
Newly created (or empty) ring

Collect and return all data items from sorted_set1 which are not contained in sorted_set2, and all data items from sorted_set2 which are not contained in 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_union ( const SfiRing sorted_set1,
const SfiRing sorted_set2,
SfiCompareFunc  cmp,
gpointer  data 
)
Parameters
sorted_set1Sorted ring 1
sorted_set2Sorted ring 2
cmpCompare function for node data
dataData argument passed into the cmp() function
Returns
Newly created (or empty) ring

Return a newly created ring that contains all data items from sorted_set1 and 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 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))).