AVLTree
view release on metacpan or search on metacpan
#include "XSUB.h"
#include "ppport.h"
#include "avltree.h"
#ifdef __cplusplus
}
#endif
typedef avltree_t AVLTree;
typedef avltrav_t AVLTrav;
/* C-level callbacks required by the AVL tree library */
static SV* callback = (SV*)NULL;
static int svcompare(SV *p1, SV *p2) {
/*
This is one way to avoid the above mentioned error when
declaring the PERL_NO_GET_CONTEXT macro
*/
README
scripts/benchmarks.pl
t/00-load.t
t/01-numbers.t
t/02-custom.t
t/03-leak.t
t/manifest.t
t/pod-coverage.t
t/pod.t
TODO
typemap
xt/boilerplate.t
META.yml Module YAML meta-data (added by MakeMaker)
META.json Module JSON meta-data (added by MakeMaker)
},
"runtime" : {
"requires" : {
"perl" : "5.008"
}
}
},
"release_status" : "stable",
"resources" : {
"repository" : {
"type" : "git",
"url" : "https://github.com/avullo/AVLTree.git",
"web" : "https://github.com/avullo/AVLTree"
}
},
"version" : "v0.1.7",
"x_serialization_backend" : "JSON::PP version 2.27400"
}
Makefile.PL view on Meta::CPAN
'Test::LeakTrace' => '0'
},
PREREQ_PM => {
#'ABC' => '1.6',
#'Foo::Bar::Module' => '5.0401',
},
META_MERGE => {
'meta-spec' => { version => 2 },
resources => {
repository => {
type => 'git',
url => 'https://github.com/avullo/AVLTree.git',
web => 'https://github.com/avullo/AVLTree',
},
},
},
LIBS => [''], # e.g., '-lm',
DEFINE => '-DENABLE_DEBUG', # e.g., '-DHAVE_SOMETHING'
INC => '-Iavltree', # e.g., '-I/usr/include/other'
MYEXTLIB => 'avltree/libavltree$(LIB_EXT)',
dist => { COMPRESS => 'gzip -9f', SUFFIX => 'gz', },
avltree/avltree.c view on Meta::CPAN
using std::size_t;
#else
#include <stdlib.h>
#include <stdio.h>
#endif
#ifndef HEIGHT_LIMIT
#define HEIGHT_LIMIT 64 /* Tallest allowable tree */
#endif
typedef struct avlnode {
int balance; /* Balance factor */
SV *data; /* User-defined content */
struct avlnode *link[2]; /* Left (0) and right (1) links */
} avlnode_t;
struct avltree {
avlnode_t *root; /* Top of the tree */
cmp_f cmp; /* Compare two items */
dup_f dup; /* Clone an item (user-defined) */
rel_f rel; /* Destroy an item (user-defined) */
avltree/avltree.h view on Meta::CPAN
using std::size_t;
extern "C" {
#else
#include <stddef.h>
#endif
#include <EXTERN.h>
#include <perl.h>
/* Opaque types */
typedef struct avltree avltree_t;
typedef struct avltrav avltrav_t;
/* User-defined item handling */
typedef int (*cmp_f) ( SV *p1, SV *p2 );
typedef SV *(*dup_f) ( SV* p );
typedef void (*rel_f) ( SV* p );
/* AVL tree functions */
avltree_t *avltree_new ( cmp_f cmp, dup_f dup, rel_f rel );
void avltree_delete ( avltree_t *tree );
SV *avltree_find ( pTHX_ avltree_t *tree, SV *data );
int avltree_insert ( avltree_t *tree, SV *data );
int avltree_erase ( avltree_t *tree, SV *data );
size_t avltree_size ( avltree_t *tree );
/* Traversal functions */
lib/AVLTree.pm view on Meta::CPAN
Arg [1] : (required) A reference to a subroutine
Example : my $tree->new(\&compare);
carp "Unable to instantiate tree" unless defined $tree;
Description : Creates a new AVL tree object.
The objects hold by the tree are implicitly defined
by the provided callback.
Returntype : AVLTreePtr or undef if unable to instantiate
Exceptions : None
Caller : General
Status : Unstable, interface might change to accomodate suitable defaults,
e.g. numbers
=head2 C<find>
Arg [1] : Item to search, can be defined just in terms of the attribute
with which the items in the tree are compared.
Example : $tree->find({ id => 10 }); # objects in the tree can hold data as well
if($result) {
printf "Item with id %d found\nData: %s\n", $id, $result->{data};
} else { print "Item with id $id not found\n"; }
Description : Query if an item exists in the tree.
Returntype : The item, if found, as stored in the tree or undef
if the item was not found or the query was not provided
or it was undefined.
Exceptions : None
Caller : General
Status : Unstable
=head2 C<insert>
Arg [1] : An item to insert in the tree.
Example : my $ok = $tree->insert({ id => 10, data => 'ten' });
croak "Unable to insert 10" unless $ok;
Description : Insert an item in the tree, use the provided, upon tree construction,
comparison function to determine the position of the item in the tree
Returntype : Bool, true if the item was successfully installed, false otherwise
Exceptions : None
Caller : General
Status : Unstable
=head2 C<remove>
Arg[1] : An item to remove from the tree
Example : my $ok = $tree->remove({ id => 10 });
croak "Unable to remove 10" unless $ok;
Description : Remove an item from the tree.
Returntype : Bool, true if the item was successfully installed, false otherwise
Exceptions : None
Caller : General
Status : Unstable
=head2 C<size>
Arg[...] : None
Example : print "Size of the tree is: %d\n", $tree->size();
Description : Returns the size of the tree (number of nodes)
Returntype : Int, the size of the tree
Exceptions : None
Caller : General
Status : Unstable
=head1 TREE TRAVERSAL METHODS
=head2 C<first>
Arg [...] : None
Example : my $item = $tree->first;
Description : Returns the first element as specified by the order defined by the tree.
Returntype : The item, if found, as stored in the tree or undef
if the tree is empty.
Exceptions : None
Caller : General
Status : Unstable
=head2 C<last>
Arg [...] : None
Example : my $item = $tree->last;
Description : Returns the last element as specified by the order defined by the tree.
Returntype : The item, if found, as stored in the tree or undef
if the tree is empty.
Exceptions : None
Caller : General
Status : Unstable
=head2 C<next>
Arg [...] : None
Example : my $item = $tree->first;
print $item, "\n";
while($item = $tree->next) { print $item, "\n"; }
Description : Returns the next element as specified by the order defined by the tree.
Returntype : The item, if found, as stored in the tree or undef
if the tree is empty.
Exceptions : None
Caller : General
Status : Unstable
=head2 C<prev>
Arg [...] : None
Example : my $item = $tree->last;
print $item, "\n";
while($item = $tree->prev) { print $item, "\n"; }
Description : Returns the previous element as specified by the order defined by the tree.
Returntype : The item, if found, as stored in the tree or undef
if the tree is empty.
Exceptions : None
Caller : General
Status : Unstable
=head1 DEPENDENCIES
AVLTree requires Carp and Test::More, Test::Deep and Test::LeakTrace to run the tests during installation.
If you want to run the benchmarks in the scripts directory, you need to install the Benchmark
and List::Util modules.
grok_number() NEED_grok_number NEED_grok_number_GLOBAL
grok_numeric_radix() NEED_grok_numeric_radix NEED_grok_numeric_radix_GLOBAL
grok_oct() NEED_grok_oct NEED_grok_oct_GLOBAL
load_module() NEED_load_module NEED_load_module_GLOBAL
my_snprintf() NEED_my_snprintf NEED_my_snprintf_GLOBAL
my_sprintf() NEED_my_sprintf NEED_my_sprintf_GLOBAL
my_strlcat() NEED_my_strlcat NEED_my_strlcat_GLOBAL
my_strlcpy() NEED_my_strlcpy NEED_my_strlcpy_GLOBAL
newCONSTSUB() NEED_newCONSTSUB NEED_newCONSTSUB_GLOBAL
newRV_noinc() NEED_newRV_noinc NEED_newRV_noinc_GLOBAL
newSV_type() NEED_newSV_type NEED_newSV_type_GLOBAL
newSVpvn_flags() NEED_newSVpvn_flags NEED_newSVpvn_flags_GLOBAL
newSVpvn_share() NEED_newSVpvn_share NEED_newSVpvn_share_GLOBAL
pv_display() NEED_pv_display NEED_pv_display_GLOBAL
pv_escape() NEED_pv_escape NEED_pv_escape_GLOBAL
pv_pretty() NEED_pv_pretty NEED_pv_pretty_GLOBAL
sv_2pv_flags() NEED_sv_2pv_flags NEED_sv_2pv_flags_GLOBAL
sv_2pvbyte() NEED_sv_2pvbyte NEED_sv_2pvbyte_GLOBAL
sv_catpvf_mg() NEED_sv_catpvf_mg NEED_sv_catpvf_mg_GLOBAL
sv_catpvf_mg_nocontext() NEED_sv_catpvf_mg_nocontext NEED_sv_catpvf_mg_nocontext_GLOBAL
sv_pvn_force_flags() NEED_sv_pvn_force_flags NEED_sv_pvn_force_flags_GLOBAL
av_len|||
av_make|||
av_pop|||
av_push|||
av_reify|||
av_shift|||
av_store|||
av_undef|||
av_unshift|||
ax|||n
bad_type|||
bind_match|||
block_end|||
block_gimme||5.004000|
block_start|||
blockhook_register||5.013003|
boolSV|5.004000||p
boot_core_PerlIO|||
boot_core_UNIVERSAL|||
boot_core_mro|||
bytes_cmp_utf8||5.013007|
call_method|5.006000||p
call_pv|5.006000||p
call_sv|5.006000||p
caller_cx||5.013005|
calloc||5.007002|n
cando|||
cast_i32||5.006000|
cast_iv||5.006000|
cast_ulong||5.006000|
cast_uv||5.006000|
check_type_and_open|||
check_uni|||
check_utf8_print|||
checkcomma|||
checkposixcc|||
ckWARN|5.006000||p
ck_entersub_args_list||5.013006|
ck_entersub_args_proto_or_list||5.013006|
ck_entersub_args_proto||5.013006|
ck_warner_d||5.011001|v
ck_warner||5.011001|v
grok_bslash_o|||
grok_hex|5.007003||p
grok_number|5.007002||p
grok_numeric_radix|5.007002||p
grok_oct|5.007003||p
group_end|||
gv_AVadd|||
gv_HVadd|||
gv_IOadd|||
gv_SVadd|||
gv_add_by_type||5.011000|
gv_autoload4||5.004000|
gv_check|||
gv_const_sv||5.009003|
gv_dump||5.006000|
gv_efullname3||5.004000|
gv_efullname4||5.006001|
gv_efullname|||
gv_ename|||
gv_fetchfile_flags||5.009005|
gv_fetchfile|||
mess_nocontext|||vn
mess_sv||5.013001|
mess||5.006000|v
method_common|||
mfree||5.007002|n
mg_clear|||
mg_copy|||
mg_dup|||
mg_findext||5.013008|
mg_find|||
mg_free_type||5.013006|
mg_free|||
mg_get|||
mg_length||5.005000|
mg_localize|||
mg_magical|||
mg_set|||
mg_size||5.005000|
mini_mktime||5.007002|
missingterm|||
mode_from_discipline|||
newPVOP|||
newRANGE|||
newRV_inc|5.004000||p
newRV_noinc|5.004000||p
newRV|||
newSLICEOP|||
newSTATEOP|||
newSUB|||
newSVOP|||
newSVREF|||
newSV_type|5.009005||p
newSVhek||5.009003|
newSViv|||
newSVnv|||
newSVpv_share||5.013006|
newSVpvf_nocontext|||vn
newSVpvf||5.004000|v
newSVpvn_flags|5.010001||p
newSVpvn_share|5.007001||p
newSVpvn_utf8|5.010001||p
newSVpvn|5.004050||p
newSV|||
newTOKEN|||
newUNOP|||
newWHENOP||5.009003|
newWHILEOP||5.013007|
newXS_flags||5.009004|
newXSproto||5.006000|
newXS||5.006000|
new_collate||5.006000|
new_constant|||
new_ctype||5.006000|
new_he|||
new_logop|||
new_numeric||5.006000|
new_stackinfo||5.005000|
new_version||5.009000|
new_warnings_bitfield|||
next_symbol|||
nextargv|||
nextchar|||
ninstr|||n
pack_rec|||
package_version|||
package|||
packlist||5.008001|
pad_add_anon|||
pad_add_name_sv|||
pad_add_name|||
pad_alloc|||
pad_block_start|||
pad_check_dup|||
pad_compname_type|||
pad_findlex|||
pad_findmy||5.011002|
pad_fixup_inner_anons|||
pad_free|||
pad_leavemy|||
pad_new|||
pad_peg|||n
pad_push|||
pad_reset|||
pad_setsv|||
savepvs||5.009003|
savepv|||
savesharedpvn||5.009005|
savesharedpvs||5.013006|
savesharedpv||5.007003|
savesharedsvpv||5.013006|
savestack_grow_cnt||5.008001|
savestack_grow|||
savesvpv||5.009002|
sawparens|||
scalar_mod_type|||n
scalarboolean|||
scalarkids|||
scalarseq|||
scalarvoid|||
scalar|||
scan_bin||5.006000|
scan_commit|||
scan_const|||
scan_formline|||
scan_heredoc|||
sv_pvbyte||5.006000|
sv_pvn_force_flags|5.007002||p
sv_pvn_force|||
sv_pvn_nomg|5.007003|5.005000|p
sv_pvn||5.005000|
sv_pvutf8n_force||5.006000|
sv_pvutf8n||5.006000|
sv_pvutf8||5.006000|
sv_pv||5.006000|
sv_recode_to_utf8||5.007003|
sv_reftype|||
sv_release_COW|||
sv_replace|||
sv_report_used|||
sv_reset|||
sv_rvweaken||5.006000|
sv_setiv_mg|5.004050||p
sv_setiv|||
sv_setnv_mg|5.006000||p
sv_setnv|||
sv_setpv_mg|5.004050||p
sv_utf8_upgrade_nomg||5.007002|
sv_utf8_upgrade||5.007001|
sv_uv|5.005000||p
sv_vcatpvf_mg|5.006000|5.004000|p
sv_vcatpvfn||5.004000|
sv_vcatpvf|5.006000|5.004000|p
sv_vsetpvf_mg|5.006000|5.004000|p
sv_vsetpvfn||5.004000|
sv_vsetpvf|5.006000|5.004000|p
sv_xmlpeek|||
svtype|||
swallow_bom|||
swash_fetch||5.007002|
swash_get|||
swash_init||5.006000|
sys_init3||5.010000|n
sys_init||5.010000|n
sys_intern_clear|||
sys_intern_dup|||
sys_intern_init|||
sys_term||5.010000|n
$file{changes} += ($c =~ s/^$HS*#$HS*define$HS+NEED_${func}_GLOBAL\b.*$LF//mg);
}
}
$file{needs_inc_ppport} = keys %{$file{uses}};
if ($file{needs_inc_ppport}) {
my $pp = '';
for $func (sort keys %{$file{needs}}) {
my $type = $file{needs}{$func};
next if $type eq 'extern';
my $suffix = $type eq 'global' ? '_GLOBAL' : '';
unless (exists $file{"needed_$type"}{$func}) {
if ($type eq 'global') {
diag("Files [@{$global{needs}{$func}}] need $func, adding global request");
}
else {
diag("File needs $func, adding static request");
}
$pp .= "#define NEED_$func$suffix\n";
}
}
if ($pp && ($c =~ s/^(?=$HS*#$HS*define$HS+NEED_\w+)/$pp/m)) {
#ifndef dNOOP
# define dNOOP extern int /*@unused@*/ Perl___notused PERL_UNUSED_DECL
#endif
#ifndef NVTYPE
# if defined(USE_LONG_DOUBLE) && defined(HAS_LONG_DOUBLE)
# define NVTYPE long double
# else
# define NVTYPE double
# endif
typedef NVTYPE NV;
#endif
#ifndef INT2PTR
# if (IVSIZE == PTRSIZE) && (UVSIZE == PTRSIZE)
# define PTRV UV
# define INT2PTR(any,d) (any)(d)
# else
# if PTRSIZE == LONGSIZE
# define PTRV unsigned long
# else
#ifndef PERLIO_FUNCS_DECL
# ifdef PERLIO_FUNCS_CONST
# define PERLIO_FUNCS_DECL(funcs) const PerlIO_funcs funcs
# define PERLIO_FUNCS_CAST(funcs) (PerlIO_funcs*)(funcs)
# else
# define PERLIO_FUNCS_DECL(funcs) PerlIO_funcs funcs
# define PERLIO_FUNCS_CAST(funcs) (funcs)
# endif
#endif
/* provide these typedefs for older perls */
#if (PERL_BCDVERSION < 0x5009003)
# ifdef ARGSproto
typedef OP* (CPERLscope(*Perl_ppaddr_t))(ARGSproto);
# else
typedef OP* (CPERLscope(*Perl_ppaddr_t))(pTHX);
# endif
typedef OP* (CPERLscope(*Perl_check_t)) (pTHX_ OP*);
#endif
#ifndef isPSXSPC
# define isPSXSPC(c) (isSPACE(c) || (c) == '\v')
#endif
#ifndef isBLANK
# define isBLANK(c) ((c) == ' ' || (c) == '\t')
#endif
#endif
/*
* Boilerplate macros for initializing and accessing interpreter-local
* data from C. All statics in extensions should be reworked to use
* this, if you want to make the extension thread-safe. See ext/re/re.xs
* for an example of the use of these macros.
*
* Code that uses these macros is responsible for the following:
* 1. #define MY_CXT_KEY to a unique string, e.g. "DynaLoader_guts"
* 2. Declare a typedef named my_cxt_t that is a structure that contains
* all the data that needs to be interpreter-local.
* 3. Use the START_MY_CXT macro after the declaration of my_cxt_t.
* 4. Use the MY_CXT_INIT macro such that it is called exactly once
* (typically put in the BOOT: section).
* 5. Use the members of the my_cxt_t structure everywhere as
* MY_CXT.member.
* 6. Use the dMY_CXT macro (a declaration) in all the functions that
* access MY_CXT.
*/
#endif
#ifndef SvREFCNT_inc_void_NN
# define SvREFCNT_inc_void_NN(sv) (void)(++SvREFCNT((SV*)(sv)))
#endif
#ifndef SvREFCNT_inc_simple_void_NN
# define SvREFCNT_inc_simple_void_NN(sv) (void)(++SvREFCNT((SV*)(sv)))
#endif
#ifndef newSV_type
#if defined(NEED_newSV_type)
static SV* DPPP_(my_newSV_type)(pTHX_ svtype const t);
static
#else
extern SV* DPPP_(my_newSV_type)(pTHX_ svtype const t);
#endif
#ifdef newSV_type
# undef newSV_type
#endif
#define newSV_type(a) DPPP_(my_newSV_type)(aTHX_ a)
#define Perl_newSV_type DPPP_(my_newSV_type)
#if defined(NEED_newSV_type) || defined(NEED_newSV_type_GLOBAL)
SV*
DPPP_(my_newSV_type)(pTHX_ svtype const t)
{
SV* const sv = newSV(0);
sv_upgrade(sv, t);
return sv;
}
#endif
#endif
#define Perl_grok_number DPPP_(my_grok_number)
#if defined(NEED_grok_number) || defined(NEED_grok_number_GLOBAL)
int
DPPP_(my_grok_number)(pTHX_ const char *pv, STRLEN len, UV *valuep)
{
const char *s = pv;
const char *send = pv + len;
const UV max_div_10 = UV_MAX / 10;
const char max_mod_10 = UV_MAX % 10;
int numtype = 0;
int sawinf = 0;
int sawnan = 0;
while (s < send && isSPACE(*s))
s++;
if (s == send) {
return 0;
} else if (*s == '-') {
s++;
numtype = IS_NUMBER_NEG;
}
else if (*s == '+')
s++;
if (s == send)
return 0;
/* next must be digit or the radix separator or beginning of infinity */
if (isDIGIT(*s)) {
/* UVs are at least 32 bits, so the first 9 decimal digits cannot
break;
}
if (digit >= 0 && digit <= 9
&& (s < send)) {
/* value overflowed.
skip the remaining digits, don't
worry about setting *valuep. */
do {
s++;
} while (s < send && isDIGIT(*s));
numtype |=
IS_NUMBER_GREATER_THAN_UV_MAX;
goto skip_value;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
numtype |= IS_NUMBER_IN_UV;
if (valuep)
*valuep = value;
skip_value:
if (GROK_NUMERIC_RADIX(&s, send)) {
numtype |= IS_NUMBER_NOT_INT;
while (s < send && isDIGIT(*s)) /* optional digits after the radix */
s++;
}
}
else if (GROK_NUMERIC_RADIX(&s, send)) {
numtype |= IS_NUMBER_NOT_INT | IS_NUMBER_IN_UV; /* valuep assigned below */
/* no digits before the radix means we need digits after it */
if (s < send && isDIGIT(*s)) {
do {
s++;
} while (s < send && isDIGIT(*s));
if (valuep) {
/* integer approximation is valid - it's 0. */
*valuep = 0;
}
}
} else if (*s == 'N' || *s == 'n') {
/* XXX TODO: There are signaling NaNs and quiet NaNs. */
s++; if (s == send || (*s != 'A' && *s != 'a')) return 0;
s++; if (s == send || (*s != 'N' && *s != 'n')) return 0;
s++;
sawnan = 1;
} else
return 0;
if (sawinf) {
numtype &= IS_NUMBER_NEG; /* Keep track of sign */
numtype |= IS_NUMBER_INFINITY | IS_NUMBER_NOT_INT;
} else if (sawnan) {
numtype &= IS_NUMBER_NEG; /* Keep track of sign */
numtype |= IS_NUMBER_NAN | IS_NUMBER_NOT_INT;
} else if (s < send) {
/* we can have an optional exponent part */
if (*s == 'e' || *s == 'E') {
/* The only flag we keep is sign. Blow away any "it's UV" */
numtype &= IS_NUMBER_NEG;
numtype |= IS_NUMBER_NOT_INT;
s++;
if (s < send && (*s == '-' || *s == '+'))
s++;
if (s < send && isDIGIT(*s)) {
do {
s++;
} while (s < send && isDIGIT(*s));
}
else
return 0;
}
}
while (s < send && isSPACE(*s))
s++;
if (s >= send)
return numtype;
if (len == 10 && memEQ(pv, "0 but true", 10)) {
if (valuep)
*valuep = 0;
return IS_NUMBER_IN_UV;
}
return 0;
}
#endif
#endif
( run in 2.162 seconds using v1.01-cache-2.11-cpan-df04353d9ac )