/* * Farstream - Farstream RTP Discover Codecs * * Copyright 2007 Collabora Ltd. * @author: Olivier Crete * @author Rob Taylor * @author Philippe Kalaf * Copyright 2007 Nokia Corp. * Copyright 2005 INdT * @author Andre Moreira Magalhaes * * fs-discover-codecs.c - A Farstream RTP Codec Discovery * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #ifdef HAVE_CONFIG_H # include "config.h" #endif #include "fs-rtp-discover-codecs.h" #include #include #include "fs-rtp-bin-error-downgrade.h" #include "fs-rtp-conference.h" #include "fs-rtp-codec-cache.h" #include "fs-rtp-special-source.h" #define GST_CAT_DEFAULT fsrtpconference_disco /* * Local TYPES */ typedef struct _CodecCap { GstCaps *caps; /* media caps */ GstCaps *rtp_caps; /* RTP caps of given media caps */ /* 2 list approach so we can have a separation after an intersection is * calculted */ GList *element_list1; /* elements for media, enc, dec, pay, depay */ GList *element_list2; /* elements for media, enc, dec, pay, depay */ } CodecCap; typedef gboolean (*FilterFunc) (GstElementFactory *factory); /* Static Functions */ static gboolean create_codec_lists (FsMediaType media_type, GList *recv_list, GList *send_list); static GList *remove_dynamic_duplicates (GList *list); static GList *remove_duplicates (GList *list); static void parse_codec_cap_list (GList *list, FsMediaType media_type); static GList *detect_send_codecs (GstCaps *caps); static GList *detect_recv_codecs (GstCaps *caps); static GList *codec_cap_list_intersect (GList *list1, GList *list2, gboolean one_is_enough); static GList *get_plugins_filtered_from_caps (FilterFunc filter, GstCaps *caps, GstPadDirection direction); static gboolean extract_field_data (GQuark field_id, const GValue *value, gpointer user_data); static void codec_blueprints_add_caps (FsMediaType media_type); /* GLOBAL variables */ static GList *list_codec_blueprints[FS_MEDIA_TYPE_LAST+1] = { NULL }; static gint codecs_lists_ref[FS_MEDIA_TYPE_LAST+1] = { 0 }; G_LOCK_DEFINE_STATIC (codecs_lists); static void debug_pipeline (GstDebugLevel level, const gchar *prefix, GList *pipeline) { GList *walk; GString *str; gboolean first = TRUE; if (gst_debug_category_get_threshold (GST_CAT_DEFAULT) < level) return; str = g_string_new (prefix); for (walk = pipeline; walk; walk = g_list_next (walk)) { GList *walk2; gboolean first_alt = TRUE; if (!first) g_string_append (str, " ->"); first = FALSE; for (walk2 = g_list_first (walk->data); walk2; walk2 = g_list_next (walk2)) { if (first_alt) g_string_append_printf (str, " %s", gst_plugin_feature_get_name (GST_PLUGIN_FEATURE (walk2->data))); else g_string_append_printf (str, " | %s", gst_plugin_feature_get_name (GST_PLUGIN_FEATURE (walk2->data))); first_alt = FALSE; } } GST_CAT_LEVEL_LOG (GST_CAT_DEFAULT, level, NULL, "%s", str->str); g_string_free (str, TRUE); } static void debug_codec_cap (CodecCap *codec_cap) { if (codec_cap->caps) GST_LOG ("%p:%d:media_caps %" GST_PTR_FORMAT, codec_cap->caps, GST_CAPS_REFCOUNT_VALUE (codec_cap->caps), codec_cap->caps); if (codec_cap->rtp_caps) { GST_LOG ("%p:%d:rtp_caps %" GST_PTR_FORMAT, codec_cap->rtp_caps, GST_CAPS_REFCOUNT_VALUE (codec_cap->rtp_caps), codec_cap->rtp_caps); g_assert (gst_caps_get_size (codec_cap->rtp_caps) == 1); } debug_pipeline (GST_LEVEL_LOG, "element_list1: ", codec_cap->element_list1); debug_pipeline (GST_LEVEL_LOG, "element_list2: ", codec_cap->element_list2); } static void debug_codec_cap_list (GList *codec_cap_list) { GList *walk; GST_LOG ("size of codec_cap list is %d", g_list_length (codec_cap_list)); for (walk = codec_cap_list; walk; walk = g_list_next (walk)) { debug_codec_cap ((CodecCap *)walk->data); } } static void codec_cap_free (CodecCap *codec_cap) { GList *walk; if (codec_cap->caps) { gst_caps_unref (codec_cap->caps); } if (codec_cap->rtp_caps) { gst_caps_unref (codec_cap->rtp_caps); } for (walk = codec_cap->element_list1; walk; walk = g_list_next (walk)) { if (walk->data) { g_list_foreach (walk->data, (GFunc) gst_object_unref, NULL); g_list_free (walk->data); } } for (walk = codec_cap->element_list2; walk; walk = g_list_next (walk)) { if (walk->data) { g_list_foreach (walk->data, (GFunc) gst_object_unref, NULL); g_list_free (walk->data); } } if (codec_cap->element_list1) { g_list_free (codec_cap->element_list1); } if (codec_cap->element_list2) { g_list_free (codec_cap->element_list2); } g_slice_free (CodecCap, codec_cap); } static void codec_cap_list_free (GList *list) { GList *mwalk; for (mwalk = list; mwalk; mwalk = g_list_next (mwalk)) { codec_cap_free ((CodecCap *)mwalk->data); } g_list_free (list); } /** * fs_rtp_blueprints_get * @media_type: a #FsMediaType * * find all plugins that follow the pattern: * input (microphone) -> N* -> rtp payloader -> network * network -> rtp depayloader -> N* -> output (soundcard) * media_type defines if we want audio or video codecs * * Returns: a #GList of #CodecBlueprint or NULL on error */ GList * fs_rtp_blueprints_get (FsMediaType media_type, GError **error) { GstCaps *caps; GList *recv_list = NULL; GList *send_list = NULL; GList *ret = NULL; if (media_type > FS_MEDIA_TYPE_LAST) { g_set_error (error, FS_ERROR, FS_ERROR_INVALID_ARGUMENTS, "Invalid media type given"); return NULL; } G_LOCK (codecs_lists); codecs_lists_ref[media_type]++; /* if already computed just return list */ if (codecs_lists_ref[media_type] > 1) { if (!list_codec_blueprints[media_type]) g_set_error (error, FS_ERROR, FS_ERROR_NO_CODECS, "No codecs for media type %s detected", fs_media_type_to_string (media_type)); ret = list_codec_blueprints[media_type]; goto out; } list_codec_blueprints[media_type] = load_codecs_cache (media_type); if (list_codec_blueprints[media_type]) { GST_DEBUG ("Loaded codec blueprints from cache file"); ret = list_codec_blueprints[media_type]; goto out; } /* caps used to find the payloaders and depayloaders based on media type */ if (media_type == FS_MEDIA_TYPE_AUDIO) { caps = gst_caps_new_simple ("application/x-rtp", "media", G_TYPE_STRING, "audio", NULL); } else if (media_type == FS_MEDIA_TYPE_VIDEO) { caps = gst_caps_new_simple ("application/x-rtp", "media", G_TYPE_STRING, "video", NULL); } else if (media_type == FS_MEDIA_TYPE_APPLICATION) { caps = gst_caps_new_simple ("application/x-rtp", "media", G_TYPE_STRING, "application", NULL); } else { g_set_error (error, FS_ERROR, FS_ERROR_INVALID_ARGUMENTS, "Invalid media type given to load_codecs"); codecs_lists_ref[media_type]--; goto out; } recv_list = detect_recv_codecs (caps); send_list = detect_send_codecs (caps); gst_caps_unref (caps); /* if we can't send or recv let's just stop here */ if (!recv_list && !send_list) { codecs_lists_ref[media_type]--; g_set_error (error, FS_ERROR, FS_ERROR_NO_CODECS, "No codecs for media type %s detected", fs_media_type_to_string (media_type)); list_codec_blueprints[media_type] = NULL; goto out; } create_codec_lists (media_type, recv_list, send_list); /* Save the codecs blueprint cache */ save_codecs_cache (media_type, list_codec_blueprints[media_type]); ret = list_codec_blueprints[media_type]; out: G_UNLOCK (codecs_lists); if (recv_list) codec_cap_list_free (recv_list); if (send_list) codec_cap_list_free (send_list); return ret; } static gboolean create_codec_lists (FsMediaType media_type, GList *recv_list, GList *send_list) { GList *duplex_list = NULL; list_codec_blueprints[media_type] = NULL; /* TODO we should support non duplex as well, as in have some caps that are * only sendable or only receivable */ duplex_list = codec_cap_list_intersect (recv_list, send_list, FALSE); if (!duplex_list) { GST_WARNING ("There are no send/recv codecs"); return FALSE; } GST_LOG ("*******Intersection of send_list and recv_list"); debug_codec_cap_list (duplex_list); duplex_list = remove_dynamic_duplicates (duplex_list); duplex_list = remove_duplicates (duplex_list); if (!duplex_list) { GST_WARNING ("Dynamic duplicate removal left us with nothing"); return FALSE; } parse_codec_cap_list (duplex_list, media_type); codec_cap_list_free (duplex_list); list_codec_blueprints[media_type] = fs_rtp_special_sources_add_blueprints (list_codec_blueprints[media_type]); codec_blueprints_add_caps (media_type); return (list_codec_blueprints[media_type] != NULL); } static gboolean struct_field_has_line (GstStructure *s, const gchar *field, const gchar *value) { const gchar *tmp = gst_structure_get_string (s, field); const GValue *v = NULL; gint i; if (tmp) return !strcmp (value, tmp); if (!gst_structure_has_field_typed (s, field, GST_TYPE_LIST)) return FALSE; v = gst_structure_get_value (s, field); for (i=0; i < gst_value_list_get_size (v); i++) { const GValue *listval = gst_value_list_get_value (v, i); if (G_VALUE_HOLDS_STRING(listval) && !strcmp (value, g_value_get_string (listval))) return TRUE; } return FALSE; } /* * This function returns TRUE if the codec_cap should be accepted, * FALSE otherwise */ static gboolean validate_h263_codecs (CodecCap *codec_cap) { /* we assume we have just one structure per caps as it should be */ GstStructure *media_struct = gst_caps_get_structure (codec_cap->caps, 0); const gchar *name = gst_structure_get_name (media_struct); GstStructure *rtp_struct; const gchar *encoding_name; if (!name) return FALSE; /* let's check if it's h263 */ if (strcmp (name, "video/x-h263")) return TRUE; /* If we don't have a h263version field, accept everything */ if (!gst_structure_has_field (media_struct, "h263version")) return TRUE; rtp_struct = gst_caps_get_structure (codec_cap->rtp_caps, 0); if (!rtp_struct) return FALSE; encoding_name = gst_structure_get_string (rtp_struct, "encoding-name"); /* If there is no encoding name, we have a problem, lets refuse it */ if (!encoding_name) return FALSE; if (struct_field_has_line (media_struct, "h263version", "h263")) { /* baseline H263 can only be encoding name H263 or H263-1998 */ if (strcmp (encoding_name, "H263") && strcmp (encoding_name, "H263-1998")) return FALSE; } else if (struct_field_has_line (media_struct, "h263version", "h263p")) { /* has to be H263-1998 */ if (strcmp (encoding_name, "H263-1998")) return FALSE; } else if (struct_field_has_line (media_struct, "h263version", "h263pp")) { /* has to be H263-2000 */ if (strcmp (encoding_name, "H263-2000")) return FALSE; } /* if no h263version specified, we assume it's all h263 versions */ return TRUE; } static gboolean validate_amr_codecs (CodecCap *codec_cap) { /* we assume we have just one structure per caps as it should be */ GstStructure *media_struct = gst_caps_get_structure (codec_cap->caps, 0); const gchar *name = gst_structure_get_name (media_struct); GstStructure *rtp_struct; const gchar *encoding_name; rtp_struct = gst_caps_get_structure (codec_cap->rtp_caps, 0); encoding_name = gst_structure_get_string (rtp_struct, "encoding-name"); /* let's check if it's AMRWB */ if (!strcmp (name, "audio/AMR-WB")) { if (!strcmp (encoding_name, "AMR-WB")) return TRUE; else return FALSE; } else if (!strcmp (name, "audio/AMR")) { if (!strcmp (encoding_name, "AMR")) return TRUE; else return FALSE; } /* Everything else is invalid */ return TRUE; } /* Removes all dynamic pts that already have a static pt in the list */ static GList * remove_dynamic_duplicates (GList *list) { GList *walk1, *walk2; CodecCap *codec_cap, *cur_codec_cap; GstStructure *rtp_struct, *cur_rtp_struct; const gchar *encoding_name, *cur_encoding_name; GList *remove_us = NULL; for (walk1 = list; walk1; walk1 = g_list_next (walk1)) { const GValue *value; GType type; codec_cap = (CodecCap *)(walk1->data); rtp_struct = gst_caps_get_structure (codec_cap->rtp_caps, 0); encoding_name = gst_structure_get_string (rtp_struct, "encoding-name"); if (!encoding_name) continue; /* let's skip all non static payload types */ value = gst_structure_get_value (rtp_struct, "payload"); if (!value) continue; type = G_VALUE_TYPE (value); if (type != G_TYPE_INT) { continue; } else { gint payload_type; payload_type = g_value_get_int (value); if (payload_type >= 96) { continue; } } for (walk2 = list; walk2; walk2 = g_list_next (walk2)) { cur_codec_cap = (CodecCap *)(walk2->data); cur_rtp_struct = gst_caps_get_structure (cur_codec_cap->rtp_caps, 0); cur_encoding_name = gst_structure_get_string (cur_rtp_struct, "encoding-name"); if (!cur_encoding_name) continue; if (g_ascii_strcasecmp (encoding_name, cur_encoding_name) == 0) { const GValue *value = gst_structure_get_value (cur_rtp_struct, "payload"); GType type = G_VALUE_TYPE (value); /* this is a dynamic pt that has a static one , let's remove it */ if (type == GST_TYPE_INT_RANGE) remove_us = g_list_prepend (remove_us, cur_codec_cap); } } } for (walk1 = remove_us; walk1; walk1 = g_list_next (walk1)) { list = g_list_remove_all (list, walk1->data); codec_cap_free (walk1->data); } g_list_free (remove_us); return list; } /* Removes duplicate codecs that have the same RTP expression */ static GList * remove_duplicates (GList *list) { GList *walk1, *walk2; for (walk1 = list; walk1; walk1 = g_list_next (walk1)) { CodecCap *codec_cap1 = walk1->data; again: for (walk2 = walk1->next; walk2; walk2 = g_list_next (walk2)) { CodecCap *codec_cap2 = walk2->data; if (gst_caps_is_equal (codec_cap1->rtp_caps, codec_cap2->rtp_caps)) { codec_cap_free (codec_cap2); walk1 = g_list_delete_link (walk1, walk2); goto again; } } } return list; } static GList * copy_element_list (GList *inlist) { GQueue outqueue = G_QUEUE_INIT; GList *tmp1; for (tmp1 = g_list_first (inlist); tmp1; tmp1 = g_list_next (tmp1)) { g_queue_push_tail (&outqueue, g_list_copy (tmp1->data)); g_list_foreach (tmp1->data, (GFunc) gst_object_ref, NULL); } return outqueue.head; } /* insert given codec_cap list into list_codecs and list_codec_blueprints */ static void parse_codec_cap_list (GList *list, FsMediaType media_type) { GList *walk; CodecCap *codec_cap; FsCodec *codec; CodecBlueprint *codec_blueprint; gint i; GstElementFactory *tmpfact; /* go thru all common caps */ for (walk = list; walk; walk = g_list_next (walk)) { codec_cap = (CodecCap *)(walk->data); codec = fs_codec_new (FS_CODEC_ID_ANY, NULL, media_type, 0); for (i = 0; i < gst_caps_get_size (codec_cap->rtp_caps); i++) { GstStructure *structure = gst_caps_get_structure (codec_cap->rtp_caps, i); gst_structure_foreach (structure, extract_field_data, (gpointer) codec); } if (!codec->encoding_name) { GstStructure *caps = gst_caps_get_structure (codec_cap->rtp_caps, 0); const gchar *encoding_name = codec->encoding_name ? codec->encoding_name : gst_structure_get_string (caps, "encoding-name"); GST_DEBUG ("skipping codec %s/%s, no encoding name specified" " (pt: %d clock_rate:%u", fs_media_type_to_string (media_type), encoding_name ? encoding_name : "unknown", codec->id, codec->clock_rate); encoding_name = NULL; fs_codec_destroy (codec); continue; } switch (codec->media_type) { case FS_MEDIA_TYPE_VIDEO: if (!validate_h263_codecs (codec_cap)) { fs_codec_destroy (codec); continue; } break; case FS_MEDIA_TYPE_AUDIO: if (!validate_amr_codecs (codec_cap)) { fs_codec_destroy (codec); continue; } break; default: break; } codec_blueprint = g_slice_new0 (CodecBlueprint); codec_blueprint->codec = codec; codec_blueprint->media_caps = gst_caps_copy (codec_cap->caps); codec_blueprint->rtp_caps = gst_caps_copy (codec_cap->rtp_caps); codec_blueprint->send_pipeline_factory = copy_element_list (codec_cap->element_list2); codec_blueprint->receive_pipeline_factory = copy_element_list (codec_cap->element_list1); /* Lets add the converters at the beginning of the encoding pipelines */ if (media_type == FS_MEDIA_TYPE_VIDEO) { tmpfact = gst_element_factory_find ("fsvideoanyrate"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } tmpfact = gst_element_factory_find ("videoconvert"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } tmpfact = gst_element_factory_find ("videoscale"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } } else if (media_type == FS_MEDIA_TYPE_AUDIO) { tmpfact = gst_element_factory_find ("audioconvert"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } tmpfact = gst_element_factory_find ("audioresample"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } tmpfact = gst_element_factory_find ("audioconvert"); if (tmpfact) { codec_blueprint->send_pipeline_factory = g_list_append ( codec_blueprint->send_pipeline_factory, g_list_append (NULL, tmpfact)); } tmpfact = gst_element_factory_find ("spanplc"); if (tmpfact) { GstElementFactory *tmpfact2; tmpfact2 = gst_element_factory_find ("audioconvert"); if (tmpfact2) { codec_blueprint->receive_pipeline_factory = g_list_append ( codec_blueprint->receive_pipeline_factory, g_list_append (NULL, tmpfact2)); codec_blueprint->receive_pipeline_factory = g_list_append ( codec_blueprint->receive_pipeline_factory, g_list_append (NULL, tmpfact)); } } } /* insert new information into tables */ list_codec_blueprints[media_type] = g_list_append ( list_codec_blueprints[media_type], codec_blueprint); GST_DEBUG ("adding codec %s with pt %d, send_pipeline %p, receive_pipeline %p", codec->encoding_name, codec->id, codec_blueprint->send_pipeline_factory, codec_blueprint->receive_pipeline_factory); GST_DEBUG ("media_caps: %" GST_PTR_FORMAT, codec_blueprint->media_caps); GST_DEBUG ("rtp_caps: %" GST_PTR_FORMAT, codec_blueprint->rtp_caps); debug_pipeline (GST_LEVEL_DEBUG, "send pipeline: ", codec_blueprint->send_pipeline_factory); debug_pipeline (GST_LEVEL_DEBUG, "receive pipeline: ", codec_blueprint->receive_pipeline_factory); } } static gboolean klass_contains (const gchar *klass, const gchar *needle) { gchar *found = strstr (klass, needle); if (!found) return FALSE; if (found != klass && *(found-1) != '/') return FALSE; if (found[strlen (needle)] != 0 && found[strlen (needle)] != '/') return FALSE; return TRUE; } static gboolean is_payloader (GstElementFactory *factory) { const gchar *klass = gst_element_factory_get_klass (factory); return (klass_contains (klass, "Payloader") && klass_contains (klass, "Network")); } static gboolean is_depayloader (GstElementFactory *factory) { const gchar *klass = gst_element_factory_get_klass (factory); return (klass_contains (klass, "Network") && (klass_contains (klass, "Depayloader") || klass_contains (klass, "Depayr"))); } static gboolean is_encoder (GstElementFactory *factory) { const gchar *klass = gst_element_factory_get_klass (factory); /* we might have some sources that provide a non raw stream */ return (klass_contains (klass, "Encoder")); } static gboolean is_decoder (GstElementFactory *factory) { const gchar *klass = gst_element_factory_get_klass (factory); /* we might have some sinks that provide decoding */ return (klass_contains (klass, "Decoder")); } /* find all encoder/payloader combos and build list for them */ static GList * detect_send_codecs (GstCaps *caps) { GList *payloaders, *encoders; GList *send_list = NULL; /* find all payloader caps. All payloaders should be from klass * Codec/Payloader/Network and have as output a data of the mimetype * application/x-rtp */ payloaders = get_plugins_filtered_from_caps (is_payloader, caps, GST_PAD_SINK); /* no payloader found. giving up */ if (!payloaders) { GST_WARNING ("No RTP Payloaders found"); return NULL; } else { GST_LOG ("**Payloaders"); debug_codec_cap_list (payloaders); } /* find all encoders based on is_encoder filter */ encoders = get_plugins_filtered_from_caps (is_encoder, NULL, GST_PAD_SRC); if (!encoders) { codec_cap_list_free (payloaders); GST_WARNING ("No encoders found"); return NULL; } else { GST_LOG ("**Encoders"); debug_codec_cap_list (encoders); } /* create intersection list of codecs common * to encoders and payloaders lists */ send_list = codec_cap_list_intersect (payloaders, encoders, TRUE); if (!send_list) { GST_WARNING ("No compatible encoder/payloader pairs found"); } else { GST_LOG ("**intersection of payloaders and encoders"); debug_codec_cap_list (send_list); } codec_cap_list_free (payloaders); codec_cap_list_free (encoders); return send_list; } /* find all decoder/depayloader combos and build list for them */ static GList * detect_recv_codecs (GstCaps *caps) { GList *depayloaders, *decoders; GList *recv_list = NULL; /* find all depayloader caps. All depayloaders should be from klass * Codec/Depayr/Network and have as input a data of the mimetype * application/x-rtp */ depayloaders = get_plugins_filtered_from_caps (is_depayloader, caps, GST_PAD_SRC); /* no depayloader found. giving up */ if (!depayloaders) { GST_WARNING ("No RTP Depayloaders found"); return NULL; } else { GST_LOG ("**Depayloaders"); debug_codec_cap_list (depayloaders); } /* find all decoders based on is_decoder filter */ decoders = get_plugins_filtered_from_caps (is_decoder, NULL, GST_PAD_SINK); if (!decoders) { codec_cap_list_free (depayloaders); GST_WARNING ("No decoders found"); return NULL; } else { GST_LOG ("**Decoders"); debug_codec_cap_list (decoders); } /* create intersection list of codecs common * to decoders and depayloaders lists */ recv_list = codec_cap_list_intersect (depayloaders, decoders, TRUE); if (!recv_list) { GST_WARNING ("No compatible decoder/depayloader pairs found"); } else { GST_LOG ("**intersection of depayloaders and decoders"); debug_codec_cap_list (recv_list); } codec_cap_list_free (depayloaders); codec_cap_list_free (decoders); return recv_list; } /* returns the intersection of two lists */ static GList * codec_cap_list_intersect (GList *list1, GList *list2, gboolean one_is_enough) { GList *walk1, *walk2; CodecCap *codec_cap1, *codec_cap2; GstCaps *caps1, *caps2; GstCaps *rtp_caps1, *rtp_caps2; GList *intersection_list = NULL; for (walk1 = g_list_first (list1); walk1; walk1 = g_list_next (walk1)) { CodecCap *item = NULL; codec_cap1 = (CodecCap *)(walk1->data); caps1 = codec_cap1->caps; rtp_caps1 = codec_cap1->rtp_caps; for (walk2 = list2; walk2; walk2 = g_list_next (walk2)) { GstCaps *intersection = NULL; GstCaps *rtp_intersection = NULL; codec_cap2 = (CodecCap *)(walk2->data); caps2 = codec_cap2->caps; rtp_caps2 = codec_cap2->rtp_caps; //g_debug ("intersecting %s AND %s", gst_caps_to_string (caps1), gst_caps_to_string (caps2)); intersection = gst_caps_intersect (caps1, caps2); if (rtp_caps1 && rtp_caps2) { //g_debug ("RTP intersecting %s AND %s", gst_caps_to_string (rtp_caps1), gst_caps_to_string (rtp_caps2)); rtp_intersection = gst_caps_intersect (rtp_caps1, rtp_caps2); } if (!gst_caps_is_empty (intersection) && (rtp_intersection == NULL || !gst_caps_is_empty (rtp_intersection))) { if (item) { GList *tmplist; item->caps = gst_caps_merge (item->caps, intersection); for (tmplist = g_list_first (codec_cap2->element_list1->data); tmplist; tmplist = g_list_next (tmplist)) { if (g_list_index (item->element_list2->data, tmplist->data) < 0) { item->element_list2->data = g_list_concat ( item->element_list2->data, g_list_copy (codec_cap2->element_list1->data)); g_list_foreach (codec_cap2->element_list1->data, (GFunc) gst_object_ref, NULL); } } } else { item = g_slice_new0 (CodecCap); item->caps = intersection; if (rtp_caps1 && rtp_caps2) { item->rtp_caps = rtp_intersection; } else if (rtp_caps1) { item->rtp_caps = rtp_caps1; gst_caps_ref (rtp_caps1); } else if (rtp_caps2) { item->rtp_caps = rtp_caps2; gst_caps_ref (rtp_caps2); } /* during an intersect, we concat/copy previous lists together and put them * into 1 and 2 */ item->element_list1 = g_list_concat ( copy_element_list (codec_cap1->element_list1), copy_element_list (codec_cap1->element_list2)); item->element_list2 = g_list_concat ( copy_element_list (codec_cap2->element_list1), copy_element_list (codec_cap2->element_list2)); intersection_list = g_list_append (intersection_list, item); if (rtp_intersection) { break; } } } else { if (rtp_intersection) gst_caps_unref (rtp_intersection); gst_caps_unref (intersection); } } if (!item && one_is_enough) { item = g_slice_new0 (CodecCap); item->caps = gst_caps_ref (codec_cap1->caps); item->rtp_caps = gst_caps_ref (codec_cap1->rtp_caps); item->element_list1 = copy_element_list (codec_cap1->element_list1); item->element_list2 = copy_element_list (codec_cap1->element_list2); intersection_list = g_list_append (intersection_list, item); } } return intersection_list; } void codec_blueprint_destroy (CodecBlueprint *codec_blueprint) { GList *walk; if (codec_blueprint->codec) { fs_codec_destroy (codec_blueprint->codec); } if (codec_blueprint->media_caps) { gst_caps_unref (codec_blueprint->media_caps); } if (codec_blueprint->rtp_caps) { gst_caps_unref (codec_blueprint->rtp_caps); } if (codec_blueprint->input_caps) { gst_caps_unref (codec_blueprint->input_caps); } if (codec_blueprint->output_caps) { gst_caps_unref (codec_blueprint->output_caps); } for (walk = codec_blueprint->send_pipeline_factory; walk; walk = g_list_next (walk)) { if (walk->data) { g_list_foreach (walk->data, (GFunc) gst_object_unref, NULL); g_list_free (walk->data); } } for (walk = codec_blueprint->receive_pipeline_factory; walk; walk = g_list_next (walk)) { if (walk->data) { g_list_foreach (walk->data, (GFunc) gst_object_unref, NULL); g_list_free (walk->data); } } g_list_free (codec_blueprint->send_pipeline_factory); g_list_free (codec_blueprint->receive_pipeline_factory); g_slice_free (CodecBlueprint, codec_blueprint); } void fs_rtp_blueprints_unref (FsMediaType media_type) { G_LOCK (codecs_lists); codecs_lists_ref[media_type]--; if (!codecs_lists_ref[media_type]) { if (list_codec_blueprints[media_type]) { GList *item; for (item = list_codec_blueprints[media_type]; item; item = g_list_next (item)) { codec_blueprint_destroy (item->data); } g_list_free (list_codec_blueprints[media_type]); list_codec_blueprints[media_type] = NULL; } } G_UNLOCK (codecs_lists); } /* check if caps are found on given element */ static gboolean check_caps_compatibility (GstElementFactory *factory, GstCaps *caps, GstCaps **matched_caps) { const GList *pads; GstStaticPadTemplate *padtemplate; GstCaps *padtemplate_caps = NULL; if (!gst_element_factory_get_num_pad_templates (factory)) { return FALSE; } pads = gst_element_factory_get_static_pad_templates (factory); while (pads) { padtemplate = (GstStaticPadTemplate *) (pads->data); pads = g_list_next (pads); padtemplate_caps = gst_static_caps_get (&padtemplate->static_caps); if (gst_caps_is_any (padtemplate_caps)) { goto next; } if (caps) { GstCaps *intersection = gst_caps_intersect (padtemplate_caps, caps); gboolean have_intersection = !gst_caps_is_empty (intersection); if (have_intersection) { *matched_caps = intersection; gst_caps_unref (padtemplate_caps); return TRUE; } gst_caps_unref (intersection); } next: if (padtemplate_caps) { gst_caps_unref (padtemplate_caps); } } *matched_caps = NULL; return FALSE; } /* GCompareFunc for list_find_custom */ /* compares caps and returns 0 if they intersect */ static gint compare_media_caps (gconstpointer a, gconstpointer b) { CodecCap *element = (CodecCap *)a; GstCaps *c_caps = (GstCaps *)b; return !gst_caps_can_intersect (element->caps, c_caps); } static gint compare_rtp_caps (CodecCap *element, GstCaps *c_caps) { return !gst_caps_can_intersect (element->rtp_caps, c_caps); } /* adds the given element to a list of CodecCap */ /* if element has several caps, several CodecCap elements will be added */ /* if element caps already in list, will make sure Transform elements have * priority and replace old ones */ static GList * create_codec_cap_list (GstElementFactory *factory, GstPadDirection direction, GList *list, GstCaps *rtp_caps) { const GList *pads = gst_element_factory_get_static_pad_templates (factory); gint i; /* Let us look at each pad for stuff to add*/ while (pads) { GstCaps *caps = NULL; GstStaticPadTemplate *padtemplate = NULL; padtemplate = (GstStaticPadTemplate *) (pads->data); pads = g_list_next (pads); if (padtemplate->direction != direction) continue; if (padtemplate->presence != GST_PAD_ALWAYS) { continue; } caps = gst_static_pad_template_get_caps (padtemplate); /* DEBUG ("%s caps are %s", gst_plugin_feature_get_name (GST_PLUGIN_FEATURE (factory)), gst_caps_to_string (caps)); */ /* skips caps ANY */ if (!caps || gst_caps_is_any (caps)) { goto done; } /* let us add one entry to the list per media type */ for (i = 0; i < gst_caps_get_size (caps); i++) { CodecCap *entry = NULL; GList *found_item = NULL; GstStructure *structure = gst_caps_get_structure (caps, i); GstCaps *cur_caps = NULL; /* FIXME fix this in gstreamer! The rtpdepay element is bogus, it claims to * be a depayloader yet has application/x-rtp on both sides and does * absolutely nothing */ /* Let's check if media caps are really media caps, this is to deal with * wierd elements such as rtpdepay that says it's a depayloader but has * application/x-rtp on src and sink pads */ const gchar *name = gst_structure_get_name (structure); if (g_ascii_strcasecmp (name, "application/x-rtp") == 0) { GST_DEBUG ("skipping %s : %s", gst_plugin_feature_get_name (GST_PLUGIN_FEATURE (factory)), name); continue; } cur_caps = gst_caps_new_full (gst_structure_copy (structure), NULL); /* let's check if this caps is already in the list, if so let's replace * that CodecCap list instead of creating a new one */ /* we need to compare both media caps and rtp caps */ found_item = g_list_find_custom (list, cur_caps, (GCompareFunc)compare_media_caps); if (found_item) { entry = (CodecCap *)found_item->data; /* if RTP caps exist and don't match nullify entry */ if (rtp_caps && compare_rtp_caps (found_item->data, rtp_caps)) { entry = NULL; } } if (!entry) { entry = g_slice_new0 (CodecCap); entry->caps = cur_caps; if (rtp_caps) { entry->rtp_caps = rtp_caps; gst_caps_ref (rtp_caps); } list = g_list_append (list, entry); entry->element_list1 = g_list_prepend (NULL, g_list_prepend (NULL, factory)); gst_object_ref (factory); } else { entry->element_list1->data = g_list_append (entry->element_list1->data, factory); gst_object_ref (factory); if (rtp_caps) { if (entry->rtp_caps) { GstCaps *tmp = gst_caps_intersect (rtp_caps, entry->rtp_caps); gst_caps_unref (entry->rtp_caps); entry->rtp_caps = tmp; } else { entry->rtp_caps = gst_caps_ref (rtp_caps); /* This shouldn't happen, its we're looking at rtp elements * or we're not */ g_assert_not_reached (); } } entry->caps = gst_caps_merge (cur_caps, entry->caps); } } done: if (caps != NULL) { gst_caps_unref (caps); } } return list; } /* function used to sort element features */ /* Copy-pasted from decodebin */ static gint compare_ranks (GstPluginFeature * f1, GstPluginFeature * f2) { gint diff; const gchar *rname1, *rname2; diff = gst_plugin_feature_get_rank (f2) - gst_plugin_feature_get_rank (f1); if (diff != 0) return diff; rname1 = gst_plugin_feature_get_name (f1); rname2 = gst_plugin_feature_get_name (f2); diff = strcmp (rname2, rname1); return diff; } /* creates/returns a list of CodecCap based on given filter function and caps */ static GList * get_plugins_filtered_from_caps (FilterFunc filter, GstCaps *caps, GstPadDirection direction) { GList *walk, *result; GList *list = NULL; GstCaps *matched_caps = NULL; result = gst_registry_get_feature_list (gst_registry_get (), GST_TYPE_ELEMENT_FACTORY); result = g_list_sort (result, (GCompareFunc) compare_ranks); for (walk = result; walk; walk = walk->next) { GstElementFactory *factory = GST_ELEMENT_FACTORY (walk->data); /* Ignore unranked plugins */ if (gst_plugin_feature_get_rank (GST_PLUGIN_FEATURE (factory)) == GST_RANK_NONE) continue; if (!filter (factory)) continue; if (caps && !check_caps_compatibility (factory, caps, &matched_caps)) continue; if (!matched_caps) { list = create_codec_cap_list (factory, direction, list, NULL); } else { gint i; GPtrArray *capslist = g_ptr_array_new_with_free_func ( (GDestroyNotify) gst_caps_unref); while (gst_caps_get_size (matched_caps) > 0) { GstCaps *stolencaps = gst_caps_new_full ( gst_caps_steal_structure (matched_caps, 0), NULL); gboolean got_match = FALSE; for (i = 0; i < capslist->len; i++) { GstCaps *intersect = gst_caps_intersect (stolencaps, g_ptr_array_index (capslist, i)); if (gst_caps_is_empty (intersect)) { gst_caps_unref (intersect); } else { got_match = TRUE; gst_caps_unref (g_ptr_array_index (capslist, i)); g_ptr_array_index (capslist, i) = intersect; } } if (got_match) gst_caps_unref (stolencaps); else g_ptr_array_add (capslist, stolencaps); } gst_caps_unref (matched_caps); for (i = 0; i < capslist->len; i++) list = create_codec_cap_list (factory, direction, list, g_ptr_array_index (capslist, i)); g_ptr_array_unref (capslist); } } gst_plugin_feature_list_free (result); return list; } /* * fill FarstreamCodec fields based on payloader capabilities * TODO: optimise using quarks */ static gboolean extract_field_data (GQuark field_id, const GValue *value, gpointer user_data) { /* TODO : This can be called several times from different rtp caps for the * same codec, it would be good to make sure any duplicate values are the * same, if not then we have several rtp elements that are giving different * caps information, therefore they need to be fixed */ FsCodec *codec = (FsCodec *) user_data; GType type = G_VALUE_TYPE (value); const gchar *field_name = g_quark_to_string (field_id); const gchar *tmp; if (0 == strcmp (field_name, "media")) { if (type != G_TYPE_STRING) { return FALSE; } tmp = g_value_get_string (value); if (strcmp (tmp, "audio") == 0) { codec->media_type = FS_MEDIA_TYPE_AUDIO; } else if (strcmp (tmp, "video") == 0) { codec->media_type = FS_MEDIA_TYPE_VIDEO; } else if (strcmp (tmp, "application") == 0) { codec->media_type = FS_MEDIA_TYPE_APPLICATION; } } else if (0 == strcmp (field_name, "payload")) { if (type == GST_TYPE_INT_RANGE) { if (gst_value_get_int_range_min (value) < 96 || gst_value_get_int_range_max (value) > 255) { return FALSE; } } else if (type == G_TYPE_INT) { int id; id = g_value_get_int (value); if (id > 96) { /* Dynamic id that was explicitelly set ?? shouldn't happen */ return FALSE; } codec->id = id; } else { return FALSE; } } else if (0 == strcmp (field_name, "clock-rate")) { if (type == GST_TYPE_INT_RANGE) { /* set to 0, this should be checked by the optional parameters code later * in Farstream */ codec->clock_rate = 0; return TRUE; } else if (type != G_TYPE_INT) { return FALSE; } codec->clock_rate = g_value_get_int (value); } else if (0 == strcmp (field_name, "ssrc") || 0 == strcmp (field_name, "clock-base") || 0 == strcmp (field_name, "seqnum-base")) { // ignore these fields for now ; } else if (0 == strcmp (field_name, "encoding-name")) { if (type == GST_TYPE_LIST) { value = gst_value_list_get_value (value, 0); type = G_VALUE_TYPE (value); } if (type != G_TYPE_STRING) { return FALSE; } if (!codec->encoding_name) { codec->encoding_name = g_value_dup_string (value); } } else if (0 == strcmp (field_name, "encoding-params")) { if (type != G_TYPE_STRING) { return FALSE; } codec->channels = (guint) g_ascii_strtoull ( g_value_get_string (value), NULL, 10); } else { if (type == G_TYPE_STRING) fs_codec_add_optional_parameter (codec, field_name, g_value_get_string (value)); } return TRUE; } gboolean codec_blueprint_has_factory (CodecBlueprint *blueprint, FsStreamDirection direction) { if (direction == FS_DIRECTION_SEND) return (blueprint->send_pipeline_factory != NULL); else if (direction == FS_DIRECTION_RECV) return (blueprint->receive_pipeline_factory != NULL); else g_assert_not_reached (); } static gboolean _g_object_has_property (GObject *object, const gchar *property) { GObjectClass *klass; klass = G_OBJECT_GET_CLASS (object); return NULL != g_object_class_find_property (klass, property); } static gboolean _create_ghost_pad (GstElement *current_element, const gchar *padname, GstElement *codec_bin, GError **error) { GstPad *ghostpad; GstPad *pad = gst_element_get_static_pad (current_element, padname); gboolean ret = FALSE; if (!pad) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not find the %s pad on the element", padname); return FALSE; } ghostpad = gst_ghost_pad_new (padname, pad); if (!ghostpad) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not create a ghost pad for pad %s", padname); goto done; } if (!gst_pad_set_active (ghostpad, TRUE)) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not active ghostpad %s", padname); gst_object_unref (ghostpad); goto done; } if (!gst_element_add_pad (codec_bin, ghostpad)) g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not add ghostpad %s to the codec bin", padname); ret = TRUE; done: gst_object_unref (pad); return ret; } /* * Builds a codec bin in the specified direction for the specified codec * using the specified blueprint */ GstElement * create_codec_bin_from_blueprint (const FsCodec *codec, CodecBlueprint *blueprint, const gchar *name, FsStreamDirection direction, GError **error) { GstElement *codec_bin = NULL; const gchar *direction_str; GList *walk = NULL; GstElement *current_element = NULL; GstElement *previous_element = NULL; GList *pipeline_factory = NULL; if (direction == FS_DIRECTION_SEND) { direction_str = "send"; pipeline_factory = blueprint->send_pipeline_factory; } else if (direction == FS_DIRECTION_RECV) { direction_str = "receive"; pipeline_factory = blueprint->receive_pipeline_factory; } else { g_assert_not_reached (); } if (!pipeline_factory) { g_set_error (error, FS_ERROR, FS_ERROR_UNKNOWN_CODEC, "The %s codec %s does not have a pipeline," " its probably a special codec", fs_media_type_to_string (codec->media_type), codec->encoding_name); return NULL; } GST_DEBUG ("creating %s codec bin for id %d, pipeline_factory %p", direction_str, codec->id, pipeline_factory); if (direction == FS_DIRECTION_SEND) codec_bin = gst_bin_new (name); else if (direction == FS_DIRECTION_RECV) codec_bin = fs_rtp_bin_error_downgrade_new (name); else g_assert_not_reached (); for (walk = g_list_first (pipeline_factory); walk; walk = g_list_next (walk)) { if (g_list_next (g_list_first (walk->data))) { /* We have to check some kind of configuration to see if we have a favorite */ current_element = gst_element_factory_make ("autoconvert", NULL); if (!current_element) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not create autoconvert element"); goto error; } g_object_set (current_element, "factories", walk->data, NULL); } else { current_element = gst_element_factory_create ( GST_ELEMENT_FACTORY (g_list_first (walk->data)->data), NULL); if (!current_element) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not create element for pt %d", codec->id); goto error; } } if (!gst_bin_add (GST_BIN (codec_bin), current_element)) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not add new element to %s codec_bin for pt %d", direction_str, codec->id); goto error; } if (_g_object_has_property (G_OBJECT (current_element), "pt")) g_object_set (current_element, "pt", codec->id, NULL); /* Lets create the ghost pads on the codec bin */ if (g_list_previous (walk) == NULL) /* if its the first element of the codec bin */ if (!_create_ghost_pad (current_element, (direction == FS_DIRECTION_SEND) ? "src" : "sink", codec_bin, error)) goto error; if (g_list_next (walk) == NULL) /* if its the last element of the codec bin */ if (!_create_ghost_pad (current_element, (direction == FS_DIRECTION_SEND) ? "sink" : "src" , codec_bin, error)) goto error; /* let's link them together using the specified media_caps if any * this will ensure that multi-codec encoders/decoders will select the * appropriate codec based on caps negotiation */ if (previous_element) { GstPad *sinkpad; GstPad *srcpad; GstPadLinkReturn ret; if (direction == FS_DIRECTION_SEND) sinkpad = gst_element_get_static_pad (previous_element, "sink"); else if (direction == FS_DIRECTION_RECV) sinkpad = gst_element_get_static_pad (current_element, "sink"); else g_assert_not_reached (); if (!sinkpad) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not get the sink pad one of the elements in the %s codec bin" " for pt %d", direction_str, codec->id); goto error; } if (direction == FS_DIRECTION_SEND) srcpad = gst_element_get_static_pad (current_element, "src"); else if (direction == FS_DIRECTION_RECV) srcpad = gst_element_get_static_pad (previous_element, "src"); else g_assert_not_reached (); if (!srcpad) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not get the src pad one of the elements in the %s codec bin" " for pt %d", direction_str, codec->id); gst_object_unref (sinkpad); goto error; } ret = gst_pad_link (srcpad, sinkpad); gst_object_unref (srcpad); gst_object_unref (sinkpad); if (GST_PAD_LINK_FAILED (ret)) { g_set_error (error, FS_ERROR, FS_ERROR_CONSTRUCTION, "Could not link element inside the %s codec bin for pt %d", direction_str, codec->id); goto error; } } previous_element = current_element; } return codec_bin; error: gst_object_unref (codec_bin); return NULL; } GstCaps * codec_get_in_out_caps (FsCodec *codec, GstCaps *rtp_caps, FsStreamDirection direction, GstElement *codecbin) { GstElement *capsfilter = NULL; GstPad *pad = NULL; gboolean r; const gchar *padname = (direction == FS_DIRECTION_SEND) ? "sink" : "src"; GstCaps *caps = NULL; capsfilter = gst_element_factory_make ("capsfilter", NULL); g_object_set (capsfilter, "caps", rtp_caps, NULL); if (direction == FS_DIRECTION_SEND) r = gst_element_link (codecbin, capsfilter); else if (direction == FS_DIRECTION_RECV) r = gst_element_link (capsfilter, codecbin); else g_assert_not_reached (); if (!r) { GST_WARNING ("Could not link capsfilter to codecbin for " FS_CODEC_FORMAT, FS_CODEC_ARGS (codec)); goto done; } pad = gst_element_get_static_pad (codecbin, padname); if (!pad) { GST_WARNING ("Could not get %s pad on codecbin for " FS_CODEC_FORMAT, padname, FS_CODEC_ARGS (codec)); goto done; } caps = gst_pad_query_caps (pad, NULL); if (!caps) { GST_WARNING ("Query for caps on codecbin failed for " FS_CODEC_FORMAT, FS_CODEC_ARGS (codec)); goto done; } done: g_clear_object (&pad); g_clear_object (&capsfilter); return caps; } static void codec_blueprints_add_caps (FsMediaType media_type) { GList *item; for (item = list_codec_blueprints[media_type]; item;) { GList *next = item->next; CodecBlueprint *blueprint = item->data; gboolean success = FALSE; GError *error = NULL; FsCodec *codec_copy = NULL; /* If there are no pipelines, it's all ok */ if (!blueprint->send_pipeline_factory && !blueprint->receive_pipeline_factory) { success = TRUE; goto next; } codec_copy = fs_codec_copy (blueprint->codec); if (codec_copy->id == FS_CODEC_ID_ANY) codec_copy->id = 96; if (blueprint->send_pipeline_factory) { GstElement *codecbin; codecbin = create_codec_bin_from_blueprint (codec_copy, blueprint, "gather_send_codecbin", FS_DIRECTION_SEND, &error); if (!codecbin) { GST_WARNING ("Could not create send codec bin from blueprint for " FS_CODEC_FORMAT": %s", FS_CODEC_ARGS (blueprint->codec), error->message); goto next; } blueprint->input_caps = codec_get_in_out_caps (blueprint->codec, blueprint->rtp_caps, FS_DIRECTION_SEND, codecbin); gst_object_unref (codecbin); if (blueprint->input_caps == NULL) goto next; } if (blueprint->receive_pipeline_factory) { GstElement *codecbin; codecbin = create_codec_bin_from_blueprint (codec_copy, blueprint, "gather_recv_codecbin", FS_DIRECTION_RECV, &error); if (!codecbin) { GST_WARNING ("Could not create receive codec bin from blueprint for " FS_CODEC_FORMAT": %s", FS_CODEC_ARGS (blueprint->codec), error->message); goto next; } blueprint->output_caps = codec_get_in_out_caps (blueprint->codec, blueprint->rtp_caps, FS_DIRECTION_RECV, codecbin); gst_object_unref (codecbin); if (!blueprint->output_caps) goto next; } if (blueprint->input_caps == NULL) blueprint->input_caps = gst_caps_new_any (); if (blueprint->output_caps == NULL) blueprint->output_caps = gst_caps_new_any (); success = TRUE; next: if (codec_copy) fs_codec_destroy (codec_copy); g_clear_error (&error); if (!success) { codec_blueprint_destroy (blueprint); list_codec_blueprints[media_type] = g_list_delete_link ( list_codec_blueprints[media_type], item); } item = next; } }