Thanks for clearing that up. I was expecting to see XSUB stuff looking like the examples in perlxstut but it seems those stubs are indeed sufficient for functions that don't involve passing anything fancy like structs or arrays.

I finally got it to work by making two changes. (Irrelevant stuff trimmed)

TwinTree.xs : libtwintree.so install
        mkdir -p TwinTree && \
        cp libtwintree.h TwinTree && \
        h2xs -Oxan TwinTree libtwintree.h -ltwintree
# Removed "lib" ----------------------------^

libtwintree.so : libtwintree.o
        gcc -shared -o libtwintree.so libtwintree.o
# Removed "-Wl,-soname,libtwintree.so" and "-lc"
[download]

Again, thank you for putting up and pointing me in the right direction :-)