Selbstprogrammierte LinkedList

[NicTheQuick]

Etwas gewöhnungsbedürftig, aber hauptsächlich für diejenigen Leute nützlich, die gerne ihre LinkedLists per Parameter bspw. an einer DLL weitergeben wollen und sie dort noch weiter bearbeiten möchten.
Ein kleines Beispiel habe ich hinzugefügt.

///Edit 1:

BugFix: [c]LL_Delete()[/c] stellte den Pointer für das letzte Element nicht um, wenn dieses gelöscht wurde.

///Edit 2:
BugFix: [c]LL_Add()[/c] und [c]LL_Insert()[/c] korrigiert. Da waren noch einige Ungereimheiten drin.
Added: [c]LL_Change()[/c] entspricht [c]ChangeCurrentElement()[/c] aus PureBasic. Bei Angabe des Pointers eines Elements wird dieser das aktuelle Element in seiner Liste. Die Angabe des Pointers zur Liste selbst ist nicht nötig.
Added: Unter Angabe zweier Elemente vertauscht [c]LL_Swap()[/c] diese beiden. Derzeit werden allerdings nicht die Zeiger verbogen, sondern einfach der Inhalt mit [c]CopyMemory()[/c] getauscht.

Code: Alles auswählen

;{ LinkedList by NicTheQuick

Structure LL_Element
  *pNext.LL_Element
  *pPrev.LL_Element
  *pParent.LL_Main
EndStructure
Structure LL_Main
  *pFirst.LL_Element
  *pLast.LL_Element
  *pAkt.LL_Element
  Struc.s
  StrucLength.l
  StrucSize.l
  *StrucOffsets
  Count.l
EndStructure
Structure LL_AllTypes
  StructureUnion
    b.b
    w.w
    l.l
    f.f
    s.s
  EndStructureUnion
EndStructure

Procedure.l LL_New(Struc.s)
  Protected *LL.LL_Main, LengthStruc.l, *pStruc.BYTE, Ok.l, *pStrucOffsets.LONG
  
  If Struc = "" : ProcedureReturn #False : EndIf
  
  *LL = AllocateMemory(SizeOf(LL_Main))
  If *LL
    *LL\pFirst = 0
    *LL\pLast = 0
    *LL\pAkt = 0
    *LL\Count = 0
    
    *pStruc = @Struc  ;Überprüfen, ob nur b, w, l, f und s vorhanden sind. Notfalls den Rest rausschmeißen
    *LL\Struc = ""
    While *pStruc\b
      Ok = #True
      Select *pStruc\b & $FF
        Case 'b' : Case 'w' : Case 'l' : Case 'f' : Case 's'
        Default : Ok = #False
      EndSelect
      If Ok
        *LL\Struc = *LL\Struc + Chr(*pStruc\b & $FF)
      EndIf
      *pStruc + 1
    Wend
    
    *LL\StrucLength = Len(*LL\Struc)
    *LL\StrucOffsets = AllocateMemory(*LL\StrucLength * 4)
    
    *LL\StrucSize = 0
    *pStrucOffsets = *LL\StrucOffsets
    *pStruc = @*LL\Struc
    While *pStruc\b
      *pStrucOffsets\l = *LL\StrucSize
      *pStrucOffsets + 4
      Select *pStruc\b & $FF
        Case 'b' : *LL\StrucSize + 1
        Case 'w' : *LL\StrucSize + 2
        Case 'l' : *LL\StrucSize + 4
        Case 'f' : *LL\StrucSize + 4
        Case 's' : *LL\StrucSize + 4
      EndSelect
      *pStruc + 1
    Wend
  EndIf
  ProcedureReturn *LL
EndProcedure

Procedure.l LL_Add(*LL.LL_Main)
  Protected *LL_E.LL_Element
  If *LL
    *LL_E = AllocateMemory(SizeOf(LL_Element) + *LL\StrucSize)
    If *LL_E
      If *LL\pAkt
        *LL_E\pNext = *LL\pAkt\pNext
        *LL_E\pPrev = *LL\pAkt
        *LL\pAkt\pNext = *LL_E
        If *LL_E\pNext
          *LL_E\pNext\pPrev = *LL_E
        EndIf
        *LL_E\pParent = *LL
        If *LL_E\pPrev = 0
          *LL\pFirst = *LL_E
        EndIf
        If *LL_E\pNext = 0
          *LL\pLast = *LL_E
        EndIf
      ElseIf *LL\pFirst
        *LL_E\pPrev = 0
        *LL_E\pNext = *LL\pFirst
        *LL\pFirst\pPrev = *LL_E
        *LL_E\pParent = *LL
        *LL\pFirst = *LL_E
      Else
        *LL\pFirst = *LL_E
        *LL\pLast = *LL_E
      EndIf
      *LL\Count + 1
      *LL\pAkt = *LL_E
    EndIf
    ProcedureReturn *LL_E + SizeOf(LL_Element)
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Insert(*LL.LL_Main)
  Protected *LL_E.LL_Element
  If *LL
    *LL_E = AllocateMemory(SizeOf(LL_Element) + *LL\StrucSize)
    If *LL_E
      If *LL\pAkt
        *LL_E\pNext = *LL\pAkt
        *LL_E\pPrev = *LL\pAkt\pPrev
        *LL\pAkt\pPrev = *LL_E
        If *LL_E\pPrev
          *LL_E\pPrev\pNext = *LL_E
        EndIf
        *LL_E\pParent = *LL
        If *LL_E\pPrev = 0
          *LL\pFirst = *LL_E
        EndIf
        If *LL_E\pNext = 0
          *LL\pLast = *LL_E
        EndIf
      ElseIf *LL\pFirst
        *LL_E\pNext = *LL\pFirst
        *LL\pFirst\pPrev = *LL_E
        *LL\pFirst = *LL_E
      Else                      ;Wenn noch kein Element vorhanden war
        *LL\pFirst = *LL_E
        *LL\pLast = *LL_E
      EndIf
      *LL\Count + 1
      *LL\pAkt = *LL_E
    EndIf
    ProcedureReturn *LL_E + SizeOf(LL_Element)
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Delete(*LL.LL_Main)
  Protected *New
  If *LL
    If *LL\pAkt
      *New = *LL\pAkt
      If *LL\pAkt\pPrev
        *LL\pAkt\pPrev\pNext = *LL\pAkt\pNext
      Else
        *LL\pFirst = *LL\pAkt\pNext
      EndIf
      
      If *LL\pAkt\pNext
        *LL\pAkt\pNext\pPrev = *LL\pAkt\pPrev
      Else
        *LL\pLast = *LL\pAkt\pPrev
      EndIf
      
      If *LL\pAkt\pPrev = 0
        *LL\pAkt = 0
      Else
        *LL\pAkt = *LL\pAkt\pPrev
      EndIf
      FreeMemory(*New)
      *LL\Count - 1
      ProcedureReturn #True
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Count(*LL.LL_Main)
  If *LL
    ProcedureReturn *LL\Count
  EndIf
EndProcedure

Procedure.l LL_First(*LL.LL_Main)
  If *LL
    *LL\pAkt = *LL\pFirst
    ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
  EndIf
EndProcedure

Procedure.l LL_Last(*LL.LL_Main)
  If *LL
    *LL\pAkt = *LL\pLast
    ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
  EndIf
EndProcedure

Procedure.l LL_Next(*LL.LL_Main)
  If *LL
    If *LL\pAkt
      If *LL\pAkt\pNext
        *LL\pAkt = *LL\pAkt\pNext
        ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
      Else
        ProcedureReturn #False
      EndIf
    ElseIf *LL\pFirst
      *LL\pAkt = *LL\pFirst
      ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Prev(*LL.LL_Main)
  If *LL
    If *LL\pAkt
      If *LL\pAkt\pPrev
        *LL\pAkt = *LL\pAkt\pPrev
        ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
      Else
        ProcedureReturn #False
      EndIf
    Else
      ProcedureReturn #False
    EndIf
  EndIf
EndProcedure

Procedure.l LL_Pointer(*LL.LL_Main)
  If *LL
    ProcedureReturn *LL\pAkt + SizeOf(LL_Element)
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Reset(*LL.LL_Main)
  If *LL
    *LL\pAkt = 0
  EndIf
EndProcedure

Procedure.l LL_Clear(*LL.LL_Main)
  Protected *LL_E.LL_Element
  If *LL
    If *LL\pFirst
      *LL_E = *LL\pFirst
      While *LL_E\pNext
        *LL_E = *LL_E\pNext
        FreeMemory(*LL_E\pPrev)
      Wend
      FreeMemory(*LL_E)
      *LL\Count = 0
      ProcedureReturn #True
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Change(*LL_E.LL_Element)
  *LL_E - SizeOf(LL_Element)
  If *LL_E
    If *LL_E\pParent
      *LL_E\pParent\pAkt = *LL_E
      ProcedureReturn *LL_E + SizeOf(LL_Element)
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

;verbesserungswürdig... :roll:
Procedure.l LL_Swap(*LL_E1.LL_Element, *LL_E2.LL_Element)
  Protected *LL.LL_Main, *Mem
  
  *LL_E1 - SizeOf(LL_Element)
  *LL_E2 - SizeOf(LL_Element)
  
  If *LL_E1\pParent = *LL_E2\pParent And *LL_E1
    *LL = *LL_E1\pParent
    *Mem = AllocateMemory(*LL\StrucSize)
    If *Mem
      CopyMemory(*LL_E1 + SizeOf(LL_Element), *Mem, *LL\StrucSize)
      CopyMemory(*LL_E2 + SizeOf(LL_Element), *LL_E1 + SizeOf(LL_Element), *LL\StrucSize)
      CopyMemory(*Mem, *LL_E2 + SizeOf(LL_Element), *LL\StrucSize)
      ProcedureReturn #True
    EndIf
    
    ; If *LL_E1 = *LL\pFirst
      ; *LL\pFirst = *LL_E2
    ; ElseIf *LL_E1 = *LL\pLast
      ; *LL\pLast
      ; 
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_Free(*LL.LL_Main)
  Protected *LL_E.LL_Element
  If *LL
    If *LL\pFirst
      *LL_E = *LL\pFirst
      While *LL_E\pNext
        *LL_E = *LL_E\pNext
        FreeMemory(*LL_E\pPrev)
      Wend
      FreeMemory(*LL_E)
    EndIf
    FreeMemory(*LL)
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_SetInteger(*LL.LL_Main, Index.l, Integer.l)
  Protected *Value.LL_AllTypes
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index)
          Case 'b' : *Value\b = Integer
          Case 'w' : *Value\w = Integer
          Case 'l' : *Value\l = Integer
          Default : ProcedureReturn #False
        EndSelect
        ProcedureReturn #True
      EndIf
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure
Procedure.l LL_SetFloat(*LL.LL_Main, Index.l, Float.f)
  Protected *Value.LL_AllTypes
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index)
          Case 'f' : *Value\f = Float
          Default : ProcedureReturn #False
        EndSelect
        ProcedureReturn #True
      EndIf
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure
Procedure.l LL_SetString(*LL.LL_Main, Index.l, String.s)
  Protected *Value.LL_AllTypes
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index)
          Case 's' : *Value\s = String
          Default : ProcedureReturn #False
        EndSelect
        ProcedureReturn #True
      EndIf
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure.l LL_GetInteger(*LL.LL_Main, Index.l)
  Protected *Value.LL_AllTypes
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index)
          Case 'b' : ProcedureReturn *Value\b
          Case 'w' : ProcedureReturn *Value\w
          Case 'l' : ProcedureReturn *Value\l
        EndSelect
        ProcedureReturn #False
      EndIf
    EndIf
  EndIf
  ProcedureReturn #False
