playlist: change from linked list to an array

Although a linked list was ideal at first, there are cases where it
sucks, and became increasingly awkward (with the mpv command API
preferring integer indexes to access the list). In future, we probably
want to add more playlist-related functionality, so better change it to
an array now.

An array isn't always ideal either. Since playlist entries are still
separate objects (because in some cases you need a stable "iterator" to
it), but you still need to efficiently get the next/previous playlist
entry, there's a pl_index field, that needs to be maintained. E.g.
adding an entry at the start of the playlist => update the pl_index
field for all other entries. Well, it's not really worth to do something
more complicated to avoid these things.

This commit is probably buggy as shit. It's not like I bothered to test
everything. That's _your_ role.

5 files changed, 30 insertions, 55 deletions

diff --git a/player/command.c b/player/command.c
index a6ceaf039a..084fd0fc4e 100644
--- a/player/command.c
+++ b/player/command.c
@@ -2709,7 +2709,7 @@ static int mp_property_playlist_pos_x(void *ctx, struct m_property *prop,
 {
     MPContext *mpctx = ctx;
     struct playlist *pl = mpctx->playlist;
-    if (!pl->first)
+    if (!pl->num_entries)
         return M_PROPERTY_UNAVAILABLE;
 
     switch (action) {
@@ -2754,30 +2754,11 @@ static int mp_property_playlist_pos_1(void *ctx, struct m_property *prop,
     return mp_property_playlist_pos_x(ctx, prop, action, arg, 1);
 }
 
-struct get_playlist_ctx {
-    struct MPContext *mpctx;
-    int last_index;
-    struct playlist_entry *last_entry;
-};
-
 static int get_playlist_entry(int item, int action, void *arg, void *ctx)
 {
-    struct get_playlist_ctx *p = ctx;
-    struct MPContext *mpctx = p->mpctx;
-
-    struct playlist_entry *e;
-    // This is an optimization that prevents O(n^2) behaviour when the entire
-    // playlist is requested. If a request is made for the last requested entry
-    // or the entry immediately following it, it can be found without a full
-    // traversal of the linked list.
-    if (p->last_entry && item == p->last_index)
-        e = p->last_entry;
-    else if (p->last_entry && item == p->last_index + 1)
-        e = p->last_entry->next;
-    else
-        e = playlist_entry_from_index(mpctx->playlist, item);
-    p->last_index = item;
-    p->last_entry = e;
+    struct MPContext *mpctx = ctx;
+
+    struct playlist_entry *e = playlist_entry_from_index(mpctx->playlist, item);
     if (!e)
         return M_PROPERTY_ERROR;
 
@@ -2802,8 +2783,8 @@ static int mp_property_playlist(void *ctx, struct m_property *prop,
         struct playlist *pl = mpctx->playlist;
         char *res = talloc_strdup(NULL, "");
 
-        for (struct playlist_entry *e = pl->first; e; e = e->next)
-        {
+        for (int n = 0; n < pl->num_entries; n++) {
+            struct playlist_entry *e = pl->entries[n];
             char *p = e->title;
             if (!p) {
                 p = e->filename;
@@ -2822,9 +2803,8 @@ static int mp_property_playlist(void *ctx, struct m_property *prop,
         return M_PROPERTY_OK;
     }
 
-    struct get_playlist_ctx p = {.mpctx = mpctx};
     return m_property_read_list(action, arg, playlist_entry_count(mpctx->playlist),
-                                get_playlist_entry, &p);
+                                get_playlist_entry, mpctx);
 }
 
 static char *print_obj_osd_list(struct m_obj_settings *list)
@@ -4860,8 +4840,11 @@ static void cmd_loadlist(void *p)
         playlist_append_entries(mpctx->playlist, pl);
         talloc_free(pl);
 
-        if (!append && mpctx->playlist->first)
-            mp_set_playlist_entry(mpctx, new ? new : mpctx->playlist->first);
+        if (!new)
+            new = playlist_get_first(mpctx->playlist);
+
+        if (!append && new)
+            mp_set_playlist_entry(mpctx, new);
 
         mp_notify(mpctx, MP_EVENT_CHANGE_PLAYLIST, NULL);
         mp_wakeup_core(mpctx);
@@ -4879,15 +4862,7 @@ static void cmd_playlist_clear(void *p)
     // Supposed to clear the playlist, except the currently played item.
     if (mpctx->playlist->current_was_replaced)
         mpctx->playlist->current = NULL;
-    while (mpctx->playlist->first) {
-        struct playlist_entry *e = mpctx->playlist->first;
-        if (e == mpctx->playlist->current) {
-            e = e->next;
-            if (!e)
-                break;
-        }
-        playlist_remove(mpctx->playlist, e);
-    }
+    playlist_clear_except_current(mpctx->playlist);
     mp_notify(mpctx, MP_EVENT_CHANGE_PLAYLIST, NULL);
     mp_wakeup_core(mpctx);
 }
diff --git a/player/configfiles.c b/player/configfiles.c
index d9a1e7d9f1..658b3549bc 100644
--- a/player/configfiles.c
+++ b/player/configfiles.c
@@ -451,7 +451,8 @@ struct playlist_entry *mp_check_playlist_resume(struct MPContext *mpctx,
 {
     if (!mpctx->opts->position_resume)
         return NULL;
-    for (struct playlist_entry *e = playlist->first; e; e = e->next) {
+    for (int n = 0; n < playlist->num_entries; n++) {
+        struct playlist_entry *e = playlist->entries[n];
         char *conf = mp_get_playback_resume_config_filename(mpctx, e->filename);
         bool exists = conf && mp_path_exists(conf);
         talloc_free(conf);
diff --git a/player/loadfile.c b/player/loadfile.c
index 462355f60e..f9dac4684d 100644
--- a/player/loadfile.c
+++ b/player/loadfile.c
@@ -905,14 +905,14 @@ void prepare_playlist(struct MPContext *mpctx, struct playlist *pl)
         pl->current = mp_check_playlist_resume(mpctx, pl);
 
     if (!pl->current)
-        pl->current = pl->first;
+        pl->current = playlist_get_first(pl);
 }
 
 // Replace the current playlist entry with playlist contents. Moves the entries
 // from the given playlist pl, so the entries don't actually need to be copied.
 static void transfer_playlist(struct MPContext *mpctx, struct playlist *pl)
 {
-    if (pl->first) {
+    if (pl->num_entries) {
         prepare_playlist(mpctx, pl);
         struct playlist_entry *new = pl->current;
         if (mpctx->playlist->current)
@@ -1441,8 +1441,7 @@ static void play_current_file(struct MPContext *mpctx)
 
     handle_force_window(mpctx, false);
 
-    if (mpctx->playlist->first != mpctx->playing ||
-        mpctx->playlist->last != mpctx->playing ||
+    if (mpctx->playlist->num_entries > 1 ||
         mpctx->playing->num_redirects)
         MP_INFO(mpctx, "Playing: %s\n", mpctx->filename);
 
@@ -1720,34 +1719,33 @@ struct playlist_entry *mp_next_file(struct MPContext *mpctx, int direction,
     if (next && direction < 0 && !force) {
         // Don't jump to files that would immediately go to next file anyway
         while (next && next->playback_short)
-            next = next->prev;
+            next = playlist_entry_get_rel(next, -1);
         // Always allow jumping to first file
         if (!next && mpctx->opts->loop_times == 1)
-            next = mpctx->playlist->first;
+            next = playlist_get_first(mpctx->playlist);
     }
     if (!next && mpctx->opts->loop_times != 1) {
         if (direction > 0) {
             if (mpctx->opts->shuffle)
                 playlist_shuffle(mpctx->playlist);
-            next = mpctx->playlist->first;
+            next = playlist_get_first(mpctx->playlist);
             if (next && mpctx->opts->loop_times > 1) {
                 mpctx->opts->loop_times--;
                 m_config_notify_change_opt_ptr(mpctx->mconfig,
                                                &mpctx->opts->loop_times);
             }
         } else {
-            next = mpctx->playlist->last;
+            next = playlist_get_last(mpctx->playlist);
             // Don't jump to files that would immediately go to next file anyway
             while (next && next->playback_short)
-                next = next->prev;
+                next = playlist_entry_get_rel(next, -1);
         }
         bool ignore_failures = mpctx->opts->loop_times == -2;
         if (!force && next && next->init_failed && !ignore_failures) {
             // Don't endless loop if no file in playlist is playable
             bool all_failed = true;
-            struct playlist_entry *cur;
-            for (cur = mpctx->playlist->first; cur; cur = cur->next) {
-                all_failed &= cur->init_failed;
+            for (int n = 0; n < mpctx->playlist->num_entries; n++) {
+                all_failed &= mpctx->playlist->entries[n]->init_failed;
                 if (!all_failed)
                     break;
             }
diff --git a/player/main.c b/player/main.c
index 983f463d3e..6cb56ef601 100644
--- a/player/main.c
+++ b/player/main.c
@@ -404,7 +404,7 @@ int mp_initialize(struct MPContext *mpctx, char **options)
         return run_tests(mpctx) ? 1 : -1;
 #endif
 
-    if (!mpctx->playlist->first && !opts->player_idle_mode) {
+    if (!mpctx->playlist->num_entries && !opts->player_idle_mode) {
         // nothing to play
         mp_print_version(mpctx->log, true);
         MP_INFO(mpctx, "%s", mp_help_text);
diff --git a/player/misc.c b/player/misc.c
index 5a96d6cc25..c3765e5055 100644
--- a/player/misc.c
+++ b/player/misc.c
@@ -278,11 +278,12 @@ int stream_dump(struct MPContext *mpctx, const char *source_filename)
 
 void merge_playlist_files(struct playlist *pl)
 {
-    if (!pl->first)
+    if (!pl->num_entries)
         return;
     char *edl = talloc_strdup(NULL, "edl://");
-    for (struct playlist_entry *e = pl->first; e; e = e->next) {
-        if (e != pl->first)
+    for (int n = 0; n < pl->num_entries; n++) {
+        struct playlist_entry *e = pl->entries[n];
+        if (n)
             edl = talloc_strdup_append_buffer(edl, ";");
         // Escape if needed
         if (e->filename[strcspn(e->filename, "=%,;\n")] ||