Can't really help out with h2xs, and I'm not entirely sure that I understand what you're doing. You say you want "to write a shared C library to be used from Perl", but then you seem to merely want to generate an XS file with a couple of functions in it. Anyway, fwiw, which may not be much:
<plug>
I can generate an XS file, a Makefile.PL and a stub TwinTree.pm using InlineX-C2XS and libtwintree.c.
One caveat - because it's using Inline::C, and because Inline::C doesn't understand 'void' as the argument list, I've had to rewrite libtwintree.c as:

// libtwintree.c:
#include "libtwintree.h"
int return_one() { return 1; }
int return_zero() { return 0; }
[download]

That 'void' in the argument list would be, I think, incorrect if included in the XS functions. (It's certainly not needed, anyway.)

Then it's just a matter of running
perl -MInlineX::C2XS="c2xs" -we 'c2xs("TwinTree","TwinTree",{SRC_LOCATION=>"./libtwintree.c",WRITE_MAKEFILE_PL=>1,VERSION=>0.01,WRITE_PM=>1})'
and you'll find TwinTree.xs, Makefile.PL and TwinTree.pm all sitting in the cwd:
TwinTree.xs:

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

// libtwintree.c:
#include "libtwintree.h"
int return_one() { return 1; }
int return_zero() { return 0; }

MODULE = TwinTree    PACKAGE = TwinTree    

PROTOTYPES: DISABLE


int
return_one ()

int
return_zero ()
[download]

TwinTree.pm:

package TwinTree;
use strict;


require Exporter;
*import = \&Exporter::import;
require DynaLoader;


$TwinTree::VERSION = '0.01';


DynaLoader::bootstrap TwinTree $TwinTree::VERSION;


@TwinTree::EXPORT = ();

@TwinTree::EXPORT_OK = ();


sub dl_load_flags {0} # Prevent DynaLoader from complaining and croaki
+ng


1;
[download]

Makefile.PL:

use ExtUtils::MakeMaker;
my %options = %{       

{
  'TYPEMAPS' => [],
  'NAME' => 'TwinTree',
  'INC' => '',
  'VERSION' => '0.01'
}

};
WriteMakefile(%options);

# Remove the Makefile dependency. Causes problems on a few systems.
sub MY::makefile { '' }
[download]

That's using version 0.14, which has only just been uploaded to CPAN, amd may take a while to reach all mirrors. Version 0.13 is quite functional, but adds the cwd to INC and the standard perl typemaps to TYPEMAP in the Makefile.PL - which neither breaks nor achieves anything (but is a bit annoying).
</plug>

Cheers,
Rob