{
   package Node;

   use strict;
   use warnings;

   use Inline C => <<'__EOI__';

      typedef struct {
         // ...
      } Node;

      Node* new_node() {
         Node* node;
         warn("new_node\n"); // DEBUG
         Newx(node, 1, Node);
         // node->... = ...;
         return node;
      }

      void DESTROY(Node* node) {
         warn("DESTROY\n"); // DEBUG
         Safefree(node);
      }

__EOI__
}

{
   use strict;
   use warnings;

   my $x = Node::new_node();
}
[download]

typemap:

Node* T_OBJECT

INPUT
T_OBJECT
   if (sv_derived_from($arg, \"${subtype}\")) {
      IV tmp = SvIV((SV*)SvRV($arg));
      $var = INT2PTR($type,tmp);
   }
   else
      Perl_croak(aTHX_ \"%s: %s is not of type %s\",
         ${$ALIAS?\q[GvNAME(CvGV(cv))]:\qq[\"$pname\"]},
         \"$var\", \"$subtype\")

OUTPUT
T_OBJECT
   sv_setref_pv($arg, \"${subtype}\", (void*)$var);
[download]

I was going to use the T_PTROBJ map for Node*, but it was blessing the objects into NodePtr instead of Node. T_OBJECT is just T_PTROBJ that uses $subtype instead of $type.