Struktur von PBs LinkedLists. Richtig so?

[Regenduft]

Nach meinem "2 LinkedLists vertauschen" Thread habe ich mal versucht herauszubekommen, wie PureBasics Dynamic Linked Lists eigentlich intern aufgebaut sind. Dabei ist folgende komplexe Struktur entstanden:

Code: Alles auswählen

Structure Typ_ListDatum
  StructureUnion
    i.i : q.q : l.l : w.w : b.b
    u.u : a.a
    s.String
  EndStructureUnion
EndStructure

Structure Typ_ListElement
  *NextElement.Typ_ListElement
  *PrevElement.Typ_ListElement
  Datum.Typ_ListDatum
EndStructure

Structure Typ_PtrToListElement
  *CurrentElement.Typ_ListElement
EndStructure

Structure Typ_ListInfo
  *FirstElement.Typ_ListElement
  *LastElement.Typ_ListElement
  *CurrentElement.Typ_ListElement
  *CurrentElementInHeader.Typ_PtrToListElement
  ListSize.i
  ListIndex.i
EndStructure

Structure Typ_ListHeader
  *ListInfo.Typ_ListInfo
  *CurrentElement.Typ_ListElement
EndStructure

Was meint Ihr hier denn so? Ist das alles richtig so? Habe ich irgendetwas vergessen?

Zum ermitteln des Zeigers zum "ListHeader" und/oder zur "ListInfo" habe ich mir übrigens folgende Macros gestrickt: (EDIT: Fehler vom Copy&Paste korrigiert)

Code: Alles auswählen

; Initialisierungen

EnableExplicit
EnableASM
#Language = 'de'

CompilerIf #PB_Integer = #PB_Quad
  ! xax equ rax
  ! iword equ qword
CompilerElse
  ! xax equ eax
  ! iword equ dword
CompilerEndIf


; Hilfs-Macros, welche ich generell gerne verwende.

CompilerSelect #Language
CompilerCase 'en'
  Macro Lang(en,de)
    en
  EndMacro
CompilerCase 'de'
  Macro Lang(en,de)
    de
  EndMacro
CompilerEndSelect
Macro AsStr(Ausdruck)
  AsStr_DoubleQuote#Ausdruck#AsStr_DoubleQuote
EndMacro
Macro AsStr_DoubleQuote
  "
EndMacro


; Die eigentlichen Macros zum ermitteln der Zeiger

