diff options
author | James Ross-Gowan <rossymiles@gmail.com> | 2016-08-19 23:13:54 +1000 |
---|---|---|
committer | James Ross-Gowan <rossymiles@gmail.com> | 2016-08-20 00:07:32 +1000 |
commit | 68dc869d6aa8eb7004e2f86e9e4dcbf203ae6a8c (patch) | |
tree | 9598d7cdf47c3f7ba30d4c1b32106775018c733a /player | |
parent | e5f61c2bd5d15821e9d6f0967884156e210e74f4 (diff) | |
download | mpv-68dc869d6aa8eb7004e2f86e9e4dcbf203ae6a8c.tar.bz2 mpv-68dc869d6aa8eb7004e2f86e9e4dcbf203ae6a8c.tar.xz |
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.
Diffstat (limited to 'player')
-rw-r--r-- | player/command.c | 28 |
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) |