From 1da84c7e67535f42b422666802f3c22a622f89a4 Mon Sep 17 00:00:00 2001 From: Wim Taymans Date: Tue, 27 Sep 2005 17:00:13 +0000 Subject: [PATCH] docs/design/part-TODO.txt: Update TODO. Original commit message from CVS: * docs/design/part-TODO.txt: Update TODO. * gst/gstbin.c: (add_to_queue), (clear_queue), (reset_outdegree), (update_outdegree), (find_element), (gst_bin_sort_iterator_next), (gst_bin_sort_iterator_resync), (gst_bin_sort_iterator_free), (gst_bin_iterate_sorted), (gst_bin_element_set_state), (gst_bin_change_state): * gst/gstelement.h: Remove element variable, we keep element info in the iterator now. --- ChangeLog | 13 +++++++++++ docs/design/part-TODO.txt | 3 --- gst/gstbin.c | 57 +++++++++++++++++++++++++++++------------------ gst/gstelement.h | 4 ---- 4 files changed, 48 insertions(+), 29 deletions(-) diff --git a/ChangeLog b/ChangeLog index 13cb0e6..af0a353 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,16 @@ +2005-09-27 Wim Taymans + + * docs/design/part-TODO.txt: + Update TODO. + + * gst/gstbin.c: (add_to_queue), (clear_queue), (reset_outdegree), + (update_outdegree), (find_element), (gst_bin_sort_iterator_next), + (gst_bin_sort_iterator_resync), (gst_bin_sort_iterator_free), + (gst_bin_iterate_sorted), (gst_bin_element_set_state), + (gst_bin_change_state): + * gst/gstelement.h: + Remove element variable, we keep element info in the iterator now. + 2005-09-27 Andy Wingo * libs/gst/dataprotocol/dataprotocol.c: Fix error-checking return diff --git a/docs/design/part-TODO.txt b/docs/design/part-TODO.txt index 1acb746..107b6de 100644 --- a/docs/design/part-TODO.txt +++ b/docs/design/part-TODO.txt @@ -8,9 +8,6 @@ done by making the event contain a GstStructure with input/output values, similar to GstMessage. -- implement iterators for traversing elements upstream or dowstream. Use more simple - algorithm using indegree topological sort. - - unlinking pads in the PAUSED state needs to make sure the stream thread is not executing code. Can this be done with a flush to unlock all downstream chain functions? diff --git a/gst/gstbin.c b/gst/gstbin.c index b8c5df5..a580518 100644 --- a/gst/gstbin.c +++ b/gst/gstbin.c @@ -1057,22 +1057,30 @@ done: typedef struct _GstBinSortIterator { GstIterator it; - GQueue *queue; - GstBin *bin; - gint mode; - GstElement *best; + GQueue *queue; /* elements queued for state change */ + GstBin *bin; /* bin we iterate */ + gint mode; /* adding or removing dependency */ + GstElement *best; /* next element with least dependencies */ + gint best_deg; /* best degree */ + GHashTable *hash; /* has table with element dependencies */ } GstBinSortIterator; +/* we add and subtract 1 to make sure we don't confuse NULL and 0 */ +#define HASH_SET_DEGREE(bit, elem, deg) \ + g_hash_table_replace (bit->hash, elem, GINT_TO_POINTER(deg+1)) +#define HASH_GET_DEGREE(bit, elem) \ + (GPOINTER_TO_INT(g_hash_table_lookup (bit->hash, elem))-1) + /* add element to queue of next elements in the iterator. * We push at the tail to give higher priority elements a * chance first */ static void -add_to_queue (GQueue * queue, GstElement * element) +add_to_queue (GstBinSortIterator * bit, GstElement * element) { GST_DEBUG ("%s add to queue", GST_ELEMENT_NAME (element)); gst_object_ref (element); - g_queue_push_tail (queue, element); - element->outdegree = -1; + g_queue_push_tail (bit->queue, element); + HASH_SET_DEGREE (bit, element, -1); } /* clear the queue, unref all objects as we took a ref when @@ -1093,10 +1101,10 @@ reset_outdegree (GstElement * element, GstBinSortIterator * bit) { /* sinks are added right away */ if (GST_FLAG_IS_SET (element, GST_ELEMENT_IS_SINK)) { - add_to_queue (bit->queue, element); + add_to_queue (bit, element); } else { /* others are marked with 0 and handled when sinks are done */ - element->outdegree = 0; + HASH_SET_DEGREE (bit, element, 0); } } @@ -1129,17 +1137,21 @@ update_outdegree (GstElement * element, GstBinSortIterator * bit) GST_LOCK (peer_element); if (GST_OBJECT_CAST (peer_element)->parent == GST_OBJECT_CAST (bit->bin)) { + gint old_deg, new_deg; + + old_deg = HASH_GET_DEGREE (bit, peer_element); + new_deg = old_deg + bit->mode; GST_DEBUG ("change element %s, degree %d->%d, linked to %s", GST_ELEMENT_NAME (peer_element), - peer_element->outdegree, peer_element->outdegree + bit->mode, - GST_ELEMENT_NAME (element)); + old_deg, new_deg, GST_ELEMENT_NAME (element)); /* update outdegree */ - peer_element->outdegree += bit->mode; - if (peer_element->outdegree == 0) { + if (new_deg == 0) { /* outdegree hit 0, add to queue */ - add_to_queue (bit->queue, peer_element); + add_to_queue (bit, peer_element); + } else { + HASH_SET_DEGREE (bit, peer_element, new_deg); } linked = TRUE; } @@ -1164,12 +1176,13 @@ find_element (GstElement * element, GstBinSortIterator * bit) gint outdegree; /* element is already handled */ - if ((outdegree = element->outdegree) < 0) + if ((outdegree = HASH_GET_DEGREE (bit, element)) < 0) return; /* first element or element with smaller outdegree */ - if (bit->best == NULL || bit->best->outdegree > outdegree) { + if (bit->best == NULL || bit->best_deg > outdegree) { bit->best = element; + bit->best_deg = outdegree; } } @@ -1181,16 +1194,17 @@ gst_bin_sort_iterator_next (GstBinSortIterator * bit, gpointer * result) /* empty queue, we have to find a next best element */ if (g_queue_is_empty (bit->queue)) { bit->best = NULL; + bit->best_deg = G_MAXINT; g_list_foreach (bit->bin->children, (GFunc) find_element, bit); if (bit->best) { - if (bit->best->outdegree != 0) { + if (bit->best_deg != 0) { /* we don't fail on this one yet */ g_warning ("loop detected in the graph !!"); } - /* best unhandled elements, add to queue */ + /* best unhandled elements, scheduler as next element */ GST_DEBUG ("queue empty, next best: %s", GST_ELEMENT_NAME (bit->best)); gst_object_ref (bit->best); - bit->best->outdegree = -1; + HASH_SET_DEGREE (bit, bit->best, -1); *result = bit->best; } else { GST_DEBUG ("queue empty, elements exhausted"); @@ -1229,6 +1243,7 @@ gst_bin_sort_iterator_free (GstBinSortIterator * bit) { clear_queue (bit->queue); g_queue_free (bit->queue); + g_hash_table_destroy (bit->hash); gst_object_unref (bit->bin); g_free (bit); } @@ -1249,9 +1264,6 @@ gst_bin_sort_iterator_free (GstBinSortIterator * bit) * * MT safe. * - * FIXME: No two iterators can run at the same time since the iterators - * use a shared element field. - * * Returns: a #GstIterator of #GstElements. gst_iterator_free after use. */ GstIterator * @@ -1274,6 +1286,7 @@ gst_bin_iterate_sorted (GstBin * bin) (GstIteratorResyncFunction) gst_bin_sort_iterator_resync, (GstIteratorFreeFunction) gst_bin_sort_iterator_free); result->queue = g_queue_new (); + result->hash = g_hash_table_new (NULL, NULL); result->bin = bin; gst_bin_sort_iterator_resync (result); GST_UNLOCK (bin); diff --git a/gst/gstelement.h b/gst/gstelement.h index bd50dd5..9fc355f 100644 --- a/gst/gstelement.h +++ b/gst/gstelement.h @@ -304,10 +304,6 @@ struct _GstElement GList *sinkpads; guint32 pads_cookie; - /* used in bin state change to calculate number of connections - * on the srcpad */ - gint outdegree; - /*< private >*/ gpointer _gst_reserved[GST_PADDING]; }; -- 2.7.4