[vlc-devel] [PATCH 02/14] mkv: make sure indexes are in order

[Filip Roséen]

> In any case you should apply that to IndexAppendCluster too since it also adds indexes
> while the file is being read. It was my poor attempt at somehow improving the seek
> without cues for a backward case.

The patch indirectly handles the case where IndexAppendCluster adds indexes (by
sorting after all IndexAppendCluster calls have been made). The function is only
invoked in one place, and as such sorting happens afterwards.

See `matroska_segment.cpp:791`:

     759     if( i_global_position >= 0 )
     760     {
     ...
     774         while( ( el = ep->Get() ) != NULL )
     775         {
     776             if( MKV_CHECKED_PTR_DECL ( kc_ptr, KaxCluster, el ) )
     777             {
     778                 cluster = kc_ptr;
     779                 i_cluster_pos = cluster->GetElementPosition();
     780                 if( index_idx() == 0 ||
     781                     ( prev_index().i_position < (int64_t)cluster->GetElementPosition() ) )
     782                 {
     783                     ParseCluster( cluster, false, SCOPE_NO_DATA );
     784                     IndexAppendCluster( cluster );
     785                 }
     786                 if( es.I_O().getFilePointer() >= static_cast<unsigned>( i_global_position ) )
     787                     break;
     788             }
     789         }
     790 
     791         std::sort( indexes_begin(), indexes_end() );
     792     }

> We'll discuss that more extensively when I come at videolabs. But if you want to start
> fixing the Seek and Cthulhu knows it *does* need fixes... indexes shouldn't be a vector
> but a key ordered map with timecode as the key so we can start adding indexes of key
> frames and maybe each track that would need some kind of preroll could have its own
> map... so we could even reinject correctly the seekpoint subtitles when seeking.

Having the indexes sorted allows us to do insertion into the right spot with
std::lower_bound and a regular insert, which means that we do not need to change
any code to make such a thing possible.

Though it could be worth exploring some other underlying storage method if we
are adding so many indexes that the O(N) insertion will be a major bottle neck
(but I am not sure how many cues we are talking about).

Changing the container is as easy as changing the typedef, and then replace the
usage of `push_back` with a call to insert (for the appropriate type).

I am really looking forward to your visit! 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.videolan.org/pipermail/vlc-devel/attachments/20160309/91637a6f/attachment.html>