Now that we have a file system that we can initialize, rebuild, mount, and dismount, we need to be able to access the files in the file system. In order to do that, we need a way to search the folders for a given file. To distinguish this operation from searching the data in the files, we will call it file lookup instead of file search. At first glance, this may appear to be simple. By the time we are done with this article, you will see that this is one of the more complicated operations our file system will perform.

{ Lookup file in directory, returning index in directory (or -1 if not found).
  Free_Index will be set to the first free header in the index (or -1 if none
  before file). }
function TUOS_Native_File_System.Find_File( const FileSpec : string ;
    Directory : TUOS_Native_File ; var Free_Index : longint ) : longint ;

var Header : TUOS_File_Header ;
    S : string ;

begin
    Free_Index := -1 ;
    Result := 0 ;
    while( true ) do
    begin
        if( Directory.Read( 0, ( Result - 1 ) * sizeof( Header ),
	  sizeof( Header ), Header ) = 0 ) then
        begin
            // No more entries in this directory...
            Set_Last_Error( Create_Exception( UOS_File_System_Path_Not_Found, nil ) ) ;
            Result := -1 ;
            exit ;
        end ;
        if( ( Header.Name <> 0 ) and ( ( Header.Flags and FAF_DELETED ) = 0 ) ) then 
        begin // Not a null entry or deleted file
            S := Get_String( Header.Name ) ;
            if( WC_Match( FileSpec, S ) ) then
            begin
                exit ;
            end ;
        end else
        if( ( Header.Name = 0 ) and ( Free_Index < 0 ) ) then
        begin
            Free_Index := Result ;
        end ; // if( H.Name <> 0 )
        inc( Result ) ;
    end ;  // while( true )
    Result := -1 ;
end ;

function TUOS_Native_File_System.Lookup_Directory( Spec : string ) : TUOS_Native_File ;

var D : string ;
    Dummy : integer ;
    F : TUOS_Native_File ;
    H : TUOS_File_Header ;
    P : cardinal ;

