src/playlist/shuffle.c

   1 /*****************************************************************************
   2  * playlist/shuffle.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 void
  33 vlc_playlist_Shuffle(vlc_playlist_t *playlist)
  34 {
  35     vlc_playlist_AssertLocked(playlist);
  36     if (playlist->items.size < 2)
  37         /* we use size_t (unsigned), so the following loop would be incorrect */
  38         return;
  39
  40     vlc_playlist_item_t *current = playlist->current != -1
  41                                  ? playlist->items.data[playlist->current]
  42                                  : NULL;
  43
  44     /* initialize separately instead of using vlc_lrand48() to avoid locking the
  45      * mutex once for each item */
  46     unsigned short xsubi[3];
  47     vlc_rand_bytes(xsubi, sizeof(xsubi));
  48
  49     /* Fisher-Yates shuffle */
  50     for (size_t i = playlist->items.size - 1; i != 0; --i)
  51     {
  52         size_t selected = (size_t) (nrand48(xsubi) % (i + 1));
  53
  54         /* swap items i and selected */
  55         vlc_playlist_item_t *tmp = playlist->items.data[i];
  56         playlist->items.data[i] = playlist->items.data[selected];
  57         playlist->items.data[selected] = tmp;
  58     }
  59
  60     struct vlc_playlist_state state;
  61     if (current)
  62     {
  63         /* the current position have changed after the shuffle */
  64         vlc_playlist_state_Save(playlist, &state);
  65         playlist->current = vlc_playlist_IndexOf(playlist, current);
  66         playlist->has_prev = vlc_playlist_ComputeHasPrev(playlist);
  67         playlist->has_next = vlc_playlist_ComputeHasNext(playlist);
  68     }
  69
  70     vlc_playlist_Notify(playlist, on_items_reset, playlist->items.data,
  71                         playlist->items.size);
  72     if (current)
  73         vlc_playlist_state_NotifyChanges(playlist, &state);
  74 }