src/playlist/sort.c

   1 /*****************************************************************************
   2  * playlist/sort.c
   3  *****************************************************************************
   4  * Copyright (C) 2018 VLC authors and VideoLAN
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU Lesser General Public License as published by
   8  * the Free Software Foundation; either version 2.1 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  19  *****************************************************************************/
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #include <vlc_common.h>
  26 #include <vlc_rand.h>
  27 #include "control.h"
  28 #include "item.h"
  29 #include "notify.h"
  30 #include "playlist.h"
  31
  32 /**
  33  * Struct containing a copy of (parsed) media metadata, used for sorting
  34  * without locking all the items.
  35  */
  36 struct vlc_playlist_item_meta {
  37     vlc_playlist_item_t *item;
  38     const char *title_or_name;
  39     vlc_tick_t duration;
  40     const char *artist;
  41     const char *album;
  42     const char *album_artist;
  43     const char *genre;
  44     const char *url;
  45     int64_t date;
  46     int64_t track_number;
  47     int64_t disc_number;
  48     int64_t rating;
  49     bool has_date;
  50     bool has_track_number;
  51     bool has_disc_number;
  52     bool has_rating;
  53 };
  54
  55 static int
  56 vlc_playlist_item_meta_CopyString(const char **to, const char *from)
  57 {
  58     if (from)
  59     {
  60         *to = strdup(from);
  61         if (unlikely(!*to))
  62             return VLC_ENOMEM;
  63     }
  64     else
  65         *to = NULL;
  66     return VLC_SUCCESS;
  67 }
  68
  69 static int
  70 vlc_playlist_item_meta_InitField(struct vlc_playlist_item_meta *meta,
  71                                  enum vlc_playlist_sort_key key)
  72 {
  73     input_item_t *media = meta->item->media;
  74     switch (key)
  75     {
  76         case VLC_PLAYLIST_SORT_KEY_TITLE:
  77         {
  78             const char *value = input_item_GetMetaLocked(media, vlc_meta_Title);
  79             if (EMPTY_STR(value))
  80                 value = media->psz_name;
  81             return vlc_playlist_item_meta_CopyString(&meta->title_or_name,
  82                                                      value);
  83         }
  84         case VLC_PLAYLIST_SORT_KEY_DURATION:
  85         {
  86             if (media->i_duration == INPUT_DURATION_INDEFINITE
  87              || media->i_duration == INPUT_DURATION_UNSET)
  88                 meta->duration = 0;
  89             else
  90                 meta->duration = media->i_duration;
  91             return VLC_SUCCESS;
  92         }
  93         case VLC_PLAYLIST_SORT_KEY_ARTIST:
  94         {
  95             const char *value = input_item_GetMetaLocked(media,
  96                                                          vlc_meta_Artist);
  97             return vlc_playlist_item_meta_CopyString(&meta->artist, value);
  98         }
  99         case VLC_PLAYLIST_SORT_KEY_ALBUM:
 100         {
 101             const char *value = input_item_GetMetaLocked(media, vlc_meta_Album);
 102             return vlc_playlist_item_meta_CopyString(&meta->album, value);
 103         }
 104         case VLC_PLAYLIST_SORT_KEY_ALBUM_ARTIST:
 105         {
 106             const char *value = input_item_GetMetaLocked(media,
 107                                                          vlc_meta_AlbumArtist);
 108             return vlc_playlist_item_meta_CopyString(&meta->album_artist,
 109                                                      value);
 110         }
 111         case VLC_PLAYLIST_SORT_KEY_GENRE:
 112         {
 113             const char *value = input_item_GetMetaLocked(media, vlc_meta_Genre);
 114             return vlc_playlist_item_meta_CopyString(&meta->genre, value);
 115         }
 116         case VLC_PLAYLIST_SORT_KEY_DATE:
 117         {
 118             const char *str = input_item_GetMetaLocked(media, vlc_meta_Date);
 119             meta->has_date = !EMPTY_STR(str);
 120             if (meta->has_date)
 121                 meta->date = atoll(str);
 122             return VLC_SUCCESS;
 123         }
 124         case VLC_PLAYLIST_SORT_KEY_TRACK_NUMBER:
 125         {
 126             const char *str = input_item_GetMetaLocked(media,
 127                                                        vlc_meta_TrackNumber);
 128             meta->has_track_number = !EMPTY_STR(str);
 129             if (meta->has_track_number)
 130                 meta->track_number = atoll(str);
 131             return VLC_SUCCESS;
 132         }
 133         case VLC_PLAYLIST_SORT_KEY_DISC_NUMBER:
 134         {
 135             const char *str = input_item_GetMetaLocked(media,
 136                                                        vlc_meta_DiscNumber);
 137             meta->has_disc_number = !EMPTY_STR(str);
 138             if (meta->has_disc_number)
 139                 meta->disc_number = atoll(str);
 140             return VLC_SUCCESS;
 141         }
 142         case VLC_PLAYLIST_SORT_KEY_URL:
 143         {
 144             const char *value = input_item_GetMetaLocked(media, vlc_meta_URL);
 145             return vlc_playlist_item_meta_CopyString(&meta->url, value);
 146         }
 147         case VLC_PLAYLIST_SORT_KEY_RATING:
 148         {
 149             const char *str = input_item_GetMetaLocked(media, vlc_meta_Rating);
 150             meta->has_rating = !EMPTY_STR(str);
 151             if (meta->has_rating)
 152                 meta->rating = atoll(str);
 153             return VLC_SUCCESS;
 154         }
 155         default:
 156             assert(!"Unknown sort key");
 157             vlc_assert_unreachable();
 158     }
 159 }
 160
 161 static void
 162 vlc_playlist_item_meta_DestroyFields(struct vlc_playlist_item_meta *meta)
 163 {
 164     free((void *) meta->title_or_name);
 165     free((void *) meta->artist);
 166     free((void *) meta->album);
 167     free((void *) meta->album_artist);
 168     free((void *) meta->genre);
 169     free((void *) meta->url);
 170 }
 171
 172 static int
 173 vlc_playlist_item_meta_InitFields(struct vlc_playlist_item_meta *meta,
 174         const struct vlc_playlist_sort_criterion criteria[], size_t count)
 175 {
 176     for (size_t i = 0; i < count; ++i)
 177     {
 178         const struct vlc_playlist_sort_criterion *criterion = &criteria[i];
 179         int ret = vlc_playlist_item_meta_InitField(meta, criterion->key);
 180         if (unlikely(ret != VLC_SUCCESS))
 181         {
 182             vlc_playlist_item_meta_DestroyFields(meta);
 183             return ret;
 184         }
 185     }
 186     return VLC_SUCCESS;
 187 }
 188
 189 static struct vlc_playlist_item_meta *
 190 vlc_playlist_item_meta_New(vlc_playlist_item_t *item,
 191                            const struct vlc_playlist_sort_criterion criteria[],
 192                            size_t count)
 193 {
 194     /* assume that NULL representation is all-zeros */
 195     struct vlc_playlist_item_meta *meta = calloc(1, sizeof(*meta));
 196     if (unlikely(!meta))
 197         return NULL;
 198
 199     meta->item = item;
 200
 201     vlc_mutex_lock(&item->media->lock);
 202     int ret = vlc_playlist_item_meta_InitFields(meta, criteria, count);
 203     vlc_mutex_unlock(&item->media->lock);
 204
 205     if (unlikely(ret != VLC_SUCCESS))
 206     {
 207         free(meta);
 208         return NULL;
 209     }
 210
 211     return meta;
 212 }
 213
 214 static void
 215 vlc_playlist_item_meta_Delete(struct vlc_playlist_item_meta *meta)
 216 {
 217     vlc_playlist_item_meta_DestroyFields(meta);
 218     free(meta);
 219 }
 220
 221 static inline int
 222 CompareStrings(const char *a, const char *b)
 223 {
 224     if (a && b)
 225         return strcasecmp(a, b);
 226     if (!a && !b)
 227         return 0;
 228     return a ? 1 : -1;
 229 }
 230
 231 static inline int
 232 CompareIntegers(int64_t a, int64_t b)
 233 {
 234     if (a < b)
 235         return -1;
 236     if (a > b)
 237         return 1;
 238     return 0;
 239 }
 240
 241 static inline int
 242 CompareOptionalIntegers(bool has_a, int64_t a, bool has_b, int64_t b)
 243 {
 244     if (has_a && has_b)
 245         return CompareIntegers(a, b);
 246
 247     if (!has_a && !has_b)
 248         return 0;
 249
 250     return a ? 1 : -1;
 251 }
 252
 253 static inline int
 254 CompareMetaByKey(const struct vlc_playlist_item_meta *a,
 255                  const struct vlc_playlist_item_meta *b,
 256                  enum vlc_playlist_sort_key key)
 257 {
 258     switch (key)
 259     {
 260         case VLC_PLAYLIST_SORT_KEY_TITLE:
 261             return CompareStrings(a->title_or_name, b->title_or_name);
 262         case VLC_PLAYLIST_SORT_KEY_DURATION:
 263             return CompareIntegers(a->duration, b->duration);
 264         case VLC_PLAYLIST_SORT_KEY_ARTIST:
 265             return CompareStrings(a->artist, b->artist);
 266         case VLC_PLAYLIST_SORT_KEY_ALBUM:
 267             return CompareStrings(a->album, b->album);
 268         case VLC_PLAYLIST_SORT_KEY_ALBUM_ARTIST:
 269             return CompareStrings(a->album_artist, b->album_artist);
 270         case VLC_PLAYLIST_SORT_KEY_GENRE:
 271             return CompareStrings(a->genre, b->genre);
 272         case VLC_PLAYLIST_SORT_KEY_DATE:
 273             return CompareOptionalIntegers(a->has_date, a->date,
 274                                            b->has_date, b->date);
 275         case VLC_PLAYLIST_SORT_KEY_TRACK_NUMBER:
 276             return CompareOptionalIntegers(a->has_track_number, a->track_number,
 277                                            b->has_track_number, b->track_number);
 278         case VLC_PLAYLIST_SORT_KEY_DISC_NUMBER:
 279             return CompareOptionalIntegers(a->has_disc_number, a->disc_number,
 280                                            b->has_disc_number, b->disc_number);
 281         case VLC_PLAYLIST_SORT_KEY_URL:
 282             return CompareStrings(a->url, b->url);
 283         case VLC_PLAYLIST_SORT_KEY_RATING:
 284             return CompareOptionalIntegers(a->has_rating, a->rating,
 285                                            b->has_rating, b->rating);
 286         default:
 287             assert(!"Unknown sort key");
 288             vlc_assert_unreachable();
 289      }
 290 }
 291
 292 /* context for qsort_r() */
 293 struct sort_request
 294 {
 295     const struct vlc_playlist_sort_criterion *criteria;
 296     size_t count;
 297 };
 298
 299 static int
 300 compare_meta(const void *lhs, const void *rhs, void *userdata)
 301 {
 302     struct sort_request *req = userdata;
 303     const struct vlc_playlist_item_meta *a =
 304             *(const struct vlc_playlist_item_meta **) lhs;
 305     const struct vlc_playlist_item_meta *b =
 306             *(const struct vlc_playlist_item_meta **) rhs;
 307
 308     for (size_t i = 0; i < req->count; ++i)
 309     {
 310         const struct vlc_playlist_sort_criterion *criterion = &req->criteria[i];
 311         int ret = CompareMetaByKey(a, b, criterion->key);
 312         if (ret)
 313         {
 314             if (criterion->order == VLC_PLAYLIST_SORT_ORDER_DESCENDING)
 315                 /* do not return -ret, it's undefined if ret == INT_MIN */
 316                 return ret > 0 ? -1 : 1;
 317             return ret;
 318         }
 319     }
 320     return 0;
 321 }
 322
 323 static void
 324 vlc_playlist_DeleteMetaArray(struct vlc_playlist_item_meta *array[],
 325                              size_t count)
 326 {
 327     for (size_t i = 0; i < count; ++i)
 328         vlc_playlist_item_meta_Delete(array[i]);
 329     free(array);
 330 }
 331
 332 static struct vlc_playlist_item_meta **
 333 vlc_playlist_NewMetaArray(vlc_playlist_t *playlist,
 334         const struct vlc_playlist_sort_criterion criteria[], size_t count)
 335 {
 336     struct vlc_playlist_item_meta **array =
 337             vlc_alloc(playlist->items.size, sizeof(*array));
 338
 339     if (unlikely(!array))
 340         return NULL;
 341
 342     size_t i;
 343     for (i = 0; i < playlist->items.size; ++i)
 344     {
 345         array[i] = vlc_playlist_item_meta_New(playlist->items.data[i],
 346                                               criteria, count);
 347         if (unlikely(!array[i]))
 348             break;
 349     }
 350
 351     if (i < playlist->items.size)
 352     {
 353         /* allocation failure */
 354         vlc_playlist_DeleteMetaArray(array, i);
 355         return NULL;
 356     }
 357
 358     return array;
 359 }
 360
 361 int
 362 vlc_playlist_Sort(vlc_playlist_t *playlist,
 363                   const struct vlc_playlist_sort_criterion criteria[],
 364                   size_t count)
 365 {
 366     assert(count > 0);
 367     vlc_playlist_AssertLocked(playlist);
 368
 369     vlc_playlist_item_t *current = playlist->current != -1
 370                                  ? playlist->items.data[playlist->current]
 371                                  : NULL;
 372
 373     struct vlc_playlist_item_meta **array =
 374         vlc_playlist_NewMetaArray(playlist, criteria, count);
 375     if (unlikely(!array))
 376         return VLC_ENOMEM;
 377
 378     struct sort_request req = { criteria, count };
 379
 380     qsort_r(array, playlist->items.size, sizeof(*array), compare_meta, &req);
 381
 382     /* apply the sorting result to the playlist */
 383     for (size_t i = 0; i < playlist->items.size; ++i)
 384         playlist->items.data[i] = array[i]->item;
 385
 386     vlc_playlist_DeleteMetaArray(array, playlist->items.size);
 387
 388     struct vlc_playlist_state state;
 389     if (current)
 390     {
 391         /* the current position have changed after the shuffle */
 392         vlc_playlist_state_Save(playlist, &state);
 393         playlist->current = vlc_playlist_IndexOf(playlist, current);
 394         playlist->has_prev = vlc_playlist_ComputeHasPrev(playlist);
 395         playlist->has_next = vlc_playlist_ComputeHasNext(playlist);
 396     }
 397
 398     vlc_playlist_Notify(playlist, on_items_reset, playlist->items.data,
 399                         playlist->items.size);
 400     if (current)
 401         vlc_playlist_state_NotifyChanges(playlist, &state);
 402
 403     return VLC_SUCCESS;
 404 }