Creating a "dynamic" structure

[nickc86]

I am creating a program for a school assignment. We are programming in MASM. Our teacher alluded to the fact that you can create a structure that is "dynamic". I am wondering what he meant by this. We are creating a program to simulate a broadcast network. Part of the program will allow the user to create their own network. A network is defined by having at least two nodes. Each node can either be a destination and an origin.

So... Someone could enter the following -- Node A connects to Node B, Node B connects to Node A, Node C and Node D, Node C connects to Node B and Node D, Node D connects to Node B and Node C, which would translate to the following diagram:

A - B - C
      \   /
        D

So, to send a message from A to any other node, it must touch B.

Part of each structure is static, and part of it is dynamic.
Two examples using previous diagram:

Node structure static parts:
Name (a)
Number of connections (1)
Ptr to a in buffer
ptr to a out buffer
start of the queue of processed messages

dynamic parts:     --- for each connection
their name (b)
input buffer from (b)
output buffer to (b)

Node structure static parts:
Name (b)
Number of connections (2)
Ptr to a in buffer
ptr to a out buffer
start of the queue of processed messages

dynamic parts:     --- for each connection
connection 1
name (c)
input buffer from (c)
output buffer to (c)
connection 2
name (d)
input buffer from (d)
output buffer to (d)

He also hinted toward using "the heap", which I somewhat understand. (dynamically allocating memory)

This project isn't due for a month, but I am trying to get a head start on it, since some of it is extra credit.

His version of this project is 26 pages long printed. I am not directly asking for the correct answer here, I am asking to be pointed in the right direction for the following questions:
How should I think about approaching this task? (dynamically creating an unknown number of nodes and creating their unknown connections)

I can do things like parse "tokens" from the users input, move an inputted string from a register to an output buffer to send to a file, etc... so I do have a handle on some moderately advanced programming techniques in assembly.

Thanks ahead of time,
Nick

[hutch--]

Nick,

It sounds like you are being required to build a dynamic tree. Generally you look at the memory allocation strategies to see which is better suited for many small allocations and my best guess here is the HeapAlloc() family of API functions. You can do it the clumsy way by doing an allocation for each structure but it will be slow and you then have to de-allocate a large number of memory handles OR you can do it in a more complicated manner by allocating ahead and writing each node to the next section of pre-allocated memory.

The second option is more complicated to set up but its way faster and you de-allocate all of the memory in 1 function call.

Show us what you hae tried to do so far and one of our members can probably help you out. Note that we will not do your homework for you but if you make the effort, you will get assistance.

Now here is yet another suggestion for you, if the data structures are all the same size, you can create an array within a single block of memory (array of DWORD pointers) and have a block of memory where the array pointer to the correct intervals in the address space.

[jj2007]

You can do it the clumsy way by doing an allocation for each structure but it will be slow and you then have to de-allocate a large number of memory handles

That might be "slow" but for this assignment it will still be in the microseconds range. Maybe you could keep it simple and transparent for now, the optimisation can follow when the project is up and running.

Nick, try to be as clear as possible about the logic and expected results. Everything is possible in assembler, most of it is even easy, but you can quickly get stuck in unreadable code. Clear setup and LOTS of comments will be helpful, for you and for those who are ready to help you.

Here is a snippet to get started. Make it better and clearer by changing it and adding comments.

Code Select Expand

NODE STRUCT
  Number_of_connections dd ?
  ptr_to_a_in_buffer dd ?
  ptr_to_a_out_buffer dd ?
  start_queue_messages dd ?
  ; dynamic parts:     --- for each connection
  their_name_b dd ?
  input_buffer_from_b dd ?
  output_buffer_to_b dd ?
NODE ENDS

.data?
staticnodes NODE 20 dup(<?>)
.code
  mov eax, 8
  imul eax, eax, NODE
  mov staticnodes[eax].Number_of_connections, 123

Btw this is also valid assembler code, it dynamically allocates a RECT structure and assigns values, but it requires a library, and I doubt that your teacher would allow that:

