1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
|
package Tie::File;
use Carp;
use POSIX 'SEEK_SET';
use Fcntl 'O_CREAT', 'O_RDWR', 'LOCK_EX';
require 5.005;
$VERSION = "0.20";
# Idea: The object will always contain an array of byte offsets
# this will be filled in as is necessary and convenient.
# fetch will do seek-read.
# There will be a cache parameter that controls the amount of cached *data*
# Also an LRU queue of cached records
# store will read the relevant record into the cache
# If it's the same length as what is being written, it will overwrite it in
# place; if not, it will do a from-to copying write.
# The record separator string is also a parameter
# Record numbers start at ZERO.
my $DEFAULT_MEMORY_SIZE = 1<<21; # 2 megabytes
my %good_opt = map {$_ => 1, "-$_" => 1}
qw(memory dw_size mode recsep discipline autochomp);
sub TIEARRAY {
if (@_ % 2 != 0) {
croak "usage: tie \@array, $_[0], filename, [option => value]...";
}
my ($pack, $file, %opts) = @_;
# transform '-foo' keys into 'foo' keys
for my $key (keys %opts) {
unless ($good_opt{$key}) {
croak("$pack: Unrecognized option '$key'\n");
}
my $okey = $key;
if ($key =~ s/^-+//) {
$opts{$key} = delete $opts{$okey};
}
}
unless (defined $opts{memory}) {
# default is the larger of the default cache size and the
# deferred-write buffer size (if specified)
$opts{memory} = $DEFAULT_MEMORY_SIZE;
$opts{memory} = $opts{dw_size}
if defined $opts{dw_size} && $opts{dw_size} > $DEFAULT_MEMORY_SIZE;
}
$opts{dw_size} = $opts{memory} unless defined $opts{dw_size};
if ($opts{dw_size} > $opts{memory}) {
croak("$pack: dw_size may not be larger than total memory allocation\n");
}
$opts{deferred} = {}; # no records presently deferred
$opts{deferred_s} = 0; # count of total bytes in ->{deferred}
# the cache is a hash instead of an array because it is likely to be
# sparsely populated
$opts{cache} = {};
$opts{cached} = 0; # total size of cached data
$opts{lru} = []; # replace with heap in later version
$opts{offsets} = [0];
$opts{filename} = $file;
unless (defined $opts{recsep}) {
$opts{recsep} = _default_recsep();
}
$opts{recseplen} = length($opts{recsep});
if ($opts{recseplen} == 0) {
croak "Empty record separator not supported by $pack";
}
$opts{autochomp} = 1 unless defined $opts{autochomp};
my $mode = defined($opts{mode}) ? $opts{mode} : O_CREAT|O_RDWR;
my $fh;
if (UNIVERSAL::isa($file, 'GLOB')) {
unless (seek $file, 0, SEEK_SET) {
croak "$pack: your filehandle does not appear to be seekable";
}
$fh = $file;
} elsif (ref $file) {
croak "usage: tie \@array, $pack, filename, [option => value]...";
} else {
$fh = \do { local *FH }; # only works in 5.005 and later
sysopen $fh, $file, $mode, 0666 or return;
binmode $fh;
}
{ my $ofh = select $fh; $| = 1; select $ofh } # autoflush on write
if (defined $opts{discipline} && $] >= 5.006) {
# This avoids a compile-time warning under 5.005
eval 'binmode($fh, $opts{discipline})';
croak $@ if $@ =~ /unknown discipline/i;
die if $@;
}
$opts{fh} = $fh;
bless \%opts => $pack;
}
sub FETCH {
my ($self, $n) = @_;
$self->_chomp1($self->_fetch($n));
}
# Chomp many records in-place; return nothing useful
sub _chomp {
my $self = shift;
return unless $self->{autochomp};
if ($self->{autochomp}) {
for (@_) {
next unless defined;
substr($_, - $self->{recseplen}) = "";
}
}
}
# Chomp one record in-place; return modified record
sub _chomp1 {
my ($self, $rec) = @_;
return $rec unless $self->{autochomp};
return unless defined $rec;
substr($rec, - $self->{recseplen}) = "";
$rec;
}
sub _fetch {
my ($self, $n) = @_;
# check the record cache
{ my $cached = $self->_check_cache($n);
return $cached if defined $cached;
}
unless ($#{$self->{offsets}} >= $n) {
my $o = $self->_fill_offsets_to($n);
# If it's still undefined, there is no such record, so return 'undef'
return unless defined $o;
}
my $fh = $self->{FH};
$self->_seek($n); # we can do this now that offsets is populated
my $rec = $self->_read_record;
# If we happen to have just read the first record, check to see if
# the length of the record matches what 'tell' says. If not, Tie::File
# won't work, and should drop dead.
#
# if ($n == 0 && defined($rec) && tell($self->{fh}) != length($rec)) {
# if (defined $self->{discipline}) {
# croak "I/O discipline $self->{discipline} not supported";
# } else {
# croak "File encoding not supported";
# }
# }
$self->_cache_insert($n, $rec) if defined $rec;
$rec;
}
sub STORE {
my ($self, $n, $rec) = @_;
$self->_fixrecs($rec);
return $self->_store_deferred($n, $rec) if $self->{defer};
# We need this to decide whether the new record will fit
# It incidentally populates the offsets table
# Note we have to do this before we alter the cache
my $oldrec = $self->_fetch($n);
# _check_cache promotes record $n to MRU. Is this correct behavior?
if (my $cached = $self->_check_cache($n)) {
my $len_diff = length($rec) - length($cached);
$self->{cache}{$n} = $rec;
$self->{cached} += $len_diff;
$self->_cache_flush
if $len_diff > 0
&& $self->{deferred_s} + $self->{cached} > $self->{memory};
}
if (not defined $oldrec) {
# We're storing a record beyond the end of the file
$self->_extend_file_to($n+1);
$oldrec = $self->{recsep};
}
my $len_diff = length($rec) - length($oldrec);
# length($oldrec) here is not consistent with text mode TODO XXX BUG
$self->_twrite($rec, $self->{offsets}[$n], length($oldrec));
# now update the offsets
# array slice goes from element $n+1 (the first one to move)
# to the end
for (@{$self->{offsets}}[$n+1 .. $#{$self->{offsets}}]) {
$_ += $len_diff;
}
}
sub _store_deferred {
my ($self, $n, $rec) = @_;
$self->_uncache($n);
my $old_deferred = $self->{deferred}{$n};
$self->{deferred}{$n} = $rec;
$self->{deferred_s} += length($rec);
$self->{deferred_s} -= length($old_deferred) if defined $old_deferred;
if ($self->{deferred_s} > $self->{dw_size}) {
$self->flush;
$self->defer; # flush clears the 'defer' flag
} elsif ($self->{deferred_s} + $self->{cached} > $self->{memory}) {
$self->_cache_flush;
}
}
sub FETCHSIZE {
my $self = shift;
my $n = $#{$self->{offsets}};
while (defined ($self->_fill_offsets_to($n+1))) {
++$n;
}
$n;
}
sub STORESIZE {
my ($self, $len) = @_;
my $olen = $self->FETCHSIZE;
return if $len == $olen; # Woo-hoo!
# file gets longer
if ($len > $olen) {
$self->_extend_file_to($len);
return;
}
# file gets shorter
$self->_seek($len);
$self->_chop_file;
$#{$self->{offsets}} = $len;
# $self->{offsets}[0] = 0; # in case we just chopped this
my @cached = grep $_ >= $len, keys %{$self->{cache}};
$self->_uncache(@cached);
}
sub PUSH {
my $self = shift;
$self->SPLICE($self->FETCHSIZE, scalar(@_), @_);
$self->FETCHSIZE;
}
sub POP {
my $self = shift;
my $size = $self->FETCHSIZE;
return if $size == 0;
# print STDERR "# POPPITY POP POP POP\n";
scalar $self->SPLICE($size-1, 1);
}
sub SHIFT {
my $self = shift;
scalar $self->SPLICE(0, 1);
}
sub UNSHIFT {
my $self = shift;
$self->SPLICE(0, 0, @_);
$self->FETCHSIZE;
}
sub CLEAR {
# And enable auto-defer mode, since it's likely that they just
# did @a = (...);
my $self = shift;
$self->_seekb(0);
$self->_chop_file;
%{$self->{cache}} = ();
$self->{cached} = 0;
@{$self->{lru}} = ();
@{$self->{offsets}} = (0);
}
sub EXTEND {
my ($self, $n) = @_;
$self->_fill_offsets_to($n);
$self->_extend_file_to($n);
}
sub DELETE {
my ($self, $n) = @_;
my $lastrec = $self->FETCHSIZE-1;
if ($n == $lastrec) {
$self->_seek($n);
$self->_chop_file;
$#{$self->{offsets}}--;
$self->_uncache($n);
# perhaps in this case I should also remove trailing null records?
} else {
$self->STORE($n, "");
}
}
sub EXISTS {
my ($self, $n) = @_;
$self->_fill_offsets_to($n);
0 <= $n && $n < $self->FETCHSIZE;
}
sub SPLICE {
my $self = shift;
$self->_flush if $self->{defer};
if (wantarray) {
$self->_chomp(my @a = $self->_splice(@_));
@a;
} else {
$self->_chomp1(scalar $self->_splice(@_));
}
}
sub DESTROY {
$self->flush if $self->{defer};
}
sub _splice {
my ($self, $pos, $nrecs, @data) = @_;
my @result;
$pos = 0 unless defined $pos;
# Deal with negative and other out-of-range positions
# Also set default for $nrecs
{
my $oldsize = $self->FETCHSIZE;
$nrecs = $oldsize unless defined $nrecs;
my $oldpos = $pos;
if ($pos < 0) {
$pos += $oldsize;
if ($pos < 0) {
croak "Modification of non-creatable array value attempted, subscript $oldpos";
}
}
if ($pos > $oldsize) {
return unless @data;
$pos = $oldsize; # This is what perl does for normal arrays
}
}
$self->_fixrecs(@data);
my $data = join '', @data;
my $datalen = length $data;
my $oldlen = 0;
# compute length of data being removed
# Incidentally fills offsets table
for ($pos .. $pos+$nrecs-1) {
my $rec = $self->_fetch($_);
last unless defined $rec;
push @result, $rec;
$oldlen += length($rec);
}
# Modify the file
$self->_twrite($data, $self->{offsets}[$pos], $oldlen);
# update the offsets table part 1
# compute the offsets of the new records:
my @new_offsets;
if (@data) {
push @new_offsets, $self->{offsets}[$pos];
for (0 .. $#data-1) {
push @new_offsets, $new_offsets[-1] + length($data[$_]);
}
}
splice(@{$self->{offsets}}, $pos, $nrecs, @new_offsets);
# update the offsets table part 2
# adjust the offsets of the following old records
for ($pos+@data .. $#{$self->{offsets}}) {
$self->{offsets}[$_] += $datalen - $oldlen;
}
# If we scrubbed out all known offsets, regenerate the trivial table
# that knows that the file does indeed start at 0.
$self->{offsets}[0] = 0 unless @{$self->{offsets}};
# Perhaps the following cache foolery could be factored out
# into a bunch of mor opaque cache functions. For example,
# it's odd to delete a record from the cache and then remove
# it from the LRU queue later on; there should be a function to
# do both at once.
# update the read cache, part 1
# modified records
# Consider this carefully for correctness
for ($pos .. $pos+$nrecs-1) {
my $cached = $self->{cache}{$_};
next unless defined $cached;
my $new = $data[$_-$pos];
if (defined $new) {
$self->{cached} += length($new) - length($cached);
$self->{cache}{$_} = $new;
} else {
$self->_uncache($_);
}
}
# update the read cache, part 2
# moved records - records past the site of the change
# need to be renumbered
# Maybe merge this with the previous block?
{
my %adjusted;
for (keys %{$self->{cache}}) {
next unless $_ >= $pos + $nrecs;
$adjusted{$_-$nrecs+@data} = delete $self->{cache}{$_};
}
@{$self->{cache}}{keys %adjusted} = values %adjusted;
# for (keys %{$self->{cache}}) {
# next unless $_ >= $pos + $nrecs;
# $self->{cache}{$_-$nrecs+@data} = delete $self->{cache}{$_};
# }
}
# fix the LRU queue
my(@new, @changed);
for (@{$self->{lru}}) {
if ($_ >= $pos + $nrecs) {
push @new, $_ + @data - $nrecs;
} elsif ($_ >= $pos) {
push @changed, $_ if $_ < $pos + @data;
} else {
push @new, $_;
}
}
@{$self->{lru}} = (@new, @changed);
# Now there might be too much data in the cache, if we spliced out
# some short records and spliced in some long ones. If so, flush
# the cache.
$self->_cache_flush;
# Yes, the return value of 'splice' *is* actually this complicated
wantarray ? @result : @result ? $result[-1] : undef;
}
# write data into the file
# $data is the data to be written.
# it should be written at position $pos, and should overwrite
# exactly $len of the following bytes.
# Note that if length($data) > $len, the subsequent bytes will have to
# be moved up, and if length($data) < $len, they will have to
# be moved down
sub _twrite {
my ($self, $data, $pos, $len) = @_;
unless (defined $pos) {
die "\$pos was undefined in _twrite";
}
my $len_diff = length($data) - $len;
if ($len_diff == 0) { # Woo-hoo!
my $fh = $self->{fh};
$self->_seekb($pos);
$self->_write_record($data);
return; # well, that was easy.
}
# the two records are of different lengths
# our strategy here: rewrite the tail of the file,
# reading ahead one buffer at a time
# $bufsize is required to be at least as large as the data we're overwriting
my $bufsize = _bufsize($len_diff);
my ($writepos, $readpos) = ($pos, $pos+$len);
my $next_block;
# Seems like there ought to be a way to avoid the repeated code
# and the special case here. The read(1) is also a little weird.
# Think about this.
do {
$self->_seekb($readpos);
my $br = read $self->{fh}, $next_block, $bufsize;
my $more_data = read $self->{fh}, my($dummy), 1;
$self->_seekb($writepos);
$self->_write_record($data);
$readpos += $br;
$writepos += length $data;
$data = $next_block;
} while $more_data;
$self->_seekb($writepos);
$self->_write_record($next_block);
# There might be leftover data at the end of the file
$self->_chop_file if $len_diff < 0;
}
# If a record does not already end with the appropriate terminator
# string, append one.
sub _fixrecs {
my $self = shift;
for (@_) {
$_ .= $self->{recsep}
unless substr($_, - $self->{recseplen}) eq $self->{recsep};
}
}
# seek to the beginning of record #$n
# Assumes that the offsets table is already correctly populated
#
# Note that $n=-1 has a special meaning here: It means the start of
# the last known record; this may or may not be the very last record
# in the file, depending on whether the offsets table is fully populated.
#
sub _seek {
my ($self, $n) = @_;
my $o = $self->{offsets}[$n];
defined($o)
or confess("logic error: undefined offset for record $n");
seek $self->{fh}, $o, SEEK_SET
or die "Couldn't seek filehandle: $!"; # "Should never happen."
}
sub _seekb {
my ($self, $b) = @_;
seek $self->{fh}, $b, SEEK_SET
or die "Couldn't seek filehandle: $!"; # "Should never happen."
}
# populate the offsets table up to the beginning of record $n
# return the offset of record $n
sub _fill_offsets_to {
my ($self, $n) = @_;
my $fh = $self->{fh};
local *OFF = $self->{offsets};
my $rec;
until ($#OFF >= $n) {
my $o = $OFF[-1];
$self->_seek(-1); # tricky -- see comment at _seek
$rec = $self->_read_record;
if (defined $rec) {
push @OFF, tell $fh;
} else {
return; # It turns out there is no such record
}
}
# we have now read all the records up to record n-1,
# so we can return the offset of record n
return $OFF[$n];
}
# assumes that $rec is already suitably terminated
sub _write_record {
my ($self, $rec) = @_;
my $fh = $self->{fh};
print $fh $rec
or die "Couldn't write record: $!"; # "Should never happen."
}
sub _read_record {
my $self = shift;
my $rec;
{ local $/ = $self->{recsep};
my $fh = $self->{fh};
$rec = <$fh>;
}
$rec;
}
sub _cache_insert {
my ($self, $n, $rec) = @_;
# Do not cache records that are too big to fit in the cache.
return unless length $rec <= $self->{memory};
$self->{cache}{$n} = $rec;
$self->{cached} += length $rec;
push @{$self->{lru}}, $n; # most-recently-used is at the END
$self->_cache_flush if $self->{cached} > $self->{memory};
}
sub _uncache {
my $self = shift;
for my $n (@_) {
my $cached = delete $self->{cache}{$n};
next unless defined $cached;
@{$self->{lru}} = grep $_ != $n, @{$self->{lru}};
$self->{cached} -= length($cached);
}
}
sub _check_cache {
my ($self, $n) = @_;
my $rec;
return unless defined($rec = $self->{cache}{$n});
# cache hit; update LRU queue and return $rec
# replace this with a heap in a later version
@{$self->{lru}} = ((grep $_ ne $n, @{$self->{lru}}), $n);
$rec;
}
sub _cache_flush {
my ($self) = @_;
while ($self->{cached} + $self->{deferred_s} > $self->{memory}) {
my $lru = shift @{$self->{lru}};
my $rec = delete $self->{cache}{$lru};
$self->{cached} -= length $rec;
}
}
# We have read to the end of the file and have the offsets table
# entirely populated. Now we need to write a new record beyond
# the end of the file. We prepare for this by writing
# empty records into the file up to the position we want
#
# assumes that the offsets table already contains the offset of record $n,
# if it exists, and extends to the end of the file if not.
sub _extend_file_to {
my ($self, $n) = @_;
$self->_seek(-1); # position after the end of the last record
my $pos = $self->{offsets}[-1];
# the offsets table has one entry more than the total number of records
$extras = $n - $#{$self->{offsets}};
# Todo : just use $self->{recsep} x $extras here?
while ($extras-- > 0) {
$self->_write_record($self->{recsep});
push @{$self->{offsets}}, tell $self->{fh};
}
}
# Truncate the file at the current position
sub _chop_file {
my $self = shift;
truncate $self->{fh}, tell($self->{fh});
}
# compute the size of a buffer suitable for moving
# all the data in a file forward $n bytes
# ($n may be negative)
# The result should be at least $n.
sub _bufsize {
my $n = shift;
return 8192 if $n < 0;
my $b = $n & ~8191;
$b += 8192 if $n & 8191;
$b;
}
# Lock the file
sub flock {
my ($self, $op) = @_;
unless (@_ <= 3) {
my $pack = ref $self;
croak "Usage: $pack\->flock([OPERATION])";
}
my $fh = $self->{fh};
$op = LOCK_EX unless defined $op;
flock $fh, $op;
}
# Defer writes
sub defer {
my $self = shift;
$self->{defer} = 1;
}
# Get/set autochomp option
sub autochomp {
my $self = shift;
if (@_) {
my $old = $self->{autochomp};
$self->{autochomp} = shift;
$old;
} else {
$self->{autochomp};
}
}
# Flush deferred writes
#
# This could be better optimized to write the file in one pass, instead
# of one pass per block of records. But that will require modifications
# to _twrite, so I should have a good _twite test suite first.
sub flush {
my $self = shift;
$self->_flush;
$self->{defer} = 0;
}
sub _flush {
my $self = shift;
my @writable = sort {$a<=>$b} (keys %{$self->{deferred}});
while (@writable) {
# gather all consecutive records from the front of @writable
my $first_rec = shift @writable;
my $last_rec = $first_rec+1;
++$last_rec, shift @writable while @writable && $last_rec == $writable[0];
--$last_rec;
$self->_fill_offsets_to($last_rec);
$self->_extend_file_to($last_rec);
$self->_splice($first_rec, $last_rec-$first_rec+1,
@{$self->{deferred}}{$first_rec .. $last_rec});
}
$self->discard; # clear out defered-write-cache
}
# Discard deferred writes
sub discard {
my $self = shift;
undef $self->{deferred};
$self->{deferred_s} = 0;
$self->{defer} = 0;
}
# Not yet implemented
sub autodefer { }
sub _default_recsep {
my $recsep = $/;
if ($^O eq 'MSWin32') {
# Windows users expect files to be terminated with \r\n
# But $/ is set to \n instead
# Note that this also transforms \n\n into \r\n\r\n.
# That is a feature.
$recsep =~ s/\n/\r\n/g;
}
$recsep;
}
# Given a file, make sure the cache is consistent with the
# file contents
sub _check_integrity {
my ($self, $file, $warn) = @_;
my $good = 1;
if (not defined $self->{offsets}[0]) {
$warn && print STDERR "# offset 0 is missing!\n";
$good = 0;
} elsif ($self->{offsets}[0] != 0) {
$warn && print STDERR "# rec 0: offset <$self->{offsets}[0]> s/b 0!\n";
$good = 0;
}
local *F = $self->{fh};
seek F, 0, SEEK_SET;
local $/ = $self->{recsep};
$. = 0;
while (<F>) {
my $n = $. - 1;
my $cached = $self->{cache}{$n};
my $offset = $self->{offsets}[$.];
my $ao = tell F;
if (defined $offset && $offset != $ao) {
$warn && print STDERR "# rec $n: offset <$offset> actual <$ao>\n";
$good = 0;
}
if (defined $cached && $_ ne $cached) {
$good = 0;
chomp $cached;
chomp;
$warn && print STDERR "# rec $n: cached <$cached> actual <$_>\n";
}
}
my $memory = 0;
while (my ($n, $r) = each %{$self->{cache}}) {
$memory += length($r);
next if $n+1 <= $.; # checked this already
$warn && print STDERR "# spurious caching of record $n\n";
$good = 0;
}
if ($memory != $self->{cached}) {
$warn && print STDERR "# cache size is $self->{cached}, should be $memory\n";
$good = 0;
}
my (%seen, @duplicate);
for (@{$self->{lru}}) {
$seen{$_}++;
if (not exists $self->{cache}{$_}) {
$warn && print "# $_ is mentioned in the LRU queue, but not in the cache\n";
$good = 0;
}
}
@duplicate = grep $seen{$_}>1, keys %seen;
if (@duplicate) {
my $records = @duplicate == 1 ? 'Record' : 'Records';
my $appear = @duplicate == 1 ? 'appears' : 'appear';
$warn && print "# $records @duplicate $appear multiple times in LRU queue: @{$self->{lru}}\n";
$good = 0;
}
for (keys %{$self->{cache}}) {
unless (exists $seen{$_}) {
print "# record $_ is in the cache but not the LRU queue\n";
$good = 0;
}
}
$good;
}
"Cogito, ergo sum."; # don't forget to return a true value from the file
=head1 NAME
Tie::File - Access the lines of a disk file via a Perl array
=head1 SYNOPSIS
# This file documents Tie::File version 0.20
tie @array, 'Tie::File', filename or die ...;
$array[13] = 'blah'; # line 13 of the file is now 'blah'
print $array[42]; # display line 42 of the file
$n_recs = @array; # how many records are in the file?
$#array = $n_recs - 2; # chop records off the end
# As you would expect:
push @array, new recs...;
my $r1 = pop @array;
unshift @array, new recs...;
my $r1 = shift @array;
@old_recs = splice @array, 3, 7, new recs...;
untie @array; # all finished
=head1 DESCRIPTION
C<Tie::File> represents a regular text file as a Perl array. Each
element in the array corresponds to a record in the file. The first
line of the file is element 0 of the array; the second line is element
1, and so on.
The file is I<not> loaded into memory, so this will work even for
gigantic files.
Changes to the array are reflected in the file immediately.
Lazy people may now stop reading the manual.
=head2 C<recsep>
What is a 'record'? By default, the meaning is the same as for the
C<E<lt>...E<gt>> operator: It's a string terminated by C<$/>, which is
probably C<"\n">. (Minor exception: on dos and Win32 systems, a
'record' is a string terminated by C<"\r\n">.) You may change the
definition of "record" by supplying the C<recsep> option in the C<tie>
call:
tie @array, 'Tie::File', $file, recsep => 'es';
This says that records are delimited by the string C<es>. If the file
contained the following data:
Curse these pesky flies!\n
then the C<@array> would appear to have four elements:
"Curse th"
"e p"
"ky fli"
"!\n"
An undefined value is not permitted as a record separator. Perl's
special "paragraph mode" semantics (E<agrave> la C<$/ = "">) are not
emulated.
Records read from the tied array do not have the record separator
string on the end; this is to allow
$array[17] .= "extra";
to work as expected.
(See L<"autochomp">, below.) Records stored into the array will have
the record separator string appended before they are written to the
file, if they don't have one already. For example, if the record
separator string is C<"\n">, then the following two lines do exactly
the same thing:
$array[17] = "Cherry pie";
$array[17] = "Cherry pie\n";
The result is that the contents of line 17 of the file will be
replaced with "Cherry pie"; a newline character will separate line 17
from line 18. This means that in particular, this will do nothing:
chomp $array[17];
Because the C<chomp>ed value will have the separator reattached when
it is written back to the file. There is no way to create a file
whose trailing record separator string is missing.
Inserting records that I<contain> the record separator string will
produce a reasonable result, but if you can't foresee what this result
will be, you'd better avoid doing this.
=head2 C<autochomp>
Normally, array elements have the record separator removed, so that if
the file contains the text
Gold
Frankincense
Myrrh
the tied array will appear to contain C<("Gold", "Frankincense", "Myrrh")>.
If you set C<autochomp> to a false value, the record separator will not be removed. If the file above was tied with
tie @gifts, "Tie::File", $gifts, autochomp => 0;
then the array C<@gifts> would appear to contain C<("Gold\n",
"Frankincense\n", "Myrrh\n")>, or (on Win32 systems) C<("Gold\r\n",
"Frankincense\r\n", "Myrrh\r\n")>.
=head2 C<mode>
Normally, the specified file will be opened for read and write access,
and will be created if it does not exist. (That is, the flags
C<O_RDWR | O_CREAT> are supplied in the C<open> call.) If you want to
change this, you may supply alternative flags in the C<mode> option.
See L<Fcntl> for a listing of available flags.
For example:
# open the file if it exists, but fail if it does not exist
use Fcntl 'O_RDWR';
tie @array, 'Tie::File', $file, mode => O_RDWR;
# create the file if it does not exist
use Fcntl 'O_RDWR', 'O_CREAT';
tie @array, 'Tie::File', $file, mode => O_RDWR | O_CREAT;
# open an existing file in read-only mode
use Fcntl 'O_RDONLY';
tie @array, 'Tie::File', $file, mode => O_RDONLY;
Opening the data file in write-only or append mode is not supported.
=head2 C<memory>
This is an (inexact) upper limit on the amount of memory that
C<Tie::File> will consume at any time while managing the file.
At present, this is used as a bound on the size of the read cache.
Records read in from the file are cached, to avoid having to re-read
them repeatedly. If you read the same record twice, the first time it
will be stored in memory, and the second time it will be fetched from
the I<read cache>. The amount of data in the read cache will not
exceed the value you specified for C<memory>. If C<Tie::File> wants
to cache a new record, but the read cache is full, it will make room
by expiring the least-recently visited records from the read cache.
The default memory limit is 2Mib. You can adjust the maximum read
cache size by supplying the C<memory> option. The argument is the
desired cache size, in bytes.
# I have a lot of memory, so use a large cache to speed up access
tie @array, 'Tie::File', $file, memory => 20_000_000;
Setting the memory limit to 0 will inhibit caching; records will be
fetched from disk every time you examine them.
=head2 Option Format
C<-mode> is a synonym for C<mode>. C<-recsep> is a synonym for
C<recsep>. C<-memory> is a synonym for C<memory>. You get the
idea.
=head1 Public Methods
The C<tie> call returns an object, say C<$o>. You may call
$rec = $o->FETCH($n);
$o->STORE($n, $rec);
to fetch or store the record at line C<$n>, respectively; similarly
the other tied array methods. (See L<perltie> for details.) You may
also call the following methods on this object:
=head2 C<flock>
$o->flock(MODE)
will lock the tied file. C<MODE> has the same meaning as the second
argument to the Perl built-in C<flock> function; for example
C<LOCK_SH> or C<LOCK_EX | LOCK_NB>. (These constants are provided by
the C<use Fcntl ':flock'> declaration.)
C<MODE> is optional; C<$o-E<gt>flock> simply locks the file with
C<LOCK_EX>.
The best way to unlock a file is to discard the object and untie the
array. It is probably unsafe to unlock the file without also untying
it, because if you do, changes may remain unwritten inside the object.
That is why there is no shortcut for unlocking. If you really want to
unlock the file prematurely, you know what to do; if you don't know
what to do, then don't do it.
All the usual warnings about file locking apply here. In particular,
note that file locking in Perl is B<advisory>, which means that
holding a lock will not prevent anyone else from reading, writing, or
erasing the file; it only prevents them from getting another lock at
the same time. Locks are analogous to green traffic lights: If you
have a green light, that does not prevent the idiot coming the other
way from plowing into you sideways; it merely guarantees to you that
the idiot does not also have a green light at the same time.
=head2 C<autochomp>
my $old_value = $o->autochomp(0); # disable autochomp option
my $old_value = $o->autochomp(1); # enable autochomp option
my $ac = $o->autochomp(); # recover current value
See L<"autochomp">, above.
=head1 Tying to an already-opened filehandle
If C<$fh> is a filehandle, such as is returned by C<IO::File> or one
of the other C<IO> modules, you may use:
tie @array, 'Tie::File', $fh, ...;
Similarly if you opened that handle C<FH> with regular C<open> or
C<sysopen>, you may use:
tie @array, 'Tie::File', \*FH, ...;
Handles that were opened write-only won't work. Handles that were
opened read-only will work as long as you don't try to write to them.
Handles must be attached to seekable sources of data---that means no
pipes or sockets. If you supply a non-seekable handle, the C<tie>
call will try to abort your program.
=head1 CAVEATS
(That's Latin for 'warnings'.)
=over 4
=item *
This is BETA RELEASE SOFTWARE. It may have bugs. See the discussion
below about the (lack of any) warranty.
=item *
Every effort was made to make this module efficient. Nevertheless,
changing the size of a record in the middle of a large file will
always be fairly slow, because everything after the new record must be
moved.
In particular, note that the following innocent-looking loop has very
bad behavior:
# million-line file
for (@file_array) {
$_ .= 'x';
}
This is likely to be very slow, because the first iteration must
relocate lines 1 through 999,999; the second iteration must relocate
lines 2 through 999,999, and so on. The relocation is done using
block writes, however, so it's not as slow as it might be.
A soon-to-be-released version of this module will provide a mechanism
for getting better performance in such cases, by deferring the writing
until it can be done all at once. This deferred writing feature might
be enabled automagically if C<Tie::File> guesses that you are about to write many consecutive records. To disable this feature, use
(tied @o)->autodefer(0);
(At present, this call does nothing.)
=item *
The behavior of tied arrays is not precisely the same as for regular
arrays. For example:
undef $a[10]; print "How unusual!\n" if $a[10];
C<undef>-ing a C<Tie::File> array element just blanks out the
corresponding record in the file. When you read it back again, you'll
see the record separator (typically, $a[10] will appear to contain
"\n") so the supposedly-C<undef>'ed value will be true.
There are other minor differences, but in general, the correspondence
is extremely close.
=item *
Not quite every effort was made to make this module as efficient as
possible. C<FETCHSIZE> should use binary search instead of linear
search. The cache's LRU queue should be a heap instead of a list.
These defects are probably minor; in any event, they will be fixed in
a later version of the module.
=item *
The author has supposed that since this module is concerned with file
I/O, almost all normal use of it will be heavily I/O bound, and that
the time to maintain complicated data structures inside the module
will be dominated by the time to actually perform the I/O. This
suggests, for example, that an LRU read-cache is a good tradeoff,
even if it requires substantial adjustment following a C<splice>
operation.
=back
=head1 WHAT ABOUT C<DB_File>?
C<DB_File>'s C<DB_RECNO> feature does something similar to
C<Tie::File>, but there are a number of reasons that you might prefer
C<Tie::File>. C<DB_File> is a great piece of software, but the
C<DB_RECNO> part is less great than the rest of it.
=over 4
=item *
C<DB_File> reads your entire file into memory, modifies it in memory,
and the writes out the entire file again when you untie the file.
This is completely impractical for large files.
C<Tie::File> does not do any of those things. It doesn't try to read
the entire file into memory; instead it uses a lazy approach and
caches recently-used records. The cache size is strictly bounded by
the C<memory> option. DB_File's C<-E<gt>{cachesize}> doesn't prevent
your process from blowing up when reading a big file.
=item *
C<DB_File> has an extremely poor writing strategy. If you have a
ten-megabyte file and tie it with C<DB_File>, and then use
$a[0] =~ s/PERL/Perl/;
C<DB_file> will then read the entire ten-megabyte file into memory, do
the change, and write the entire file back to disk, reading ten
megabytes and writing ten megabytes. C<Tie::File> will read and write
only the first record.
If you have a million-record file and tie it with C<DB_File>, and then
use
$a[999998] =~ s/Larry/Larry Wall/;
C<DB_File> will read the entire million-record file into memory, do
the change, and write the entire file back to disk. C<Tie::File> will
only rewrite records 999998 and 999999. During the writing process,
it will never have more than a few kilobytes of data in memory at any
time, even if the two records are very large.
=item *
Since changes to C<DB_File> files only appear when you do C<untie>, it
can be inconvenient to arrange for concurrent access to the same file
by two or more processes. Each process needs to call C<$db-E<gt>sync>
after every write. When you change a C<Tie::File> array, the changes
are reflected in the file immediately; no explicit C<-E<gt>sync> call
is required. (The forthcoming "deferred writing" mode will allow you
to request that writes be held in memory until explicitly C<sync>'ed.)
=item *
C<DB_File> is only installed by default if you already have the C<db>
library on your system; C<Tie::File> is pure Perl and is installed by
default no matter what. Starting with Perl 5.7.3 you can be
absolutely sure it will be everywhere. You will never have that
surety with C<DB_File>. If you don't have C<DB_File> yet, it requires
a C compiler. You can install C<Tie::File> from CPAN in five minutes
with no compiler.
=item *
C<DB_File> is written in C, so if you aren't allowed to install
modules on your system, it is useless. C<Tie::File> is written in Perl,
so even if you aren't allowed to install modules, you can look into
the source code, see how it works, and copy the subroutines or the
ideas from the subroutines directly into your own Perl program.
=item *
Except in very old, unsupported versions, C<DB_File>'s free license
requires that you distribute the source code for your entire
application. If you are not able to distribute the source code for
your application, you must negotiate an alternative license from
Sleepycat, possibly for a fee. Tie::File is under the Perl Artistic
license and can be distributed free under the same terms as Perl
itself.
=back
=head1 AUTHOR
Mark Jason Dominus
To contact the author, send email to: C<mjd-perl-tiefile+@plover.com>
To receive an announcement whenever a new version of this module is
released, send a blank email message to
C<mjd-perl-tiefile-subscribe@plover.com>.
=head1 LICENSE
C<Tie::File> version 0.20 is copyright (C) 2002 Mark Jason Dominus.
This library is free software; you may redistribute it and/or modify
it under the same terms as Perl itself.
These terms include your choice of (1) the Perl Artistic Licence, or
(2) version 2 of the GNU General Public License as published by the
Free Software Foundation, or (3) any later version of the GNU General
Public License.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this library program; it should be in the file C<COPYING>.
If not, write to the Free Software Foundation, Inc., 59 Temple Place,
Suite 330, Boston, MA 02111 USA
For licensing inquiries, contact the author at:
Mark Jason Dominus
255 S. Warnock St.
Philadelphia, PA 19107
=head1 WARRANTY
C<Tie::File> version 0.20 comes with ABSOLUTELY NO WARRANTY.
For details, see the license.
=head1 THANKS
Gigantic thanks to Jarkko Hietaniemi, for agreeing to put this in the
core when I hadn't written it yet, and for generally being helpful,
supportive, and competent. (Usually the rule is "choose any one.")
Also big thanks to Abhijit Menon-Sen for all of the same things.
Special thanks to Craig Berry (for VMS portability help), Randy Kobes
(for Win32 portability help), Clinton Pierce and Autrijus Tang (for
heroic eleventh-hour Win32 testing above and beyond the call of duty),
and the rest of the CPAN testers (for testing generally).
More thanks to:
Edward Avis /
Gerrit Haase /
Nikola Knezevic /
Nick Ing-Simmons /
Tassilo von Parseval /
H. Dieter Pearcey /
Slaven Rezic /
Peter Somu /
Tels
=head1 TODO
Test DELETE machinery more carefully.
More tests. (C<mode> option. _twrite should be tested separately,
because there are a lot of weird special cases lurking in there.)
More tests. (Stuff I didn't think of yet.)
Paragraph mode?
More tests.
Fixed-length mode.
Maybe an autolocking mode?
Finish deferred writing.
Autodeferment.
Record locking with fcntl()? Then you might support an undo log and
get real transactions. What a coup that would be.
Leave-blanks mode
=cut
|