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 accoring 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 = 1;
  91     else if( psz_first && !psz_second )
  92         i_ret = -1;
  93     /* No meta, sort by name */
  94     else if( !psz_first && !psz_second )
  95         i_ret = meta_strcasecmp_title( first, second );
  96     else
  97     {
  98         if( b_integer )
  99             i_ret = atoi( psz_first ) - atoi( psz_second );
 100         else
 101             i_ret = strcasecmp( psz_first, psz_second );
 102     }
 103
 104     free( psz_first );
 105     free( psz_second );
 106     return i_ret;
 107 }
 108
 109 /* Comparison functions */
 110
 111 /**
 112  * Return the comparison function appropriate for the SORT_* and ORDER_*
 113  * arguments given, or NULL for SORT_RANDOM.
 114  * @param i_mode: a SORT_* enum indicating the field to sort on
 115  * @param i_type: ORDER_NORMAL or ORDER_REVERSE
 116  * @return function pointer, or NULL for SORT_RANDOM or invalid input
 117  */
 118 typedef int (*sortfn_t)(const void *,const void *);
 119 static const sortfn_t sorting_fns[NUM_SORT_FNS][2];
 120 static inline sortfn_t find_sorting_fn( unsigned i_mode, unsigned i_type )
 121 {
 122     if( i_mode>=NUM_SORT_FNS || i_type>1 )
 123         return 0;
 124     return sorting_fns[i_mode][i_type];
 125 }
 126
 127 /**
 128  * Sort an array of items recursively
 129  * @param i_items: number of items
 130  * @param pp_items: the array of items
 131  * @param p_sortfn: the sorting function
 132  * @return nothing
 133  */
 134 static inline
 135 void playlist_ItemArraySort( unsigned i_items, playlist_item_t **pp_items,
 136                              sortfn_t p_sortfn )
 137 {
 138     if( p_sortfn )
 139     {
 140         qsort( pp_items, i_items, sizeof( pp_items[0] ), p_sortfn );
 141     }
 142     else /* Randomise */
 143     {
 144         unsigned i_position;
 145         unsigned i_new;
 146         playlist_item_t *p_temp;
 147
 148         for( i_position = i_items - 1; i_position > 0; i_position-- )
 149         {
 150             i_new = ((unsigned)vlc_mrand48()) % (i_position+1);
 151             p_temp = pp_items[i_position];
 152             pp_items[i_position] = pp_items[i_new];
 153             pp_items[i_new] = p_temp;
 154         }
 155     }
 156 }
 157
 158
 159 /**
 160  * Sort a node recursively.
 161  * This function must be entered with the playlist lock !
 162  * @param p_playlist the playlist
 163  * @param p_node the node to sort
 164  * @param p_sortfn the sorting function
 165  * @return VLC_SUCCESS on success
 166  */
 167 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 168                               sortfn_t p_sortfn )
 169 {
 170     int i;
 171     playlist_ItemArraySort(p_node->i_children,p_node->pp_children,p_sortfn);
 172     for( i = 0 ; i< p_node->i_children; i++ )
 173     {
 174         if( p_node->pp_children[i]->i_children != -1 )
 175         {
 176             recursiveNodeSort( p_playlist, p_node->pp_children[i], p_sortfn );
 177         }
 178     }
 179     return VLC_SUCCESS;
 180 }
 181
 182 /**
 183  * Sort a node recursively.
 184  *
 185  * This function must be entered with the playlist lock !
 186  *
 187  * \param p_playlist the playlist
 188  * \param p_node the node to sort
 189  * \param i_mode: a SORT_* constant indicating the field to sort on
 190  * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
 191  * \return VLC_SUCCESS on success
 192  */
 193 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 194                                 int i_mode, int i_type )
 195 {
 196     /* Ask the playlist to reset as we are changing the order */
 197     pl_priv(p_playlist)->b_reset_currently_playing = true;
 198
 199     /* Do the real job recursively */
 200     return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
 201 }
 202
 203
 204 /* This is the stuff the sorting functions are made of. The proto_##
 205  * functions are wrapped in cmp_a_## and cmp_d_## functions that do
 206  * void * to const playlist_item_t * casting and dereferencing and
 207  * cmp_d_## inverts the result, too. proto_## are static inline,
 208  * cmp_[ad]_## are merely static as they're the target of pointers.
 209  *
 210  * In any case, each SORT_## constant (except SORT_RANDOM) must have
 211  * a matching SORTFN( )-declared function here.
 212  */
 213
 214 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
 215         ( const playlist_item_t *first, const playlist_item_t *second )
 216
 217 SORTFN( SORT_ALBUM, first, second )
 218 {
 219     int i_ret = meta_sort( first, second, vlc_meta_Album, false );
 220     /* Items came from the same album: compare the track numbers */
 221     if( i_ret == 0 )
 222         i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
 223
 224     return i_ret;
 225 }
 226
 227 SORTFN( SORT_ARTIST, first, second )
 228 {
 229     int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
 230     /* Items came from the same artist: compare the albums */
 231     if( i_ret == 0 )
 232         i_ret = proto_SORT_ALBUM( first, second );
 233
 234     return i_ret;
 235 }
 236
 237 SORTFN( SORT_DESCRIPTION, first, second )
 238 {
 239     return meta_sort( first, second, vlc_meta_Description, false );
 240 }
 241
 242 SORTFN( SORT_DURATION, first, second )
 243 {
 244     mtime_t time1 = input_item_GetDuration( first->p_input );
 245     mtime_t time2 = input_item_GetDuration( second->p_input );
 246     int i_ret = time1 > time2 ? 1 :
 247                     ( time1 == time2 ? 0 : -1 );
 248     return i_ret;
 249 }
 250
 251 SORTFN( SORT_GENRE, first, second )
 252 {
 253     return meta_sort( first, second, vlc_meta_Genre, false );
 254 }
 255
 256 SORTFN( SORT_ID, first, second )
 257 {
 258     return first->i_id - second->i_id;
 259 }
 260
 261 SORTFN( SORT_RATING, first, second )
 262 {
 263     return meta_sort( first, second, vlc_meta_Rating, true );
 264 }
 265
 266 SORTFN( SORT_TITLE, first, second )
 267 {
 268     return meta_strcasecmp_title( first, second );
 269 }
 270
 271 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
 272 {
 273     /* If first is a node but not second */
 274     if( first->i_children == -1 && second->i_children >= 0 )
 275         return -1;
 276     /* If second is a node but not first */
 277     else if( first->i_children >= 0 && second->i_children == -1 )
 278         return 1;
 279     /* Both are nodes or both are not nodes */
 280     else
 281         return meta_strcasecmp_title( first, second );
 282 }
 283
 284 SORTFN( SORT_TITLE_NUMERIC, first, second )
 285 {
 286     int i_ret;
 287     char *psz_first = input_item_GetTitleFbName( first->p_input );
 288     char *psz_second = input_item_GetTitleFbName( second->p_input );
 289
 290     if( psz_first && psz_second )
 291         i_ret = atoi( psz_first ) - atoi( psz_second );
 292     else if( !psz_first && psz_second )
 293         i_ret = 1;
 294     else if( psz_first && !psz_second )
 295         i_ret = -1;
 296     else
 297         i_ret = 0;
 298
 299     free( psz_first );
 300     free( psz_second );
 301     return i_ret;
 302 }
 303
 304 SORTFN( SORT_TRACK_NUMBER, first, second )
 305 {
 306     return meta_sort( first, second, vlc_meta_TrackNumber, true );
 307 }
 308
 309 SORTFN( SORT_URI, first, second )
 310 {
 311     int i_ret;
 312     char *psz_first = input_item_GetURI( first->p_input );
 313     char *psz_second = input_item_GetURI( second->p_input );
 314
 315     if( psz_first && psz_second )
 316         i_ret = strcasecmp( psz_first, psz_second );
 317     else if( !psz_first && psz_second )
 318         i_ret = 1;
 319     else if( psz_first && !psz_second )
 320         i_ret = -1;
 321     else
 322         i_ret = 0;
 323
 324     free( psz_first );
 325     free( psz_second );
 326     return i_ret;
 327 }
 328
 329 #undef  SORTFN
 330
 331 /* Generate stubs around the proto_## sorting functions, ascending and
 332  * descending both. Preprocessor magic up ahead. Brace yourself.
 333  */
 334
 335 #ifndef VLC_DEFINE_SORT_FUNCTIONS
 336 #error  Where is VLC_DEFINE_SORT_FUNCTIONS?
 337 #endif
 338
 339 #define DEF( s ) \
 340         static int cmp_a_##s(const void *l,const void *r) \
 341         { return proto_##s(*(const playlist_item_t *const *)l, \
 342                            *(const playlist_item_t *const *)r); } \
 343         static int cmp_d_##s(const void *l,const void *r) \
 344         { return -1*proto_##s(*(const playlist_item_t * const *)l, \
 345                               *(const playlist_item_t * const *)r); }
 346
 347         VLC_DEFINE_SORT_FUNCTIONS
 348
 349 #undef  DEF
 350
 351 /* And populate an array with the addresses */
 352
 353 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
 354 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
 355 { VLC_DEFINE_SORT_FUNCTIONS };
 356 #undef  DEF
 357