Macro PointerToListHeader(IN_ListName, OUT_Variable, GlobalList=#True)
  __PointerToXXX_ParameterCheck(IN_ListName, OUT_Variable)
  CompilerIf GlobalList
    LEA xax, [t_#IN_ListName]
  CompilerElse
    LEA xax, [p.t_#IN_ListName]
  CompilerEndIf
  MOV OUT_Variable, xax
EndMacro

Macro PointerToListInfo(IN_ListName, OUT_Variable, GlobalList=#True)
  __PointerToXXX_ParameterCheck(IN_ListName, OUT_Variable)
  CompilerIf GlobalList
    MOV xax, [t_#IN_ListName]
  CompilerElse
    MOV xax, [p.t_#IN_ListName]
  CompilerEndIf
  MOV OUT_Variable, xax
EndMacro

Macro __PointerToXXX_ParameterCheck(IN_ListName, OUT_Variable)
  CompilerIf Defined(IN_ListName, #PB_LinkedList) = 0
    CompilerError Lang("List has to be defined in advance","Liste muss zuvor definiert worden sein")+": "+AsStr(IN_ListName)+"()"
  CompilerEndIf
  CompilerIf Defined(OUT_Variable, #PB_Variable) = 0
    CompilerError Lang("Variable has to be defined in advance","Variable muss zuvor definiert worden sein")+": "+AsStr(OUT_Variable)
  CompilerEndIf
  CompilerIf Defined(t_#IN_ListName, #PB_Variable)
    CompilerError Lang("Collision between ASM-List name and variable name","Kollision zwischen ASM-Listenname und Variablenname")+": "+AsStr(t_#IN_ListName)
  CompilerEndIf
  CompilerIf SizeOf(OUT_Variable) < SizeOf(Integer)
    CompilerError "SizeOf("+AsStr(OUT_Variable)+") "+Lang("has To be equal or greater than SizeOf(Integer)","muss größer gleich SizeOf(Integer) sein")
  CompilerEndIf
EndMacro

Über Meinungen und Anregungen zu meinen Macros würde ich mich natürlich auch freuen!

EDIT 2: Eine kleine Demo is evtl. nicht schlecht. Die obigen 2 Codes habe ich als "LinkedListStructure.pb" und "LinkedListMacros.pb" per IncludeFile eingebunden.

Code: Alles auswählen

IncludeFile "LinkedListStructure.pb"
IncludeFile "LinkedListMacros.pb"

NewList bla.s()
Define *ListHeader.Typ_ListHeader
Define *ListInfo.Typ_ListInfo

AddElement(bla()) : bla() = "das"
AddElement(bla()) : bla() = "is"
AddElement(bla()) : bla() = "ne"
AddElement(bla()) : bla() = "Demo"

Debug "=== via PointerToListHeader ==="
PointerToListHeader(bla, *ListHeader)
Debug *ListHeader\ListInfo\FirstElement\Datum\s\s
Debug *ListHeader\ListInfo\FirstElement\NextElement\Datum\s\s
Debug *ListHeader\ListInfo\FirstElement\NextElement\NextElement\Datum\s\s
Debug *ListHeader\ListInfo\FirstElement\NextElement\NextElement\NextElement\Datum\s\s
Debug ""

Debug "=== via PointerToListHeader ==="
PointerToListInfo(bla, *ListInfo)
Debug *ListInfo\CurrentElement\PrevElement\Datum\s\s
Debug *ListInfo\CurrentElement\Datum\s\s
Debug *ListInfo\FirstElement\NextElement\Datum\s\s
Debug *ListInfo\FirstElement\Datum\s\s
Debug ""

[STARGÅTE]

Läuft nicht unter x86, weil bei CompilerIf #PB_Integer = #PB_Quad in beiden Möglichkeiten der selber x64-Code steht.

Auch solltest du du sehr vorsichtig mit sowas umgehen. Lesen von Vorgänger und Nachfolger eines Elements geht ja noch (das mach in hin und wieder auch mal, weill ich nicht NextElement() nutzen will, damit das aktuelle Element erhalten bleibt). Allerdings kann das Verändern der Internen sachen u.U. schwerer Fehler verursachen, vorallem wenn es ein Versionsupdate gibt.

Ich glaube auch, dass sich die ListInfo etwas abändert, wenn die Elemente der Liste eine komplexe Struktur haben, mit internen Listen, Maps usw. dann wird irgendwo noch ein Pointer hinterlegt, der den Strukturaufbau enthält.

[Regenduft]

Auch solltest du du sehr vorsichtig mit sowas umgehen. Lesen von Vorgänger und Nachfolger eines Elements geht ja noch (das mach in hin und wieder auch mal, weill ich nicht NextElement() nutzen will, damit das aktuelle Element erhalten bleibt). Allerdings kann das Verändern der Internen sachen u.U. schwerer Fehler verursachen, vorallem wenn es ein Versionsupdate gibt.

Gebe ich Dir voll und ganz recht! Meinen Code sollte man auf gar keinen Fall in irgendeinem Projekt verwenden oder wenn, dann extrem vorsichtig! Es ging mir mehr darum andere an meinem erarbeiteten Wissen teilhabenzulassen, wie denn PureBasics LinkedLists aufgebaut sind, bzw. zu prüfen, ob ich mir falsches oder lückenhaftes Wissen erarbeitet habe. Auch das mit dem "NextElement" per Zeiger ist mit Vorsicht zu genießen, da ja der Zeiger zum nächten Element im Falle des Letzten Elements #Null ist, was bei einem Zugriff zu einem ungültigen Speicherzugriff führen würde.

Ich glaube auch, dass sich die ListInfo etwas abändert, wenn die Elemente der Liste eine komplexe Struktur haben, mit internen Listen, Maps usw. dann wird irgendwo noch ein Pointer hinterlegt, der den Strukturaufbau enthält.

Danke für die Info! Ich bin einfach mal davon ausgegangen, dass (im Falle einer internen Liste) einfach ein Zeiger auf den Header der internen Liste gesetzt wird. Werde ich gleich mal versuchen herrauszufinden wie PureBasic das macht!

Läuft nicht unter x86, weil bei CompilerIf #PB_Integer = #PB_Quad in beiden Möglichkeiten der selber x64-Code steht.

Doch doch, das läuft. Da steht nicht derselbe x64-Code...

Code: Alles auswählen

CompilerIf #PB_Integer = #PB_Quad
  ! xax equ rax
  ! iword equ qword
CompilerElse
  ! xax equ eax
  ! iword equ dword
CompilerEndIf

Das sind FASM-Direktiven. Im x64-Fall wird "xax" im Folgecode immer mit "rax" erstetzt, im x86-Fall mit "eax". Entsprechendes gilt für "iword" mit "qword" (x64) bzw. "dword" (x86). Zweiteres hätte ich mir allerdings sparen können, da in meinem Assemblercode keine Mehrdeutigkeiten vorkommen, d.h. FASM braucht keine Typeninformationen. Oder sehe ich da etwas falsch? In Assembler bin ich nicht wirklich fit!

[STARGÅTE]

Wenn ich dein Code ausführe, bekomme ich ein:
Zeile 120: 'xax' ist kein gültiger Operator.

Habe gerade etwas näher angeguckt und gesehen, dass EnableASM fehlt.
Zumindest verwendest du ASM ohne das !, und nicht jeder hat EnableASM als standard aktiviert.

Wegen der Struktur:
Definiert man in PB eine Structure zB:

Code: Alles auswählen

Structure MyStruc
  Long.l
  StaticString.s{3}
  Double.d
  List Liste.i()
  Word.w
  String.s
EndStructure

dann speichert PB intern folgendes Muster ab: Data[15], List, Data[2], String
was nix anderes bedeutet als, dass bei CopyStructure, ClearStructure usw. die ersten 15Bytes Daten sind, danach eine Liste kommt, dann wieder 2 Bytes und dann ein String, sodass alles Richtig Kopiert wird.

Bei einem Array, wird die Addresse, wo das gespeichert wird (wenn es nötig ist) zB bei Offset: -16 (32Bit) gespeichert:

Code: Alles auswählen

Structure MyStruc1
	Long.l
	List Liste.i()
EndStructure

Structure MyStruc2
	Long.l
	Float.f
	String.s{6}
EndStructure

Dim Test1.MyStruc1(4)
Dim Test2.MyStruc2(4)

Debug PeekI(@Test1()-4*SizeOf(Integer))
Debug PeekI(@Test2()-4*SizeOf(Integer))

MyStruc2 hat nur Daten, also keine "komplizierte" Struktur, MyStruc1 hat dageben eine interne Liste.

Wie genau diese Strukturdaten auszulesen sind, hatte ich auch mal ausgearbeitet, aber er wurde dann irgendwann ungültig, vllt erneuer ich ihn mal.

[Regenduft]

dass EnableASM fehlt.
Zumindest verwendest du ASM ohne das !, und nicht jeder hat EnableASM als standard aktiviert.

Danke, hatte ich vergessen bzw. nicht berücksichtigt! Mit einem "!" ist leider nicht möglich, da ich die Macro-Parameter im ASM-Code verwende. Z.B. "LEA xax, [t_#IN_ListName]", wobei "IN_ListName" als Parameter übergeben wurde. Das "!" führt ja dazu, dass die Zeile vom PB-Compiler einfach direkt als 1zu1-Assemlerzeile weitergereicht wird. Macros (inkl. Parameter) und Compilerfunktionen werden also nicht aufgelöst.

dann speichert PB intern folgendes Muster ab: Data[15], List, Data[2], String
was nix anderes bedeutet als, dass bei CopyStructure, ClearStructure usw. die ersten 15Bytes Daten sind, danach eine Liste kommt, dann wieder 2 Bytes und dann ein String, sodass alles Richtig Kopiert wird.

Bei einem Array, wird die Addresse, wo das gespeichert wird (wenn es nötig ist) zB bei Offset: -16 (32Bit) gespeichert.

Hui, jetzt wird's kompliziert (zumindest für mich ). Wenn ich das richtig verstehe kann man also alle Strukturen (also sozusagen deren Definitionen) tatsächlich irgendwo im Kompilat finden...?! Ist ja höchst interessant! Dann könnte man ja theoretisch Strukturen zur Laufzeit verändern! (Wobei mir da kein praktischer Nutzen einfiele - außer man will fleißig das Programm abschießen...)
Werden diese Daten "nur" für CopyStructure, ClearStructure usw. gespeichert, oder gibt's da noch andere (interne) Verwendungszwecke dafür?

Also ich habe jetzt mal ausgetestet wie eine Liste innerhalb einer Struktur gespeichert wird und - siehe da - es wird einfach der List-Header (d.h. zwei Zeiger) reingespeichert (EDIT -> Quelltext überarbeitet):

Code: Alles auswählen

EnableExplicit

Structure MyStruc1
  Long.l ; <- als "absichtlich potentielle Fehlerquelle" dringelassen
  List Liste.s()
EndStructure

;{ LinkedList-Strukturen, einfach zuklappen ;-)
Structure Typ_ListDatum
  StructureUnion
    i.i : q.q : l.l : w.w : b.b
    u.u : a.a
    s.String
  EndStructureUnion
EndStructure
Structure Typ_ListElement
  *NextElement.Typ_ListElement
  *PrevElement.Typ_ListElement
  Datum.Typ_ListDatum
EndStructure
Structure Typ_PtrToListElement
  *CurrentElement.Typ_ListElement
EndStructure
Structure Typ_ListInfo
  *FirstElement.Typ_ListElement
  *LastElement.Typ_ListElement
  *CurrentElement.Typ_ListElement
  *CurrentElementInHeader.Typ_PtrToListElement
  ListSize.i
  ListIndex.i
EndStructure
Structure Typ_ListHeader
  *ListInfo.Typ_ListInfo
  *CurrentElement.Typ_ListElement
EndStructure
;}

Dim Test1.MyStruc1(4)
Define *ListHeader.Typ_ListHeader

AddElement(Test1(0)\Liste()): Test1(0)\Liste() = "Test1(0)\Liste(); Element 0"
AddElement(Test1(0)\Liste()): Test1(0)\Liste() = "Test1(0)\Liste(); Element 1"
AddElement(Test1(1)\Liste()): Test1(1)\Liste() = "Test1(1)\Liste(); Element 0"
AddElement(Test1(1)\Liste()): Test1(1)\Liste() = "Test1(1)\Liste(); Element 1"

Debug "=== Test1(0)\Liste ==="
*ListHeader = @Test1(0) + OffsetOf(MyStruc1\Liste)
Debug *ListHeader\ListInfo\FirstElement\Datum\s\s
Debug *ListHeader\ListInfo\LastElement\Datum\s\s
Debug ""
Debug "=== Test1(1)\Liste ==="
*ListHeader = @Test1(1) + OffsetOf(MyStruc1\Liste)
Debug *ListHeader\ListInfo\FirstElement\Datum\s\s
Debug *ListHeader\ListInfo\LastElement\Datum\s\s
Debug ""
Debug "=== SizeOf(MyStruc1) ==="
Debug SizeOf(MyStruc1)
Debug "= SizeOf(Long) + SizeOf(Integer) + SizeOf(Integer) ="
Debug "= SizeOf(Long) + SizeOf(Typ_ListHeader)"