recipes-kernel/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
   5
   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.
  10
  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(-)
  19
  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 +}
 103 +
 104 +static struct media_entity *stack_pop(struct media_entity_graph *graph)
 105 +{
 106 +       struct media_entity *entity;
 107 +
 108 +       entity = graph->stack[graph->top].entity;
 109 +       graph->top--;
 110 +
 111 +       return entity;
 112 +}
 113 +
 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)
 117 +
 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);
 136 +
 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;
 154 +
 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;
 164 +
 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 +               }
 170 +
 171 +               /* Get the entity in the other end of the link . */
 172 +               next = media_entity_other(entity, link);
 173 +
 174 +               /* Was it the entity we came here from? */
 175 +               if (next == stack_peek(graph)) {
 176 +                       link_top(graph)++;
 177 +                       continue;
 178 +               }
 179 +
 180 +               /* Push the new entity to stack and start over. */
 181 +               link_top(graph)++;
 182 +               stack_push(graph, next);
 183 +       }
 184 +
 185 +       return stack_pop(graph);
 186 +}
 187 +EXPORT_SYMBOL_GPL(media_entity_graph_walk_next);
 188 +
 189 +/* -----------------------------------------------------------------------------
 190 + * Links management
 191 + */
 192 +
 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
 205 +
 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 +};
 213 +
 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);
 224 +
 225  #endif
 226 --
 227 1.6.6.1
 228