|
NAMETree::Node - Memory-efficient tree nodes in PerlSYNOPSISuse Tree::Node; $node = Tree::Node->new(2); $node->set_child(0, $left); $node->set_child(1, $right); while ($node->key_cmp($key) < 0) { $node = $node->get_child(0); } DESCRIPTIONThis module implements a memory-efficient node type (for trees, skip lists and similar data structures) for Perl.You may ask "Why bother implementing an ordered structure such as a tree when Perl has hashes built-in?" Since Perl is optimized for speed over memory usage, hashes (and lists) use a lot of memory. Using Devel::Size for a reference, a list with four elements (corresponding to a key, value, and two child node pointers) will use at least 120 bytes. A hash with four key/value pairs will use at least 228 bytes. But an equivalent Tree::Node object will use at least 68 bytes. (However, see the "KNOWN ISSUES" section below for caveats regarding memory usage.) So the purpose of this package is to provide a simple low-level Node class which can be used as a base class to implement various kinds of tree structures. Each node has a key/value pair and a variable number of "children" pointers. How nodes are organized or the algorithm used to organize them is for you to implement. Object Oritented Interface
Procedural InferfaceThe experimental procedural interface was added in version 0.06. The advantage of this interface is that there is much less overhead than the object-oriented interface (16 bytes instead of 45 bytes). A disadvantage is that the node cannot be simply subclassed to change the "p_key_cmp" function.To use the procedural interface, you must import the procedure names: use Tree::Node ':p_node'; Aside from working with pointers rather than blessed objects, the procedures listed below are analagous to their object-oriented counterparts. However, you must manually call "p_destroy" when you are done with the node, since Perl will not automatically destroy it when done.
KNOWN ISSUESThis module implements a Perl wrapper around a C struct, which for the object-oriented inferface involves a blessed reference to a pointer to the struct. This overhead of about 45 bytes may make up for any memory savings that the C-based struct provided!So if you what you are doing is implementing a simple key/value lookup, then you may be better off sticking with hashes. If what you are doing requires a special structure that cannot be satisfied with hashes (even sorted hashes), or requires a very large number of nodes, then this module may be useful to you. Another alternative is to use the "Procedural Interface". Packages such as Clone and Storable cannot properly handle Tree::Node objects. Devel::Size may not properly determine the size of a node. Use the "_allocated" method to determine how much space is allocated for the node in C. This does not include the overhead for Perl to maintain a reference to the C struct. SEE ALSOTree::DAG_Node is written in pure Perl, but it offers a more flexible interface.AUTHORRobert Rothenberg <rrwo at cpan.org>Suggestions and Bug ReportingFeedback is always welcome. Please use the CPAN Request Tracker at <http://rt.cpan.org> to submit bug reports.LICENSECopyright (c) 2005,2007 Robert Rothenberg. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
Visit the GSP FreeBSD Man Page Interface. |