Has anyone successfully compiled and used liblcthw?

C
#1

I downloaded liblcthw and tried to compile. Mostly I can compile, but for the calls to heapsort and mergesort in darray_algos.c and darray_algos.h. Search on google revealed these 2 are not part of the C-standard library. The question I am referring to is : https://stackoverflow.com/questions/23851098/c-compile-errors-learn-c-the-hard-way-ex-32.

The accepted answer has the following text:

The Exercise 32 code downloaded from the github repo is platform specific for a BSD system (and perhaps OS X). Specifically, there are a couple required symbols for a successful build that are present on a BSD sysem, but which are most likely not present on a (Linux) Ubuntu 12.04 system. These include:

mergesort
heapsort

Nevertheless, the library and unit tests can all be successfully compiled, with the exception of one unit test that (eventually) will require the above symbols. Moving the single problematic test from the tests directory will allow the other tests to compile on a (Linux) SuSE SLES 11 system, if a slight change is made to a flaw in the makefile shown below.

And it goes on to explain how to compile correctly.

I also searched the source file of the standard C library that my system implements (Fedora) and found only qsort there, not heapsort or mergesort.

Ofcourse removing the heapsort and mergesort is an option, but the heapsort and mergesort seem like reasonable choices, especially due to the attractive characteristics of heapsort and mergesort. So I set out to implement heapsort and see what roadbumps I came accross. I came across a few, especially the fact that we do not know what type we are sorting so I need a way to express an unknown type using its size into things like char *. Most example program just assume and integer array, which simplifies everything (including comparison). The point is to also be able to sort any kind of object even a struct using a comparison function.

In order to get an idea how to do it I checked out the implementation of qsort in the Fedora implementation (probably related to or part of the gcc project). I found that it is complex and while I am writing this, I am trying to understand the code so I can tranlate this to an implementation of heapsort. Still working on this.

In the meantime my question is: “Has anyone successfully implemented liblcthw and how did your do it?”.

Did you exclude heapsort and mergesort? Or did you find an implementation?

#2

It might be that this version of Linux doesn’t have those two, so I’ll have to try it on Debian or another OS to make sure. Let me look at it.

#3

Thanks Zed. In the meantime I created the header for heapsort and mergesort and ran into additional issues with this library;

  1. qsort_r is only availalbe if you define _GNU_SOURCE. The manpage for qsort (which includes qsort_r) remarks this.

  2. The arguments for qsort_r might be confused. It has the array struct as the 4th argument and the compare function as the 5th argument:

    qsort_r(sarry->indices, length, sizeof(int), sarry, SuffixArray_compare);

So the compiler errors on the call parameter sarray. I suspect the call should be

qsort_r(sarry->indices, length, sizeof(int), SuffixArray_compare, sarray);

But when I change the code this way, the compiler complains that the args of the compare function which are (void *, const void *, const void *) should be (const void *, const void *, void *). Also the manpage has a remark that I do no understand at all and I quote:

A pointer is passed to the comparison function via arg. In this way, the
comparison function does not need to use global variables to pass through arbitrary arguments,
and is therefore reentrant and safe to use in threads.

I have progressed to exercise 31, so this could be in one of the next lessons, but at the moment I do not understand this, so I will let this go and see if with the current knowledge I can finish the exercises starting from 32.

1 Like
#4