Code Select Expand

            Dim rc() As RECT
            For_ n=0 To 3
                    m2m rc(n, left), n                        ; n is a global variable, so you need m2m
            Next

Welcome to the forum :icon14:

[nickc86]

So, the part of the program where the user defines the network is extra credit. Here is what I am thinking so far:

A network is defined by a group of more than one node. That said, each node can have at most n connections (in the worst possible scenario) defined by the following:
n = numOfNodes - 1, since each node can't connect to itself.

Here is the default network if a user doesn't enter one:

            B ---- C
          /   \    /   \
        A       X      D
          \   /    \   /
            E ----- F

Each node will have the following:   (may not be exactly correct masm syntax)

Code Select Expand


;static for each node --- this section equals 14 bytes
name byte "a"
numConnections byte 2
inPtr dword ?
outPtr dword ?
startOfQueuePtr dword ?
;dynamic need for each connection  --- for each connection, we need 12 bytes
;----start of 'b' connection
prtToB dword  ?                 ;b's location in memory
prtToXmitBuff dword ?        ;transmit buffer to b
prttoRcvBuff dword ?          ;receive buffer from b
;----end of 'b' connection
;----start of 'e' connection
prtToE dword ?                   ;e's location in memory
prtToXmitE dword ?            ;transmit buffer to e
prtToRcvE dword ?              ;receive buffer from e
;----end of 'e' connection

....and so on for each node and it's connections.


Now, this is great for a static network. I can just define each node in this way, but what if I have an undetermined number of nodes with undetermined connections?

Should I think about just allocating a linear number of bytes in memory?
each node will take up 14 static bytes and 12 bytes for each connection. I can create this space by doing the following, although I am not sure of the code:
sizeOfSpaceNeeded = numOfNodes*14 + totalNumberOfConnections*12

Do you follow what I am trying to do so far?

Also, thank you for the welcome. I am interested in embedded software development or something of that nature, so I will probably be looking at assembly language long term. I am trying to do the extra credit parts because it helps me learn more useful information. Thank you for the help so far.

[hutch--]

One thing to be aware about, when you make an array in memory, set the data size to an alignment of 4 in 32 bit. This means if you need 14 bytes, allocate 16 and write the 14 bytes to the start of the 16 byte offset. If you compact it to save a few bytes, you risk getting a performance hit due to mis-alignment.

[LordAdef]

hi there, only MASM, not masm32 I suppose?

[mineiro]

Now, this is great for a static network. I can just define each node in this way, but what if I have an undetermined number of nodes with undetermined connections?
Do you follow what I am trying to do so far?

You need create a counter variable and insert that inside some structure.
To me you're thinking right.
Something like this:
sizeOfSpaceNeeded = numOfNodes*(sizeof Nodes) + totalNumberOfConnections*(sizeof Connections)

[newrobert]

One thing to be aware about, when you make an array in memory, set the data size to an alignment of 4 in 32 bit. This means if you need 14 bytes, allocate 16 and write the 14 bytes to the start of the 16 byte offset. If you compact it to save a few bytes, you risk getting a performance hit due to mis-alignment.

maybe need use byte ptr or word ptr to point an register;

[HSE]

I think the idea is to make an exercise, but the solution is very simple using ObjAsm32. In the end what is under development here is OOP.
Regards. HSE.

[hutch--]

Robert,

> maybe need use byte ptr or word ptr to point an register;

Memory alignment has little to do with data alignment, you use BYTE PTR / WORD PTR / DWORD PTR to tell the assembler what a data size is when it cannot be determined by the registers used OR the memory operand not being defined as a LOCAL.

[fearless]

Here is a rough idea i set up. Its basically a pointer to an array of structures to store the connection data for each node (oNode)

Would require testing and adjusting code im sure to do more error checking and possibly handle other issues like nodes disconnecting and re-connecting which might require other functions to loop through an array of node_ex structure and resort/reindex or maybe just mark a flag in a structure to say connected/disconnected.

