Date | Commit message (Collapse) |
|
* fix segfault from unpredictable GC ordering
when node objects outlive the trees they come from
|
|
We cannot guarantee GC will mark valid nodes when the tree
the node belongs to is destroyed, so we have to allocate
a new node that is a copy of the original node whenever
we create Patricia::Node objects
|
|
* rely on Ruby GC for allocations/free
no need to explicitly destroy objects anymore
* Ruby 1.9.2 C API compatibility
* allow creation of subclasses of Patricia class
* non-String objects may be stored as node-data
* Patricia::Node objects are returned when match succeeds
It's no longer possible to call tree methods on node
objects and cause segfaults.
* Patricia#show_nodes may be given a custom IO-like object
* sync docs with remove, match_best and match_exact behavior
* ArgumentError is raised for invalid addresses
no more assertion failures for bad addresses
* Patricia#show_nodes and Patricia#num_nodes no longer
segfaults on empty trees
|
|
This makes it easy to dump the node output to an
alternate IO/StringIO object without temporarily
replacing $stdout.
|
|
match_best and match_exact will both return nil instead
of false on failures, matching the documentation.
remove documentation is updated to match the code, which
returns true or false, never nil.
|
|
Ruby's xcalloc() has built-in failure handling and will force
GC to run if memory is needed. Patricia.new will no longer
fail with anything other than NoMemoryError, which rare.
|
|
This behaves like Patricia#match_best, but is more
efficient as it does not need to allocate a new object
on successful matches.
|
|
While the GC can take care of this, this is still useful
if one wishes to reuse the same object.
|
|
Instead of defining the Patricia.new singleton method, we
only need to define the allocation function. The allocation
function allows "dup" and "clone" methods to be called on
Patricia instances and we will walk the original tree
to copy node prefixes and data into the new one.
This also allows us to subclass Patricia and create
objects from that subclass.
|
|
Patricia#num_nodes properly returns zero and
Patricia#show_nodes displays nothing.
|
|
This allows the output of Patricia#show_nodes to be redirected
to StringIO objects (or anything else that responds to printf).
Since Ruby 1.9 no longer uses stdio, this lets us go through the
normal output stream used by Ruby.
|
|
This prevents improper dereferencing and segfaults if the code
is misused. Instead NoMethodError should be raised when it
would previously segfault.
|
|
This is preferable to hitting an assertion and killing
the running process. The plan is this code will deal with
potentially hostile/invalid user inputs in a network server,
so we do not have the luxury if just letting a process die.
|
|
rb_str_dup should be slightly faster as the call stack
is shallower and does not need additional method lookups
|
|
STR2CSTR has been deprecated for a while now, and is
completely removed in Ruby 1.9.2-preview3
|
|
This prevents segfaults from double free() calls when using
Patricia#destroy on node data or the same object twice.
Patricia#destroy and Patricia#clear are now no-ops for backwards
compatibility.
One (hopefully welcome) side effect of this change is that
arbitrary Ruby objects may be attached to nodes, not just
strings. String objects will continue to alway be duplicated
when returned to the user for backwards compatibility, but
arbitrary Ruby objects may be attached to each node. This
feature can now be used to track node usage data directly in the
Patricia object without the need for a separate lookup table.
The only downside of this change is that the GC mark phase
takes a tiny bit longer due to the presence of more Ruby
objects.
There are also additional tests for the new behavior, including
an expensive test to force GC pressure and ensure there are no
memory leaks.
|
|
There is no need for these functions and global variable
to be visible outside of rpatricia.c, so mark them as
static to avoid potential conflicts with other libraries.
|
|
- reorganized directory layout
no chance of accidentally having 'extconf' in the require path
|
|
This makes it easier to avoid accidentally putting extconf.rb
and test.rb in an application $LOAD_PATH
|
|
To build the gem:
gem build rpatricia.gemspec
|
|
|