src/playlist/sort.c

   1 /*****************************************************************************
   2  * sort.c : Playlist sorting functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2009 VLC authors and VideoLAN
   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 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  */
  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  */
  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];
 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
 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  */
 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  */
 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
 218 SORTFN( SORT_TRACK_NUMBER, first, second )
 219 {
 220     return meta_sort( first, second, vlc_meta_TrackNumber, true );
 221 }
 222
 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
 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
 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
 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
 263 SORTFN( SORT_DESCRIPTION, first, second )
 264 {
 265     return meta_sort( first, second, vlc_meta_Description, false );
 266 }
 267
 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
 277 SORTFN( SORT_GENRE, first, second )
 278 {
 279     return meta_sort( first, second, vlc_meta_Genre, false );
 280 }
 281
 282 SORTFN( SORT_ID, first, second )
 283 {
 284     return first->i_id - second->i_id;
 285 }
 286
 287 SORTFN( SORT_RATING, first, second )
 288 {
 289     return meta_sort( first, second, vlc_meta_Rating, true );
 290 }
 291
 292 SORTFN( SORT_TITLE, first, second )
 293 {
 294     return meta_strcasecmp_title( first, second );
 295 }
 296
 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
 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
 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