Menu
Logged-In As
ACCOUNTNot Logged In
Implement a platform independent re-entrant sort functionBRL-CAD
Status: ClosedTime to complete:
72 hrs
Mentors: Daniel Rossberg
The classic C library qsort() does not support a context parameter. A work around is to store the context information in a static variable. However, this solution is not thread save and may result in unpredictable behavior.
There are platform specific sort functions qsort_r() in incompatible versions for BSD and GNU and qsort_s() for MSVC. Your task is to implement a bu_sort() function for BRL-CAD which is platform independent.
Code:
- src/libbu/sort.c
The new sort function could look like this:
void bu_sort(genptr_t array, size_t nummemb, size_t sizememb,
int (*compare)(const_genptr_t, const_genptr_t, genptr_t),
genptr_t context);
Uploaded Work
| File name/URL | File size | Date submitted | |
|---|---|---|---|
| bu_sort.patch | 2.4 KB | December 14 2013 17:06 UTC | |
| bu_sort.patch | 5.7 KB | December 16 2013 21:50 UTC | |
| bu_sort.patch | 7.3 KB | December 17 2013 20:09 UTC | |
| bu_sort.patch | 7.3 KB | December 18 2013 15:25 UTC |
I would like to work on this task.
This task has been assigned to Johannes Schulte. You have 72 hours to complete this task, good luck!
I didn't push the patch to the tree, because I couldn't test it on Win and Mac. Nevertheless, if the code looks reasonable to you, or you can test it, I can do the commit afterwards.
BTW, did you create this task on purpose a second time? (https://google-melange.appspot.com/gci/task/view/google/gci2013/4993291800018944)
The work on this task is ready to be reviewed.
Just saw, that I missed one genptr_t use, so, though it shouldn't influence the function, this is the fixed version: http://pastebin.com/aQ6sjHaL
Melange has detected that the deadline has passed and no more work can be submitted. The submitted work should be reviewed.
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
There are several issues I see with this implementation.
First and foremost is that you use preprocessor platform identifiers and version numbers to determine whether you can call qsort_r() and qsort_s(). See our HACKING file for details, but that is not a desireable approach. Use of those function sshould be tied to feature identifiers that are tested for by cmake (e.g., you can test in the top-level CMakeLists.txt file whether qsort_s is available, it'll define HAVE_QSORT_S). Testing for qsort_r is a little tricky, but doable to figure out which of either is available.
That brings me to the second point, you have no failover implementation (which you may want to just start with first instead of figuring out the CMake testing you'd need). To be truely portable, there needs to be an #else case that still does the sorting, otherwise we have an empty function that will do nothing and result in bad behavior.
The last point is stylistic. The indentations are off. Notably, you have two-char indent on the struct and the sort callback function, and tabs or something else going on in bu_sort(). You also have spaces before the '#' preprocessor directives, which is not portable. See HACKING for details and an example of our expected format (this is critical if you're to commit it yourself as we take pride in consistency), or browse some of the other files.
so, did I understand right, that reimplementing qsort is the way to go? Is then the cmake testing and usage of qsort_r and qsort_s still necessary, or can I use this implementation for every platform ?
Only an idea, but the license of the BSD implementation should allow to use the code in BRL-CAD's LGPL libbu library.
The deadline of the task has been extended with 2 days and 0 hours.
I tried to create the task on different ways. One was directly in google-melange and another via a Google docs form provided by Sean. Now both are visible.
The work on this task is ready to be reviewed.
As Daniel proposed, I used BSD's implementation. Is any source naming necessary for this in the source file?
BTW, what is status quo concernig genptr_t. On the maillist I read, that it's deprecated, but in task specification it's required. For now I used void *, is this right or should I go back to genptr_t?
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
The deadline of the task has been extended with 1 days and 0 hours.
Johannes, this is looking really good but there is one major problem with the patch. You used code from BSD as-is, but you do not credit them anywhere. This is technically illegal and morally crummy to do too.. I'm sure that wasn't your intention, and fortunately easy to fix. You should always "cite your sources" whether you are writing prose or writing code, even if the license doesn't require it.
The fix: You can put their entire legal comment block that was at the top of their file right there in the file before their sources (after our legal comment header block). You should put a comment in there too to say what sources this code was copied/derived from [wherever you got them from, specifically]. See src/libbu/fnmatch.c for an example.
That said, there are also numerous issues with the copy-pasting that must be addressed. Their code does not comply with our code conventions. So while you can use them and that gives you an advantage, you must update them to our conventions. A few I see right away:
The usage of sizeof(long) is also highly suspect, may not be portable, but I don't see any blatant problems at the moment. You might want to try a few of the other BSD's (there are at least 3 or 4 implementations to consider) to see if any others avoid performing runtime type sizing.
Using void* is Ok.
The work on this task is ready to be reviewed.
Thanks for your explanation, thats what my "source naming"-question was all about.
Oops, shame on me. That's what happens, if you forget to build a last time before commiting. This version should work : http://pastebin.com/aDzUXhwZ
One of the mentors has sent this task back for more work. Talk to the mentor(s) assigned to this task to satisfy the requirements needed to complete this task, submit your work again and mark the task as complete once you re-submit your work.
Go ahead and upload the patch update here so we can track it with the task, but a quick review and it looked good to me.
The deadline of the task has been extended with 1 days and 0 hours.
The work on this task is ready to be reviewed.
Congratulations, this task has been completed successfully.
Johannes, this looks perfect now, Please commit it yourself (great first commit!).
A unit test for this would be a great follow-on task. Using this function where we sort things would be another.
Both tasks, especially the replacement of old qsort uses, sound interesting. It would be great, if you create them.
Numerous follow-on tasks related to this have been created including unit test and conversion of qsort to bu_sort.