PureBoard

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

Selbstprogrammierte LinkedList

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

Seite 1 von 3

Selbstprogrammierte LinkedList

Verfasst: 30.09.2004 00:15
von 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

Verfasst: 23.11.2004 19:37
von 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? /:->

Verfasst: 23.11.2004 20:11
von DrShrek
NicTheQuick hat geschrieben:.... Oder wer hat damit denn überhaupt schonmal 'rumgespielt? /:->
Hast Du selbst schon? :wink:

Verfasst: 23.11.2004 20:20
von NicTheQuick
:?

Klar hab ich das schon. Was funktioniert denn nicht? /:->

Verfasst: 23.11.2004 20:28
von DrShrek
Keine Ahnung. Habe meine eigenen Listen.

Verfasst: 23.11.2004 20:59
von 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.

Verfasst: 23.11.2004 21:18
von DrShrek
NicTheQuick hat geschrieben:...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'.

Verfasst: 23.11.2004 21:54
von 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.

Verfasst: 24.11.2004 08:27
von DrShrek
NicTheQuick hat geschrieben: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.

Verfasst: 24.11.2004 21:32
von DrShrek
IceSoft hat geschrieben:...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? :wink:
Alle Zeiten sind UTC+02:00
Seite 1 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de