Em 20-08-2010 12:29, Laurent Pinchart escreveu:
> From: Sakari Ailus <sakari.ailus@xxxxxxxxxxxxxxxxxxxxxxxxxx>
>
> Add media entity graph traversal. The traversal follows active links by
> depth first. Traversing graph backwards is prevented by comparing the next
> possible entity in the graph with the previous one. Multiply connected
> graphs are thus not supported.
>
> Signed-off-by: Sakari Ailus <sakari.ailus@xxxxxxxxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Laurent Pinchart <laurent.pinchart@xxxxxxxxxxxxxxxx>
> Signed-off-by: Vimarsh Zutshi <vimarsh.zutshi@xxxxxxxxx>
> ---
> Documentation/media-framework.txt | 40 +++++++++++++
> drivers/media/media-entity.c | 115 +++++++++++++++++++++++++++++++++++++
> include/media/media-entity.h | 15 +++++
> 3 files changed, 170 insertions(+), 0 deletions(-)
>
> diff --git a/Documentation/media-framework.txt b/Documentation/media-framework.txt
> index 35d74e4..a599824 100644
> --- a/Documentation/media-framework.txt
> +++ b/Documentation/media-framework.txt
> @@ -238,3 +238,43 @@ Links have flags that describe the link capabilities and state.
> MEDIA_LINK_FLAG_ACTIVE must also be set since an immutable link is
> always active.
>
> +
> +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 active 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.
Please document that a maximum depth exists to prevent loops, currently
defined as 16 (MEDIA_ENTITY_ENUM_MAX_DEPTH).
> +
> +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.
> +
> diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
> index 541063b..c277c18 100644
> --- a/drivers/media/media-entity.c
> +++ b/drivers/media/media-entity.c
> @@ -82,6 +82,121 @@ media_entity_cleanup(struct media_entity *entity)
> }
> EXPORT_SYMBOL(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 active so we do not follow. */
> + if (!(link->flags & MEDIA_LINK_FLAG_ACTIVE)) {
> + 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) {
> diff --git a/include/media/media-entity.h b/include/media/media-entity.h
> index 32bb20a..3a7c74d 100644
> --- a/include/media/media-entity.h
> +++ b/include/media/media-entity.h
> @@ -87,10 +87,25 @@ static inline u32 media_entity_subtype(struct media_entity *entity)
> return entity->type & MEDIA_ENTITY_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
--
To unsubscribe from this list: send the line "unsubscribe linux-media" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
