summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorwm4 <wm4@nowhere>2019-06-02 23:29:40 +0200
committerwm4 <wm4@nowhere>2019-09-19 20:37:05 +0200
commit911718c413a80ee5e3bc30a9510b6aaaba35d2ad (patch)
tree1cb1b5675bd768d7046f970de7ce8d05e7bf75a3
parent1f13bd09427b2784a59168e6807b7c134c79addb (diff)
downloadmpv-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?
-rw-r--r--demux/demux.c35
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) {