Scan a directory structure recursively without recursivity

[cy-5]

I've just finished converting my delphi directory structure scan function.

Here is what it look like in PB. To be able to do this I add directories in a stack directory structure.

Here is the code:

Code: Select all

;->Stack.pb

Structure TStackElement
  *MptrData
  *MptrNext.TStackElement
EndStructure

Structure TStack
  *MptrFirst.TStackElement
EndStructure

Declare.l Stack_Init(*stack.TStack)
Declare.l Stack_Push(*stack.TStack, *ptrData)
Declare.l Stack_Pop(*stack.TStack)
Declare.l Stack_Clear(*stack.TStack)

Procedure.l Stack_Init(*stack.TStack)
  If (*stack = 0) : ProcedureReturn(#False) : EndIf
  
  *stack\MptrFirst = 0
  
  ProcedureReturn(#True)
EndProcedure ;Procedure.l Stack_Init(*stack.TStack)

Procedure.l Stack_Push(*stack.TStack, *ptrData)
  Protected *Lelement.TStackElement = 0

  If(*stack = 0) : ProcedureReturn(#False) : EndIf
  
  *Lelement = AllocateMemory(SizeOf(TStackElement))
  
  If (*Lelement = 0) : ProcedureReturn(#False) : EndIf
  
  *Lelement\MptrNext = *stack\MptrFirst
  *Lelement\MptrData = *ptrData
  *stack\MptrFirst = *Lelement
  
  ProcedureReturn(#True)
EndProcedure ;Procedure.l Stack_Push(*stack.TStack, *ptrData)

Procedure.l Stack_Pop(*stack.TStack)
  Protected *LptrFirstTemp.TStackElement = 0

  If (*stack = 0) : ProcedureReturn(#False) : EndIf
  
  If (*stack\MptrFirst = 0) : ProcedureReturn(#False) : EndIf
  
  *LptrFirstTemp = *stack\MptrFirst
  
  If (*LptrFirstTemp\MptrData <> 0) : FreeMemory(*LptrFirstTemp\MptrData) : EndIf
  
  *stack\MptrFirst = *stack\MptrFirst\MptrNext
  
  FreeMemory(*LptrFirstTemp)  
  
  ProcedureReturn(#True)

EndProcedure ;Procedure.l Stack_Pop(*stack.TStack)

Procedure.l Stack_Clear(*stack.TStack)
  Protected LbooFnResult.l = #False

  If (*stack = 0) : ProcedureReturn(#False) : EndIf
  
  If (*stack\MptrFirst) : ProcedureReturn(#False) : EndIf
  
  Repeat
    LbooFnResult = Stack_Pop(*stack)
  Until(*stack\MptrFirst = 0)

  ProcedureReturn(#True)

EndProcedure ;Procedure.l Stack_Clear(*stack.TStack)

;->ScanDirStruct.pb

Structure TFileSysEntrie
  MintDirectoryNumber.l
  MdatCreated.l
  MdatAccessed.l
  MdatModified.l
  MstrName.s
  MbooIsDirectory.b
  MqSize.q
  MintAttributes.l
EndStructure

Structure TStructSearch
  MstrPath.s
EndStructure

Prototype ProtoExecSearchHandler(*searchHandler, strPath.s, *entrieFileSys.TFileSysEntrie)

Structure TSearchHandler
  Exec.ProtoExecSearchHandler
EndStructure

Enumeration
  #CintGetNoEntrie
  #CintGetFirstEntrie
  #CintGetNextEntrie
EndEnumeration 

Global GstrOSDirSep.s = ""
CompilerIf (#PB_Compiler_OS = #PB_OS_Linux) Or (#PB_Compiler_OS = #PB_OS_MacOS)
  GstrOSDirSep = "/"
CompilerElse
  GstrOSDirSep = "\"
CompilerEndIf

Declare.l __NameIsDotOrTwoDots(strName.s)
Declare.l __FillFileSysEntrie(intDirectoryNumber.l, *entrieFileSys.TFileSysEntrie, booNext.b = #False)
Declare.l __FindFirstFileSysEntrie(strPath.s, strFilter.s, *entrieFileSys.TFileSysEntrie)
Declare.l __FindNextFileSysEntrie(*entrieFileSys.TFileSysEntrie)
Declare.l __FindCloseFileSysEntrie(*entrieFileSys.TFileSysEntrie)
Declare.l ScanDirStruct(strPathDir.s, *searchHandler.TSearchHandler)

Procedure.l __NameIsDotOrTwoDots(strName.s)
  Protected LstrDot.s = "."
  Protected LstrTwoDots.s = ".."
  Protected LbooIsDot.b = #False
  Protected LbooIsTwoDots.b = #False

  ;If the name has no characters then return that the name received
  ;is not a "." or ".." string.
  If Len(strName) = 0 : ProcedureReturn(#False)  : EndIf
  
  ;If the size of the name received is the number of characters of LstrDot(which is 1) then
  If Len(strName) = Len(LstrDot)
    
    ;If the name and LstrDot are the same then
    ;set that the name received is a "." string.    
    If CompareMemoryString(@strName, @LstrDot, #PB_String_NoCase, Len(LstrDot)) = #PB_String_Equal
      LbooIsDot = #True
    EndIf  
    
  EndIf ;If Len(strName) = Len(LstrDot)
  
  
  ;If the name is not a "." character then
  If (LbooIsDot = #False)
  
    ;If the length of the name received is sam as the number of characeters of LstrDot(which is 2) then
    If Len(strName) = Len(LstrTwoDots)
    
      ;If the name and LstrTowDots are the same then
      ;set that the name received is a ".." string.
      If CompareMemoryString(@strName, @LstrTwoDots, #PB_String_NoCase, Len(LstrTwoDots)) = #PB_String_Equal
        LbooIsTwoDots = #True
      EndIf  
      
    EndIf ;If Len(strName) = Len(LTwoDots)
    
  EndIf ;If (LbooIsDot = #False)
  
  ;Return if the name received is a "." or a ".." string.
  ProcedureReturn((LbooIsDot = #True) Or (LbooIsTwoDots = #True))

EndProcedure ;Procedure.l __NameIsDotOrTwoDots(strName.s)

Procedure.l __FillFileSysEntrie(intDirectoryNumber.l, *entrieFileSys.TFileSysEntrie, booNext.b = #False)

  ;If the received file system entrie object is not a valid pointer
  ;then return that filling the system entrie object with the info
  ;of the current file system entrie examined failed.
  If (*entrieFileSys = 0) : ProcedureReturn(#False) : EndIf

  ;If the received directory identify a invvalid directory then return that
  ;filling the file system entrie received failed.
  If (IsDirectory(intDirectoryNumber) = 0) : ProcedureReturn(#False) : EndIf
  
  ;If it is specified to get the next directory entry and it is not possible to get it then
  ;return that filling file system entrie with the next entrie failed.
  If (booNext = #True)
    If (NextDirectoryEntry(intDirectoryNumber) = 0) : ProcedureReturn(#False) : EndIf
  EndIf
  
  ;Assign the received directory number to the received file system entrie.
  *entrieFileSys\MintDirectoryNumber = intDirectoryNumber
  
  ;Retrieve possible values of the current file system entrie and assign
  ;them to their respective members.
  *entrieFileSys\MdatCreated = DirectoryEntryDate(intDirectoryNumber, #PB_Date_Created)
  *entrieFileSys\MdatAccessed = DirectoryEntryDate(intDirectoryNumber, #PB_Date_Accessed)
  *entrieFileSys\MdatModified = DirectoryEntryDate(intDirectoryNumber, #PB_Date_Modified)
  *entrieFileSys\MstrName = DirectoryEntryName(intDirectoryNumber)
  If (DirectoryEntryType(intDirectoryNumber) = #PB_DirectoryEntry_Directory)
    *entrieFileSYs\MbooIsDirectory = #True
  Else
    *entrieFileSYs\MbooIsDirectory = #False
  EndIf
  *entrieFileSys\MqSize = DirectoryEntrySize(intDirectoryNumber)
  *entrieFileSys\MintAttributes = DirectoryEntryAttributes(intDirectoryNumber)
  
  ;Return that filling the received file system entrie succeeded.
  ProcedureReturn(#True)
  
EndProcedure ;Procedure.l __FillFileSysEntrie(intDirectoryNumber.l, *entrieFileSys.TFileSysEntrie, booNext.b =#False)

Procedure.l __FindFirstFileSysEntrie(strPath.s, strFilter.s, *entrieFileSys.TFileSysEntrie)
  Protected LintDirectoryNumber.l = 0
  Protected *LentrieFileSys.TFileSysEntrie = 0
  Protected LbooFnResult.l = #False
  
  ;If the file system object is not a valid pointer then return
  ;that first entrie were not found.
  If (*entrieFileSys = 0): ProcedureReturn(#False) : EndIf
  
  ;Try findinf first entrie in the received path.
  LintDirectoryNumber = ExamineDirectory(#PB_Any, strPath, strFilter)
  
  ;If no entrie is found then return a invalid pointer
  ;as the first file system entrie found.
  If (LintDirectoryNumber = 0) : ProcedureReturn(#False) : EndIf
  
  ;If the fist entrie in the directory were not found then
  ;close examination of the directory and return that nothing
  ;were found.
  If (NextDirectoryEntry(LintDirectoryNumber) = 0)
    FinishDirectory(LintDirectoryNumber)
    ProcedureReturn(#False)
  EndIf
  
  ;Retrieve information about current entrie examines by
  ;the opened directory list and assign them to the file
  ;system entrie object passed.
  LbooFnResult = __FillFileSysEntrie(LintDirectoryNumber, *entrieFileSys)
  
  ;Return pointer to the first directory entrie of the directory
  ;list opened.
  ProcedureReturn(#True)

EndProcedure ;Procedure.l __FindFirstFileSysEntrie(strPath.s, strFilter.s, *entrieFileSys.TFileSysEntrie)

Procedure.l __FindNextFileSysEntrie(*entrieFileSys.TFileSysEntrie)

  ;If the file system object is not a valid pointer then return
  ;that next entrie were not found.
  If (*entrieFileSys = 0): ProcedureReturn(#False) : EndIf
  
  ;Try getting info of the next file system entrie and return
  ;if that were possible or not. #True is specified for booNext parameter to
  ;make the function call NextDirectoryEntry to move to the next file system entrie
  ;and get its info.
  ProcedureReturn(__FillFileSysEntrie(*entrieFileSys\MintDirectoryNumber, *entrieFileSys, #True))
  
EndProcedure ;Procedure.l __FindNextFileSysEntrie(*entrieFileSys.TFileSysEntrie)


Procedure.l __FindCloseFileSysEntrie(*entrieFileSys.TFileSysEntrie)
  
  ;If the received file sytem entrie object is not a valid pointer then
  ;return that closing the directory list it contains failed.
  If (*entrieFileSys = 0) : ProcedureReturn(#False) : EndIf
  
  ;If the directory number contained in the received file system entrie 
  ;object is not valid directory list number then return that closing the directory list failed.
  If (IsDirectory(*entrieFileSys\MintDirectoryNumber)  = 0) : ProcedureReturn(#False) : EndIf
  
  ;Close opened directory list and clear members of the
  ;received file system entrie object.
  FinishDirectory(*entrieFileSys\MintDirectoryNumber)
  *entrieFileSys\MintDirectoryNumber = 0
  *entrieFileSys\MdatCreated = 0
  *entrieFileSys\MdatAccessed = 0
  *entrieFileSys\MdatModified = 0
  *entrieFileSys\MstrName = ""
  *entrieFileSYs\MbooIsDirectory = #False
  *entrieFileSys\MqSize = 0
  *entrieFileSys\MintAttributes = 0
  
  ;Return that closing directory list of the received file system entrie succeeded.
  ProcedureReturn(#True)

EndProcedure ;Procedure.l __FindCloseFileSysEntrie(*entrieFileSys.TFileSysEntrie)

Procedure.l ScanDirStruct(strPathDir.s, *searchHandler.TSearchHandler)
  Shared GstrOSDirSep.s
  
  Protected LstackDir.TStack
  Protected LstrNewSearchDir.s = ""
  Protected LentrieFileSys.TFileSysEntrie
  Protected LstrPath.s = strPathDir
  Protected LintAction.c = #CintGetNoEntrie
  Protected LbooIsDirScanned.b = #False
  Protected *LsearchElement.TStructSearch = 0
  Protected LbooFnResult.l = #False
  
  ;If the received search handler is not a valid pointer then
  ;return tha scanning directory structure failed.
  If (*searchHandler = 0) : ProcedureReturn(#False) : EndIf
  
  ;If the exec funtion of the search handler is not set then
  ;return that scanning directory structure failed.
  If (*searchHandler\Exec = 0) : ProcedureReturn(#False) : EndIf
  
  ;Init the stack. This set the pointer *MptrFirst to 0.
  LbooFnResult = Stack_Init(@LstackDir)
  
  
  ;If the first entrie of the received path can't be found then
  ;free memory allocated for the file system entrie and return
  ;that scanning directory structure failed.
  If (__FindFirstFileSysEntrie(LstrPath, "*.*", @LentrieFileSys) = #False)
    ProcedureReturn(#False)
  EndIf
  
  
  ;If the first entrie found is a directory and is not "." or ".." then
  If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
  
    ;Add the current path to the stack.
    *LsearchElement = AllocateMemory(SizeOf(TStructSearch))
    *LsearchElement\MstrPath = LstrPath + LentrieFileSys\MstrName + GstrOSDirSep
    LbooFnResult = Stack_Push(@LstackDir, *LsearchElement)
    
    ;Execute the Exec function of the search handler by passing it 
    ;the path and a pointer to the file system entrie found.
    *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)
  
  Else ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
  
    ;If the file system entrie is not "." or ".." then execute the Exec function
    ;of the search handler by passing it the path and a pointer to the file system
    ;entrie found.
    If (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
      *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)
    EndIf
    
  EndIf ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
    
  ;Set to get the next file system entrie.
  LintAction = #CintGetNextEntrie
    
  ;Scan until LintAction is equal to #CintGetNoEntrie
  Repeat
    
    ;If FindFirst call needed then    
    If (LintAction = #CintGetFirstEntrie)
      
      ;If there is no entrie inside the directory then
      If (__FindFirstFileSysEntrie(LstrPath, "*.*", @LentrieFileSys) = #False)
        
        ;Deallocate previous memory(by FindFirst Or FindNext).
        LbooFnResult = __FindCloseFileSysEntrie(@LentrieFileSys)
          
        ;Get the first directory of the serarch stack And
        ;remove it from the stack.          
        If (LstackDir\MptrFirst <> 0)
          
          ;Get the saved path.
          *LsearchElement = LstackDir\MptrFirst\MptrData
          LstrPath = *LsearchElement\MstrPath
          LbooFnResult = Stack_Pop(@LstackDir)
          *LsearchElement = 0
            
          ;The stack serve only For directories, so
          ;we need an other call of FindFirst().            
          LintAction = #CintGetFirstEntrie
            
        Else ;Else ;If (LstackDir\MptrFirst <> 0)
          
          ;All files and directory are scanned, so
          ;it is finished.
          LintAction = #CintGetNoEntrie
          LbooIsDirScanned = #True
          
        EndIf ;Else ;If (LstackDir\MptrFirst <> 0)
          
      Else ;Else ;If (__FindFirstFileSysEntrie(LstrPath, "*.*", @LentrieFileSys) = #False)
        
        ;Check current entrie is a directory but Not '.' or '..'
        ;because '.' go to the begining of the disk and '..' go
        ;to parent directory.
        If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
          ;Add the current path to the stack.
          *LsearchElement = AllocateMemory(SizeOf(TStructSearch))
          *LsearchElement\MstrPath = LstrPath + LentrieFileSys\MstrName + GstrOSDirSep
          LbooFnResult = Stack_Push(@LstackDir, *LsearchElement)       
            
          ;Execute the Exec function of the search handler by passing it 
          ;the path and a pointer to the file system entrie found.
          *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)              
            
        Else ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
          ;If the file system entrie is not "." or ".." then execute the Exec function
          ;of the search handler by passing it the path and a pointer to the file system
          ;entrie found.
          If (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
            *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)
          EndIf
          
        EndIf ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
        ;Set to get the next file system entrie.
        LintAction = #CintGetNextEntrie
        
      EndIf ;Else ;If (__FindFirstFileSysEntrie(LstrPath, "*.*", @LentrieFileSys) = #False)
      
    Else ;Else ;If (intAction = #CintGetFirstEntrie)
      
      ;If a FindNext call is needed then
      If (LintAction = #CintGetNextEntrie)
        
        ;If we can find a entrie in the directory then
        If (__FindNextFileSysEntrie(@LentrieFileSys) = #True)
                    
          ;Check current entrie is a directory but Not '.' or '..'
          ;because '.' go to the begining of the disk and '..' go
          ;to parent directory.
          If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
            ;Add the current path to the stack.
            *LsearchElement = AllocateMemory(SizeOf(TStructSearch))
            *LsearchElement\MstrPath = LstrPath + LentrieFileSys\MstrName + GstrOSDirSep
            LbooFnResult = Stack_Push(@LstackDir, *LsearchElement)       
            
            ;Execute the Exec function of the search handler by passing it 
            ;the path and a pointer to the file system entrie found.
            *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)              
            
          Else ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) And (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
            ;If the file system entrie is not "." or ".." then execute the Exec function
            ;of the search handler by passing it the path and a pointer to the file system
            ;entrie found.
            If (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)            
              *searchHandler\Exec(*searchHandler, LstrPath, @LentrieFileSys)
            EndIf
          
          EndIf ;Else ;If (LentrieFileSys\MbooIsDirectory = #True) (__NameIsDotOrTwoDots(LentrieFileSys\MstrName) = #False)
          
          ;Set to get the next file system entrie.
          LintAction = #CintGetNextEntrie   
                    
        Else ;Else ;If (__FindFirstFileSysEntrie(LstrPath, "*.*", @LentrieFileSys) = #False)   
          
          ;Deallocate previous memory(by FindFirst Or FindNext).
          LbooFnResult = __FindCloseFileSysEntrie(@LentrieFileSys)
          
          ;Get the first directory of the serarch stack And
          ;remove it from the stack.          
          If (LstackDir\MptrFirst <> 0)
          
            ;Get the saved path.
            *LsearchElement = LstackDir\MptrFirst\MptrData
            LstrPath = *LsearchElement\MstrPath
            LbooFnResult = Stack_Pop(@LstackDir)
            *LsearchElement = 0
            
            ;The stack serve only For directories, so
            ;we need an other call of FindFirst().            
            LintAction = #CintGetFirstEntrie
            
          Else ;Else ;If (LstackDir\MptrFirst <> 0)
          
            ;All files and directory are scanned, so
            ;it is finished.
            LintAction = #CintGetNoEntrie
            LbooIsDirScanned = #True
          
          EndIf ;Else ;If (LstackDir\MptrFirst <> 0)          
          
        EndIf  ;Else ;If (__FindNextFileSysEntrie(@LentrieFileSys)
      
      EndIf ;If (LintAction = #CintGetNextEntrie)
      
    EndIf ;Else ;If (intAction = #CintGetFirstEntrie)
    
  Until (LintAction = #CintGetNoEntrie) ;Repeat
  
  
  ;Return if the directory strucutre were scanned or not.
  ProcedureReturn(LbooIsDirScanned)
  
EndProcedure ;Procedure.l ScanDirStruct(strPathDir.s, *searchHandler.TSearchHandler)

Global Gtest.TSearchHandler

Procedure Test(*searchHandler.TSearchHandler, strPath.s, *entrieFileSys.TFileSysEntrie)

  Delay(1)

  ;If (*entrieFileSys\MbooIsDirectory = #False)
  ;  PrintN(strPath + *entrieFileSys\MstrName)
  ;EndIf

EndProcedure

Gtest\Exec = @Test()

OpenConsole()
PrintN("[PRESS ESC]")
Repeat
  Delay(1)
Until Inkey() = Chr(27)

ScanDirStruct(GstrOSDirSep + "usr" + GstrOSDirSep, @Gtest)

PrintN("[SCANNING FINISHED]")
PrintN("[PRESS ESC]")
Repeat
  Delay(1)
Until Inkey() = Chr(27)

There is only one thing I've noticed. It seems having a memory leak somewhere. I've tried running the program and just by scanning my complete hard drive memory at the end were 5MB. If anyone can find why please let me know. First thing I'm thinking is that it is a bug with the FileSystem lib or there is some FinishDirectory calls missing. So far I've seen nothing wrong. I'm using PB4.31 on Ubuntu 9.04. As I know I never got this problem with the delphi program I made with this algorithm.

[Matt]

What is the advantage of this over a recursive solution....?

[cy-5]

What is the advantage of this over a recursive solution....?

To answer that I should say: no more stack overflow

Try making a normal recursive that scan a complete hard drive. You'll have a stack overflow. Especially on LINUX which have a lot sub-directories.

At first the algorithm was to impress my teacher because he said making a file sytem scan structure thread will be harder than a recursive and that we will not have time to do it.

He was right about the harder part but it was not impossible. Yes I made the recursive but fall with a stack overflow which I did not liked.

Think about it...you want to get a list of the entire mp3 on your hardrive. By using a recursive you'll have a lot of time to pass before having the right solution. By this I mean without any stack overfow.

The delphi program I made was to scan complete FretsOnFire .ini files to extract the scores and put them in a Access database for us at my job.

I know recursivity is faster but not easy to implement if you don't want to get stack overflows. If you know how to do it then I will be glad to know about it

I should add that I've also made a complete c++ file system lib using this type of thinking.

So I should say this is not a bad idea.

[SFSxOI]

It started, it seemed to be running, but here on windows 7 it didn't really be seem to be scanning.

[UserOfPure]

It looks like the code is for Linux. There are several smaller versions in these forums that do a recursive scan with no stack problems, in like 10 lines of code or so. Something for the OP to think about.

[Fred]

Are you sure about the stack overflow issue on linux ? Each thread on linux is set to 1MB in PB, so get a stack overflow while recursing directory is virtually impossible (let's say 128 bytes of stack per dir, that would means 10.000 nested directories).

[Trond]

The stack on Windows grows automatically by 4096 kb. You won't get a stack overflow unless more than 4096 kb is allocated at once and from reverse.

The maximum stack size is by default something like 1 mb. This can be changed if you need more by putting something in a linker script (search the forum for it).

[Trond]

Are you sure about the stack overflow issue on linux ? Each thread on linux is set to 1MB in PB, so get a stack overflow while recursing directory is virtually impossible (let's say 128 bytes of stack per dir, that would means 10.000 nested directories).

Maybe he's examining the "." directory and in it finds a new "." directory? Just guessing.

[Fred]

The stack on Windows grows automatically by 4096 kb. You won't get a stack overflow unless more than 4096 kb is allocated at once and from reverse.

Note than PB now takes care of it automatically (it was a problem in early version).

[Joakim Christiansen]

It looks like the code is for Linux. There are several smaller versions in these forums that do a recursive scan with no stack problems, in like 10 lines of code or so. Something for the OP to think about.

Here is a little one I made, have not had any problems with it (neither tested it on Linux):

Code: Select all

Procedure scanDir(Directory$)
  Protected DirID, Ext$
  DirID = ExamineDirectory(#PB_Any,Directory$,"")
  If DirID
    While NextDirectoryEntry(DirID)
      If Left(DirectoryEntryName(DirID),1) <> "."
        If DirectoryEntryType(DirID) = #PB_DirectoryEntry_Directory
          scanDir(Directory$+""+DirectoryEntryName(DirID))
        Else
          Ext$ = LCase(GetExtensionPart(DirectoryEntryName(DirID)))
          If Ext$ = "pb"
            Debug Directory$+""+DirectoryEntryName(DirID)
          EndIf
        EndIf
      EndIf
    Wend
    FinishDirectory(DirID)
  EndIf
EndProcedure

scanDir("Z:\PureBasic\Projects") ;will list all .pb files

But the way he does stuff is very interesting I must say.

[freak]

A non-recursive version does not have to be any more complicated:

Code: Select all

; breadth-first search with a queue
;
NewList Queue.s()

AddElement(Queue())
Queue() = "C:\"

While FirstElement(Queue()) 
  Current$ = Queue()
  DeleteElement(Queue())
  Debug Current$

  If ExamineDirectory(0, Current$, "*")
    While NextDirectoryEntry(0)
      If DirectoryEntryType(0) = #PB_DirectoryEntry_Directory
        Name$ = DirectoryEntryName(0)
        If Name$ <> "." And Name$ <> ".."
          LastElement(Queue())
          AddElement(Queue())
          Queue() = Current$ + Name$ + "\"
        EndIf
      EndIf
    Wend
    FinishDirectory(0)
  EndIf
Wend

[pcfreak]

the basic stuff..
http://en.wikipedia.org/wiki/Tree_traversal

[cy-5]

Hi all! Thanks for your replies. For those who wants to try it using windows you should note that the test at the end is with a linux path. Try changing the first parameter to "C:".

About the stack overflow I should say I got it with previous versions of PB. Don't remember which one. Never tried again if I got stack overflow.

Sorry if I'm wrong about that. Also, don't remember which version of LINUX I used.

For the "." issue well I already ensured that in my algorithm it don't do anything if it is encountered as well as ".." Maybe its because I forgot the "." and ".." when I did the old linux version that I got the stack overflow.

But as I know on windows I ended up all time with a stack overflow with a normal recursive made with Borland Builder C++ 6.

I were thinking the stack size were limited directly on the motherboard. At least now I know we can up it ourself.

I've also need to say that my ScanDirStruct function will serve to make a auto-extractor executable using PB compression lib.

Once it'll be done I'll share it with PB comunity as well as the source code.

[cy-5]

I've just tried a recursive scan on linux and all is right. No stack overflow.
BTW there is really a memory leak.

Try running the following code on a LINUX machine. On my computer the system monitor display 2.6MB of memory at the end of the scan.

First I were thinking maybe it is the console that took this. After checked the console just make use of 84kB so it is not that.

Once the console program is started press Esc. Recursive scan will be done in "/usr" directory and sub-directories. Then once the scan is done a message will be displayed.

After this if you press esc it will enter in a REPEAT FOREVER loop. Check linux system monitor(if you have ubuntu it should be there) you'll see that the memory used is not freed.

It looks like FinishDirectory() call don't free all the memory after all.

Also If you learned liked me about recursivity is that you should not use any LOOPS in a recursivity function. My teacher sait it block the recursive function and is not that good. Maybe he is wrong. But I decided to use one in it so that It will be easier to implement and to see if there is no stack overflow problem or really a MEMORY LEAK somewhere.

I've checked the code of my non recursive function and all is fine. Just one thing I've changed. When I pop a directory from my stack I ensure the one at the top of the stack is cleared: by this I mean *LsearchElement\MstrPath = "". That way memory used by the string is really freed.

BTW as you can see there really a MEMORY LEAK with the FileSystem lib.

Code: Select all

;Setup the os separator depending on the compiler OS.
Global GstrOSDirSep.s = ""
CompilerIf (#PB_Compiler_OS = #PB_OS_Linux) Or (#PB_Compiler_OS = #PB_OS_MacOS)
  GstrOSDirSep = "/"
CompilerElse
  GstrOSDirSep = "\"
CompilerEndIf


Procedure ScanDirStructRec(strPath.s)
  
  Protected LintDirectoryNumber.l = 0
  
  LintDirectoryNumber = ExamineDirectory(#PB_Any, strPath, "*.*")
  
  If LintDirectoryNumber <> 0
    While NextDirectoryEntry(LintDirectoryNumber) <> 0
    
      Delay(1)    
      If DirectoryEntryType(LintDirectoryNumber) = #PB_DirectoryEntry_Directory And (DirectoryEntryName(LintDirectoryNumber) <> ".") And (DirectoryEntryName(LintDirectoryNumber) <> "..")
        ScanDirStructRec(strPath + DirectoryEntryName(LintDirectoryNumber) + GstrOSDirSep)
      EndIf
    
    Wend
    FinishDirectory(LintDirectoryNumber)
  EndIf

EndProcedure

OpenConsole()
PrintN("[TYPE ESC]")
Repeat
  Delay(1)
Until Inkey() = Chr(27)

ScanDirStructRec(GstrOSDirSep + "usr" + GstrOSDirSep)

PrintN("[SCANNING FINISHED]")
PrintN("[PRESS ESC AND CHECK MEM OF THE PROCESS]")

Repeat
  Delay(1)
Until Inkey() = Chr(27)

Repeat
  Delay(1)
ForEver

[/b]

[cy-5]

I had difficulty to sleep so I decided to make a recursivity procedure wich don't use any loop. I've tried it by scanning my complete hard drive and all is fine. No stack overflow.

Code: Select all

;Setup the os separator depending on the compiler OS.
Global GstrOSDirSep.s = ""
CompilerIf (#PB_Compiler_OS = #PB_OS_Linux) Or (#PB_Compiler_OS = #PB_OS_MacOS)
  GstrOSDirSep = "/"
CompilerElse
  GstrOSDirSep = "\"
CompilerEndIf

Declare ScanDirStructRec(strPath.s, intDirectoryNumber.l, booFindFirst.l = #True)


Procedure ScanDirStructRec(strPath.s, intDirectoryNumber.l, booFindFirst.l = #True)
  Shared GstrOSDirSep.s
  
  If booFindFirst = #True
  
    intDirectoryNumber = ExamineDirectory(#PB_Any, strPath, "*.*")
    
    If intDirectoryNumber <> 0
    
      If NextDirectoryEntry(intDirectoryNumber) <> 0
      
        PrintN(strPath + DirectoryEntryName(intDirectoryNumber))
  
        If (DirectoryEntryType(intDirectoryNumber) = #PB_DirectoryEntry_Directory) And (DirectoryEntryName(intDirectoryNumber) <> ".") And (DirectoryEntryName(intDirectoryNumber) <> "..") 
          ScanDirStructRec(strPath + DirectoryEntryName(intDirectoryNumber) + GstrOSDirSep, 0, #True)  
        EndIf
    
        ScanDirStructRec(strPath, intDirectoryNumber, #False)
        
      EndIf
    
      FinishDirectory(intDirectoryNumber)
    EndIf
  
  Else
  
    If NextDirectoryEntry(intDirectoryNumber) <> 0
  
      PrintN(strPath + DirectoryEntryName(intDirectoryNumber))
    
      If (DirectoryEntryType(intDirectoryNumber) = #PB_DirectoryEntry_Directory) And (DirectoryEntryName(intDirectoryNumber) <> ".") And (DirectoryEntryName(intDirectoryNumber) <> "..") 
        ScanDirStructRec(strPath + DirectoryEntryName(intDirectoryNumber) + GstrOSDirSep, 0, #True)
      EndIf    
    
      ScanDirStructRec(strPath, intDirectoryNumber, #False)    
  
    EndIf  
    
  EndIf

EndProcedure

OpenConsole()
PrintN("[TYPE ESC]")
Repeat
  Delay(1)
Until Inkey() = Chr(27)

ScanDirStructRec(GstrOSDirSep, 0)

PrintN("[SCANNING FINISHED]")
PrintN("[CHECK MEM OF THE PROCESS]")

Repeat
  Delay(1)
Until Inkey() = Chr(27)

;Repeat
;  Delay(1)
;ForEver