From 68dc869d6aa8eb7004e2f86e9e4dcbf203ae6a8c Mon Sep 17 00:00:00 2001 From: James Ross-Gowan Date: Fri, 19 Aug 2016 23:13:54 +1000 Subject: 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. --- player/command.c | 28 +++++++++++++++++++++++++--- 1 file 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) -- cgit v1.2.3