git.sesse.net Git - vlc/blob - src/playlist/sort.c

   1 /*****************************************************************************
   2  * sort.c : Playlist sorting functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2009 the VideoLAN team
   5  * $Id$
   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
  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.
  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 General Public License for more details.
  20  *
  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  *****************************************************************************/
  25 #ifdef HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <vlc_common.h>
  30 #define  VLC_INTERNAL_PLAYLIST_SORT_FUNCTIONS
  31 #include "vlc_playlist.h"
  32 #include "playlist_internal.h"
  33
  34
  35 /* General comparison functions */
  36 /**
  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
  41  */
  42 static inline int meta_strcasecmp_title( const playlist_item_t *first,
  43                               const playlist_item_t *second )
  44 {
  45     int i_ret;
  46     char *psz_first = input_item_GetTitleFbName( first->p_input );
  47     char *psz_second = input_item_GetTitleFbName( second->p_input );
  48
  49     if( psz_first && psz_second )
  50         i_ret = strcasecmp( psz_first, psz_second );
  51     else if( !psz_first && psz_second )
  52         i_ret = 1;
  53     else if( psz_first && !psz_second )
  54         i_ret = -1;
  55     else
  56         i_ret = 0;
  57     free( psz_first );
  58     free( psz_second );
  59
  60     return i_ret;
  61 }
  62
  63 /**
  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
  70  */
  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 )
  74 {
  75     int i_ret;
  76     char *psz_first = input_item_GetMeta( first->p_input, meta );
  77     char *psz_second = input_item_GetMeta( second->p_input, meta );
  78
  79     /* Nodes go first */
  80     if( first->i_children == -1 && second->i_children >= 0 )
  81         i_ret = 1;
  82     else if( first->i_children >= 0 && second->i_children == -1 )
  83        i_ret = -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 );
  87     /* Both are items */
  88     else if( !psz_first && psz_second )
  89         i_ret = 1;
  90     else if( psz_first && !psz_second )
  91         i_ret = -1;
  92     /* No meta, sort by name */
  93     else if( !psz_first && !psz_second )
  94         i_ret = meta_strcasecmp_title( first, second );
  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];
 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 i_mode: a SORT_* enum indicating the field to sort on
 131  * @param i_type: ORDER_NORMAL or ORDER_REVERSE
 132  * @return nothing
 133  */
 134 static inline
 135 void playlist_ItemArraySort( unsigned i_items, playlist_item_t **pp_items,
 136                              unsigned i_mode, unsigned i_type )
 137 {
 138     sortfn_t sortfn = find_sorting_fn(i_mode, i_type);
 139
 140     if( sortfn )
 141     {
 142         qsort( pp_items, i_items, sizeof( pp_items[0] ), sortfn );
 143     }
 144     else /* Randomise */
 145     {
 146         int i_position;
 147         playlist_item_t *p_temp;
 148
 149         for( i_position = 0; i_position < i_items ; i_position++ )
 150         {
 151             int i_new;
 152
 153             if( i_items > 1 )
 154                 i_new = rand() % (i_items - 1);
 155             else
 156                 i_new = 0;
 157             p_temp = pp_items[i_position];
 158             pp_items[i_position] = pp_items[i_new];
 159             pp_items[i_new] = p_temp;
 160         }
 161     }
 162 }
 163
 164
 165 /**
 166  * Sort a node recursively.
 167  * This function must be entered with the playlist lock !
 168  * @param p_playlist the playlist
 169  * @param p_node the node to sort
 170  * @param i_mode: SORT_ID, SORT_TITLE, SORT_ARTIST, SORT_ALBUM, SORT_RANDOM
 171  * @param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
 172  * @return VLC_SUCCESS on success
 173  */
 174 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 175                               int i_mode, int i_type )
 176 {
 177     int i;
 178     playlist_ItemArraySort( p_node->i_children, p_node->pp_children,
 179                             i_mode, i_type );
 180     for( i = 0 ; i< p_node->i_children; i++ )
 181     {
 182         if( p_node->pp_children[i]->i_children != -1 )
 183         {
 184             recursiveNodeSort( p_playlist, p_node->pp_children[i],
 185                                i_mode, i_type );
 186         }
 187     }
 188     return VLC_SUCCESS;
 189 }
 190
 191 /**
 192  * Sort a node recursively.
 193  *
 194  * This function must be entered with the playlist lock !
 195  *
 196  * \param p_playlist the playlist
 197  * \param p_node the node to sort
 198  * \param i_mode: SORT_ID, SORT_TITLE, SORT_ARTIST, SORT_ALBUM, SORT_RANDOM
 199  * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
 200  * \return VLC_SUCCESS on success
 201  */
 202 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 203                                 int i_mode, int i_type )
 204 {
 205     /* Ask the playlist to reset as we are changing the order */
 206     pl_priv(p_playlist)->b_reset_currently_playing = true;
 207
 208     /* Do the real job recursively */
 209     return recursiveNodeSort( p_playlist, p_node, i_mode, i_type );
 210 }
 211
 212
 213 /* This is the stuff the sorting functions are made of. The proto_##
 214  * functions are wrapped in cmp_a_## and cmp_d_## functions that do
 215  * void * to const playlist_item_t * casting and dereferencing and
 216  * cmp_d_## inverts the result, too. proto_## are static inline,
 217  * cmp_[ad]_## are merely inline as they're the target of pointers.
 218  *
 219  * In any case, each SORT_## constant (except SORT_RANDOM) must have
 220  * a matching SORTFN( )-declared function here.
 221  */
 222
 223 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
 224         ( const playlist_item_t *first, const playlist_item_t *second )
 225
 226 SORTFN( SORT_ALBUM, first, second )
 227 {
 228     int i_ret = meta_sort( first, second, vlc_meta_Album, false );
 229     /* Items came from the same album: compare the track numbers */
 230     if( i_ret == 0 )
 231         i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
 232
 233     return i_ret;
 234 }
 235
 236 SORTFN( SORT_ARTIST, first, second )
 237 {
 238     int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
 239     /* Items came from the same artist: compare the albums */
 240     if( i_ret == 0 )
 241         i_ret = proto_SORT_ALBUM( first, second );
 242
 243     return i_ret;
 244 }
 245
 246 SORTFN( SORT_DESCRIPTION, first, second )
 247 {
 248     return meta_sort( first, second, vlc_meta_Description, false );
 249 }
 250
 251 SORTFN( SORT_DURATION, first, second )
 252 {
 253     return input_item_GetDuration( first->p_input ) -
 254            input_item_GetDuration( second->p_input );
 255 }
 256
 257 SORTFN( SORT_GENRE, first, second )
 258 {
 259     return meta_sort( first, second, vlc_meta_Genre, false );
 260 }
 261
 262 SORTFN( SORT_ID, first, second )
 263 {
 264     return first->i_id - second->i_id;
 265 }
 266
 267 SORTFN( SORT_RATING, first, second )
 268 {
 269     return meta_sort( first, second, vlc_meta_Rating, true );
 270 }
 271
 272 SORTFN( SORT_TITLE, first, second )
 273 {
 274     return meta_strcasecmp_title( first, second );
 275 }
 276
 277 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
 278 {
 279     /* If first is a node but not second */
 280     if( first->i_children == -1 && second->i_children >= 0 )
 281         return -1;
 282     /* If second is a node but not first */
 283     else if( first->i_children >= 0 && second->i_children == -1 )
 284         return 1;
 285     /* Both are nodes or both are not nodes */
 286     else
 287         return meta_strcasecmp_title( first, second );
 288 }
 289
 290 SORTFN( SORT_TITLE_NUMERIC, first, second )
 291 {
 292     int i_ret;
 293     char *psz_first = input_item_GetTitleFbName( first->p_input );
 294     char *psz_second = input_item_GetTitleFbName( second->p_input );
 295
 296     if( psz_first && psz_second )
 297         i_ret = atoi( psz_first ) - atoi( psz_second );
 298     else if( !psz_first && psz_second )
 299         i_ret = 1;
 300     else if( psz_first && !psz_second )
 301         i_ret = -1;
 302     else
 303         i_ret = 0;
 304
 305     free( psz_first );
 306     free( psz_second );
 307     return i_ret;
 308 }
 309
 310 SORTFN( SORT_TRACK_NUMBER, first, second )
 311 {
 312     return meta_sort( first, second, vlc_meta_TrackNumber, true );
 313 }
 314
 315 SORTFN( SORT_URI, first, second )
 316 {
 317     int i_ret;
 318     char *psz_first = input_item_GetURI( first->p_input );
 319     char *psz_second = input_item_GetURI( second->p_input );
 320
 321     if( psz_first && psz_second )
 322         i_ret = strcasecmp( psz_first, psz_second );
 323     else if( !psz_first && psz_second )
 324         i_ret = 1;
 325     else if( psz_first && !psz_second )
 326         i_ret = -1;
 327     else
 328         i_ret = 0;
 329
 330     free( psz_first );
 331     free( psz_second );
 332     return i_ret;
 333 }
 334
 335 #undef  SORTFN
 336
 337 /* Generate stubs around the proto_## sorting functions, ascending and
 338  * descending both. Preprocessor magic up ahead. Brace yourself.
 339  */
 340
 341 #ifndef VLC_DEFINE_SORT_FUNCTIONS
 342 #error  Where is VLC_DEFINE_SORT_FUNCTIONS?
 343 #endif
 344
 345 #define DEF( s ) \
 346         static int cmp_a_##s(const void *l,const void *r) \
 347         { return proto_##s(*(const playlist_item_t *const *)l, \
 348                            *(const playlist_item_t *const *)r); } \
 349         static int cmp_d_##s(const void *l,const void *r) \
 350         { return -1*proto_##s(*(const playlist_item_t * const *)l, \
 351                               *(const playlist_item_t * const *)r); }
 352
 353         VLC_DEFINE_SORT_FUNCTIONS
 354
 355 #undef  DEF
 356
 357 /* And populate an array with the addresses */
 358
 359 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
 360 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
 361 { VLC_DEFINE_SORT_FUNCTIONS };
 362 #undef  DEF
 363