Rename of Scalar -> Ref
[dbsrgits/DBM-Deep.git] / lib / DBM / Deep / Engine.pm
CommitLineData
a20d9a3f 1package DBM::Deep::Engine;
2
3use strict;
4
5use Fcntl qw( :DEFAULT :flock :seek );
6
8db25060 7##
8# Setup file and tag signatures. These should never change.
9##
10sub SIG_FILE () { 'DPDB' }
11sub SIG_INTERNAL () { 'i' }
12sub SIG_HASH () { 'H' }
13sub SIG_ARRAY () { 'A' }
d5d7c51d 14sub SIG_REF () { 'R' }
8db25060 15sub SIG_NULL () { 'N' }
16sub SIG_DATA () { 'D' }
17sub SIG_INDEX () { 'I' }
18sub SIG_BLIST () { 'B' }
19sub SIG_SIZE () { 1 }
20
612969fb 21sub precalc_sizes {
beac1dff 22 ##
23 # Precalculate index, bucket and bucket list sizes
24 ##
251dfd0e 25 my $self = shift;
1bf65be7 26
251dfd0e 27 $self->{index_size} = (2**8) * $self->{long_size};
28 $self->{bucket_size} = $self->{hash_size} + $self->{long_size};
29 $self->{bucket_list_size} = $self->{max_buckets} * $self->{bucket_size};
1bf65be7 30
251dfd0e 31 return 1;
1bf65be7 32}
33
34sub set_pack {
beac1dff 35 ##
36 # Set pack/unpack modes (see file header for more)
37 ##
251dfd0e 38 my $self = shift;
1bf65be7 39 my ($long_s, $long_p, $data_s, $data_p) = @_;
40
81d16922 41 ##
75be6413 42 # Set to 4 and 'N' for 32-bit offset tags (default). Theoretical limit of 4
43 # GB per file.
beac1dff 44 # (Perl must be compiled with largefile support for files > 2 GB)
81d16922 45 #
46 # Set to 8 and 'Q' for 64-bit offsets. Theoretical limit of 16 XB per file.
beac1dff 47 # (Perl must be compiled with largefile and 64-bit long support)
81d16922 48 ##
251dfd0e 49 $self->{long_size} = $long_s ? $long_s : 4;
50 $self->{long_pack} = $long_p ? $long_p : 'N';
1bf65be7 51
81d16922 52 ##
75be6413 53 # Set to 4 and 'N' for 32-bit data length prefixes. Limit of 4 GB for each
d5d7c51d 54 # key/value. Upgrading this is possible (see above) but probably not
55 # necessary. If you need more than 4 GB for a single key or value, this
56 # module is really not for you :-)
81d16922 57 ##
251dfd0e 58 $self->{data_size} = $data_s ? $data_s : 4;
59 $self->{data_pack} = $data_p ? $data_p : 'N';
1bf65be7 60
beac1dff 61 return $self->precalc_sizes();
1bf65be7 62}
63
64sub set_digest {
beac1dff 65 ##
66 # Set key digest function (default is MD5)
67 ##
251dfd0e 68 my $self = shift;
1bf65be7 69 my ($digest_func, $hash_size) = @_;
70
d0b74c17 71 $self->{digest} = $digest_func ? $digest_func : \&Digest::MD5::md5;
251dfd0e 72 $self->{hash_size} = $hash_size ? $hash_size : 16;
612969fb 73
beac1dff 74 return $self->precalc_sizes();
612969fb 75}
76
77sub new {
78 my $class = shift;
79 my ($args) = @_;
80
81 my $self = bless {
82 long_size => 4,
83 long_pack => 'N',
84 data_size => 4,
85 data_pack => 'N',
251dfd0e 86
612969fb 87 digest => \&Digest::MD5::md5,
88 hash_size => 16,
251dfd0e 89
81d16922 90 ##
d5d7c51d 91 # Maximum number of buckets per list before another level of indexing is
92 # done.
93 # Increase this value for slightly greater speed, but larger database
94 # files. DO NOT decrease this value below 16, due to risk of recursive
95 # reindex overrun.
81d16922 96 ##
612969fb 97 max_buckets => 16,
98 }, $class;
99
251dfd0e 100 $self->precalc_sizes;
612969fb 101
102 return $self;
1bf65be7 103}
104
70b55428 105sub setup_fh {
106 my $self = shift;
107 my ($obj) = @_;
108
109 $self->open( $obj ) if !defined $obj->_fh;
110
673464d9 111 #XXX We have to make sure we don't mess up when autoflush isn't turned on
70b55428 112 unless ( $obj->_root->{inode} ) {
113 my @stats = stat($obj->_fh);
114 $obj->_root->{inode} = $stats[1];
115 $obj->_root->{end} = $stats[7];
116 }
117
118 return 1;
119}
120
a20d9a3f 121sub open {
20f7b20c 122 ##
123 # Open a fh to the database, create if nonexistent.
124 # Make sure file signature matches DBM::Deep spec.
125 ##
a20d9a3f 126 my $self = shift;
70b55428 127 my ($obj) = @_;
a20d9a3f 128
3d1b8be9 129 if (defined($obj->_fh)) { $self->close_fh( $obj ); }
20f7b20c 130
673464d9 131 # Theoretically, adding O_BINARY should remove the need for the binmode
132 # Of course, testing it is going to be ... interesting.
133 my $flags = O_RDWR | O_CREAT | O_BINARY;
a20d9a3f 134
673464d9 135 my $fh;
d5d7c51d 136 my $filename = $obj->_root->{file};
137 sysopen( $fh, $filename, $flags )
138 or $obj->_throw_error("Cannot sysopen file '$filename': $!");
673464d9 139 $obj->_root->{fh} = $fh;
a20d9a3f 140
141 #XXX Can we remove this by using the right sysopen() flags?
142 # Maybe ... q.v. above
143 binmode $fh; # for win32
144
cd59cad8 145 if ($obj->_root->{autoflush}) {
a20d9a3f 146 my $old = select $fh;
147 $|=1;
148 select $old;
149 }
20f7b20c 150
cd59cad8 151 seek($fh, 0 + $obj->_root->{file_offset}, SEEK_SET);
a20d9a3f 152 my $signature;
8db25060 153 my $bytes_read = read( $fh, $signature, length(SIG_FILE));
20f7b20c 154
a20d9a3f 155 ##
156 # File is empty -- write signature and master index
157 ##
158 if (!$bytes_read) {
cd59cad8 159 seek($fh, 0 + $obj->_root->{file_offset}, SEEK_SET);
8db25060 160 print( $fh SIG_FILE);
d0b74c17 161
d5d7c51d 162 $self->create_tag(
163 $obj, $obj->_base_offset, $obj->_type,
164 chr(0) x $self->{index_size},
165 );
a20d9a3f 166
a20d9a3f 167 # Flush the filehandle
168 my $old_fh = select $fh;
169 my $old_af = $|; $| = 1; $| = $old_af;
170 select $old_fh;
171
a20d9a3f 172 return 1;
173 }
20f7b20c 174
a20d9a3f 175 ##
176 # Check signature was valid
177 ##
8db25060 178 unless ($signature eq SIG_FILE) {
3d1b8be9 179 $self->close_fh( $obj );
e5fc7e69 180 $obj->_throw_error("Signature not found -- file is not a Deep DB");
a20d9a3f 181 }
182
a20d9a3f 183 ##
184 # Get our type from master index signature
185 ##
e5fc7e69 186 my $tag = $self->load_tag($obj, $obj->_base_offset)
187 or $obj->_throw_error("Corrupted file, no master index record");
d0b74c17 188
e5fc7e69 189 unless ($obj->{type} eq $tag->{signature}) {
190 $obj->_throw_error("File type mismatch");
a20d9a3f 191 }
20f7b20c 192
d0b74c17 193#XXX We probably also want to store the hash algorithm name and not assume anything
194#XXX The cool thing would be to allow a different hashing algorithm at every level
195
a20d9a3f 196 return 1;
197}
198
3d1b8be9 199sub close_fh {
cd59cad8 200 my $self = shift;
a21f2d90 201 my ($obj) = @_;
cd59cad8 202
203 if ( my $fh = $obj->_root->{fh} ) {
204 close $fh;
205 }
206 $obj->_root->{fh} = undef;
207
208 return 1;
209}
210
d4b1166e 211sub create_tag {
20f7b20c 212 ##
213 # Given offset, signature and content, create tag and write to disk
214 ##
d4b1166e 215 my $self = shift;
20f7b20c 216 my ($obj, $offset, $sig, $content) = @_;
217 my $size = length($content);
218
d4b1166e 219 my $fh = $obj->_fh;
220
20f7b20c 221 seek($fh, $offset + $obj->_root->{file_offset}, SEEK_SET);
251dfd0e 222 print( $fh $sig . pack($self->{data_pack}, $size) . $content );
20f7b20c 223
224 if ($offset == $obj->_root->{end}) {
8db25060 225 $obj->_root->{end} += SIG_SIZE + $self->{data_size} + $size;
20f7b20c 226 }
227
228 return {
229 signature => $sig,
230 size => $size,
8db25060 231 offset => $offset + SIG_SIZE + $self->{data_size},
20f7b20c 232 content => $content
233 };
d4b1166e 234}
235
236sub load_tag {
20f7b20c 237 ##
238 # Given offset, load single tag and return signature, size and data
239 ##
d4b1166e 240 my $self = shift;
20f7b20c 241 my ($obj, $offset) = @_;
242
d4b1166e 243 my $fh = $obj->_fh;
244
20f7b20c 245 seek($fh, $offset + $obj->_root->{file_offset}, SEEK_SET);
e5fc7e69 246
75be6413 247 #XXX I'm not sure this check will work if autoflush isn't enabled ...
e5fc7e69 248 return if eof $fh;
20f7b20c 249
d4b1166e 250 my $b;
8db25060 251 read( $fh, $b, SIG_SIZE + $self->{data_size} );
251dfd0e 252 my ($sig, $size) = unpack( "A $self->{data_pack}", $b );
20f7b20c 253
254 my $buffer;
255 read( $fh, $buffer, $size);
256
257 return {
258 signature => $sig,
259 size => $size,
8db25060 260 offset => $offset + SIG_SIZE + $self->{data_size},
20f7b20c 261 content => $buffer
262 };
d4b1166e 263}
264
20f7b20c 265sub add_bucket {
266 ##
267 # Adds one key/value pair to bucket list, given offset, MD5 digest of key,
268 # plain (undigested) key and value.
269 ##
d4b1166e 270 my $self = shift;
20f7b20c 271 my ($obj, $tag, $md5, $plain_key, $value) = @_;
75be6413 272
20f7b20c 273 my $location = 0;
274 my $result = 2;
275
276 my $root = $obj->_root;
277
d5d7c51d 278 my $is_dbm_deep = eval {
279 local $SIG{'__DIE__'};
280 $value->isa( 'DBM::Deep' );
281 };
282
20f7b20c 283 my $internal_ref = $is_dbm_deep && ($value->_root eq $root);
284
285 my $fh = $obj->_fh;
286
386bab6c 287 my ($subloc, $offset) = $self->_find_in_buckets( $tag, $md5 );
75be6413 288
386bab6c 289 # Updating a known md5
290 if ( $subloc ) {
291 $result = 1;
20f7b20c 292
386bab6c 293 ##
d5d7c51d 294 # If value is a hash, array, or raw value with equal or less size, we
295 # can reuse the same content area of the database. Otherwise, we have
296 # to create a new content area at the EOF.
386bab6c 297 ##
298 my $actual_length;
299 if ( $internal_ref ) {
300 $actual_length = $self->{long_size};
301 }
302 else {
303 my $r = Scalar::Util::reftype( $value ) || '';
304 if ( $r eq 'HASH' || $r eq 'ARRAY' ) {
305 $actual_length = $self->{index_size};
306
307 # if autobless is enabled, must also take into consideration
308 # the class name, as it is stored along with key/value.
309 if ( $root->{autobless} ) {
310 my $value_class = Scalar::Util::blessed($value);
311 if ( defined $value_class && !$value->isa('DBM::Deep') ) {
312 $actual_length += length($value_class);
8db25060 313 }
75be6413 314 }
20f7b20c 315 }
386bab6c 316 else { $actual_length = length($value); }
75be6413 317 }
20f7b20c 318
d5d7c51d 319 seek($fh, $subloc + SIG_SIZE + $root->{file_offset}, SEEK_SET);
320 my $size;
321 read( $fh, $size, $self->{data_size});
322 $size = unpack($self->{data_pack}, $size);
323
386bab6c 324 if ($actual_length <= $size) {
325 $location = $subloc;
20f7b20c 326 }
75be6413 327 else {
328 $location = $root->{end};
386bab6c 329 seek(
330 $fh,
331 $tag->{offset} + $offset + $self->{hash_size} + $root->{file_offset},
332 SEEK_SET,
333 );
334 print( $fh pack($self->{long_pack}, $location) );
75be6413 335 }
75be6413 336 }
386bab6c 337 # Adding a new md5
338 elsif ( defined $offset ) {
386bab6c 339 $location = $root->{end};
340
341 seek( $fh, $tag->{offset} + $offset + $root->{file_offset}, SEEK_SET );
342 print( $fh $md5 . pack($self->{long_pack}, $location) );
343 }
344 # If bucket didn't fit into list, split into a new index level
345 else {
346 $self->split_index( $obj, $md5, $tag );
347
348 $location = $root->{end};
349 }
20f7b20c 350
d5d7c51d 351 $self->write_value( $obj, $location, $plain_key, $value );
352
353 return $result;
354}
355
356sub write_value {
357 my $self = shift;
358 my ($obj, $location, $key, $value) = @_;
359
360 my $fh = $obj->_fh;
361 my $root = $obj->_root;
362
363 my $is_dbm_deep = eval {
364 local $SIG{'__DIE__'};
365 $value->isa( 'DBM::Deep' );
366 };
367
368 my $internal_ref = $is_dbm_deep && ($value->_root eq $root);
369
370 seek($fh, $location + $root->{file_offset}, SEEK_SET);
371
20f7b20c 372 ##
d5d7c51d 373 # Write signature based on content type, set content length and write
374 # actual value.
20f7b20c 375 ##
d5d7c51d 376 my $r = Scalar::Util::reftype($value) || '';
377 my $content_length;
378 if ( $internal_ref ) {
379 print( $fh SIG_INTERNAL );
380 print( $fh pack($self->{data_pack}, $self->{long_size}) );
381 print( $fh pack($self->{long_pack}, $value->_base_offset) );
382 $content_length = $self->{long_size};
383 }
384 else {
385 if ($r eq 'HASH') {
386 print( $fh SIG_HASH );
387 print( $fh pack($self->{data_pack}, $self->{index_size}) . chr(0) x $self->{index_size} );
388 $content_length = $self->{index_size};
389 }
390 elsif ($r eq 'ARRAY') {
391 print( $fh SIG_ARRAY );
392 print( $fh pack($self->{data_pack}, $self->{index_size}) . chr(0) x $self->{index_size} );
393 $content_length = $self->{index_size};
394 }
395 elsif (!defined($value)) {
396 print( $fh SIG_NULL );
397 print( $fh pack($self->{data_pack}, 0) );
398 $content_length = 0;
20f7b20c 399 }
400 else {
d5d7c51d 401 print( $fh SIG_DATA );
402 print( $fh pack($self->{data_pack}, length($value)) . $value );
403 $content_length = length($value);
20f7b20c 404 }
d5d7c51d 405 }
20f7b20c 406
d5d7c51d 407 ##
408 # Plain key is stored AFTER value, as keys are typically fetched less often.
409 ##
410 print( $fh pack($self->{data_pack}, length($key)) . $key );
20f7b20c 411
d5d7c51d 412 ##
413 # If value is blessed, preserve class name
414 ##
415 if ( $root->{autobless} ) {
416 my $value_class = Scalar::Util::blessed($value);
417 if ( defined $value_class && !$value->isa( 'DBM::Deep' ) ) {
418 ##
419 # Blessed ref -- will restore later
420 ##
421 print( $fh chr(1) );
422 print( $fh pack($self->{data_pack}, length($value_class)) . $value_class );
423 $content_length += 1;
424 $content_length += $self->{data_size} + length($value_class);
20f7b20c 425 }
d5d7c51d 426 else {
427 print( $fh chr(0) );
428 $content_length += 1;
20f7b20c 429 }
d5d7c51d 430 }
20f7b20c 431
d5d7c51d 432 ##
433 # If this is a new content area, advance EOF counter
434 ##
435 if ($location == $root->{end}) {
436 $root->{end} += SIG_SIZE;
437 $root->{end} += $self->{data_size} + $content_length;
438 $root->{end} += $self->{data_size} + length($key);
439 }
440
441 ##
442 # If content is a hash or array, create new child DBM::Deep object and
443 # pass each key or element to it.
444 ##
445 if ( ! $internal_ref ) {
446 if ($r eq 'HASH') {
447 my $branch = DBM::Deep->new(
448 type => DBM::Deep->TYPE_HASH,
449 base_offset => $location,
450 root => $root,
451 );
452 foreach my $key (keys %{$value}) {
453 $branch->STORE( $key, $value->{$key} );
20f7b20c 454 }
d5d7c51d 455 }
456 elsif ($r eq 'ARRAY') {
457 my $branch = DBM::Deep->new(
458 type => DBM::Deep->TYPE_ARRAY,
459 base_offset => $location,
460 root => $root,
461 );
462 my $index = 0;
463 foreach my $element (@{$value}) {
464 $branch->STORE( $index, $element );
465 $index++;
20f7b20c 466 }
467 }
20f7b20c 468 }
d4b1166e 469
d5d7c51d 470 return 1;
d4b1166e 471}
472
75be6413 473sub split_index {
474 my $self = shift;
475 my ($obj, $md5, $tag) = @_;
476
477 my $fh = $obj->_fh;
478 my $root = $obj->_root;
479 my $keys = $tag->{content};
480
481 seek($fh, $tag->{ref_loc} + $root->{file_offset}, SEEK_SET);
482 print( $fh pack($self->{long_pack}, $root->{end}) );
483
484 my $index_tag = $self->create_tag(
485 $obj,
486 $root->{end},
8db25060 487 SIG_INDEX,
75be6413 488 chr(0) x $self->{index_size},
489 );
490
491 my @offsets = ();
492
493 $keys .= $md5 . pack($self->{long_pack}, 0);
494
495 BUCKET:
496 for (my $i = 0; $i <= $self->{max_buckets}; $i++) {
9cec1360 497 my ($key, $old_subloc) = $self->_get_key_subloc( $keys, $i );
75be6413 498
499 next BUCKET unless $key;
500
75be6413 501 my $num = ord(substr($key, $tag->{ch} + 1, 1));
502
503 if ($offsets[$num]) {
8db25060 504 my $offset = $offsets[$num] + SIG_SIZE + $self->{data_size};
75be6413 505 seek($fh, $offset + $root->{file_offset}, SEEK_SET);
506 my $subkeys;
507 read( $fh, $subkeys, $self->{bucket_list_size});
508
509 for (my $k=0; $k<$self->{max_buckets}; $k++) {
9cec1360 510 my ($temp, $subloc) = $self->_get_key_subloc( $subkeys, $k );
75be6413 511
512 if (!$subloc) {
513 seek($fh, $offset + ($k * $self->{bucket_size}) + $root->{file_offset}, SEEK_SET);
514 print( $fh $key . pack($self->{long_pack}, $old_subloc || $root->{end}) );
515 last;
516 }
517 } # k loop
518 }
519 else {
520 $offsets[$num] = $root->{end};
521 seek($fh, $index_tag->{offset} + ($num * $self->{long_size}) + $root->{file_offset}, SEEK_SET);
522 print( $fh pack($self->{long_pack}, $root->{end}) );
523
8db25060 524 my $blist_tag = $self->create_tag($obj, $root->{end}, SIG_BLIST, chr(0) x $self->{bucket_list_size});
75be6413 525
526 seek($fh, $blist_tag->{offset} + $root->{file_offset}, SEEK_SET);
527 print( $fh $key . pack($self->{long_pack}, $old_subloc || $root->{end}) );
528 }
529 } # i loop
530
531 return;
532}
533
8db25060 534sub read_from_loc {
535 my $self = shift;
536 my ($obj, $subloc) = @_;
537
538 my $fh = $obj->_fh;
539
540 ##
541 # Found match -- seek to offset and read signature
542 ##
543 my $signature;
544 seek($fh, $subloc + $obj->_root->{file_offset}, SEEK_SET);
545 read( $fh, $signature, SIG_SIZE);
546
547 ##
548 # If value is a hash or array, return new DBM::Deep object with correct offset
549 ##
550 if (($signature eq SIG_HASH) || ($signature eq SIG_ARRAY)) {
551 my $obj = DBM::Deep->new(
552 type => $signature,
553 base_offset => $subloc,
554 root => $obj->_root,
555 );
556
557 if ($obj->_root->{autobless}) {
558 ##
559 # Skip over value and plain key to see if object needs
560 # to be re-blessed
561 ##
562 seek($fh, $self->{data_size} + $self->{index_size}, SEEK_CUR);
563
564 my $size;
565 read( $fh, $size, $self->{data_size}); $size = unpack($self->{data_pack}, $size);
566 if ($size) { seek($fh, $size, SEEK_CUR); }
567
568 my $bless_bit;
569 read( $fh, $bless_bit, 1);
570 if (ord($bless_bit)) {
571 ##
572 # Yes, object needs to be re-blessed
573 ##
574 my $class_name;
575 read( $fh, $size, $self->{data_size}); $size = unpack($self->{data_pack}, $size);
576 if ($size) { read( $fh, $class_name, $size); }
577 if ($class_name) { $obj = bless( $obj, $class_name ); }
578 }
579 }
580
581 return $obj;
582 }
583 elsif ( $signature eq SIG_INTERNAL ) {
584 my $size;
585 read( $fh, $size, $self->{data_size});
586 $size = unpack($self->{data_pack}, $size);
587
588 if ( $size ) {
589 my $new_loc;
590 read( $fh, $new_loc, $size );
591 $new_loc = unpack( $self->{long_pack}, $new_loc );
592
593 return $self->read_from_loc( $obj, $new_loc );
594 }
595 else {
596 return;
597 }
598 }
599 ##
600 # Otherwise return actual value
601 ##
602 elsif ($signature eq SIG_DATA) {
603 my $size;
604 read( $fh, $size, $self->{data_size});
605 $size = unpack($self->{data_pack}, $size);
606
607 my $value = '';
608 if ($size) { read( $fh, $value, $size); }
609 return $value;
610 }
611
612 ##
613 # Key exists, but content is null
614 ##
615 return;
616}
617
9020ee8c 618sub get_bucket_value {
beac1dff 619 ##
620 # Fetch single value given tag and MD5 digested key.
621 ##
622 my $self = shift;
623 my ($obj, $tag, $md5) = @_;
9020ee8c 624
386bab6c 625 my ($subloc, $offset) = $self->_find_in_buckets( $tag, $md5 );
626 if ( $subloc ) {
8db25060 627 return $self->read_from_loc( $obj, $subloc );
386bab6c 628 }
beac1dff 629 return;
9020ee8c 630}
ab0e4957 631
632sub delete_bucket {
beac1dff 633 ##
634 # Delete single key/value pair given tag and MD5 digested key.
635 ##
636 my $self = shift;
637 my ($obj, $tag, $md5) = @_;
ab0e4957 638
386bab6c 639 my ($subloc, $offset) = $self->_find_in_buckets( $tag, $md5 );
640 if ( $subloc ) {
641 my $fh = $obj->_fh;
642 seek($fh, $tag->{offset} + $offset + $obj->_root->{file_offset}, SEEK_SET);
643 print( $fh substr($tag->{content}, $offset + $self->{bucket_size} ) );
251dfd0e 644 print( $fh chr(0) x $self->{bucket_size} );
d0b74c17 645
ab0e4957 646 return 1;
386bab6c 647 }
beac1dff 648 return;
ab0e4957 649}
650
912d50b1 651sub bucket_exists {
beac1dff 652 ##
653 # Check existence of single key given tag and MD5 digested key.
654 ##
655 my $self = shift;
656 my ($obj, $tag, $md5) = @_;
912d50b1 657
386bab6c 658 my ($subloc, $offset) = $self->_find_in_buckets( $tag, $md5 );
d5d7c51d 659 return $subloc && 1;
912d50b1 660}
661
6736c116 662sub find_bucket_list {
beac1dff 663 ##
664 # Locate offset for bucket list, given digested key
665 ##
666 my $self = shift;
d0b74c17 667 my ($obj, $md5, $args) = @_;
668 $args = {} unless $args;
669
beac1dff 670 ##
671 # Locate offset for bucket list using digest index system
672 ##
e5fc7e69 673 my $tag = $self->load_tag($obj, $obj->_base_offset)
d5d7c51d 674 or $obj->_throw_error( "INTERNAL ERROR - Cannot find tag" );
d0b74c17 675
e5fc7e69 676 my $ch = 0;
8db25060 677 while ($tag->{signature} ne SIG_BLIST) {
d0b74c17 678 my $num = ord substr($md5, $ch, 1);
679
680 my $ref_loc = $tag->{offset} + ($num * $self->{long_size});
681 $tag = $self->index_lookup( $obj, $tag, $num );
682
683 if (!$tag) {
d5d7c51d 684 return if ! $args->{create};
d0b74c17 685
d5d7c51d 686 my $fh = $obj->_fh;
687 seek($fh, $ref_loc + $obj->_root->{file_offset}, SEEK_SET);
688 print( $fh pack($self->{long_pack}, $obj->_root->{end}) );
d0b74c17 689
d5d7c51d 690 $tag = $self->create_tag(
691 $obj, $obj->_root->{end},
692 SIG_BLIST,
693 chr(0) x $self->{bucket_list_size},
694 );
695
696 $tag->{ref_loc} = $ref_loc;
697 $tag->{ch} = $ch;
698
699 last;
d0b74c17 700 }
701
702 $tag->{ch} = $ch;
703 $tag->{ref_loc} = $ref_loc;
704
beac1dff 705 $ch++;
706 }
d0b74c17 707
beac1dff 708 return $tag;
6736c116 709}
710
d0b74c17 711sub index_lookup {
712 ##
713 # Given index tag, lookup single entry in index and return .
714 ##
715 my $self = shift;
716 my ($obj, $tag, $index) = @_;
717
718 my $location = unpack(
719 $self->{long_pack},
720 substr(
721 $tag->{content},
722 $index * $self->{long_size},
723 $self->{long_size},
724 ),
725 );
726
727 if (!$location) { return; }
728
729 return $self->load_tag( $obj, $location );
730}
731
6736c116 732sub traverse_index {
beac1dff 733 ##
734 # Scan index and recursively step into deeper levels, looking for next key.
735 ##
6736c116 736 my $self = shift;
737 my ($obj, $offset, $ch, $force_return_next) = @_;
d0b74c17 738
beac1dff 739 my $tag = $self->load_tag($obj, $offset );
6736c116 740
741 my $fh = $obj->_fh;
d0b74c17 742
8db25060 743 if ($tag->{signature} ne SIG_BLIST) {
beac1dff 744 my $content = $tag->{content};
e5fc7e69 745 my $start = $obj->{return_next} ? 0 : ord(substr($obj->{prev_md5}, $ch, 1));
d0b74c17 746
d5d7c51d 747 for (my $idx = $start; $idx < (2**8); $idx++) {
e5fc7e69 748 my $subloc = unpack(
749 $self->{long_pack},
d5d7c51d 750 substr($content, $idx * $self->{long_size}, $self->{long_size}),
e5fc7e69 751 );
752
beac1dff 753 if ($subloc) {
e5fc7e69 754 my $result = $self->traverse_index(
755 $obj, $subloc, $ch + 1, $force_return_next,
756 );
757
beac1dff 758 if (defined($result)) { return $result; }
759 }
760 } # index loop
d0b74c17 761
beac1dff 762 $obj->{return_next} = 1;
763 } # tag is an index
d0b74c17 764
e5fc7e69 765 else {
beac1dff 766 my $keys = $tag->{content};
767 if ($force_return_next) { $obj->{return_next} = 1; }
d0b74c17 768
beac1dff 769 ##
770 # Iterate through buckets, looking for a key match
771 ##
8db25060 772 for (my $i = 0; $i < $self->{max_buckets}; $i++) {
9cec1360 773 my ($key, $subloc) = $self->_get_key_subloc( $keys, $i );
d0b74c17 774
8db25060 775 # End of bucket list -- return to outer loop
beac1dff 776 if (!$subloc) {
beac1dff 777 $obj->{return_next} = 1;
778 last;
779 }
8db25060 780 # Located previous key -- return next one found
beac1dff 781 elsif ($key eq $obj->{prev_md5}) {
beac1dff 782 $obj->{return_next} = 1;
783 next;
784 }
8db25060 785 # Seek to bucket location and skip over signature
beac1dff 786 elsif ($obj->{return_next}) {
8db25060 787 seek($fh, $subloc + $obj->_root->{file_offset}, SEEK_SET);
d0b74c17 788
beac1dff 789 # Skip over value to get to plain key
8db25060 790 my $sig;
791 read( $fh, $sig, SIG_SIZE );
792
beac1dff 793 my $size;
e5fc7e69 794 read( $fh, $size, $self->{data_size});
795 $size = unpack($self->{data_pack}, $size);
beac1dff 796 if ($size) { seek($fh, $size, SEEK_CUR); }
d0b74c17 797
beac1dff 798 # Read in plain key and return as scalar
beac1dff 799 my $plain_key;
e5fc7e69 800 read( $fh, $size, $self->{data_size});
801 $size = unpack($self->{data_pack}, $size);
beac1dff 802 if ($size) { read( $fh, $plain_key, $size); }
d0b74c17 803
beac1dff 804 return $plain_key;
805 }
8db25060 806 }
d0b74c17 807
beac1dff 808 $obj->{return_next} = 1;
809 } # tag is a bucket list
d0b74c17 810
beac1dff 811 return;
6736c116 812}
813
814sub get_next_key {
beac1dff 815 ##
816 # Locate next key, given digested previous one
817 ##
6736c116 818 my $self = shift;
819 my ($obj) = @_;
d0b74c17 820
beac1dff 821 $obj->{prev_md5} = $_[1] ? $_[1] : undef;
822 $obj->{return_next} = 0;
d0b74c17 823
beac1dff 824 ##
825 # If the previous key was not specifed, start at the top and
826 # return the first one found.
827 ##
828 if (!$obj->{prev_md5}) {
829 $obj->{prev_md5} = chr(0) x $self->{hash_size};
830 $obj->{return_next} = 1;
831 }
d0b74c17 832
beac1dff 833 return $self->traverse_index( $obj, $obj->_base_offset, 0 );
6736c116 834}
835
75be6413 836# Utilities
837
9cec1360 838sub _get_key_subloc {
75be6413 839 my $self = shift;
840 my ($keys, $idx) = @_;
841
9cec1360 842 my ($key, $subloc) = unpack(
843 "a$self->{hash_size} $self->{long_pack}",
75be6413 844 substr(
845 $keys,
9cec1360 846 ($idx * $self->{bucket_size}),
847 $self->{bucket_size},
75be6413 848 ),
849 );
850
9cec1360 851 return ($key, $subloc);
75be6413 852}
853
d608b06e 854sub _find_in_buckets {
855 my $self = shift;
856 my ($tag, $md5) = @_;
857
858 BUCKET:
859 for ( my $i = 0; $i < $self->{max_buckets}; $i++ ) {
860 my ($key, $subloc) = $self->_get_key_subloc( $tag->{content}, $i );
861
862 return ($subloc, $i * $self->{bucket_size}) unless $subloc;
863
864 next BUCKET if $key ne $md5;
865
866 return ($subloc, $i * $self->{bucket_size});
867 }
868
869 return;
870}
871
a20d9a3f 8721;
873__END__
d5d7c51d 874
875# This will be added in later, after more refactoring is done. This is an early
876# attempt at refactoring on the physical level instead of the virtual level.
877sub _read_at {
878 my $self = shift;
879 my ($obj, $spot, $amount, $unpack) = @_;
880
881 my $fh = $obj->_fh;
882 seek( $fh, $spot + $obj->_root->{file_offset}, SEEK_SET );
883
884 my $buffer;
885 my $bytes_read = read( $fh, $buffer, $amount );
886
887 if ( $unpack ) {
888 $buffer = unpack( $unpack, $buffer );
889 }
890
891 if ( wantarray ) {
892 return ($buffer, $bytes_read);
893 }
894 else {
895 return $buffer;
896 }
897}