This is just a proposed design at the moment. Comments are more than welcome.

Barry McIntosh
4 August 2003
To comment, ask me a question, or add new information, please contact me.

A Quick Introduction (for anyone not familiar with playlist operation)

Here's how playlists currently work in ROCKbox:

When in memory, each playlist entry is effectively a pointer into a playlist file. So when a playlist file is "played", the file is scanned to find all the music file entries. For each entry the offset in the file is stored in an array in memory. As the playlist plays, each time a new music file is needed, we pick up the playlist offset pointer, seek that offset into the playlist file, read one line, which is expected to be the name of the music file, and we can open the music file. Since we must read the music file, first reading a line from the playlist file is only a small overhead. Thus the playlist mechanism needs to keep just the path to the playlist file itself, and one offset pointer for each music file namein the playlist file. Shuffling the playlist consists of shuffling just an array of fixed-size playlist entries, so can be simple and fast.

Each playlist pointer entry is a 32 bit integer. It is preferable to avoid increasing this size, as any memory used for playlists is unavailable for MPEG buffer.

The original operation used all 32 bits of each playlist entry as an offset into a playlist file. This would allow the playlist file to be 4GBytes in length - far longer than is likely in reality.

To support dynamic playlist operation, the top three bits have been "stolen" from the playlist pointer to serve as indicators of the type of each entry. This leaves 29 bits as the pointer, leaving the maximum playlist size at a more than adequate 512MBytes (that's over 50KBytes for each entry in a 10,000 song playlist). Dynamic playlists are a good thing, so let's leave those top three bits alone!

As it stands, the playlist mechanism can only cope with a playlist containing music file entries (.MP3, .MP2, .MPA). If the file is some other type, it will not be loaded. In order to support nested playlists, if an entry in a playlist is a .M3U file, we want to effectively include the content of that playlist within the first playlist.

Nested Playlists

To nest playlists we need to be able to keep access to every music file line in any number of playlist files, starting from the "root" playlist. Here's the (proposed) mechanism....

The 29 available bits in a playlist entry are divided into two fields. The lower 'S' bits (Seek Index) are the offset into a playlist file which normally points to a music file (just as the 32 bits in the original playlist mechanism or the 29 bits in the dynamic playlist mechanism). The upper 'P' bits (Playlist Index) are an index which identifies the particular playlist file that seek is applicable to.

Also we split off a few of the playlist entries (at the top of the playlist array) to serve as playlist indices. These are similarly split into a seek index part and a playlist index part. We need one of these for each playlist file which is used in the "tree" of nested playlists. So here's an example of how a playlist entry may be split - although read on before getting excited about the maximum size of a playlist file etc. :

| ||      ||                      |
| ||      ||                      |
| ||      ||         ^            |
| ||  ^   ||         |            |
|^||  |   ||         +---------------- Seek Index
||||  +------------------------------- Playlist Index
|+------------------------------------ Dynamic playlist flags

And here's how array entries in the playlist are allocated:

 0                                                                        9999
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

M = Music Entry
U = Unused Entry
P = Playlist Entry

For each entry, the seek index is an index into a playlist file, and the playlist index is an index identifying one of the playlist entries. So a Playlist Index of 1 refers to the 9999th entry in the real array, 2 refers to the 9998th entry etc.

A playlist index of zero means the root playlist (the one which was "played"), rather than a playlist entry.

Loading the Playlist Into Memory

When playlist is "played" it is opened and scanned. For each music file in the playlist file a music file entry is created containing the appropriate seek index and a playlist index part of zero to indicate the root playlist.

When a nested playlist entry is found, we make a new Playlist entry containing a playlist index of zero (root playlist) and a seek index pointing to the .m3U line in the root playlist file containing the name of the nested playlist. We then open the nested playlist file and scan it creating both music and playlist entries. These new entries are given a Playlist Index which identifies the Playlist Entry we just created (that is, the playlist entry that can be used to find the name of the playlist we are scanning).

Thus we recursively scan the tree of nested playlists, creating a music entry for each music file, and a playlist entry for each of the playlist which contain those music file entries. Each music entry points to a playlist entry (or to the root playlist). The playlist enties are effectively connected to form a tree leading back to the "root" playlist.

Shuffling the Playlist

To shuffle, simply shuffle the Music entries.

Playing the Playlist From Memory

To play, we step through the music entries. To "play" a music entry we need two pieces of information to find the name of the .MP3 file to open: the offset into a playlist file, and the name of the playlist file.

The Music Entry contains the offset into the playlist file in its Seek Index.

To find the name of the playlist file we look at the Playlist Index. If this is zero, we use the "root" playlist. Otherwise, we get the appropriate Playlist Entry, and look at its Playlist Index, repeating until we reach the root playlist. This builds up a list of playlist entries. We now follow them in the reverse order (that is, starting with the root playlist file) reading the name of each playlist file and opening it at the seek index until we get to the required music file.

Dynamically Setting Field Sizes

The trouble with allocating a certain number of bits to each field in a playlist entry is that it is inevitably a compromise between the number of playlists that can be nested, and the size of any one playlist.

We have 29 bits in total available.

If we were to allocate 7 bits (say) to the Playlist Index and 22 bits to the Seek Index, we would be limited to 128 playlists in the tree, and no playlist could be bigger than 4MBytes. Sounds OK, but I bet there is someone out there who wants to make a playlist nesting 129 playlists.

If we were to allocate 10 bits to the Playlist Index and 19 bits to the seek index we could have 1024 playlists in the tree, but even a single flat playlist would be limited to 512KBytes. Again, maybe OK, but I bet there is someone with a single flat playlist bigger than that 512KBytes.

So, the sizes of the fields are allocated dynamically during the load of the playlist into memory.

Initially, no bits are allocated to Seek Index, and no bits are allocated to Playlist Index. As we scan playlists, we increase the number of bits allocated to the seek index to accommodate the highest seek index required. As nested playlists are encountered, Playlist Entries are required so we allocate bits to Playlist Index. We allocate bits from the right for the Seek Index, and from bit 28 working left for the Playlist Index. So at the end of loading the nested playlists, our bit allocation might look like:

| ||      ||      ||              |
| ||      ||      ||              |
| ||      ||      ||      ^       |
| ||  ^   ||   ^  ||      |       |
|^||  |   ||   |  ||      +----------- Seek Index
||||  |   ||   +---------------------- Unused bits
||||  +------------------------------- Playlist Index
|+------------------------------------ Dynamic playlist flags

We can keep allocating bits to either index until doing so would cause the fields to overlap. This allows us to have either a small number of very large playlists or a very large number of small playlists. The same bit allocation applies to all entries in the in-memory playlist at any time, but can change whenever a fresh root playlist is loaded, or if additional tracks are added to the in-memory playlist.

So, including the root playlist, we can have:

   1 playlist upto 512MB
   2 playlists each upto 256MB
   4 playlists each upto 128MB
   8 playlists each upto 64MB
  16 playlists each upto 32MB
  32 playlists each upto 16MB
  64 playlists each upto 8MB
 128 playlists each upto 4MB
 256 playlists each upto 2MB
 512 playlists each upto 1MB
1024 playlists each upto 512KB
2048 playlists each upto 256KB
4096 playlists each upto 128KB

To achieve this reallocation of bits, whenever our scan creates the 2nd, 4th, 8th etc. Playlist Entry we go back through all the previously allocated Music and Playlist Entries, shifting their Playlist Index fields one bit to the right. (If this has a big impact on playlist load time we could try a scheme that does all the adjustments at the end of the load, or pre-allocate bits and only reallocate if we run out of space in one field.)

Implications of this Design

  1. If allocating another bit to either the Playlist Index or the Seek Index would cause the fields to overlap, we have run out of address space in the playlist entries. This is unlikely, but we show the user a warning, and can continue to create both Playlist Entries and Music Entries that can fit within the required bit allocation. If we cannot allocate a playlist entry on this basis, then we must skip that whole playlist file and anything nested within it.

  2. The playlist size limit (default 10000) is now the number of music files plus the number of nested playlists. We run out of space in the in-memory playlist when the music file entries and the playlist entries meet.

  3. We need to protect playlist load from circularity (i.e. playlist has itself nested inside). This is easily achieved by setting a limit on the depth of nesting and aborting if it is exceeded. Similarly, when loading an MP3, the code which steps up through the playlist tree should include some protection on the depth of recursion, to reduce the chance that a bug in loading the playlist will cause a crash when reading it.

  4. Finding the name of an MP3 file to open from the nested playlist involves opening and seeking through each playlist in the tree of playlists, starting from the root playlist which was originally played. So to identify an MP3 file in the root playlist (depth 0) we have to open and seek in one file, as at present. For an MP3 file from a playlist at depth 1 we have to open and seek in two files,. For depth 2 it is three files etc. For shallow nesting this will probably be fine, but I don't know how deep the nesting will be before it has too big an impact on track loading time - some experiments are probably in order here, before going too far.

  5. As each nested playlist is opened, we will have to take into account that each playlist entry may be relative to the location of the containing playlist, or may be absolute. This shouldn't be too hard, but probably won't be completely trivial either.