Rockbox mail archive
Subject: RE: Search Plugin
From: TP Diffenbach (rockbox_at_diffenbach.org)
> some ideas:
> -- database, database, database.
Why do you think I asked about usage patterns in my poll? ;)
> make a utility that creates
> a database of your player on the computer that you can then just drop
> into /.rockbox/rocks/db/
I was trying to determine how often a user would have to update their
database. If the set of songs was mostly stable, we could go with simpler
data structures, where the cost of update would be very high (array-style
and arrays of offsets where one update could potentially force
re-calculating an entire database "table"), but the cost of search and
retrieval would be low and could be done in bulk.
A key advantage of bulk retrievals is that it minimizes costly (in terms of
power consumption) disk usage. On the other hand, directory operations run
the disk too, and as with the directory cache, we can cache (portions of)
the database too.
Another problem is working memory: unless we want to use the mpeg buffer,
we'll need to limit the database to about 20KB of working memory; the code
can /probably/ be loaded in the 32KB reserved for plugins, but the plugin
API would have to be extended to allow the manipulation of playlists, and
the database would probably need additional working memory.
Regardless of the amount of working memory, it is possible to encounter
situations where the user specifies an "OR" query ("Bob Dylan OR Vladimir
Horowitz OR Aaron Copland", the results of which (most likely for tracks but
possible for other data sets) exceed available working memory. Because what
I'm looking at would process each operand of the OR separately,
concatenating and removing duplicates from the result, we would end up
either presenting the results set unsorted (or with each chunk that fills
memory sorted, but the entire set unsorted), or doing on-disk sorting. I
don't like on-disk sorting, because it would mean a lot of disk spinning and
thus battery cost; it would also take non-negliable time, outweighing its
usefulness in most cases. Of course, the greater the working memory, the
less often we run into this problem.
In general, of course, more memory means less disk accesses and faster
operations. To that end, I'll use (static) Garsia-Wachs coding to compress
the string data; since Garsia-Wachs encoding preserves lexigraphic ordering,
we'll be able to do sorting on (and the database will be able to store) the
/encoded/ strings (and we'll gain a small speed/battery boost by reading and
writing encoded strings to disk) and save working memory; we'll only decode
the strings on display.
From: owner-rockbox_at_cool.haxx.se [mailto:owner-rockbox_at_cool.haxx.se]On
Behalf Of Eric Linenberg
Sent: Wednesday, December 17, 2003 10:32 AM
To: Rune Wiinberg
Subject: Search Plugin
I really like this plugin although it takes about 2 minutes to search my 60
-- database, database, database. make a utility that creates
a database of your player on the computer that you can then just drop
into /.rockbox/rocks/db/ (it could scan ID3 tags and filenams)
-- an option to rename the search results, or just use the default
-- maybe list the songs as they are found? (more verbose deiplay)
this is a keeper for me!
RW> Hi all.
RW> I've made a plugin for simple recursive filesearching.
RW> If interrested you can grab it at:
RW> The zip containes a compiled version for the Recorder + sourcecode.
RW> The searches are case-insensitive and the results are placed in
RW> called /SEARCH-xxx.m3u (where xxx is the respective search word).
RW> Performance could be greately improved by eg. using a DB.
RW> But a slow algorimth is better than nothing. :-)
RW> Feedback are welcome
RW> / Rune
Page was last modified "Jan 10 2012" The Rockbox Crew