From f0a0540239edfa94f727190d35ffe4e7814a8844 Mon Sep 17 00:00:00 2001 From: Marius Gavrilescu Date: Sat, 24 Feb 2018 19:02:05 +0000 Subject: [PATCH 1/1] Initial commit --- Changes | 4 ++ MANIFEST | 6 ++ Makefile.PL | 22 +++++++ README | 44 +++++++++++++ lib/Tie/Hash/Sorted/XS.pm | 130 ++++++++++++++++++++++++++++++++++++++ t/Tie-Hash-Sorted-XS.t | 35 ++++++++++ 6 files changed, 241 insertions(+) create mode 100644 Changes create mode 100644 MANIFEST create mode 100644 Makefile.PL create mode 100644 README create mode 100644 lib/Tie/Hash/Sorted/XS.pm create mode 100644 t/Tie-Hash-Sorted-XS.t diff --git a/Changes b/Changes new file mode 100644 index 0000000..b00e035 --- /dev/null +++ b/Changes @@ -0,0 +1,4 @@ +Revision history for Perl extension Tie::Hash::Sorted::XS. + +0.000_001 2018-02-24T19:02+00:00 + - Initial release diff --git a/MANIFEST b/MANIFEST new file mode 100644 index 0000000..d298900 --- /dev/null +++ b/MANIFEST @@ -0,0 +1,6 @@ +Changes +Makefile.PL +MANIFEST +README +t/Tie-Hash-Sorted-XS.t +lib/Tie/Hash/Sorted/XS.pm diff --git a/Makefile.PL b/Makefile.PL new file mode 100644 index 0000000..ccc6936 --- /dev/null +++ b/Makefile.PL @@ -0,0 +1,22 @@ +use ExtUtils::MakeMaker; +use strict; +use warnings; + +WriteMakefile( + NAME => 'Tie::Hash::Sorted::XS', + VERSION_FROM => 'lib/Tie/Hash/Sorted/XS.pm', + ABSTRACT_FROM => 'lib/Tie/Hash/Sorted/XS.pm', + AUTHOR => 'Marius Gavrilescu ', + MIN_PERL_VERSION => '5.14.0', + LICENSE => 'perl', + SIGN => 1, + PREREQ_PM => { + qw/Tree::SizeBalanced 0/, + }, + META_ADD => { + dynamic_config => 0, + resources => { + repository => 'https://git.ieval.ro/?p=tie-hash-sorted-xs.git', + }, + } +); diff --git a/README b/README new file mode 100644 index 0000000..171fb92 --- /dev/null +++ b/README @@ -0,0 +1,44 @@ +Tie-Hash-Sorted-XS version 0.000_001 +==================================== + +This module is not yet fully implemented. Current limitations include +the CLEAR function not being implemented (meaning it is impossible to +assign a list to a tied hash) and iteration being slow (O(n log n) to +iterate over the whole hash). The latter is due to lack of suitable +methods in the underlying Tree::SizeBalanced. + +Tree::SizeBalanced is an implementation of a size-balanced tree, a +kind of self-balanced binary search tree. This is a data structure +similar to a Perl hash that permits O(log n) insertion, deletion, and +random access while keeping the keys sorted. + +This module is a tie interface to Tree::SizeBalanced. It allows one to +create a hash that is implemented by a Tree::SizeBalanced. +These hashes should work similarly to regular Perl hashes except that +keys will be ordered, keys can be any objects (not just strings), and +they have different performance characteristics. + +INSTALLATION + +To install this module type the following: + + perl Makefile.PL + make + make test + make install + +DEPENDENCIES + +This module requires these other modules and libraries: + +* Tie::Hash::Sorted::XS + +COPYRIGHT AND LICENCE + +Copyright (C) 2018 by Marius Gavrilescu + +This library is free software; you can redistribute it and/or modify +it under the same terms as Perl itself, either Perl version 5.24.3 or, +at your option, any later version of Perl 5 you may have available. + + diff --git a/lib/Tie/Hash/Sorted/XS.pm b/lib/Tie/Hash/Sorted/XS.pm new file mode 100644 index 0000000..2867209 --- /dev/null +++ b/lib/Tie/Hash/Sorted/XS.pm @@ -0,0 +1,130 @@ +package Tie::Hash::Sorted::XS; + +use 5.014000; +use strict; +use warnings; + +use Tree::SizeBalanced; + +our $VERSION = '0.000_001'; + +sub TIEHASH { + my ($class, $tree) = @_; + $tree //= Tree::SizeBalanced::str_any->new; + bless \$tree, $class +} + +sub FETCH { + my ($self, $key) = @_; + my ($k, $v) = $$self->find($key); + $v +} + +sub STORE { + my ($self, $key, $value) = @_; + $$self->delete($key); + $$self->insert($key, $value); +} + +sub DELETE { + my ($self, $key) = @_; + $$self->delete($key); +} + +# sub CLEAR unimplemented + +sub EXISTS { + my ($self, $key) = @_; + my @list = $$self->find($key); + @list > 0; +} + +sub FIRSTKEY { + my ($self) = @_; + $$self->find_min +} + +sub NEXTKEY { + my ($self, $lastkey) = @_; + $$self->find_gt($lastkey); +} + +sub SCALAR { + my ($self) = @_; + $$self->size +} + +1; +__END__ + +=encoding utf-8 + +=head1 NAME + +Tie::Hash::Sorted::XS - hash with ordered keys backed by binary search tree + +=head1 SYNOPSIS + + use Tie::Hash::Sorted::XS; + + tie my %hash, 'Tie::Hash::Sorted::XS'; + + $hash{Jim} = 5; + $hash{Bob} = 3; + $hash{Anna} = 7; + + my $keys = join ' ', keys %hash; + + is $keys, 'Anna Bob Jim', 'keys are ordered'; + is $hash{Bob}, 3, 'retrieval works'; + +=head1 DESCRIPTION + +This module is not yet fully implemented. Current limitations include +the CLEAR function not being implemented (meaning it is impossible to +assign a list to a tied hash) and iteration being slow (O(n log n) to +iterate over the whole hash). The latter is due to lack of suitable +methods in the underlying L. + +L is an implementation of a size-balanced tree, a +kind of self-balanced binary search tree. This is a data structure +similar to a Perl hash that permits O(log n) insertion, deletion, and +random access while keeping the keys sorted. + +This module is a C interface to L. It allows +one to create a hash that is implemented by a L. +These hashes should work similarly to regular Perl hashes except that +keys will be ordered, keys can be any objects (not just strings), and +they have different performance characteristics. + +The module is used by calling the tie function: + +=over + +=item B my %hash, 'Tie::Hash::Sorted::XS'[, I<$tree>] + +This ties a brand new hash to a given L object (or +if none is given, C<< Tree::SizeBalanced::str_any->new >> is used). + +Whenever this hash is iterated, the keys will come ordered. + +=back + +=head1 SEE ALSO + +L, L + +=head1 AUTHOR + +Marius Gavrilescu, Emarius@ieval.roE + +=head1 COPYRIGHT AND LICENSE + +Copyright (C) 2018 by Marius Gavrilescu + +This library is free software; you can redistribute it and/or modify +it under the same terms as Perl itself, either Perl version 5.24.3 or, +at your option, any later version of Perl 5 you may have available. + + +=cut diff --git a/t/Tie-Hash-Sorted-XS.t b/t/Tie-Hash-Sorted-XS.t new file mode 100644 index 0000000..46431fb --- /dev/null +++ b/t/Tie-Hash-Sorted-XS.t @@ -0,0 +1,35 @@ +#!/usr/bin/perl +use strict; +use warnings; + +use Test::More tests => 5; +BEGIN { use_ok('Tie::Hash::Sorted::XS') }; + +tie my %hash, 'Tie::Hash::Sorted::XS'; + +$hash{Jim} = 5; +$hash{Bob} = 3; +$hash{Anna} = 7; + +my $keys = join ' ', keys %hash; + +is $keys, 'Anna Bob Jim', 'keys are ordered'; +is $hash{Bob}, 3, 'retrieval works'; + + +tie my %refhash, 'Tie::Hash::Sorted::XS', Tree::SizeBalanced::any_int->new(sub { $$a <=> $$b }); +$refhash{\5} = 1; +my $three = 3; +$refhash{\$three} = 2; +my $tworef = \2; +$refhash{$tworef} = 3; + +my $values = ''; +for (keys %refhash) { + $values .= $refhash{$_} . ' '; +} +chop $values; + +my @keys = keys %refhash; +is ref($keys[0]), 'SCALAR', 'non-string keys work'; +is $values, '3 2 1', 'values of refhash' -- 2.30.2