src/playlist/request.c

   1 /*****************************************************************************
   2  * playlist/request.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 "item.h"
  26 #include "playlist.h"
  27
  28 #include <vlc_input_item.h>
  29
  30 int
  31 vlc_playlist_RequestInsert(vlc_playlist_t *playlist, size_t index,
  32                            input_item_t *const media[], size_t count)
  33 {
  34     vlc_playlist_AssertLocked(playlist);
  35
  36     size_t size = vlc_playlist_Count(playlist);
  37     if (index > size)
  38         index = size;
  39
  40     return vlc_playlist_Insert(playlist, index, media, count);
  41 }
  42
  43 static ssize_t
  44 vlc_playlist_FindRealIndex(vlc_playlist_t *playlist, vlc_playlist_item_t *item,
  45                            ssize_t index_hint)
  46 {
  47     if (index_hint != -1 && (size_t) index_hint < vlc_playlist_Count(playlist))
  48     {
  49         if (item == vlc_playlist_Get(playlist, index_hint))
  50             /* we are lucky */
  51             return index_hint;
  52     }
  53
  54     /* we are unlucky, we need to find the item */
  55     return vlc_playlist_IndexOf(playlist, item);
  56 }
  57
  58 struct size_vector VLC_VECTOR(size_t);
  59
  60 static void
  61 vlc_playlist_FindIndices(vlc_playlist_t *playlist,
  62                          vlc_playlist_item_t *const items[], size_t count,
  63                          ssize_t index_hint, struct size_vector *out)
  64 {
  65     for (size_t i = 0; i < count; ++i)
  66     {
  67         ssize_t real_index = vlc_playlist_FindRealIndex(playlist, items[i],
  68                                                         index_hint);
  69         if (real_index != -1)
  70         {
  71             int ok = vlc_vector_push(out, real_index);
  72             assert(ok); /* cannot fail, space had been reserved */
  73             VLC_UNUSED(ok);
  74             /* the next item is expected after this one */
  75             index_hint = real_index + 1;
  76         }
  77     }
  78 }
  79
  80 static void
  81 vlc_playlist_RemoveBySlices(vlc_playlist_t *playlist, size_t sorted_indices[],
  82                             size_t count)
  83 {
  84     assert(count > 0);
  85     size_t last_index = sorted_indices[count - 1];
  86     size_t slice_size = 1;
  87     /* size_t is unsigned, take care not to test for non-negativity */
  88     for (size_t i = count - 1; i != 0; --i)
  89     {
  90         size_t index = sorted_indices[i - 1];
  91         if (index == last_index - 1)
  92             slice_size++;
  93         else
  94         {
  95             /* the previous slice is complete */
  96             vlc_playlist_Remove(playlist, last_index, slice_size);
  97             slice_size = 1;
  98         }
  99         last_index = index;
 100     }
 101     /* remove the last slice */
 102     vlc_playlist_Remove(playlist, last_index, slice_size);
 103 }
 104
 105 /**
 106  * Move all items specified by their indices to form a contiguous slice, in
 107  * order.
 108  *
 109  * \param playlist   the playlist
 110  * \param indices    the indices of the items to regroup
 111  * \param head_index the index where to prepend the group
 112  * \return the start index of the resulting slice
 113  */
 114 static size_t
 115 vlc_playlist_Regroup(vlc_playlist_t *playlist, size_t indices[],
 116                      size_t head_index)
 117 {
 118     size_t head = indices[head_index];
 119     if (head_index == 0)
 120         /* nothing to regroup */
 121         return head;
 122
 123     size_t slice_size = 1;
 124     size_t last_index = indices[head_index - 1];
 125
 126     /* size_t is unsigned, take care not to test for non-negativity */
 127     for (size_t i = head_index - 1; i != 0; --i)
 128     {
 129         size_t index = indices[i - 1];
 130         if (index == last_index - 1)
 131             slice_size++;
 132         else
 133         {
 134             assert(last_index != head);
 135             if (last_index < head)
 136             {
 137                 assert(head >= slice_size);
 138                 head -= slice_size;
 139
 140                 /* update index of items that will be moved as a side-effect */
 141                 for (size_t j = 0; j <= i; ++j)
 142                     if (indices[j] >= last_index + slice_size && indices[j] < head)
 143                         indices[j] -= slice_size;
 144             }
 145             else
 146             {
 147                 /* update index of items that will be moved as a side-effect */
 148                 for (size_t j = 0; j <= i; ++j)
 149                     if (indices[j] >= head && indices[j] < last_index)
 150                         indices[j] += slice_size;
 151             }
 152             index = indices[i - 1]; /* current index might have been updated */
 153
 154             /* the slice is complete, move it to build the unique slice */
 155             vlc_playlist_Move(playlist, last_index, slice_size, head);
 156             slice_size = 1;
 157         }
 158
 159         last_index = index;
 160     }
 161
 162     /* move the last slice to build the unique slice */
 163     if (last_index < head)
 164     {
 165         assert(head >= slice_size);
 166         head -= slice_size;
 167     }
 168     vlc_playlist_Move(playlist, last_index, slice_size, head);
 169     return head;
 170 }
 171
 172 static void
 173 vlc_playlist_MoveBySlices(vlc_playlist_t *playlist, size_t indices[],
 174                           size_t count, size_t target)
 175 {
 176     assert(count > 0);
 177
 178     /* pass the last slice */
 179     size_t i;
 180     for (i = count - 1; i != 0; --i)
 181         if (indices[i - 1] != indices[i] - 1)
 182             break;
 183
 184     /* regroup items to form a unique slice */
 185     size_t head = vlc_playlist_Regroup(playlist, indices, i);
 186
 187     /* move the unique slice to the requested target */
 188     if (head != target)
 189         vlc_playlist_Move(playlist, head, count, target);
 190 }
 191
 192 static int
 193 cmp_size(const void *lhs, const void *rhs)
 194 {
 195     size_t a = *(size_t *) lhs;
 196     size_t b = *(size_t *) rhs;
 197     if (a < b)
 198         return -1;
 199     if (a == b)
 200         return 0;
 201     return 1;
 202 }
 203
 204 int
 205 vlc_playlist_RequestMove(vlc_playlist_t *playlist,
 206                          vlc_playlist_item_t *const items[], size_t count,
 207                          size_t target, ssize_t index_hint)
 208 {
 209     vlc_playlist_AssertLocked(playlist);
 210
 211     struct size_vector vector = VLC_VECTOR_INITIALIZER;
 212     if (!vlc_vector_reserve(&vector, count))
 213         return VLC_ENOMEM;
 214
 215     vlc_playlist_FindIndices(playlist, items, count, index_hint, &vector);
 216
 217     size_t move_count = vector.size;
 218     if (move_count)
 219     {
 220         size_t size = vlc_playlist_Count(playlist);
 221         assert(size >= move_count);
 222         /* move at most to the end of the list */
 223         if (target + move_count > size)
 224             target = size - move_count;
 225
 226         /* keep the items in the same order as the request (do not sort them) */
 227         vlc_playlist_MoveBySlices(playlist, vector.data, vector.size, target);
 228     }
 229
 230     vlc_vector_destroy(&vector);
 231     return VLC_SUCCESS;
 232 }
 233
 234 int
 235 vlc_playlist_RequestRemove(vlc_playlist_t *playlist,
 236                            vlc_playlist_item_t *const items[], size_t count,
 237                            ssize_t index_hint)
 238 {
 239     vlc_playlist_AssertLocked(playlist);
 240
 241     struct size_vector vector = VLC_VECTOR_INITIALIZER;
 242     if (!vlc_vector_reserve(&vector, count))
 243         return VLC_ENOMEM;
 244
 245     vlc_playlist_FindIndices(playlist, items, count, index_hint, &vector);
 246
 247     if (vector.size > 0)
 248     {
 249         /* sort so that removing an item does not shift the other indices */
 250         qsort(vector.data, vector.size, sizeof(vector.data[0]), cmp_size);
 251
 252         vlc_playlist_RemoveBySlices(playlist, vector.data, vector.size);
 253     }
 254
 255     vlc_vector_destroy(&vector);
 256     return VLC_SUCCESS;
 257 }
 258
 259 int
 260 vlc_playlist_RequestGoTo(vlc_playlist_t *playlist, vlc_playlist_item_t *item,
 261                          ssize_t index_hint)
 262 {
 263     vlc_playlist_AssertLocked(playlist);
 264     ssize_t real_index = item
 265                        ? vlc_playlist_FindRealIndex(playlist, item, index_hint)
 266                        : -1;
 267     return vlc_playlist_GoTo(playlist, real_index);
 268 }