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         playlist_item_t *p_temp;
 145
 146         for( i_position = 0; i_position < i_items ; i_position++ )
 147         {
 148             int i_new;
 149
 150             if( i_items > 1 )
 151                 i_new = rand() % (i_items - 1);
 152             else
 153                 i_new = 0;
 154             p_temp = pp_items[i_position];
 155             pp_items[i_position] = pp_items[i_new];
 156             pp_items[i_new] = p_temp;
 157         }
 158     }
 159 }
 160
 161
 162 /**
 163  * Sort a node recursively.
 164  * This function must be entered with the playlist lock !
 165  * @param p_playlist the playlist
 166  * @param p_node the node to sort
 167  * @param p_sortfn the sorting function
 168  * @return VLC_SUCCESS on success
 169  */
 170 static int recursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 171                               sortfn_t p_sortfn )
 172 {
 173     int i;
 174     playlist_ItemArraySort(p_node->i_children,p_node->pp_children,p_sortfn);
 175     for( i = 0 ; i< p_node->i_children; i++ )
 176     {
 177         if( p_node->pp_children[i]->i_children != -1 )
 178         {
 179             recursiveNodeSort( p_playlist, p_node->pp_children[i], p_sortfn );
 180         }
 181     }
 182     return VLC_SUCCESS;
 183 }
 184
 185 /**
 186  * Sort a node recursively.
 187  *
 188  * This function must be entered with the playlist lock !
 189  *
 190  * \param p_playlist the playlist
 191  * \param p_node the node to sort
 192  * \param i_mode: a SORT_* constant indicating the field to sort on
 193  * \param i_type: ORDER_NORMAL or ORDER_REVERSE (reversed order)
 194  * \return VLC_SUCCESS on success
 195  */
 196 int playlist_RecursiveNodeSort( playlist_t *p_playlist, playlist_item_t *p_node,
 197                                 int i_mode, int i_type )
 198 {
 199     /* Ask the playlist to reset as we are changing the order */
 200     pl_priv(p_playlist)->b_reset_currently_playing = true;
 201
 202     /* Do the real job recursively */
 203     return recursiveNodeSort(p_playlist,p_node,find_sorting_fn(i_mode,i_type));
 204 }
 205
 206
 207 /* This is the stuff the sorting functions are made of. The proto_##
 208  * functions are wrapped in cmp_a_## and cmp_d_## functions that do
 209  * void * to const playlist_item_t * casting and dereferencing and
 210  * cmp_d_## inverts the result, too. proto_## are static inline,
 211  * cmp_[ad]_## are merely static as they're the target of pointers.
 212  *
 213  * In any case, each SORT_## constant (except SORT_RANDOM) must have
 214  * a matching SORTFN( )-declared function here.
 215  */
 216
 217 #define SORTFN( SORT, first, second ) static inline int proto_##SORT \
 218         ( const playlist_item_t *first, const playlist_item_t *second )
 219
 220 SORTFN( SORT_ALBUM, first, second )
 221 {
 222     int i_ret = meta_sort( first, second, vlc_meta_Album, false );
 223     /* Items came from the same album: compare the track numbers */
 224     if( i_ret == 0 )
 225         i_ret = meta_sort( first, second, vlc_meta_TrackNumber, true );
 226
 227     return i_ret;
 228 }
 229
 230 SORTFN( SORT_ARTIST, first, second )
 231 {
 232     int i_ret = meta_sort( first, second, vlc_meta_Artist, false );
 233     /* Items came from the same artist: compare the albums */
 234     if( i_ret == 0 )
 235         i_ret = proto_SORT_ALBUM( first, second );
 236
 237     return i_ret;
 238 }
 239
 240 SORTFN( SORT_DESCRIPTION, first, second )
 241 {
 242     return meta_sort( first, second, vlc_meta_Description, false );
 243 }
 244
 245 SORTFN( SORT_DURATION, first, second )
 246 {
 247     return input_item_GetDuration( first->p_input ) -
 248            input_item_GetDuration( second->p_input );
 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