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 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 = rand() % i_position;
 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     /* Ask the playlist to reset as we are changing the order */
 196     pl_priv(p_playlist)->b_reset_currently_playing = true;
 197
 198     /* Do the real job recursively */
 199     return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
 200 }
 201
 202
 203 /* This is the stuff the sorting functions are made of. The proto_##
 204  * functions are wrapped in cmp_a_## and cmp_d_## functions that do
 205  * void * to const playlist_item_t * casting and dereferencing and
 206  * cmp_d_## inverts the result, too. proto_## are static inline,
 207  * cmp_[ad]_## are merely static as they're the target of pointers.
 208  *
 209  * In any case, each SORT_## constant (except SORT_RANDOM) must have
 210  * a matching SORTFN( )-declared function here.
 211  */
 212
 213 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
 214         ( const playlist_item_t *first, const playlist_item_t *second )
 215
 216 SORTFN( SORT_ALBUM, first, 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 SORTFN( SORT_ARTIST, first, second )
 227 {
 228     int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
 229     /* Items came from the same artist: compare the albums */
 230     if( i_ret == 0 )
 231         i_ret = proto_SORT_ALBUM( first, second );
 232
 233     return i_ret;
 234 }
 235
 236 SORTFN( SORT_DESCRIPTION, first, second )
 237 {
 238     return meta_sort( first, second, vlc_meta_Description, false );
 239 }
 240
 241 SORTFN( SORT_DURATION, first, second )
 242 {
 243     mtime_t time1 = input_item_GetDuration( first->p_input );
 244     mtime_t time2 = input_item_GetDuration( second->p_input );
 245     int i_ret = time1 > time2 ? 1 :
 246                     ( time1 == time2 ? 0 : -1 );
 247     return i_ret;
 248 }
 249
 250 SORTFN( SORT_GENRE, first, second )
 251 {
 252     return meta_sort( first, second, vlc_meta_Genre, false );
 253 }
 254
 255 SORTFN( SORT_ID, first, second )
 256 {
 257     return first->i_id - second->i_id;
 258 }
 259
 260 SORTFN( SORT_RATING, first, second )
 261 {
 262     return meta_sort( first, second, vlc_meta_Rating, true );
 263 }
 264
 265 SORTFN( SORT_TITLE, first, second )
 266 {
 267     return meta_strcasecmp_title( first, second );
 268 }
 269
 270 SORTFN( SORT_TITLE_NODES_FIRST, first, second )
 271 {
 272     /* If first is a node but not second */
 273     if( first->i_children == -1 && second->i_children >= 0 )
 274         return -1;
 275     /* If second is a node but not first */
 276     else if( first->i_children >= 0 && second->i_children == -1 )
 277         return 1;
 278     /* Both are nodes or both are not nodes */
 279     else
 280         return meta_strcasecmp_title( first, second );
 281 }
 282
 283 SORTFN( SORT_TITLE_NUMERIC, first, second )
 284 {
 285     int i_ret;
 286     char *psz_first = input_item_GetTitleFbName( first->p_input );
 287     char *psz_second = input_item_GetTitleFbName( second->p_input );
 288
 289     if( psz_first && psz_second )
 290         i_ret = atoi( psz_first ) - atoi( psz_second );
 291     else if( !psz_first && psz_second )
 292         i_ret = 1;
 293     else if( psz_first && !psz_second )
 294         i_ret = -1;
 295     else
 296         i_ret = 0;
 297
 298     free( psz_first );
 299     free( psz_second );
 300     return i_ret;
 301 }
 302
 303 SORTFN( SORT_TRACK_NUMBER, first, second )
 304 {
 305     return meta_sort( first, second, vlc_meta_TrackNumber, true );
 306 }
 307
 308 SORTFN( SORT_URI, first, second )
 309 {
 310     int i_ret;
 311     char *psz_first = input_item_GetURI( first->p_input );
 312     char *psz_second = input_item_GetURI( second->p_input );
 313
 314     if( psz_first && psz_second )
 315         i_ret = strcasecmp( psz_first, psz_second );
 316     else if( !psz_first && psz_second )
 317         i_ret = 1;
 318     else if( psz_first && !psz_second )
 319         i_ret = -1;
 320     else
 321         i_ret = 0;
 322
 323     free( psz_first );
 324     free( psz_second );
 325     return i_ret;
 326 }
 327
 328 #undef  SORTFN
 329
 330 /* Generate stubs around the proto_## sorting functions, ascending and
 331  * descending both. Preprocessor magic up ahead. Brace yourself.
 332  */
 333
 334 #ifndef VLC_DEFINE_SORT_FUNCTIONS
 335 #error  Where is VLC_DEFINE_SORT_FUNCTIONS?
 336 #endif
 337
 338 #define DEF( s ) \
 339         static int cmp_a_##s(const void *l,const void *r) \
 340         { return proto_##s(*(const playlist_item_t *const *)l, \
 341                            *(const playlist_item_t *const *)r); } \
 342         static int cmp_d_##s(const void *l,const void *r) \
 343         { return -1*proto_##s(*(const playlist_item_t * const *)l, \
 344                               *(const playlist_item_t * const *)r); }
 345
 346         VLC_DEFINE_SORT_FUNCTIONS
 347
 348 #undef  DEF
 349
 350 /* And populate an array with the addresses */
 351
 352 static const sortfn_t sorting_fns[NUM_SORT_FNS][2] =
 353 #define DEF( a ) { cmp_a_##a, cmp_d_##a },
 354 { VLC_DEFINE_SORT_FUNCTIONS };
 355 #undef  DEF
 356