diff options
author | wm4 <wm4@nowhere> | 2019-06-02 23:29:40 +0200 |
---|---|---|
committer | wm4 <wm4@nowhere> | 2019-09-19 20:37:05 +0200 |
commit | 911718c413a80ee5e3bc30a9510b6aaaba35d2ad (patch) | |
tree | 1cb1b5675bd768d7046f970de7ce8d05e7bf75a3 /demux/demux.c | |
parent | 1f13bd09427b2784a59168e6807b7c134c79addb (diff) | |
download | mpv-911718c413a80ee5e3bc30a9510b6aaaba35d2ad.tar.bz2 mpv-911718c413a80ee5e3bc30a9510b6aaaba35d2ad.tar.xz |
demux: use binary search for cache seek index
Not sure if this is bug-free. You _always_ make bugs when writing a
binary search from scratch (and such is the curse of C, though if I did
this in C++ it would probably end in blood). It seems to work though,
checking against the normal linear search.
It's slightly faster. Not much.
I wonder if the termination condition can be written in a nicer/elegant
way. I guess the fact that it's not a == predicate makes this slightly
messier?
Diffstat (limited to 'demux/demux.c')
-rw-r--r-- | demux/demux.c | 35 |
1 files changed, 28 insertions, 7 deletions
diff --git a/demux/demux.c b/demux/demux.c index 3032e69784..3f65b2f158 100644 --- a/demux/demux.c +++ b/demux/demux.c @@ -3098,18 +3098,39 @@ static void switch_current_range(struct demux_internal *in, free_empty_cached_ranges(in); } +// Search for the entry with the highest index with entry.pts <= pts true. +static struct demux_packet *search_index(struct demux_queue *queue, double pts) +{ + size_t a = 0; + size_t b = queue->num_index; + + while (a < b) { + size_t m = a + (b - a) / 2; + struct index_entry *e = &QUEUE_INDEX_ENTRY(queue, m); + + bool m_ok = e->pts <= pts; + + if (a + 1 == b) + return m_ok ? e->pkt : NULL; + + if (m_ok) { + a = m; + } else { + b = m; + } + } + + return NULL; +} + static struct demux_packet *find_seek_target(struct demux_queue *queue, double pts, int flags) { pts -= queue->ds->sh->seek_preroll; - struct demux_packet *start = queue->head; - for (size_t n = 0; n < queue->num_index; n++) { - struct index_entry *e = &QUEUE_INDEX_ENTRY(queue, n); - if (e->pts > pts) - break; - start = e->pkt; - } + struct demux_packet *start = search_index(queue, pts); + if (!start) + start = queue->head; struct demux_packet *target = NULL; for (struct demux_packet *dp = start; dp; dp = dp->next) { |