| Stop Censorship |
| The Music and Movie industries attempt to disable the internet and truncate your freedom of speech using US legislation nicknamed SOPA, PIPA and as of April 2012, CISPA. |
| ACTA is just as bad (perhaps worse) and and an attempt is in progress to get it approved by governments all over the world. |
| The DMCA law in the US is equally bad and was written by the same industries but I don't document the law or its bad effects on the world's people here. |
| See my censorship web page with its links to more information on how vital it is to stop PIPA, SOPA, and ACTA. |
| HOME | Software | Palm | DWARF | Lotus Cars | RPM Building | eeepc | kindle |
|
|
||
David A's tsearch example |
One application I wrote has both C and C++ versions. I wanted search routines for C that would do what the C++ map and set STL datatypes do. A base requirement (for me) is that the routines be open source, not proprietary. A few minutes search turned up hsearch and tsearch. Both are in the Single Unix Specification and both are part of GNU libc. I am sure there are other similar routines on the web.
hsearch is pretty useless because one must provide a fixed size for the table (which cannot be increased). And there is no way to empty the table. I won't mention hsearch again.
tsearch is much better. It grows as necessary automatically and the GNU glibc version has a tdestroy() function to clean out all memory used. It is a binary tree representation so performance is quite reasonable. The cutest part is that nothing in the library has any dependency on the data involved. So the same code (see the example code) works fine as either a map or a set.
What I found surprising and bizarre was that in some cases the values are void *pointers and in some cases they are pointers-to-pointers, but all the function interfaces simply say void *. I found existing documentation (including the Single Unix Specification) to be unclear on where the values were actually pointers-to-pointers. I found an example on the web which failed to account for this and which therefore simply did not entirely work on Linux.
I do not currently (2011) have access to IRIX, HP-UX, Solaris or any other Unix so I do not know whether this characteristic is solely a Linux issue.
When you see something like the following pointer indirection in the source you are dealing with one of the indirect pointers.
struct my_tentry *m = *(struct my_tentry **)mt_data;
The C example assumes you have a GNU libc in that it calls tdestroy(), which is a GNU only function. If you have a non-GNU libc just comment out the call to tdestroy() and compile with cc (it should work).
Another surprise was the difficulty in using tdelete() so that memory was not leaked. Similarly, using tsearch without leaking was tricky. I discovered and fixed these problems in the tsearch.c source on about September 8, 2011.
An example of a build and execution of the code on Linux Ubuntu 9.10 for X86 follows:
q2 1206: gcc -Wall tsearch.c q2 1207: ./a.out insert ok 0 insert ok 1 insert ok 2 found ok 0 found ok 1 found ok 2 Fail TSRCH on 3 is ok Fail TSRCH on 4 is ok <0>Walk on node preorder 1 data for 1 <1>Walk on node leaf 0 data for 0 <0>Walk on node postorder 1 data for 1 <1>Walk on node leaf 2 data for 2 <0>Walk on node endorder 1 data for 1 tdelete returned parent: 2 data for 2 <0>Walk on node preorder 2 data for 2 <1>Walk on node leaf 0 data for 0 <0>Walk on node postorder 2 data for 2 <0>Walk on node endorder 2 data for 2 PASS tsearch test.
Enjoy!