With this small wrapper library you can.
It wraps all the functions from the LinkedList and Sort PB-library,
so you can now use an allocated memory block, a defined varaible or
even an array of linked lists.
The PB user library is here: DLinkedList
Use 'Save as' to save the library to your hd.
Put it in your UserLibraries directory and restart the compiler, if you have the IDE already running.
The source code is here: DLinkedList_SrcPack
Please read the included Readme.txt file for compiling the library!
The new functions have the same name as the standard PB-functions, just with a 'D' in front:
AddElement() -> DAddElement()
SortList() -> DSortList()
for example
There are three macros to handle the dynamic linked list (dll):
1. DefineDList(dllType / dllStructure)
To define a new dll of type / structure
Use b, w, l, any build in type ... for a simple dll.
Use any already defined structure for a structured dll
2. DNewList(*dllVar, dllType / dllStructure)
Initialize a dll for usage, if the dll was already initialized,
all elements will be erased!
3. DElementAddr(*dllVar)
Get the address of the current element, or zero if the dll has no current
element.
Is the same as @list(), for build in linked lists.
There is one new function for dynamic linked list:
DDeleteList(*dllVar)
This will erase all elements from the list and also the linked list infoblock,
so after this the linked list will not take up any memory, except for the *dllVar.
If you had this allocated with AllocateMemory() and now frees the memory
for *dllVar, the list is completely gone.
Because the compiler don't know of this dynamic lists, it is your responsiblity to free the memory allocated by the list elements at the
end of a procedure, or before ReDim an array of dlls
For example:
Code: Select all
Structure MyStruc
l1.l
l2.l
s1.s
s2.s
EndStructure
DefineDList(MyStruc)
Dim myDLLArray.MyStruc_dlist(9)
For i = 0 To 9
DNewList(myDLLArray(i), MyStruc)
DAddElement(myDLLArray(i))
myDLLArray(i)\d\d\s1 = "String1"
myDLLArray(i)\d\d\s2 = "String2"
Next i
; Before ReDim:
For i = 5 To 9
; Completely remove the dll from memory
DDeleteList(myDLLArray(i))
Next i
; Now you can ReDim the array:
ReDim myDLLArray.MyStruc_dlist(4)
You maybe need a newer version of FAsm to get this compiled.
This two include files will be needed to compiler dlls:
1. 'dynamicLinkedList.pbi' :
Code: Select all
Structure LinkedListInfo
*pFirst ; Pointer to first element of list
*pLast ; Pointer to last element of list
size.l ; Size of list elements, includes 8 bytes for header
count.l ; Number of elements in list
index.l ; Index (zero based) of actual element, not always valide, see below
*pStringOffsets ; Pointer to a list of offsets for strings in a structure, see below
indexInvalide.l ; If none zero, index is not valide, for example after using ChangeCurrentElement()
; Using ListIndex() will validate it again.
type.l ; Element type number, see below
EndStructure
!struct LLINFO
! pFirst dd ?
! pLast dd ?
! size dd ?
! count dd ?
! index dd ?
! pStringOffsets dd ?
! indexValide dd ?
! type dd ?
!ends
; Element type numbers, thiese are the same as for type numbers of arrays
; Type number
;
; Byte 1
; Word 3
; Long 5
; Structure 7
; String 8
; Float 9
; Character 11
; Double 12
; Quad 13
; String offsets:
; If there are strings in a structure, or the linked list is of type string,
; this a pointer to a list of offset into the structure, where the string pointers are stored.
; If there are no strings, this pointer is zero
; The list has the form:
; dd offset1 Offset to first string
; dd offset2 Offset to second string, if applicable
; dd offsetN ... And so on for all string in structure
; dd -1 End of offset list, here it is -1, because a offset can
; be zero, for example if it is a string only linked list,
; or the first element of a structure is a string
; One example for the string offset list:
; Structure MyStruc
; b1.b ; Structure offset 0
; s1.s ; Structure offset 1
; s2.s ; Structure offset 5
; b2.b ; Structure offset 9
; s3.s ; Structure offset 10
; l.l ; Structure offset 14
; EndStructure
;
; String offset lists are only created, if you use a structure to create
; an array or linked list!
;
; This Structure would create a list like this in the *.asm file:
; s_mystruc: ; Name of Structure in lower case with s_ prefix
; dd 1
; dd 5
; dd 10
; dd -1
;
; This list is used to free the memory allocated for the strings as follows:
;
; PUSH address_of_string_offsets
; PUSH address_of_structure
; CALL _SYS_FreeStructureStrings@8
;
; After freeing the string(s), the string pointer(s) in the structure are
; still pointing to the old location(s), so be carefull,
; assigning a string to such an invalide pointer will crash the program!
; So better set the pointers to zero, if you plan on reusing the structure,
; this will allocate new valide memory locations to the string(s) at
; next assignment.
;
; To get rid of the a structure allocation itself:
;
; PUSH address_of_structure
; PUSH dword 0 ; Flags for HeapFree, see MSDK docs
; PUSH dowrd[PB_MemoryBase] ; Heap handle
; CALL _HeapFree@12
;
; The above is only valide, if this is not a structure in a linked list!
; For structures, or general all data in linked lists, you have to use:
;
; MOV eax,address_of_data
; SUB eax,8 ; Set address to header of linked list element
; PUSH eax
; PUSH dword 0 ; Flags for HeapFree, see MSDK docs
; PUSH dword[PB_MemoryBase] ; Heap handle
; CALL _HeapFree@12
;
; But using this, you are in trouble,
; because the element isn't unlinked properly from the list!
;
; To really work with your own linked list you need this structures:
Structure LinkedListHeader
*pNext.LinkedListHeader
*pPrev.LinkedListHeader
EndStructure
Structure LinkedListElement Extends LinkedListHeader
_data.b
EndStructure
!struct LLHEADER
! pNext dd ?
! pPrev dd ?
!ends
Structure LinkedListCtrl
*pInfo.LinkedListInfo ; Pointer to info about this list, see above
*pHeader.LinkedListHeader ; Pointer to actual element header, eight bytes after this is the element data
; This pointer is zero for an empty list, or if you use ResetList()
EndStructure
!struct LLCTRL
! pInfo dd ?
! pHeader dd ?
!ends
; Get address of current element, just for convenience
Macro DElementAddr(list)
(list\d\d)
EndMacro
Macro DefineDList(typeName)
Structure typeName#_element
*pNext.typeName#_element
*pPrev.typeName#_element
d.typeName
EndStructure
Structure typeName#_dlist
*pInfo.LinkedListInfo
*d.typeName#_element
EndStructure
EndMacro
; Structure name must be the same letter case as in the definition!
Macro DNewList(listPtr, typeName)
; We are messing with the stack here, this could be
; problematic when using the debugger in single step mode through this part!
CompilerIf Defined(_dnewlist_dummy_#typeName, #PB_LinkedList)
CompilerElse
; Create a dummy linked list, necessary to get the string offset table,
; if there are strings in this structure, only done once for each type
Global NewList _dnewlist_dummy_#typeName.typeName()
CompilerEndIf
DListEvaluateParameter(listPtr) ; Get value of pointer to list ctrl
; !PUSH edx ; Save register, necessary?
!PUSH eax ; Save list ctrl pointer
!MOV eax,[t__dnewlist_dummy_#typeName] ; Get pointer to dummy list info
!PUSH dword[eax + LLINFO.type] ; Number for type of list
!PUSH dword[eax + LLINFO.pStringOffsets] ; Get pointer to string offsets table, or zero
!MOV eax,[eax + LLINFO.size] ; Get size of one list element, includes 8 bytes for header
!SUB eax,sizeof.LLHEADER ; Correct size
!PUSH eax ; for new allocation
!MOV eax,[esp + 12] ; Get save list ctrl pointer
!CALL PB_NewList ; Actuall create the list
!ADD esp,4 ; Correct stack for list ctrl pointer
; !POP edx ; Retrieve saved register
EndMacro
Code: Select all
!
!; Macroinstructions for defining data structures
!
!macro struct name
! { fields@struct equ name
! match child parent, name \{ fields@struct equ child,fields@\#parent \}
! sub@struct equ
! struc db [val] \{ \common define field@struct .,db,<val>
! fields@struct equ fields@struct,field@struct \}
! struc dw [val] \{ \common define field@struct .,dw,<val>
! fields@struct equ fields@struct,field@struct \}
! struc du [val] \{ \common define field@struct .,du,<val>
! fields@struct equ fields@struct,field@struct \}
! struc dd [val] \{ \common define field@struct .,dd,<val>
! fields@struct equ fields@struct,field@struct \}
! struc dp [val] \{ \common define field@struct .,dp,<val>
! fields@struct equ fields@struct,field@struct \}
! struc dq [val] \{ \common define field@struct .,dq,<val>
! fields@struct equ fields@struct,field@struct \}
! struc dt [val] \{ \common define field@struct .,dt,<val>
! fields@struct equ fields@struct,field@struct \}
! struc rb count \{ define field@struct .,db,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! struc rw count \{ define field@struct .,dw,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! struc rd count \{ define field@struct .,dd,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! struc rp count \{ define field@struct .,dp,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! struc rq count \{ define field@struct .,dq,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! struc rt count \{ define field@struct .,dt,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro db [val] \{ \common \local anonymous
! define field@struct anonymous,db,<val>
! fields@struct equ fields@struct,field@struct \}
! macro dw [val] \{ \common \local anonymous
! define field@struct anonymous,dw,<val>
! fields@struct equ fields@struct,field@struct \}
! macro du [val] \{ \common \local anonymous
! define field@struct anonymous,du,<val>
! fields@struct equ fields@struct,field@struct \}
! macro dd [val] \{ \common \local anonymous
! define field@struct anonymous,dd,<val>
! fields@struct equ fields@struct,field@struct \}
! macro dp [val] \{ \common \local anonymous
! define field@struct anonymous,dp,<val>
! fields@struct equ fields@struct,field@struct \}
! macro dq [val] \{ \common \local anonymous
! define field@struct anonymous,dq,<val>
! fields@struct equ fields@struct,field@struct \}
! macro dt [val] \{ \common \local anonymous
! define field@struct anonymous,dt,<val>
! fields@struct equ fields@struct,field@struct \}
! macro rb count \{ \local anonymous
! define field@struct anonymous,db,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro rw count \{ \local anonymous
! define field@struct anonymous,dw,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro rd count \{ \local anonymous
! define field@struct anonymous,dd,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro rp count \{ \local anonymous
! define field@struct anonymous,dp,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro rq count \{ \local anonymous
! define field@struct anonymous,dq,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro rt count \{ \local anonymous
! define field@struct anonymous,dt,count dup (?)
! fields@struct equ fields@struct,field@struct \}
! macro union \{ fields@struct equ fields@struct,,union,<
! sub@struct equ union \}
! macro struct \{ fields@struct equ fields@struct,,substruct,<
! sub@struct equ substruct \}
! virtual at 0 }
!
!macro ends
! { match , sub@struct \{ restruc db,dw,du,dd,dp,dq,dt
! restruc rb,rw,rd,rp,rq,rt
! purge db,dw,du,dd,dp,dq,dt
! purge rb,rw,rd,rp,rq,rt
! purge union,struct
! match name=,fields,fields@struct \\{ fields@struct equ
! make@struct name,fields
! define fields@\\#name fields \\}
! end virtual \}
! match any, sub@struct \{ fields@struct equ fields@struct> \}
! restore sub@struct }
!
!macro make@struct name,[field,type,def]
! { common
! if $
! display 'Error: definition of ',`name,' contains illegal instructions.',0Dh,0Ah
! err
! end if
! local define
! define equ name
! forward
! local sub
! match , field \{ make@substruct type,name,sub def
! define equ define,.,sub, \}
! match any, field \{ define equ define,.#field,type,<def> \}
! common
! match fields, define \{ define@struct fields \} }
!
!macro define@struct name,[field,type,def]
! { common
! local list
! list equ
! forward
! if ~ field eq .
! name#field type def
! sizeof.#name#field = $ - name#field
! else
! label name#.#type
! rb sizeof.#type
! end if
! local value
! match any, list \{ list equ list, \}
! list equ list <value>
! common
! sizeof.#name = $
! restruc name
! match values, list \{
! struc name value \\{
! match any, fields@struct \\\{ fields@struct equ fields@struct,.,name,<values> \\\}
! match , fields@struct \\\{ label .
! forward
! match , value \\\\{ field type def \\\\}
! match any, value \\\\{ field type value
! if ~ field eq .
! rb sizeof.#name#field - ($-field)
! end if \\\\}
! common \\\} \\}
! macro name value \\{
! forward
! match , value \\\{ type def \\\}
! match any, value \\\{ \\\local ..field
! ..field: type value
! if ~ field eq .
! rb sizeof.#name#field - ($-..field)
! end if \\\}
! common \\} \} }
!macro enable@substruct
! { macro make@substruct substruct,parent,name,[field,type,def]
! \{ \common
! \local define
! define equ parent,name
! \forward
! \local sub
! match , field \\{ match any, type \\\{ enable@substruct
! make@substruct type,name,sub def
! purge make@substruct
! define equ define,.,sub, \\\} \\}
! match any, field \\{ define equ define,.\#field,type,<def> \\}
! \common
! match fields, define \\{ define@\#substruct fields \\} \} }
!
!enable@substruct
!
!macro define@union parent,name,[field,type,def]
! { common
! virtual at parent#.#name
! forward
! if ~ field eq .
! virtual at parent#.#name
! parent#field type def
! sizeof.#parent#field = $ - parent#field
! end virtual
! if sizeof.#parent#field > $ - parent#.#name
! rb sizeof.#parent#field - ($ - parent#.#name)
! end if
! else
! label name#.#type at parent#.#name
! if sizeof.#type > $ - parent#.#name
! rb sizeof.#type - ($ - parent#.#name)
! end if
! end if
! common
! sizeof.#name = $ - parent#.#name
! end virtual
! struc name [value] \{ \common
! label .\#name
! last@union equ
! forward
! match any, last@union \\{ virtual at .\#name
! field type def
! end virtual \\}
! match , last@union \\{ match , value \\\{ field type def \\\}
! match any, value \\\{ field type value \\\} \\}
! last@union equ field
! common rb sizeof.#name - ($ - .\#name) \} }
!
!macro define@substruct parent,name,[field,type,def]
! { common
! virtual at parent#.#name
! forward
! if ~ field eq .
! parent#field type def
! sizeof.#parent#field = $ - parent#field
! else
! label name#.#type
! rb sizeof.#type
! end if
! common
! sizeof.#name = $ - parent#.#name
! end virtual
! struc name value \{
! label .\#name
! forward
! match , value \\{ field type def \\}
! match any, value \\{ field type value
! if ~ field eq .
! rb sizeof.#parent#field - ($-field)
! end if \\}
! common \} }
!
Code: Select all
EnableExplicit
IncludePath #PBIncludePath
XIncludeFile "STRUCT.pbi"
XIncludeFile "dynamicLinkedList.pbi"
Structure MyStructure
l.l
s.s
EndStructure
; Define a dynamic list from a structure
DefineDList(MyStructure)
; Define a simple dynamic list of longs
DefineDList(l)
Define i.l, iEnd.l = 4, i2.l, i2End.l
; Create an array of dynamic linked list of type MyStructure
Dim dListArray.MyStructure_dlist(iEnd)
; Create a pointer to a simple dynamic list of longs
Define *dList.l_dlist
For i = 0 To iEnd
; Create a new list for every index
DNewList(dListArray(i), MyStructure)
i2End = Random(10)
For i2 = 1 To i2End
DAddElement(dListArray(i))
dListArray(i)\d\d\l = Random(10000)
dListArray(i)\d\d\s = "List " + Str(i) + ": string" + RSet(Str(DCountList(dListArray(i))), 3, "0")
Next i2
Next i
For i = 0 To iEnd
Debug ""
Debug "Elements in list " + Str(i) + ": " + Str(DCountList(dListArray(i)))
DResetList(dListArray(i))
While DNextElement(dListArray(i))
Debug dListArray(i)\d\d\s + " l = " + Str(dListArray(i)\d\d\l)
Wend
Next i
Debug ""
Debug "Sorting lists by l:"
For i = 0 To iEnd
Debug "List " + Str(i)
DSortStructuredList(dListArray(i), 0, OffsetOf(MyStructure\l), #PB_Sort_Long)
Next i
Debug ""
Debug "Showing sorted lists:"
For i = 0 To iEnd
Debug ""
Debug "Elements in list " + Str(i) + ": " + Str(DCountList(dListArray(i)))
DResetList(dListArray(i))
While DNextElement(dListArray(i))
Debug dListArray(i)\d\d\s + " l = " + Str(dListArray(i)\d\d\l)
Wend
Next i
Debug ""
Debug "Remove the lists completely from memory:"
For i = 0 To iEnd
; This will remove all list elements and the list info block
DDeleteList(dListArray(i))
Next i
Debug ""
Debug "Creating a dynamic list on the fly"
; Creating a dynamic list on the fly
; Allocating memory for the control block
*dList = AllocateMemory(SizeOf(LinkedListCtrl))
; Initialize the list
DNewList(*dList, l)
For i = 1 To 20
DAddElement(*dList)
*dList\d\d = Random(10000)
Next i
Debug "Showing list contents:"
DResetList(*dList)
While DNextElement(*dList)
Debug *dList\d\d
Wend
Debug "Sorting list:"
DSortList(*dList, 0)
Debug "Showing sorted list contents:"
DResetList(*dList)
While DNextElement(*dList)
Debug *dList\d\d
Wend
Debug "Removing list from memory:"
DDeleteList(*dList)
FreeMemory(*dList)
Debug "Done"
technicorn
