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

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


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?
This task depends upon

Comment by sideral (sideral) - Monday, 18 July 2011, 20:06 GMT
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, 10:13 GMT
The accidental commit showed about 100 bytes binsize increase.
Comment by Fred Bauer (freddyb) - Tuesday, 18 October 2011, 04:05 GMT
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...