@@ -216,3 +216,45 @@ Links have flags that describe the link capabilities and state.
modified at runtime. If MEDIA_LNK_FL_IMMUTABLE is set, then
MEDIA_LNK_FL_ENABLED must also be set since an immutable link is always
enabled.
+
+
+Graph traversal
+---------------
+
+The media framework provides APIs to iterate over entities in a graph.
+
+To iterate over all entities belonging to a media device, drivers can use the
+media_device_for_each_entity macro, defined in include/media/media-device.h.
+
+ struct media_entity *entity;
+
+ media_device_for_each_entity(entity, mdev) {
+ /* entity will point to each entity in turn */
+ ...
+ }
+
+Drivers might also need to iterate over all entities in a graph that can be
+reached only through enabled links starting at a given entity. The media
+framework provides a depth-first graph traversal API for that purpose.
+
+Note that graphs with cycles (whether directed or undirected) are *NOT*
+supported by the graph traversal API. To prevent infinite loops, the graph
+traversal code limits the maximum depth to MEDIA_ENTITY_ENUM_MAX_DEPTH,
+currently defined as 16.
+
+Drivers initiate a graph traversal by calling
+
+ media_entity_graph_walk_start(struct media_entity_graph *graph,
+ struct media_entity *entity);
+
+The graph structure, provided by the caller, is initialized to start graph
+traversal at the given entity.
+
+Drivers can then retrieve the next entity by calling
+
+ media_entity_graph_walk_next(struct media_entity_graph *graph);
+
+When the graph traversal is complete the function will return NULL.
+
+Graph traversal can be interrupted at any moment. No cleanup function call is
+required and the graph structure can be freed normally.
@@ -84,6 +84,121 @@ media_entity_cleanup(struct media_entity *entity)
}
EXPORT_SYMBOL_GPL(media_entity_cleanup);
+/* -----------------------------------------------------------------------------
+ * Graph traversal
+ */
+
+static struct media_entity *
+media_entity_other(struct media_entity *entity, struct media_link *link)
+{
+ if (link->source->entity == entity)
+ return link->sink->entity;
+ else
+ return link->source->entity;
+}
+
+/* push an entity to traversal stack */
+static void stack_push(struct media_entity_graph *graph,
+ struct media_entity *entity)
+{
+ if (graph->top == MEDIA_ENTITY_ENUM_MAX_DEPTH - 1) {
+ WARN_ON(1);
+ return;
+ }
+ graph->top++;
+ graph->stack[graph->top].link = 0;
+ graph->stack[graph->top].entity = entity;
+}
+
+static struct media_entity *stack_pop(struct media_entity_graph *graph)
+{
+ struct media_entity *entity;
+
+ entity = graph->stack[graph->top].entity;
+ graph->top--;
+
+ return entity;
+}
+
+#define stack_peek(en) ((en)->stack[(en)->top - 1].entity)
+#define link_top(en) ((en)->stack[(en)->top].link)
+#define stack_top(en) ((en)->stack[(en)->top].entity)
+
+/**
+ * media_entity_graph_walk_start - Start walking the media graph at a given entity
+ * @graph: Media graph structure that will be used to walk the graph
+ * @entity: Starting entity
+ *
+ * This function initializes the graph traversal structure to walk the entities
+ * graph starting at the given entity. The traversal structure must not be
+ * modified by the caller during graph traversal. When done the structure can
+ * safely be freed.
+ */
+void media_entity_graph_walk_start(struct media_entity_graph *graph,
+ struct media_entity *entity)
+{
+ graph->top = 0;
+ graph->stack[graph->top].entity = NULL;
+ stack_push(graph, entity);
+}
+EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
+
+/**
+ * media_entity_graph_walk_next - Get the next entity in the graph
+ * @graph: Media graph structure
+ *
+ * Perform a depth-first traversal of the given media entities graph.
+ *
+ * The graph structure must have been previously initialized with a call to
+ * media_entity_graph_walk_start().
+ *
+ * Return the next entity in the graph or NULL if the whole graph have been
+ * traversed.
+ */
+struct media_entity *
+media_entity_graph_walk_next(struct media_entity_graph *graph)
+{
+ if (stack_top(graph) == NULL)
+ return NULL;
+
+ /*
+ * Depth first search. Push entity to stack and continue from
+ * top of the stack until no more entities on the level can be
+ * found.
+ */
+ while (link_top(graph) < stack_top(graph)->num_links) {
+ struct media_entity *entity = stack_top(graph);
+ struct media_link *link = &entity->links[link_top(graph)];
+ struct media_entity *next;
+
+ /* The link is not enabled so we do not follow. */
+ if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
+ link_top(graph)++;
+ continue;
+ }
+
+ /* Get the entity in the other end of the link . */
+ next = media_entity_other(entity, link);
+
+ /* Was it the entity we came here from? */
+ if (next == stack_peek(graph)) {
+ link_top(graph)++;
+ continue;
+ }
+
+ /* Push the new entity to stack and start over. */
+ link_top(graph)++;
+ stack_push(graph, next);
+ }
+
+ return stack_pop(graph);
+}
+EXPORT_SYMBOL_GPL(media_entity_graph_walk_next);
+
+/* -----------------------------------------------------------------------------
+ * Links management
+ */
+
static struct media_link *media_entity_add_link(struct media_entity *entity)
{
if (entity->num_links >= entity->max_links) {
@@ -113,10 +113,25 @@ static inline u32 media_entity_subtype(struct media_entity *entity)
return entity->type & MEDIA_ENT_SUBTYPE_MASK;
}
+#define MEDIA_ENTITY_ENUM_MAX_DEPTH 16
+
+struct media_entity_graph {
+ struct {
+ struct media_entity *entity;
+ int link;
+ } stack[MEDIA_ENTITY_ENUM_MAX_DEPTH];
+ int top;
+};
+
int media_entity_init(struct media_entity *entity, u16 num_pads,
struct media_pad *pads, u16 extra_links);
void media_entity_cleanup(struct media_entity *entity);
int media_entity_create_link(struct media_entity *source, u16 source_pad,
struct media_entity *sink, u16 sink_pad, u32 flags);
+void media_entity_graph_walk_start(struct media_entity_graph *graph,
+ struct media_entity *entity);
+struct media_entity *
+media_entity_graph_walk_next(struct media_entity_graph *graph);
+
#endif