Not sure if it will help, i havnt compiled or tested it, just wrote down roughly what i think might work.

Code Select Expand

include windows.inc
include user32.inc
include kernel32.inc

includelib user32.lib
includelib kernel32.lib


.CONST

NODE_NAME_MAX_LENGTH     EQU 32
NODE_MAX_CONNECTIONS     EQU 200

NODE                     STRUCT
    dbNodeName           db NODE_NAME_MAX_LENGTH dup (0)
    dwNodeConnections    dd 0
    lpNodeBufferIn       dd 0
    lpNodeBufferOut      dd 0
    lpMessageQueue       dd 0
    lpNodeExArray        dd 0
NODE                     ENDS
 
 
NODE_EX                  STRUCT
    dwNodeExIndex        dd 0
    dbNodeExName         db NODE_NAME_MAX_LENGTH dup (0)
    lpNodeExBufferIn     dd 0
    lpNodeExBufferOut    dd 0
NODE_EX                  ENDS


.CODE

; returns handle to node object, or NULL if error
CreateNode PROC USES EBX EDX lpszNodeName:DWORD, lpBufferIn:DWORD, lpBufferOut:DWORD, lpMsgQueue:DWORD
    LOCAL oNode:DWORD
   
    .IF lpszNodeName == NULL
        mov eax, NULL
        ret
    .ENDIF
   
    mov eax, NULL
    mov oNode, eax
   
    Invoke HeapAlloc, SIZEOF NODE
    .IF eax == NULL
        ret
    .ENDIF
    mov oNode, eax
   
    mov ebx, oNode
    mov eax, lpszNodeName
    lea edx, [ebx].NODE.dbNodeName
    Invoke lstrcpyn, edx, eax, NODE_NAME_MAX_LENGTH

    mov eax, 0
    mov [ebx].NODE.dwNodeConnections, eax
   
    mov eax, lpBufferIn
    mov [ebx].NODE.lpNodeBufferIn, eax
   
    mov eax, lpBufferOut
    mov [ebx].NODE.lpNodeBufferOut, eax

    mov eax, lpMsgQueue
    mov [ebx].NODE.lpMessageQueue, eax
   
    mov eax, 0
    mov [ebx].NODE.lpNodeExArray, eax
   
    mov eax, oNode
    ret
CreateNode ENDP


