home | O'Reilly's CD bookshelfs | FreeBSD | Linux | Cisco | Cisco Exam  

Perl CookbookPerl CookbookSearch this book

8.27. Program: Flat File Indexes

It sometimes happens that you need to jump directly to a particular line number in a file, but the lines vary in length, so you can't use Recipe 8.12. Although you could start at the beginning of the file and read every line, this is inefficient if you're making multiple queries.

The solution is to build an index of fixed-width records, one per line. Each record contains the offset in the data file of the corresponding line. The subroutine in Example 8-10 takes the data file and a filehandle to send the index to. It reads a record at a time and prints the current offset in the file to the index, packed into a big-ending unsigned 32-bit integer; see the documentation for the pack function in perlfunc(1) for alternative storage types.

Example 8-10. build_index

  # usage: build_index(*DATA_HANDLE, *INDEX_HANDLE)
  sub build_index {
      my $data_file  = shift;
      my $index_file = shift;
      my $offset     = 0;
      while (<$data_file>) {
          print $index_file pack("N", $offset);
          $offset = tell($data_file);

Once you have an index, it becomes easy to read a particular line from the data file. Jump to that record in the index, read the offset, and jump to that position in the data file. The next line you read will be the one you want. Example 8-11 returns the line, given the line number and the index and data file handles.

Example 8-11. line_with_index

  # usage: line_with_index(*DATA_HANDLE, *INDEX_HANDLE, $LINE_NUMBER)
  # returns line or undef if LINE_NUMBER was out of range
  sub line_with_index {
      my $data_file   = shift;
      my $index_file  = shift;
      my $line_number = shift;
      my $size;               # size of an index entry
      my $i_offset;           # offset into the index of the entry
      my $entry;              # index entry
      my $d_offset;           # offset into the data file
      $size = length(pack("N", 0));
      $i_offset = $size * ($line_number-1);
      seek($index_file, $i_offset, 0) or return;
      read($index_file, $entry, $size);
      $d_offset = unpack("N", $entry);
      seek($data_file, $d_offset, 0);
      return scalar(<$data_file>);

To use these subroutines, just say:

open($fh,  "<", $file)         or die "Can't open $file for reading: $!\n";
open($index, "+>", $file.idx)
  or die "Can't open $file.idx for read/write: $!\n";
build_index($fh, $index);
$line = line_with_index($file, $index, $seeking);

The next step is to cache the index file between runs of the program, so you're not building it each time. This is shown in Example Recipe 8.12. Then add locking for concurrent access, and check time stamps on the files to see whether a change to the data file has made an old index file out of date.

Library Navigation Links

Copyright © 2003 O'Reilly & Associates. All rights reserved.