lib/DBM/Deep/Engine.pm

   1 package DBM::Deep::Engine;
   2
   3 use 5.6.0;
   4
   5 use strict;
   6 use warnings;
   7
   8 use Fcntl qw( :DEFAULT :flock :seek );
   9
  10 ##
  11 # Setup file and tag signatures.  These should never change.
  12 ##
  13 sub SIG_FILE     () { 'DPDB' }
  14 sub SIG_HEADER   () { 'h'    }
  15 sub SIG_INTERNAL () { 'i'    }
  16 sub SIG_HASH     () { 'H'    }
  17 sub SIG_ARRAY    () { 'A'    }
  18 sub SIG_NULL     () { 'N'    }
  19 sub SIG_DATA     () { 'D'    }
  20 sub SIG_INDEX    () { 'I'    }
  21 sub SIG_BLIST    () { 'B'    }
  22 sub SIG_FREE     () { 'F'    }
  23 sub SIG_SIZE     () {  1     }
  24
  25 sub new {
  26     my $class = shift;
  27     my ($args) = @_;
  28
  29     my $self = bless {
  30         long_size   => 4,
  31         long_pack   => 'N',
  32         data_size   => 4,
  33         data_pack   => 'N',
  34
  35         digest      => \&Digest::MD5::md5,
  36         hash_size   => 16,
  37
  38         ##
  39         # Maximum number of buckets per list before another level of indexing is
  40         # done. Increase this value for slightly greater speed, but larger database
  41         # files. DO NOT decrease this value below 16, due to risk of recursive
  42         # reindex overrun.
  43         ##
  44         max_buckets => 16,
  45
  46         fileobj => undef,
  47     }, $class;
  48
  49     if ( defined $args->{pack_size} ) {
  50         if ( lc $args->{pack_size} eq 'small' ) {
  51             $args->{long_size} = 2;
  52             $args->{long_pack} = 'S';
  53         }
  54         elsif ( lc $args->{pack_size} eq 'medium' ) {
  55             $args->{long_size} = 4;
  56             $args->{long_pack} = 'N';
  57         }
  58         elsif ( lc $args->{pack_size} eq 'large' ) {
  59             $args->{long_size} = 8;
  60             $args->{long_pack} = 'Q';
  61         }
  62         else {
  63             die "Unknown pack_size value: '$args->{pack_size}'\n";
  64         }
  65     }
  66
  67     # Grab the parameters we want to use
  68     foreach my $param ( keys %$self ) {
  69         next unless exists $args->{$param};
  70         $self->{$param} = $args->{$param};
  71     }
  72
  73     if ( $self->{max_buckets} < 16 ) {
  74         warn "Floor of max_buckets is 16. Setting it to 16 from '$self->{max_buckets}'\n";
  75         $self->{max_buckets} = 16;
  76     }
  77
  78     return $self;
  79 }
  80
  81 sub _fileobj { return $_[0]{fileobj} }
  82 sub _fh      { return $_[0]->_fileobj->{fh} }
  83
  84 sub calculate_sizes {
  85     my $self = shift;
  86
  87     $self->{index_size}       = (2**8) * $self->{long_size};
  88     $self->{bucket_size}      = $self->{hash_size} + $self->{long_size} * 2;
  89     $self->{bucket_list_size} = $self->{max_buckets} * $self->{bucket_size};
  90
  91     return;
  92 }
  93
  94 sub write_file_header {
  95     my $self = shift;
  96
  97     my $fh = $self->_fh;
  98
  99     my $loc = $self->_request_space( length( SIG_FILE ) + 21 );
 100     seek($fh, $loc + $self->_fileobj->{file_offset}, SEEK_SET);
 101     print( $fh
 102         SIG_FILE,
 103         SIG_HEADER,
 104         pack('N', 1),  # header version
 105         pack('N', 12), # header size
 106         pack('N', 0),  # file version
 107         pack('S', $self->{long_size}),
 108         pack('A', $self->{long_pack}),
 109         pack('S', $self->{data_size}),
 110         pack('A', $self->{data_pack}),
 111         pack('S', $self->{max_buckets}),
 112     );
 113
 114     return;
 115 }
 116
 117 sub read_file_header {
 118     my $self = shift;
 119
 120     my $fh = $self->_fh;
 121
 122     seek($fh, 0 + $self->_fileobj->{file_offset}, SEEK_SET);
 123     my $buffer;
 124     my $bytes_read = read( $fh, $buffer, length(SIG_FILE) + 9 );
 125
 126     return unless $bytes_read;
 127
 128     my ($file_signature, $sig_header, $header_version, $size) = unpack(
 129         'A4 A N N', $buffer
 130     );
 131
 132     unless ( $file_signature eq SIG_FILE ) {
 133         $self->{fileobj}->close;
 134         $self->_throw_error( "Signature not found -- file is not a Deep DB" );
 135     }
 136
 137     unless ( $sig_header eq SIG_HEADER ) {
 138         $self->{fileobj}->close;
 139         $self->_throw_error( "Old file version found." );
 140     }
 141
 142     my $buffer2;
 143     $bytes_read += read( $fh, $buffer2, $size );
 144     my ($file_version, @values) = unpack( 'N S A S A S', $buffer2 );
 145     if ( @values < 5 || grep { !defined } @values ) {
 146         $self->{fileobj}->close;
 147         $self->_throw_error("Corrupted file - bad header");
 148     }
 149
 150     #XXX Add warnings if values weren't set right
 151     @{$self}{qw(long_size long_pack data_size data_pack max_buckets)} = @values;
 152
 153     return $bytes_read;
 154 }
 155
 156 sub setup_fh {
 157     my $self = shift;
 158     my ($obj) = @_;
 159
 160     my $fh = $self->_fh;
 161     flock $fh, LOCK_EX;
 162
 163     #XXX The duplication of calculate_sizes needs to go away
 164     unless ( $obj->{base_offset} ) {
 165         my $bytes_read = $self->read_file_header;
 166
 167         $self->calculate_sizes;
 168
 169         ##
 170         # File is empty -- write header and master index
 171         ##
 172         if (!$bytes_read) {
 173             $self->write_file_header;
 174
 175             $obj->{base_offset} = $self->_request_space( $self->tag_size( $self->{index_size} ) );
 176
 177             $self->write_tag(
 178                 $obj->_base_offset, $obj->_type,
 179                 chr(0)x$self->{index_size},
 180             );
 181
 182             # Flush the filehandle
 183             my $old_fh = select $fh;
 184             my $old_af = $|; $| = 1; $| = $old_af;
 185             select $old_fh;
 186         }
 187         else {
 188             $obj->{base_offset} = $bytes_read;
 189
 190             ##
 191             # Get our type from master index header
 192             ##
 193             my $tag = $self->load_tag($obj->_base_offset)
 194                 or $self->_throw_error("Corrupted file, no master index record");
 195
 196             unless ($obj->_type eq $tag->{signature}) {
 197                 $self->_throw_error("File type mismatch");
 198             }
 199         }
 200     }
 201     else {
 202         $self->calculate_sizes;
 203     }
 204
 205     #XXX We have to make sure we don't mess up when autoflush isn't turned on
 206     unless ( $self->_fileobj->{inode} ) {
 207         my @stats = stat($fh);
 208         $self->_fileobj->{inode} = $stats[1];
 209         $self->_fileobj->{end} = $stats[7];
 210     }
 211
 212     flock $fh, LOCK_UN;
 213
 214     return 1;
 215 }
 216
 217 sub tag_size {
 218     my $self = shift;
 219     my ($size) = @_;
 220     return SIG_SIZE + $self->{data_size} + $size;
 221 }
 222
 223 sub write_tag {
 224     ##
 225     # Given offset, signature and content, create tag and write to disk
 226     ##
 227     my $self = shift;
 228     my ($offset, $sig, $content) = @_;
 229     my $size = length( $content );
 230
 231     my $fh = $self->_fh;
 232
 233     if ( defined $offset ) {
 234         seek($fh, $offset + $self->_fileobj->{file_offset}, SEEK_SET);
 235     }
 236
 237     print( $fh $sig . pack($self->{data_pack}, $size) . $content );
 238
 239     return unless defined $offset;
 240
 241     return {
 242         signature => $sig,
 243         size => $size,
 244         offset => $offset + SIG_SIZE + $self->{data_size},
 245         content => $content
 246     };
 247 }
 248
 249 sub load_tag {
 250     ##
 251     # Given offset, load single tag and return signature, size and data
 252     ##
 253     my $self = shift;
 254     my ($offset) = @_;
 255
 256 #    print join(':',map{$_||''}caller(1)), $/;
 257
 258     my $fh = $self->_fh;
 259
 260     seek($fh, $offset + $self->_fileobj->{file_offset}, SEEK_SET);
 261
 262     #XXX I'm not sure this check will work if autoflush isn't enabled ...
 263     return if eof $fh;
 264
 265     my $b;
 266     read( $fh, $b, SIG_SIZE + $self->{data_size} );
 267     my ($sig, $size) = unpack( "A $self->{data_pack}", $b );
 268
 269     my $buffer;
 270     read( $fh, $buffer, $size);
 271
 272     return {
 273         signature => $sig,
 274         size => $size,
 275         offset => $offset + SIG_SIZE + $self->{data_size},
 276         content => $buffer
 277     };
 278 }
 279
 280 sub _get_dbm_object {
 281     my $item = shift;
 282
 283     my $obj = eval {
 284         local $SIG{__DIE__};
 285         if ($item->isa( 'DBM::Deep' )) {
 286             return $item;
 287         }
 288         return;
 289     };
 290     return $obj if $obj;
 291
 292     my $r = Scalar::Util::reftype( $item ) || '';
 293     if ( $r eq 'HASH' ) {
 294         my $obj = eval {
 295             local $SIG{__DIE__};
 296             my $obj = tied(%$item);
 297             if ($obj->isa( 'DBM::Deep' )) {
 298                 return $obj;
 299             }
 300             return;
 301         };
 302         return $obj if $obj;
 303     }
 304     elsif ( $r eq 'ARRAY' ) {
 305         my $obj = eval {
 306             local $SIG{__DIE__};
 307             my $obj = tied(@$item);
 308             if ($obj->isa( 'DBM::Deep' )) {
 309                 return $obj;
 310             }
 311             return;
 312         };
 313         return $obj if $obj;
 314     }
 315
 316     return;
 317 }
 318
 319 sub _length_needed {
 320     my $self = shift;
 321     my ($value, $key) = @_;
 322
 323     my $is_dbm_deep = eval {
 324         local $SIG{'__DIE__'};
 325         $value->isa( 'DBM::Deep' );
 326     };
 327
 328     my $len = SIG_SIZE + $self->{data_size}
 329             + $self->{data_size} + length( $key );
 330
 331     if ( $is_dbm_deep && $value->_fileobj eq $self->_fileobj ) {
 332         return $len + $self->{long_size};
 333     }
 334
 335     my $r = Scalar::Util::reftype( $value ) || '';
 336     if ( $self->_fileobj->{autobless} ) {
 337         # This is for the bit saying whether or not this thing is blessed.
 338         $len += 1;
 339     }
 340
 341     unless ( $r eq 'HASH' || $r eq 'ARRAY' ) {
 342         if ( defined $value ) {
 343             $len += length( $value );
 344         }
 345         return $len;
 346     }
 347
 348     $len += $self->{index_size};
 349
 350     # if autobless is enabled, must also take into consideration
 351     # the class name as it is stored after the key.
 352     if ( $self->_fileobj->{autobless} ) {
 353         my $c = Scalar::Util::blessed($value);
 354         if ( defined $c && !$is_dbm_deep ) {
 355             $len += $self->{data_size} + length($c);
 356         }
 357     }
 358
 359     return $len;
 360 }
 361
 362 sub add_bucket {
 363     ##
 364     # Adds one key/value pair to bucket list, given offset, MD5 digest of key,
 365     # plain (undigested) key and value.
 366     ##
 367     my $self = shift;
 368     my ($tag, $md5, $plain_key, $value) = @_;
 369
 370     # This verifies that only supported values will be stored.
 371     {
 372         my $r = Scalar::Util::reftype( $value );
 373         last if !defined $r;
 374
 375         last if $r eq 'HASH';
 376         last if $r eq 'ARRAY';
 377
 378         $self->_throw_error(
 379             "Storage of variables of type '$r' is not supported."
 380         );
 381     }
 382
 383     my $location = 0;
 384     my $result = 2;
 385
 386     my $root = $self->_fileobj;
 387     my $fh   = $self->_fh;
 388
 389     my $actual_length = $self->_length_needed( $value, $plain_key );
 390
 391     my ($subloc, $offset, $size) = $self->_find_in_buckets( $tag, $md5 );
 392
 393 #    $self->_release_space( $size, $subloc );
 394     # Updating a known md5
 395 #XXX This needs updating to use _release_space
 396     if ( $subloc ) {
 397         $result = 1;
 398
 399         if ($actual_length <= $size) {
 400             $location = $subloc;
 401         }
 402         else {
 403             $location = $self->_request_space( $actual_length );
 404             seek(
 405                 $fh,
 406                 $tag->{offset} + $offset
 407               + $self->{hash_size} + $root->{file_offset},
 408                 SEEK_SET,
 409             );
 410             print( $fh pack($self->{long_pack}, $location ) );
 411             print( $fh pack($self->{long_pack}, $actual_length ) );
 412         }
 413     }
 414     # Adding a new md5
 415     elsif ( defined $offset ) {
 416         $location = $self->_request_space( $actual_length );
 417
 418         seek( $fh, $tag->{offset} + $offset + $root->{file_offset}, SEEK_SET );
 419         print( $fh $md5 . pack($self->{long_pack}, $location ) );
 420         print( $fh pack($self->{long_pack}, $actual_length ) );
 421     }
 422     # If bucket didn't fit into list, split into a new index level
 423     # split_index() will do the _request_space() call
 424     else {
 425         $location = $self->split_index( $md5, $tag );
 426     }
 427
 428     $self->write_value( $location, $plain_key, $value );
 429
 430     return $result;
 431 }
 432
 433 sub write_value {
 434     my $self = shift;
 435     my ($location, $key, $value) = @_;
 436
 437     my $fh = $self->_fh;
 438     my $root = $self->_fileobj;
 439
 440     my $dbm_deep_obj = _get_dbm_object( $value );
 441     if ( $dbm_deep_obj && $dbm_deep_obj->_fileobj ne $self->_fileobj ) {
 442         $self->_throw_error( "Cannot cross-reference. Use export() instead" );
 443     }
 444
 445     seek($fh, $location + $root->{file_offset}, SEEK_SET);
 446
 447     ##
 448     # Write signature based on content type, set content length and write
 449     # actual value.
 450     ##
 451     my $r = Scalar::Util::reftype( $value ) || '';
 452     if ( $dbm_deep_obj ) {
 453         $self->write_tag( undef, SIG_INTERNAL,pack($self->{long_pack}, $dbm_deep_obj->_base_offset) );
 454     }
 455     elsif ($r eq 'HASH') {
 456         if ( !$dbm_deep_obj && tied %{$value} ) {
 457             $self->_throw_error( "Cannot store something that is tied" );
 458         }
 459         $self->write_tag( undef, SIG_HASH, chr(0)x$self->{index_size} );
 460     }
 461     elsif ($r eq 'ARRAY') {
 462         if ( !$dbm_deep_obj && tied @{$value} ) {
 463             $self->_throw_error( "Cannot store something that is tied" );
 464         }
 465         $self->write_tag( undef, SIG_ARRAY, chr(0)x$self->{index_size} );
 466     }
 467     elsif (!defined($value)) {
 468         $self->write_tag( undef, SIG_NULL, '' );
 469     }
 470     else {
 471         $self->write_tag( undef, SIG_DATA, $value );
 472     }
 473
 474     ##
 475     # Plain key is stored AFTER value, as keys are typically fetched less often.
 476     ##
 477     print( $fh pack($self->{data_pack}, length($key)) . $key );
 478
 479     # Internal references don't care about autobless
 480     return 1 if $dbm_deep_obj;
 481
 482     ##
 483     # If value is blessed, preserve class name
 484     ##
 485     if ( $root->{autobless} ) {
 486         my $c = Scalar::Util::blessed($value);
 487         if ( defined $c && !$dbm_deep_obj ) {
 488             print( $fh chr(1) );
 489             print( $fh pack($self->{data_pack}, length($c)) . $c );
 490         }
 491         else {
 492             print( $fh chr(0) );
 493         }
 494     }
 495
 496     ##
 497     # Tie the passed in reference so that changes to it are reflected in the
 498     # datafile. The use of $location as the base_offset will act as the
 499     # the linkage between parent and child.
 500     #
 501     # The overall assignment is a hack around the fact that just tying doesn't
 502     # store the values. This may not be the wrong thing to do.
 503     ##
 504     if ($r eq 'HASH') {
 505         my %x = %$value;
 506         tie %$value, 'DBM::Deep', {
 507             base_offset => $location,
 508             fileobj     => $root,
 509         };
 510         %$value = %x;
 511     }
 512     elsif ($r eq 'ARRAY') {
 513         my @x = @$value;
 514         tie @$value, 'DBM::Deep', {
 515             base_offset => $location,
 516             fileobj     => $root,
 517         };
 518         @$value = @x;
 519     }
 520
 521     return 1;
 522 }
 523
 524 sub split_index {
 525     my $self = shift;
 526     my ($md5, $tag) = @_;
 527
 528     my $fh = $self->_fh;
 529     my $root = $self->_fileobj;
 530
 531     my $loc = $self->_request_space(
 532         $self->tag_size( $self->{index_size} ),
 533     );
 534
 535     seek($fh, $tag->{ref_loc} + $root->{file_offset}, SEEK_SET);
 536     print( $fh pack($self->{long_pack}, $loc) );
 537
 538     my $index_tag = $self->write_tag(
 539         $loc, SIG_INDEX,
 540         chr(0)x$self->{index_size},
 541     );
 542
 543     my $newtag_loc = $self->_request_space(
 544         $self->tag_size( $self->{bucket_list_size} ),
 545     );
 546
 547     my $keys = $tag->{content}
 548              . $md5 . pack($self->{long_pack}, $newtag_loc)
 549                     . pack($self->{long_pack}, 0);
 550
 551     my @newloc = ();
 552     BUCKET:
 553     for (my $i = 0; $i <= $self->{max_buckets}; $i++) {
 554         my ($key, $old_subloc, $size) = $self->_get_key_subloc( $keys, $i );
 555
 556         die "[INTERNAL ERROR]: No key in split_index()\n" unless $key;
 557         die "[INTERNAL ERROR]: No subloc in split_index()\n" unless $old_subloc;
 558
 559         my $num = ord(substr($key, $tag->{ch} + 1, 1));
 560
 561         if ($newloc[$num]) {
 562             seek($fh, $newloc[$num] + $root->{file_offset}, SEEK_SET);
 563             my $subkeys;
 564             read( $fh, $subkeys, $self->{bucket_list_size});
 565
 566             # This is looking for the first empty spot
 567             my ($subloc, $offset, $size) = $self->_find_in_buckets(
 568                 { content => $subkeys }, '',
 569             );
 570
 571             seek($fh, $newloc[$num] + $offset + $root->{file_offset}, SEEK_SET);
 572             print( $fh $key . pack($self->{long_pack}, $old_subloc) );
 573
 574             next;
 575         }
 576
 577         seek($fh, $index_tag->{offset} + ($num * $self->{long_size}) + $root->{file_offset}, SEEK_SET);
 578
 579         my $loc = $self->_request_space(
 580             $self->tag_size( $self->{bucket_list_size} ),
 581         );
 582
 583         print( $fh pack($self->{long_pack}, $loc) );
 584
 585         my $blist_tag = $self->write_tag(
 586             $loc, SIG_BLIST,
 587             chr(0)x$self->{bucket_list_size},
 588         );
 589
 590         seek($fh, $blist_tag->{offset} + $root->{file_offset}, SEEK_SET);
 591         print( $fh $key . pack($self->{long_pack}, $old_subloc) );
 592
 593         $newloc[$num] = $blist_tag->{offset};
 594     }
 595
 596     $self->_release_space(
 597         $self->tag_size( $self->{bucket_list_size} ),
 598         $tag->{offset} - SIG_SIZE - $self->{data_size},
 599     );
 600
 601     return $newtag_loc;
 602 }
 603
 604 sub read_from_loc {
 605     my $self = shift;
 606     my ($subloc) = @_;
 607
 608     my $fh = $self->_fh;
 609
 610     ##
 611     # Found match -- seek to offset and read signature
 612     ##
 613     my $signature;
 614     seek($fh, $subloc + $self->_fileobj->{file_offset}, SEEK_SET);
 615     read( $fh, $signature, SIG_SIZE);
 616
 617     ##
 618     # If value is a hash or array, return new DBM::Deep object with correct offset
 619     ##
 620     if (($signature eq SIG_HASH) || ($signature eq SIG_ARRAY)) {
 621         my $new_obj = DBM::Deep->new({
 622             type => $signature,
 623             base_offset => $subloc,
 624             fileobj     => $self->_fileobj,
 625         });
 626
 627         if ($new_obj->_fileobj->{autobless}) {
 628             ##
 629             # Skip over value and plain key to see if object needs
 630             # to be re-blessed
 631             ##
 632             seek($fh, $self->{data_size} + $self->{index_size}, SEEK_CUR);
 633
 634             my $size;
 635             read( $fh, $size, $self->{data_size});
 636             $size = unpack($self->{data_pack}, $size);
 637             if ($size) { seek($fh, $size, SEEK_CUR); }
 638
 639             my $bless_bit;
 640             read( $fh, $bless_bit, 1);
 641             if (ord($bless_bit)) {
 642                 ##
 643                 # Yes, object needs to be re-blessed
 644                 ##
 645                 my $class_name;
 646                 read( $fh, $size, $self->{data_size});
 647                 $size = unpack($self->{data_pack}, $size);
 648                 if ($size) { read( $fh, $class_name, $size); }
 649                 if ($class_name) { $new_obj = bless( $new_obj, $class_name ); }
 650             }
 651         }
 652
 653         return $new_obj;
 654     }
 655     elsif ( $signature eq SIG_INTERNAL ) {
 656         my $size;
 657         read( $fh, $size, $self->{data_size});
 658         $size = unpack($self->{data_pack}, $size);
 659
 660         if ( $size ) {
 661             my $new_loc;
 662             read( $fh, $new_loc, $size );
 663             $new_loc = unpack( $self->{long_pack}, $new_loc );
 664
 665             return $self->read_from_loc( $new_loc );
 666         }
 667         else {
 668             return;
 669         }
 670     }
 671     ##
 672     # Otherwise return actual value
 673     ##
 674     elsif ( $signature eq SIG_DATA ) {
 675         my $size;
 676         read( $fh, $size, $self->{data_size});
 677         $size = unpack($self->{data_pack}, $size);
 678
 679         my $value = '';
 680         if ($size) { read( $fh, $value, $size); }
 681         return $value;
 682     }
 683
 684     ##
 685     # Key exists, but content is null
 686     ##
 687     return;
 688 }
 689
 690 sub get_bucket_value {
 691     ##
 692     # Fetch single value given tag and MD5 digested key.
 693     ##
 694     my $self = shift;
 695     my ($tag, $md5) = @_;
 696
 697     my ($subloc, $offset, $size) = $self->_find_in_buckets( $tag, $md5 );
 698     if ( $subloc ) {
 699         return $self->read_from_loc( $subloc );
 700     }
 701     return;
 702 }
 703
 704 sub delete_bucket {
 705     ##
 706     # Delete single key/value pair given tag and MD5 digested key.
 707     ##
 708     my $self = shift;
 709     my ($tag, $md5) = @_;
 710
 711     my ($subloc, $offset, $size) = $self->_find_in_buckets( $tag, $md5 );
 712 #XXX This needs _release_space()
 713     if ( $subloc ) {
 714         my $fh = $self->_fh;
 715         seek($fh, $tag->{offset} + $offset + $self->_fileobj->{file_offset}, SEEK_SET);
 716         print( $fh substr($tag->{content}, $offset + $self->{bucket_size} ) );
 717         print( $fh chr(0) x $self->{bucket_size} );
 718
 719         return 1;
 720     }
 721     return;
 722 }
 723
 724 sub bucket_exists {
 725     ##
 726     # Check existence of single key given tag and MD5 digested key.
 727     ##
 728     my $self = shift;
 729     my ($tag, $md5) = @_;
 730
 731     my ($subloc, $offset, $size) = $self->_find_in_buckets( $tag, $md5 );
 732     return $subloc && 1;
 733 }
 734
 735 sub find_bucket_list {
 736     ##
 737     # Locate offset for bucket list, given digested key
 738     ##
 739     my $self = shift;
 740     my ($offset, $md5, $args) = @_;
 741     $args = {} unless $args;
 742
 743     ##
 744     # Locate offset for bucket list using digest index system
 745     ##
 746     my $tag = $self->load_tag( $offset )
 747         or $self->_throw_error( "INTERNAL ERROR - Cannot find tag" );
 748
 749     my $ch = 0;
 750     while ($tag->{signature} ne SIG_BLIST) {
 751         my $num = ord substr($md5, $ch, 1);
 752
 753         my $ref_loc = $tag->{offset} + ($num * $self->{long_size});
 754         $tag = $self->index_lookup( $tag, $num );
 755
 756         if (!$tag) {
 757             return if !$args->{create};
 758
 759             my $loc = $self->_request_space(
 760                 $self->tag_size( $self->{bucket_list_size} ),
 761             );
 762
 763             my $fh = $self->_fh;
 764             seek($fh, $ref_loc + $self->_fileobj->{file_offset}, SEEK_SET);
 765             print( $fh pack($self->{long_pack}, $loc) );
 766
 767             $tag = $self->write_tag(
 768                 $loc, SIG_BLIST,
 769                 chr(0)x$self->{bucket_list_size},
 770             );
 771
 772             $tag->{ref_loc} = $ref_loc;
 773             $tag->{ch} = $ch;
 774
 775             last;
 776         }
 777
 778         $tag->{ch} = $ch++;
 779         $tag->{ref_loc} = $ref_loc;
 780     }
 781
 782     return $tag;
 783 }
 784
 785 sub index_lookup {
 786     ##
 787     # Given index tag, lookup single entry in index and return .
 788     ##
 789     my $self = shift;
 790     my ($tag, $index) = @_;
 791
 792     my $location = unpack(
 793         $self->{long_pack},
 794         substr(
 795             $tag->{content},
 796             $index * $self->{long_size},
 797             $self->{long_size},
 798         ),
 799     );
 800
 801     if (!$location) { return; }
 802
 803     return $self->load_tag( $location );
 804 }
 805
 806 sub traverse_index {
 807     ##
 808     # Scan index and recursively step into deeper levels, looking for next key.
 809     ##
 810     my $self = shift;
 811     my ($obj, $offset, $ch, $force_return_next) = @_;
 812
 813     my $tag = $self->load_tag( $offset );
 814
 815     my $fh = $self->_fh;
 816
 817     if ($tag->{signature} ne SIG_BLIST) {
 818         my $content = $tag->{content};
 819         my $start = $obj->{return_next} ? 0 : ord(substr($obj->{prev_md5}, $ch, 1));
 820
 821         for (my $idx = $start; $idx < (2**8); $idx++) {
 822             my $subloc = unpack(
 823                 $self->{long_pack},
 824                 substr(
 825                     $content,
 826                     $idx * $self->{long_size},
 827                     $self->{long_size},
 828                 ),
 829             );
 830
 831             if ($subloc) {
 832                 my $result = $self->traverse_index(
 833                     $obj, $subloc, $ch + 1, $force_return_next,
 834                 );
 835
 836                 if (defined($result)) { return $result; }
 837             }
 838         } # index loop
 839
 840         $obj->{return_next} = 1;
 841     } # tag is an index
 842
 843     else {
 844         my $keys = $tag->{content};
 845         if ($force_return_next) { $obj->{return_next} = 1; }
 846
 847         ##
 848         # Iterate through buckets, looking for a key match
 849         ##
 850         for (my $i = 0; $i < $self->{max_buckets}; $i++) {
 851             my ($key, $subloc) = $self->_get_key_subloc( $keys, $i );
 852
 853             # End of bucket list -- return to outer loop
 854             if (!$subloc) {
 855                 $obj->{return_next} = 1;
 856                 last;
 857             }
 858             # Located previous key -- return next one found
 859             elsif ($key eq $obj->{prev_md5}) {
 860                 $obj->{return_next} = 1;
 861                 next;
 862             }
 863             # Seek to bucket location and skip over signature
 864             elsif ($obj->{return_next}) {
 865                 seek($fh, $subloc + $self->_fileobj->{file_offset}, SEEK_SET);
 866
 867                 # Skip over value to get to plain key
 868                 my $sig;
 869                 read( $fh, $sig, SIG_SIZE );
 870
 871                 my $size;
 872                 read( $fh, $size, $self->{data_size});
 873                 $size = unpack($self->{data_pack}, $size);
 874                 if ($size) { seek($fh, $size, SEEK_CUR); }
 875
 876                 # Read in plain key and return as scalar
 877                 my $plain_key;
 878                 read( $fh, $size, $self->{data_size});
 879                 $size = unpack($self->{data_pack}, $size);
 880                 if ($size) { read( $fh, $plain_key, $size); }
 881
 882                 return $plain_key;
 883             }
 884         }
 885
 886         $obj->{return_next} = 1;
 887     } # tag is a bucket list
 888
 889     return;
 890 }
 891
 892 sub get_next_key {
 893     ##
 894     # Locate next key, given digested previous one
 895     ##
 896     my $self = shift;
 897     my ($obj) = @_;
 898
 899     $obj->{prev_md5} = $_[1] ? $_[1] : undef;
 900     $obj->{return_next} = 0;
 901
 902     ##
 903     # If the previous key was not specifed, start at the top and
 904     # return the first one found.
 905     ##
 906     if (!$obj->{prev_md5}) {
 907         $obj->{prev_md5} = chr(0) x $self->{hash_size};
 908         $obj->{return_next} = 1;
 909     }
 910
 911     return $self->traverse_index( $obj, $obj->_base_offset, 0 );
 912 }
 913
 914 # Utilities
 915
 916 sub _get_key_subloc {
 917     my $self = shift;
 918     my ($keys, $idx) = @_;
 919
 920     my ($key, $subloc, $size) = unpack(
 921         "a$self->{hash_size} $self->{long_pack} $self->{long_pack}",
 922         substr(
 923             $keys,
 924             ($idx * $self->{bucket_size}),
 925             $self->{bucket_size},
 926         ),
 927     );
 928
 929     return ($key, $subloc, $size);
 930 }
 931
 932 sub _find_in_buckets {
 933     my $self = shift;
 934     my ($tag, $md5) = @_;
 935
 936     BUCKET:
 937     for ( my $i = 0; $i < $self->{max_buckets}; $i++ ) {
 938         my ($key, $subloc, $size) = $self->_get_key_subloc(
 939             $tag->{content}, $i,
 940         );
 941
 942         return ($subloc, $i * $self->{bucket_size}, $size) unless $subloc;
 943
 944         next BUCKET if $key ne $md5;
 945
 946         return ($subloc, $i * $self->{bucket_size}, $size);
 947     }
 948
 949     return;
 950 }
 951
 952 sub _request_space {
 953     my $self = shift;
 954     my ($size) = @_;
 955
 956     my $loc = $self->_fileobj->{end};
 957     $self->_fileobj->{end} += $size;
 958
 959     return $loc;
 960 }
 961
 962 sub _release_space {
 963     my $self = shift;
 964     my ($size, $loc) = @_;
 965
 966     my $next_loc = 0;
 967
 968     my $fh = $self->_fh;
 969     seek( $fh, $loc + $self->_fileobj->{file_offset}, SEEK_SET );
 970     print( $fh SIG_FREE
 971         . pack($self->{long_pack}, $size )
 972         . pack($self->{long_pack}, $next_loc )
 973     );
 974
 975     return;
 976 }
 977
 978 sub _throw_error {
 979     die "DBM::Deep: $_[1]\n";
 980 }
 981
 982 1;
 983 __END__
 984
 985 # This will be added in later, after more refactoring is done. This is an early
 986 # attempt at refactoring on the physical level instead of the virtual level.
 987 sub _read_at {
 988     my $self = shift;
 989     my ($spot, $amount, $unpack) = @_;
 990
 991     my $fh = $self->_fh;
 992     seek( $fh, $spot + $self->_fileobj->{file_offset}, SEEK_SET );
 993
 994     my $buffer;
 995     my $bytes_read = read( $fh, $buffer, $amount );
 996
 997     if ( $unpack ) {
 998         $buffer = unpack( $unpack, $buffer );
 999     }
1000
1001     if ( wantarray ) {
1002         return ($buffer, $bytes_read);
1003     }
1004     else {
1005         return $buffer;
1006     }
1007 }
1008
1009 sub _print_at {
1010     my $self = shift;
1011     my ($spot, $data) = @_;
1012
1013     my $fh = $self->_fh;
1014     seek( $fh, $spot, SEEK_SET );
1015     print( $fh $data );
1016
1017     return;
1018 }
1019
1020 sub get_file_version {
1021     my $self = shift;
1022
1023     my $fh = $self->_fh;
1024
1025     seek( $fh, 13 + $self->_fileobj->{file_offset}, SEEK_SET );
1026     my $buffer;
1027     my $bytes_read = read( $fh, $buffer, 4 );
1028     unless ( $bytes_read == 4 ) {
1029         $self->_throw_error( "Cannot read file version" );
1030     }
1031
1032     return unpack( 'N', $buffer );
1033 }
1034
1035 sub write_file_version {
1036     my $self = shift;
1037     my ($new_version) = @_;
1038
1039     my $fh = $self->_fh;
1040
1041     seek( $fh, 13 + $self->_fileobj->{file_offset}, SEEK_SET );
1042     print( $fh pack( 'N', $new_version ) );
1043
1044     return;
1045 }
1046