• Status New
  • Percent Complete
  • Task Type Patches
  • Category Operating System/Drivers
  • Assigned To No-one
  • Operating System All players
  • Severity Low
  • Priority Very Low
  • Reported Version Release 3.8.1
  • Due in Version Undecided
  • Due Date Undecided
  • Votes
  • Private
Attached to Project: Rockbox
Opened by kugel. - 2011-07-18

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

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 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).

The accidental commit showed about 100 bytes binsize increase.

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…


Available keyboard shortcuts


Task Details

Task Editing