1 /*****************************************************************************
2 * sort.c : Playlist sorting functions
3 *****************************************************************************
4 * Copyright (C) 1999-2009 VLC authors and VideoLAN
5 * $Id: c0982cd1330fa4522f1406b5dfe4cbe3c257a7e3 $
6 *
7 * Authors: Clément Stenac <zorglub@videolan.org>
8 * Ilkka Ollakka <ileoo@videolan.org>
9 * Rémi Duraffort <ivoire@videolan.org>
10 *
11 * This program is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 2.1 of the License, or
14 * (at your option) any later version.
15 *
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 Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this program; if not, write to the Free Software Foundation,
23 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
24 *****************************************************************************/
25 #ifdef HAVE_CONFIG_H
26 # include "config.h"
27 #endif
28
29 #include <vlc_common.h>
30 #include <vlc_rand.h>
31 #define VLC_INTERNAL_PLAYLIST_SORT_FUNCTIONS
32 #include "vlc_playlist.h"
33 #include "playlist_internal.h"
34
35
36 /* General comparison functions */
37 /**
38 * Compare two items using their title or name
39 * @param first: the first item
40 * @param second: the second item
41 * @return -1, 0 or 1 like strcmp
42 */
meta_strcasecmp_title(const playlist_item_t * first,const playlist_item_t * second)43 static inline int meta_strcasecmp_title( const playlist_item_t *first,
44 const playlist_item_t *second )
45 {
46 int i_ret;
47 char *psz_first = input_item_GetTitleFbName( first->p_input );
48 char *psz_second = input_item_GetTitleFbName( second->p_input );
49
50 if( psz_first && psz_second )
51 i_ret = strcasecmp( psz_first, psz_second );
52 else if( !psz_first && psz_second )
53 i_ret = 1;
54 else if( psz_first && !psz_second )
55 i_ret = -1;
56 else
57 i_ret = 0;
58 free( psz_first );
59 free( psz_second );
60
61 return i_ret;
62 }
63
64 /**
65 * Compare two intems according to the given meta type
66 * @param first: the first item
67 * @param second: the second item
68 * @param meta: the meta type to use to sort the items
69 * @param b_integer: true if the meta are integers
70 * @return -1, 0 or 1 like strcmp
71 */
meta_sort(const playlist_item_t * first,const playlist_item_t * second,vlc_meta_type_t meta,bool b_integer)72 static inline int meta_sort( const playlist_item_t *first,
73 const playlist_item_t *second,
74 vlc_meta_type_t meta, bool b_integer )
75 {
76 int i_ret;
77 char *psz_first = input_item_GetMeta( first->p_input, meta );
78 char *psz_second = input_item_GetMeta( second->p_input, meta );
79
80 /* Nodes go first */
81 if( first->i_children == -1 && second->i_children >= 0 )
82 i_ret = 1;
83 else if( first->i_children >= 0 && second->i_children == -1 )
84 i_ret = -1;
85 /* Both are nodes, sort by name */
86 else if( first->i_children >= 0 && second->i_children >= 0 )
87 i_ret = meta_strcasecmp_title( first, second );
88 /* Both are items */
89 else if( !psz_first && !psz_second )
90 i_ret = 0;
91 else if( !psz_first && psz_second )
92 i_ret = 1;
93 else if( psz_first && !psz_second )
94 i_ret = -1;
95 else
96 {
97 if( b_integer )
98 i_ret = atoi( psz_first ) - atoi( psz_second );
99 else
100 i_ret = strcasecmp( psz_first, psz_second );
101 }
102
103 free( psz_first );
104 free( psz_second );
105 return i_ret;
106 }
107
108 /* Comparison functions */
109
110 /**
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
116 */
117 typedef int (*sortfn_t)(const void *,const void *);
118 static const sortfn_t sorting_fns[NUM_SORT_FNS][2];
find_sorting_fn(unsigned i_mode,unsigned i_type)119 static inline sortfn_t find_sorting_fn( unsigned i_mode, unsigned i_type )
120 {
121 if( i_mode>=NUM_SORT_FNS || i_type>1 )
122 return 0;
123 return sorting_fns[i_mode][i_type];
124 }
125
126 /**
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
131 * @return nothing
132 */
133 static inline
playlist_ItemArraySort(unsigned i_items,playlist_item_t ** pp_items,sortfn_t p_sortfn)134 void playlist_ItemArraySort( unsigned i_items, playlist_item_t **pp_items,
135 sortfn_t p_sortfn )
136 {
137 if( p_sortfn )
138 {
139 qsort( pp_items, i_items, sizeof( pp_items[0] ), p_sortfn );
140 }
141 else /* Randomise */
142 {
143 unsigned i_position;
144 unsigned i_new;
145 playlist_item_t *p_temp;
146
147 for( i_position = i_items - 1; i_position > 0; i_position-- )
148 {
149 i_new = ((unsigned)vlc_mrand48()) % (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;
153 }
154 }
155 }
156
157
158 /**
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
165 */
recursiveNodeSort(playlist_t * p_playlist,playlist_item_t * p_node,sortfn_t p_sortfn)166 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
167 sortfn_t p_sortfn )
168 {
169 int i;
170 playlist_ItemArraySort(p_node->i_children,p_node->pp_children,p_sortfn);
171 for( i = 0 ; i< p_node->i_children; i++ )
172 {
173 if( p_node->pp_children[i]->i_children != -1 )
174 {
175 recursiveNodeSort( p_playlist, p_node->pp_children[i], p_sortfn );
176 }
177 }
178 return VLC_SUCCESS;
179 }
180
181 /**
182 * Sort a node recursively.
183 *
184 * This function must be entered with the playlist lock !
185 *
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
191 */
playlist_RecursiveNodeSort(playlist_t * p_playlist,playlist_item_t * p_node,int i_mode,int i_type)192 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
193 int i_mode, int i_type )
194 {
195 PL_ASSERT_LOCKED;
196
197 /* Ask the playlist to reset as we are changing the order */
198 pl_priv(p_playlist)->b_reset_currently_playing = true;
199
200 /* Do the real job recursively */
201 return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
202 }
203
204
205 /* This is the stuff the sorting functions are made of. The proto_##
206 * functions are wrapped in cmp_a_## and cmp_d_## functions that do
207 * void * to const playlist_item_t * casting and dereferencing and
208 * cmp_d_## inverts the result, too. proto_## are static inline,
209 * cmp_[ad]_## are merely static as they're the target of pointers.
210 *
211 * In any case, each SORT_## constant (except SORT_RANDOM) must have
212 * a matching SORTFN( )-declared function here.
213 */
214
215 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
216 ( const playlist_item_t *first, const playlist_item_t *second )
217
SORTFN(SORT_TRACK_NUMBER,first,second)218 SORTFN( SORT_TRACK_NUMBER, first, second )
219 {
220 return meta_sort( first, second, vlc_meta_TrackNumber, true );
221 }
222
SORTFN(SORT_DISC_NUMBER,first,second)223 SORTFN( SORT_DISC_NUMBER, first, second )
224 {
225 int i_ret = meta_sort( first, second, vlc_meta_DiscNumber, true );
226 /* Items came from the same disc: compare the track numbers */
227 if( i_ret == 0 )
228 i_ret = proto_SORT_TRACK_NUMBER( first, second );
229
230 return i_ret;
231 }
232
SORTFN(SORT_ALBUM,first,second)233 SORTFN( SORT_ALBUM, first, second )
234 {
235 int i_ret = meta_sort( first, second, vlc_meta_Album, false );
236 /* Items came from the same album: compare the disc numbers */
237 if( i_ret == 0 )
238 i_ret = proto_SORT_DISC_NUMBER( first, second );
239
240 return i_ret;
241 }
242
SORTFN(SORT_DATE,first,second)243 SORTFN( SORT_DATE, first, second )
244 {
245 int i_ret = meta_sort( first, second, vlc_meta_Date, true );
246 /* Items came from the same date: compare the albums */
247 if( i_ret == 0 )
248 i_ret = proto_SORT_ALBUM( first, second );
249
250 return i_ret;
251 }
252
SORTFN(SORT_ARTIST,first,second)253 SORTFN( SORT_ARTIST, first, second )
254 {
255 int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
256 /* Items came from the same artist: compare the dates */
257 if( i_ret == 0 )
258 i_ret = proto_SORT_DATE( first, second );
259
260 return i_ret;
261 }
262
SORTFN(SORT_DESCRIPTION,first,second)263 SORTFN( SORT_DESCRIPTION, first, second )
264 {
265 return meta_sort( first, second, vlc_meta_Description, false );
266 }
267
SORTFN(SORT_DURATION,first,second)268 SORTFN( SORT_DURATION, first, second )
269 {
270 mtime_t time1 = input_item_GetDuration( first->p_input );
271 mtime_t time2 = input_item_GetDuration( second->p_input );
272 int i_ret = time1 > time2 ? 1 :
273 ( time1 == time2 ? 0 : -1 );
274 return i_ret;
275 }
276
SORTFN(SORT_GENRE,first,second)277 SORTFN( SORT_GENRE, first, second )
278 {
279 return meta_sort( first, second, vlc_meta_Genre, false );
280 }
281
SORTFN(SORT_ID,first,second)282 SORTFN( SORT_ID, first, second )
283 {
284 return first->i_id - second->i_id;
285 }
286
SORTFN(SORT_RATING,first,second)287 SORTFN( SORT_RATING, first, second )
288 {
289 return meta_sort( first, second, vlc_meta_Rating, true );
290 }
291
SORTFN(SORT_TITLE,first,second)292 SORTFN( SORT_TITLE, first, second )
293 {
294 return meta_strcasecmp_title( first, second );
295 }
296
SORTFN(SORT_TITLE_NODES_FIRST,first,second)297 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
298 {
299 /* If first is a node but not second */
300 if( first->i_children == -1 && second->i_children >= 0 )
301 return -1;
302 /* If second is a node but not first */
303 else if( first->i_children >= 0 && second->i_children == -1 )
304 return 1;
305 /* Both are nodes or both are not nodes */
306 else
307 return meta_strcasecmp_title( first, second );
308 }
309
SORTFN(SORT_TITLE_NUMERIC,first,second)310 SORTFN( SORT_TITLE_NUMERIC, first, second )
311 {
312 int i_ret;
313 char *psz_first = input_item_GetTitleFbName( first->p_input );
314 char *psz_second = input_item_GetTitleFbName( second->p_input );
315
316 if( psz_first && psz_second )
317 i_ret = atoi( psz_first ) - atoi( psz_second );
318 else if( !psz_first && psz_second )
319 i_ret = 1;
320 else if( psz_first && !psz_second )
321 i_ret = -1;
322 else
323 i_ret = 0;
324
325 free( psz_first );
326 free( psz_second );
327 return i_ret;
328 }
329
SORTFN(SORT_URI,first,second)330 SORTFN( SORT_URI, first, second )
331 {
332 int i_ret;
333 char *psz_first = input_item_GetURI( first->p_input );
334 char *psz_second = input_item_GetURI( second->p_input );
335
336 if( psz_first && psz_second )
337 i_ret = strcasecmp( psz_first, psz_second );
338 else if( !psz_first && psz_second )
339 i_ret = 1;
340 else if( psz_first && !psz_second )
341 i_ret = -1;
342 else
343 i_ret = 0;
344
345 free( psz_first );
346 free( psz_second );
347 return i_ret;
348 }
349
350 #undef SORTFN
351
352 /* Generate stubs around the proto_## sorting functions, ascending and
353 * descending both. Preprocessor magic up ahead. Brace yourself.
354 */
355
356 #ifndef VLC_DEFINE_SORT_FUNCTIONS
357 #error Where is VLC_DEFINE_SORT_FUNCTIONS?
358 #endif
359
360 #define DEF( s ) \
361 static int cmp_a_##s(const void *l,const void *r) \
362 { return proto_##s(*(const playlist_item_t *const *)l, \
363 *(const playlist_item_t *const *)r); } \
364 static int cmp_d_##s(const void *l,const void *r) \
365 { return -1*proto_##s(*(const playlist_item_t * const *)l, \
366 *(const playlist_item_t * const *)r); }
367
368 VLC_DEFINE_SORT_FUNCTIONS
369
370 #undef DEF
371
372 /* And populate an array with the addresses */
373
374 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
375 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
376 { VLC_DEFINE_SORT_FUNCTIONS };
377 #undef DEF
378