AVLTree

 view release on metacpan or  search on metacpan

MANIFEST  view on Meta::CPAN

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)

MANIFEST.SKIP  view on Meta::CPAN

\.old$
\#$
\b\.#
\.bak$
\.tmp$
\.#
\.rej$
\..*\.sw.?$

# Avoid OS-specific files/dirs
# Mac OSX metadata
\B\.DS_Store
# Mac OSX SMB mount metadata files
\B\._

# Avoid Devel::Cover and Devel::CoverX::Covered files.
\bcover_db\b
\bcovered\b

# Avoid prove files
\B\.prove$

# Avoid MYMETA files

avltree/avltree.c  view on Meta::CPAN

#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) */
  size_t         size;   /* Number of items (user-defined) */
};

avltree/avltree.h  view on Meta::CPAN

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 */
avltrav_t *avltnew ( void );
void       avltdelete ( avltrav_t *trav );
SV        *avltfirst (pTHX_ avltrav_t *trav, avltree_t *tree );
SV        *avltlast (pTHX_ avltrav_t *trav, avltree_t *tree );
SV        *avltnext (pTHX_ avltrav_t *trav );
SV        *avltprev (pTHX_ avltrav_t *trav );

lib/AVLTree.pm  view on Meta::CPAN

  if($tree->remove($item)) {
    print "Item $item has been removed\n";
  } else {
    print "Item $item was not in the tree so it's not been removed\n";
  }
  
  printf "Size of tree is now: %d\n", $tree->size();

  ...

  # Suppose you want the tree to hold generic data items, e.g. hashrefs
  # which hold some data. We can deal with these by definying a custom
  # comparison function based on one of the attributes of these data items, 
  # e.g. 'id':
 
  sub compare {
    my ($i1, $i2) = @_;
    my ($id1, $id2) = ($i1->{id}, $i2->{id});

    croak "Cannot compare items based on id"
      unless defined $id1 and defined $id2;
  
    return $id1<$id2?-1:($id1>$id2)?1:0;
  }

  # Now can do the same as with numbers
  my $tree = AVLTree->new(\&compare);

  my $insert_ok = $tree->insert({ id => 10, data => 'ten' });
  croak "Could not insert item" unless $insert_ok;

  $insert_ok = $tree->insert({ id => 20, data => 'twenty' });
  
  ...

  my $id = 10;
  my $result = $tree->find({ id => $id });
  if($result) {
    printf "Item with id %d found\nData: %s\n", $id, $result->{data};
  } else {
    print "Item with id $id not found\n";
  }

  # forward tree traversal
  my $item = $tree->first();
  print "First item: ", $item, "\n";

  while($item = $tree->next()) {
    print $item, "\n";

t/03-leak.t  view on Meta::CPAN

} 'After inserting&querying';

no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_numbers);
  map { $tree->insert($_) } qw/10 20 30 40 50 25/;

  $tree->remove(1); # unsuccessful removal
  $tree->remove(10); # successful removal
} 'After inserting&removing';

# repeat with custom data
no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_custom);
} 'Empty tree';

no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_custom);
  map { $tree->insert($_) }
    ({ id => 10, data => 'ten' },
     { id => 20, data => 'twenty' },
     { id => 30, data => 'thirty' },
     { id => 40, data => 'forty' },
     { id => 50, data => 'fifty' },
     { id => 25, data => 'twneryfive' });
} 'Non-empty tree';

no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_custom);
  map { $tree->insert($_) }
    ({ id => 10, data => 'ten' },
     { id => 20, data => 'twenty' },
     { id => 30, data => 'thirty' },
     { id => 40, data => 'forty' },
     { id => 50, data => 'fifty' },
     { id => 25, data => 'twneryfive' });
  
  my $query = { id => 30 };
  my $result = $tree->find($query);
} 'After inserting&querying';

no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_custom);
  map { $tree->insert($_) }
    ({ id => 10, data => 'ten' },
     { id => 20, data => 'twenty' },
     { id => 30, data => 'thirty' },
     { id => 40, data => 'forty' },
     { id => 50, data => 'fifty' },
     { id => 25, data => 'twneryfive' });  

  $tree->remove({ id => 1 }); # unsuccessful removal
  $tree->remove({ id => 10 }); # successful removal
} 'After inserting&removing';

no_leaks_ok {
  my $tree = AVLTree->new(\&cmp_custom);
  map { $tree->insert($_) }
    ({ id => 10, data => 'ten' },
     { id => 20, data => 'twenty' },
     { id => 30, data => 'thirty' },
     { id => 40, data => 'forty' },
     { id => 50, data => 'fifty' },
     { id => 25, data => 'twneryfive' });  

  my $item = $tree->first;
  while ($item = $tree->next) {}
} 'Tree traversal';


diag( "Testing memory leaking AVLTree $AVLTree::VERSION, Perl $], $^X" );

 view all matches for this distribution
 view release on metacpan -  search on metacpan