EndProcedure
Procedure.f LL_GetFloat(*LL.LL_Main, Index.l)
  Protected *Value.LL_AllTypes, Float.f
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index) & $FF
          Case 'f' : Float = *Value\f
          Default : Float = 0
        EndSelect
        ProcedureReturn Float
      EndIf
    EndIf
  EndIf
  ProcedureReturn 0
EndProcedure
Procedure.s LL_GetString(*LL.LL_Main, Index.l)
  Protected *Value.LL_AllTypes
  If *LL
    If Index >= 0 And Index < *LL\StrucLength
      If *LL\pAkt
        *Value = *LL\pAkt + SizeOf(LL_Element) + PeekL(*LL\StrucOffsets + Index * 4)
        Select PeekB(@*LL\Struc + Index)
          Case 's' : ProcedureReturn *Value\s
        EndSelect
        ProcedureReturn ""
      EndIf
    EndIf
  EndIf
  ProcedureReturn ""
EndProcedure

;}

#Entries = 10

Procedure WriteLinkedList(*LL)
  Protected a.l
  
  LL_Clear(*LL) ; LinkedList löschen
  
  For a = 1 To #Entries
    If LL_Add(*LL)
      LL_SetInteger(*LL, 0, a)
      LL_SetString(*LL, 1, "Value: " + Str(a))
      LL_SetFloat(*LL, 2, 1 / a)
    EndIf
  Next
