Page 1 of 1

Arrays, structures and linked lists in Batch files

Posted: 22 Apr 2012 00:10
by Aacini
In this SO topic the OP asked for "Arrays, linked lists and other data structures in Batch scripts". This subject was quite interesting to me, so I made some fascinating developments in this area and replied with this answer.

Before enter this topic I want to insert here a phrase I used before:
I occasionally wrote:I think the important point here is not to discuss if Batch really have such features or not, but the fact that you may use such features in a Batch file with the aid of a couple small tricks.
You may see this topic as a simulation of such features written in Batch language, but in the final analysis, most features of high level languages are also simulations in one or other way (remember that the RAM is just a flat set of bytes with no structure at all!). I tried to use the simplest/clearest way to achieve these simulations, but I know that many different ways to do the same thing exist.

1- ARRAY MANAGEMENT IN BATCH FILES

Arrays in Batch files may be simulated in a straightforward way: just write variable names in the form of array elements:

Code: Select all

set "elem[1]=First element"
set "elem[2]=Second one"
set "elem[3]=The third one"

To use another variable as index use Delayed Expansion: enclose index variable in percent symbols, and enclose the array element in exclamation marks:

Code: Select all

setlocal EnableDelayedExpansion
set "elem[1]=First element"
set "elem[2]=Second one"
set "elem[3]=The third one"
set i=2
echo !elem[%i%]!

rem You may use parameters of FOR command as indexes:
for /L %%i in (1,1,3) do echo !elem[%%i]!

You must use !index! to store values in array elements when the index is changed inside a FOR or IF:

Code: Select all

set num=0
for /F "delims=" %%a in (severalLines.txt) do (
   set /A num+=1
   set "elem[!num!]=%%a"
)

To get the value of an element when the index changes inside FOR/IF, enclose the element in double percent symbols and precede the command with CALL. For example, to move a range of array elements four places to the left:

Code: Select all

for /L %%i in (%start%,1,%end%) do (
   set /A j=%%i + 4
   call set "elem[%%i]=%%elem[!j!]%%"
)

Another way to achieve the previous process is to use an additional FOR command to change the delayed expansion of the index by an equivalent replaceable parameter, and then use the delayed expansion for the array element. This method runs faster than previous CALL:

Code: Select all

for /L %%i in (%start%,1,%end%) do (
   set /A j=%%i + 4
   for %%j in (!j!) do set "elem[%%i]=!elem[%%j]!"
)

If the array contain numbers, you may use SET /A command to directly process array element values with no need of the additional value expansion:

Code: Select all

for /L %%i in (%start%,1,%end%) do (
   set /A j=%%i + 4
   set /A "elem[%%i]=elem[!j!]"
)

Multi-dimensional arrays may be simulated in the same way, but there are different flavors to write the multiple indexes. The C-like notation matrix[%i%][%j%] have some advantages because we may extract a row from a matrix as a vector in a very easy way:

Code: Select all

:setVector vector=matrix[!row!]
for /F "tokens=3,4 delims=[]=" %%a in ('set %2') do (
   set "%1[%%a]=%%b"
)
exit /B

An interesting difference that Batch arrays have versus other programming languages is that the indexes are not restricted to be numerical values, so they may be any string. The Batch file below is an example of a two-dimensional array management program that uses no-numerical indexes; it is a very basic multi-language translation program that may "learn" new translation terms. The program have multiple limitations because it is focused on the array management part only.

TRANSLATE.BAT:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

rem Example of Multi-dimensional array management in Batch files
rem Antonio Perez Ayala - Apr/22/2012

rem Load Translation matrix from saved file, and define Language vector
call Translation.bat
for /F "tokens=2 delims=[]" %%v in ('set Translation[') do (
   set Language[%%v]=1
)
set anyModification=

:chooseFromTo
cls
echo I know these translation languages:
echo/
for /F "tokens=2 delims=[]" %%a in ('set Language[') do (
   echo     %%a
)
echo/
set fromTo=
set /P "fromTo=Type one or enter a new one (empty to end): "
if not defined fromTo goto endTranslation

for /F "tokens=1,2 delims=-" %%a in ("%fromTo%") do (
   set from=%%a
   set to=%%b
)
set Language[%fromTo%]=1
set Language[%to%-%from%]=1

   :readWord
   echo/
   set word=
   set /P "word=Enter word in first language: "
   if not defined word goto chooseFromTo
   if defined Translation[%fromTo%][%word%] (
      echo The translated word is: !Translation[%fromTo%][%word%]!
   ) else (
      set new=%to%
      set /P "new=I don't know that word, enter %to% equivalent: "
      set Translation[%fromTo%][%word%]=!new!
      set Translation[%to%-%from%][!new!]=%word%
      set anyModification=TRUE
   )
   goto readWord

