linux-omap 2.6.37: sync with OE .dev
[glsdk/meta-ti-glsdk.git] / recipes-bsp / linux / linux-omap / media / 0011-media-Entity-graph-traversal.patch
1 From 5b45472e8a692e6acea3cb6d601b44c17ea8d59e Mon Sep 17 00:00:00 2001
2 From: Sakari Ailus <sakari.ailus@maxwell.research.nokia.com>
3 Date: Sun, 7 Mar 2010 21:14:14 +0200
4 Subject: [PATCH 11/43] media: Entity graph traversal
6 Add media entity graph traversal. The traversal follows enabled links by
7 depth first. Traversing graph backwards is prevented by comparing the next
8 possible entity in the graph with the previous one. Multiply connected
9 graphs are thus not supported.
11 Signed-off-by: Sakari Ailus <sakari.ailus@maxwell.research.nokia.com>
12 Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
13 Signed-off-by: Vimarsh Zutshi <vimarsh.zutshi@nokia.com>
14 ---
15  Documentation/media-framework.txt |   42 +++++++++++++
16  drivers/media/media-entity.c      |  115 +++++++++++++++++++++++++++++++++++++
17  include/media/media-entity.h      |   15 +++++
18  3 files changed, 172 insertions(+), 0 deletions(-)
20 diff --git a/Documentation/media-framework.txt b/Documentation/media-framework.txt
21 index b252cf9..88fe379 100644
22 --- a/Documentation/media-framework.txt
23 +++ b/Documentation/media-framework.txt
24 @@ -216,3 +216,45 @@ Links have flags that describe the link capabilities and state.
25         modified at runtime. If MEDIA_LNK_FL_IMMUTABLE is set, then
26         MEDIA_LNK_FL_ENABLED must also be set since an immutable link is always
27         enabled.
28 +
29 +
30 +Graph traversal
31 +---------------
32 +
33 +The media framework provides APIs to iterate over entities in a graph.
34 +
35 +To iterate over all entities belonging to a media device, drivers can use the
36 +media_device_for_each_entity macro, defined in include/media/media-device.h.
37 +
38 +       struct media_entity *entity;
39 +
40 +       media_device_for_each_entity(entity, mdev) {
41 +               /* entity will point to each entity in turn */
42 +               ...
43 +       }
44 +
45 +Drivers might also need to iterate over all entities in a graph that can be
46 +reached only through enabled links starting at a given entity. The media
47 +framework provides a depth-first graph traversal API for that purpose.
48 +
49 +Note that graphs with cycles (whether directed or undirected) are *NOT*
50 +supported by the graph traversal API. To prevent infinite loops, the graph
51 +traversal code limits the maximum depth to MEDIA_ENTITY_ENUM_MAX_DEPTH,
52 +currently defined as 16.
53 +
54 +Drivers initiate a graph traversal by calling
55 +
56 +       media_entity_graph_walk_start(struct media_entity_graph *graph,
57 +                                     struct media_entity *entity);
58 +
59 +The graph structure, provided by the caller, is initialized to start graph
60 +traversal at the given entity.
61 +
62 +Drivers can then retrieve the next entity by calling
63 +
64 +       media_entity_graph_walk_next(struct media_entity_graph *graph);
65 +
66 +When the graph traversal is complete the function will return NULL.
67 +
68 +Graph traversal can be interrupted at any moment. No cleanup function call is
69 +required and the graph structure can be freed normally.
70 diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
71 index e4ba2bc..a805f20 100644
72 --- a/drivers/media/media-entity.c
73 +++ b/drivers/media/media-entity.c
74 @@ -84,6 +84,121 @@ media_entity_cleanup(struct media_entity *entity)
75  }
76  EXPORT_SYMBOL_GPL(media_entity_cleanup);
77  
78 +/* -----------------------------------------------------------------------------
79 + * Graph traversal
80 + */
81 +
82 +static struct media_entity *
83 +media_entity_other(struct media_entity *entity, struct media_link *link)
84 +{
85 +       if (link->source->entity == entity)
86 +               return link->sink->entity;
87 +       else
88 +               return link->source->entity;
89 +}
90 +
91 +/* push an entity to traversal stack */
92 +static void stack_push(struct media_entity_graph *graph,
93 +                      struct media_entity *entity)
94 +{
95 +       if (graph->top == MEDIA_ENTITY_ENUM_MAX_DEPTH - 1) {
96 +               WARN_ON(1);
97 +               return;
98 +       }
99 +       graph->top++;
100 +       graph->stack[graph->top].link = 0;
101 +       graph->stack[graph->top].entity = entity;
102 +}
104 +static struct media_entity *stack_pop(struct media_entity_graph *graph)
105 +{
106 +       struct media_entity *entity;
108 +       entity = graph->stack[graph->top].entity;
109 +       graph->top--;
111 +       return entity;
112 +}
114 +#define stack_peek(en) ((en)->stack[(en)->top - 1].entity)
115 +#define link_top(en)   ((en)->stack[(en)->top].link)
116 +#define stack_top(en)  ((en)->stack[(en)->top].entity)
118 +/**
119 + * media_entity_graph_walk_start - Start walking the media graph at a given entity
120 + * @graph: Media graph structure that will be used to walk the graph
121 + * @entity: Starting entity
122 + *
123 + * This function initializes the graph traversal structure to walk the entities
124 + * graph starting at the given entity. The traversal structure must not be
125 + * modified by the caller during graph traversal. When done the structure can
126 + * safely be freed.
127 + */
128 +void media_entity_graph_walk_start(struct media_entity_graph *graph,
129 +                                  struct media_entity *entity)
130 +{
131 +       graph->top = 0;
132 +       graph->stack[graph->top].entity = NULL;
133 +       stack_push(graph, entity);
134 +}
135 +EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
137 +/**
138 + * media_entity_graph_walk_next - Get the next entity in the graph
139 + * @graph: Media graph structure
140 + *
141 + * Perform a depth-first traversal of the given media entities graph.
142 + *
143 + * The graph structure must have been previously initialized with a call to
144 + * media_entity_graph_walk_start().
145 + *
146 + * Return the next entity in the graph or NULL if the whole graph have been
147 + * traversed.
148 + */
149 +struct media_entity *
150 +media_entity_graph_walk_next(struct media_entity_graph *graph)
151 +{
152 +       if (stack_top(graph) == NULL)
153 +               return NULL;
155 +       /*
156 +        * Depth first search. Push entity to stack and continue from
157 +        * top of the stack until no more entities on the level can be
158 +        * found.
159 +        */
160 +       while (link_top(graph) < stack_top(graph)->num_links) {
161 +               struct media_entity *entity = stack_top(graph);
162 +               struct media_link *link = &entity->links[link_top(graph)];
163 +               struct media_entity *next;
165 +               /* The link is not enabled so we do not follow. */
166 +               if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
167 +                       link_top(graph)++;
168 +                       continue;
169 +               }
171 +               /* Get the entity in the other end of the link . */
172 +               next = media_entity_other(entity, link);
174 +               /* Was it the entity we came here from? */
175 +               if (next == stack_peek(graph)) {
176 +                       link_top(graph)++;
177 +                       continue;
178 +               }
180 +               /* Push the new entity to stack and start over. */
181 +               link_top(graph)++;
182 +               stack_push(graph, next);
183 +       }
185 +       return stack_pop(graph);
186 +}
187 +EXPORT_SYMBOL_GPL(media_entity_graph_walk_next);
189 +/* -----------------------------------------------------------------------------
190 + * Links management
191 + */
193  static struct media_link *media_entity_add_link(struct media_entity *entity)
194  {
195         if (entity->num_links >= entity->max_links) {
196 diff --git a/include/media/media-entity.h b/include/media/media-entity.h
197 index 7cf9135..b82f824 100644
198 --- a/include/media/media-entity.h
199 +++ b/include/media/media-entity.h
200 @@ -113,10 +113,25 @@ static inline u32 media_entity_subtype(struct media_entity *entity)
201         return entity->type & MEDIA_ENT_SUBTYPE_MASK;
202  }
203  
204 +#define MEDIA_ENTITY_ENUM_MAX_DEPTH    16
206 +struct media_entity_graph {
207 +       struct {
208 +               struct media_entity *entity;
209 +               int link;
210 +       } stack[MEDIA_ENTITY_ENUM_MAX_DEPTH];
211 +       int top;
212 +};
214  int media_entity_init(struct media_entity *entity, u16 num_pads,
215                 struct media_pad *pads, u16 extra_links);
216  void media_entity_cleanup(struct media_entity *entity);
217  int media_entity_create_link(struct media_entity *source, u16 source_pad,
218                 struct media_entity *sink, u16 sink_pad, u32 flags);
219  
220 +void media_entity_graph_walk_start(struct media_entity_graph *graph,
221 +               struct media_entity *entity);
222 +struct media_entity *
223 +media_entity_graph_walk_next(struct media_entity_graph *graph);
225  #endif
226 -- 
227 1.6.6.1