From: Lion Templin <ltemplin_at_leonine.com>
Date: Mon, 3 Jun 2002 03:55:14 -0500 (CDT)

Playlist Handler Alg
for Rockbox
Lion Templin
20029603

Overview

Managing a playlist, moreso large playlists, presents a problem when you are
limited by memory consumption (cannot load full playlist in memory) and you
do not want to access the disk often to conserve power consumption (cannot
load piecemeal). Playlists are important such that they also can be
shuffled quickly and deterministically. In order to accomplish both memory
and disk efficiency, data is handled in blocks designed to both prevent
fragmentation of scarce memory and batch requests from disk.

Notes

The operation of this algorthm depends on the functionality of lseek(), a
random access method for accessing on-disk files.

Since write() and derivatives are not supported, resuming from power cycles
is not available, though may be supported at a later time by writing a
single data structure to disk.

FIRST HALF - STORING THE PLAYLIST

It is unreasonable to store the contents of the playlist in memory as a
structure containing the list's filenames. This makes the amount of memory
unpredictable and possibly consuming. Therefore, a simple and
space-deterministic method should be used. In this case, we simply store
byte-offsets into the playlist where each entry begins. Optionally, we can
also store the length of each entry for easier reading by lseek(), without
requiring a second parse & imposing a file length limit. Obviously, we will
build this index of integers by scanning the playlist at initial load time.

To store these integers, a useful ADT must be considered. Arrays are not
useful becuase we want to build our list at load time, and we will not know
the total length. Predefined arrays limit the number of entries in our
lists. We cal realloc(), but that will cause fragmentation and loss of
available memory. Linked lists (and tree decendants) are bad becuase they
too will cause massive fragmentation, esp if another thread is doing
malloc()'s during the build. In order to consume memory in a controllable
way, we'll malloc() blocks (optimum size, 4064?) as arrays of integers, but
as a block fills, we'll link off the end of the block to another block.
Blocks will all be n-sized, so it will be simple to compute when you'll need
to jump a link and reference the next block. Doubly-circular linked blocks
will all infinate play of the list as well as the ability to jump backwards
across block boundries.

In order to shuffle our new found list, we can do an acceptable shuffle in
two (plus one) steps. First, exchange links on blocks, changing the order
in which blocks are linked. And then second, inter-block exhanges of
individual elements. Exchange one element for another out of another block.
Finally, our plus one step will be to do single exchanges on the (possible)
odd block that's remaining by exchanging with another processed block.

Mind you, all of this is really straightforward pointer arithmetic. After
moving the main block around, two pointers can traverse opposite sides of
the ring and exchanges can be done within those two blocks. Move the
pointers to the next blocks, and rinse and repeat.

Realistically this can be done in slightly over O(n/2), which is useful
for a small device with limited power.

SECOND HALF - TRAVERSING THE LIST

Ok, well, at this point we've got a good method for storing data ABOUT the
list, let's manage the list itself. We'll eventually need to get the
filenames out of the original playlist. We'd like to batch these requests
so that we don't have to spin the disk too much, since we have to read from
it to get the actual names. Once again, we'll use a block structure. We'll
keep some n filenames in memory, and traverse the linear structure until we
reach a boundry where we unload some y elements and replace them from the
lseek() reads for the names, based upon the records in the linked blocks.
For example:

We store 20 song filenames in memory at one time. We load 15 at the top of
the list starting at position 5. Then we walk backwards and load the 5 at
the end of the list at positions 0-4. As each song is played/skipped, we
move our pointer forwards. When we reach, say, position 15, we move our
data backwards so that the current pointer is at 5, loading a new block of
10 songs. Since it is my own personal experiance that I spend far more time
skipping forward, we use a larger number of elements forward of the default
starting position. If this is not the case, then simply change the default
starting position up the list. The smae is true for going backwards, we set
a limit, say position 1, where we load and reset the default position. IN
FACT, if enough effort was given to it, you could track how many times you
had to reset the pointer in each direction and adjust the default pointer
based on which direction the user moves the most.

SAVING THE LIST

In order to restore from a power cycle, first save the playlist name, the
element in the block you are on, and then a dump of all the block contents
starting with the current block. Grab the file pointer to the playlist
itself, reload the blocks, and reload the play blocks based on the saved
starting element. Since the blocks will be saved from the current block, we
know then that the nth element of the first block is the one to be played
first.


PROBLEMS

List size is still limited by memory, though 4 bytes per song (min, plus a
little overhead per block) is still a lot before we use significant amounts
of mem.

Some cases need to be in place for really small lists (ie, 1-block).

Shuffling will not be true-random. Should be good enough for average users.

No support for distance shuffling.



= lion is Lion J Templin (KB9ENE) lion_at_leonine.com =
= || // ||> UNIX Systems Consulting for the =
= ||=EONINE \OMPUTATIONAL ||\ESOURCES Northland FROM the Northland =
= UNIX Systems Consultants http://www.leonine.com =
Received on 2002-06-03