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 );
145 playlist_item_t *p_temp;
147 for( i_position = i_items - 1; i_position > 0; i_position-- )
149 i_new = rand() % (i_position+1);
150 p_temp = pp_items[i_position];
151 pp_items[i_position] = pp_items[i_new];
152 pp_items[i_new] = p_temp;
159 * Sort a node recursively.
160 * This function must be entered with the playlist lock !
161 * @param p_playlist the playlist
162 * @param p_node the node to sort
163 * @param p_sortfn the sorting function
164 * @return VLC_SUCCESS on success
166 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
170 playlist_ItemArraySort(p_node->i_children,p_node->pp_children,p_sortfn);
171 for( i = 0 ; i< p_node->i_children; i++ )
173 if( p_node->pp_children[i]->i_children != -1 )
175 recursiveNodeSort( p_playlist, p_node->pp_children[i], p_sortfn );
182 * Sort a node recursively.
184 * This function must be entered with the playlist lock !
186 * \param p_playlist the playlist
187 * \param p_node the node to sort
188 * \param i_mode: a SORT_* constant indicating the field to sort on
189 * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
190 * \return VLC_SUCCESS on success
192 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
193 int i_mode, int i_type )
195 /* Ask the playlist to reset as we are changing the order */
196 pl_priv(p_playlist)->b_reset_currently_playing = true;
198 /* Do the real job recursively */
199 return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
203 /* This is the stuff the sorting functions are made of. The proto_##
204 * functions are wrapped in cmp_a_## and cmp_d_## functions that do
205 * void * to const playlist_item_t * casting and dereferencing and
206 * cmp_d_## inverts the result, too. proto_## are static inline,
207 * cmp_[ad]_## are merely static as they're the target of pointers.
209 * In any case, each SORT_## constant (except SORT_RANDOM) must have
210 * a matching SORTFN( )-declared function here.
213 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
214 ( const playlist_item_t *first, const playlist_item_t *second )
216 SORTFN( SORT_ALBUM, first, second )
218 int i_ret = meta_sort( first, second, vlc_meta_Album, false );
219 /* Items came from the same album: compare the track numbers */
221 i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
226 SORTFN( SORT_ARTIST, first, second )
228 int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
229 /* Items came from the same artist: compare the albums */
231 i_ret = proto_SORT_ALBUM( first, second );
236 SORTFN( SORT_DESCRIPTION, first, second )
238 return meta_sort( first, second, vlc_meta_Description, false );
241 SORTFN( SORT_DURATION, first, second )
243 mtime_t time1 = input_item_GetDuration( first->p_input );
244 mtime_t time2 = input_item_GetDuration( second->p_input );
245 int i_ret = time1 > time2 ? 1 :
246 ( time1 == time2 ? 0 : -1 );
250 SORTFN( SORT_GENRE, first, second )
252 return meta_sort( first, second, vlc_meta_Genre, false );
255 SORTFN( SORT_ID, first, second )
257 return first->i_id - second->i_id;
260 SORTFN( SORT_RATING, first, second )
262 return meta_sort( first, second, vlc_meta_Rating, true );
265 SORTFN( SORT_TITLE, first, second )
267 return meta_strcasecmp_title( first, second );
270 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
272 /* If first is a node but not second */
273 if( first->i_children == -1 && second->i_children >= 0 )
275 /* If second is a node but not first */
276 else if( first->i_children >= 0 && second->i_children == -1 )
278 /* Both are nodes or both are not nodes */
280 return meta_strcasecmp_title( first, second );
283 SORTFN( SORT_TITLE_NUMERIC, first, second )
286 char *psz_first = input_item_GetTitleFbName( first->p_input );
287 char *psz_second = input_item_GetTitleFbName( second->p_input );
289 if( psz_first && psz_second )
290 i_ret = atoi( psz_first ) - atoi( psz_second );
291 else if( !psz_first && psz_second )
293 else if( psz_first && !psz_second )
303 SORTFN( SORT_TRACK_NUMBER, first, second )
305 return meta_sort( first, second, vlc_meta_TrackNumber, true );
308 SORTFN( SORT_URI, first, second )
311 char *psz_first = input_item_GetURI( first->p_input );
312 char *psz_second = input_item_GetURI( second->p_input );
314 if( psz_first && psz_second )
315 i_ret = strcasecmp( psz_first, psz_second );
316 else if( !psz_first && psz_second )
318 else if( psz_first && !psz_second )
330 /* Generate stubs around the proto_## sorting functions, ascending and
331 * descending both. Preprocessor magic up ahead. Brace yourself.
334 #ifndef VLC_DEFINE_SORT_FUNCTIONS
335 #error Where is VLC_DEFINE_SORT_FUNCTIONS?
339 static int cmp_a_##s(const void *l,const void *r) \
340 { return proto_##s(*(const playlist_item_t *const *)l, \
341 *(const playlist_item_t *const *)r); } \
342 static int cmp_d_##s(const void *l,const void *r) \
343 { return -1*proto_##s(*(const playlist_item_t * const *)l, \
344 *(const playlist_item_t * const *)r); }
346 VLC_DEFINE_SORT_FUNCTIONS
350 /* And populate an array with the addresses */
352 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
353 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
354 { VLC_DEFINE_SORT_FUNCTIONS };