:endTranslation
if defined anyModification (
   for /F %%v in ('set Translation[') do echo set %%v
) > Translation.bat
cls
TRANSLATION.BAT:

Code: Select all

set Translation[ENGLISH-SPANISH][RED]=ROJO
set Translation[ENGLISH-SPANISH][SUNDAY]=DOMINGO
set Translation[SPANISH-ENGLISH][DOMINGO]=SUNDAY
set Translation[SPANISH-ENGLISH][ROJO]=RED


2- STRUCTURES AND LINKED LISTS IN BATCH FILES

The Batch file below simulate structures and linked-list management. The program use such simulations to traverse through the directory tree of a given subdirectory and assemble a complex data scheme that include multiple linked lists comprised of these self-referential structures:

Code: Select all

struct DirNode {
    DirName    = Name of this DirNode
    Prev       = Pointer to previous DirNode at this level
    Next       = Pointer to next DirNode at this level
    NestedDir  = Pointer to first nested DirNode
    NestedFile = Pointer to first nested FileNode
}

struct FileNode {
    FileName = Name of this FileNode
    Prev     = Pointer to previous FileNode
    Next     = Pointer to next FileNode
}

After the whole data structure is created, the program process it and output a result similar of TREE command's.

I used structName.memberName notation for structure members and "%pointer%->memberName" notation for dynamic structures allocated via :malloc routine (quotes are mandatory). I simulated a pointer, that in C language is a real memory address, with an unique address that distinguish a certain variable from other instances of itself (in the same way of C language).

Most subroutines below have not any error checking to made they simpler and smaller, but such checking may be added if someone want to use these features in a real application. Of course, Batch is too slow to make good use of such features, but it may be a very good example of such features for educative purposes (i.e. to have a first contact with these concepts before using they in C language).

I suggest you to take paper and pencil and draw small rectangles ("nodes") that include arrows ("pointers") to other rectangles ("linked-list") while you review the Batch file below. Also, the program have a few commands written in UPPERCASE letters that are used just to trace the execution, so I suggest you to ignore such commands in the first reading.

MyTree.bat:

Code: Select all

@echo off

rem Example of Structures and Linked-lists management in Batch files
rem Antonio Perez Ayala - Apr/22/2012

rem Auxiliary variables for easier structure declaration
setlocal DisableDelayedExpansion
set struct=set
set {==^^
set ;=^^
set }=

FOR /F "SKIP=4 DELIMS=pR TOKENS=1,2" %%A IN (
       'reg query hkcu\environment /v temp' ) DO SET TAB=%%B
FOR /F %%A IN ('COPY /Z "%~F0" NUL') DO SET CR=%%A

setlocal EnableDelayedExpansion
rem Initialize global variables
set NULL=0
set heapPointer=%NULL%

goto Main


rem Auxiliary subroutine to echo "%pointer%->structMember" with no quotes

:show "value"
echo %~1
exit /B



/* "Method" to allocate a structure

   Parameter %1 is the structure name, that must be defined this way:
   set structName= member1=value1, member2="value2 with delimiters", ...
   Values are assigned to members when the struct is allocated

   Value returned in %2 variable is a "pointer" to the allocated struct */

:malloc structName pointer=
set /A heapPointer+=1, %2=heapPointer
set #=
for %%a in (!%1!) do (
   if not defined # (
      set #=%%a
   ) else (
      set "!%2!->!#!=%%~a"
      set #=
   )
)
exit /B



/* "Method" to release a structure

   Parameter %1 must be a "pointer" value to the struct to release */

:free pointer
for /F "delims==" %%a in ('set "%1->"') do (
   set "%%a="
)
exit /B



/* "Method" to insert a Node struct into a linked or double-linked list

   Param %1->Node after which the new Param %2->Node will be inserted

   This method use standard "Prev" and "Next" member names for the links */

:insert original new

rem Update new-Node links (backward if defined, and forward)
if "!%2->Prev!" neq "" (
   set "%2->Prev=%1"
)
set "%2->Next=!%1->Next!"

rem Change original-Node forward link to new-Node
set "%1->Next=%2"

rem Change "originally next"-Node backward link to new-Node, if defined and exists
if "!%2->Prev!" neq "" (
   if "!%2->Next!" neq "%NULL%" (
      set "!%2->Next!->Prev=%2"
   )
)

