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