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.

11 files changed, 172 insertions, 187 deletions

diff --git a/common/playlist.c b/common/playlist.c
index b5d6ca15c2..300fc48bf9 100644
--- a/common/playlist.c
+++ b/common/playlist.c
@@ -50,85 +50,68 @@ void playlist_entry_add_params(struct playlist_entry *e,
         playlist_entry_add_param(e, params[n].name, params[n].value);
 }
 
-// Add entry "add" after entry "after".
-// If "after" is NULL, add as first entry.
-// Post condition: add->prev == after
-void playlist_insert(struct playlist *pl, struct playlist_entry *after,
-                     struct playlist_entry *add)
+static void playlist_update_indexes(struct playlist *pl, int start, int end)
 {
-    assert(pl && add->pl == NULL && add->next == NULL && add->prev == NULL);
-    if (after) {
-        assert(after->pl == pl);
-        assert(pl->first && pl->last);
-    }
-    add->prev = after;
-    if (after) {
-        add->next = after->next;
-        after->next = add;
-    } else {
-        add->next = pl->first;
-        pl->first = add;
-    }
-    if (add->next) {
-        add->next->prev = add;
-    } else {
-        pl->last = add;
-    }
+    start = MPMAX(start, 0);
+    end = end < 0 ? pl->num_entries : MPMIN(end, pl->num_entries);
+
+    for (int n = start; n < end; n++)
+        pl->entries[n]->pl_index = n;
+}
+
+void playlist_add(struct playlist *pl, struct playlist_entry *add)
+{
+    MP_TARRAY_APPEND(pl, pl->entries, pl->num_entries, add);
     add->pl = pl;
+    add->pl_index = pl->num_entries - 1;
     talloc_steal(pl, add);
 }
 
-void playlist_add(struct playlist *pl, struct playlist_entry *add)
+void playlist_entry_unref(struct playlist_entry *e)
 {
-    playlist_insert(pl, pl->last, add);
+    e->reserved--;
+    if (e->reserved < 0) {
+        assert(!e->pl);
+        talloc_free(e);
+    }
 }
 
-static void playlist_unlink(struct playlist *pl, struct playlist_entry *entry)
+void playlist_remove(struct playlist *pl, struct playlist_entry *entry)
 {
     assert(pl && entry->pl == pl);
 
     if (pl->current == entry) {
-        pl->current = entry->next;
+        pl->current = playlist_entry_get_rel(entry, 1);
         pl->current_was_replaced = true;
     }
 
-    if (entry->next) {
-        entry->next->prev = entry->prev;
-    } else {
-        pl->last = entry->prev;
-    }
-    if (entry->prev) {
-        entry->prev->next = entry->next;
-    } else {
-        pl->first = entry->next;
-    }
-    entry->next = entry->prev = NULL;
-    // xxx: we'd want to reset the talloc parent of entry
-    entry->pl = NULL;
-}
+    MP_TARRAY_REMOVE_AT(pl->entries, pl->num_entries, entry->pl_index);
+    playlist_update_indexes(pl, entry->pl_index, -1);
 
-void playlist_entry_unref(struct playlist_entry *e)
-{
-    e->reserved--;
-    if (e->reserved < 0)
-        talloc_free(e);
-}
+    entry->pl = NULL;
+    entry->pl_index = -1;
+    ta_set_parent(entry, NULL);
 
-void playlist_remove(struct playlist *pl, struct playlist_entry *entry)
-{
-    playlist_unlink(pl, entry);
     entry->removed = true;
     playlist_entry_unref(entry);
 }
 
 void playlist_clear(struct playlist *pl)
 {
-    while (pl->first)
-        playlist_remove(pl, pl->first);
+    for (int n = pl->num_entries - 1; n >= 0; n--)
+        playlist_remove(pl, pl->entries[n]);
     assert(!pl->current);
     pl->current_was_replaced = false;
 }
 
