PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

PB_LinkedLists

https://www.purebasic.fr/german/viewtopic.php?t=1749

Seite 1 von 3

PB_LinkedLists

Verfasst: 23.01.2005 06:22
von Deeem2031
Da ich versucht habe eine SortierProc für LinkedLists zu basteln, habe ih mich notwendigerweise auch mit der internen Verwaltung der LinkedLists auseinandergesetzt. Da ich das relativ interessant finde und es auch nicht ganz einfach rauszufinden ist erklär ich euch das mal ein bisl ;)

Ich kann natürlich nicht dafür garantieren das der Code bei der nächsten PB-Version noch funzt, da Fred das ja nach belieben ändern kann, wie er die Linkedlists aufruft/speichert.

Code: Alles auswählen

;PB_LinkedLists
;by Deeém2031 (23.12.2005)
;for Purebasic 3.92

Structure PB_LinkedListData_Struc
  *FirstElement.PB_LinkedListElement ; FirstElement(LL()): = @LL()-8
  *LastElement.PB_LinkedListElement ; LastElement(LL()): = @LL()-8
  SizeofElement.l ; (Structure + *NextElement.l and *PrevElement.l (8 Byte))
  AmountofElements.l ; = CountList()
  NumberofCurrentElement.l ; = ListIndex()
  ;Maybe something is saved here...
EndStructure

Structure PB_LinkedListElement
  *NextElement.l
  *PrevElement.l
  ;[...] Content
EndStructure

Structure PB_LinkedList
  *PB_LinkedListData.PB_LinkedListData_Struc
  *CurrentElement.PB_LinkedListElement
EndStructure



NewList LL.l()

;To get the pointer to the PB_LinkedList-Struc you must use assembler:
Global *p.PB_LinkedList

!MOV Eax, dword t_LL ; "LL" is the name of the LinkedList
!MOV dword [p_p],Eax

Debug "Pointer to the PB_LinkedList-Struc: "+Str(*p)

;At the beginning *FirstElement, *LastElement, *CurrentElement, AmountofElements.l and NumberofCurrentElement.l are 0

Debug "*p\PB_LinkedListData\FirstElement: "+Str(*p\PB_LinkedListData\FirstElement)
Debug "*p\PB_LinkedListData\LastElement: "+Str(*p\PB_LinkedListData\LastElement)
Debug "*p\CurrentElement: "+Str(*p\CurrentElement)
Debug "*p\PB_LinkedListData\AmountofElement: "+Str(*p\PB_LinkedListData\AmountofElements)
Debug "*p\PB_LinkedListData\NumberofCurrentElement: "+Str(*p\PB_LinkedListData\NumberofCurrentElement)

Debug "---AddElement()---"
AddElement(LL())

;*FirstElement and *LastElement change if you create the first element
;*CurrentElement change, too.
;AmountofElements and NumberofCurrentElement increase by 1 ...

Debug "*p\PB_LinkedListData\FirstElement: "+Str(*p\PB_LinkedListData\FirstElement)
Debug "*p\PB_LinkedListData\LastElement: "+Str(*p\PB_LinkedListData\LastElement)
Debug "*p\CurrentElement: "+Str(*p\CurrentElement)
Debug "*p\PB_LinkedListData\AmountofElement: "+Str(*p\PB_LinkedListData\AmountofElements)
Debug "*p\PB_LinkedListData\NumberofCurrentElement: "+Str(*p\PB_LinkedListData\NumberofCurrentElement)

;@LL() always return the address to the PB_LinkedListElement + 8
;, because *NextElement.l And *PrevElement.l are saved in the structure too.
;To change the address to the next element you can use PokeL(@LL()-8,address)
;For the previous PokeL(@LL()-4,address)

Debug "Prev Element: "+Str(PeekL(@LL()-4))+" (0 because its the first Element)"
Debug "Next Element: "+Str(PeekL(@LL()-8))+" (0 because its the last Element)"

