diff options
| -rw-r--r-- | Documentation/media-framework.txt | 42 | ||||
| -rw-r--r-- | drivers/media/media-entity.c | 115 | ||||
| -rw-r--r-- | include/media/media-entity.h | 15 |
3 files changed, 172 insertions, 0 deletions
diff --git a/Documentation/media-framework.txt b/Documentation/media-framework.txt index 0257bad..ab17f33 100644 --- a/Documentation/media-framework.txt +++ b/Documentation/media-framework.txt @@ -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. diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c index 5c31df9..166f2b5 100644 --- a/drivers/media/media-entity.c +++ b/drivers/media/media-entity.c @@ -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) { diff --git a/include/media/media-entity.h b/include/media/media-entity.h index f6c856c..28f61f6 100644 --- a/include/media/media-entity.h +++ b/include/media/media-entity.h @@ -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 |
