4 use Carp ':DEFAULT', 'confess';
6 use Fcntl 'O_CREAT', 'O_RDWR', 'LOCK_EX', 'LOCK_SH', 'O_WRONLY', 'O_RDONLY';
7 sub O_ACCMODE () { O_RDONLY | O_RDWR | O_WRONLY }
11 my $DEFAULT_MEMORY_SIZE = 1<<21; # 2 megabytes
12 my $DEFAULT_AUTODEFER_THRESHHOLD = 3; # 3 records
13 my $DEFAULT_AUTODEFER_FILELEN_THRESHHOLD = 65536; # 16 disk blocksful
15 my %good_opt = map {$_ => 1, "-$_" => 1}
16 qw(memory dw_size mode recsep discipline
17 autodefer autochomp autodefer_threshhold concurrent);
21 croak "usage: tie \@array, $_[0], filename, [option => value]...";
23 my ($pack, $file, %opts) = @_;
25 # transform '-foo' keys into 'foo' keys
26 for my $key (keys %opts) {
27 unless ($good_opt{$key}) {
28 croak("$pack: Unrecognized option '$key'\n");
31 if ($key =~ s/^-+//) {
32 $opts{$key} = delete $opts{$okey};
36 if ($opts{concurrent}) {
37 croak("$pack: concurrent access not supported yet\n");
40 unless (defined $opts{memory}) {
41 # default is the larger of the default cache size and the
42 # deferred-write buffer size (if specified)
43 $opts{memory} = $DEFAULT_MEMORY_SIZE;
44 $opts{memory} = $opts{dw_size}
45 if defined $opts{dw_size} && $opts{dw_size} > $DEFAULT_MEMORY_SIZE;
48 $opts{dw_size} = $opts{memory} unless defined $opts{dw_size};
49 if ($opts{dw_size} > $opts{memory}) {
50 croak("$pack: dw_size may not be larger than total memory allocation\n");
52 # are we in deferred-write mode?
53 $opts{defer} = 0 unless defined $opts{defer};
54 $opts{deferred} = {}; # no records are presently deferred
55 $opts{deferred_s} = 0; # count of total bytes in ->{deferred}
56 $opts{deferred_max} = -1; # empty
58 # What's a good way to arrange that this class can be overridden?
59 $opts{cache} = Tie::File::Cache->new($opts{memory});
61 # autodeferment is enabled by default
62 $opts{autodefer} = 1 unless defined $opts{autodefer};
63 $opts{autodeferring} = 0; # but is not initially active
64 $opts{ad_history} = [];
65 $opts{autodefer_threshhold} = $DEFAULT_AUTODEFER_THRESHHOLD
66 unless defined $opts{autodefer_threshhold};
67 $opts{autodefer_filelen_threshhold} = $DEFAULT_AUTODEFER_FILELEN_THRESHHOLD
68 unless defined $opts{autodefer_filelen_threshhold};
71 $opts{filename} = $file;
72 unless (defined $opts{recsep}) {
73 $opts{recsep} = _default_recsep();
75 $opts{recseplen} = length($opts{recsep});
76 if ($opts{recseplen} == 0) {
77 croak "Empty record separator not supported by $pack";
80 $opts{autochomp} = 1 unless defined $opts{autochomp};
82 $opts{mode} = O_CREAT|O_RDWR unless defined $opts{mode};
83 $opts{rdonly} = (($opts{mode} & O_ACCMODE) == O_RDONLY);
84 $opts{sawlastrec} = undef;
88 if (UNIVERSAL::isa($file, 'GLOB')) {
89 # We use 1 here on the theory that some systems
90 # may not indicate failure if we use 0.
91 # MSWin32 does not indicate failure with 0, but I don't know if
92 # it will indicate failure with 1 or not.
93 unless (seek $file, 1, SEEK_SET) {
94 croak "$pack: your filehandle does not appear to be seekable";
96 seek $file, 0, SEEK_SET # put it back
97 $fh = $file; # setting binmode is the user's problem
99 croak "usage: tie \@array, $pack, filename, [option => value]...";
101 # $fh = \do { local *FH }; # XXX this is buggy
103 # perl 5.005 and earlier don't autovivify filehandles
105 $fh = Symbol::gensym();
107 sysopen $fh, $file, $opts{mode}, 0666 or return;
111 { my $ofh = select $fh; $| = 1; select $ofh } # autoflush on write
112 if (defined $opts{discipline} && $] >= 5.006) {
113 # This avoids a compile-time warning under 5.005
114 eval 'binmode($fh, $opts{discipline})';
115 croak $@ if $@ =~ /unknown discipline/i;
120 bless \%opts => $pack;
127 # check the defer buffer
128 $rec = $self->{deferred}{$n} if exists $self->{deferred}{$n};
129 $rec = $self->_fetch($n) unless defined $rec;
132 substr($rec, - $self->{recseplen}) = ""
133 if defined $rec && $self->{autochomp};
137 # Chomp many records in-place; return nothing useful
140 return unless $self->{autochomp};
141 if ($self->{autochomp}) {
144 substr($_, - $self->{recseplen}) = "";
149 # Chomp one record in-place; return modified record
151 my ($self, $rec) = @_;
152 return $rec unless $self->{autochomp};
153 return unless defined $rec;
154 substr($rec, - $self->{recseplen}) = "";
161 # check the record cache
162 { my $cached = $self->{cache}->lookup($n);
163 return $cached if defined $cached;
166 if ($#{$self->{offsets}} < $n) {
167 return if $self->{eof}; # request for record beyond end of file
168 my $o = $self->_fill_offsets_to($n);
169 # If it's still undefined, there is no such record, so return 'undef'
170 return unless defined $o;
173 my $fh = $self->{FH};
174 $self->_seek($n); # we can do this now that offsets is populated
175 my $rec = $self->_read_record;
177 # If we happen to have just read the first record, check to see if
178 # the length of the record matches what 'tell' says. If not, Tie::File
179 # won't work, and should drop dead.
181 # if ($n == 0 && defined($rec) && tell($self->{fh}) != length($rec)) {
182 # if (defined $self->{discipline}) {
183 # croak "I/O discipline $self->{discipline} not supported";
185 # croak "File encoding not supported";
189 $self->{cache}->insert($n, $rec) if defined $rec && not $self->{flushing};
194 my ($self, $n, $rec) = @_;
195 die "STORE called from _check_integrity!" if $DIAGNOSTIC;
197 $self->_fixrecs($rec);
199 if ($self->{autodefer}) {
200 $self->_annotate_ad_history($n);
203 return $self->_store_deferred($n, $rec) if $self->_is_deferring;
206 # We need this to decide whether the new record will fit
207 # It incidentally populates the offsets table
208 # Note we have to do this before we alter the cache
209 # 20020324 Wait, but this DOES alter the cache. TODO BUG?
210 my $oldrec = $self->_fetch($n);
212 if (not defined $oldrec) {
213 # We're storing a record beyond the end of the file
214 $self->_extend_file_to($n+1);
215 $oldrec = $self->{recsep};
217 # return if $oldrec eq $rec; # don't bother
218 my $len_diff = length($rec) - length($oldrec);
220 # length($oldrec) here is not consistent with text mode TODO XXX BUG
221 $self->_mtwrite($rec, $self->{offsets}[$n], length($oldrec));
222 $self->_oadjust([$n, 1, $rec]);
223 $self->{cache}->update($n, $rec);
226 sub _store_deferred {
227 my ($self, $n, $rec) = @_;
228 $self->{cache}->remove($n);
229 my $old_deferred = $self->{deferred}{$n};
231 if (defined $self->{deferred_max} && $n > $self->{deferred_max}) {
232 $self->{deferred_max} = $n;
234 $self->{deferred}{$n} = $rec;
236 my $len_diff = length($rec);
237 $len_diff -= length($old_deferred) if defined $old_deferred;
238 $self->{deferred_s} += $len_diff;
239 $self->{cache}->adj_limit(-$len_diff);
240 if ($self->{deferred_s} > $self->{dw_size}) {
242 } elsif ($self->_cache_too_full) {
247 # Remove a single record from the deferred-write buffer without writing it
248 # The record need not be present
249 sub _delete_deferred {
251 my $rec = delete $self->{deferred}{$n};
252 return unless defined $rec;
254 if (defined $self->{deferred_max}
255 && $n == $self->{deferred_max}) {
256 undef $self->{deferred_max};
259 $self->{deferred_s} -= length $rec;
260 $self->{cache}->adj_limit(length $rec);
265 my $n = $self->{eof} ? $#{$self->{offsets}} : $self->_fill_offsets;
267 my $top_deferred = $self->_defer_max;
268 $n = $top_deferred+1 if defined $top_deferred && $n < $top_deferred+1;
273 my ($self, $len) = @_;
275 if ($self->{autodefer}) {
276 $self->_annotate_ad_history('STORESIZE');
279 my $olen = $self->FETCHSIZE;
280 return if $len == $olen; # Woo-hoo!
284 if ($self->_is_deferring) {
285 for ($olen .. $len-1) {
286 $self->_store_deferred($_, $self->{recsep});
289 $self->_extend_file_to($len);
295 if ($self->_is_deferring) {
296 # TODO maybe replace this with map-plus-assignment?
297 for (grep $_ >= $len, keys %{$self->{deferred}}) {
298 $self->_delete_deferred($_);
300 $self->{deferred_max} = $len-1;
305 $#{$self->{offsets}} = $len;
306 # $self->{offsets}[0] = 0; # in case we just chopped this
308 $self->{cache}->remove(grep $_ >= $len, $self->{cache}->ckeys);
312 ### It should not be necessary to do FETCHSIZE
313 ### Just seek to the end of the file.
316 $self->SPLICE($self->FETCHSIZE, scalar(@_), @_);
319 # $self->FETCHSIZE; # because av.c takes care of this for me
324 my $size = $self->FETCHSIZE;
325 return if $size == 0;
326 # print STDERR "# POPPITY POP POP POP\n";
327 scalar $self->SPLICE($size-1, 1);
332 scalar $self->SPLICE(0, 1);
337 $self->SPLICE(0, 0, @_);
338 # $self->FETCHSIZE; # av.c takes care of this for me
344 if ($self->{autodefer}) {
345 $self->_annotate_ad_history('CLEAR');
350 $self->{cache}->set_limit($self->{memory});
351 $self->{cache}->empty;
352 @{$self->{offsets}} = (0);
353 %{$self->{deferred}}= ();
354 $self->{deferred_s} = 0;
355 $self->{deferred_max} = -1;
361 # No need to pre-extend anything in this case
362 return if $self->_is_deferring;
364 $self->_fill_offsets_to($n);
365 $self->_extend_file_to($n);
371 if ($self->{autodefer}) {
372 $self->_annotate_ad_history('DELETE');
375 my $lastrec = $self->FETCHSIZE-1;
376 my $rec = $self->FETCH($n);
377 $self->_delete_deferred($n) if $self->_is_deferring;
378 if ($n == $lastrec) {
381 $#{$self->{offsets}}--;
382 $self->{cache}->remove($n);
383 # perhaps in this case I should also remove trailing null records?
385 # Note that delete @a[-3..-1] deletes the records in the wrong order,
386 # so we only chop the very last one out of the file. We could repair this
387 # by tracking deleted records inside the object.
388 } elsif ($n < $lastrec) {
389 $self->STORE($n, "");
396 return 1 if exists $self->{deferred}{$n};
397 $n < $self->FETCHSIZE;
403 if ($self->{autodefer}) {
404 $self->_annotate_ad_history('SPLICE');
407 $self->_flush if $self->_is_deferring; # move this up?
409 $self->_chomp(my @a = $self->_splice(@_));
412 $self->_chomp1(scalar $self->_splice(@_));
418 $self->flush if $self->_is_deferring;
419 $self->{cache}->delink if defined $self->{cache}; # break circular link
420 if ($self->{fh} and $self->{ourfh}) {
421 delete $self->{ourfh};
422 close delete $self->{fh};
427 my ($self, $pos, $nrecs, @data) = @_;
430 $pos = 0 unless defined $pos;
432 # Deal with negative and other out-of-range positions
433 # Also set default for $nrecs
435 my $oldsize = $self->FETCHSIZE;
436 $nrecs = $oldsize unless defined $nrecs;
442 croak "Modification of non-creatable array value attempted, subscript $oldpos";
446 if ($pos > $oldsize) {
448 $pos = $oldsize; # This is what perl does for normal arrays
451 # The manual is very unclear here
453 $nrecs = $oldsize - $pos + $nrecs;
454 $nrecs = 0 if $nrecs < 0;
457 # nrecs is too big---it really means "until the end"
459 if ($nrecs + $pos > $oldsize) {
460 $nrecs = $oldsize - $pos;
464 $self->_fixrecs(@data);
465 my $data = join '', @data;
466 my $datalen = length $data;
469 # compute length of data being removed
470 for ($pos .. $pos+$nrecs-1) {
471 last unless defined $self->_fill_offsets_to($_);
472 my $rec = $self->_fetch($_);
473 last unless defined $rec;
476 # Why don't we just use length($rec) here?
477 # Because that record might have come from the cache. _splice
478 # might have been called to flush out the deferred-write records,
479 # and in this case length($rec) is the length of the record to be
480 # *written*, not the length of the actual record in the file. But
481 # the offsets are still true. 20020322
482 $oldlen += $self->{offsets}[$_+1] - $self->{offsets}[$_]
483 if defined $self->{offsets}[$_+1];
485 $self->_fill_offsets_to($pos+$nrecs);
488 $self->_mtwrite($data, $self->{offsets}[$pos], $oldlen);
489 # Adjust the offsets table
490 $self->_oadjust([$pos, $nrecs, @data]);
492 { # Take this read cache stuff out into a separate function
493 # You made a half-attempt to put it into _oadjust.
494 # Finish something like that up eventually.
495 # STORE also needs to do something similarish
497 # update the read cache, part 1
499 for ($pos .. $pos+$nrecs-1) {
500 my $new = $data[$_-$pos];
502 $self->{cache}->update($_, $new);
504 $self->{cache}->remove($_);
508 # update the read cache, part 2
509 # moved records - records past the site of the change
510 # need to be renumbered
511 # Maybe merge this with the previous block?
513 my @oldkeys = grep $_ >= $pos + $nrecs, $self->{cache}->ckeys;
514 my @newkeys = map $_-$nrecs+@data, @oldkeys;
515 $self->{cache}->rekey(\@oldkeys, \@newkeys);
518 # Now there might be too much data in the cache, if we spliced out
519 # some short records and spliced in some long ones. If so, flush
524 # Yes, the return value of 'splice' *is* actually this complicated
525 wantarray ? @result : @result ? $result[-1] : undef;
529 # write data into the file
530 # $data is the data to be written.
531 # it should be written at position $pos, and should overwrite
532 # exactly $len of the following bytes.
533 # Note that if length($data) > $len, the subsequent bytes will have to
534 # be moved up, and if length($data) < $len, they will have to
537 my ($self, $data, $pos, $len) = @_;
539 unless (defined $pos) {
540 die "\$pos was undefined in _twrite";
543 my $len_diff = length($data) - $len;
545 if ($len_diff == 0) { # Woo-hoo!
546 my $fh = $self->{fh};
548 $self->_write_record($data);
549 return; # well, that was easy.
552 # the two records are of different lengths
553 # our strategy here: rewrite the tail of the file,
554 # reading ahead one buffer at a time
555 # $bufsize is required to be at least as large as the data we're overwriting
556 my $bufsize = _bufsize($len_diff);
557 my ($writepos, $readpos) = ($pos, $pos+$len);
561 # Seems like there ought to be a way to avoid the repeated code
562 # and the special case here. The read(1) is also a little weird.
565 $self->_seekb($readpos);
566 my $br = read $self->{fh}, $next_block, $bufsize;
567 $more_data = read $self->{fh}, my($dummy), 1;
568 $self->_seekb($writepos);
569 $self->_write_record($data);
571 $writepos += length $data;
574 $self->_seekb($writepos);
575 $self->_write_record($next_block);
577 # There might be leftover data at the end of the file
578 $self->_chop_file if $len_diff < 0;
582 # Insert text D at position S.
583 # Let C = E-S-|D|. If C < 0; die.
584 # Data in [S,S+C) is copied to [S+D,S+D+C) = [S+D,E).
585 # Data in [S+C = E-D, E) is returned. Data in [E, oo) is untouched.
587 # In a later version, don't read the entire intervening area into
588 # memory at once; do the copying block by block.
591 my ($D, $s, $e) = @_;
594 local *FH = $self->{fh};
595 confess "Not enough space to insert $d bytes between $s and $e"
597 confess "[$s,$e) is an invalid insertion range" if $e < $s;
600 read FH, my $buf, $e-$s;
602 $D .= substr($buf, 0, $c, "");
605 $self->_write_record($D);
610 # Like _twrite, but the data-pos-len triple may be repeated; you may
611 # write several chunks. All the writing will be done in
612 # one pass. Chunks SHALL be in ascending order and SHALL NOT overlap.
619 or die "Arguments to _mtwrite did not come in groups of three";
622 my ($data, $pos, $len) = splice @_, 0, 3;
623 my $end = $pos + $len; # The OLD end of the segment to be replaced
624 $data = $unwritten . $data;
625 $delta -= length($unwritten);
627 $pos += $delta; # This is where the data goes now
628 my $dlen = length $data;
630 if ($len >= $dlen) { # the data will fit
631 $self->_write_record($data);
632 $delta += ($dlen - $len); # everything following moves down by this much
633 $data = ""; # All the data in the buffer has been written
635 my $writable = substr($data, 0, $len - $delta, "");
636 $self->_write_record($writable);
637 $delta += ($dlen - $len); # everything following moves down by this much
640 # At this point we've written some but maybe not all of the data.
641 # There might be a gap to close up, or $data might still contain a
642 # bunch of unwritten data that didn't fit.
643 my $ndlen = length $data;
645 $self->_write_record($data);
646 } elsif ($delta < 0) {
647 # upcopy (close up gap)
649 $self->_upcopy($end, $end + $delta, $_[1] - $end);
651 $self->_upcopy($end, $end + $delta);
654 # downcopy (insert data that didn't fit; replace this data in memory
655 # with _later_ data that doesn't fit)
657 $unwritten = $self->_downcopy($data, $end, $_[1] - $end);
659 # Make the file longer to accomodate the last segment that doesn'
660 $unwritten = $self->_downcopy($data, $end);
666 # Copy block of data of length $len from position $spos to position $dpos
667 # $dpos must be <= $spos
669 # If $len is undefined, go all the way to the end of the file
670 # and then truncate it ($spos - $dpos bytes will be removed)
672 my $blocksize = 8192;
673 my ($self, $spos, $dpos, $len) = @_;
675 die "source ($spos) was upstream of destination ($dpos) in _upcopy";
676 } elsif ($dpos == $spos) {
680 while (! defined ($len) || $len > 0) {
681 my $readsize = ! defined($len) ? $blocksize
682 : $len > $blocksize ? $blocksize
685 my $fh = $self->{fh};
686 $self->_seekb($spos);
687 my $bytes_read = read $fh, my($data), $readsize;
688 $self->_seekb($dpos);
693 $self->_write_record($data);
694 $spos += $bytes_read;
695 $dpos += $bytes_read;
696 $len -= $bytes_read if defined $len;
700 # Write $data into a block of length $len at position $pos,
701 # moving everything in the block forwards to make room.
702 # Instead of writing the last length($data) bytes from the block
703 # (because there isn't room for them any longer) return them.
705 # Undefined $len means 'until the end of the file'
707 my $blocksize = 8192;
708 my ($self, $data, $pos, $len) = @_;
709 my $fh = $self->{fh};
711 while (! defined $len || $len > 0) {
712 my $readsize = ! defined($len) ? $blocksize
713 : $len > $blocksize? $blocksize : $len;
715 read $fh, my($old), $readsize;
716 my $last_read_was_short = length($old) < $readsize;
719 if ($last_read_was_short) {
720 # If last read was short, then $data now contains the entire rest
721 # of the file, so there's no need to write only one block of it
725 $writable = substr($data, 0, $readsize, "");
727 last if $writable eq "";
729 $self->_write_record($writable);
730 $len -= $readsize if defined $len;
736 # Adjust the object data structures following an '_mtwrite'
738 # [$pos, $nrecs, @length] items
739 # indicating that $nrecs records were removed at $recpos (a record offset)
740 # and replaced with records of length @length...
741 # Arguments guarantee that $recpos is strictly increasing.
751 my ($pos, $nrecs, @data) = @$_;
754 # Adjust the offsets of the records after the previous batch up
755 # to the first new one of this batch
756 for my $i ($prev_end+2 .. $pos - 1) {
757 $self->{offsets}[$i] += $delta;
758 $newkey{$i} = $i + $delta_recs;
761 $prev_end = $pos + @data - 1; # last record moved on this pass
763 # Remove the offsets for the removed records;
764 # replace with the offsets for the inserted records
765 my @newoff = ($self->{offsets}[$pos] + $delta);
766 for my $i (0 .. $#data) {
767 my $newlen = length $data[$i];
768 push @newoff, $newoff[$i] + $newlen;
772 for my $i ($pos .. $pos+$nrecs-1) {
773 last if $i+1 > $#{$self->{offsets}};
774 my $oldlen = $self->{offsets}[$i+1] - $self->{offsets}[$i];
778 # # also this data has changed, so update it in the cache
779 # for (0 .. $#data) {
780 # $self->{cache}->update($pos + $_, $data[$_]);
783 # my @oldkeys = grep $_ >= $pos + @data, $self->{cache}->ckeys;
784 # my @newkeys = map $_ + $delta_recs, @oldkeys;
785 # $self->{cache}->rekey(\@oldkeys, \@newkeys);
788 # replace old offsets with new
789 splice @{$self->{offsets}}, $pos, $nrecs+1, @newoff;
790 # What if we just spliced out the end of the offsets table?
791 # shouldn't we clear $self->{eof}? Test for this XXX BUG TODO
793 $delta_recs += @data - $nrecs; # net change in total number of records
796 # The trailing records at the very end of the file
798 for my $i ($prev_end+2 .. $#{$self->{offsets}}) {
799 $self->{offsets}[$i] += $delta;
803 # If we scrubbed out all known offsets, regenerate the trivial table
804 # that knows that the file does indeed start at 0.
805 $self->{offsets}[0] = 0 unless @{$self->{offsets}};
806 # If the file got longer, the offsets table is no longer complete
807 # $self->{eof} = 0 if $delta_recs > 0;
809 # Now there might be too much data in the cache, if we spliced out
810 # some short records and spliced in some long ones. If so, flush
815 # If a record does not already end with the appropriate terminator
816 # string, append one.
820 $_ = "" unless defined $_;
821 $_ .= $self->{recsep}
822 unless substr($_, - $self->{recseplen}) eq $self->{recsep};
827 ################################################################
829 # Basic read, write, and seek
832 # seek to the beginning of record #$n
833 # Assumes that the offsets table is already correctly populated
835 # Note that $n=-1 has a special meaning here: It means the start of
836 # the last known record; this may or may not be the very last record
837 # in the file, depending on whether the offsets table is fully populated.
841 my $o = $self->{offsets}[$n];
843 or confess("logic error: undefined offset for record $n");
844 seek $self->{fh}, $o, SEEK_SET
845 or confess "Couldn't seek filehandle: $!"; # "Should never happen."
848 # seek to byte $b in the file
851 seek $self->{fh}, $b, SEEK_SET
852 or die "Couldn't seek filehandle: $!"; # "Should never happen."
855 # populate the offsets table up to the beginning of record $n
856 # return the offset of record $n
857 sub _fill_offsets_to {
860 return $self->{offsets}[$n] if $self->{eof};
862 my $fh = $self->{fh};
863 local *OFF = $self->{offsets};
866 until ($#OFF >= $n) {
867 $self->_seek(-1); # tricky -- see comment at _seek
868 $rec = $self->_read_record;
870 push @OFF, int(tell $fh); # Tels says that int() saves memory here
873 return; # It turns out there is no such record
877 # we have now read all the records up to record n-1,
878 # so we can return the offset of record n
885 my $fh = $self->{fh};
886 local *OFF = $self->{offsets};
888 $self->_seek(-1); # tricky -- see comment at _seek
890 # Tels says that inlining read_record() would make this loop
891 # five times faster. 20030508
892 while ( defined $self->_read_record()) {
893 # int() saves us memory here
894 push @OFF, int(tell $fh);
901 # assumes that $rec is already suitably terminated
903 my ($self, $rec) = @_;
904 my $fh = $self->{fh};
907 or die "Couldn't write record: $!"; # "Should never happen."
908 # $self->{_written} += length($rec);
914 { local $/ = $self->{recsep};
915 my $fh = $self->{fh};
918 return unless defined $rec;
919 if (substr($rec, -$self->{recseplen}) ne $self->{recsep}) {
920 # improperly terminated final record --- quietly fix it.
921 # my $ac = substr($rec, -$self->{recseplen});
923 $self->{sawlastrec} = 1;
924 unless ($self->{rdonly}) {
926 my $fh = $self->{fh};
927 print $fh $self->{recsep};
929 $rec .= $self->{recsep};
931 # $self->{_read} += length($rec) if defined $rec;
937 @{$self}{'_read', '_written'};
940 ################################################################
942 # Read cache management
946 $self->{cache}->reduce_size_to($self->{memory} - $self->{deferred_s});
949 sub _cache_too_full {
951 $self->{cache}->bytes + $self->{deferred_s} >= $self->{memory};
954 ################################################################
956 # File custodial services
960 # We have read to the end of the file and have the offsets table
961 # entirely populated. Now we need to write a new record beyond
962 # the end of the file. We prepare for this by writing
963 # empty records into the file up to the position we want
965 # assumes that the offsets table already contains the offset of record $n,
966 # if it exists, and extends to the end of the file if not.
967 sub _extend_file_to {
969 $self->_seek(-1); # position after the end of the last record
970 my $pos = $self->{offsets}[-1];
972 # the offsets table has one entry more than the total number of records
973 my $extras = $n - $#{$self->{offsets}};
975 # Todo : just use $self->{recsep} x $extras here?
976 while ($extras-- > 0) {
977 $self->_write_record($self->{recsep});
978 push @{$self->{offsets}}, int(tell $self->{fh});
982 # Truncate the file at the current position
985 truncate $self->{fh}, tell($self->{fh});
989 # compute the size of a buffer suitable for moving
990 # all the data in a file forward $n bytes
991 # ($n may be negative)
992 # The result should be at least $n.
995 return 8192 if $n <= 0;
997 $b += 8192 if $n & 8191;
1001 ################################################################
1003 # Miscellaneous public methods
1008 my ($self, $op) = @_;
1010 my $pack = ref $self;
1011 croak "Usage: $pack\->flock([OPERATION])";
1013 my $fh = $self->{fh};
1014 $op = LOCK_EX unless defined $op;
1015 my $locked = flock $fh, $op;
1017 if ($locked && ($op & (LOCK_EX | LOCK_SH))) {
1018 # If you're locking the file, then presumably it's because
1019 # there might have been a write access by another process.
1020 # In that case, the read cache contents and the offsets table
1021 # might be invalid, so discard them. 20030508
1022 $self->{offsets} = [0];
1023 $self->{cache}->empty;
1029 # Get/set autochomp option
1033 my $old = $self->{autochomp};
1034 $self->{autochomp} = shift;
1041 # Get offset table entries; returns offset of nth record
1043 my ($self, $n) = @_;
1045 if ($#{$self->{offsets}} < $n) {
1046 return if $self->{eof}; # request for record beyond the end of file
1047 my $o = $self->_fill_offsets_to($n);
1048 # If it's still undefined, there is no such record, so return 'undef'
1049 return unless defined $o;
1052 $self->{offsets}[$n];
1055 sub discard_offsets {
1057 $self->{offsets} = [0];
1060 ################################################################
1062 # Matters related to deferred writing
1068 $self->_stop_autodeferring;
1069 @{$self->{ad_history}} = ();
1073 # Flush deferred writes
1075 # This could be better optimized to write the file in one pass, instead
1076 # of one pass per block of records. But that will require modifications
1077 # to _twrite, so I should have a good _twrite test suite first.
1087 my @writable = sort {$a<=>$b} (keys %{$self->{deferred}});
1090 # gather all consecutive records from the front of @writable
1091 my $first_rec = shift @writable;
1092 my $last_rec = $first_rec+1;
1093 ++$last_rec, shift @writable while @writable && $last_rec == $writable[0];
1095 $self->_fill_offsets_to($last_rec);
1096 $self->_extend_file_to($last_rec);
1097 $self->_splice($first_rec, $last_rec-$first_rec+1,
1098 @{$self->{deferred}}{$first_rec .. $last_rec});
1101 $self->_discard; # clear out defered-write-cache
1106 my @writable = sort {$a<=>$b} (keys %{$self->{deferred}});
1111 # gather all consecutive records from the front of @writable
1112 my $first_rec = shift @writable;
1113 my $last_rec = $first_rec+1;
1114 ++$last_rec, shift @writable while @writable && $last_rec == $writable[0];
1116 my $end = $self->_fill_offsets_to($last_rec+1);
1117 if (not defined $end) {
1118 $self->_extend_file_to($last_rec);
1119 $end = $self->{offsets}[$last_rec];
1121 my ($start) = $self->{offsets}[$first_rec];
1123 join("", @{$self->{deferred}}{$first_rec .. $last_rec}), # data
1125 $end-$start; # length
1126 push @adjust, [$first_rec, # starting at this position...
1127 $last_rec-$first_rec+1, # this many records...
1128 # are replaced with these...
1129 @{$self->{deferred}}{$first_rec .. $last_rec},
1133 $self->_mtwrite(@args); # write multiple record groups
1134 $self->_discard; # clear out defered-write-cache
1135 $self->_oadjust(@adjust);
1138 # Discard deferred writes and disable future deferred writes
1145 # Discard deferred writes, but retain old deferred writing mode
1148 %{$self->{deferred}} = ();
1149 $self->{deferred_s} = 0;
1150 $self->{deferred_max} = -1;
1151 $self->{cache}->set_limit($self->{memory});
1154 # Deferred writing is enabled, either explicitly ($self->{defer})
1155 # or automatically ($self->{autodeferring})
1158 $self->{defer} || $self->{autodeferring};
1161 # The largest record number of any deferred record
1164 return $self->{deferred_max} if defined $self->{deferred_max};
1166 for my $key (keys %{$self->{deferred}}) {
1167 $max = $key if $key > $max;
1169 $self->{deferred_max} = $max;
1173 ################################################################
1175 # Matters related to autodeferment
1178 # Get/set autodefer option
1182 my $old = $self->{autodefer};
1183 $self->{autodefer} = shift;
1185 $self->_stop_autodeferring;
1186 @{$self->{ad_history}} = ();
1194 # The user is trying to store record #$n Record that in the history,
1195 # and then enable (or disable) autodeferment if that seems useful.
1196 # Note that it's OK for $n to be a non-number, as long as the function
1197 # is prepared to deal with that. Nobody else looks at the ad_history.
1199 # Now, what does the ad_history mean, and what is this function doing?
1200 # Essentially, the idea is to enable autodeferring when we see that the
1201 # user has made three consecutive STORE calls to three consecutive records.
1202 # ("Three" is actually ->{autodefer_threshhold}.)
1203 # A STORE call for record #$n inserts $n into the autodefer history,
1204 # and if the history contains three consecutive records, we enable
1205 # autodeferment. An ad_history of [X, Y] means that the most recent
1206 # STOREs were for records X, X+1, ..., Y, in that order.
1208 # Inserting a nonconsecutive number erases the history and starts over.
1210 # Performing a special operation like SPLICE erases the history.
1212 # There's one special case: CLEAR means that CLEAR was just called.
1213 # In this case, we prime the history with [-2, -1] so that if the next
1214 # write is for record 0, autodeferring goes on immediately. This is for
1215 # the common special case of "@a = (...)".
1217 sub _annotate_ad_history {
1218 my ($self, $n) = @_;
1219 return unless $self->{autodefer}; # feature is disabled
1220 return if $self->{defer}; # already in explicit defer mode
1221 return unless $self->{offsets}[-1] >= $self->{autodefer_filelen_threshhold};
1223 local *H = $self->{ad_history};
1224 if ($n eq 'CLEAR') {
1225 @H = (-2, -1); # prime the history with fake records
1226 $self->_stop_autodeferring;
1227 } elsif ($n =~ /^\d+$/) {
1231 if ($H[1] == $n-1) { # another consecutive record
1233 if ($H[1] - $H[0] + 1 >= $self->{autodefer_threshhold}) {
1234 $self->{autodeferring} = 1;
1236 } else { # nonconsecutive- erase and start over
1238 $self->_stop_autodeferring;
1241 } else { # SPLICE or STORESIZE or some such
1243 $self->_stop_autodeferring;
1247 # If autodeferring was enabled, cut it out and discard the history
1248 sub _stop_autodeferring {
1250 if ($self->{autodeferring}) {
1253 $self->{autodeferring} = 0;
1256 ################################################################
1259 # This is NOT a method. It is here for two reasons:
1260 # 1. To factor a fairly complicated block out of the constructor
1261 # 2. To provide access for the test suite, which need to be sure
1262 # files are being written properly.
1263 sub _default_recsep {
1265 if ($^O eq 'MSWin32') { # Dos too?
1266 # Windows users expect files to be terminated with \r\n
1267 # But $/ is set to \n instead
1268 # Note that this also transforms \n\n into \r\n\r\n.
1269 # That is a feature.
1270 $recsep =~ s/\n/\r\n/g;
1275 # Utility function for _check_integrity
1283 # Given a file, make sure the cache is consistent with the
1284 # file contents and the internal data structures are consistent with
1285 # each other. Returns true if everything checks out, false if not
1287 # The $file argument is no longer used. It is retained for compatibility
1288 # with the existing test suite.
1289 sub _check_integrity {
1290 my ($self, $file, $warn) = @_;
1291 my $rsl = $self->{recseplen};
1292 my $rs = $self->{recsep};
1294 local *_; # local $_ does not work here
1295 local $DIAGNOSTIC = 1;
1297 if (not defined $rs) {
1298 _ci_warn("recsep is undef!");
1300 } elsif ($rs eq "") {
1301 _ci_warn("recsep is empty!");
1303 } elsif ($rsl != length $rs) {
1304 my $ln = length $rs;
1305 _ci_warn("recsep <$rs> has length $ln, should be $rsl");
1309 if (not defined $self->{offsets}[0]) {
1310 _ci_warn("offset 0 is missing!");
1313 } elsif ($self->{offsets}[0] != 0) {
1314 _ci_warn("rec 0: offset <$self->{offsets}[0]> s/b 0!");
1320 local *F = $self->{fh};
1321 seek F, 0, SEEK_SET;
1327 my $cached = $self->{cache}->_produce($n);
1328 my $offset = $self->{offsets}[$.];
1330 if (defined $offset && $offset != $ao) {
1331 _ci_warn("rec $n: offset <$offset> actual <$ao>");
1334 if (defined $cached && $_ ne $cached && ! $self->{deferred}{$n}) {
1336 _ci_warn("rec $n: cached <$cached> actual <$_>");
1338 if (defined $cached && substr($cached, -$rsl) ne $rs) {
1340 _ci_warn("rec $n in the cache is missing the record separator");
1342 if (! defined $offset && $self->{eof}) {
1344 _ci_warn("The offset table was marked complete, but it is missing element $.");
1347 if (@{$self->{offsets}} > $.+1) {
1349 my $n = @{$self->{offsets}};
1350 _ci_warn("The offset table has $n items, but the file has only $.");
1353 my $deferring = $self->_is_deferring;
1354 for my $n ($self->{cache}->ckeys) {
1355 my $r = $self->{cache}->_produce($n);
1356 $cached += length($r);
1357 next if $n+1 <= $.; # checked this already
1358 _ci_warn("spurious caching of record $n");
1361 my $b = $self->{cache}->bytes;
1362 if ($cached != $b) {
1363 _ci_warn("cache size is $b, should be $cached");
1368 # That cache has its own set of tests
1369 $good = 0 unless $self->{cache}->_check_integrity;
1371 # Now let's check the deferbuffer
1372 # Unless deferred writing is enabled, it should be empty
1373 if (! $self->_is_deferring && %{$self->{deferred}}) {
1374 _ci_warn("deferred writing disabled, but deferbuffer nonempty");
1378 # Any record in the deferbuffer should *not* be present in the readcache
1380 while (my ($n, $r) = each %{$self->{deferred}}) {
1381 $deferred_s += length($r);
1382 if (defined $self->{cache}->_produce($n)) {
1383 _ci_warn("record $n is in the deferbuffer *and* the readcache");
1386 if (substr($r, -$rsl) ne $rs) {
1387 _ci_warn("rec $n in the deferbuffer is missing the record separator");
1392 # Total size of deferbuffer should match internal total
1393 if ($deferred_s != $self->{deferred_s}) {
1394 _ci_warn("buffer size is $self->{deferred_s}, should be $deferred_s");
1398 # Total size of deferbuffer should not exceed the specified limit
1399 if ($deferred_s > $self->{dw_size}) {
1400 _ci_warn("buffer size is $self->{deferred_s} which exceeds the limit of $self->{dw_size}");
1404 # Total size of cached data should not exceed the specified limit
1405 if ($deferred_s + $cached > $self->{memory}) {
1406 my $total = $deferred_s + $cached;
1407 _ci_warn("total stored data size is $total which exceeds the limit of $self->{memory}");
1411 # Stuff related to autodeferment
1412 if (!$self->{autodefer} && @{$self->{ad_history}}) {
1413 _ci_warn("autodefer is disabled, but ad_history is nonempty");
1416 if ($self->{autodeferring} && $self->{defer}) {
1417 _ci_warn("both autodeferring and explicit deferring are active");
1420 if (@{$self->{ad_history}} == 0) {
1421 # That's OK, no additional tests required
1422 } elsif (@{$self->{ad_history}} == 2) {
1423 my @non_number = grep !/^-?\d+$/, @{$self->{ad_history}};
1427 $msg = "ad_history contains non-numbers (@{$self->{ad_history}})";
1431 } elsif ($self->{ad_history}[1] < $self->{ad_history}[0]) {
1432 _ci_warn("ad_history has nonsensical values @{$self->{ad_history}}");
1436 _ci_warn("ad_history has bad length <@{$self->{ad_history}}>");
1443 ################################################################
1449 package Tie::File::Cache;
1450 $Tie::File::Cache::VERSION = $Tie::File::VERSION;
1451 use Carp ':DEFAULT', 'confess';
1457 #sub STAT () { 4 } # Array with request statistics for each record
1458 #sub MISS () { 5 } # Total number of cache misses
1459 #sub REQ () { 6 } # Total number of cache requests
1463 my ($pack, $max) = @_;
1465 croak "missing argument to ->new" unless defined $max;
1467 bless $self => $pack;
1468 @$self = (Tie::File::Heap->new($self), {}, $max, 0);
1473 my ($self, $n) = @_;
1478 my ($self, $n) = @_;
1482 # For internal use only
1483 # Will be called by the heap structure to notify us that a certain
1484 # piece of data has moved from one heap element to another.
1485 # $k is the hash key of the item
1486 # $n is the new index into the heap at which it is stored
1487 # If $n is undefined, the item has been removed from the heap.
1489 my ($self, $k, $n) = @_;
1491 $self->[HASH]{$k} = $n;
1493 delete $self->[HASH]{$k};
1498 my ($self, $key, $val) = @_;
1500 croak "missing argument to ->insert" unless defined $key;
1501 unless (defined $self->[MAX]) {
1502 confess "undefined max" ;
1504 confess "undefined val" unless defined $val;
1505 return if length($val) > $self->[MAX];
1507 # if ($self->[STAT]) {
1508 # $self->[STAT][$key] = 1;
1512 my $oldnode = $self->[HASH]{$key};
1513 if (defined $oldnode) {
1514 my $oldval = $self->[HEAP]->set_val($oldnode, $val);
1515 $self->[BYTES] -= length($oldval);
1517 $self->[HEAP]->insert($key, $val);
1519 $self->[BYTES] += length($val);
1520 $self->flush if $self->[BYTES] > $self->[MAX];
1525 my $old_data = $self->[HEAP]->popheap;
1526 return unless defined $old_data;
1527 $self->[BYTES] -= length $old_data;
1532 my ($self, @keys) = @_;
1535 # if ($self->[STAT]) {
1536 # for my $key (@keys) {
1537 # $self->[STAT][$key] = 0;
1542 for my $key (@keys) {
1543 next unless exists $self->[HASH]{$key};
1544 my $old_data = $self->[HEAP]->remove($self->[HASH]{$key});
1545 $self->[BYTES] -= length $old_data;
1546 push @result, $old_data;
1552 my ($self, $key) = @_;
1554 croak "missing argument to ->lookup" unless defined $key;
1556 # if ($self->[STAT]) {
1557 # $self->[MISS]++ if $self->[STAT][$key]++ == 0;
1559 # my $hit_rate = 1 - $self->[MISS] / $self->[REQ];
1560 # # Do some testing to determine this threshhold
1561 # $#$self = STAT - 1 if $hit_rate > 0.20;
1564 if (exists $self->[HASH]{$key}) {
1565 $self->[HEAP]->lookup($self->[HASH]{$key});
1571 # For internal use only
1573 my ($self, $key) = @_;
1574 my $loc = $self->[HASH]{$key};
1575 return unless defined $loc;
1576 $self->[HEAP][$loc][2];
1579 # For internal use only
1581 my ($self, $key) = @_;
1582 $self->[HEAP]->promote($self->[HASH]{$key});
1587 %{$self->[HASH]} = ();
1589 $self->[HEAP]->empty;
1590 # @{$self->[STAT]} = ();
1591 # $self->[MISS] = 0;
1597 keys %{$self->[HASH]} == 0;
1601 my ($self, $key, $val) = @_;
1603 croak "missing argument to ->update" unless defined $key;
1604 if (length($val) > $self->[MAX]) {
1605 my ($oldval) = $self->remove($key);
1606 $self->[BYTES] -= length($oldval) if defined $oldval;
1607 } elsif (exists $self->[HASH]{$key}) {
1608 my $oldval = $self->[HEAP]->set_val($self->[HASH]{$key}, $val);
1609 $self->[BYTES] += length($val);
1610 $self->[BYTES] -= length($oldval) if defined $oldval;
1612 $self->[HEAP]->insert($key, $val);
1613 $self->[BYTES] += length($val);
1619 my ($self, $okeys, $nkeys) = @_;
1622 @map{@$okeys} = @$nkeys;
1623 croak "missing argument to ->rekey" unless defined $nkeys;
1624 croak "length mismatch in ->rekey arguments" unless @$nkeys == @$okeys;
1625 my %adjusted; # map new keys to heap indices
1626 # You should be able to cut this to one loop TODO XXX
1627 for (0 .. $#$okeys) {
1628 $adjusted{$nkeys->[$_]} = delete $self->[HASH]{$okeys->[$_]};
1630 while (my ($nk, $ix) = each %adjusted) {
1631 # @{$self->[HASH]}{keys %adjusted} = values %adjusted;
1632 $self->[HEAP]->rekey($ix, $nk);
1633 $self->[HASH]{$nk} = $ix;
1639 my @a = keys %{$self->[HASH]};
1643 # Return total amount of cached data
1649 # Expire oldest item from cache until cache size is smaller than $max
1650 sub reduce_size_to {
1651 my ($self, $max) = @_;
1652 until ($self->[BYTES] <= $max) {
1653 # Note that Tie::File::Cache::expire has been inlined here
1654 my $old_data = $self->[HEAP]->popheap;
1655 return unless defined $old_data;
1656 $self->[BYTES] -= length $old_data;
1660 # Why not just $self->reduce_size_to($self->[MAX])?
1661 # Try this when things stabilize TODO XXX
1662 # If the cache is too full, expire the oldest records
1665 $self->reduce_size_to($self->[MAX]) if $self->[BYTES] > $self->[MAX];
1668 # For internal use only
1671 $self->[HEAP]->expire_order;
1674 BEGIN { *_ci_warn = \&Tie::File::_ci_warn }
1676 sub _check_integrity { # For CACHE
1681 $self->[HEAP]->_check_integrity or $good = 0;
1685 for my $k (keys %{$self->[HASH]}) {
1686 if ($k ne '0' && $k !~ /^[1-9][0-9]*$/) {
1688 _ci_warn "Cache hash key <$k> is non-numeric";
1691 my $h = $self->[HASH]{$k};
1694 _ci_warn "Heap index number for key $k is undefined";
1697 _ci_warn "Heap index number for key $k is zero";
1699 my $j = $self->[HEAP][$h];
1702 _ci_warn "Heap contents key $k (=> $h) are undefined";
1704 $bytes += length($j->[2]);
1705 if ($k ne $j->[1]) {
1707 _ci_warn "Heap contents key $k (=> $h) is $j->[1], should be $k";
1714 if ($bytes != $self->[BYTES]) {
1716 _ci_warn "Total data in cache is $bytes, expected $self->[BYTES]";
1720 if ($bytes > $self->[MAX]) {
1722 _ci_warn "Total data in cache is $bytes, exceeds maximum $self->[MAX]";
1730 $self->[HEAP] = undef; # Bye bye heap
1733 ################################################################
1737 # Heap data structure for use by cache LRU routines
1739 package Tie::File::Heap;
1740 use Carp ':DEFAULT', 'confess';
1741 $Tie::File::Heap::VERSION = $Tie::File::Cache::VERSION;
1747 my ($pack, $cache) = @_;
1748 die "$pack: Parent cache object $cache does not support _heap_move method"
1749 unless eval { $cache->can('_heap_move') };
1750 my $self = [[0,$cache,0]];
1751 bless $self => $pack;
1754 # Allocate a new sequence number, larger than all previously allocated numbers
1789 $self->[0][0] = 0; # might as well reset the sequence numbers
1792 # notify the parent cache object that we moved something
1795 $self->_cache->_heap_move(@_);
1798 # Insert a piece of data into the heap with the indicated sequence number.
1799 # The item with the smallest sequence number is always at the top.
1800 # If no sequence number is specified, allocate a new one and insert the
1801 # item at the bottom.
1803 my ($self, $key, $data, $seq) = @_;
1804 $seq = $self->_nseq unless defined $seq;
1805 $self->_insert_new([$seq, $key, $data]);
1808 # Insert a new, fresh item at the bottom of the heap
1810 my ($self, $item) = @_;
1812 $i = int($i/2) until defined $self->[$i/2];
1813 $self->[$i] = $item;
1814 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1818 # Insert [$data, $seq] pair at or below item $i in the heap.
1819 # If $i is omitted, default to 1 (the top element.)
1821 my ($self, $item, $i) = @_;
1822 # $self->_check_loc($i) if defined $i;
1823 $i = 1 unless defined $i;
1824 until (! defined $self->[$i]) {
1825 if ($self->[$i][SEQ] > $item->[SEQ]) { # inserted item is older
1826 ($self->[$i], $item) = ($item, $self->[$i]);
1827 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1829 # If either is undefined, go that way. Otherwise, choose at random
1831 $dir = 0 if !defined $self->[2*$i];
1832 $dir = 1 if !defined $self->[2*$i+1];
1833 $dir = int(rand(2)) unless defined $dir;
1836 $self->[$i] = $item;
1837 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1841 # Remove the item at node $i from the heap, moving child items upwards.
1842 # The item with the smallest sequence number is always at the top.
1843 # Moving items upwards maintains this condition.
1844 # Return the removed item. Return undef if there was no item at node $i.
1846 my ($self, $i) = @_;
1847 $i = 1 unless defined $i;
1848 my $top = $self->[$i];
1849 return unless defined $top;
1852 my ($L, $R) = (2*$i, 2*$i+1);
1854 # If either is undefined, go the other way.
1855 # Otherwise, go towards the smallest.
1856 last unless defined $self->[$L] || defined $self->[$R];
1857 $ii = $R if not defined $self->[$L];
1858 $ii = $L if not defined $self->[$R];
1859 unless (defined $ii) {
1860 $ii = $self->[$L][SEQ] < $self->[$R][SEQ] ? $L : $R;
1863 $self->[$i] = $self->[$ii]; # Promote child to fill vacated spot
1864 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1865 $i = $ii; # Fill new vacated spot
1867 $self->[0][1]->_heap_move($top->[KEY], undef);
1878 # set the sequence number of the indicated item to a higher number
1879 # than any other item in the heap, and bubble the item down to the
1882 my ($self, $n) = @_;
1883 # $self->_check_loc($n);
1884 $self->[$n][SEQ] = $self->_nseq;
1887 my ($L, $R) = (2*$i, 2*$i+1);
1889 last unless defined $self->[$L] || defined $self->[$R];
1890 $dir = $R unless defined $self->[$L];
1891 $dir = $L unless defined $self->[$R];
1892 unless (defined $dir) {
1893 $dir = $self->[$L][SEQ] < $self->[$R][SEQ] ? $L : $R;
1895 @{$self}[$i, $dir] = @{$self}[$dir, $i];
1897 $self->[0][1]->_heap_move($self->[$_][KEY], $_) if defined $self->[$_];
1903 # Return item $n from the heap, promoting its LRU status
1905 my ($self, $n) = @_;
1906 # $self->_check_loc($n);
1907 my $val = $self->[$n];
1913 # Assign a new value for node $n, promoting it to the bottom of the heap
1915 my ($self, $n, $val) = @_;
1916 # $self->_check_loc($n);
1917 my $oval = $self->[$n][DAT];
1918 $self->[$n][DAT] = $val;
1923 # The hask key has changed for an item;
1924 # alter the heap's record of the hash key
1926 my ($self, $n, $new_key) = @_;
1927 # $self->_check_loc($n);
1928 $self->[$n][KEY] = $new_key;
1932 my ($self, $n) = @_;
1933 unless (1 || defined $self->[$n]) {
1934 confess "_check_loc($n) failed";
1938 BEGIN { *_ci_warn = \&Tie::File::_ci_warn }
1940 sub _check_integrity {
1945 unless (eval {$self->[0][1]->isa("Tie::File::Cache")}) {
1946 _ci_warn "Element 0 of heap corrupt";
1949 $good = 0 unless $self->_satisfies_heap_condition(1);
1950 for my $i (2 .. $#{$self}) {
1951 my $p = int($i/2); # index of parent node
1952 if (defined $self->[$i] && ! defined $self->[$p]) {
1953 _ci_warn "Element $i of heap defined, but parent $p isn't";
1957 if (defined $self->[$i]) {
1958 if ($seq{$self->[$i][SEQ]}) {
1959 my $seq = $self->[$i][SEQ];
1960 _ci_warn "Nodes $i and $seq{$seq} both have SEQ=$seq";
1963 $seq{$self->[$i][SEQ]} = $i;
1971 sub _satisfies_heap_condition {
1977 next unless defined $self->[$c];
1978 if ($self->[$n][SEQ] >= $self->[$c]) {
1979 _ci_warn "Node $n of heap does not predate node $c";
1982 $good = 0 unless $self->_satisfies_heap_condition($c);
1987 # Return a list of all the values, sorted by expiration order
1990 my @nodes = sort {$a->[SEQ] <=> $b->[SEQ]} $self->_nodes;
1991 map { $_->[KEY] } @nodes;
1997 return unless defined $self->[$i];
1998 ($self->[$i], $self->_nodes($i*2), $self->_nodes($i*2+1));
2001 "Cogito, ergo sum."; # don't forget to return a true value from the file
2007 Tie::File - Access the lines of a disk file via a Perl array
2011 # This file documents Tie::File version 0.97
2014 tie @array, 'Tie::File', filename or die ...;
2016 $array[13] = 'blah'; # line 13 of the file is now 'blah'
2017 print $array[42]; # display line 42 of the file
2019 $n_recs = @array; # how many records are in the file?
2020 $#array -= 2; # chop two records off the end
2024 s/PERL/Perl/g; # Replace PERL with Perl everywhere in the file
2027 # These are just like regular push, pop, unshift, shift, and splice
2028 # Except that they modify the file in the way you would expect
2030 push @array, new recs...;
2031 my $r1 = pop @array;
2032 unshift @array, new recs...;
2033 my $r2 = shift @array;
2034 @old_recs = splice @array, 3, 7, new recs...;
2036 untie @array; # all finished
2041 C<Tie::File> represents a regular text file as a Perl array. Each
2042 element in the array corresponds to a record in the file. The first
2043 line of the file is element 0 of the array; the second line is element
2046 The file is I<not> loaded into memory, so this will work even for
2049 Changes to the array are reflected in the file immediately.
2051 Lazy people and beginners may now stop reading the manual.
2055 What is a 'record'? By default, the meaning is the same as for the
2056 C<E<lt>...E<gt>> operator: It's a string terminated by C<$/>, which is
2057 probably C<"\n">. (Minor exception: on DOS and Win32 systems, a
2058 'record' is a string terminated by C<"\r\n">.) You may change the
2059 definition of "record" by supplying the C<recsep> option in the C<tie>
2062 tie @array, 'Tie::File', $file, recsep => 'es';
2064 This says that records are delimited by the string C<es>. If the file
2065 contained the following data:
2067 Curse these pesky flies!\n
2069 then the C<@array> would appear to have four elements:
2076 An undefined value is not permitted as a record separator. Perl's
2077 special "paragraph mode" semantics (E<agrave> la C<$/ = "">) are not
2080 Records read from the tied array do not have the record separator
2081 string on the end; this is to allow
2083 $array[17] .= "extra";
2085 to work as expected.
2087 (See L<"autochomp">, below.) Records stored into the array will have
2088 the record separator string appended before they are written to the
2089 file, if they don't have one already. For example, if the record
2090 separator string is C<"\n">, then the following two lines do exactly
2093 $array[17] = "Cherry pie";
2094 $array[17] = "Cherry pie\n";
2096 The result is that the contents of line 17 of the file will be
2097 replaced with "Cherry pie"; a newline character will separate line 17
2098 from line 18. This means that this code will do nothing:
2102 Because the C<chomp>ed value will have the separator reattached when
2103 it is written back to the file. There is no way to create a file
2104 whose trailing record separator string is missing.
2106 Inserting records that I<contain> the record separator string is not
2107 supported by this module. It will probably produce a reasonable
2108 result, but what this result will be may change in a future version.
2109 Use 'splice' to insert records or to replace one record with several.
2113 Normally, array elements have the record separator removed, so that if
2114 the file contains the text
2120 the tied array will appear to contain C<("Gold", "Frankincense",
2121 "Myrrh")>. If you set C<autochomp> to a false value, the record
2122 separator will not be removed. If the file above was tied with
2124 tie @gifts, "Tie::File", $gifts, autochomp => 0;
2126 then the array C<@gifts> would appear to contain C<("Gold\n",
2127 "Frankincense\n", "Myrrh\n")>, or (on Win32 systems) C<("Gold\r\n",
2128 "Frankincense\r\n", "Myrrh\r\n")>.
2132 Normally, the specified file will be opened for read and write access,
2133 and will be created if it does not exist. (That is, the flags
2134 C<O_RDWR | O_CREAT> are supplied in the C<open> call.) If you want to
2135 change this, you may supply alternative flags in the C<mode> option.
2136 See L<Fcntl> for a listing of available flags.
2139 # open the file if it exists, but fail if it does not exist
2141 tie @array, 'Tie::File', $file, mode => O_RDWR;
2143 # create the file if it does not exist
2144 use Fcntl 'O_RDWR', 'O_CREAT';
2145 tie @array, 'Tie::File', $file, mode => O_RDWR | O_CREAT;
2147 # open an existing file in read-only mode
2148 use Fcntl 'O_RDONLY';
2149 tie @array, 'Tie::File', $file, mode => O_RDONLY;
2151 Opening the data file in write-only or append mode is not supported.
2155 This is an upper limit on the amount of memory that C<Tie::File> will
2156 consume at any time while managing the file. This is used for two
2157 things: managing the I<read cache> and managing the I<deferred write
2160 Records read in from the file are cached, to avoid having to re-read
2161 them repeatedly. If you read the same record twice, the first time it
2162 will be stored in memory, and the second time it will be fetched from
2163 the I<read cache>. The amount of data in the read cache will not
2164 exceed the value you specified for C<memory>. If C<Tie::File> wants
2165 to cache a new record, but the read cache is full, it will make room
2166 by expiring the least-recently visited records from the read cache.
2168 The default memory limit is 2Mib. You can adjust the maximum read
2169 cache size by supplying the C<memory> option. The argument is the
2170 desired cache size, in bytes.
2172 # I have a lot of memory, so use a large cache to speed up access
2173 tie @array, 'Tie::File', $file, memory => 20_000_000;
2175 Setting the memory limit to 0 will inhibit caching; records will be
2176 fetched from disk every time you examine them.
2178 The C<memory> value is not an absolute or exact limit on the memory
2179 used. C<Tie::File> objects contains some structures besides the read
2180 cache and the deferred write buffer, whose sizes are not charged
2183 The cache itself consumes about 310 bytes per cached record, so if
2184 your file has many short records, you may want to decrease the cache
2185 memory limit, or else the cache overhead may exceed the size of the
2191 (This is an advanced feature. Skip this section on first reading.)
2193 If you use deferred writing (See L<"Deferred Writing">, below) then
2194 data you write into the array will not be written directly to the
2195 file; instead, it will be saved in the I<deferred write buffer> to be
2196 written out later. Data in the deferred write buffer is also charged
2197 against the memory limit you set with the C<memory> option.
2199 You may set the C<dw_size> option to limit the amount of data that can
2200 be saved in the deferred write buffer. This limit may not exceed the
2201 total memory limit. For example, if you set C<dw_size> to 1000 and
2202 C<memory> to 2500, that means that no more than 1000 bytes of deferred
2203 writes will be saved up. The space available for the read cache will
2204 vary, but it will always be at least 1500 bytes (if the deferred write
2205 buffer is full) and it could grow as large as 2500 bytes (if the
2206 deferred write buffer is empty.)
2208 If you don't specify a C<dw_size>, it defaults to the entire memory
2211 =head2 Option Format
2213 C<-mode> is a synonym for C<mode>. C<-recsep> is a synonym for
2214 C<recsep>. C<-memory> is a synonym for C<memory>. You get the
2217 =head1 Public Methods
2219 The C<tie> call returns an object, say C<$o>. You may call
2221 $rec = $o->FETCH($n);
2222 $o->STORE($n, $rec);
2224 to fetch or store the record at line C<$n>, respectively; similarly
2225 the other tied array methods. (See L<perltie> for details.) You may
2226 also call the following methods on this object:
2232 will lock the tied file. C<MODE> has the same meaning as the second
2233 argument to the Perl built-in C<flock> function; for example
2234 C<LOCK_SH> or C<LOCK_EX | LOCK_NB>. (These constants are provided by
2235 the C<use Fcntl ':flock'> declaration.)
2237 C<MODE> is optional; the default is C<LOCK_EX>.
2239 C<Tie::File> maintains an internal table of the byte offset of each
2240 record it has seen in the file.
2242 When you use C<flock> to lock the file, C<Tie::File> assumes that the
2243 read cache is no longer trustworthy, because another process might
2244 have modified the file since the last time it was read. Therefore, a
2245 successful call to C<flock> discards the contents of the read cache
2246 and the internal record offset table.
2248 C<Tie::File> promises that the following sequence of operations will
2251 my $o = tie @array, "Tie::File", $filename;
2254 In particular, C<Tie::File> will I<not> read or write the file during
2255 the C<tie> call. (Exception: Using C<mode =E<gt> O_TRUNC> will, of
2256 course, erase the file during the C<tie> call. If you want to do this
2257 safely, then open the file without C<O_TRUNC>, lock the file, and use
2260 The best way to unlock a file is to discard the object and untie the
2261 array. It is probably unsafe to unlock the file without also untying
2262 it, because if you do, changes may remain unwritten inside the object.
2263 That is why there is no shortcut for unlocking. If you really want to
2264 unlock the file prematurely, you know what to do; if you don't know
2265 what to do, then don't do it.
2267 All the usual warnings about file locking apply here. In particular,
2268 note that file locking in Perl is B<advisory>, which means that
2269 holding a lock will not prevent anyone else from reading, writing, or
2270 erasing the file; it only prevents them from getting another lock at
2271 the same time. Locks are analogous to green traffic lights: If you
2272 have a green light, that does not prevent the idiot coming the other
2273 way from plowing into you sideways; it merely guarantees to you that
2274 the idiot does not also have a green light at the same time.
2278 my $old_value = $o->autochomp(0); # disable autochomp option
2279 my $old_value = $o->autochomp(1); # enable autochomp option
2281 my $ac = $o->autochomp(); # recover current value
2283 See L<"autochomp">, above.
2285 =head2 C<defer>, C<flush>, C<discard>, and C<autodefer>
2287 See L<"Deferred Writing">, below.
2291 $off = $o->offset($n);
2293 This method returns the byte offset of the start of the C<$n>th record
2294 in the file. If there is no such record, it returns an undefined
2297 =head1 Tying to an already-opened filehandle
2299 If C<$fh> is a filehandle, such as is returned by C<IO::File> or one
2300 of the other C<IO> modules, you may use:
2302 tie @array, 'Tie::File', $fh, ...;
2304 Similarly if you opened that handle C<FH> with regular C<open> or
2305 C<sysopen>, you may use:
2307 tie @array, 'Tie::File', \*FH, ...;
2309 Handles that were opened write-only won't work. Handles that were
2310 opened read-only will work as long as you don't try to modify the
2311 array. Handles must be attached to seekable sources of data---that
2312 means no pipes or sockets. If C<Tie::File> can detect that you
2313 supplied a non-seekable handle, the C<tie> call will throw an
2314 exception. (On Unix systems, it can detect this.)
2316 Note that Tie::File will only close any filehandles that it opened
2317 internally. If you passed it a filehandle as above, you "own" the
2318 filehandle, and are responsible for closing it after you have untied
2321 =head1 Deferred Writing
2323 (This is an advanced feature. Skip this section on first reading.)
2325 Normally, modifying a C<Tie::File> array writes to the underlying file
2326 immediately. Every assignment like C<$a[3] = ...> rewrites as much of
2327 the file as is necessary; typically, everything from line 3 through
2328 the end will need to be rewritten. This is the simplest and most
2329 transparent behavior. Performance even for large files is reasonably
2332 However, under some circumstances, this behavior may be excessively
2333 slow. For example, suppose you have a million-record file, and you
2340 The first time through the loop, you will rewrite the entire file,
2341 from line 0 through the end. The second time through the loop, you
2342 will rewrite the entire file from line 1 through the end. The third
2343 time through the loop, you will rewrite the entire file from line 2 to
2346 If the performance in such cases is unacceptable, you may defer the
2347 actual writing, and then have it done all at once. The following loop
2348 will perform much better for large files:
2356 If C<Tie::File>'s memory limit is large enough, all the writing will
2357 done in memory. Then, when you call C<-E<gt>flush>, the entire file
2358 will be rewritten in a single pass.
2360 (Actually, the preceding discussion is something of a fib. You don't
2361 need to enable deferred writing to get good performance for this
2362 common case, because C<Tie::File> will do it for you automatically
2363 unless you specifically tell it not to. See L<"autodeferring">,
2366 Calling C<-E<gt>flush> returns the array to immediate-write mode. If
2367 you wish to discard the deferred writes, you may call C<-E<gt>discard>
2368 instead of C<-E<gt>flush>. Note that in some cases, some of the data
2369 will have been written already, and it will be too late for
2370 C<-E<gt>discard> to discard all the changes. Support for
2371 C<-E<gt>discard> may be withdrawn in a future version of C<Tie::File>.
2373 Deferred writes are cached in memory up to the limit specified by the
2374 C<dw_size> option (see above). If the deferred-write buffer is full
2375 and you try to write still more deferred data, the buffer will be
2376 flushed. All buffered data will be written immediately, the buffer
2377 will be emptied, and the now-empty space will be used for future
2380 If the deferred-write buffer isn't yet full, but the total size of the
2381 buffer and the read cache would exceed the C<memory> limit, the oldest
2382 records will be expired from the read cache until the total size is
2385 C<push>, C<pop>, C<shift>, C<unshift>, and C<splice> cannot be
2386 deferred. When you perform one of these operations, any deferred data
2387 is written to the file and the operation is performed immediately.
2388 This may change in a future version.
2390 If you resize the array with deferred writing enabled, the file will
2391 be resized immediately, but deferred records will not be written.
2392 This has a surprising consequence: C<@a = (...)> erases the file
2393 immediately, but the writing of the actual data is deferred. This
2394 might be a bug. If it is a bug, it will be fixed in a future version.
2396 =head2 Autodeferring
2398 C<Tie::File> tries to guess when deferred writing might be helpful,
2399 and to turn it on and off automatically.
2405 In this example, only the first two assignments will be done
2406 immediately; after this, all the changes to the file will be deferred
2407 up to the user-specified memory limit.
2409 You should usually be able to ignore this and just use the module
2410 without thinking about deferring. However, special applications may
2411 require fine control over which writes are deferred, or may require
2412 that all writes be immediate. To disable the autodeferment feature,
2415 (tied @o)->autodefer(0);
2419 tie @array, 'Tie::File', $file, autodefer => 0;
2422 Similarly, C<-E<gt>autodefer(1)> re-enables autodeferment, and
2423 C<-E<gt>autodefer()> recovers the current value of the autodefer setting.
2426 =head1 CONCURRENT ACCESS TO FILES
2428 Caching and deferred writing are inappropriate if you want the same
2429 file to be accessed simultaneously from more than one process. Other
2430 optimizations performed internally by this module are also
2431 incompatible with concurrent access. A future version of this module will
2432 support a C<concurrent =E<gt> 1> option that enables safe concurrent access.
2434 Previous versions of this documentation suggested using C<memory
2435 =E<gt> 0> for safe concurrent access. This was mistaken. Tie::File
2436 will not support safe concurrent access before version 0.98.
2440 (That's Latin for 'warnings'.)
2446 Reasonable effort was made to make this module efficient. Nevertheless,
2447 changing the size of a record in the middle of a large file will
2448 always be fairly slow, because everything after the new record must be
2453 The behavior of tied arrays is not precisely the same as for regular
2454 arrays. For example:
2456 # This DOES print "How unusual!"
2457 undef $a[10]; print "How unusual!\n" if defined $a[10];
2459 C<undef>-ing a C<Tie::File> array element just blanks out the
2460 corresponding record in the file. When you read it back again, you'll
2461 get the empty string, so the supposedly-C<undef>'ed value will be
2462 defined. Similarly, if you have C<autochomp> disabled, then
2464 # This DOES print "How unusual!" if 'autochomp' is disabled
2466 print "How unusual!\n" if $a[10];
2468 Because when C<autochomp> is disabled, C<$a[10]> will read back as
2469 C<"\n"> (or whatever the record separator string is.)
2471 There are other minor differences, particularly regarding C<exists>
2472 and C<delete>, but in general, the correspondence is extremely close.
2476 I have supposed that since this module is concerned with file I/O,
2477 almost all normal use of it will be heavily I/O bound. This means
2478 that the time to maintain complicated data structures inside the
2479 module will be dominated by the time to actually perform the I/O.
2480 When there was an opportunity to spend CPU time to avoid doing I/O, I
2481 usually tried to take it.
2485 You might be tempted to think that deferred writing is like
2486 transactions, with C<flush> as C<commit> and C<discard> as
2487 C<rollback>, but it isn't, so don't.
2491 There is a large memory overhead for each record offset and for each
2492 cache entry: about 310 bytes per cached data record, and about 21 bytes per offset table entry.
2494 The per-record overhead will limit the maximum number of records you
2495 can access per file. Note that I<accessing> the length of the array
2496 via C<$x = scalar @tied_file> accesses B<all> records and stores their
2497 offsets. The same for C<foreach (@tied_file)>, even if you exit the
2504 This version promises absolutely nothing about the internals, which
2505 may change without notice. A future version of the module will have a
2506 well-defined and stable subclassing API.
2508 =head1 WHAT ABOUT C<DB_File>?
2510 People sometimes point out that L<DB_File> will do something similar,
2511 and ask why C<Tie::File> module is necessary.
2513 There are a number of reasons that you might prefer C<Tie::File>.
2514 A list is available at C<http://perl.plover.com/TieFile/why-not-DB_File>.
2520 To contact the author, send email to: C<mjd-perl-tiefile+@plover.com>
2522 To receive an announcement whenever a new version of this module is
2523 released, send a blank email message to
2524 C<mjd-perl-tiefile-subscribe@plover.com>.
2526 The most recent version of this module, including documentation and
2527 any news of importance, will be available at
2529 http://perl.plover.com/TieFile/
2534 C<Tie::File> version 0.97 is copyright (C) 2003 Mark Jason Dominus.
2536 This library is free software; you may redistribute it and/or modify
2537 it under the same terms as Perl itself.
2539 These terms are your choice of any of (1) the Perl Artistic Licence,
2540 or (2) version 2 of the GNU General Public License as published by the
2541 Free Software Foundation, or (3) any later version of the GNU General
2544 This library is distributed in the hope that it will be useful,
2545 but WITHOUT ANY WARRANTY; without even the implied warranty of
2546 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2547 GNU General Public License for more details.
2549 You should have received a copy of the GNU General Public License
2550 along with this library program; it should be in the file C<COPYING>.
2551 If not, write to the Free Software Foundation, Inc., 59 Temple Place,
2552 Suite 330, Boston, MA 02111 USA
2554 For licensing inquiries, contact the author at:
2558 Philadelphia, PA 19107
2562 C<Tie::File> version 0.97 comes with ABSOLUTELY NO WARRANTY.
2563 For details, see the license.
2567 Gigantic thanks to Jarkko Hietaniemi, for agreeing to put this in the
2568 core when I hadn't written it yet, and for generally being helpful,
2569 supportive, and competent. (Usually the rule is "choose any one.")
2570 Also big thanks to Abhijit Menon-Sen for all of the same things.
2572 Special thanks to Craig Berry and Peter Prymmer (for VMS portability
2573 help), Randy Kobes (for Win32 portability help), Clinton Pierce and
2574 Autrijus Tang (for heroic eleventh-hour Win32 testing above and beyond
2575 the call of duty), Michael G Schwern (for testing advice), and the
2576 rest of the CPAN testers (for testing generally).
2578 Special thanks to Tels for suggesting several speed and memory
2581 Additional thanks to:
2587 Jarkko Hietaniemi (again) /
2591 Tassilo von Parseval /
2597 Autrijus Tang (again) /
2603 More tests. (Stuff I didn't think of yet.)
2607 Fixed-length mode. Leave-blanks mode.
2609 Maybe an autolocking mode?
2611 For many common uses of the module, the read cache is a liability.
2612 For example, a program that inserts a single record, or that scans the
2613 file once, will have a cache hit rate of zero. This suggests a major
2614 optimization: The cache should be initially disabled. Here's a hybrid
2615 approach: Initially, the cache is disabled, but the cache code
2616 maintains statistics about how high the hit rate would be *if* it were
2617 enabled. When it sees the hit rate get high enough, it enables
2618 itself. The STAT comments in this code are the beginning of an
2619 implementation of this.
2621 Record locking with fcntl()? Then the module might support an undo
2622 log and get real transactions. What a tour de force that would be.
2624 Keeping track of the highest cached record. This would allow reads-in-a-row
2625 to skip the cache lookup faster (if reading from 1..N with empty cache at
2626 start, the last cached value will be always N-1).