1 /*****************************************************************************
2 * sort.c : Playlist sorting functions
3 *****************************************************************************
4 * Copyright (C) 1999-2009 the VideoLAN team
7 * Authors: Clément Stenac <zorglub@videolan.org>
8 * Ilkka Ollakka <ileoo@videolan.org>
9 * Rémi Duraffort <ivoire@videolan.org>
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
21 * You should have received a copy of the GNU General Public License along
22 * with this program; if not, write to the Free Software Foundation, Inc.,
23 * 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
24 *****************************************************************************/
29 #include <vlc_common.h>
30 #define VLC_INTERNAL_PLAYLIST_SORT_FUNCTIONS
31 #include "vlc_playlist.h"
32 #include "playlist_internal.h"
35 /* General comparison functions */
37 * Compare two items using their title or name
38 * @param first: the first item
39 * @param second: the second item
40 * @return -1, 0 or 1 like strcmp
42 static inline int meta_strcasecmp_title( const playlist_item_t *first,
43 const playlist_item_t *second )
46 char *psz_first = input_item_GetTitleFbName( first->p_input );
47 char *psz_second = input_item_GetTitleFbName( second->p_input );
49 if( psz_first && psz_second )
50 i_ret = strcasecmp( psz_first, psz_second );
51 else if( !psz_first && psz_second )
53 else if( psz_first && !psz_second )
64 * Compare two intems accoring to the given meta type
65 * @param first: the first item
66 * @param second: the second item
67 * @param meta: the meta type to use to sort the items
68 * @param b_integer: true if the meta are integers
69 * @return -1, 0 or 1 like strcmp
71 static inline int meta_sort( const playlist_item_t *first,
72 const playlist_item_t *second,
73 vlc_meta_type_t meta, bool b_integer )
76 char *psz_first = input_item_GetMeta( first->p_input, meta );
77 char *psz_second = input_item_GetMeta( second->p_input, meta );
80 if( first->i_children == -1 && second->i_children >= 0 )
82 else if( first->i_children >= 0 && second->i_children == -1 )
84 /* Both are nodes, sort by name */
85 else if( first->i_children >= 0 && second->i_children >= 0 )
86 i_ret = meta_strcasecmp_title( first, second );
88 else if( !psz_first && psz_second )
90 else if( psz_first && !psz_second )
92 /* No meta, sort by name */
93 else if( !psz_first && !psz_second )
94 i_ret = meta_strcasecmp_title( first, second );
98 i_ret = atoi( psz_first ) - atoi( psz_second );
100 i_ret = strcasecmp( psz_first, psz_second );
108 /* Comparison functions */
111 * Return the comparison function appropriate for the SORT_* and ORDER_*
112 * arguments given, or NULL for SORT_RANDOM.
113 * @param i_mode: a SORT_* enum indicating the field to sort on
114 * @param i_type: ORDER_NORMAL or ORDER_REVERSE
115 * @return function pointer, or NULL for SORT_RANDOM or invalid input
117 typedef int (*sortfn_t)(const void *,const void *);
118 static const sortfn_t sorting_fns[NUM_SORT_FNS][2];
119 static inline sortfn_t find_sorting_fn( unsigned i_mode, unsigned i_type )
121 if( i_mode>=NUM_SORT_FNS || i_type>1 )
123 return sorting_fns[i_mode][i_type];
127 * Sort an array of items recursively
128 * @param i_items: number of items
129 * @param pp_items: the array of items
130 * @param p_sortfn: the sorting function
134 void playlist_ItemArraySort( unsigned i_items, playlist_item_t **pp_items,
139 qsort( pp_items, i_items, sizeof( pp_items[0] ), p_sortfn );
144 playlist_item_t *p_temp;
146 for( i_position = 0; i_position < i_items ; i_position++ )
151 i_new = rand() % (i_items - 1);
154 p_temp = pp_items[i_position];
155 pp_items[i_position] = pp_items[i_new];
156 pp_items[i_new] = p_temp;
163 * Sort a node recursively.
164 * This function must be entered with the playlist lock !
165 * @param p_playlist the playlist
166 * @param p_node the node to sort
167 * @param p_sortfn the sorting function
168 * @return VLC_SUCCESS on success
170 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
174 playlist_ItemArraySort(p_node->i_children,p_node->pp_children,p_sortfn);
175 for( i = 0 ; i< p_node->i_children; i++ )
177 if( p_node->pp_children[i]->i_children != -1 )
179 recursiveNodeSort( p_playlist, p_node->pp_children[i], p_sortfn );
186 * Sort a node recursively.
188 * This function must be entered with the playlist lock !
190 * \param p_playlist the playlist
191 * \param p_node the node to sort
192 * \param i_mode: a SORT_* constant indicating the field to sort on
193 * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
194 * \return VLC_SUCCESS on success
196 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
197 int i_mode, int i_type )
199 /* Ask the playlist to reset as we are changing the order */
200 pl_priv(p_playlist)->b_reset_currently_playing = true;
202 /* Do the real job recursively */
203 return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
207 /* This is the stuff the sorting functions are made of. The proto_##
208 * functions are wrapped in cmp_a_## and cmp_d_## functions that do
209 * void * to const playlist_item_t * casting and dereferencing and
210 * cmp_d_## inverts the result, too. proto_## are static inline,
211 * cmp_[ad]_## are merely static as they're the target of pointers.
213 * In any case, each SORT_## constant (except SORT_RANDOM) must have
214 * a matching SORTFN( )-declared function here.
217 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
218 ( const playlist_item_t *first, const playlist_item_t *second )
220 SORTFN( SORT_ALBUM, first, second )
222 int i_ret = meta_sort( first, second, vlc_meta_Album, false );
223 /* Items came from the same album: compare the track numbers */
225 i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
230 SORTFN( SORT_ARTIST, first, second )
232 int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
233 /* Items came from the same artist: compare the albums */
235 i_ret = proto_SORT_ALBUM( first, second );
240 SORTFN( SORT_DESCRIPTION, first, second )
242 return meta_sort( first, second, vlc_meta_Description, false );
245 SORTFN( SORT_DURATION, first, second )
247 return input_item_GetDuration( first->p_input ) -
248 input_item_GetDuration( second->p_input );
251 SORTFN( SORT_GENRE, first, second )
253 return meta_sort( first, second, vlc_meta_Genre, false );
256 SORTFN( SORT_ID, first, second )
258 return first->i_id - second->i_id;
261 SORTFN( SORT_RATING, first, second )
263 return meta_sort( first, second, vlc_meta_Rating, true );
266 SORTFN( SORT_TITLE, first, second )
268 return meta_strcasecmp_title( first, second );
271 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
273 /* If first is a node but not second */
274 if( first->i_children == -1 && second->i_children >= 0 )
276 /* If second is a node but not first */
277 else if( first->i_children >= 0 && second->i_children == -1 )
279 /* Both are nodes or both are not nodes */
281 return meta_strcasecmp_title( first, second );
284 SORTFN( SORT_TITLE_NUMERIC, first, second )
287 char *psz_first = input_item_GetTitleFbName( first->p_input );
288 char *psz_second = input_item_GetTitleFbName( second->p_input );
290 if( psz_first && psz_second )
291 i_ret = atoi( psz_first ) - atoi( psz_second );
292 else if( !psz_first && psz_second )
294 else if( psz_first && !psz_second )
304 SORTFN( SORT_TRACK_NUMBER, first, second )
306 return meta_sort( first, second, vlc_meta_TrackNumber, true );
309 SORTFN( SORT_URI, first, second )
312 char *psz_first = input_item_GetURI( first->p_input );
313 char *psz_second = input_item_GetURI( second->p_input );
315 if( psz_first && psz_second )
316 i_ret = strcasecmp( psz_first, psz_second );
317 else if( !psz_first && psz_second )
319 else if( psz_first && !psz_second )
331 /* Generate stubs around the proto_## sorting functions, ascending and
332 * descending both. Preprocessor magic up ahead. Brace yourself.
335 #ifndef VLC_DEFINE_SORT_FUNCTIONS
336 #error Where is VLC_DEFINE_SORT_FUNCTIONS?
340 static int cmp_a_##s(const void *l,const void *r) \
341 { return proto_##s(*(const playlist_item_t *const *)l, \
342 *(const playlist_item_t *const *)r); } \
343 static int cmp_d_##s(const void *l,const void *r) \
344 { return -1*proto_##s(*(const playlist_item_t * const *)l, \
345 *(const playlist_item_t * const *)r); }
347 VLC_DEFINE_SORT_FUNCTIONS
351 /* And populate an array with the addresses */
353 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
354 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
355 { VLC_DEFINE_SORT_FUNCTIONS };