gst/autoplug/gstsearchfuncs.c

   1 /* GStreamer
   2  * Copyright (C) 1999-2002 Erik Walthinsen <omega@cse.ogi.edu>
   3  *               2000-2002 Wim Taymans <wtay@chello.be>
   4  *
   5  * gstsearchfuncs.c: functions needed when doing searches while
   6  *                   autoplugging
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Library General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Library General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Library General Public
  19  * License along with this library; if not, write to the
  20  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  21  * Boston, MA 02111-1307, USA.
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #  include "config.h"
  26 #endif
  27
  28 #include "gstsearchfuncs.h"
  29
  30 /* FIXME: "evil hack" alarm, we need a better way to get a category in here */
  31 #ifndef GST_DISABLE_GST_DEBUG
  32 extern GstDebugCategory *GST_CAT_AUTOPLUG_ATTEMPT;
  33 #define GST_CAT_DEFAULT GST_CAT_AUTOPLUG_ATTEMPT
  34 #endif
  35
  36 /* function that really misses in GLib
  37  * though the GLib version should take a function as argument...
  38  */
  39 static void
  40 g_list_free_list_and_elements (GList *list)
  41 {
  42   GList *walk = list;
  43
  44   while (walk)
  45   {
  46     g_free (walk->data);
  47     walk = g_list_next (walk);
  48   }
  49   g_list_free (list);
  50 }
  51 /**
  52  * gst_autoplug_caps_intersect:
  53  * @src: a source #GstCaps
  54  * @sink: the sink #GstCaps
  55  *
  56  * Checks if the given caps have a non-null intersection.
  57  *
  58  * Returns: TRUE, if both caps intersect.
  59  */
  60 gboolean
  61 gst_autoplug_caps_intersect (const GstCaps *src, const GstCaps *sink)
  62 {
  63   GstCaps *caps;
  64
  65   /* if there are no caps, we can link */
  66   if ((src == NULL) && (sink == NULL))
  67     return TRUE;
  68
  69   /* get an intersection */
  70   caps = gst_caps_intersect (src, sink);
  71
  72   /* if the caps can't link, there is no intersection */
  73   if (caps == NULL)
  74     return FALSE;
  75
  76   /* hurrah, we can link, now remove the intersection */
  77   gst_caps_free (caps);
  78   return TRUE;
  79 }
  80
  81 /**
  82  * gst_autoplug_can_connect_src:
  83  * @fac: factory to connect to
  84  * @src: caps to check
  85  *
  86  * Checks if a factory's sink can connect to the given caps
  87  *
  88  * Returns: #GstPadTemplate that can connect to the given caps
  89  */
  90 GstPadTemplate *
  91 gst_autoplug_can_connect_src (GstElementFactory *fac, const GstCaps *src)
  92 {
  93   GList *templs;
  94
  95   templs = fac->padtemplates;
  96
  97   while (templs)
  98   {
  99     if ((GST_PAD_TEMPLATE_DIRECTION (templs->data) == GST_PAD_SINK) &&
 100         gst_autoplug_caps_intersect (src,
 101                                      GST_PAD_TEMPLATE_CAPS (templs->data)))
 102     {
 103       return GST_PAD_TEMPLATE (templs->data);
 104     }
 105     templs = g_list_next (templs);
 106   }
 107
 108   return NULL;
 109 }
 110 /**
 111  * gst_autoplug_can_connect_sink:
 112  * @fac: factory to connect to
 113  * @sink: caps to check
 114  *
 115  * Checks if a factory's src can connect to the given caps
 116  *
 117  * Returns: #GstPadTemplate that can connect to the given caps
 118  */
 119 GstPadTemplate *
 120 gst_autoplug_can_connect_sink (GstElementFactory *fac, const GstCaps *sink)
 121 {
 122   GList *templs;
 123
 124   templs = fac->padtemplates;
 125
 126   while (templs)
 127   {
 128     GstCaps *caps = GST_PAD_TEMPLATE_CAPS (templs->data);
 129     if ((GST_PAD_TEMPLATE_DIRECTION (templs->data) == GST_PAD_SRC) &&
 130         gst_autoplug_caps_intersect (caps, sink))
 131     {
 132       return GST_PAD_TEMPLATE (templs->data);
 133     }
 134     templs = g_list_next (templs);
 135   }
 136
 137   return NULL;
 138 }
 139 GstPadTemplate *
 140 gst_autoplug_can_match (GstElementFactory *src, GstElementFactory *dest)
 141 {
 142   GList *srctemps, *desttemps;
 143
 144   srctemps = src->padtemplates;
 145
 146   while (srctemps) {
 147     GstPadTemplate *srctemp = (GstPadTemplate *)srctemps->data;
 148
 149     desttemps = dest->padtemplates;
 150
 151     while (desttemps) {
 152       GstPadTemplate *desttemp = (GstPadTemplate *)desttemps->data;
 153
 154       if (srctemp->direction == GST_PAD_SRC &&
 155           desttemp->direction == GST_PAD_SINK) {
 156           if (gst_autoplug_caps_intersect (gst_pad_template_get_caps (srctemp),
 157               gst_pad_template_get_caps (desttemp))) {
 158             GST_DEBUG ("factory \"%s\" can connect with factory \"%s\"",
 159                        GST_OBJECT_NAME (src), GST_OBJECT_NAME (dest));
 160             return desttemp;
 161          }
 162       }
 163
 164       desttemps = g_list_next (desttemps);
 165     }
 166     srctemps = g_list_next (srctemps);
 167   }
 168   GST_DEBUG ("factory \"%s\" cannot connect with factory \"%s\"",
 169              GST_OBJECT_NAME (src), GST_OBJECT_NAME (dest));
 170   return NULL;
 171 }
 172
 173 /* returns TRUE if the factory has padtemplates with the specified direction */
 174 gboolean
 175 gst_autoplug_factory_has_direction (GstElementFactory *fac, GstPadDirection dir)
 176 {
 177   GList *templs = fac->padtemplates;
 178
 179   while (templs)
 180   {
 181     if (GST_PAD_TEMPLATE_DIRECTION (templs->data) == dir)
 182     {
 183       return TRUE;
 184     }
 185     templs = g_list_next (templs);
 186   }
 187
 188   return FALSE;
 189 }
 190
 191 /* Decisions are based on the padtemplates.
 192  * These functions return a new list so be sure to free it.
 193  */
 194 GList *
 195 gst_autoplug_factories_sinks (GList *factories)
 196 {
 197   GList *ret = NULL;
 198
 199   while (factories)
 200   {
 201     if (gst_autoplug_factory_has_sink (factories->data))
 202       ret = g_list_prepend (ret, factories->data);
 203     factories = g_list_next (factories);
 204   }
 205   return ret;
 206 }
 207 GList *
 208 gst_autoplug_factories_srcs (GList *factories)
 209 {
 210   GList *ret = NULL;
 211
 212   while (factories)
 213   {
 214     if (gst_autoplug_factory_has_src (factories->data))
 215       ret = g_list_prepend (ret, factories->data);
 216     factories = g_list_next (factories);
 217   }
 218   return ret;
 219 }
 220 GList *
 221 gst_autoplug_factories_filters (GList *factories)
 222 {
 223   GList *ret = NULL;
 224
 225   while (factories)
 226   {
 227     /* if you want it faster do src/sink check at once, don't call two functions */
 228     if (gst_autoplug_factory_has_src (factories->data) && gst_autoplug_factory_has_sink (factories->data))
 229       ret = g_list_prepend (ret, factories->data);
 230     factories = g_list_next (factories);
 231   }
 232   return ret;
 233 }
 234
 235
 236 static gint
 237 gst_autoplug_rank_compare (const GstElementFactory *a, const GstElementFactory *b)
 238 {
 239         if (GST_PLUGIN_FEATURE (a)->rank > GST_PLUGIN_FEATURE (b)->rank) return -1;
 240         return (GST_PLUGIN_FEATURE (a)->rank < GST_PLUGIN_FEATURE (b)->rank) ? 1 : 0;
 241 }
 242
 243 /* returns all factories which have sinks with non-NULL caps and srcs with
 244  * any caps. also only returns factories with a non-zero rank, and sorts by
 245  * rank descending.
 246  */
 247 GList *
 248 gst_autoplug_factories_filters_with_sink_caps (GList *factories)
 249 {
 250   GList *ret = NULL;
 251   GstElementFactory *factory;
 252   GList *templs;
 253
 254   while (factories)
 255   {
 256     factory = (GstElementFactory *) factories->data;
 257     templs = factory->padtemplates;
 258
 259     if (GST_PLUGIN_FEATURE (factory)->rank > 0){
 260       gboolean have_src = FALSE;
 261       gboolean have_sink = FALSE;
 262
 263       while (templs)
 264       {
 265         if (GST_PAD_TEMPLATE_DIRECTION (templs->data) == GST_PAD_SRC)
 266         {
 267           have_src = TRUE;
 268         }
 269         if ((GST_PAD_TEMPLATE_DIRECTION (templs->data) == GST_PAD_SINK) && (GST_PAD_TEMPLATE_CAPS (templs->data) != NULL))
 270         {
 271           have_sink = TRUE;
 272         }
 273         if (have_src && have_sink)
 274         {
 275           ret = g_list_prepend (ret, factory);
 276           break;
 277         }
 278         templs = g_list_next (templs);
 279       }
 280     }
 281     factories = g_list_next (factories);
 282   }
 283   return g_list_sort(ret, (GCompareFunc)gst_autoplug_rank_compare);
 284 }
 285
 286
 287
 288 /* returns all factories which have a maximum of maxtemplates GstPadTemplates in direction dir
 289  */
 290 GList *
 291 gst_autoplug_factories_at_most_templates(GList *factories, GstPadDirection dir, guint maxtemplates)
 292 {
 293   GList *ret = NULL;
 294
 295   while (factories)
 296   {
 297     guint count = 0;
 298     GList *templs = ((GstElementFactory *) factories->data)->padtemplates;
 299
 300     while (templs)
 301     {
 302       if (GST_PAD_TEMPLATE_DIRECTION (templs->data) == dir)
 303       {
 304         count++;
 305       }
 306       if (count > maxtemplates)
 307         break;
 308       templs = g_list_next (templs);
 309     }
 310     if (count <= maxtemplates)
 311       ret = g_list_prepend (ret, factories->data);
 312
 313     factories = g_list_next (factories);
 314   }
 315   return ret;
 316 }
 317 /*********************************************************************
 318  *
 319  * SHORTEST PATH ALGORITHM
 320  */
 321 /**
 322  * gst_autoplug_sp:
 323  * @src_caps: a #GstCaps to plug from.
 324  * @sink_caps: the #GstCaps to plug to.
 325  * @factories: a #GList containing all allowed #GstElementFactory entries.
 326  *
 327  * Finds the shortest path of elements that together make up a possible
 328  * connection between the source and sink caps.
 329  *
 330  * Returns: a #GList of #GstElementFactory items which have to be connected
 331  * to get the shortest path.
 332  */
 333 GList *
 334 gst_autoplug_sp (const GstCaps *srccaps, const GstCaps *sinkcaps, GList *factories)
 335 {
 336   GList *factory_nodes = NULL;
 337   guint curcost = GST_AUTOPLUG_MAX_COST; /* below this cost, there is no path */
 338   GstAutoplugNode *bestnode = NULL; /* best (unconnected) endpoint currently */
 339
 340   g_return_val_if_fail (srccaps != NULL, NULL);
 341   g_return_val_if_fail (sinkcaps != NULL, NULL);
 342
 343   GST_INFO ("attempting to autoplug via shortest path from %s to %s",
 344                   gst_caps_to_string(srccaps), gst_caps_to_string(sinkcaps));
 345
 346   /* wrap all factories as GstAutoplugNode
 347    * initialize the cost */
 348   while (factories)
 349   {
 350     GstAutoplugNode *node = g_new0 (GstAutoplugNode, 1);
 351     node->prev = NULL;
 352     node->fac = (GstElementFactory *) factories->data;
 353     GST_DEBUG ("trying with %s", node->fac->details.longname);
 354     node->templ = gst_autoplug_can_connect_src (node->fac, srccaps);
 355     node->cost = (node->templ ? gst_autoplug_get_cost (node->fac)
 356                               : GST_AUTOPLUG_MAX_COST);
 357     node->endpoint = gst_autoplug_can_connect_sink (node->fac, sinkcaps);
 358     if (node->templ && node->endpoint)
 359       GST_DEBUG ("%s makes connection possible",
 360                  node->fac->details.longname);
 361     else
 362       GST_DEBUG ("direct connection with %s not possible",
 363                  node->fac->details.longname);
 364     if ((node->endpoint != NULL) &&
 365         ((bestnode == NULL) || (node->cost < bestnode->cost)))
 366     {
 367       bestnode = node;
 368     }
 369     factory_nodes = g_list_prepend (factory_nodes, node);
 370     /* make curcost the minimum cost of any plugin */
 371     curcost = node->cost < curcost ? node->cost : curcost;
 372     factories = g_list_next (factories);
 373   }
 374
 375   /* check if we even have possible endpoints */
 376   if (bestnode == NULL)
 377   {
 378     GST_DEBUG ("no factory found that could connect to sink caps");
 379     g_list_free_list_and_elements (factory_nodes);
 380     return NULL;
 381   }
 382
 383   /* iterate until we found the best path */
 384   while (curcost < GST_AUTOPLUG_MAX_COST)
 385   {
 386     GList *nodes = factory_nodes;
 387     guint nextcost = GST_AUTOPLUG_MAX_COST; /* next cost to check */
 388     GST_DEBUG ("iterating at current cost %d, bestnode %s at %d", curcost, GST_OBJECT_NAME (bestnode->fac), bestnode->cost);
 389     /* check if we already have a valid best connection to the sink */
 390     if (bestnode->cost <= curcost)
 391     {
 392       GList *ret;
 393       GST_DEBUG ("found a way to connect via %s", GST_OBJECT_NAME ((GstObject *) bestnode->fac));
 394       /* enter all factories into the return list */
 395       ret = g_list_prepend (NULL, bestnode->fac);
 396       bestnode = bestnode->prev;
 397       while (bestnode != NULL)
 398       {
 399         ret = g_list_prepend (ret, bestnode->fac);
 400         bestnode = bestnode->prev;
 401       }
 402       g_list_free_list_and_elements (factory_nodes);
 403       return ret;
 404     }
 405
 406     /* iterate over all factories we have
 407      * if they have the current cost, calculate if this
 408      * factory supplies shorter paths to other elements
 409      */
 410     while (nodes)
 411     {
 412       if (((GstAutoplugNode *) nodes->data)->cost == curcost)
 413       {
 414         /* now check all elements if we got a shorter path */
 415         GList *sinknodes = factory_nodes;
 416         GstAutoplugNode *srcnode = (GstAutoplugNode *) nodes->data;
 417         while (sinknodes)
 418         {
 419           GstAutoplugNode *sinknode = (GstAutoplugNode *) sinknodes->data;
 420           GstPadTemplate *templ;
 421           if ((sinknode->cost > srcnode->cost + gst_autoplug_get_cost (sinknode->fac)) && (templ = gst_autoplug_can_match(srcnode->fac, sinknode->fac)))
 422           {
 423             /* we got a shorter path
 424              * now enter that path to that node */
 425             sinknode->prev = srcnode;
 426             sinknode->templ = templ;
 427             sinknode->cost = srcnode->cost + gst_autoplug_get_cost (sinknode->fac);
 428             /* make sure to set which cost to view next */
 429             nextcost = (nextcost > sinknode->cost) ? sinknode->cost : nextcost;
 430             /* did we get a new best node? */
 431             if (sinknode->endpoint && (sinknode->cost < bestnode->cost))
 432             {
 433               bestnode = sinknode;
 434             }
 435           }
 436           sinknodes = g_list_next (sinknodes);
 437         }
 438         /* FIXME: for speed remove the item we just iterated with from the factory_nodes
 439          * but don't free it yet and don't forget to free it.
 440          */
 441       }
 442       nodes = g_list_next (nodes);
 443     }
 444     curcost = nextcost;
 445   }
 446
 447   GST_DEBUG ("found no path from source caps to sink caps");
 448   g_list_free_list_and_elements (factory_nodes);
 449   return NULL;
 450 }