exit /B



/* "Method" to remove a Node struct from a linked or double-linked list

   Param %1->Node after which the %1->Node->Node will be removed

   This method use standard "Prev" and "Next" member names for the links

   Note that you must use :free to release the Head-node of a linked-list
   and that that node must be the last one to be released! */

:remove afterThis

rem Get a pointer to the Node after this one
set "#2=!%1->Next!"

rem Change this Node forward link to the node 2 places forward, if exists
if %#2% neq %NULL% (
   if "!%#2%->Next!" neq "%NULL%" (
      set "%1->Next=!%#2%->Next!"
   ) else (
      set "%1->Next=%NULL%"
   )
)

rem Change "2 places forward"-Node backward link to this Node, if defined and exists
if "!%1->Prev!" neq "" (
   if %#2% neq %NULL% (
      if "!%#2%->Next!" neq "%NULL%" (
         set "!%#2%->Next!->Prev=%1"
      )
   )
)

rem Release the Node after this one
call :free %#2%

exit /B



rem Recursive subroutine to create the data structure beneath a subDir

rem Parameter %1->parentDir Node of this Dir

:ProcessThisDir parentDir

rem This sub can NOT have SetLocal, because its purpose is create global variables

SET /A LEVEL+=1

rem Create the linked list of nested files in this level
set parentDir=%1
for %%f in (*.*) do (
   SET /A NODES_IN_LEVEL[%LEVEL%]+=1
   SET /P "=!CR!NODES BY LEVEL" <NUL >&2
   (FOR /L %%I IN (1,1,%LEVEL%) DO (
       SET /P "=!TAB!%%I: !NODES_IN_LEVEL[%%I]!"
   )) <NUL >&2
   call :malloc FileNode thisFile=
   set "!thisFile!->FileName=%%f"
   if defined parentDir (
      rem This node is the Head node of a new linked list
      set "%parentDir%->NestedFile=!thisFile!"
      set parentDir=
   ) else (
      rem This node is an additional one in the list
      set "!prevFile!->Next=!thisFile!"
   )
   rem In next iteration "thisNode" becomes "prevNode"
   set prevFile=!thisFile!
)

rem Create the linked list of nested directories in this level
set parentDir=%1
for /D %%d in (*) do (
   SET /A NODES_IN_LEVEL[%LEVEL%]+=1
   SET /P "=!CR!NODES BY LEVEL" <NUL >&2
   (FOR /L %%I IN (1,1,%LEVEL%) DO (
       SET /P "=!TAB!%%I: !NODES_IN_LEVEL[%%I]!"
   )) <NUL >&2
   call :malloc DirNode thisDir=
   set "!thisDir!->DirName=%%d"
   if defined parentDir (
      rem This node is the Head node of a new linked list
      set "%parentDir%->NestedDir=!thisDir!"
      set parentDir=
   ) else (
      rem This node is an additional one in the list
      set "!prevDir!->Next=!thisDir!"
   )
   rem In next iteration "thisNode" becomes "prevNode"
   set prevDir=!thisDir!

   rem Enter to each Subdir, process it recursively and go back to original Dir
   cd "%%d"
   rem Simulate a SetLocal on prevDir variable (and undefined parentDir)
   set /A sp+=1
   set prevDir[!sp!]=!prevDir!
   call :ProcessThisDir !thisDir!
   rem Simulate an EndLocal on prevDir variable (and undefined parentDir)
   set /A prevDir=prevDir[!sp!], sp-=1
   set parentDir=
   cd ..
)

SET /A LEVEL-=1

exit /B



rem Recursive subroutine to display the data structure beneath a DirNode

rem Parameter %1->DirNode to display
rem Parameter %2: nextMargin to add to current one

:DisplayThisNode thisNode nextMargin
setlocal EnableDelayedExpansion

set "margin=%margin%%~2"

rem Display FileNodes, if requested
if not defined showFiles% goto endShowFiles
rem Get current file margin
if "!%1->NestedDir!" neq "%NULL%" (
   set "fileMargin=│   "
) else (
   set "fileMargin=    "
)
rem Display nested FileNodes
set "nextFile=!%1->NestedFile!"
:While_nextFile neq %NULL% do
   if %nextFile% equ %NULL% goto WEnd_nextFile
   call :show "%margin%%fileMargin%!%nextFile%->FileName!"
   set "nextFile=!%nextFile%->Next!"
   goto While_nextFile
