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
  22  * along with this program; if not, write to the Free Software
  23  * Foundation, 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_playlist.h"
  31 #include "playlist_internal.h"
  32
  33
  34 static void playlist_ItemArraySort( int i_items, playlist_item_t **pp_items,
  35                                     int i_mode, int i_type );
  36 static int playlist_cmp( const void *, const void * );
  37
  38 /* Comparaison functions */
  39 static int playlist_cmp_album( const playlist_item_t *, const playlist_item_t *);
  40 static int playlist_cmp_artist( const playlist_item_t *, const playlist_item_t *);
  41 static int playlist_cmp_desc( const playlist_item_t *, const playlist_item_t *);
  42 static int playlist_cmp_duration( const playlist_item_t *, const playlist_item_t *);
  43 static int playlist_cmp_genre( const playlist_item_t *, const playlist_item_t *);
  44 static int playlist_cmp_id( const playlist_item_t *, const playlist_item_t *);
  45 static int playlist_cmp_rating( const playlist_item_t *, const playlist_item_t *);
  46 static int playlist_cmp_title( const playlist_item_t *, const playlist_item_t *);
  47 static int playlist_cmp_title_nodes_first( const playlist_item_t *,
  48                                           const playlist_item_t *);
  49 static int playlist_cmp_title_num( const playlist_item_t *, const playlist_item_t *);
  50 static int playlist_cmp_track_num( const playlist_item_t *, const playlist_item_t *);
  51 static int playlist_cmp_uri( const playlist_item_t *, const playlist_item_t *);
  52
  53 /* General comaraison functions */
  54 static inline int meta_strcasecmp_title( const playlist_item_t *,
  55                                   const playlist_item_t *);
  56 static inline int meta_sort( const playlist_item_t *, const playlist_item_t *,
  57                       vlc_meta_type_t, bool );
  58
  59
  60 /**
  61  * Sort a node recursively.
  62  * This function must be entered with the playlist lock !
  63  * @param p_playlist the playlist
  64  * @param p_node the node to sort
  65  * @param i_mode: SORT_ID, SORT_TITLE, SORT_ARTIST, SORT_ALBUM, SORT_RANDOM
  66  * @param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
  67  * @return VLC_SUCCESS on success
  68  */
  69 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
  70                               int i_mode, int i_type )
  71 {
  72     int i;
  73     playlist_ItemArraySort( p_node->i_children, p_node->pp_children,
  74                             i_mode, i_type );
  75     for( i = 0 ; i< p_node->i_children; i++ )
  76     {
  77         if( p_node->pp_children[i]->i_children != -1 )
  78         {
  79             recursiveNodeSort( p_playlist, p_node->pp_children[i],
  80                                i_mode, i_type );
  81         }
  82     }
  83     return VLC_SUCCESS;
  84 }
  85
  86 /**
  87  * Sort a node recursively.
  88  *
  89  * This function must be entered with the playlist lock !
  90  *
  91  * \param p_playlist the playlist
  92  * \param p_node the node to sort
  93  * \param i_mode: SORT_ID, SORT_TITLE, SORT_ARTIST, SORT_ALBUM, SORT_RANDOM
  94  * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
  95  * \return VLC_SUCCESS on success
  96  */
  97 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
  98                                 int i_mode, int i_type )
  99 {
 100     /* Ask the playlist to reset as we are changing the order */
 101     pl_priv(p_playlist)->b_reset_currently_playing = true;
 102
 103     /* Do the real job recursively */
 104     return recursiveNodeSort( p_playlist, p_node, i_mode, i_type );
 105 }
 106
 107
 108 static int (*sort_function)(const playlist_item_t *, const playlist_item_t *);
 109 static int sort_order = 1;
 110
 111
 112 /**
 113  * Sort an array of items recursively
 114  * @param i_items: number of items
 115  * @param pp_items: the array of items
 116  * @param i_mode: the criterias for the comparisons
 117  * @param i_type: ORDER_NORMAL or ORDER_REVERSE
 118  * @return nothing
 119  */
 120 static void playlist_ItemArraySort( int i_items, playlist_item_t **pp_items,
 121                                    int i_mode, int i_type )
 122 {
 123     int i_position;
 124     playlist_item_t *p_temp;
 125
 126     /* Random sort */
 127     if( i_mode == SORT_RANDOM )
 128     {
 129         for( i_position = 0; i_position < i_items ; i_position++ )
 130         {
 131             int i_new;
 132
 133             if( i_items > 1 )
 134                 i_new = rand() % (i_items - 1);
 135             else
 136                 i_new = 0;
 137             p_temp = pp_items[i_position];
 138             pp_items[i_position] = pp_items[i_new];
 139             pp_items[i_new] = p_temp;
 140         }
 141     }
 142     else
 143     {
 144         /* Choose the funtion to compare two items */
 145         switch( i_mode )
 146         {
 147         case SORT_ALBUM:
 148             sort_function = playlist_cmp_album;
 149             break;
 150         case SORT_ARTIST:
 151             sort_function = playlist_cmp_artist;
 152             break;
 153         case SORT_DESCRIPTION:
 154             sort_function = playlist_cmp_desc;
 155             break;
 156         case SORT_DURATION:
 157             sort_function = playlist_cmp_duration;
 158             break;
 159         case SORT_GENRE:
 160             sort_function = playlist_cmp_genre;
 161             break;
 162         case SORT_ID:
 163             sort_function = playlist_cmp_id;
 164             break;
 165         case SORT_TITLE:
 166             sort_function = playlist_cmp_title;
 167             break;
 168         case SORT_TITLE_NODES_FIRST:
 169             sort_function = playlist_cmp_title_nodes_first;
 170             break;
 171         case SORT_TITLE_NUMERIC:
 172             sort_function = playlist_cmp_title_num;
 173             break;
 174         case SORT_TRACK_NUMBER:
 175             sort_function = playlist_cmp_track_num;
 176             break;
 177         case SORT_RATING:
 178             sort_function = playlist_cmp_rating;
 179             break;
 180         case SORT_URI:
 181             sort_function = playlist_cmp_uri;
 182             break;
 183         default:
 184             assert(0);
 185         }
 186         sort_order = i_type == ORDER_REVERSE ? -1 : 1;
 187         qsort( pp_items, i_items, sizeof( pp_items[0] ), playlist_cmp );
 188     }
 189 }
 190
 191
 192 /**
 193  * Wrapper around playlist_cmp_* function
 194  * @param first: the first item
 195  * @param second: the second item
 196  * @return -1, 0 or 1 like strcmp
 197  */
 198 static int playlist_cmp( const void *first, const void *second )
 199 {
 200     if( sort_order == -1 )
 201         return -1 * sort_function( *(playlist_item_t **)first,
 202                                    *(playlist_item_t **)second );
 203     else
 204         return sort_function( *(playlist_item_t **)first,
 205                               *(playlist_item_t **)second );
 206 }
 207
 208
 209 /**
 210  * Compare two items according to the title
 211  * @param first: the first item
 212  * @param second: the second item
 213  * @return -1, 0 or 1 like strcmp
 214  */
 215 static int playlist_cmp_album( const playlist_item_t *first,
 216                                const playlist_item_t *second )
 217 {
 218     int i_ret = meta_sort( first, second, vlc_meta_Album, false );
 219     /* Items came from the same album: compare the track numbers */
 220     if( i_ret == 0 )
 221         i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
 222
 223     return i_ret;
 224 }
 225
 226
 227 /**
 228  * Compare two items according to the artist
 229  * @param first: the first item
 230  * @param second: the second item
 231  * @return -1, 0 or 1 like strcmp
 232  */
 233 static int playlist_cmp_artist( const playlist_item_t *first,
 234                                 const playlist_item_t *second )
 235 {
 236     int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
 237     /* Items came from the same artist: compare the albums */
 238     if( i_ret == 0 )
 239         i_ret = playlist_cmp_album( first, second );
 240
 241     return i_ret;
 242 }
 243
 244
 245 /**
 246  * Compare two items according to the description
 247  * @param first: the first item
 248  * @param second: the second item
 249  * @return -1, 0 or 1 like strcmp
 250  */
 251 static int playlist_cmp_desc( const playlist_item_t *first,
 252                               const playlist_item_t *second )
 253 {
 254     return meta_sort( first, second, vlc_meta_Description, false );
 255 }
 256
 257
 258 /**
 259  * Compare two items according to the duration
 260  * @param first: the first item
 261  * @param second: the second item
 262  * @return -1, 0 or 1 like strcmp
 263  */
 264 static int playlist_cmp_duration( const playlist_item_t *first,
 265                                   const playlist_item_t *second )
 266 {
 267     return input_item_GetDuration( first->p_input ) -
 268            input_item_GetDuration( second->p_input );
 269 }
 270
 271
 272 /**
 273  * Compare two items according to the genre
 274  * @param first: the first item
 275  * @param second: the second item
 276  * @return -1, 0 or 1 like strcmp
 277  */
 278 static int playlist_cmp_genre( const playlist_item_t *first,
 279                                const playlist_item_t *second )
 280 {
 281     return meta_sort( first, second, vlc_meta_Genre, false );
 282 }
 283
 284
 285 /**
 286  * Compare two items according to the ID
 287  * @param first: the first item
 288  * @param second: the second item
 289  * @return -1, 0 or 1 like strcmp
 290  */
 291 static int playlist_cmp_id( const playlist_item_t *first,
 292                             const playlist_item_t *second )
 293 {
 294     return first->i_id - second->i_id;
 295 }
 296
 297
 298 /**
 299  * Compare two items according to the rating
 300  * @param first: the first item
 301  * @param second: the second item
 302  * @return -1, 0 or 1 like strcmp
 303  */
 304 static int playlist_cmp_rating( const playlist_item_t *first,
 305                                 const playlist_item_t *second )
 306 {
 307     return meta_sort( first, second, vlc_meta_Rating, true );
 308 }
 309
 310
 311 /**
 312  * Compare two items according to the title
 313  * @param first: the first item
 314  * @param second: the second item
 315  * @return -1, 0 or 1 like strcmp
 316  */
 317 static int playlist_cmp_title( const playlist_item_t *first,
 318                                const playlist_item_t *second )
 319 {
 320     return meta_strcasecmp_title( first, second );
 321 }
 322
 323
 324 /**
 325  * Compare two items according to the title, with the nodes first in the list
 326  * @param first: the first item
 327  * @param second: the second item
 328  * @return -1, 0 or 1 like strcmp
 329  */
 330 static int playlist_cmp_title_nodes_first( const playlist_item_t *first,
 331                                            const playlist_item_t *second )
 332 {
 333     /* If first is a node but not second */
 334     if( first->i_children == -1 && second->i_children >= 0 )
 335         return -1;
 336     /* If second is a node but not first */
 337     else if( first->i_children >= 0 && second->i_children == -1 )
 338         return 1;
 339     /* Both are nodes or both are not nodes */
 340     else
 341         return meta_strcasecmp_title( first, second );
 342 }
 343
 344
 345 /**
 346  * Compare two item according to the title as a numeric value
 347  * @param first: the first item
 348  * @param second: the second item
 349  * @return -1, 0 or 1 like strcmp
 350  */
 351 static int playlist_cmp_title_num( const playlist_item_t *first,
 352                                    const playlist_item_t *second )
 353 {
 354     int i_ret;
 355     char *psz_first = input_item_GetTitleFbName( first->p_input );
 356     char *psz_second = input_item_GetTitleFbName( second->p_input );
 357
 358     if( psz_first && psz_second )
 359         i_ret = atoi( psz_first ) - atoi( psz_second );
 360     else if( !psz_first && psz_second )
 361         i_ret = 1;
 362     else if( psz_first && !psz_second )
 363         i_ret = -1;
 364     else
 365         i_ret = 0;
 366
 367     free( psz_first );
 368     free( psz_second );
 369     return i_ret;
 370 }
 371
 372
 373 /**
 374  * Compare two item according to the track number
 375  * @param first: the first item
 376  * @param second: the second item
 377  * @return -1, 0 or 1 like strcmp
 378  */
 379 static int playlist_cmp_track_num( const playlist_item_t *first,
 380                                    const playlist_item_t *second )
 381 {
 382     return meta_sort( first, second, vlc_meta_TrackNumber, true );
 383 }
 384
 385
 386 /**
 387  * Compare two item according to the URI
 388  * @param first: the first item
 389  * @param second: the second item
 390  * @return -1, 0 or 1 like strcmp
 391  */
 392 static int playlist_cmp_uri( const playlist_item_t *first,
 393                              const playlist_item_t *second )
 394 {
 395     int i_ret;
 396     char *psz_first = input_item_GetURI( first->p_input );
 397     char *psz_second = input_item_GetURI( second->p_input );
 398
 399     if( psz_first && psz_second )
 400         i_ret = strcasecmp( psz_first, psz_second );
 401     else if( !psz_first && psz_second )
 402         i_ret = 1;
 403     else if( psz_first && !psz_second )
 404         i_ret = -1;
 405     else
 406         i_ret = 0;
 407
 408     free( psz_first );
 409     free( psz_second );
 410     return i_ret;
 411 }
 412
 413
 414 /**
 415  * Compare two items using their title or name
 416  * @param first: the first item
 417  * @param second: the second item
 418  * @return -1, 0 or 1 like strcmp
 419  */
 420 static inline int meta_strcasecmp_title( const playlist_item_t *first,
 421                               const playlist_item_t *second )
 422 {
 423     int i_ret;
 424     char *psz_first = input_item_GetTitleFbName( first->p_input );
 425     char *psz_second = input_item_GetTitleFbName( second->p_input );
 426
 427     if( psz_first && psz_second )
 428         i_ret = strcasecmp( psz_first, psz_second );
 429     else if( !psz_first && psz_second )
 430         i_ret = 1;
 431     else if( psz_first && !psz_second )
 432         i_ret = -1;
 433     else
 434         i_ret = 0;
 435     free( psz_first );
 436     free( psz_second );
 437
 438     return i_ret;
 439 }
 440
 441
 442 /**
 443  * Compare two intems accoring to the given meta type
 444  * @param first: the first item
 445  * @param second: the second item
 446  * @param meta: the meta type to use to sort the items
 447  * @param b_integer: true if the meta are integers
 448  * @return -1, 0 or 1 like strcmp
 449  */
 450 static inline int meta_sort( const playlist_item_t *first,
 451                              const playlist_item_t *second,
 452                              vlc_meta_type_t meta, bool b_integer )
 453 {
 454     int i_ret;
 455     char *psz_first = input_item_GetMeta( first->p_input, meta );
 456     char *psz_second = input_item_GetMeta( second->p_input, meta );
 457
 458     /* Nodes go first */
 459     if( first->i_children == -1 && second->i_children >= 0 )
 460         i_ret = 1;
 461     else if( first->i_children >= 0 && second->i_children == -1 )
 462        i_ret = -1;
 463     /* Both are nodes, sort by name */
 464     else if( first->i_children >= 0 && second->i_children >= 0 )
 465         i_ret = meta_strcasecmp_title( first, second );
 466     /* Both are items */
 467     else if( !psz_first && psz_second )
 468         i_ret = 1;
 469     else if( psz_first && !psz_second )
 470         i_ret = -1;
 471     /* No meta, sort by name */
 472     else if( !psz_first && !psz_second )
 473         i_ret = meta_strcasecmp_title( first, second );
 474     else
 475     {
 476         if( b_integer )
 477             i_ret = atoi( psz_first ) - atoi( psz_second );
 478         else
 479             i_ret = strcasecmp( psz_first, psz_second );
 480     }
 481
 482     free( psz_first );
 483     free( psz_second );
 484     return i_ret;
 485 }
 486