Debug "---AddElement()---"
AddElement(LL())
Debug "Prev Element: "+Str(PeekL(@LL()-4))

Debug "---PreviousElement()---"
PreviousElement(LL())
Debug "Next Element: "+Str(PeekL(@LL()-8))
Edit: Ein Kommentar war fehlerhaft.

Verfasst: 23.01.2005 08:09
von DarkDragon
:mrgreen: Endlich hats mal einer Ausführlich beschrieben, danke Deeem2031 :wink:

Verfasst: 23.01.2005 16:01
von PMV
cool ... :allright: deeem2031

hm, es heißt ja hier im forum immer wieder, das SelectElement() nicht so sonderlich komfortable ist, um es mal milde aus zu drücken :D ... aber wie wäre es, wenn das mal auch einer erklärt, also die Funktionsweise und dann noch, warum das nicht so gut ist und öhm ... wies besser gemacht werden sollte vielleicht auch noch :mrgreen: ...

^^Interezant und Wissenswert ist es auf jeden Fall <)

MFG PMV

Verfasst: 23.01.2005 16:18
von ParkL
Das liegt am Prinzip linearer Listen.

Hier wird wohl keine bestreiten, daß SelectElement komfortabel ist. Aber es ist leider nicht effizient.

Der Rechner weiß nie, wo sich das nächste Element im Speicher befinden wird, daher muß er im schlechtesten Fall CountList(Liste()) mal springen.

Beispiel:

Das aktuelle Element ist das erste in der Liste (oder sogar vor dem ersten). Wenn Du dann das vorletzte Element anspringen willst müsste der Rechner ja dann theoretisch einmal mit dem *next pointer durch die ganze Liste latschen O(n). Ein Array liegt im Gegensatz dazu als ein Block im Speicher. Wenn man also ein Array Element anspricht, kann PB einfach ausrechnen wo sich das im Speicher befindet (startoffset + index*elementbreite). Das ist in konstanter Zeit möglich O(1).

In der Praxis wird Fred allerdings in seiner LinkedList ein paar Zusatzvariablen eingebaut haben. Wahrscheinlich Pointer auf erstes Element, Pointer auf letztes Element, ListCount etc. So kann er z.B. beim SelectElement abschätzen, ob es sinnvoller ist, vom letzen Element durch die Liste nach vorne zu wandern oder vom ersten Element nach hinten.

Verfasst: 23.01.2005 16:37
von Deeem2031
ParkL hat geschrieben:In der Praxis wird Fred allerdings in seiner LinkedList ein paar Zusatzvariablen eingebaut haben. Wahrscheinlich Pointer auf erstes Element, Pointer auf letztes Element, ListCount etc. [...]
Damit ihr wisst wo diese Variablen stehen hab ich doch den Code geschrieben, die stehen nämlich in der Structure drin:

Code: Alles auswählen

Structure PB_LinkedListData_Struc 
  *FirstElement.PB_LinkedListElement ; FirstElement(LL()): = @LL()-8 
  *LastElement.PB_LinkedListElement ; LastElement(LL()): = @LL()-8 
  SizeofElement.l ; (Structure + *NextElement.l and *PrevElement.l (8 Byte)) 
  AmountofElements.l ; = CountList() 
  NumberofCurrentElement.l ; = ListIndex() 
  ;Maybe something is saved here... 
EndStructure
Wie die einzelnen Procs von PB für die LLs funktionieren könnt ich auch mal untersuchen. Von ResetList, FirstElement(), LastElement(), NextElement(),PreviousElement() und ChangeCurrentElement() weiß ich ja schon wie 'se funktionieren.

BTW. Die Beschreibung für SelectElement() ist irreführend, dort steht nämlich "SelectElement(LinkedList(), *Position)". Das würde aber heißen Position soll ein Pointer sein, so ist es aber nicht. In der Hilfe steht es richtig...

Verfasst: 23.01.2005 16:52
von PMV
Vielen dank euch zwei. <)
Also funktioniert es so, wie ich es mir grad gedacht hab ...