EndProcedure

Procedure ReadLinkedList(*LL)
  Protected Text.s
  LL_Reset(*LL)
  While LL_Next(*LL)
    Debug LL_GetInteger(*LL, 0)
    Debug LL_GetString(*LL, 1)
    Debug LL_GetFloat(*LL, 2)
  Wend
EndProcedure

Procedure ChangeLinkedList(*LL) ; Löscht alle geraden Zahlen
  LL_Reset(*LL)
  While LL_Next(*LL)
    If LL_GetInteger(*LL, 0) & 1 = 0
      LL_Delete(*LL)
    EndIf
  Wend
EndProcedure

*LL = LL_New("lsf") ; Linkedlist mit der Structure: Long, String, Float
If *LL
  WriteLinkedList(*LL)
  ReadLinkedList(*LL)
  Debug "----------------"
  ChangeLinkedList(*LL)
  Debug "----------------"
  ReadLinkedList(*LL)
  LL_Free(*LL) ; LinkedList wieder freigeben
EndIf

[NicTheQuick]

Neues Update. Versionsnummer verwende ich hier nicht.

Weitere Details siehe erstes Post.

Ansonsten: Hat jemand schon Fehler finden können? Oder wer hat damit denn überhaupt schonmal 'rumgespielt?

[DrShrek]