+void playlist_clear_except_current(struct playlist *pl)
+{
+    for (int n = pl->num_entries - 1; n >= 0; n--) {
+        if (pl->entries[n] != pl->current)
+            playlist_remove(pl, pl->entries[n]);
+    }
+}
+
 // Moves the entry so that it takes "at"'s place (or move to end, if at==NULL).
 void playlist_move(struct playlist *pl, struct playlist_entry *entry,
                    struct playlist_entry *at)
@@ -136,14 +119,19 @@ void playlist_move(struct playlist *pl, struct playlist_entry *entry,
     if (entry == at)
         return;
 
-    struct playlist_entry *save_current = pl->current;
-    bool save_replaced = pl->current_was_replaced;
+    assert(entry && entry->pl == pl);
+    assert(!at || at->pl == pl);
+
+    int index = at ? at->pl_index : pl->num_entries;
+    MP_TARRAY_INSERT_AT(pl, pl->entries, pl->num_entries, index, entry);
 
-    playlist_unlink(pl, entry);
-    playlist_insert(pl, at ? at->prev : pl->last, entry);
+    int old_index = entry->pl_index;
+    if (old_index >= index)
+        old_index += 1;
+    MP_TARRAY_REMOVE_AT(pl->entries, pl->num_entries, old_index);
 
-    pl->current = save_current;
-    pl->current_was_replaced = save_replaced;
+    playlist_update_indexes(pl, MPMIN(index - 1, old_index - 1),
+                                MPMAX(index + 1, old_index + 1));
 }
 
 void playlist_add_file(struct playlist *pl, const char *filename)
@@ -151,34 +139,25 @@ void playlist_add_file(struct playlist *pl, const char *filename)
     playlist_add(pl, playlist_entry_new(filename));
 }
 
-static int playlist_count(struct playlist *pl)
+void playlist_shuffle(struct playlist *pl)
 {
-    int c = 0;
-    for (struct playlist_entry *e = pl->first; e; e = e->next)
-        c++;
-    return c;
+    for (int n = 0; n < pl->num_entries - 1; n++) {
+        int j = (int)((double)(pl->num_entries - n) * rand() / (RAND_MAX + 1.0));
+        MPSWAP(struct playlist_entry *, pl->entries[n], pl->entries[n + j]);
+    }
+    playlist_update_indexes(pl, 0, -1);
 }
 
-void playlist_shuffle(struct playlist *pl)
+// (Explicitly ignores current_was_replaced.)
+struct playlist_entry *playlist_get_first(struct playlist *pl)
 {
-    struct playlist_entry *save_current = pl->current;
-    bool save_replaced = pl->current_was_replaced;
-    int count = playlist_count(pl);
-    struct playlist_entry **arr = talloc_array(NULL, struct playlist_entry *,
-                                               count);
-    for (int n = 0; n < count; n++) {
-        arr[n] = pl->first;
-        playlist_unlink(pl, pl->first);
-    }
-    for (int n = 0; n < count - 1; n++) {
-        int j = (int)((double)(count - n) * rand() / (RAND_MAX + 1.0));
-        MPSWAP(struct playlist_entry *, arr[n], arr[n + j]);
-    }
-    for (int n = 0; n < count; n++)
-        playlist_add(pl, arr[n]);
-    talloc_free(arr);
-    pl->current = save_current;
-    pl->current_was_replaced = save_replaced;
+    return pl->num_entries ? pl->entries[0] : NULL;
+}
+
+// (Explicitly ignores current_was_replaced.)
+struct playlist_entry *playlist_get_last(struct playlist *pl)
+{
+    return pl->num_entries ? pl->entries[pl->num_entries - 1] : NULL;
 }
 
 struct playlist_entry *playlist_get_next(struct playlist *pl, int direction)
@@ -188,15 +167,27 @@ struct playlist_entry *playlist_get_next(struct playlist *pl, int direction)
         return NULL;
     assert(pl->current->pl == pl);
     if (direction < 0)