:WEnd_nextFile
if "!%1->NestedFile!" neq "%NULL%" (
   echo/%margin%%fileMargin%
)
:endShowFiles

rem Display nested DirNodes
set "nextDir=!%1->NestedDir!"
:While_nextDir neq %NULL% do
   if %nextDir% equ %NULL% goto WEnd_nextDir
   rem Get current dir margin
   if "!%nextDir%->Next!" neq "%NULL%" (
      set "dirMargin=├───"
      set "nextMargin=│   "
   ) else (
      set "dirMargin=└───"
      set "nextMargin=    "
   )
   rem Display Name of next DirNode
   call :show "%margin%%dirMargin%!%nextDir%->DirName!"
   rem Display contents of next DirNode
   call :DisplayThisNode %nextDir% "%nextMargin%"
   rem Pass to next DirNode in this level
   set "nextDir=!%nextDir%->Next!"
   goto While_nextDir
:WEnd_nextDir

exit /B



:Main

rem Show the help, if requested
if "%1" equ "/?" (
   echo Graphically displays the folder structure of a drive or path.
   echo/
   echo MYTREE [drive:][path] [/F]
   echo/
   echo    /F   Display the names of the files in each folder.
   goto :EOF
)

rem Get the parameters
set showFiles=
set targetDir=.
if "%~1" neq "" (
   if /I "%~1" equ "/F" (
      set showFiles=YES
   ) else (
      set "targetDir=%~1"
   )
   shift
)
if "%~1" neq "" (
   if /I "%~1" equ "/F" (
      set showFiles=YES
   ) else (
      set "targetDir=%~1"
   )
)

pushd .
cd /D "%targetDir%" || popd && goto :EOF

rem Single-line (Batch style) struct definition:
set FileNode= FileName=name, Prev="%NULL% not used in this example", Next=%NULL%

rem Multi-line (C style) struct definition (with the aid of some variables)
rem Do NOT leave any space between structName and %{%
%struct% DirNode%{%
    DirName    = name    %;%
    Prev       = "%NULL% not used in this example" %;%
    Next       = %NULL%  %;%
    NestedDir  = %NULL%  %;%
    NestedFile = %NULL%  %;%
%}%

rem Create the node of target directory
call :malloc DirNode targetDir=
set "%targetDir%->DirName=%CD%"

rem Create the whole data structure beneath it
SET LEVEL=0
set sp=0
call :ProcessThisDir %targetDir%
(ECHO/&ECHO/) >&2

REM DUMP HEAP MEMORY
REM IF %HEAPPOINTER% GTR 9 SET HEAPPOINTER=9
REM FOR /L %%I IN (1,1,%HEAPPOINTER%) DO SET %%I
REM PAUSE

rem Show the created data structure in TREE command format
echo Folder PATH listing
for /F "skip=1 delims=" %%a in ('vol') do echo %%a
call :show "!%targetDir%->DirName!"
set margin=
call :DisplayThisNode %targetDir%
if "!%targetDir%->NestedDir!" equ "%NULL%" (
   echo No subfolders exists
   echo/
)

popd


Antonio

Re: Arrays, structures and linked lists in Batch files

Posted: 23 Apr 2012 13:04
by aGerman
I like that idea. Unfortunately there is an issue: You can't allocate space in a batch file, hence you have to work with the environment which is (afaik) limited to 32 KB.

BTW It seems you wrote the code for XP. It doesn't run on my Win7 due to several changes they did. For example I wasn't able to find a command where to extract a TAB character (It's replaced with spaces on Win7). Also leading white spaces (like CR) are ignored for SET /P etc.

Regards
aGerman

Re: Arrays, structures and linked lists in Batch files

Posted: 23 Apr 2012 20:25
by Aacini
Total environment size in Windows XP is 64 MB (yes, MegaBytes!). See the note under "Setting environment variables" heading at this site. Also, in this dbenham's topic there are some interesting tests with very large environments.

As I said above, UPPERCASE commands are just used to trace the execution, so don't cares if you REMove them; you need to REM just 4 SET /P commands. The rest of the program use no Win XP tricks, so it should execute the same in any Win version.

Re: Arrays, structures and linked lists in Batch files

Posted: 24 Apr 2012 00:30
by jeb
It's a good starting point for batch "arrays" and "structures" and to see some good concepts :D

The main problem I see in the concept of structures is the setlocal-scope.
So you can't change structures directly or via "pointer" in a function with setlocal/endlocal block.

We need some good macro to safe the values when returning.

jeb