Das es nicht so komfortable ist, ist klar. Aber wie soll man es besser machen, wenn man nie weis, wann noch ein Element dazu kommt und wie viele es maximal sein sollen?

Sonnst könnte man ja auch Arrays benutzten, oder gibbet da doch möglichkeiten?

MFG PMV

Verfasst: 23.01.2005 17:09
von Deeem2031
Es gibt doch auch ChangeCurrentElement(), das läuft wesentlich schneller.

Hier erstmal ein paar Procs zum begucken ;)

Code: Alles auswählen

;Some Procedures to show how the PB-Procs works
Procedure LL_Reset(*LinkedList.PB_LinkedList)
  *LinkedList\CurrentElement = 0
EndProcedure

Procedure.l LL_NextElement(*LinkedList.PB_LinkedList)
  If *LinkedList\CurrentElement\NextElement
    *LinkedList\CurrentElement = *LinkedList\CurrentElement\NextElement
    ProcedureReturn *LinkedList\CurrentElement\NextElement
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_PreviousElement(*LinkedList.PB_LinkedList)
  If *LinkedList\CurrentElement\PrevElement
    *LinkedList\CurrentElement = *LinkedList\CurrentElement\PrevElement
    ProcedureReturn *LinkedList\CurrentElement\PrevElement
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_FirstElement(*LinkedList.PB_LinkedList)
  *LinkedList\CurrentElement = *LinkedList\PB_LinkedListData\FirstElement
  ProcedureReturn *LinkedList\PB_LinkedListData\FirstElement
EndProcedure

Procedure.l LL_LastElement(*LinkedList.PB_LinkedList)
  *LinkedList\CurrentElement = *LinkedList\PB_LinkedListData\LastElement
  ProcedureReturn *LinkedList\PB_LinkedListData\LastElement
EndProcedure

Procedure LL_ChangeCurrentElement(*LinkedList.PB_LinkedList,*Element.l)
  *LinkedList\CurrentElement = *Element
EndProcedure

Verfasst: 23.01.2005 18:39
von PMV
Ja sicha ... aber woher soll ma den den Pointer wissen? ... den Index weiss man beim Programmieren ... aber den Pointer? ...

Man könnte höchstens vor dem ablauf die einzellnen Indexe (oder was ist die mehrzahl?) in die entsprechenden Pointer verwandeln und dann das so machen ... aber ist das auch nicht immer möglich, und manchmal auch etwas sehr aufwendig :D .

^^Aber klar, um das ganze zu Optimieren sollte man so oft wie möglich ChangeCurrentElement() benutzten statt SelectElement(). Ich dacht immer SelectElement() macht wer weiss was -_- ... so wie das hier immer beschimpft wurde :lol: ... aber jetzt weiss ich endlich genau, was ihr immer meintet. <)

MFG PMV

Verfasst: 23.01.2005 19:07
von Deeem2031
Mir ist vorhin aufgefallen das meine Procs die "NumberofCurrentElement" garnicht verändern. Also versuchte ich rauszufinden wie PB das macht und bin auf 'nen Bug gestoßen. Ich glaube dieser wurde zwar schonmal erwähnt, aber er besteht anscheinend immernoch und zwar mag ListIndex() unter Bestimmten umständen nicht zweimal aufgerufen werden:

Code: Alles auswählen

NewList LL.l()

AddElement(LL())
AddElement(LL())
tmp = @LL()

PreviousElement(LL())
ChangeCurrentElement(LL(),tmp)
Debug ListIndex(LL())
Debug ListIndex(LL())
Wär nett wenn das jemand an Fred meldet, ich werd mir auch mal den ASM-Code angucken um zu schauen was denn da nich richtig läuft. Vielleicht bekomm ich ja eine entbuggte Proc hin ;)

EDIT: Hat sich erledigt, im engl. Forum wurde das ganze schon durchgenommen. Die entbugte Lib gibts unter http://purebasic.com/beta