begin
    Result := nil ;

    // Get root directory...
    if( copy( Spec, length( Spec ), 1 ) = '\' ) then
    begin
        setlength( Spec, length( Spec ) - 1 ) ;
    end ;
    if( Spec = '' ) then // Asked for root
    begin
        Result := Root ;
        exit ;
    end ;
    F := Root ;

    // Find specified directory...
    while( Spec <> '' ) do
    begin
        Dummy := pos( '\', Spec + '\' ) ;
        D := lowercase( copy( Spec, 1, Dummy - 1 ) ) ;
        Spec := copy( Spec, Dummy + 1, length( Spec ) ) ;
        P := 0 ;
        while( F.Read( 0, P, sizeof( H ), H ) > 0 ) do
        begin // Not a null entry or deleted file
            P := P + sizeof( H ) ;
            if( ( H.Name <> 0 ) and ( ( H.Flags and FAF_DELETED ) = 0 ) ) then 
            begin
                if( WC_Match( D, lowercase( Get_String( H.Name ) ) ) ) then
                begin
                    F := Create_File_Instance( F, P div sizeof( H ) ) ;
                    F.Header := H ;
                    if( Spec = '' ) then
                    begin
                        Result := F ;
                        exit ;
                    end ;
                    if( ( H.Flags and FAF_DIRECTORY ) = 0 ) then 
                    begin // Path contained a non-folder
                        if( F <> _Root ) then
                        begin
                            F.Free ;
                        end ;
                        exit ;
                    end ;
                    P := 0 ;
                    continue ;
                end ; // if
            end ; // if
        end ; // while

        // If we get here, we didn't find a match in the directory
        if( F <> _Root ) then
        begin
            F.Free ;
        end ;
        exit ;
    end ; // while( Spec <> '' )
    Result := F ;
end ; // TUOS_Native_File_System.Lookup_Directory

Wildcards:
Finding a specific file is not the only kind of file lookup we need to support. Users will want to do listings of all files in a folder, or all files with a specific extension, and so forth. We could leave it up to the directory program (eg "Explorer" on Windows) to open the folder file and work through the headers, but that would be less efficient and would require privileges that the user might not have. Further, it wouldn't support unprivileged users doing directory searches within their own programs. For these reasons, all file systems support wildcard lookups. A wildcard is a character in a filename template that represents one or more characters in the actual file names. For the technical users, the most flexible way to do this would be to support regular expressions. However, that is too technical for the general public and so all file systems support wildcards, although different operating systems support different wildcards (for instance, VMS supports a "%" wildcard). For our file system, we will support "*" and "?" wildcards. The question mark is used to match one single character. The asterisk is used to match any number of characters (including no characters at all). The File Processor will support additional wildcards, but it will apply those on top of what we do without our class having to know anything about them. Note that we break from the VMS specification by not supporting the "%" wildcard. The reason for this is because most people are used to being able to use "%" as a character in a filename. The utility provided by the wildcard is overshadowed by the potential confusion resulting from breaking with what most people are used to.
File extensions are a short code appended to the end of filenames that indicates the file's purpose or format. Usually they are separated from the rest of the filename by a dot (.). In olden days, the extension was kept physically separate from the filename in the file header. Modern operating systems allow any number of dots within a filename and extensions are largely a matter of usage rather than being built into the file system. But the convention is so commonly used that we need to provide a minimal amount of support for it. Typically, a wildcard specification which contains a dot is indicating the position of the extension. Without special handling, something like "*.A*" would match both filenames "File.A.txt" as well as "File.Application". Because our wildcard matching will largely be done from left to right, the first dot in the file name matches the dot in our wildcard specification. But convention says that the first file's extension is ".txt" and it shouldn't match the wildcard specification. So, in the case of a dot in the specification, we will need to match it up with the last dot appearing in the file name when we do our matching. We also have to handle a null extension. That is, when the filename ends with a dot. Further, we need to handle the case where there are no dots at all, in the file. This case is also considered a null extension. The idea being that the dot is more of a delimiter for the extension than an actual character. In fact, the early operating systems did not store the dot at all - it was always implied. Finally, it is customary for a single asterisk to match against any/all files regardless of extension. For ease of coding, we will internally normalize a wildcard specification of "*" as "*.*".

Unicode:
If all we had to deal with is wildcard matching, our job would be relatively easy. However, recall that we support Unicode filenames and store them in UTF8 format. UTF8 is simply a compressed way of storing Unicode. The use of UTF8 means that we need an added step of normalizing (decompressing) the UTF8 to Unicode-32.
But that's not all our matching function needs to do. Unix and its derivatives (like Linux) support case-sensitive filenames. That is, "This file.txt" and "this File.txt" are treated as different filenames. This may appeal to the more technically-minded people - and it is simpler to implement in code - but the average person doesn't see why these two names don't refer to the same file. In fact, Unix/Linux are the only operating systems I know of that allow this abomination. UOS will treat filenames in a case-insensitive way for the sake of the average person on planet Earth. However, this requires extra work on our part. This is not unique to Unicode, of course - we'd have to deal with it in an ASCII-only situation as well. The best way to simplify our code is to normalize the values we are comparing to either all lowercase or all uppercase. For various reasons which I won't go into, we will normalize everything to lowercase. In our example, both names would normalize to "this file.txt". Mind you, we will store the name using the mixed case specified by the user when the file is created or renamed. However, during our file lookup, we will normalize the strings before we do our matching. Though we need to attack this problem even without Unicode, the truth is that Unicode makes it a little more complicated. You see, there are sometimes multiple uppercase letters (for some languages) that normalize to a single lowercase letter. In other cases (eg Greek) the glyph used for a character changes if it is at the end of the word. For some characters, the process actually adds characters to the string. This whole process is called "character folding", but we will call it part of our normalization process. A more detailed description of all the issues involved can be found at The Unicode Consortium. Fortunately, the Unicode people have provided a table that gives us the folding mappings.
We also remove multiple spaces for similar reasons. Imagine trying to tell how many spaces separate other characters - especially when using a proportional font to display it. Most people couldn't tell if there were one, two, or three spaces. There are other characters which might be hard to distinguish, such as underscores which can run together to look like a solid line. However, both Windows and Linux support multiple underscores so we will also allow it so as to allow easier interchange of files between the different systems.
Armed with this information, we can now write our WC_Match function.

For the sake of explanation, let's look at a simplified version of the wildcard match routine, which assumes an already normalized and non-Unicode string:

    // Do wildcard match...
    Wildcard_Start := 1 ;
    Name_Start := 1 ;
    Wildcard_End := length( Wildcard ) ;
    Name_End := length( Name ) ;

    // Check prefix before first wildcard...
    Dummy := pos( '*', Wildcard ) ;
    if( Dummy > Wildcard_Start ) then // Something before the asterisk
    begin
        if( not Compare( Wildcard, Wildcard_Start, Dummy - Wildcard_Start, Name,
	  Name_Start, True ) ) then
        begin
            exit ;
        end ;
        Wildcard_Start := Dummy ;
        Name_Start := Dummy ;
    end ; // if( Dummy > Wildcard_Start )

    // Check suffix after last wildcard...
    Dummy := RPos( Wildcard, '*' ) ;
    if( Dummy < length( Wildcard ) ) then
    begin
        if( not Compare( Wildcard, Dummy + 1, length( Wildcard ) - Dummy, Name,
	  length( Name ) - ( length( Wildcard ) - Dummy ) + 1, True ) ) then
        begin
            exit ;
        end ;
        Wildcard_End := Dummy ;
        Name_End := length( Name ) - ( length( Wildcard ) - Dummy ) ;
    end ; // if( Dummy < length( Wildcard ) )

    // Check for remaining matches, left-to-right...
    while( Wildcard_Start <= Wildcard_End ) do
    begin
        if( Wildcard_Start >= Wildcard_End ) then // All that's left in the wildcard spec is "*"
        begin
            break ; // So we match whatever remains in Name
        end ;
        Dummy := _Pos( '*', Wildcard, Wildcard_Start + 1 ) ;
        S := Copy( Wildcard, Wildcard_Start + 1, Dummy - Wildcard_Start - 1 ) ;
        Dummy1 := _Pos( Name, S, Name_Start ) ;
        if( Dummy1 = 0 ) then
        begin
            exit ; // Not found
        end ;
        Name_Start := Dummy1 + Dummy - Wildcard_Start - 1 ;
        Wildcard_Start := Dummy ; // Move past wildcard and matching characters
    end ; // while

    Result := True ;
end ; // _Wildcard_Match

We made use of a Compare function that compares a substring of Wildcard to a substring of Name. Here is that function:

function Compare( const Contents : string ; Wildcard_Start, _Length : integer ;
    const Match : string ; Name_Start : integer ; Wildcard : boolean ) : boolean ;

var Loop : integer ;

begin
    // Setup...
    Result := False ;
    if( _Length < 1 ) then
    begin
        exit ;
    end ;
    if( Wildcard_Start < 1 ) then
    begin
        Wildcard_Start := 1 ;
    end ;
    if( Name_Start < 1 ) then
    begin
        Name_Start := 1 ;
    end ;
    if( Wildcard_Start + _Length > Length( Contents ) + 1 ) then
    begin
        _Length := Length( Contents ) - Wildcard_Start + 1 ;
    end ;

    // Do comparison...
    for Loop := 0 to _Length - 1 do
    begin
        if( Name_Start + Loop > length( Match ) ) then
        begin
            exit ;
        end ;
        if( Contents[ Wildcard_Start + Loop ] <> Match[ Name_Start + Loop ] ) then
        begin
            if( ( not Wildcard ) or ( Contents[ Wildcard_Start + Loop ] <> '?' ) ) then
            begin
                exit ;
            end ;
        end ;
    end ;
    Result := True ;
end ; // _Compare

We also use an Equal function that is a simplified version of Compare. Why not use Compare instead? The reason is that there is extra overhead in Compare (and in the call itself due to the extra parameters) - and we want the matching code to run fast.

function _Equal( const Contents, Match : string ) : boolean ;

var Loop : integer ;

begin
    Result := False ;
    if( Length( Contents ) <> length( Match ) ) then
    begin
        exit ;
    end ;
    for Loop := 1 to Length( Contents ) do
    begin
        if( ( Contents[ Loop ] <> Match[ Loop ] ) ) then
        begin
            if( ( Contents[ Loop ] <> '?' ) and ( Match[ Loop ] <> '?' ) ) then
            begin
                exit ;
            end ;
        end ;
    end ;
    Result := True ;
end ; // TUnicode_String.Equal

Likewise, our _Pos function looks for a string within another string, as does the Pascal pos() function. The difference is that we match on the question mark (?) wildcard.

function _Pos( const Contents : string ; const Value : string ;
    Start : integer = 1 ) : integer ;

var Dummy, Dummy1 : integer ;
    Found : boolean ;

begin
    Result := 0 ;
    if( Start > Length( Contents ) ) then
    begin
        exit ;
    end ;
    if( length( Value ) > Length( Contents ) - Start + 1 ) then
    begin
        exit ; // Substring is longer than our contents
    end ;
    for Dummy := Start to Length( Contents ) - length( Value ) + 1 do
    begin
        Found := True ;
        for Dummy1 := 1 to length( Value ) do
        begin
            if(
                ( Value[ Dummy1 ] <> Contents[ Dummy1 + Dummy - 1 ] )
                and
                ( Contents[ Dummy1 + Dummy - 1 ] <> '?' )
                and
                ( Value[ Dummy1 ] <> '?' )
              ) then
            begin
                Found := False ;
                break ;
            end ;
        end ; // for Dummy1
        if( Found ) then
        begin
            Result := Dummy ;
            exit ;
        end ;
    end ; // for Dummy
end ;

TUnicode_String
The preceding code was for the purpose of explaining the algorithm. Though we will be keeping the algorithm, we will not be keeping the code. If we were only dealing with ASCII strings, we would be (nearly) finished. However, that is not the case. So, we now present the TUnicode_String class, which contains all the support needed for the use of Unicode in our wildcard matching.

type TUnicode_String = class
                           private // Instance data...
                               Has_Asterisk : boolean ;
                               Contents : array[ 0..384 ] of cardinal ;

                           protected // Property handlers...
                               // Return length of our contents...
                               function Get_Length : integer ;
                               procedure Set_Length( Value : integer ) ;

                           public // API...
                               function As_String : string ;

                               // Assign our contents from a UTF8 string...
                               procedure Assign_From_String( const S : string ;
                                   Format : integer ) ;

                               { Return true if our substring matches the passed
                                 substring.  W_Start indicates the start
                                 position and _Length is the length of the
                                 substring.  Name_Start indicates the start in the
                                 compared string }
                               function Compare( Wildcard_Start, _Length : integer ;
                                   Match : TUnicode_String ; Name_Start : integer ;
                                   Wildcard : boolean ) : boolean ;

                               // Create...
                               function Copy( Start, Len : integer ) : TUnicode_String ;

                               // Return true if our contents are equal to the match
                               function Equal( Match : TUnicode_String ;
                                   Wildcard : boolean ) : boolean ;

                               // Insert character at given position
                               procedure Insert( Position : integer ;
                                   Value : cardinal ) ;

                               // Convert our characters to lowercase...
                               procedure Lowercase ;

                               // Position of substring...
                               function Pos( const Value : string ;
                                   Start : integer = 1 ) : integer ; overload ;

                               function Pos( const Value : TUnicode_String ;
                                   Start : integer = 1 ) : integer ; overload ;

                               // Return rightmost instance of Value
                               function RPos( Value : char ) : integer ;

                           public // Properties...
                               property Length : integer
                                   read Get_Length
                                   write Set_Length ;
                       end ; // TUnicode_String

procedure TUnicode_String.Assign_From_String( const S : string ;
    Format : integer ) ;

var Index, Size, Mask : integer ;
    Value : cardinal ;

begin
    Index := 1 ; // Index in Spec
    Contents[ 0 ] := 0 ;
    if( Format = 3 ) then // UTF8
    begin
        while( Index <= system.length( S ) ) do
        begin
            Value := 0 ;
            if( S[ Index ] > #$FC ) then
            begin
                Size := 6 ;
                Mask := 1 ;
            end else
            if( S[ Index ] > #$F8 ) then
            begin
                Size := 5 ;
                Mask := 3 ;
            end else
            if( S[ Index ] > #$F0 ) then
            begin
                Size := 4 ;
                Mask := 7 ;
            end else
            if( S[ Index ] > #$E0 ) then
            begin
                Size := 3 ;
                Mask := $F ;
            end else
            if( S[ Index ] > #$C0 ) then
            begin
                Size := 2 ;
                Mask := $1F ;
            end else
            begin
                Size := 1 ;
                Mask := $7F ;
            end ;
            while( Size > 0 ) do
            begin
                dec( Size ) ;
                Value := Value or ( ord( S[ Index ] ) and Mask ) ;
                if( Size > 0 ) then
                begin
                    Value := Value shl 6 ;
                end ;
                Mask := $3F ;
                inc( Index ) ;
            end ;
            inc( Contents[ 0 ] ) ;
            Contents[ Contents[ 0 ] ] := Value ;
        end ; // while( Index < system.length( S ) )
    end else
    begin
        Value := 0 ;
        Index := 1 ; // Index in S
        while( Index <= system.length( S ) ) do
        begin
            move( PChar( S )[ Index - 1 ], Value, Format ) ;
            Index := Index + Format ;
            inc( Contents[ 0 ] ) ;
            Contents[ Contents[ 0 ] ] := Value ;
        end ;
    end ; // if( Format = 3 )
end ; // TUnicode_String.Assign_From_String

function lowcase( V : cardinal ; var _Folding_Index : integer ) : cardinal ;

var L, H, Index : integer ;

begin
    Result := V ;
    if( ( V < $41 ) or ( V > $118BF ) ) then // Not within range of our table
    begin
        exit ;
    end ;
    L := 0 ;
    H := high( Foldings ) ;
    while( L < H ) do
    begin
        Index := L + ( ( H - L ) div 2 ) ;
        if( V = Foldings[ Index, 0 ] ) then
        begin
            if( Foldings[ Index, 2 ] > 0 ) then // Multiple outputs
            begin
                Result := 0 ;
                _Folding_Index := Index ;
                exit ;
            end ;
            Result := Foldings[ Index, 1 ] ;
            exit ;
        end else
        if( V < Foldings[ Index, 0 ] ) then
        begin
            H := Index ;
        end else
        begin
            L := Index + 1 ;
        end ;
        if( L >= H ) then
        begin
            exit ;
        end ;
    end ; // while( L < H )
end ; // lowcase


procedure TUnicode_String.Lowercase ;

var Dummy, V : integer ;
    _Folding_Index : integer ;

begin
    Dummy := 1 ;
    while( Dummy <= Length ) do
    begin
        V := lowcase( Contents[ Dummy ], _Folding_Index ) ;
        if( V = 0 ) then
        begin
            Contents[ Dummy ] := Foldings[ _Folding_Index, 1 ] ;
            for V := 2 to 3 do
            begin
                if( Foldings[ _Folding_Index, V ] <> 0 ) then
                begin
                    Insert( Dummy + 1, Foldings[ _Folding_Index, V ] ) ;
                    inc( Dummy ) ;
                end ;
            end ;
        end else
        begin
            Contents[ Dummy ] := V ;
        end ;
        inc( Dummy ) ;
    end ;
end ; // TUnicode_String.Lowercase

const Foldings : array[ 0..1320, 0..3 ] of cardinal =
      (
        ( $41, $61, 0, 0 ), // 65 "A"
        ( $42, $62, 0, 0 ),
        ( $43, $63, 0, 0 ),
        ( $44, $64, 0, 0 ),
        ( $45, $65, 0, 0 ),
        ( $46, $66, 0, 0 ),
        ( $47, $67, 0, 0 ),
        ( $48, $68, 0, 0 ),
        ( $49, $69, 0, 0 ),
        ( $4A, $6A, 0, 0 ),
        ( $4B, $6B, 0, 0 ),
        ( $4C, $6C, 0, 0 ),
        ( $4D, $6D, 0, 0 ),
        ( $4E, $6E, 0, 0 ),
        ( $4F, $6F, 0, 0 ),
        ( $50, $70, 0, 0 ),
        ( $51, $71, 0, 0 ),
        ( $52, $72, 0, 0 ),
        ( $53, $73, 0, 0 ),
        ( $54, $74, 0, 0 ),
        ( $55, $75, 0, 0 ),
        ( $56, $76, 0, 0 ),
        ( $57, $77, 0, 0 ),
        ( $58, $78, 0, 0 ),
        ( $59, $79, 0, 0 ),
        ( $5A, $7A, 0, 0 ), // "Z"
        ( $B5, $3BC, 0, 0 ),
        ( $C0, $E0, 0, 0 ),
        ( $C1, $E1, 0, 0 ),
        ( $C2, $E2, 0, 0 ),
        ( $C3, $E3, 0, 0 ),
        ( $C4, $E4, 0, 0 ),
        ( $C5, $E5, 0, 0 ),
        ( $C6, $E6, 0, 0 ),
        ( $C7, $E7, 0, 0 ),
        ( $C8, $E8, 0, 0 ),
        ( $C9, $E9, 0, 0 ),
        ( $CA, $EA, 0, 0 ),
        ( $CB, $EB, 0, 0 ),
        ( $CC, $EC, 0, 0 ),
        ( $CD, $ED, 0, 0 ),
        ( $CE, $EE, 0, 0 ),
        ( $CF, $EF, 0, 0 ),
        ( $D0, $F0, 0, 0 ),
        ( $D1, $F1, 0, 0 ),
        ( $D2, $F2, 0, 0 ),
        ( $D3, $F3, 0, 0 ),
        ( $D4, $F4, 0, 0 ),
        ( $D5, $F5, 0, 0 ),
        ( $D6, $F6, 0, 0 ),
        ( $D8, $F8, 0, 0 ),
        ( $D9, $F9, 0, 0 ),
        ( $DA, $FA, 0, 0 ),
        ( $DB, $FB, 0, 0 ),
        ( $DC, $FC, 0, 0 ),
        ( $DD, $FD, 0, 0 ),
        ( $DE, $FE, 0, 0 ),
        ( $DF, $73, $73, 0 ),

function TUnicode_String.Copy( Start, Len : integer ) : TUnicode_String ;

begin
    // Setup...
    Result := TUnicode_String.Create ;
    if( Start > Length ) then
    begin
        exit ;
    end ;
    if( Start < 1 ) then
    begin
        Start := 1 ;
    end ;
    if( Start + Len - 1 > Length ) then
    begin
        Len := Length - Start + 1 ;
    end ;

    Result.Length := Len ;
    move( Contents[ Start ], Result.Contents[ 1 ], Len * sizeof( cardinal ) ) ;
end ; // TUnicode_String.Copy

function TUnicode_String.Compare( Wildcard_Start, _Length : integer ;
    Match : TUnicode_String ; Match_Start : integer ) : boolean ;

var Loop : integer ;

begin
    // Setup...
    Result := False ;
    if( _Length < 1 ) then
    begin
        exit ;
    end ;
    if( Wildcard_Start < 1 ) then
    begin
        Wildcard_Start := 1 ;
    end ;
    if( Match_Start < 1 ) then
    begin
        Match_Start := 1 ;
    end ;
    if( Wildcard_Start + _Length > Length + 1 ) then
    begin
        _Length := Length - Wildcard_Start + 1 ;
    end ;
    if( Match_Start + _Length > Match.Length + 1 ) then
    begin
        _Length := Match.Length - Match_Start + 1 ;
    end ;

    // Do comparison...
    for Loop := 0 to _Length - 1 do
    begin
        if( Contents[ Wildcard_Start + Loop ] <>
            Match.Contents[ Match_Start + Loop ] ) then
        begin
            if(
                ( Contents[ Wildcard_Start + Loop ] <> ord( '?' ) )
                and
                ( Match.Contents[ Wildcard_Start + Loop ] <> ord( '?' ) )
              ) then
            begin
                exit ;
            end ;
        end ;
    end ;
    Result := True ;
end ; // TUnicode_String.Compare


function TUnicode_String.Equal( Match : TUnicode_String ) : boolean ;

var Loop : integer ;

begin
    Result := False ;
    if( Length <> Match.Length ) then
    begin
        exit ;
    end ;
    for Loop := 1 to Length do
    begin
        if( ( Contents[ Loop ] <> Match.Contents[ Loop ] ) ) then
        begin
            if(
                ( Contents[ Loop ] <> ord( '?' ) )
                and
                ( Match.Contents[ Loop ] <> ord( '?' ) )
              ) then
            begin
                exit ;
            end ;
        end ;
    end ;
    Result := True ;
end ; // TUnicode_String.Equal

function TUnicode_String.Pos( const Value : TUnicode_String ;
    Start : integer = 1 ) : integer ;

var Dummy, Dummy1 : integer ;
    Found : boolean ;

begin
    Result := 0 ;
    if( Start > Length ) then
    begin
        exit ;
    end ;
    if( Value.Length > Length - Start + 1 ) then
    begin
        exit ; // Substring is longer than our contents
    end ;
    for Dummy := Start to Length - Value.Length + 1 do
    begin
        Found := True ;
        for Dummy1 := 1 to Value.Length do
        begin
            if(
                ( Value.Contents[ Dummy1 ] <> Contents[ Dummy1 + Dummy - 1 ] )
                and
                ( Contents[ Dummy1 + Dummy - 1 ] <> ord( '?' ) )
                and
                ( Value.Contents[ Dummy1 ] <> ord( '?' ) )
              ) then
            begin
                Found := False ;
                break ;
            end ;
        end ; // for Dummy1
        if( Found ) then
        begin
            Result := Dummy ;
            exit ;
        end ;
    end ; // for Dummy
end ; // TUnicode_String.Pos


function TUnicode_String.Pos( const Value : string ;
    Start : integer = 1 ) : integer ;

var Dummy, Dummy1 : integer ;
    Found : boolean ;

begin
    Result := 0 ;
    if( Start > Length ) then
    begin
        exit ;
    end ;
    if( System.Length( Value ) > Length - Start + 1 ) then
    begin
        exit ; // Substring is longer than our contents
    end ;
    for Dummy := Start to Length - system.length( Value ) + 1 do
    begin
        Found := True ;
        for Dummy1 := 1 to system.length( Value ) do
        begin
            if( ord( Value[ Dummy1 ] ) <> Contents[ Dummy1 + Dummy - 1 ] ) then
            begin
                Found := False ;
                break ;
            end ;
        end ; // for Dummy1
        if( Found ) then
        begin
            Result := Dummy ;
            exit ;
        end ;
    end ; // for Dummy
end ; // TUnicode_String.Pos


function TUnicode_String.RPos( Value : char ) : integer ;

var Loop, V : cardinal ;

begin
    V := ord( Value ) ;
    for Loop := Length downto 1 do
    begin
        if( Contents[ Loop ] = V ) then
        begin
            Result := Loop ;
            exit ;
        end ;
    end ;
    Result := 0 ;
end ;

Wildcard_Match and WC_Match
You've seen a version of Wilcard_Match earlier - this is the same algorithm but uses our class instead of Pascal strings.

function Wildcard_Match( Wildcard, Name : TUnicode_String ) : boolean ;

var Dummy, Dummy1 : integer ;
    Wildcard_Start, Wildcard_End, Name_Start, Name_End : integer ;
    S : TUnicode_String ;

begin
    // Quick check and setup...
    if( Wildcard.As_String = '*' ) then
    begin
        Result := True ;
        exit ;
    end ;

    // Non-wildcard check...
    if( not Wildcard.Has_Asterisk ) then
    begin
        Result := Wildcard.Equal( Name ) ;
        exit ;
    end ;
    Result := False ; // Assume failure

    // Do wildcard match...
    Wildcard_Start := 1 ;
    Name_Start := 1 ;
    Wildcard_End := Wildcard.Length ;
    Name_End := Name.Length ;

    // Check prefix before first wildcard...
    Dummy := Wildcard.Pos( '*' ) ;
    if( Dummy > Wildcard_Start ) then // Something before the asterisk
    begin
        if( not Wildcard.Compare( Wildcard_Start, Dummy - Wildcard_Start, Name,
          Name_Start ) ) then
        begin
            exit ;
        end ;
        Wildcard_Start := Dummy ;
        Name_Start := Dummy ;
    end ;

    // Check suffix after last wildcard...
    Dummy := Wildcard.RPos( '*' ) ;
    if( Dummy < Wildcard.Length ) then
    begin
        if( not Wildcard.Compare( Dummy + 1, Wildcard.Length - Dummy, Name,
          Name.Length - ( Wildcard.Length - Dummy ) + 1 ) ) then
        begin
            exit ;
        end ;
        Wildcard_End := Dummy ;
        Name_End := Name.Length - ( Wildcard.Length - Dummy ) ;
    end ;

    // Check for remaining matches, left-to-right...
    while( Wildcard_Start <= Wildcard_End ) do
    begin
        if( Wildcard_Start >= Wildcard_End ) then
        begin
            break ; // All that's left in the wildcard spec is an asterisk - we match
        end ;
        Dummy := Wildcard.Pos( '*', Wildcard_Start + 1 ) ;
        S := Wildcard.Copy( Wildcard_Start + 1, Dummy - Wildcard_Start - 1 ) ;
        Dummy1 := Name.Pos( S, Name_Start ) ;
        S.Free ;
        if( Dummy1 = 0 ) then
        begin
            exit ; // Not found
        end ;

        // Move past wildcard and matching characters...
        Name_Start := Dummy1 + Dummy - Wildcard_Start - 1 ;
        Wildcard_Start := Dummy ;
    end ; // while

    Result := True ;
end ; // Wildcard_Match

function Context_WC_Match( _Spec, _Spec_Extension : TUnicode_String ;
    Name : string ; Format : integer ) : boolean ;

var Dummy : integer ;
    _Name, _Name_Extension : TUnicode_String ;

begin
    // Setup...
    Result := False ; // Assume no match
    if( ( Format < 1 ) or ( Format > 4 ) ) then
    begin
        Format := 1 ;
    end ;
    Name := Edit( Name, 16 ) ;

    // Create the Unicode string instances...
    _Name := TUnicode_String.Create ;
    try
        _Name.Assign_From_String( Name, Format ) ;

        // Normalize to lowercase...
        _Name.Lowercase ;

        // Parse out the extensions...
        Dummy := _Name.RPos( '.' ) ;
        if( Dummy = 0 ) then
        begin
            Dummy := _Name.Length + 1 ;
        end ;
        _Name_Extension := _Name.Copy( Dummy + 1, 1024 ) ;
        _Name.Length := Dummy - 1 ;
        _Name.Has_Asterisk := ( _Name.Pos( '*' ) > 0 ) ;
        _Name_Extension.Has_Asterisk := ( _Name_Extension.Pos( '*' ) > 0 ) ;

        // Check for extension...
        try
            if( not Wildcard_Match( _Spec_Extension, _Name_Extension ) ) then
            begin
                exit ; // Extension doesn't match - exit with false
            end ;
            Result := Wildcard_Match( _Spec, _Name ) ;
        finally
            _Name_Extension.Free ;
        end ;
    finally
        _Name.Free ;
    end ;
end ; // Context_WC_Match


function Create_WC_Context( Spec : string ; Format : integer ;
    var Extension : TUnicode_String ) : TUnicode_String ;

var Dummy : integer ;

begin
    // Setup...
    if( ( Format < 1 ) or ( Format > 4 ) ) then
    begin
        Format := 1 ;
    end ;
    Spec := Edit( Spec, 16 ) ;

    // Pre-normalize the specification...
    Dummy := pos( '**', Spec ) ;
    while( Dummy > 0 ) do
    begin
        delete( Spec, Dummy, 1 ) ;
        Dummy := pos( '**', Spec ) ;
    end ;
    Dummy := pos( '*?', Spec ) ;
    while( Dummy > 0 ) do
    begin
        Spec := copy( Spec, 1, Dummy - 1 ) + '?*' +
            copy( Spec, Dummy + 2, length( Spec ) ) ;
        Dummy := pos( '*?', Spec ) ;
    end ;
    if( pos( '.', Spec ) = 0 ) then // No explicit extension
    begin
        Spec := Spec + '.*' ;
    end ;

    // Create the Unicode string instances...
    Result := TUnicode_String.Create ;
    Result.Assign_From_String( Spec, Format ) ;

    // Normalize to lowercase...
    Result.Lowercase ;

    // Parse out the extensions...
    Dummy := Result.RPos( '.' ) ;
    if( Dummy = 0 ) then
    begin
        Dummy := Result.Length + 1 ;
    end ;
    Extension := Result.Copy( Dummy + 1, 1024 ) ;
    Result.Length := Dummy - 1 ;
    Result.Has_Asterisk := ( Result.Pos( '*' ) > 0 ) ;
    Extension.Has_Asterisk := ( Extension.Pos( '*' ) > 0 ) ;
end ; // Create_WC_Context


function WC_Match( Spec, Name : string ; Format : integer ) : boolean ;

var _Spec, _Spec_Extension : TUnicode_String ;
    S : string ;

begin
    _Spec := Create_WC_Context( Spec, Format, _Spec_Extension ) ;
    S := _Spec.As_String ;
    if( ( S = '*' ) or ( S = '*.*' ) ) then
    begin
        Result := True ; // Wildcard matches anything/everything
        exit ;
    end ;
    try
        Result := Context_WC_Match( _Spec, _Spec_Extension, Name, Format ) ;
    finally
        _Spec.Free ;
        _Spec_Extension.Free ;
    end ;
end ; // WC_Match

Back to our File System class
The preceeding code supports the Find_File and Lookup_Directory methods, but there is one more File System method that makes use of the wildcard matching. When a wildcard is used in a file specification, there is a possibility that multiple file matches may be found. In the most extreme case, the wildcard could match every file on the disk. Rather than returning a list of all matches, which could be quite long, most operating systems support a one-at-a-time wildcard lookup. The initial call sets up the lookup operation and returns the first match. Subsequent calls find the next match after the one returned by the previous match. This continues until no more matches are found. Thus, the calling code loops through the results until it is done. To support multiple lookups happening at the same time (multiple users or tasks), each lookup operation is represented by a lookup context. The calls to the lookup function pass this context.
Lookup is an API function that provides the file lookup ability to the end user via the File Processor.

function TUOS_Native_File_System.Lookup( Spec : PChar ; var Context : pointer ) : PChar ;

var _Context : TLookup_Context ;
    Dir : string ;
    Dummy : integer ;
    Directory : TUOS_Native_File ;
    Filespec : string ;
    H : TUOS_File_Header ;
    S : string ;

begin
    Result := nil ;
    if( Context = nil ) then
    begin
        // Parse specification...
        S := Spec ;
        if( S = '' ) then
        begin
            exit ; // No context and no file spec
        end ;
        Dummy := length( S ) ;
        while( ( Dummy > 0 ) and ( S[ Dummy ] <> '\' ) ) do
        begin
            dec( Dummy ) ;
        end ;
        Dir := copy( S, 1, Dummy ) ;
        S := copy( S, Dummy + 1, length( S ) + 1 ) ;
        FileSpec := S ;
        Directory := Lookup_Directory( Dir ) ;
        if( Directory = nil ) then
        begin
            exit ; // Directory not found
        end ;

        // Create context...
        _Context := TLookup_Context.Create ;
        _Context.Spec := S ;
        _Context.Dir := Dir ;
        _Context.Index := 0 ; // Next file to read is index 0
        _Context.Directory := Directory ;
        _Context._Spec := Create_WC_Context( S, 3, _Context._Spec_Extension ) ;
        Context := _Context ;
    end ; // if( Context = nil )

    _Context := TLookup_Context( Context ) ;
    if( Lookup_Contexts.IndexOf( _Context ) = -1 ) then // Not a valid context
    begin
        exit ;
    end ;
    while( true ) do
    begin
        inc( _Context.Index ) ;
        if( _Context.Directory.Read( 0, ( _Context.Index - 1 ) * sizeof( H ),
	  sizeof( H ), H ) = 0 ) then
        begin
            // No more entries in this directory...
            _Context.Free ;
            Context := nil ;
            exit ;
        end ;
        if( ( H.Name <> 0 ) and ( ( H.Flags and FAF_DELETED ) = 0 ) ) then 
        begin // Not a null entry or deleted file
            S := Get_String( H.Name ) ;
            if( Context_WC_Match( _Context._Spec, _Context._Spec_Extension, S, 3 ) ) then
            begin
                Temp := S ;
                Result := PChar( Temp ) ;
                exit ;
            end ;
        end ; // if( H.Name <> 0 )
    end ;  // while( true )
end ; // TUOS_Native_File_System.Lookup

Finally, here is the TLookup_Context class and related function, used by our File System class:

var _Lookup_Contexts : TList = nil ;

function Lookup_Contexts : TList ;

begin
    if( _Lookup_Contexts = nil ) then
    begin
        _Lookup_Contexts := TList.Create ;
    end ;
    Result := _Lookup_Contexts ;
end ;


type TLookup_Context = class
                           public // Constructors and destructors...
                               constructor Create ;
                               destructor Destroy ; override ;

                           public // Instance data...
                               Dir, Spec : string ;
                               _Spec, _Spec_Extension : TUnicode_String ;
                               Directory : TUOS_Native_File ;
                               Index : longint ;
                       end ;


// Constructors and destructors...

constructor TLookup_Context.Create ;

begin
    inherited Create ;

    Lookup_Contexts.Add( self ) ;
end ;


destructor TLookup_Context.Destroy ;

begin
    _Spec.Free ;
    _Spec := nil ;
    _Spec_Extension.Free ;
    _Spec_Extension := nil ;
    Lookup_Contexts.Remove( self ) ;

    inherited Destroy ;
end ;

I ran some performance tests comparing the speed of the wildcard match using the Pascal string and using our TUnicode_String class. So, how does the overhead of the Unicode handling affect the speed of our comparisons? It is hard to say since different operations have different comparative speeds. Some operations were faster with our Unicode codes and some were faster with the Pascal string code. It is hard to predict what mix of operations would occur during normal UOS operation. In fact, it is likely that in an average environment, the mix would differ from time to time. So, in my test, I ran a number of what I thought were fairly "typical" operations in a loop - the exact same set on both types of routines. For what its worth, the Unicode tests was almost exactly one-half the speed of the non-Unicode test. I would like it to be faster, but considering the extra work involved and the tradeoffs we've discussed, I'm not entirely displeased.

I apologize for the length of this article. In the next (and shorter!) article, we will address other support methods for our file system class.