From patchwork Thu Jul 29 16:06:37 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Laurent Pinchart X-Patchwork-Id: 115237 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter.kernel.org (8.14.4/8.14.3) with ESMTP id o6TG8lQD005669 for ; Thu, 29 Jul 2010 16:08:48 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757952Ab0G2QHJ (ORCPT ); Thu, 29 Jul 2010 12:07:09 -0400 Received: from perceval.irobotique.be ([92.243.18.41]:36475 "EHLO perceval.irobotique.be" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757943Ab0G2QHG (ORCPT ); Thu, 29 Jul 2010 12:07:06 -0400 Received: from localhost.localdomain (unknown [91.178.154.203]) by perceval.irobotique.be (Postfix) with ESMTPSA id 71F3735E01; Thu, 29 Jul 2010 16:07:03 +0000 (UTC) From: Laurent Pinchart To: linux-media@vger.kernel.org Cc: sakari.ailus@maxwell.research.nokia.com Subject: [RFC/PATCH v3 04/10] media: Entity graph traversal Date: Thu, 29 Jul 2010 18:06:37 +0200 Message-Id: <1280419616-7658-5-git-send-email-laurent.pinchart@ideasonboard.com> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1280419616-7658-1-git-send-email-laurent.pinchart@ideasonboard.com> References: <1280419616-7658-1-git-send-email-laurent.pinchart@ideasonboard.com> Sender: linux-media-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-media@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.3 (demeter.kernel.org [140.211.167.41]); Thu, 29 Jul 2010 16:08:48 +0000 (UTC) diff --git a/Documentation/media-framework.txt b/Documentation/media-framework.txt index 5bd7216..4fe3b32 100644 --- a/Documentation/media-framework.txt +++ b/Documentation/media-framework.txt @@ -196,3 +196,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. + +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 a2f9ad9..443c5c9 100644 --- a/drivers/media/media-entity.c +++ b/drivers/media/media-entity.c @@ -81,6 +81,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 37a25bf..05c37a6 100644 --- a/include/media/media-entity.h +++ b/include/media/media-entity.h @@ -76,10 +76,25 @@ struct media_entity { #define media_entity_subtype(entity) \ ((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, u8 num_pads, struct media_pad *pads, u8 extra_links); void media_entity_cleanup(struct media_entity *entity); int media_entity_create_link(struct media_entity *source, u8 source_pad, struct media_entity *sink, u8 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