Verfasst: 23.01.2005 22:54
von Deeem2031
So, fertig. Sämmtliche Variablen die für LLs wichtig sind wurden enttarnt und der Code wurde sogar von AlphaSND höchst persönlich für richtig anerkannt :)

Code: Alles auswählen

;PB_LinkedLists
;by Deeém2031 (23.01.2005)
;for Purebasic 3.92

Structure PB_LinkedListData_Struc
  *FirstElement.PB_LinkedListElement_Struc ; FirstElement(LL()): = @LL()-8
  *LastElement.PB_LinkedListElement_Struc ; LastElement(LL()): = @LL()-8
  SizeofElement.l ; (Structure + *NextElement.l and *PrevElement.l (8 Byte))
  AmountofElements.l ; = CountList()
  NumberofCurrentElement.l ; = ListIndex() + 1 (with the normal PB 3.92 LL-Library NumberofCurrentElement.l is equal to the result of ListIndex(), with the new one from purebasic.com/beta its bigger by 1)
  StructureMap.l ; "the structureMap is the address of the structure associated with the list, so if there is string in it they can be freed easily" by AlphaSND (explained at the end of the file)
  IsSetNumberofCurrentElement.l ; Is NumberofCurrentElement saving the correct value? (0=yes,other=no)
EndStructure

Structure PB_LinkedListElement_Struc
  *NextElement.l
  *PrevElement.l
  ;[...] Content
EndStructure

Structure PB_LinkedList_Struc
  *PB_LinkedListData.PB_LinkedListData_Struc
  *CurrentElement.PB_LinkedListElement_Struc
EndStructure



NewList LL.l()

;To get the Pointer to the PB_LinkedList-Struc you must use Assembler:
Global *p.PB_LinkedList_Struc

!MOV Eax, dword t_LL ; "LL" is the name of the LinkedList
!MOV dword [p_p],Eax

Debug "Pointer to the PB_LinkedList-Struc: "+Str(*p)

;At the beginning *FirstElement, *LastElement, *CurrentElement, AmountofElements.l and NumberofCurrentElement.l are 0

Debug "*p\PB_LinkedListData\FirstElement: "+Str(*p\PB_LinkedListData\FirstElement)
Debug "*p\PB_LinkedListData\LastElement: "+Str(*p\PB_LinkedListData\LastElement)
Debug "*p\CurrentElement: "+Str(*p\CurrentElement)
Debug "*p\PB_LinkedListData\AmountofElement: "+Str(*p\PB_LinkedListData\AmountofElements)
Debug "*p\PB_LinkedListData\NumberofCurrentElement: "+Str(*p\PB_LinkedListData\NumberofCurrentElement)

Debug ""
Debug "---AddElement()---"
Debug ""
AddElement(LL())

;*FirstElement and *LastElement change if you create the first Element
;*CurrentElement change, too.
;AmountofElements and NumberofCurrentElement increase by 1 ...

Debug "*p\PB_LinkedListData\FirstElement: "+Str(*p\PB_LinkedListData\FirstElement)
Debug "*p\PB_LinkedListData\LastElement: "+Str(*p\PB_LinkedListData\LastElement)
Debug "*p\CurrentElement: "+Str(*p\CurrentElement)
Debug "*p\PB_LinkedListData\AmountofElement: "+Str(*p\PB_LinkedListData\AmountofElements)
Debug "*p\PB_LinkedListData\NumberofCurrentElement: "+Str(*p\PB_LinkedListData\NumberofCurrentElement)

;@LL() always return the address to the PB_LinkedListData_Struc + 8
;, because *NextElement.l And *PrevElement.l are saved in the Structure too.
;To change the address To the Next Element you can use PokeL(@LL()-8,address)
;For the previous PokeL(@LL()-4,address)

Debug "Prev Element: "+Str(PeekL(@LL()-4))+" (0 because its the first Element)"
Debug "Next Element: "+Str(PeekL(@LL()-8))+" (0 because its the last Element)"

