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