-        return pl->current->prev;
-    return pl->current_was_replaced ? pl->current : pl->current->next;
+        return playlist_entry_get_rel(pl->current, -1);
+    return pl->current_was_replaced ? pl->current :
+           playlist_entry_get_rel(pl->current, 1);
+}
+
+// (Explicitly ignores current_was_replaced.)
+struct playlist_entry *playlist_entry_get_rel(struct playlist_entry *e,
+                                              int direction)
+{
+    assert(direction == -1 || direction == +1);
+    if (!e->pl)
+        return NULL;
+    return playlist_entry_from_index(e->pl, e->pl_index + direction);
 }
 
 void playlist_add_base_path(struct playlist *pl, bstr base_path)
 {
     if (base_path.len == 0 || bstrcmp0(base_path, ".") == 0)
         return;
-    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];
         if (!mp_is_url(bstr0(e->filename))) {
             char *new_file = mp_path_join_bstr(e, base_path, bstr0(e->filename));
             talloc_free(e->filename);
@@ -208,72 +199,84 @@ void playlist_add_base_path(struct playlist *pl, bstr base_path)
 // Add redirected_from as new redirect entry to each item in pl.
 void playlist_add_redirect(struct playlist *pl, const char *redirected_from)
 {
-    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];
         if (e->num_redirects >= 10) // arbitrary limit for sanity
-            break;
+            continue;
         char *s = talloc_strdup(e, redirected_from);
         if (s)
             MP_TARRAY_APPEND(e, e->redirects, e->num_redirects, s);
     }
 }
 
