Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/TBTREE.ZIP/FILES.PAS

Pascal/Delphi Source File | 1988-07-25 | 26.3 KB | 629 lines

(* TBTree13             Copyright (c)  1988            Dean H. Farwell II    *)

unit Files;

(*****************************************************************************)
(*                                                                           *)
(*                 F I L E  H A N D L I N G  R O U T I N E S                 *)
(*                                                                           *)
(*****************************************************************************)

(* This unit is used to create files and to manipulate the existence BITMAPs
   for the associated files.  There are currently four types of files:
   BITMAP, DATA, INDEX and LLIST.  The data files are used to hold user data.
   The INDEX files can be used to hold an index for a given DATA file.  The
   BITMAP files are used to show which physical or logical records are in use.
   In the case of INDEX files, the associated BITMAPs show  which physical
   records are in use.  In the case of DATA files, the associated BITMAPS show
   which logical records are in use.  This will allow deleted records to be
   reused for new records.  The LLIST files are for holding logical record
   lists which take up more than one disk page and must be stored on
   disk (or in the page buffer.  The is no BITMAPs associated with LLIST
   files.                                                                    *)

(* Version Information

   Version 1.1 - No Changes

   Version 1.2 - No Changes

   Version 1.3 - No Changes                                                  *)



(*\*)
(*////////////////////////// I N T E R F A C E //////////////////////////////*)

interface

uses
    FileBuff,
    FileDecs,
    Math,
    Numbers,
    Page,
    Strings;


(* This routine will take the input file name and will strip off any extension
   which exists.  It will then add on the file extension which applies to the
   type passed in as a parameter.                                            *)

procedure FixFileName(var fName : FnString;
                      fType : FileTypes);


(* This creates a file of the type specified.  The routine will also create the
   0th record for the new file and initialize it to all zeroes.  This is all
   that needs to be done unless an index record is being created.  To create an
   index file use CreateIndex (located in the BTree unit ) which eventually
   calls this routine.  This routine also creates a BITMAP for the newly
   created file.

   note - file name passed as parameter does not contain a file extension.  The
   file will be changed to reflect the proper file extension.                *)

procedure CreateFile(var fName : FnString;
                     fType : FileTypes);


(*\*)
(* This routine will delete a file.  It accomplishes this by removing all
   associated pages from the page buffer, closing the file, deleting the file
   from the files open buffer and deleting the file from disk.  If the file
   type is either DATA or INDEX (determined by file extension) then the
   associated BITMAP file will also be deleted.  Never !!! delete a BITMAP
   file explicitly.                                                          *)

procedure DeleteFile(fName : FnString);


(* This routine will find the first unused record (logical or physical
   depending on the what type of file the record belongs to).  It is used for
   creating a new record.  Once the first unused record is determined it
   will be marked as used (using the BITMAP).  If an INDEX record is called
   for, the routine will find a free physical record.  If a data record is
   being requested, then the routine will locate a free logical record.
   The first free record from the beginning of the file will be returned.
   (BITMAP bit will be set).

   This routine is not used to get new records for a BITMAP file since BITMAP
   files don't have BITMAPS.

   This is a rather complicated scheme which uses an existence BITMAP to
   determine if each record is in use.  The existence BITMAP file
   consists of some number of physical records.  Each record contains PAGESIZE
   bytes.  Each byte has 8 bits.  Each bit corresponds to 1 record
   in the file.  If the bit is 1 then the record exists, if it is 0 then the
   record does not exist (is not in use).

   Remember, a record could be either a logical or a physical record depending
   on file type.                                                             *)

function FirstUnUsedRecord(fName : FnString) : RecordNumber;


(* This routine will delete a Logical or Physical record from a file.  It will
   accomomplish this by setting the appropriate bit in the associated BITMAP
   to zero.  It will also release the page from the buffer if the record is in
   the buffer.  Prior to deleting the record, this routine checks to make sure
   that the record is actually in use.  It it is not then it is not deleted.
   (Nothing happens)

   note : This routine will release the page from the buffer if it is an index
   file (a physical record).  If it is a data record the page will not be
   released.  It is somewhat complicated to determine if one or more pages can
   be released in this latter case.  This is because a logical record could use
   part of a physical record or a couple of physical records.  Releasing
   the records will allow that buffer space to be used.  Not releasing it
   means that the page will be swapped out when it gets old.  The routines
   will still function normally.  It is important to note that the logical
   records are always checked against the appropriate bitmat prior to using
   them.  I may do the releasing for logical records latter.                 *)


procedure DeleteRecord(fName : FnString;
                       rNum : RecordNumber);


(* This routine will check to see if a logical or physical record is currently
   in use.  It accomplishes this by using the appropriate BITMAP.            *)

function RecordUsed(fName : FnString;
                    rNum : RecordNumber) : Boolean;


(* This routine will set the appropriate BITMAP to show that a given
   logical or physical record is currently in use.                           *)

procedure SetRecordUsed(fName : FnString;
                        rNum : RecordNumber);


(* This routine will determine which logical record or physical record
   (depending on if its a DATA or INDEX file) is the last one used. It uses the
   associated BITMAP to accomplish this.  The routine returns the record number
   of the last record in use.  If no records are in use then 0 will be returned.
   Remember, the INDEX and DATA files do not use record zero for normal data.
   The zero records are used for special purposes if at all.  All files
   (BITMAP,INDEX,DATA) have zeroth records which are created when the file is
   created.                                                                  *)

function LastUsedRecord(fName : FnString) : RecordNumber;

(*\*)
(*///////////////////// I M P L E M E N T A T I O N /////////////////////////*)

implementation

const
    FILEEXTENSIONSIZE   = 4;     (* number of characters in a file extension
                                    string                                   *)

    BITMAPFILEEXTENSION = '.bit';
    INDEXFILEEXTENSION  = '.idx';
    DATAFILEEXTENSION   = '.dat';
    LLISTFILEEXTENSION  = '.lrf';

type
    ExtensionString = String[FILEEXTENSIONSIZE];

(* This routine will delete a file extension if it exists.  Otherwise,
   nothing will happen.  The file name will be passed in as a parameter      *)

procedure DeleteFileExtension(var fName : FnString);

var
    dotPos : 0 .. FNSIZE;

    begin
    dotPos := Pos('.',fName);
    if dotPos <> 0 then
        begin
        Delete(fName,dotPos,FILEEXTENSIONSIZE);
        end;
    end;                               (* end of DeleteFileExtension routine *)


(* This routine will change a file extension to a new file extension.  The
   file name and new extension are passed in as parameters                   *)

procedure ChangeFileExtension(var fName : FnString;
                              extension : ExtensionString);

    begin
    DeleteFileExtension(fName);
    fName := fName + extension;
    end;                               (* end of ChangeFileExtension routine *)

(*\*)
(* This routine will return the type for the given file.  It does this using
   the file extension.                                                       *)

function FindFileType(fName : FnString) : FileTypes;

var
    dotPos : 1 .. FNSIZE;
    ext : ExtensionString;

    begin
    dotPos := Pos('.',fName);
    ext := Copy(fName,dotPos,FILEEXTENSIONSIZE);
    if ext = BITMAPFILEEXTENSION then FindFileType := BITMAP else
    if ext = INDEXFILEEXTENSION  then FindFileType := INDEX else
    if ext = DATAFILEEXTENSION   then FindFileType := DATA else
    if ext = LLISTFILEEXTENSION  then FindFileType := LLIST;
    end;                                      (* end of FindFileType routine *)


(* This routine will take the input file name and will strip off any extension
   which exists.  It will then add on the file extension which applies to the
   type passed in as a parameter.                                            *)

procedure FixFileName(var fName : FnString;
                      fType : FileTypes);

    begin
    DeleteFileExtension(fName);
    case fType of
        BITMAP : fName := fName + BITMAPFILEEXTENSION;
        INDEX  : fName := fName + INDEXFILEEXTENSION;
        DATA   : fName := fName + DATAFILEEXTENSION;
        LLIST  : fName := fName + LLISTFILEEXTENSION;
        end;                                        (* end of case statement *)
    end;                                       (* end of FixFileName routine *)

(*\*)
(* This creates a file of the type specified.  The routine will also create the
   0th record for the new file and initialize it to all zeroes.  This is all
   that needs to be done unless an index record is being created.  To create an
   index file use CreateIndex (BTree unit) which eventually calls this routine.
   This routine also creates a BITMAP for the newly created file unless the
   file being created is an LLIST file which does not have BITMAPs.

   note - file name passed as parameter does not contain a file extension.  The
   file will be changed to reflect the proper file extension.                *)

procedure CreateFile(var fName : FnString;
                     fType : FileTypes);

    (* This routine creates a BITMAP file for the file fName.                *)

    procedure CreateBitMap(fName : FnString);

    var
        bmFName : FnString;

        begin
        bmFName := fName;
        DeleteFileExtension(bmFName);
        CreateFile(bmFName,BITMAP);
        end;                                  (* end of CreateBitMap routine *)

var
    tempFile : File;
    page : SinglePage;

    begin
    FixFileName(fName,fType);
    RewriteUntypedFile(fName,tempFile,PAGESIZE);  (* force creation of new file
                                                     - will rewrite old file if
                                                       it exists             *)
    FillChar(page,PAGESIZE,0);                    (* 0th record of all zeros *)
    StorePage(fName,0,page);                             (* store 0th record *)
    if (fType <> BITMAP) and (fType <> LLIST) then
       begin
       CreateBitMap(fName);
       end;
    end;                                        (* end of CreateFile routine *)

(*\*)
(* This routine will delete a file.  It accomplishes this by removing all
   associated pages from the page buffer, closing the file, deleting the file
   from the files open buffer and deleting the file from disk.  If the file
   type is either DATA or INDEX (determined by file extension) then the
   associated BITMAP file will also be deleted.  Never !!! delete a BITMAP
   file explicitly.                                                          *)

procedure DeleteFile(fName : FnString);

var
    bmFName : FnString;
    tempFile : File;

    begin
    ReleaseAllPages(fName);                    (* release all pages for this
                                                        file from the buffer *)
    OpenUntypedFile(fName,tempFile,PAGESIZE);        (* needed to get the file
                                                        id (tempFile)        *)
    CloseFile(fName);
    Erase(tempFile);
    case FindFileType (fName) of
        LLIST,
        BITMAP : ;
        INDEX,
        DATA   : begin
                 bmFName := fName;
                 ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
                 DeleteFile(bmFName);
                 end;
        end;                                        (* end of case statement *)
    end;                                        (* end of DeleteFile routine *)

(*\*)
(* This routine will find the first unused record (logical or physical
   depending on the what type of file the record belongs to).  It is used for
   creating a new record.  Once the first unused record is determined it
   will be marked as used (using the BITMAP).  If an INDEX record is called
   for, the routine will find a free physical record.  If a data record is
   being requested, then the routine will locate a free logical record.
   The first free record from the beginning of the file will be returned.
   (BITMAP bit will be set).

   This routine is not used to get new records for a BITMAP file since BITMAP
   files don't have BITMAPS.

   This is a rather complicated scheme which uses an existence BITMAP to
   determine if each record is in use.  The existence BITMAP file
   consists of some number of physical records.  Each record contains PAGESIZE
   bytes.  Each byte has 8 bits.  Each bit corresponds to 1 record
   in the file.  If the bit is 1 then the record exists, if it is 0 then the
   record does not exist (is not in use).

   Remember, a record could be either a logical or a physical record depending
   on file type.                                                             *)

function FirstUnUsedRecord(fName : FnString) : RecordNumber;

var
    dummyPage,                                  (* used as dummy for calling
                                                   CreatePage when creating new
                                                   page for fname            *)
    page : SinglePage;                          (* copy of page in buffer *)
    byteCtr : 0 .. PAGESIZE;                    (* byte position within page *)
    recCtr : PrNumber;                          (* bit map record counter *)
    found,                                      (* BITMAP record loop *)
    done,                                       (* byte loop *)
    through : boolean;                          (* bit loop *)
    bmFName : FNString;                         (* bit map file name *)
    bitCtr : BytePosition;                      (* bit position within byte  *)
    newRecord : RecordNumber;                   (* new record number *)

    begin
    bmFName := fName;
    ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
    recCtr := 0;
    found := FALSE;
    while not found do                                 (* BITMAP record loop *)
        begin
        if PageExists(bmFName,recCtr) then            (* if past last record *)
            begin
            FetchPage(bmFName,recCtr,page);           (* get next b m record *)
            end
        else
            begin
            FillChar(page,PAGESIZE,0);              (* create new record page
                                                     for this bit map record *)
            end;
        byteCtr := 0;
        done := FALSE;
        while not done do                                       (* byte loop *)
            begin
            if byteCtr = PAGESIZE then
                begin
                done := TRUE;
                end
            else
                begin
                byteCtr := byteCtr + 1;
                bitCtr := 7;
                through := FALSE;
                while not through and (page[byteCtr] <> MAXBYTE) do
                              (* the check against MAXBYTE is for efficiency
                               since it will preclude checking individual
                               bits for a byte in which all bits are set
                               to one                                     *)
                    begin                                        (* bit loop *)
                    if not BitOn(page[byteCtr],bitCtr) then
                        begin
                        through := TRUE;
                        done := TRUE;
                        found := TRUE;
                        newRecord := (recCtr * PAGESIZE * 8) +
                                     ((byteCtr - 1) * 8) +
                                     (8 - bitCtr);
                        FirstUnUsedRecord := newRecord;
                        SetBit(page[byteCtr],bitCtr,1);
                        StorePage(bmFName,recCtr,page);
                        end
                    else
                        begin
                        if bitCtr = 0  then
                            begin
                            through := TRUE;
                            end
                        else
                            begin
                            bitCtr := bitCtr - 1;
                            end;
                        end;
                    end;
                end;
            end;
        recCtr := recCtr + 1;
        end;
    end;                                 (* end of FirstUnUsedRecord routine *)

(*\*)
(* This routine will delete a Logical or Physical record from a file.  It will
   accomomplish this by setting the appropriate bit in the associated BITMAP
   to zero.  It will also release the page from the buffer if the record is in
   the buffer.  Prior to deleting the record, this routine checks to make sure
   that the record is actually in use.  It it is not then it is not deleted.
   (Nothing happens)

   note : This routine will release the page from the buffer if it is an index
   file (a physical record).  If it is a data record the page will not be
   released.  It is somewhat complicated to determine if one or more pages can
   be released in this latter case.  This is because a logical record could use
   part of a physical record or a couple of physical records.  Releasing
   the records will allow that buffer space to be used.  Not releasing it
   means that the page will be swapped out when it gets old.  The routines
   will still function normally.  It is important to note that the logical
   records are always checked against the appropriate bitmat prior to using
   them.  I may do the releasing for logical records latter.                 *)

procedure DeleteRecord(fName : FnString;
                       rNum : RecordNumber);

var
    page : SinglePage;
    bitMapRecNum : PrNumber;
    targetBit : BytePosition;
    targetByte : PageRange;
    bmFName : FnString;
    tempString : ExtensionString;

    function FileType(fName : FnString) : FileTypes;
    {$V-}                    (* turn off strong type checking for parameters *)
        begin
        EndOfString(fName,4,tempString);
        if tempString = BITMAPFILEEXTENSION then FileType := BITMAP else
        if tempString = INDEXFILEEXTENSION  then FileType := INDEX  else
                                                 FileType := DATA;
        end;                                      (* end of FileType Routine *)
    {$V+}                    (* turn on strong type checking for parameters  *)

    begin
    if RecordUsed(fName,rNum) then         (* if it doesn't exist do nothing *)
        begin
        if FileType(fName) = INDEX then              (* see note above *)
            begin
            ReleasePage(fName,rNum);             (* release page from buffer *)
            end;
        bmFName := fName;
        ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
        bitMapRecNum := (rNum - 1) Div (8 * PAGESIZE); (* correct BITMAP rec *)
        FetchPage(bmFName,bitMapRecNum,page);
        targetByte := (((rNum - 1) mod (8 * PAGESIZE)) div 8) + 1;
        targetbit := (rNum - 1) mod 8;
        targetBit := (targetBit xor 7) and 7; (* this will yield the correct
                                                 bit position within the byte.
                                                 This is necessary because bit
                                                 7 (most significant) in the
                                                 byte is the existence bit for
                                                 the first record not the
                                                 eighth                      *)

        SetBit(page[targetByte],targetBit,0);
        StorePage(bmFName,bitMapRecNum,page);
        end;
    end;                                      (* end of DeleteRecord routine *)

(*\*)
(* This routine will check to see if a logical or physical record is currently
   in use.  It accomplishes this by using the appropriate BITMAP.            *)

function RecordUsed(fName : FnString;
                    rNum : RecordNumber) : Boolean;

var
    page : SinglePage;
    bitMapRecNum : PrNumber;
    targetBit : BytePosition;
    targetByte : PageRange;
    bmFName : FnString;

    begin
    bmFName := fName;
    ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
    bitMapRecNum := (rNum - 1) Div (8 * PAGESIZE);   (* correct BITMAP record *)
    if PageExists(bmFName,bitMapRecNum) then
        begin
        FetchPage(bmFName,bitMapRecNum,page);
        targetByte := (((rNum - 1) mod (8 * PAGESIZE)) div 8) + 1;
        targetbit := (rNum - 1) mod 8;
        targetBit := (targetBit xor 7) and 7; (* this will yield the correct
                                                 bit position within the byte.
                                                 This is necessary because bit
                                                 7 (most significant) in the
                                                 byte is the existence bit for
                                                 the first record not the
                                                 eighth                      *)

        RecordUsed := BitOn(page[targetByte],targetBit);
        end
    else
        begin
        RecordUsed := FALSE;
        end;
    end;                                        (* end of RecordUsed routine *)

(*\*)
(* This routine will set the appropriate BITMAP to show that a given
   logical or physical record is currently in use.                           *)

procedure SetRecordUsed(fName : FnString;
                        rNum : RecordNumber);

var
    page : SinglePage;
    bitMapRecNum : PrNumber;
    targetBit : BytePosition;
    targetByte : PageRange;
    bmFName : FnString;

    begin
    bmFName := fName;
    ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
    bitMapRecNum := (rNum - 1) Div (8 * PAGESIZE);  (* correct BITMAP record *)
    if PageExists(bmFName,bitMapRecNum) then
        begin
        FetchPage(bmFName,bitMapRecNum,page);
        end
    else
        begin
        FillChar(page,PAGESIZE,0);
        end;
    targetByte := (((rNum - 1) mod (8 * PAGESIZE)) div 8) + 1;
    targetbit := (rNum - 1) mod 8;
    targetBit := (targetBit xor 7) and 7; (* this will yield the correct bit
                                             position within the byte.  This is
                                             necessary because bit 7 (most
                                             significant) in the byte is the
                                             existence bit for the first
                                             record not the eighth           *)
    SetBit(page[targetByte],targetBit,1);        (* set the BITMAP bit to on *)
    StorePage(bmFName,bitMapRecNum,page);
    end;                                        (* end of RecordUsed routine *)

(*\*)
(* This routine will determine which logical record or physical record
   (depending on if its a DATA or INDEX file) is the last one used. It uses the
   associated BITMAP to accomplish this.  The routine returns the record number
   of the last record in use.  If no records are in use then 0 will be returned.
   Remember, the INDEX and DATA files do not use record zero for normal data.
   The zero records are used for special purposes if at all.  All files
   (BITMAP,INDEX,DATA) have zeroth records which are created when the file is
   created.                                                                  *)

function LastUsedRecord(fName : FnString) : RecordNumber;

var
    recCnt : RecordNumber;
    page : SinglePage;
    byteCnt : 0 .. PAGESIZE;
    bitCtr : BytePosition;
    bmFName : FnString;
    found : Boolean;

    begin
    bmFName := fName;
    ChangeFileExtension(bmFName,BITMAPFILEEXTENSION);
    recCnt := 0;
    while PageExists(bmFName,recCnt) do
        begin
        recCnt := recCnt + 1;
        end;
    recCnt := recCnt - 1;
    found := FALSE;
    while (not found) and (recCnt >= 0) do
        begin
        FetchPage(bmFName,recCnt,page);
        byteCnt := PAGESIZE;
        while (byteCnt <> 0) and (not found) do
            begin
            if page[byteCnt] <> 0 then
                begin
                found := TRUE;
                end
            else
                begin
                byteCnt := byteCnt - 1;
                end;
            end;
        if not found then
            begin
            recCnt := recCnt - 1;
            end;
        end;
    if found then
        begin
        bitCtr := 0;
        while not BitOn(page[byteCnt],bitCtr) do
            begin
            bitCtr := bitCtr + 1;
            end;
        LastUsedRecord := (((byteCnt - 1) * 8) + ((bitCtr XOR 7) and 7) + 1)
                        + (PAGESIZE * recCnt * 8);
        end
    else
        begin
        LastUsedRecord := 0;                               (* no last record *)
        end;
    end;                                    (* end of LastUsedRecord routine *)


begin
end.                                                    (* end of Files unit *)