I got the library to compile and had to do the following to get it done:

  1. Add compile switch _GNU_SOURCE for qsort_r

  2. Add compile switch _XOPEN_SOURCE=700 for round. The function round actually
    only needs POSIX 2001, so defining _XOPEN_SOURCE=700 might be overkill (it implies POSIX2008.

  3. Changed the call to qsort_r to

     qsort_r(sarry->indices, length, sizeof(int), SuffixArray_compare, sarry);

  4. Changed the definition of SuffixArray_compare to

     int SuffixArray_compare(const void *a, const void *b, void *thunk)

(The argument thunk was in the original code specified as first argument).

  1. In the function gen_keys made all checks appear after defining urand, key and stream, because these are referenced when it gets to the error-label. In the original code at the first check (if an error occurs) the data items for stream and key are not defined.

  2. Defined header declaration and empty definition of heapsort and mergesort. I am working on a heapsort, but need to test it first. The header declarations are:

     int heapsort(void *array, size_t nmem, size_t size, compare_t compare);
 int mergesort(void *array, size_t nmem, size_t size, compare_t compare);

where the compare function type compare_t is defined as

    typedef int (*compare_t)(const void *a, const void *b);
  1. I also got some set-but-not-used warnings which I could prevent with an extra statement: (void)(item); if item was set but not used.

After doing these changes, the library compiles and the testoutput seems ok.

EDIT1: My fork of liblcthw does not show these changes yet, because I want at least heapsort to work. As soon as I get that finished I will commit and push.

EDIT2: The above changes are the most essential changes. Due to using a autoformatting plugin for vi, some of the changes that I will commit are non-essential.

EDIT3: Tests are ok according to the file tests/tests.log. All tests pass. However, the terminal does show an inordinate amount of DEBUG messages concerning mainly bstring tests. I have no idea whether that is ok or not ok. At the moment I am focussing on the library itself and getting heapsort and mergesort working.

#5

Nice, alright shoot me a pull request and I can work on the debug things. I think those are actually normal but I’ll have to compare with my version and your version if you have a regression.

#6

Hey Zed,

Did you have a look at the pull request yet? Not meaning to put pressure on, your regular day job probably does that just fine, just wondering whether you saw it appear.

#7

Hey Zed,

I bumped into another problem. The file list_algos.c starts out with a definition of an inline function.

If the compiler heeds the hint to make it inline, then calling it from a different file will not work. As it happens, when doing a make all, gcc apparantly ignores the inline and makes a function, so its in the library and any call will work.

When doing a make dev, gcc choses to heed the suggestion and make the function inline. However,this means that the file in test (tests/list_algos_tests.c) has no definition of the function. The call generates an underfined reference.

Once I saw the only difference was the inline part, I knew something was different and found a description of inline functions w.r.t. c99 and gcc: http://www.greenend.org.uk/rjk/tech/inline.html.

After reading this description I decided to include the inline definition in the header file (list_algos.h) as that is the interface to calling modules (like list_algos_tests.c).

Let me know if I got this wrong.

EDIT1: As it turns out the function List_merge is also inline and has the same problem. I moved the definition from the c-source to the header file as well (and removed the original declaration in the header file).

EDIT2: I found lots of inline functions all defined in the c-source so, if called from a test file will be undefined reference if gcc heeds the hint, which it consistently does in make dev and does not in make all. I will attempt to correct it all and commit these changes separately. The current pull request might automatically include them, if you didn’t merge yet.

EDIT3: Doing an nm on the static library (after a normal make) it looks like no ListNode symbols are there, there are no undefines either. If gcc had made an normal function, I would have expected a symbol for ListNode_swap. Doing make dev I get an U ListNode_swp when doing nm on the library. So, I am thoroughly confused how this inline stuff works. Maybe I should continue the course first. After all, if I do a make I have a working library.

EDIT4: (Final edit, I promis). Both ListNode_swap and List_merge needed an extern declaration in the c-source file for the compiler to not give an undefined reference when doing make clean;make dev. For make clean;make everything worked with or without extern declaration and with definition in either c-source or h-file.

The only difference I can think of is -DNDEBUG, which make does have and make dev does not have. But that does not seem relevant at all.

I am officially at a loss how this works.

#8

I have now implemented and tested heapsort.c and committed and pushed it to my fork. If the pull request I did earlier was not merged yet, then this should be part of the pull request too.

EDIT1: I just checked, the newest commit is indeed automatically part of the pull request.

I also changed the depency of tests on target in the Makefile. I noticed testfiles were not being compiled if I had a new library. Adding $(TARGETS) to the dependeny of tests solved the problem.

I created heapsort with a user license as standard for this project, or at user choice any license GPL v3 or higher. I hope that doesn’t clash with the lcthw project.

#9

Great, I’ll hit this very soon. I started a new class with a bunch of people today so haven’t had time.

#10

No problem, I will also commit the mergesort today. I am not completely happy with my style of coding. It is a lot more wordy than I see others program, so any feedback is welcome.

Kind regards, Guus.

1 Like