Debug ""
Debug "---AddElement()---"
Debug ""
AddElement(LL())
Debug "Prev Element: "+Str(PeekL(@LL()-4))
Sec_ElementP = @LL()

Debug ""
Debug "---PreviousElement()---"
Debug ""
PreviousElement(LL())
Debug "Next Element: "+Str(PeekL(@LL()-8))

;Some Procedures to show how the PB-Procs works
Procedure LL_Reset(*LinkedList.PB_LinkedList_Struc)
  *LinkedList\CurrentElement = 0
EndProcedure

Procedure.l LL_NextElement(*LinkedList.PB_LinkedList_Struc)
  If *LinkedList\CurrentElement\NextElement
    *LinkedList\CurrentElement = *LinkedList\CurrentElement\NextElement
    ProcedureReturn *LinkedList\CurrentElement\NextElement
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_PreviousElement(*LinkedList.PB_LinkedList_Struc)
  If *LinkedList\CurrentElement\PrevElement
    *LinkedList\CurrentElement = *LinkedList\CurrentElement\PrevElement
    ProcedureReturn *LinkedList\CurrentElement\PrevElement
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_FirstElement(*LinkedList.PB_LinkedList_Struc)
  *LinkedList\CurrentElement = *LinkedList\PB_LinkedListData\FirstElement
  ProcedureReturn *LinkedList\PB_LinkedListData\FirstElement
EndProcedure

Procedure.l LL_LastElement(*LinkedList.PB_LinkedList_Struc)
  *LinkedList\CurrentElement = *LinkedList\PB_LinkedListData\LastElement
  ProcedureReturn *LinkedList\PB_LinkedListData\LastElement
EndProcedure

Procedure LL_ChangeCurrentElement(*LinkedList.PB_LinkedList_Struc,*Element.l)
  *LinkedList\CurrentElement = *Element-8
EndProcedure

Debug "ListIndex: "+Str(ListIndex(LL()))
Debug ""
Debug "---ChangeCurrentElement()--- to second element"
ChangeCurrentElement(LL(),Sec_ElementP)

If *p\PB_LinkedListData\IsSetNumberofCurrentElement
  Debug "This Value isn't correct:"
Else
  Debug "This Value is correct:"
EndIf
Debug "ListIndex: "+Str(*p\PB_LinkedListData\NumberofCurrentElement-1)
Debug ""
Debug "ListIndex (PB): "+Str(ListIndex(LL())) ;
If *p\PB_LinkedListData\IsSetNumberofCurrentElement
  Debug "This Value isn't correct:"
Else
  Debug "This Value is correct:"
EndIf
Debug "ListIndex: "+Str(*p\PB_LinkedListData\NumberofCurrentElement-1)
Debug ""


;So now we play something with Structures in a LinkedList

Structure teststruc
  l.l
  s.s
  w.w
  b.b
  f.f
  s2.s
  s3.s
EndStructure

;StructureMap of teststruc:
;s_teststruc:
;dd     4  ;String are at Positions 4,15 and 19
;dd     15
;dd     19
;dd     -1 ;-1 ist the endcharacter of a structurefield

NewList LL2.teststruc()

;To get the Pointer to the PB_LinkedList-Struc you must use Assembler:
Global *p.PB_LinkedList_Struc

!MOV Eax, dword t_LL2 ; "LL2" is the name of the LinkedList
!MOV dword [p_p],Eax

Debug "Size of one LL2-element: "+Str(*p\PB_LinkedListData\SizeofElement)+"bytes"
Debug ""

If *p\PB_LinkedListData\StructureMap ;The structuremap is to speed up PB handling with strings
  Debug "The linkedliststructure contain a string at"
  While PeekL(*p\PB_LinkedListData\StructureMap+i) <> -1
    Debug "Position: "+Str(PeekL(*p\PB_LinkedListData\StructureMap+i))
    i+4
  Wend
EndIf
Alle Zeiten sind UTC+02:00
Seite 1 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de