command: prevent O(n^2) behaviour for playlist property

When fetching the playlist property, playlist_entry_from_index would be
called for each playlist entry, which traversed a linked list to get the
entry corresponding to the specified index. This was very slow for large
playlists. Since get_playlist_entry is called for each index in order,
it can avoid a full traversal of the linked list by using the next
pointer on the previously requested entry.

1 files changed, 25 insertions, 3 deletions

diff --git a/player/command.c b/player/command.c
index 99538cebcf..e9a051db8c 100644
--- a/player/command.c
+++ b/player/command.c
@@ -3192,10 +3192,30 @@ 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 MPContext *mpctx = ctx;
-    struct playlist_entry *e = playlist_entry_from_index(mpctx->playlist, item);
+    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;
     if (!e)
         return M_PROPERTY_ERROR;
 
@@ -3235,8 +3255,10 @@ static int mp_property_playlist(void *ctx, struct m_property *prop,
         *(char **)arg = res;
         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, mpctx);
+                                get_playlist_entry, &p);
 }
 
 static char *print_obj_osd_list(struct m_obj_settings *list)