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);
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 unless (defined $opts{memory}) {
37 # default is the larger of the default cache size and the
38 # deferred-write buffer size (if specified)
39 $opts{memory} = $DEFAULT_MEMORY_SIZE;
40 $opts{memory} = $opts{dw_size}
41 if defined $opts{dw_size} && $opts{dw_size} > $DEFAULT_MEMORY_SIZE;
44 $opts{dw_size} = $opts{memory} unless defined $opts{dw_size};
45 if ($opts{dw_size} > $opts{memory}) {
46 croak("$pack: dw_size may not be larger than total memory allocation\n");
48 # are we in deferred-write mode?
49 $opts{defer} = 0 unless defined $opts{defer};
50 $opts{deferred} = {}; # no records are presently deferred
51 $opts{deferred_s} = 0; # count of total bytes in ->{deferred}
52 $opts{deferred_max} = -1; # empty
54 # What's a good way to arrange that this class can be overridden?
55 $opts{cache} = Tie::File::Cache->new($opts{memory});
57 # autodeferment is enabled by default
58 $opts{autodefer} = 1 unless defined $opts{autodefer};
59 $opts{autodeferring} = 0; # but is not initially active
60 $opts{ad_history} = [];
61 $opts{autodefer_threshhold} = $DEFAULT_AUTODEFER_THRESHHOLD
62 unless defined $opts{autodefer_threshhold};
63 $opts{autodefer_filelen_threshhold} = $DEFAULT_AUTODEFER_FILELEN_THRESHHOLD
64 unless defined $opts{autodefer_filelen_threshhold};
67 $opts{filename} = $file;
68 unless (defined $opts{recsep}) {
69 $opts{recsep} = _default_recsep();
71 $opts{recseplen} = length($opts{recsep});
72 if ($opts{recseplen} == 0) {
73 croak "Empty record separator not supported by $pack";
76 $opts{autochomp} = 1 unless defined $opts{autochomp};
78 $opts{mode} = O_CREAT|O_RDWR unless defined $opts{mode};
79 $opts{rdonly} = (($opts{mode} & O_ACCMODE) == O_RDONLY);
80 $opts{sawlastrec} = undef;
84 if (UNIVERSAL::isa($file, 'GLOB')) {
85 # We use 1 here on the theory that some systems
86 # may not indicate failure if we use 0.
87 # MSWin32 does not indicate failure with 0, but I don't know if
88 # it will indicate failure with 1 or not.
89 unless (seek $file, 1, SEEK_SET) {
90 croak "$pack: your filehandle does not appear to be seekable";
92 seek $file, 0, SEEK_SET # put it back
93 $fh = $file; # setting binmode is the user's problem
95 croak "usage: tie \@array, $pack, filename, [option => value]...";
97 $fh = \do { local *FH }; # only works in 5.005 and later
98 sysopen $fh, $file, $opts{mode}, 0666 or return;
102 { my $ofh = select $fh; $| = 1; select $ofh } # autoflush on write
103 if (defined $opts{discipline} && $] >= 5.006) {
104 # This avoids a compile-time warning under 5.005
105 eval 'binmode($fh, $opts{discipline})';
106 croak $@ if $@ =~ /unknown discipline/i;
111 bless \%opts => $pack;
118 # check the defer buffer
119 $rec = $self->{deferred}{$n} if exists $self->{deferred}{$n};
120 $rec = $self->_fetch($n) unless defined $rec;
123 substr($rec, - $self->{recseplen}) = ""
124 if defined $rec && $self->{autochomp};
128 # Chomp many records in-place; return nothing useful
131 return unless $self->{autochomp};
132 if ($self->{autochomp}) {
135 substr($_, - $self->{recseplen}) = "";
140 # Chomp one record in-place; return modified record
142 my ($self, $rec) = @_;
143 return $rec unless $self->{autochomp};
144 return unless defined $rec;
145 substr($rec, - $self->{recseplen}) = "";
152 # check the record cache
153 { my $cached = $self->{cache}->lookup($n);
154 return $cached if defined $cached;
157 if ($#{$self->{offsets}} < $n) {
158 return if $self->{eof}; # request for record beyond end of file
159 my $o = $self->_fill_offsets_to($n);
160 # If it's still undefined, there is no such record, so return 'undef'
161 return unless defined $o;
164 my $fh = $self->{FH};
165 $self->_seek($n); # we can do this now that offsets is populated
166 my $rec = $self->_read_record;
168 # If we happen to have just read the first record, check to see if
169 # the length of the record matches what 'tell' says. If not, Tie::File
170 # won't work, and should drop dead.
172 # if ($n == 0 && defined($rec) && tell($self->{fh}) != length($rec)) {
173 # if (defined $self->{discipline}) {
174 # croak "I/O discipline $self->{discipline} not supported";
176 # croak "File encoding not supported";
180 $self->{cache}->insert($n, $rec) if defined $rec && not $self->{flushing};
185 my ($self, $n, $rec) = @_;
186 die "STORE called from _check_integrity!" if $DIAGNOSTIC;
188 $self->_fixrecs($rec);
190 if ($self->{autodefer}) {
191 $self->_annotate_ad_history($n);
194 return $self->_store_deferred($n, $rec) if $self->_is_deferring;
197 # We need this to decide whether the new record will fit
198 # It incidentally populates the offsets table
199 # Note we have to do this before we alter the cache
200 # 20020324 Wait, but this DOES alter the cache. TODO BUG?
201 my $oldrec = $self->_fetch($n);
203 if (not defined $oldrec) {
204 # We're storing a record beyond the end of the file
205 $self->_extend_file_to($n+1);
206 $oldrec = $self->{recsep};
208 # return if $oldrec eq $rec; # don't bother
209 my $len_diff = length($rec) - length($oldrec);
211 # length($oldrec) here is not consistent with text mode TODO XXX BUG
212 $self->_mtwrite($rec, $self->{offsets}[$n], length($oldrec));
213 $self->_oadjust([$n, 1, $rec]);
214 $self->{cache}->update($n, $rec);
217 sub _store_deferred {
218 my ($self, $n, $rec) = @_;
219 $self->{cache}->remove($n);
220 my $old_deferred = $self->{deferred}{$n};
222 if (defined $self->{deferred_max} && $n > $self->{deferred_max}) {
223 $self->{deferred_max} = $n;
225 $self->{deferred}{$n} = $rec;
227 my $len_diff = length($rec);
228 $len_diff -= length($old_deferred) if defined $old_deferred;
229 $self->{deferred_s} += $len_diff;
230 $self->{cache}->adj_limit(-$len_diff);
231 if ($self->{deferred_s} > $self->{dw_size}) {
233 } elsif ($self->_cache_too_full) {
238 # Remove a single record from the deferred-write buffer without writing it
239 # The record need not be present
240 sub _delete_deferred {
242 my $rec = delete $self->{deferred}{$n};
243 return unless defined $rec;
245 if (defined $self->{deferred_max}
246 && $n == $self->{deferred_max}) {
247 undef $self->{deferred_max};
250 $self->{deferred_s} -= length $rec;
251 $self->{cache}->adj_limit(length $rec);
256 my $n = $self->{eof} ? $#{$self->{offsets}} : $self->_fill_offsets;
258 my $top_deferred = $self->_defer_max;
259 $n = $top_deferred+1 if defined $top_deferred && $n < $top_deferred+1;
264 my ($self, $len) = @_;
266 if ($self->{autodefer}) {
267 $self->_annotate_ad_history('STORESIZE');
270 my $olen = $self->FETCHSIZE;
271 return if $len == $olen; # Woo-hoo!
275 if ($self->_is_deferring) {
276 for ($olen .. $len-1) {
277 $self->_store_deferred($_, $self->{recsep});
280 $self->_extend_file_to($len);
286 if ($self->_is_deferring) {
287 # TODO maybe replace this with map-plus-assignment?
288 for (grep $_ >= $len, keys %{$self->{deferred}}) {
289 $self->_delete_deferred($_);
291 $self->{deferred_max} = $len-1;
296 $#{$self->{offsets}} = $len;
297 # $self->{offsets}[0] = 0; # in case we just chopped this
299 $self->{cache}->remove(grep $_ >= $len, $self->{cache}->ckeys);
303 ### It should not be necessary to do FETCHSIZE
304 ### Just seek to the end of the file.
307 $self->SPLICE($self->FETCHSIZE, scalar(@_), @_);
310 # $self->FETCHSIZE; # because av.c takes care of this for me
315 my $size = $self->FETCHSIZE;
316 return if $size == 0;
317 # print STDERR "# POPPITY POP POP POP\n";
318 scalar $self->SPLICE($size-1, 1);
323 scalar $self->SPLICE(0, 1);
328 $self->SPLICE(0, 0, @_);
329 # $self->FETCHSIZE; # av.c takes care of this for me
335 if ($self->{autodefer}) {
336 $self->_annotate_ad_history('CLEAR');
341 $self->{cache}->set_limit($self->{memory});
342 $self->{cache}->empty;
343 @{$self->{offsets}} = (0);
344 %{$self->{deferred}}= ();
345 $self->{deferred_s} = 0;
346 $self->{deferred_max} = -1;
352 # No need to pre-extend anything in this case
353 return if $self->_is_deferring;
355 $self->_fill_offsets_to($n);
356 $self->_extend_file_to($n);
362 if ($self->{autodefer}) {
363 $self->_annotate_ad_history('DELETE');
366 my $lastrec = $self->FETCHSIZE-1;
367 my $rec = $self->FETCH($n);
368 $self->_delete_deferred($n) if $self->_is_deferring;
369 if ($n == $lastrec) {
372 $#{$self->{offsets}}--;
373 $self->{cache}->remove($n);
374 # perhaps in this case I should also remove trailing null records?
376 # Note that delete @a[-3..-1] deletes the records in the wrong order,
377 # so we only chop the very last one out of the file. We could repair this
378 # by tracking deleted records inside the object.
379 } elsif ($n < $lastrec) {
380 $self->STORE($n, "");
387 return 1 if exists $self->{deferred}{$n};
388 $n < $self->FETCHSIZE;
394 if ($self->{autodefer}) {
395 $self->_annotate_ad_history('SPLICE');
398 $self->_flush if $self->_is_deferring; # move this up?
400 $self->_chomp(my @a = $self->_splice(@_));
403 $self->_chomp1(scalar $self->_splice(@_));
409 $self->flush if $self->_is_deferring;
410 $self->{cache}->delink if defined $self->{cache}; # break circular link
411 if ($self->{fh} and $self->{ourfh}) {
412 delete $self->{ourfh};
413 close delete $self->{fh};
418 my ($self, $pos, $nrecs, @data) = @_;
421 $pos = 0 unless defined $pos;
423 # Deal with negative and other out-of-range positions
424 # Also set default for $nrecs
426 my $oldsize = $self->FETCHSIZE;
427 $nrecs = $oldsize unless defined $nrecs;
433 croak "Modification of non-creatable array value attempted, subscript $oldpos";
437 if ($pos > $oldsize) {
439 $pos = $oldsize; # This is what perl does for normal arrays
442 # The manual is very unclear here
444 $nrecs = $oldsize - $pos + $nrecs;
445 $nrecs = 0 if $nrecs < 0;
448 # nrecs is too big---it really means "until the end"
450 if ($nrecs + $pos > $oldsize) {
451 $nrecs = $oldsize - $pos;
455 $self->_fixrecs(@data);
456 my $data = join '', @data;
457 my $datalen = length $data;
460 # compute length of data being removed
461 for ($pos .. $pos+$nrecs-1) {
462 last unless defined $self->_fill_offsets_to($_);
463 my $rec = $self->_fetch($_);
464 last unless defined $rec;
467 # Why don't we just use length($rec) here?
468 # Because that record might have come from the cache. _splice
469 # might have been called to flush out the deferred-write records,
470 # and in this case length($rec) is the length of the record to be
471 # *written*, not the length of the actual record in the file. But
472 # the offsets are still true. 20020322
473 $oldlen += $self->{offsets}[$_+1] - $self->{offsets}[$_]
474 if defined $self->{offsets}[$_+1];
476 $self->_fill_offsets_to($pos+$nrecs);
479 $self->_mtwrite($data, $self->{offsets}[$pos], $oldlen);
480 # Adjust the offsets table
481 $self->_oadjust([$pos, $nrecs, @data]);
483 { # Take this read cache stuff out into a separate function
484 # You made a half-attempt to put it into _oadjust.
485 # Finish something like that up eventually.
486 # STORE also needs to do something similarish
488 # update the read cache, part 1
490 for ($pos .. $pos+$nrecs-1) {
491 my $new = $data[$_-$pos];
493 $self->{cache}->update($_, $new);
495 $self->{cache}->remove($_);
499 # update the read cache, part 2
500 # moved records - records past the site of the change
501 # need to be renumbered
502 # Maybe merge this with the previous block?
504 my @oldkeys = grep $_ >= $pos + $nrecs, $self->{cache}->ckeys;
505 my @newkeys = map $_-$nrecs+@data, @oldkeys;
506 $self->{cache}->rekey(\@oldkeys, \@newkeys);
509 # Now there might be too much data in the cache, if we spliced out
510 # some short records and spliced in some long ones. If so, flush
515 # Yes, the return value of 'splice' *is* actually this complicated
516 wantarray ? @result : @result ? $result[-1] : undef;
520 # write data into the file
521 # $data is the data to be written.
522 # it should be written at position $pos, and should overwrite
523 # exactly $len of the following bytes.
524 # Note that if length($data) > $len, the subsequent bytes will have to
525 # be moved up, and if length($data) < $len, they will have to
528 my ($self, $data, $pos, $len) = @_;
530 unless (defined $pos) {
531 die "\$pos was undefined in _twrite";
534 my $len_diff = length($data) - $len;
536 if ($len_diff == 0) { # Woo-hoo!
537 my $fh = $self->{fh};
539 $self->_write_record($data);
540 return; # well, that was easy.
543 # the two records are of different lengths
544 # our strategy here: rewrite the tail of the file,
545 # reading ahead one buffer at a time
546 # $bufsize is required to be at least as large as the data we're overwriting
547 my $bufsize = _bufsize($len_diff);
548 my ($writepos, $readpos) = ($pos, $pos+$len);
552 # Seems like there ought to be a way to avoid the repeated code
553 # and the special case here. The read(1) is also a little weird.
556 $self->_seekb($readpos);
557 my $br = read $self->{fh}, $next_block, $bufsize;
558 $more_data = read $self->{fh}, my($dummy), 1;
559 $self->_seekb($writepos);
560 $self->_write_record($data);
562 $writepos += length $data;
565 $self->_seekb($writepos);
566 $self->_write_record($next_block);
568 # There might be leftover data at the end of the file
569 $self->_chop_file if $len_diff < 0;
573 # Insert text D at position S.
574 # Let C = E-S-|D|. If C < 0; die.
575 # Data in [S,S+C) is copied to [S+D,S+D+C) = [S+D,E).
576 # Data in [S+C = E-D, E) is returned. Data in [E, oo) is untouched.
578 # In a later version, don't read the entire intervening area into
579 # memory at once; do the copying block by block.
582 my ($D, $s, $e) = @_;
585 local *FH = $self->{fh};
586 confess "Not enough space to insert $d bytes between $s and $e"
588 confess "[$s,$e) is an invalid insertion range" if $e < $s;
591 read FH, my $buf, $e-$s;
593 $D .= substr($buf, 0, $c, "");
596 $self->_write_record($D);
601 # Like _twrite, but the data-pos-len triple may be repeated; you may
602 # write several chunks. All the writing will be done in
603 # one pass. Chunks SHALL be in ascending order and SHALL NOT overlap.
610 or die "Arguments to _mtwrite did not come in groups of three";
613 my ($data, $pos, $len) = splice @_, 0, 3;
614 my $end = $pos + $len; # The OLD end of the segment to be replaced
615 $data = $unwritten . $data;
616 $delta -= length($unwritten);
618 $pos += $delta; # This is where the data goes now
619 my $dlen = length $data;
621 if ($len >= $dlen) { # the data will fit
622 $self->_write_record($data);
623 $delta += ($dlen - $len); # everything following moves down by this much
624 $data = ""; # All the data in the buffer has been written
626 my $writable = substr($data, 0, $len - $delta, "");
627 $self->_write_record($writable);
628 $delta += ($dlen - $len); # everything following moves down by this much
631 # At this point we've written some but maybe not all of the data.
632 # There might be a gap to close up, or $data might still contain a
633 # bunch of unwritten data that didn't fit.
634 my $ndlen = length $data;
636 $self->_write_record($data);
637 } elsif ($delta < 0) {
638 # upcopy (close up gap)
640 $self->_upcopy($end, $end + $delta, $_[1] - $end);
642 $self->_upcopy($end, $end + $delta);
645 # downcopy (insert data that didn't fit; replace this data in memory
646 # with _later_ data that doesn't fit)
648 $unwritten = $self->_downcopy($data, $end, $_[1] - $end);
650 # Make the file longer to accomodate the last segment that doesn'
651 $unwritten = $self->_downcopy($data, $end);
657 # Copy block of data of length $len from position $spos to position $dpos
658 # $dpos must be <= $spos
660 # If $len is undefined, go all the way to the end of the file
661 # and then truncate it ($spos - $dpos bytes will be removed)
663 my $blocksize = 8192;
664 my ($self, $spos, $dpos, $len) = @_;
666 die "source ($spos) was upstream of destination ($dpos) in _upcopy";
667 } elsif ($dpos == $spos) {
671 while (! defined ($len) || $len > 0) {
672 my $readsize = ! defined($len) ? $blocksize
673 : $len > $blocksize ? $blocksize
676 my $fh = $self->{fh};
677 $self->_seekb($spos);
678 my $bytes_read = read $fh, my($data), $readsize;
679 $self->_seekb($dpos);
684 $self->_write_record($data);
685 $spos += $bytes_read;
686 $dpos += $bytes_read;
687 $len -= $bytes_read if defined $len;
691 # Write $data into a block of length $len at position $pos,
692 # moving everything in the block forwards to make room.
693 # Instead of writing the last length($data) bytes from the block
694 # (because there isn't room for them any longer) return them.
696 my $blocksize = 8192;
697 my ($self, $data, $pos, $len) = @_;
698 my $fh = $self->{fh};
700 while (! defined $len || $len > 0) {
701 my $readsize = ! defined($len) ? $blocksize
702 : $len > $blocksize? $blocksize : $len;
704 read $fh, my($old), $readsize;
707 my $writable = substr($data, 0, $readsize, "");
708 last if $writable eq "";
709 $self->_write_record($writable);
710 $len -= $readsize if defined $len;
716 # Adjust the object data structures following an '_mtwrite'
718 # [$pos, $nrecs, @length] items
719 # indicating that $nrecs records were removed at $recpos (a record offset)
720 # and replaced with records of length @length...
721 # Arguments guarantee that $recpos is strictly increasing.
731 my ($pos, $nrecs, @data) = @$_;
734 # Adjust the offsets of the records after the previous batch up
735 # to the first new one of this batch
736 for my $i ($prev_end+2 .. $pos - 1) {
737 $self->{offsets}[$i] += $delta;
738 $newkey{$i} = $i + $delta_recs;
741 $prev_end = $pos + @data - 1; # last record moved on this pass
743 # Remove the offsets for the removed records;
744 # replace with the offsets for the inserted records
745 my @newoff = ($self->{offsets}[$pos] + $delta);
746 for my $i (0 .. $#data) {
747 my $newlen = length $data[$i];
748 push @newoff, $newoff[$i] + $newlen;
752 for my $i ($pos .. $pos+$nrecs-1) {
753 last if $i+1 > $#{$self->{offsets}};
754 my $oldlen = $self->{offsets}[$i+1] - $self->{offsets}[$i];
758 # # also this data has changed, so update it in the cache
759 # for (0 .. $#data) {
760 # $self->{cache}->update($pos + $_, $data[$_]);
763 # my @oldkeys = grep $_ >= $pos + @data, $self->{cache}->ckeys;
764 # my @newkeys = map $_ + $delta_recs, @oldkeys;
765 # $self->{cache}->rekey(\@oldkeys, \@newkeys);
768 # replace old offsets with new
769 splice @{$self->{offsets}}, $pos, $nrecs+1, @newoff;
770 # What if we just spliced out the end of the offsets table?
771 # shouldn't we clear $self->{eof}? Test for this XXX BUG TODO
773 $delta_recs += @data - $nrecs; # net change in total number of records
776 # The trailing records at the very end of the file
778 for my $i ($prev_end+2 .. $#{$self->{offsets}}) {
779 $self->{offsets}[$i] += $delta;
783 # If we scrubbed out all known offsets, regenerate the trivial table
784 # that knows that the file does indeed start at 0.
785 $self->{offsets}[0] = 0 unless @{$self->{offsets}};
786 # If the file got longer, the offsets table is no longer complete
787 # $self->{eof} = 0 if $delta_recs > 0;
789 # Now there might be too much data in the cache, if we spliced out
790 # some short records and spliced in some long ones. If so, flush
795 # If a record does not already end with the appropriate terminator
796 # string, append one.
800 $_ = "" unless defined $_;
801 $_ .= $self->{recsep}
802 unless substr($_, - $self->{recseplen}) eq $self->{recsep};
807 ################################################################
809 # Basic read, write, and seek
812 # seek to the beginning of record #$n
813 # Assumes that the offsets table is already correctly populated
815 # Note that $n=-1 has a special meaning here: It means the start of
816 # the last known record; this may or may not be the very last record
817 # in the file, depending on whether the offsets table is fully populated.
821 my $o = $self->{offsets}[$n];
823 or confess("logic error: undefined offset for record $n");
824 seek $self->{fh}, $o, SEEK_SET
825 or confess "Couldn't seek filehandle: $!"; # "Should never happen."
828 # seek to byte $b in the file
831 seek $self->{fh}, $b, SEEK_SET
832 or die "Couldn't seek filehandle: $!"; # "Should never happen."
835 # populate the offsets table up to the beginning of record $n
836 # return the offset of record $n
837 sub _fill_offsets_to {
840 return $self->{offsets}[$n] if $self->{eof};
842 my $fh = $self->{fh};
843 local *OFF = $self->{offsets};
846 until ($#OFF >= $n) {
847 $self->_seek(-1); # tricky -- see comment at _seek
848 $rec = $self->_read_record;
850 push @OFF, int(tell $fh); # Tels says that int() saves memory here
853 return; # It turns out there is no such record
857 # we have now read all the records up to record n-1,
858 # so we can return the offset of record n
865 my $fh = $self->{fh};
866 local *OFF = $self->{offsets};
868 $self->_seek(-1); # tricky -- see comment at _seek
870 # Tels says that inlining read_record() would make this loop
871 # five times faster. 20030508
872 while ( defined $self->_read_record()) {
873 # int() saves us memory here
874 push @OFF, int(tell $fh);
881 # assumes that $rec is already suitably terminated
883 my ($self, $rec) = @_;
884 my $fh = $self->{fh};
887 or die "Couldn't write record: $!"; # "Should never happen."
888 # $self->{_written} += length($rec);
894 { local $/ = $self->{recsep};
895 my $fh = $self->{fh};
898 return unless defined $rec;
899 if (! $self->{sawlastrec} &&
900 substr($rec, -$self->{recseplen}) ne $self->{recsep}) {
901 # improperly terminated final record --- quietly fix it.
902 # my $ac = substr($rec, -$self->{recseplen});
904 $self->{sawlastrec} = 1;
905 unless ($self->{rdonly}) {
907 my $fh = $self->{fh};
908 print $fh $self->{recsep};
910 $rec .= $self->{recsep};
912 # $self->{_read} += length($rec) if defined $rec;
918 @{$self}{'_read', '_written'};
921 ################################################################
923 # Read cache management
927 $self->{cache}->reduce_size_to($self->{memory} - $self->{deferred_s});
930 sub _cache_too_full {
932 $self->{cache}->bytes + $self->{deferred_s} >= $self->{memory};
935 ################################################################
937 # File custodial services
941 # We have read to the end of the file and have the offsets table
942 # entirely populated. Now we need to write a new record beyond
943 # the end of the file. We prepare for this by writing
944 # empty records into the file up to the position we want
946 # assumes that the offsets table already contains the offset of record $n,
947 # if it exists, and extends to the end of the file if not.
948 sub _extend_file_to {
950 $self->_seek(-1); # position after the end of the last record
951 my $pos = $self->{offsets}[-1];
953 # the offsets table has one entry more than the total number of records
954 my $extras = $n - $#{$self->{offsets}};
956 # Todo : just use $self->{recsep} x $extras here?
957 while ($extras-- > 0) {
958 $self->_write_record($self->{recsep});
959 push @{$self->{offsets}}, int(tell $self->{fh});
963 # Truncate the file at the current position
966 truncate $self->{fh}, tell($self->{fh});
970 # compute the size of a buffer suitable for moving
971 # all the data in a file forward $n bytes
972 # ($n may be negative)
973 # The result should be at least $n.
976 return 8192 if $n <= 0;
978 $b += 8192 if $n & 8191;
982 ################################################################
984 # Miscellaneous public methods
989 my ($self, $op) = @_;
991 my $pack = ref $self;
992 croak "Usage: $pack\->flock([OPERATION])";
994 my $fh = $self->{fh};
995 $op = LOCK_EX unless defined $op;
996 my $locked = flock $fh, $op;
998 if ($locked && ($op & (LOCK_EX | LOCK_SH))) {
999 # If you're locking the file, then presumably it's because
1000 # there might have been a write access by another process.
1001 # In that case, the read cache contents and the offsets table
1002 # might be invalid, so discard them. 20030508
1003 $self->{offsets} = [0];
1004 $self->{cache}->empty;
1010 # Get/set autochomp option
1014 my $old = $self->{autochomp};
1015 $self->{autochomp} = shift;
1022 # Get offset table entries; returns offset of nth record
1024 my ($self, $n) = @_;
1026 if ($#{$self->{offsets}} < $n) {
1027 return if $self->{eof}; # request for record beyond the end of file
1028 my $o = $self->_fill_offsets_to($n);
1029 # If it's still undefined, there is no such record, so return 'undef'
1030 return unless defined $o;
1033 $self->{offsets}[$n];
1036 sub discard_offsets {
1038 $self->{offsets} = [0];
1041 ################################################################
1043 # Matters related to deferred writing
1049 $self->_stop_autodeferring;
1050 @{$self->{ad_history}} = ();
1054 # Flush deferred writes
1056 # This could be better optimized to write the file in one pass, instead
1057 # of one pass per block of records. But that will require modifications
1058 # to _twrite, so I should have a good _twrite test suite first.
1068 my @writable = sort {$a<=>$b} (keys %{$self->{deferred}});
1071 # gather all consecutive records from the front of @writable
1072 my $first_rec = shift @writable;
1073 my $last_rec = $first_rec+1;
1074 ++$last_rec, shift @writable while @writable && $last_rec == $writable[0];
1076 $self->_fill_offsets_to($last_rec);
1077 $self->_extend_file_to($last_rec);
1078 $self->_splice($first_rec, $last_rec-$first_rec+1,
1079 @{$self->{deferred}}{$first_rec .. $last_rec});
1082 $self->_discard; # clear out defered-write-cache
1087 my @writable = sort {$a<=>$b} (keys %{$self->{deferred}});
1092 # gather all consecutive records from the front of @writable
1093 my $first_rec = shift @writable;
1094 my $last_rec = $first_rec+1;
1095 ++$last_rec, shift @writable while @writable && $last_rec == $writable[0];
1097 my $end = $self->_fill_offsets_to($last_rec+1);
1098 if (not defined $end) {
1099 $self->_extend_file_to($last_rec);
1100 $end = $self->{offsets}[$last_rec];
1102 my ($start) = $self->{offsets}[$first_rec];
1104 join("", @{$self->{deferred}}{$first_rec .. $last_rec}), # data
1106 $end-$start; # length
1107 push @adjust, [$first_rec, # starting at this position...
1108 $last_rec-$first_rec+1, # this many records...
1109 # are replaced with these...
1110 @{$self->{deferred}}{$first_rec .. $last_rec},
1114 $self->_mtwrite(@args); # write multiple record groups
1115 $self->_discard; # clear out defered-write-cache
1116 $self->_oadjust(@adjust);
1119 # Discard deferred writes and disable future deferred writes
1126 # Discard deferred writes, but retain old deferred writing mode
1129 %{$self->{deferred}} = ();
1130 $self->{deferred_s} = 0;
1131 $self->{deferred_max} = -1;
1132 $self->{cache}->set_limit($self->{memory});
1135 # Deferred writing is enabled, either explicitly ($self->{defer})
1136 # or automatically ($self->{autodeferring})
1139 $self->{defer} || $self->{autodeferring};
1142 # The largest record number of any deferred record
1145 return $self->{deferred_max} if defined $self->{deferred_max};
1147 for my $key (keys %{$self->{deferred}}) {
1148 $max = $key if $key > $max;
1150 $self->{deferred_max} = $max;
1154 ################################################################
1156 # Matters related to autodeferment
1159 # Get/set autodefer option
1163 my $old = $self->{autodefer};
1164 $self->{autodefer} = shift;
1166 $self->_stop_autodeferring;
1167 @{$self->{ad_history}} = ();
1175 # The user is trying to store record #$n Record that in the history,
1176 # and then enable (or disable) autodeferment if that seems useful.
1177 # Note that it's OK for $n to be a non-number, as long as the function
1178 # is prepared to deal with that. Nobody else looks at the ad_history.
1180 # Now, what does the ad_history mean, and what is this function doing?
1181 # Essentially, the idea is to enable autodeferring when we see that the
1182 # user has made three consecutive STORE calls to three consecutive records.
1183 # ("Three" is actually ->{autodefer_threshhold}.)
1184 # A STORE call for record #$n inserts $n into the autodefer history,
1185 # and if the history contains three consecutive records, we enable
1186 # autodeferment. An ad_history of [X, Y] means that the most recent
1187 # STOREs were for records X, X+1, ..., Y, in that order.
1189 # Inserting a nonconsecutive number erases the history and starts over.
1191 # Performing a special operation like SPLICE erases the history.
1193 # There's one special case: CLEAR means that CLEAR was just called.
1194 # In this case, we prime the history with [-2, -1] so that if the next
1195 # write is for record 0, autodeferring goes on immediately. This is for
1196 # the common special case of "@a = (...)".
1198 sub _annotate_ad_history {
1199 my ($self, $n) = @_;
1200 return unless $self->{autodefer}; # feature is disabled
1201 return if $self->{defer}; # already in explicit defer mode
1202 return unless $self->{offsets}[-1] >= $self->{autodefer_filelen_threshhold};
1204 local *H = $self->{ad_history};
1205 if ($n eq 'CLEAR') {
1206 @H = (-2, -1); # prime the history with fake records
1207 $self->_stop_autodeferring;
1208 } elsif ($n =~ /^\d+$/) {
1212 if ($H[1] == $n-1) { # another consecutive record
1214 if ($H[1] - $H[0] + 1 >= $self->{autodefer_threshhold}) {
1215 $self->{autodeferring} = 1;
1217 } else { # nonconsecutive- erase and start over
1219 $self->_stop_autodeferring;
1222 } else { # SPLICE or STORESIZE or some such
1224 $self->_stop_autodeferring;
1228 # If autodeferring was enabled, cut it out and discard the history
1229 sub _stop_autodeferring {
1231 if ($self->{autodeferring}) {
1234 $self->{autodeferring} = 0;
1237 ################################################################
1240 # This is NOT a method. It is here for two reasons:
1241 # 1. To factor a fairly complicated block out of the constructor
1242 # 2. To provide access for the test suite, which need to be sure
1243 # files are being written properly.
1244 sub _default_recsep {
1246 if ($^O eq 'MSWin32') { # Dos too?
1247 # Windows users expect files to be terminated with \r\n
1248 # But $/ is set to \n instead
1249 # Note that this also transforms \n\n into \r\n\r\n.
1250 # That is a feature.
1251 $recsep =~ s/\n/\r\n/g;
1256 # Utility function for _check_integrity
1264 # Given a file, make sure the cache is consistent with the
1265 # file contents and the internal data structures are consistent with
1266 # each other. Returns true if everything checks out, false if not
1268 # The $file argument is no longer used. It is retained for compatibility
1269 # with the existing test suite.
1270 sub _check_integrity {
1271 my ($self, $file, $warn) = @_;
1272 my $rsl = $self->{recseplen};
1273 my $rs = $self->{recsep};
1275 local *_; # local $_ does not work here
1276 local $DIAGNOSTIC = 1;
1278 if (not defined $rs) {
1279 _ci_warn("recsep is undef!");
1281 } elsif ($rs eq "") {
1282 _ci_warn("recsep is empty!");
1284 } elsif ($rsl != length $rs) {
1285 my $ln = length $rs;
1286 _ci_warn("recsep <$rs> has length $ln, should be $rsl");
1290 if (not defined $self->{offsets}[0]) {
1291 _ci_warn("offset 0 is missing!");
1294 } elsif ($self->{offsets}[0] != 0) {
1295 _ci_warn("rec 0: offset <$self->{offsets}[0]> s/b 0!");
1301 local *F = $self->{fh};
1302 seek F, 0, SEEK_SET;
1308 my $cached = $self->{cache}->_produce($n);
1309 my $offset = $self->{offsets}[$.];
1311 if (defined $offset && $offset != $ao) {
1312 _ci_warn("rec $n: offset <$offset> actual <$ao>");
1315 if (defined $cached && $_ ne $cached && ! $self->{deferred}{$n}) {
1317 _ci_warn("rec $n: cached <$cached> actual <$_>");
1319 if (defined $cached && substr($cached, -$rsl) ne $rs) {
1321 _ci_warn("rec $n in the cache is missing the record separator");
1323 if (! defined $offset && $self->{eof}) {
1325 _ci_warn("The offset table was marked complete, but it is missing element $.");
1328 if (@{$self->{offsets}} > $.+1) {
1330 my $n = @{$self->{offsets}};
1331 _ci_warn("The offset table has $n items, but the file has only $.");
1334 my $deferring = $self->_is_deferring;
1335 for my $n ($self->{cache}->ckeys) {
1336 my $r = $self->{cache}->_produce($n);
1337 $cached += length($r);
1338 next if $n+1 <= $.; # checked this already
1339 _ci_warn("spurious caching of record $n");
1342 my $b = $self->{cache}->bytes;
1343 if ($cached != $b) {
1344 _ci_warn("cache size is $b, should be $cached");
1349 # That cache has its own set of tests
1350 $good = 0 unless $self->{cache}->_check_integrity;
1352 # Now let's check the deferbuffer
1353 # Unless deferred writing is enabled, it should be empty
1354 if (! $self->_is_deferring && %{$self->{deferred}}) {
1355 _ci_warn("deferred writing disabled, but deferbuffer nonempty");
1359 # Any record in the deferbuffer should *not* be present in the readcache
1361 while (my ($n, $r) = each %{$self->{deferred}}) {
1362 $deferred_s += length($r);
1363 if (defined $self->{cache}->_produce($n)) {
1364 _ci_warn("record $n is in the deferbuffer *and* the readcache");
1367 if (substr($r, -$rsl) ne $rs) {
1368 _ci_warn("rec $n in the deferbuffer is missing the record separator");
1373 # Total size of deferbuffer should match internal total
1374 if ($deferred_s != $self->{deferred_s}) {
1375 _ci_warn("buffer size is $self->{deferred_s}, should be $deferred_s");
1379 # Total size of deferbuffer should not exceed the specified limit
1380 if ($deferred_s > $self->{dw_size}) {
1381 _ci_warn("buffer size is $self->{deferred_s} which exceeds the limit of $self->{dw_size}");
1385 # Total size of cached data should not exceed the specified limit
1386 if ($deferred_s + $cached > $self->{memory}) {
1387 my $total = $deferred_s + $cached;
1388 _ci_warn("total stored data size is $total which exceeds the limit of $self->{memory}");
1392 # Stuff related to autodeferment
1393 if (!$self->{autodefer} && @{$self->{ad_history}}) {
1394 _ci_warn("autodefer is disabled, but ad_history is nonempty");
1397 if ($self->{autodeferring} && $self->{defer}) {
1398 _ci_warn("both autodeferring and explicit deferring are active");
1401 if (@{$self->{ad_history}} == 0) {
1402 # That's OK, no additional tests required
1403 } elsif (@{$self->{ad_history}} == 2) {
1404 my @non_number = grep !/^-?\d+$/, @{$self->{ad_history}};
1408 $msg = "ad_history contains non-numbers (@{$self->{ad_history}})";
1412 } elsif ($self->{ad_history}[1] < $self->{ad_history}[0]) {
1413 _ci_warn("ad_history has nonsensical values @{$self->{ad_history}}");
1417 _ci_warn("ad_history has bad length <@{$self->{ad_history}}>");
1424 ################################################################
1430 package Tie::File::Cache;
1431 $Tie::File::Cache::VERSION = $Tie::File::VERSION;
1432 use Carp ':DEFAULT', 'confess';
1438 #sub STAT () { 4 } # Array with request statistics for each record
1439 #sub MISS () { 5 } # Total number of cache misses
1440 #sub REQ () { 6 } # Total number of cache requests
1444 my ($pack, $max) = @_;
1446 croak "missing argument to ->new" unless defined $max;
1448 bless $self => $pack;
1449 @$self = (Tie::File::Heap->new($self), {}, $max, 0);
1454 my ($self, $n) = @_;
1459 my ($self, $n) = @_;
1463 # For internal use only
1464 # Will be called by the heap structure to notify us that a certain
1465 # piece of data has moved from one heap element to another.
1466 # $k is the hash key of the item
1467 # $n is the new index into the heap at which it is stored
1468 # If $n is undefined, the item has been removed from the heap.
1470 my ($self, $k, $n) = @_;
1472 $self->[HASH]{$k} = $n;
1474 delete $self->[HASH]{$k};
1479 my ($self, $key, $val) = @_;
1481 croak "missing argument to ->insert" unless defined $key;
1482 unless (defined $self->[MAX]) {
1483 confess "undefined max" ;
1485 confess "undefined val" unless defined $val;
1486 return if length($val) > $self->[MAX];
1488 # if ($self->[STAT]) {
1489 # $self->[STAT][$key] = 1;
1493 my $oldnode = $self->[HASH]{$key};
1494 if (defined $oldnode) {
1495 my $oldval = $self->[HEAP]->set_val($oldnode, $val);
1496 $self->[BYTES] -= length($oldval);
1498 $self->[HEAP]->insert($key, $val);
1500 $self->[BYTES] += length($val);
1501 $self->flush if $self->[BYTES] > $self->[MAX];
1506 my $old_data = $self->[HEAP]->popheap;
1507 return unless defined $old_data;
1508 $self->[BYTES] -= length $old_data;
1513 my ($self, @keys) = @_;
1516 # if ($self->[STAT]) {
1517 # for my $key (@keys) {
1518 # $self->[STAT][$key] = 0;
1523 for my $key (@keys) {
1524 next unless exists $self->[HASH]{$key};
1525 my $old_data = $self->[HEAP]->remove($self->[HASH]{$key});
1526 $self->[BYTES] -= length $old_data;
1527 push @result, $old_data;
1533 my ($self, $key) = @_;
1535 croak "missing argument to ->lookup" unless defined $key;
1537 # if ($self->[STAT]) {
1538 # $self->[MISS]++ if $self->[STAT][$key]++ == 0;
1540 # my $hit_rate = 1 - $self->[MISS] / $self->[REQ];
1541 # # Do some testing to determine this threshhold
1542 # $#$self = STAT - 1 if $hit_rate > 0.20;
1545 if (exists $self->[HASH]{$key}) {
1546 $self->[HEAP]->lookup($self->[HASH]{$key});
1552 # For internal use only
1554 my ($self, $key) = @_;
1555 my $loc = $self->[HASH]{$key};
1556 return unless defined $loc;
1557 $self->[HEAP][$loc][2];
1560 # For internal use only
1562 my ($self, $key) = @_;
1563 $self->[HEAP]->promote($self->[HASH]{$key});
1568 %{$self->[HASH]} = ();
1570 $self->[HEAP]->empty;
1571 # @{$self->[STAT]} = ();
1572 # $self->[MISS] = 0;
1578 keys %{$self->[HASH]} == 0;
1582 my ($self, $key, $val) = @_;
1584 croak "missing argument to ->update" unless defined $key;
1585 if (length($val) > $self->[MAX]) {
1586 my ($oldval) = $self->remove($key);
1587 $self->[BYTES] -= length($oldval) if defined $oldval;
1588 } elsif (exists $self->[HASH]{$key}) {
1589 my $oldval = $self->[HEAP]->set_val($self->[HASH]{$key}, $val);
1590 $self->[BYTES] += length($val);
1591 $self->[BYTES] -= length($oldval) if defined $oldval;
1593 $self->[HEAP]->insert($key, $val);
1594 $self->[BYTES] += length($val);
1600 my ($self, $okeys, $nkeys) = @_;
1603 @map{@$okeys} = @$nkeys;
1604 croak "missing argument to ->rekey" unless defined $nkeys;
1605 croak "length mismatch in ->rekey arguments" unless @$nkeys == @$okeys;
1606 my %adjusted; # map new keys to heap indices
1607 # You should be able to cut this to one loop TODO XXX
1608 for (0 .. $#$okeys) {
1609 $adjusted{$nkeys->[$_]} = delete $self->[HASH]{$okeys->[$_]};
1611 while (my ($nk, $ix) = each %adjusted) {
1612 # @{$self->[HASH]}{keys %adjusted} = values %adjusted;
1613 $self->[HEAP]->rekey($ix, $nk);
1614 $self->[HASH]{$nk} = $ix;
1620 my @a = keys %{$self->[HASH]};
1624 # Return total amount of cached data
1630 # Expire oldest item from cache until cache size is smaller than $max
1631 sub reduce_size_to {
1632 my ($self, $max) = @_;
1633 until ($self->[BYTES] <= $max) {
1634 # Note that Tie::File::Cache::expire has been inlined here
1635 my $old_data = $self->[HEAP]->popheap;
1636 return unless defined $old_data;
1637 $self->[BYTES] -= length $old_data;
1641 # Why not just $self->reduce_size_to($self->[MAX])?
1642 # Try this when things stabilize TODO XXX
1643 # If the cache is too full, expire the oldest records
1646 $self->reduce_size_to($self->[MAX]) if $self->[BYTES] > $self->[MAX];
1649 # For internal use only
1652 $self->[HEAP]->expire_order;
1655 BEGIN { *_ci_warn = \&Tie::File::_ci_warn }
1657 sub _check_integrity { # For CACHE
1662 $self->[HEAP]->_check_integrity or $good = 0;
1666 for my $k (keys %{$self->[HASH]}) {
1667 if ($k ne '0' && $k !~ /^[1-9][0-9]*$/) {
1669 _ci_warn "Cache hash key <$k> is non-numeric";
1672 my $h = $self->[HASH]{$k};
1675 _ci_warn "Heap index number for key $k is undefined";
1678 _ci_warn "Heap index number for key $k is zero";
1680 my $j = $self->[HEAP][$h];
1683 _ci_warn "Heap contents key $k (=> $h) are undefined";
1685 $bytes += length($j->[2]);
1686 if ($k ne $j->[1]) {
1688 _ci_warn "Heap contents key $k (=> $h) is $j->[1], should be $k";
1695 if ($bytes != $self->[BYTES]) {
1697 _ci_warn "Total data in cache is $bytes, expected $self->[BYTES]";
1701 if ($bytes > $self->[MAX]) {
1703 _ci_warn "Total data in cache is $bytes, exceeds maximum $self->[MAX]";
1711 $self->[HEAP] = undef; # Bye bye heap
1714 ################################################################
1718 # Heap data structure for use by cache LRU routines
1720 package Tie::File::Heap;
1721 use Carp ':DEFAULT', 'confess';
1722 $Tie::File::Heap::VERSION = $Tie::File::Cache::VERSION;
1728 my ($pack, $cache) = @_;
1729 die "$pack: Parent cache object $cache does not support _heap_move method"
1730 unless eval { $cache->can('_heap_move') };
1731 my $self = [[0,$cache,0]];
1732 bless $self => $pack;
1735 # Allocate a new sequence number, larger than all previously allocated numbers
1770 $self->[0][0] = 0; # might as well reset the sequence numbers
1773 # notify the parent cache object that we moved something
1776 $self->_cache->_heap_move(@_);
1779 # Insert a piece of data into the heap with the indicated sequence number.
1780 # The item with the smallest sequence number is always at the top.
1781 # If no sequence number is specified, allocate a new one and insert the
1782 # item at the bottom.
1784 my ($self, $key, $data, $seq) = @_;
1785 $seq = $self->_nseq unless defined $seq;
1786 $self->_insert_new([$seq, $key, $data]);
1789 # Insert a new, fresh item at the bottom of the heap
1791 my ($self, $item) = @_;
1793 $i = int($i/2) until defined $self->[$i/2];
1794 $self->[$i] = $item;
1795 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1799 # Insert [$data, $seq] pair at or below item $i in the heap.
1800 # If $i is omitted, default to 1 (the top element.)
1802 my ($self, $item, $i) = @_;
1803 # $self->_check_loc($i) if defined $i;
1804 $i = 1 unless defined $i;
1805 until (! defined $self->[$i]) {
1806 if ($self->[$i][SEQ] > $item->[SEQ]) { # inserted item is older
1807 ($self->[$i], $item) = ($item, $self->[$i]);
1808 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1810 # If either is undefined, go that way. Otherwise, choose at random
1812 $dir = 0 if !defined $self->[2*$i];
1813 $dir = 1 if !defined $self->[2*$i+1];
1814 $dir = int(rand(2)) unless defined $dir;
1817 $self->[$i] = $item;
1818 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1822 # Remove the item at node $i from the heap, moving child items upwards.
1823 # The item with the smallest sequence number is always at the top.
1824 # Moving items upwards maintains this condition.
1825 # Return the removed item. Return undef if there was no item at node $i.
1827 my ($self, $i) = @_;
1828 $i = 1 unless defined $i;
1829 my $top = $self->[$i];
1830 return unless defined $top;
1833 my ($L, $R) = (2*$i, 2*$i+1);
1835 # If either is undefined, go the other way.
1836 # Otherwise, go towards the smallest.
1837 last unless defined $self->[$L] || defined $self->[$R];
1838 $ii = $R if not defined $self->[$L];
1839 $ii = $L if not defined $self->[$R];
1840 unless (defined $ii) {
1841 $ii = $self->[$L][SEQ] < $self->[$R][SEQ] ? $L : $R;
1844 $self->[$i] = $self->[$ii]; # Promote child to fill vacated spot
1845 $self->[0][1]->_heap_move($self->[$i][KEY], $i);
1846 $i = $ii; # Fill new vacated spot
1848 $self->[0][1]->_heap_move($top->[KEY], undef);
1859 # set the sequence number of the indicated item to a higher number
1860 # than any other item in the heap, and bubble the item down to the
1863 my ($self, $n) = @_;
1864 # $self->_check_loc($n);
1865 $self->[$n][SEQ] = $self->_nseq;
1868 my ($L, $R) = (2*$i, 2*$i+1);
1870 last unless defined $self->[$L] || defined $self->[$R];
1871 $dir = $R unless defined $self->[$L];
1872 $dir = $L unless defined $self->[$R];
1873 unless (defined $dir) {
1874 $dir = $self->[$L][SEQ] < $self->[$R][SEQ] ? $L : $R;
1876 @{$self}[$i, $dir] = @{$self}[$dir, $i];
1878 $self->[0][1]->_heap_move($self->[$_][KEY], $_) if defined $self->[$_];
1884 # Return item $n from the heap, promoting its LRU status
1886 my ($self, $n) = @_;
1887 # $self->_check_loc($n);
1888 my $val = $self->[$n];
1894 # Assign a new value for node $n, promoting it to the bottom of the heap
1896 my ($self, $n, $val) = @_;
1897 # $self->_check_loc($n);
1898 my $oval = $self->[$n][DAT];
1899 $self->[$n][DAT] = $val;
1904 # The hask key has changed for an item;
1905 # alter the heap's record of the hash key
1907 my ($self, $n, $new_key) = @_;
1908 # $self->_check_loc($n);
1909 $self->[$n][KEY] = $new_key;
1913 my ($self, $n) = @_;
1914 unless (1 || defined $self->[$n]) {
1915 confess "_check_loc($n) failed";
1919 BEGIN { *_ci_warn = \&Tie::File::_ci_warn }
1921 sub _check_integrity {
1926 unless (eval {$self->[0][1]->isa("Tie::File::Cache")}) {
1927 _ci_warn "Element 0 of heap corrupt";
1930 $good = 0 unless $self->_satisfies_heap_condition(1);
1931 for my $i (2 .. $#{$self}) {
1932 my $p = int($i/2); # index of parent node
1933 if (defined $self->[$i] && ! defined $self->[$p]) {
1934 _ci_warn "Element $i of heap defined, but parent $p isn't";
1938 if (defined $self->[$i]) {
1939 if ($seq{$self->[$i][SEQ]}) {
1940 my $seq = $self->[$i][SEQ];
1941 _ci_warn "Nodes $i and $seq{$seq} both have SEQ=$seq";
1944 $seq{$self->[$i][SEQ]} = $i;
1952 sub _satisfies_heap_condition {
1958 next unless defined $self->[$c];
1959 if ($self->[$n][SEQ] >= $self->[$c]) {
1960 _ci_warn "Node $n of heap does not predate node $c";
1963 $good = 0 unless $self->_satisfies_heap_condition($c);
1968 # Return a list of all the values, sorted by expiration order
1971 my @nodes = sort {$a->[SEQ] <=> $b->[SEQ]} $self->_nodes;
1972 map { $_->[KEY] } @nodes;
1978 return unless defined $self->[$i];
1979 ($self->[$i], $self->_nodes($i*2), $self->_nodes($i*2+1));
1982 "Cogito, ergo sum."; # don't forget to return a true value from the file
1988 Tie::File - Access the lines of a disk file via a Perl array
1992 # This file documents Tie::File version 0.95
1995 tie @array, 'Tie::File', filename or die ...;
1997 $array[13] = 'blah'; # line 13 of the file is now 'blah'
1998 print $array[42]; # display line 42 of the file
2000 $n_recs = @array; # how many records are in the file?
2001 $#array -= 2; # chop two records off the end
2005 s/PERL/Perl/g; # Replace PERL with Perl everywhere in the file
2008 # These are just like regular push, pop, unshift, shift, and splice
2009 # Except that they modify the file in the way you would expect
2011 push @array, new recs...;
2012 my $r1 = pop @array;
2013 unshift @array, new recs...;
2014 my $r2 = shift @array;
2015 @old_recs = splice @array, 3, 7, new recs...;
2017 untie @array; # all finished
2022 C<Tie::File> represents a regular text file as a Perl array. Each
2023 element in the array corresponds to a record in the file. The first
2024 line of the file is element 0 of the array; the second line is element
2027 The file is I<not> loaded into memory, so this will work even for
2030 Changes to the array are reflected in the file immediately.
2032 Lazy people and beginners may now stop reading the manual.
2036 What is a 'record'? By default, the meaning is the same as for the
2037 C<E<lt>...E<gt>> operator: It's a string terminated by C<$/>, which is
2038 probably C<"\n">. (Minor exception: on DOS and Win32 systems, a
2039 'record' is a string terminated by C<"\r\n">.) You may change the
2040 definition of "record" by supplying the C<recsep> option in the C<tie>
2043 tie @array, 'Tie::File', $file, recsep => 'es';
2045 This says that records are delimited by the string C<es>. If the file
2046 contained the following data:
2048 Curse these pesky flies!\n
2050 then the C<@array> would appear to have four elements:
2057 An undefined value is not permitted as a record separator. Perl's
2058 special "paragraph mode" semantics (E<agrave> la C<$/ = "">) are not
2061 Records read from the tied array do not have the record separator
2062 string on the end; this is to allow
2064 $array[17] .= "extra";
2066 to work as expected.
2068 (See L<"autochomp">, below.) Records stored into the array will have
2069 the record separator string appended before they are written to the
2070 file, if they don't have one already. For example, if the record
2071 separator string is C<"\n">, then the following two lines do exactly
2074 $array[17] = "Cherry pie";
2075 $array[17] = "Cherry pie\n";
2077 The result is that the contents of line 17 of the file will be
2078 replaced with "Cherry pie"; a newline character will separate line 17
2079 from line 18. This means that this code will do nothing:
2083 Because the C<chomp>ed value will have the separator reattached when
2084 it is written back to the file. There is no way to create a file
2085 whose trailing record separator string is missing.
2087 Inserting records that I<contain> the record separator string is not
2088 supported by this module. It will probably produce a reasonable
2089 result, but what this result will be may change in a future version.
2090 Use 'splice' to insert records or to replace one record with several.
2094 Normally, array elements have the record separator removed, so that if
2095 the file contains the text
2101 the tied array will appear to contain C<("Gold", "Frankincense",
2102 "Myrrh")>. If you set C<autochomp> to a false value, the record
2103 separator will not be removed. If the file above was tied with
2105 tie @gifts, "Tie::File", $gifts, autochomp => 0;
2107 then the array C<@gifts> would appear to contain C<("Gold\n",
2108 "Frankincense\n", "Myrrh\n")>, or (on Win32 systems) C<("Gold\r\n",
2109 "Frankincense\r\n", "Myrrh\r\n")>.
2113 Normally, the specified file will be opened for read and write access,
2114 and will be created if it does not exist. (That is, the flags
2115 C<O_RDWR | O_CREAT> are supplied in the C<open> call.) If you want to
2116 change this, you may supply alternative flags in the C<mode> option.
2117 See L<Fcntl> for a listing of available flags.
2120 # open the file if it exists, but fail if it does not exist
2122 tie @array, 'Tie::File', $file, mode => O_RDWR;
2124 # create the file if it does not exist
2125 use Fcntl 'O_RDWR', 'O_CREAT';
2126 tie @array, 'Tie::File', $file, mode => O_RDWR | O_CREAT;
2128 # open an existing file in read-only mode
2129 use Fcntl 'O_RDONLY';
2130 tie @array, 'Tie::File', $file, mode => O_RDONLY;
2132 Opening the data file in write-only or append mode is not supported.
2136 This is an upper limit on the amount of memory that C<Tie::File> will
2137 consume at any time while managing the file. This is used for two
2138 things: managing the I<read cache> and managing the I<deferred write
2141 Records read in from the file are cached, to avoid having to re-read
2142 them repeatedly. If you read the same record twice, the first time it
2143 will be stored in memory, and the second time it will be fetched from
2144 the I<read cache>. The amount of data in the read cache will not
2145 exceed the value you specified for C<memory>. If C<Tie::File> wants
2146 to cache a new record, but the read cache is full, it will make room
2147 by expiring the least-recently visited records from the read cache.
2149 The default memory limit is 2Mib. You can adjust the maximum read
2150 cache size by supplying the C<memory> option. The argument is the
2151 desired cache size, in bytes.
2153 # I have a lot of memory, so use a large cache to speed up access
2154 tie @array, 'Tie::File', $file, memory => 20_000_000;
2156 Setting the memory limit to 0 will inhibit caching; records will be
2157 fetched from disk every time you examine them.
2159 The C<memory> value is not an absolute or exact limit on the memory
2160 used. C<Tie::File> objects contains some structures besides the read
2161 cache and the deferred write buffer, whose sizes are not charged
2164 The cache itself consumes about 310 bytes per cached record, so if
2165 your file has many short records, you may want to decrease the cache
2166 memory limit, or else the cache overhead may exceed the size of the
2172 (This is an advanced feature. Skip this section on first reading.)
2174 If you use deferred writing (See L<"Deferred Writing">, below) then
2175 data you write into the array will not be written directly to the
2176 file; instead, it will be saved in the I<deferred write buffer> to be
2177 written out later. Data in the deferred write buffer is also charged
2178 against the memory limit you set with the C<memory> option.
2180 You may set the C<dw_size> option to limit the amount of data that can
2181 be saved in the deferred write buffer. This limit may not exceed the
2182 total memory limit. For example, if you set C<dw_size> to 1000 and
2183 C<memory> to 2500, that means that no more than 1000 bytes of deferred
2184 writes will be saved up. The space available for the read cache will
2185 vary, but it will always be at least 1500 bytes (if the deferred write
2186 buffer is full) and it could grow as large as 2500 bytes (if the
2187 deferred write buffer is empty.)
2189 If you don't specify a C<dw_size>, it defaults to the entire memory
2192 =head2 Option Format
2194 C<-mode> is a synonym for C<mode>. C<-recsep> is a synonym for
2195 C<recsep>. C<-memory> is a synonym for C<memory>. You get the
2198 =head1 Public Methods
2200 The C<tie> call returns an object, say C<$o>. You may call
2202 $rec = $o->FETCH($n);
2203 $o->STORE($n, $rec);
2205 to fetch or store the record at line C<$n>, respectively; similarly
2206 the other tied array methods. (See L<perltie> for details.) You may
2207 also call the following methods on this object:
2213 will lock the tied file. C<MODE> has the same meaning as the second
2214 argument to the Perl built-in C<flock> function; for example
2215 C<LOCK_SH> or C<LOCK_EX | LOCK_NB>. (These constants are provided by
2216 the C<use Fcntl ':flock'> declaration.)
2218 C<MODE> is optional; the default is C<LOCK_EX>.
2220 C<Tie::File> maintains an internal table of the byte offset of each
2221 record it has seen in the file.
2223 When you use C<flock> to lock the file, C<Tie::File> assumes that the
2224 read cache is no longer trustworthy, because another process might
2225 have modified the file since the last time it was read. Therefore, a
2226 successful call to C<flock> discards the contents of the read cache
2227 and the internal record offset table.
2229 C<Tie::File> promises that the following sequence of operations will
2232 my $o = tie @array, "Tie::File", $filename;
2235 In particular, C<Tie::File> will I<not> read or write the file during
2236 the C<tie> call. (Exception: Using C<mode =E<gt> O_TRUNC> will, of
2237 course, erase the file during the C<tie> call. If you want to do this
2238 safely, then open the file without C<O_TRUNC>, lock the file, and use
2241 The best way to unlock a file is to discard the object and untie the
2242 array. It is probably unsafe to unlock the file without also untying
2243 it, because if you do, changes may remain unwritten inside the object.
2244 That is why there is no shortcut for unlocking. If you really want to
2245 unlock the file prematurely, you know what to do; if you don't know
2246 what to do, then don't do it.
2248 All the usual warnings about file locking apply here. In particular,
2249 note that file locking in Perl is B<advisory>, which means that
2250 holding a lock will not prevent anyone else from reading, writing, or
2251 erasing the file; it only prevents them from getting another lock at
2252 the same time. Locks are analogous to green traffic lights: If you
2253 have a green light, that does not prevent the idiot coming the other
2254 way from plowing into you sideways; it merely guarantees to you that
2255 the idiot does not also have a green light at the same time.
2259 my $old_value = $o->autochomp(0); # disable autochomp option
2260 my $old_value = $o->autochomp(1); # enable autochomp option
2262 my $ac = $o->autochomp(); # recover current value
2264 See L<"autochomp">, above.
2266 =head2 C<defer>, C<flush>, C<discard>, and C<autodefer>
2268 See L<"Deferred Writing">, below.
2272 $off = $o->offset($n);
2274 This method returns the byte offset of the start of the C<$n>th record
2275 in the file. If there is no such record, it returns an undefined
2278 =head1 Tying to an already-opened filehandle
2280 If C<$fh> is a filehandle, such as is returned by C<IO::File> or one
2281 of the other C<IO> modules, you may use:
2283 tie @array, 'Tie::File', $fh, ...;
2285 Similarly if you opened that handle C<FH> with regular C<open> or
2286 C<sysopen>, you may use:
2288 tie @array, 'Tie::File', \*FH, ...;
2290 Handles that were opened write-only won't work. Handles that were
2291 opened read-only will work as long as you don't try to modify the
2292 array. Handles must be attached to seekable sources of data---that
2293 means no pipes or sockets. If C<Tie::File> can detect that you
2294 supplied a non-seekable handle, the C<tie> call will throw an
2295 exception. (On Unix systems, it can detect this.)
2297 Note that Tie::File will only close any filehandles that it opened
2298 internally. If you passed it a filehandle as above, you "own" the
2299 filehandle, and are responsible for closing it after you have untied
2302 =head1 Deferred Writing
2304 (This is an advanced feature. Skip this section on first reading.)
2306 Normally, modifying a C<Tie::File> array writes to the underlying file
2307 immediately. Every assignment like C<$a[3] = ...> rewrites as much of
2308 the file as is necessary; typically, everything from line 3 through
2309 the end will need to be rewritten. This is the simplest and most
2310 transparent behavior. Performance even for large files is reasonably
2313 However, under some circumstances, this behavior may be excessively
2314 slow. For example, suppose you have a million-record file, and you
2321 The first time through the loop, you will rewrite the entire file,
2322 from line 0 through the end. The second time through the loop, you
2323 will rewrite the entire file from line 1 through the end. The third
2324 time through the loop, you will rewrite the entire file from line 2 to
2327 If the performance in such cases is unacceptable, you may defer the
2328 actual writing, and then have it done all at once. The following loop
2329 will perform much better for large files:
2337 If C<Tie::File>'s memory limit is large enough, all the writing will
2338 done in memory. Then, when you call C<-E<gt>flush>, the entire file
2339 will be rewritten in a single pass.
2341 (Actually, the preceding discussion is something of a fib. You don't
2342 need to enable deferred writing to get good performance for this
2343 common case, because C<Tie::File> will do it for you automatically
2344 unless you specifically tell it not to. See L<"autodeferring">,
2347 Calling C<-E<gt>flush> returns the array to immediate-write mode. If
2348 you wish to discard the deferred writes, you may call C<-E<gt>discard>
2349 instead of C<-E<gt>flush>. Note that in some cases, some of the data
2350 will have been written already, and it will be too late for
2351 C<-E<gt>discard> to discard all the changes. Support for
2352 C<-E<gt>discard> may be withdrawn in a future version of C<Tie::File>.
2354 Deferred writes are cached in memory up to the limit specified by the
2355 C<dw_size> option (see above). If the deferred-write buffer is full
2356 and you try to write still more deferred data, the buffer will be
2357 flushed. All buffered data will be written immediately, the buffer
2358 will be emptied, and the now-empty space will be used for future
2361 If the deferred-write buffer isn't yet full, but the total size of the
2362 buffer and the read cache would exceed the C<memory> limit, the oldest
2363 records will be expired from the read cache until the total size is
2366 C<push>, C<pop>, C<shift>, C<unshift>, and C<splice> cannot be
2367 deferred. When you perform one of these operations, any deferred data
2368 is written to the file and the operation is performed immediately.
2369 This may change in a future version.
2371 If you resize the array with deferred writing enabled, the file will
2372 be resized immediately, but deferred records will not be written.
2373 This has a surprising consequence: C<@a = (...)> erases the file
2374 immediately, but the writing of the actual data is deferred. This
2375 might be a bug. If it is a bug, it will be fixed in a future version.
2377 =head2 Autodeferring
2379 C<Tie::File> tries to guess when deferred writing might be helpful,
2380 and to turn it on and off automatically.
2386 In this example, only the first two assignments will be done
2387 immediately; after this, all the changes to the file will be deferred
2388 up to the user-specified memory limit.
2390 You should usually be able to ignore this and just use the module
2391 without thinking about deferring. However, special applications may
2392 require fine control over which writes are deferred, or may require
2393 that all writes be immediate. To disable the autodeferment feature,
2396 (tied @o)->autodefer(0);
2400 tie @array, 'Tie::File', $file, autodefer => 0;
2403 Similarly, C<-E<gt>autodefer(1)> re-enables autodeferment, and
2404 C<-E<gt>autodefer()> recovers the current value of the autodefer setting.
2407 =head1 CONCURRENT ACCESS TO FILES
2409 Caching and deferred writing are inappropriate if you want the same
2410 file to be accessed simultaneously from more than one process. You
2411 will want to disable these features. You should do that by including
2412 the C<memory =E<gt> 0> option in your C<tie> calls; this will inhibit
2413 caching and deferred writing.
2415 You will also want to lock the file while reading or writing it. You
2416 can use the C<-E<gt>flock> method for this. A future version of this
2417 module may provide an 'autolocking' mode.
2421 (That's Latin for 'warnings'.)
2427 Reasonable effort was made to make this module efficient. Nevertheless,
2428 changing the size of a record in the middle of a large file will
2429 always be fairly slow, because everything after the new record must be
2434 The behavior of tied arrays is not precisely the same as for regular
2435 arrays. For example:
2437 # This DOES print "How unusual!"
2438 undef $a[10]; print "How unusual!\n" if defined $a[10];
2440 C<undef>-ing a C<Tie::File> array element just blanks out the
2441 corresponding record in the file. When you read it back again, you'll
2442 get the empty string, so the supposedly-C<undef>'ed value will be
2443 defined. Similarly, if you have C<autochomp> disabled, then
2445 # This DOES print "How unusual!" if 'autochomp' is disabled
2447 print "How unusual!\n" if $a[10];
2449 Because when C<autochomp> is disabled, C<$a[10]> will read back as
2450 C<"\n"> (or whatever the record separator string is.)
2452 There are other minor differences, particularly regarding C<exists>
2453 and C<delete>, but in general, the correspondence is extremely close.
2457 I have supposed that since this module is concerned with file I/O,
2458 almost all normal use of it will be heavily I/O bound. This means
2459 that the time to maintain complicated data structures inside the
2460 module will be dominated by the time to actually perform the I/O.
2461 When there was an opportunity to spend CPU time to avoid doing I/O, I
2462 usually tried to take it.
2466 You might be tempted to think that deferred writing is like
2467 transactions, with C<flush> as C<commit> and C<discard> as
2468 C<rollback>, but it isn't, so don't.
2472 There is a large memory overhead for each record offset and for each
2473 cache entry: about 310 bytes per cached data record, and about 21 bytes per offset table entry.
2475 The per-record overhead will limit the maximum number of records you
2476 can access per file. Note that I<accessing> the length of the array
2477 via C<$x = scalar @tied_file> accesses B<all> records and stores their
2478 offsets. The same for C<foreach (@tied_file)>, even if you exit the
2485 This version promises absolutely nothing about the internals, which
2486 may change without notice. A future version of the module will have a
2487 well-defined and stable subclassing API.
2489 =head1 WHAT ABOUT C<DB_File>?
2491 People sometimes point out that L<DB_File> will do something similar,
2492 and ask why C<Tie::File> module is necessary.
2494 There are a number of reasons that you might prefer C<Tie::File>.
2495 A list is available at C<http://perl.plover.com/TieFile/why-not-DB_File>.
2501 To contact the author, send email to: C<mjd-perl-tiefile+@plover.com>
2503 To receive an announcement whenever a new version of this module is
2504 released, send a blank email message to
2505 C<mjd-perl-tiefile-subscribe@plover.com>.
2507 The most recent version of this module, including documentation and
2508 any news of importance, will be available at
2510 http://perl.plover.com/TieFile/
2515 C<Tie::File> version 0.95 is copyright (C) 2002 Mark Jason Dominus.
2517 This library is free software; you may redistribute it and/or modify
2518 it under the same terms as Perl itself.
2520 These terms are your choice of any of (1) the Perl Artistic Licence,
2521 or (2) version 2 of the GNU General Public License as published by the
2522 Free Software Foundation, or (3) any later version of the GNU General
2525 This library is distributed in the hope that it will be useful,
2526 but WITHOUT ANY WARRANTY; without even the implied warranty of
2527 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2528 GNU General Public License for more details.
2530 You should have received a copy of the GNU General Public License
2531 along with this library program; it should be in the file C<COPYING>.
2532 If not, write to the Free Software Foundation, Inc., 59 Temple Place,
2533 Suite 330, Boston, MA 02111 USA
2535 For licensing inquiries, contact the author at:
2539 Philadelphia, PA 19107
2543 C<Tie::File> version 0.95 comes with ABSOLUTELY NO WARRANTY.
2544 For details, see the license.
2548 Gigantic thanks to Jarkko Hietaniemi, for agreeing to put this in the
2549 core when I hadn't written it yet, and for generally being helpful,
2550 supportive, and competent. (Usually the rule is "choose any one.")
2551 Also big thanks to Abhijit Menon-Sen for all of the same things.
2553 Special thanks to Craig Berry and Peter Prymmer (for VMS portability
2554 help), Randy Kobes (for Win32 portability help), Clinton Pierce and
2555 Autrijus Tang (for heroic eleventh-hour Win32 testing above and beyond
2556 the call of duty), Michael G Schwern (for testing advice), and the
2557 rest of the CPAN testers (for testing generally).
2559 Special thanks to Tels for suggesting several speed and memory
2562 Additional thanks to:
2566 Jarkko Hietaniemi (again) /
2570 Tassilo von Parseval /
2576 Autrijus Tang (again) /
2582 More tests. (Stuff I didn't think of yet.)
2586 Fixed-length mode. Leave-blanks mode.
2588 Maybe an autolocking mode?
2590 For many common uses of the module, the read cache is a liability.
2591 For example, a program that inserts a single record, or that scans the
2592 file once, will have a cache hit rate of zero. This suggests a major
2593 optimization: The cache should be initially disabled. Here's a hybrid
2594 approach: Initially, the cache is disabled, but the cache code
2595 maintains statistics about how high the hit rate would be *if* it were
2596 enabled. When it sees the hit rate get high enough, it enables
2597 itself. The STAT comments in this code are the beginning of an
2598 implementation of this.
2600 Record locking with fcntl()? Then the module might support an undo
2601 log and get real transactions. What a tour de force that would be.
2603 Keeping track of the highest cached record. This would allow reads-in-a-row
2604 to skip the cache lookup faster (if reading from 1..N with empty cache at
2605 start, the last cached value will be always N-1).