Rockbox

This is the bug/patch tracker for Rockbox. Click here for more information.

Quick links: Bugs · Patches · Rockbox frontpage

Tasklist

FS#12192 - Introduce bsearch() and use it in tagtree.c.

Attached to Project: Rockbox
Opened by Thomas Martitz (kugel.) - Monday, 18 July 2011, 19:33 GMT+2
Task Type Patches
Category Operating System/Drivers
Status New
Assigned To No-one
Player Type All players
Severity Low
Priority Normal
Reported Version Release 3.8.1
Due in Version Undecided
Due Date Undecided
Percent Complete 0%
Private No

Details

bsearch() is a general purpose binary search function for arrays.
It's supposedly faster than looping over arrays.
The array needs to be sorted in ascending order under the provided
comparison function. If the key and array element are of the same kind,
then the same compare function can be used for qsort() and bsearch().

Code taken from glibc.

---

So, is anyone interested?
   0001-Introduce-bsearch-and-use-it-in-tagtree.c.pa... (10 KiB) 
 b/apps/tagtree.c             |  134 ++++++++++++++++++++++---------------------
 b/firmware/SOURCES           |    1 
 b/firmware/common/bsearch.c  |   49 +++++++++++++++
 b/firmware/include/bsearch.h |   28 ++++++++
 4 files changed, 147 insertions(+), 65 deletions(-)

This task depends upon

Comment by sideral (sideral) - Monday, 18 July 2011, 22:06 GMT+2
This looks like a good idea, but likely has negligible effect on runtime and battery life for the use case you've provided (tagnavi.config parsing). If you think otherwise, it would be good if you could provide some measurements.

What does the binsize diff look like?

This should not be committed before the current DB / dircache problems are sorted out to reduce the number of moving parts while debugging. This includes FS#12175 and occasional crashes when browsing the DB (FS# forthcoming).
Comment by Thomas Martitz (kugel.) - Tuesday, 19 July 2011, 12:13 GMT+2
The accidental commit showed about 100 bytes binsize increase.
Comment by Fred Bauer (freddyb) - Tuesday, 18 October 2011, 06:05 GMT+2
A binary search with O(log n) performance is definitely better than a linear search with O(n) performance, especially for long lists. There is also a binary search in font_cache.c that could call bsearch() instead, mitigating the size difference. I wonder how many other linear searches there are in the code...

Loading...