.... Oder wer hat damit denn überhaupt schonmal 'rumgespielt?

Hast Du selbst schon?

[NicTheQuick]

Klar hab ich das schon. Was funktioniert denn nicht?

[DrShrek]

Keine Ahnung. Habe meine eigenen Listen.

[NicTheQuick]

Cool. Zeig mal her. Welche Vorteile haben die denn gegenüber den Listen von PureBasic.

Meine haben eigentlich nur den Vorteil, dass man bei ihrer Erstellung ein Handle bekommt und sie somit auch dynamisch zum Programmverlauf erstellen kann, was mit den PB-LinkedLists ja nicht funktioniert.

Ich wollte demnächst aber noch andere coden, die wesentlich schneller und einfacher zu handhaben sind als meine bisherige LinkedList und auch noch wunderbar schnell sind, wenn man sie mit Indices anspricht.

[DrShrek]

...Meine haben eigentlich nur den Vorteil, dass man bei ihrer Erstellung ein Handle bekommt und sie somit auch dynamisch zum Programmverlauf erstellen kann, was mit den PB-LinkedLists ja nicht funktioniert...

Nun dazu brauche ich aber nicht unbedingt eine 'Liste'.
Reserviere einen Speicherbereich und arbeite direkt in diesen.

Schnell, dafür nicht komfortabel und nicht unbedingt 'sicher'.

[NicTheQuick]

Ein fester Speicherbereich ist aber keine LinkedList, sondern eher ein Array. Dort kann man nicht mal schnell irgendwo zwischenrein ein Element reinschieben oder eins löschen. Da muss man dann die nachfolgenden immer wieder zurechtrücken.

Also so verstehe ich dein Argument nicht besonders.

[DrShrek]

Ein fester Speicherbereich ist aber keine LinkedList, sondern eher ein Array. Dort kann man nicht mal schnell irgendwo zwischenrein ein Element reinschieben oder eins löschen. Da muss man dann die nachfolgenden immer wieder zurechtrücken.
Also so verstehe ich dein Argument nicht besonders.

Hallo Nic,
Es geht Dir doch in erster Linie um ein 'Handle' das Du an eine z.B. DLL weitergeben möchtest? Also da reicht doch auch ein Array (Dieses muss vorher natürlich entsprechend gefüttert werden.

Möchtest Du aber dieses Array erweitern, dann gebe ich Dir allerdings recht, ein Array ist dafür eher ungeeignet. Es ist eben auch entscheidend was mit dem Daten in der DLL passiert (Read only oder eben auch Write). Und auch wie performant das ganze sein muss.

Geht es Dir aber eher um das dynamische Anlegen einer LinkedList (oder Array) dann denke ich, das das noch ein (wichtiges) fehlendes Feature in PureBasic ist. Es geht hier doch nur darum, das die aktuelle LinkedList auch mit 'PointerVariabeln' klarkommt, "mehr" denke ich, ist es eigentlich nicht.

[DrShrek]

...Geht es Dir aber eher um das dynamische Anlegen einer LinkedList (oder Array) dann denke ich, das das noch ein (wichtiges) fehlendes Feature in PureBasic ist. Es geht hier doch nur darum, das die aktuelle LinkedList auch mit 'PointerVariabeln' klarkommt, "mehr" denke ich, ist es eigentlich nicht.

Hallo @Andre,
was meint eigentlich @Fred zu dieser Behauptung?