; return true or false
; Can rename this function to AddConnectionToNode or Add_NodeEx_To_Node or AddNodeExToNode or whatever
AddConnectionToNode PROC USES EBX EDX oNode:DWORD, lpszNodeName:DWORD, lpBufferIn:DWORD, lpBufferOut:DWORD
    LOCAL pNodeExArray:DWORD
    LOCAL pNewNodeEx:DWORD
    LOCAL nTotalConnections:DWORD
    LOCAL dwSize:DWORD
   
    .IF oNode == NULL
        mov eax, FALSE
        ret
    .ENDIF   
   
    .IF lpszNodeName == NULL
        mov eax, FALSE
        ret
    .ENDIF   
   
    Invoke GetProcessHeap
    .IF eax == NULL
        mov eax, FALSE
        ret
    .ENDIF   
    mov hHeap, eax
   
    mov ebx, oNode
    mov eax, [ebx].NODE.dwNodeConnections
    mov nTotalConnections, eax
   
    .IF nTotalConnections == 0

        ; 1 connection
        inc nTotalConnections
        mov eax, nTotalConnections
       
        ; Alloc memory for NODE_EX structure
        mov edx, SIZEOF NODE_EX
        mul edx
        mov dwSize, eax
        Invoke HeapAlloc, hHeap, HEAP_ZERO_MEMORY, dwSize
        .IF eax == NULL
            mov eax, FALSE
            ret
        .ENDIF
        mov pNodeExArray, eax
        mov pNewNodeEx, eax ; used in next bit after end of this IF/ELSE/ENDIF
       
        ; Update NODE with new pointer to NODE_EX arrays
        mov eax, pNodeExArray
        mov ebx, oNode
        mov [ebx].NODE.lpNodeExArray, eax
       
        ; update NODE with new total no of connections now
        mov eax, nTotalConnections
        mov ebx, oNode
        mov [ebx].NODE.dwNodeConnections, eax
   
    .ELSE ; already some connections
   
        mov eax, nTotalConnections
        .IF eax > NODE_MAX_CONNECTIONS
            mov eax, FALSE
            ret
        .ENDIF
       
        inc nTotalConnections
        mov eax, nTotalConnections

        ; Alloc memory for NODE_EX structures
        mov edx, SIZEOF NODE_EX
        mul edx
        mov dwSize, eax
       
        ; Get current pointer to NODE_EX arrays
        mov ebx, oNode
        mov eax, [ebx].NODE.lpNodeExArray
        mov pNodeExArray, eax
       
        ; Have to reallocate memory for new heap
        Invoke HeapReAlloc, hHeap, 0, pNodeExArray, dwSize
        .IF eax == NULL
            Invoke HeapFree, hHeap, 0, pNodeExArray
            mov eax, FALSE
            ret
        .ENDIF
        mov pNodeExArray, eax
       
        ; save new NODE_EX array pointer back to oNode
        mov ebx, oNode
        mov [ebx].NODE.lpNodeExArray, eax
       
        ; Get pointer to new record in NODE_EX arrays
        mov eax, pNodeExArray
        add eax, dwSize
        sub eax, SIZEOF NODE_EX
        mov pNewNodeEx, eax
       
        ; update NODE with new total no of connections now
        mov eax, nTotalConnections
        mov ebx, oNode
        mov [ebx].NODE.dwNodeConnections, eax       
       
    .ENDIF
   
    ; Fill in new NODE_EX record
    mov ebx, pNodeExArray

    mov eax, nTotalConnections
    mov [ebx].NODE_EX.dwNodeExIndex, eax

    mov ebx, pNodeExArray
    mov eax, lpszNodeName
    lea edx, [ebx].NODE_EX.dbNodeExName
    Invoke lstrcpyn, edx, eax, NODE_NAME_MAX_LENGTH
   
    mov ebx, pNodeExArray
    mov eax, lpBufferIn
    mov [ebx].NODE_EX.lpNodeExBufferIn
   
    mov ebx, pNodeExArray
    mov eax, lpBufferOut
    mov [ebx].NODE_EX.lpNodeExBufferOut

    mov eax, TRUE
    ret
AddConnectionToNode ENDP

[nickc86]

Thank you much for all of the responses. I will review them this weekend and tell you were I'm at as far as code.

Also, our only "allowed" include is Irvine32.inc

I know I didn't mention that before.

[jj2007]

Also, our only "allowed" include is Irvine32.inc

Our condolences 8)

[fearless]

Code Select Expand

IRVINE_RESTRICTIONS EQU 1 ; comment out to disable restrictions

IFDEF IRVINE_RESTRICTIONS

    include irvine32.inc
    includelib irvine32.lib
   
ELSE

    include windows.inc
    include user32.inc
    include kernel32.inc
    include gdi32.inc
    include shell32.inc
    include comctl32.inc
    include comdlg32.inc
    include masm32.inc

    includelib user32.lib
    includelib kernel32.lib
    includelib gdi32.lib
    includelib shell32.lib
    includelib comctl32.lib
    includelib comdlg32.lib
    includelib masm32.lib
   
ENDIF

.DATA
dwNumber_of_legs        DD 2

.CODE

start:

IFDEF IRVINE_RESTRICTIONS
    dec dwNumber_of_legs
ENDIF

Invoke ArseKickingCompetition, dwNumber_of_legs

...

[newrobert]

Also, our only "allowed" include is Irvine32.inc

Our condolences 8)

where is  Irvine32.inc file, in my masm32 directory, not this file?