+void playlist_set_stream_flags(struct playlist *pl, int flags)
+{
+    for (int n = 0; n < pl->num_entries; n++)
+        pl->entries[n]->stream_flags = flags;
+}
+
+static void playlist_transfer_entries_to(struct playlist *pl, int dst_index,
+                                         struct playlist *source_pl)
+{
+    assert(pl != source_pl);
+
+    int count = source_pl->num_entries;
+    MP_TARRAY_INSERT_N_AT(pl, pl->entries, pl->num_entries, dst_index, count);
+
+    for (int n = 0; n < count; n++) {
+        struct playlist_entry *e = source_pl->entries[n];
+        e->pl = pl;
+        e->pl_index = dst_index + n;
+        pl->entries[e->pl_index] = e;
+        talloc_steal(pl, e);
+    }
+
+    playlist_update_indexes(pl, dst_index + count, -1);
+    source_pl->num_entries = 0;
+}
+
 // Move all entries from source_pl to pl, appending them after the current entry
 // of pl. source_pl will be empty, and all entries have changed ownership to pl.
 void playlist_transfer_entries(struct playlist *pl, struct playlist *source_pl)
 {
-    struct playlist_entry *add_after = pl->current;
-    if (pl->current && pl->current_was_replaced)
-        add_after = pl->current->next;
-    if (!add_after)
-        add_after = pl->last;
-
-    while (source_pl->first) {
-        struct playlist_entry *e = source_pl->first;
-        playlist_unlink(source_pl, e);
-        playlist_insert(pl, add_after, e);
-        add_after = e;
+
+    int add_at = pl->num_entries;
+    if (pl->current) {
+        add_at = pl->current->pl_index + 1;
+        if (pl->current_was_replaced)
+            add_at += 1;
     }
+    assert(add_at >= 0);
+    assert(add_at <= pl->num_entries);
+
+    playlist_transfer_entries_to(pl, add_at, source_pl);
 }
 
 void playlist_append_entries(struct playlist *pl, struct playlist *source_pl)
 {
-    while (source_pl->first) {
-        struct playlist_entry *e = source_pl->first;
-        playlist_unlink(source_pl, e);
-        playlist_add(pl, e);
-    }
+    playlist_transfer_entries_to(pl, pl->num_entries, source_pl);
 }
 
 // Return number of entries between list start and e.
 // Return -1 if e is not on the list, or if e is NULL.
 int playlist_entry_to_index(struct playlist *pl, struct playlist_entry *e)
 {
-    struct playlist_entry *cur = pl->first;
-    int pos = 0;
     if (!e)
         return -1;
-    while (cur && cur != e) {
-        cur = cur->next;
-        pos++;
-    }
-    return cur == e ? pos : -1;
+    assert(e->pl == pl);
+    return e->pl_index;
 }
 
 int playlist_entry_count(struct playlist *pl)
 {
-    return playlist_entry_to_index(pl, pl->last) + 1;
+    return pl->num_entries;
 }
 
 // Return entry for which playlist_entry_to_index() would return index.
 // Return NULL if not found.
 struct playlist_entry *playlist_entry_from_index(struct playlist *pl, int index)
 {
-    struct playlist_entry *e = pl->first;
-    for (int n = 0; ; n++) {
-        if (!e || n == index)
-            return e;
-        e = e->next;
-    }
+    return index >= 0 && index < pl->num_entries ? pl->entries[index] : NULL;
 }
 
 struct playlist *playlist_parse_file(const char *file, struct mp_cancel *cancel,
@@ -309,7 +312,7 @@ struct playlist *playlist_parse_file(const char *file, struct mp_cancel *cancel,
         mp_err(log, "Error while parsing playlist\n");
     }
 
-    if (ret && !ret->first)
+    if (ret && !ret->num_entries)
         mp_warn(log, "Warning: empty playlist\n");
 
     talloc_free(log);
diff --git a/common/playlist.h b/common/playlist.h
index bbf6821428..d0f17e315f 100644
--- a/common/playlist.h
+++ b/common/playlist.h
@@ -26,8 +26,9 @@ struct playlist_param {
 };
 
 struct playlist_entry {
-    struct playlist_entry *prev, *next;
+    // Invariant: (pl && pl->entries[pl_index] == this) || (!pl && pl_index < 0)
     struct playlist *pl;
+    int pl_index;
 
     char *filename;
 
@@ -59,7 +60,8 @@ struct playlist_entry {
 };
 
 struct playlist {
-    struct playlist_entry *first, *last;
+    struct playlist_entry **entries;
+    int num_entries;
 
     // This provides some sort of stable iterator. If this entry is removed from
     // the playlist, current is set to the next element (or NULL), and
@@ -75,20 +77,24 @@ void playlist_entry_add_params(struct playlist_entry *e,
 
 struct playlist_entry *playlist_entry_new(const char *filename);
 
-void playlist_insert(struct playlist *pl, struct playlist_entry *after,
-                     struct playlist_entry *add);
 void playlist_add(struct playlist *pl, struct playlist_entry *add);
 void playlist_remove(struct playlist *pl, struct playlist_entry *entry);
 void playlist_clear(struct playlist *pl);
+void playlist_clear_except_current(struct playlist *pl);
 
 void playlist_move(struct playlist *pl, struct playlist_entry *entry,
                    struct playlist_entry *at);
 
 void playlist_add_file(struct playlist *pl, const char *filename);
 void playlist_shuffle(struct playlist *pl);
+struct playlist_entry *playlist_get_first(struct playlist *pl);
+struct playlist_entry *playlist_get_last(struct playlist *pl);
 struct playlist_entry *playlist_get_next(struct playlist *pl, int direction);
+struct playlist_entry *playlist_entry_get_rel(struct playlist_entry *e,
+                                              int direction);
 void playlist_add_base_path(struct playlist *pl, bstr base_path);
 void playlist_add_redirect(struct playlist *pl, const char *redirected_from);
+void playlist_set_stream_flags(struct playlist *pl, int flags);
 void playlist_transfer_entries(struct playlist *pl, struct playlist *source_pl);
 void playlist_append_entries(struct playlist *pl, struct playlist *source_pl);
 
diff --git a/demux/demux_libarchive.c b/demux/demux_libarchive.c
index f2e669aa72..b038e149d9 100644
--- a/demux/demux_libarchive.c
+++ b/demux/demux_libarchive.c
@@ -82,8 +82,7 @@ static int open_file(struct demuxer *demuxer, enum demux_check check)
     for (int n = 0; n < num_files; n++)
         playlist_add_file(pl, files[n]);
 
-    for (struct playlist_entry *e = pl->first; e; e = e->next)
-        e->stream_flags = demuxer->stream_origin;
+    playlist_set_stream_flags(pl, demuxer->stream_origin);
 
     demuxer->filetype = "archive";
     demuxer->fully_read = true;
diff --git a/demux/demux_mkv_timeline.c b/demux/demux_mkv_timeline.c
index 22d859c75c..1062aa3685 100644
--- a/demux/demux_mkv_timeline.c
+++ b/demux/demux_mkv_timeline.c
@@ -258,8 +258,10 @@ static void find_ordered_chapter_sources(struct tl_ctx *ctx)
                 playlist_parse_file(opts->ordered_chapters_files,
                                     ctx->tl->cancel, ctx->global);
             talloc_steal(tmp, pl);
-            for (struct playlist_entry *e = pl ? pl->first : NULL; e; e = e->next)
-                MP_TARRAY_APPEND(tmp, filenames, num_filenames, e->filename);
+            for (int n = 0; n < pl->num_entries; n++) {
+                MP_TARRAY_APPEND(tmp, filenames, num_filenames,
+                                 pl->entries[n]->filename);
+            }
         } else if (!ctx->demuxer->stream->is_local_file) {
             MP_WARN(ctx, "Playback source is not a "
                     "normal disk file. Will not search for related files.\n");
diff --git a/demux/demux_playlist.c b/demux/demux_playlist.c
index b40beda980..417642e75a 100644
--- a/demux/demux_playlist.c
+++ b/demux/demux_playlist.c
@@ -462,8 +462,7 @@ static int open_file(struct demuxer *demuxer, enum demux_check check)
     bool ok = fmt->parse(p) >= 0 && !p->error;
     if (p->add_base)
         playlist_add_base_path(p->pl, mp_dirname(demuxer->filename));
-    for (struct playlist_entry *e = p->pl->first; e; e = e->next)
-        e->stream_flags = demuxer->stream_origin;
+    playlist_set_stream_flags(p->pl, demuxer->stream_origin);
     demuxer->playlist = talloc_steal(demuxer, p->pl);
     demuxer->filetype = p->format ? p->format : fmt->name;
     demuxer->fully_read = true;
diff --git a/options/parse_commandline.c b/options/parse_commandline.c
index 711f1f1df5..e89239c33b 100644
--- a/options/parse_commandline.c
+++ b/options/parse_commandline.c
@@ -165,7 +165,7 @@ int m_config_parse_mp_command_line(m_config_t *config, struct playlist *files,
                 }
                 mode = LOCAL;
                 assert(!local_start);
-                local_start = files->last;
+                local_start = playlist_get_last(files);
                 continue;
             }
 
@@ -179,14 +179,15 @@ int m_config_parse_mp_command_line(m_config_t *config, struct playlist *files,
                     // the entry _after_ local_start, until the end of the list.
                     // If local_start is NULL, the list was empty on '{', and we
                     // want all files in the list.
-                    struct playlist_entry *cur
-                        = local_start ? local_start->next : files->first;
+                    struct playlist_entry *cur = local_start
+                        ? playlist_entry_get_rel(local_start, 1)
+                        : playlist_get_first(files);
                     if (!cur)
                         MP_WARN(config, "Ignored options!\n");
                     while (cur) {
                         playlist_entry_add_params(cur, local_params,
                                                 local_params_count);
-                        cur = cur->next;
+                        cur = playlist_entry_get_rel(cur, 1);
                     }
                 }
                 local_params_count = 0;
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")] ||