Skip to content

sys/binsearch: Add binary search module.#8974

Closed
jcarrano wants to merge 3 commits intoRIOT-OS:masterfrom
jcarrano:binsearch
Closed

sys/binsearch: Add binary search module.#8974
jcarrano wants to merge 3 commits intoRIOT-OS:masterfrom
jcarrano:binsearch

Conversation

@jcarrano
Copy link
Copy Markdown
Contributor

Description

There are places (for example, the shell and the Lua interpreter I'm working on) where one has to search an array of structs (a table), which is generally ordered.

This code allows to do this in a generic way. Also, it uses binary search so it should be faster than iteration for bigger arrays.

There are two functions and two macros. The macros are a convenience to avoid having to use sizeof and offsetof all the time.

@jcarrano jcarrano changed the title Add binary search module. sys/binsearch: Add binary search module. Apr 18, 2018
@jnohlgard
Copy link
Copy Markdown
Member

Is there any benefit to using this over stdlib.h bsearch()?

@jnohlgard
Copy link
Copy Markdown
Member

A more flexible approach is to use a comparison function pointer argument, which allows adapting it to comparing all kinds of data, not only strings.

@jcarrano
Copy link
Copy Markdown
Contributor Author

jcarrano commented Apr 18, 2018

@gebart : It could be implemented in terms of bsearch, but in the end you'll end up with even more code. The idea of adding a comparison callback is quite easy to implement, but I don't know how useful it will be.
My idea when doing this was to make array searching take one line for the most common case.

@jnohlgard
Copy link
Copy Markdown
Member

In my opinion, a custom comparison I'd extremely useful. Even just reversing the sort order can be trivially implemented with a custom comparison function (cmp(a, b) { return a > b;} vs. cmp(a, b) { return a < b;})

I don't like adding code which does the same thing as some standard library part unless there is any special circumstance that makes the standard library version unsuitable (e.g. the fmt library which uses a lot less memory than the libc printf family of functions).
The standard library components are usually pretty well tested, and we don't have to maintain the implementations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants