Steve Lhomme pushed to branch master at VideoLAN / VLC
Commits:
4fdd351c by Romain Vimont at 2023-02-10T07:46:02+00:00
playlist: use stable sort
An unstable sort may confuse users.
Since we already create a full array of items with their metadata before
sorting, adding the initial index as an additional criteria is almost
free.
Fixes #27783
- - - - -
2 changed files:
- src/playlist/sort.c
- src/playlist/test.c
Changes:
=====================================
src/playlist/sort.c
=====================================
@@ -37,6 +37,7 @@
*/
struct vlc_playlist_item_meta {
vlc_playlist_item_t *item;
+ size_t index;
const char *title_or_name;
vlc_tick_t duration;
const char *artist;
@@ -240,7 +241,7 @@ vlc_playlist_item_meta_InitFields(struct
vlc_playlist_item_meta *meta,
}
static struct vlc_playlist_item_meta *
-vlc_playlist_item_meta_New(vlc_playlist_item_t *item,
+vlc_playlist_item_meta_New(size_t index, vlc_playlist_item_t *item,
const struct vlc_playlist_sort_criterion criteria[],
size_t count)
{
@@ -250,6 +251,7 @@ vlc_playlist_item_meta_New(vlc_playlist_item_t *item,
return NULL;
meta->item = item;
+ meta->index = index;
vlc_mutex_lock(&item->media->lock);
int ret = vlc_playlist_item_meta_InitFields(meta, criteria, count);
@@ -394,7 +396,11 @@ compare_meta(const void *lhs, const void *rhs, void
*userdata)
return ret;
}
}
- return 0;
+
+ /* If the items are equals regarding the sorting criteria, keep their
+ * initial relative order, to make the sort stable. */
+ assert(a->index != b->index);
+ return a->index < b->index ? -1 : 1;
}
static void
@@ -419,7 +425,7 @@ vlc_playlist_NewMetaArray(vlc_playlist_t *playlist,
size_t i;
for (i = 0; i < playlist->items.size; ++i)
{
- array[i] = vlc_playlist_item_meta_New(playlist->items.data[i],
+ array[i] = vlc_playlist_item_meta_New(i, playlist->items.data[i],
criteria, count);
if (unlikely(!array[i]))
break;
=====================================
src/playlist/test.c
=====================================
@@ -2349,6 +2349,80 @@ test_sort(void)
vlc_playlist_Delete(playlist);
}
+static void
+test_stable_sort(void)
+{
+ vlc_playlist_t *playlist = vlc_playlist_New(NULL);
+ assert(playlist);
+
+ input_item_t *media[10];
+ media[0] = CreateDummyMedia(1); media[0]->i_duration = 10;
+ media[1] = CreateDummyMedia(1); media[1]->i_duration = 20;
+ media[2] = CreateDummyMedia(1); media[2]->i_duration = 30;
+ media[3] = CreateDummyMedia(3); media[3]->i_duration = 10;
+ media[4] = CreateDummyMedia(3); media[4]->i_duration = 20;
+ media[5] = CreateDummyMedia(3); media[5]->i_duration = 30;
+ media[6] = CreateDummyMedia(4); media[6]->i_duration = 10;
+ media[7] = CreateDummyMedia(2); media[7]->i_duration = 20;
+ media[8] = CreateDummyMedia(2); media[8]->i_duration = 30;
+ media[9] = CreateDummyMedia(2); media[9]->i_duration = 10;
+
+ /* initial playlist with 10 items */
+ int ret = vlc_playlist_Append(playlist, media, 10);
+ assert(ret == VLC_SUCCESS);
+
+ struct vlc_playlist_sort_criterion criteria[] = {
+ { VLC_PLAYLIST_SORT_KEY_TITLE, VLC_PLAYLIST_SORT_ORDER_ASCENDING },
+ { VLC_PLAYLIST_SORT_KEY_DURATION, VLC_PLAYLIST_SORT_ORDER_ASCENDING },
+ };
+
+ /* first sort by the 2nd criteria (duration) */
+ vlc_playlist_Sort(playlist, &criteria[1], 1);
+
+ EXPECT_AT(0, 0);
+ EXPECT_AT(1, 3);
+ EXPECT_AT(2, 6);
+ EXPECT_AT(3, 9);
+ EXPECT_AT(4, 1);
+ EXPECT_AT(5, 4);
+ EXPECT_AT(6, 7);
+ EXPECT_AT(7, 2);
+ EXPECT_AT(8, 5);
+ EXPECT_AT(9, 8);
+
+ /* then sort by the 1st criteria (title) */
+ vlc_playlist_Sort(playlist, &criteria[0], 1);
+
+ EXPECT_AT(0, 0);
+ EXPECT_AT(1, 1);
+ EXPECT_AT(2, 2);
+ EXPECT_AT(3, 9);
+ EXPECT_AT(4, 7);
+ EXPECT_AT(5, 8);
+ EXPECT_AT(6, 3);
+ EXPECT_AT(7, 4);
+ EXPECT_AT(8, 5);
+ EXPECT_AT(9, 6);
+
+ /* sorting by both criteria at once must be equivalent */
+ vlc_playlist_Shuffle(playlist);
+ vlc_playlist_Sort(playlist, criteria, 2);
+
+ EXPECT_AT(0, 0);
+ EXPECT_AT(1, 1);
+ EXPECT_AT(2, 2);
+ EXPECT_AT(3, 9);
+ EXPECT_AT(4, 7);
+ EXPECT_AT(5, 8);
+ EXPECT_AT(6, 3);
+ EXPECT_AT(7, 4);
+ EXPECT_AT(8, 5);
+ EXPECT_AT(9, 6);
+
+ DestroyMediaArray(media, 10);
+ vlc_playlist_Delete(playlist);
+}
+
#undef EXPECT_AT
int main(void)
@@ -2384,6 +2458,7 @@ int main(void)
test_random();
test_shuffle();
test_sort();
+ test_stable_sort();
return 0;
}
View it on GitLab:
https://code.videolan.org/videolan/vlc/-/commit/4fdd351c85ed9caf10c15b21ad9fd33c7d24441d
--
View it on GitLab:
https://code.videolan.org/videolan/vlc/-/commit/4fdd351c85ed9caf10c15b21ad9fd33c7d24441d
You're receiving this email because of your account on code.videolan.org.
VideoLAN code repository instance_______________________________________________
vlc-commits mailing list
vlc-commits@videolan.org
https://mailman.videolan.org/listinfo/vlc-commits
