The Generics Stack

[himitsu]

Moin ihr alle, :angel:

dieses winzige Produkt ist ein kleiner Stack (kann auch als Queue verwendet werden).

Dank der Generics kann man ihn in allen möglichen Formaten erstellen
und er ist auch noch threadsicher.

Delphi-Quellcode:

Type 
  TStack<Typ> = Class(TCriticalSection)
  Public
    Procedure Push (Const X: Typ);
    Function  Pop  (Var   X: Typ): Boolean; Overload;
    Function  Pop:           Typ;           Overload;
    Function  Count:         Integer;
    Function  Empty:         Boolean;
    Function  Unshift:       Typ;           Overload;
    Function  Unshift(Var X: Typ): Boolean; Overload;
    Procedure Shift(Const X: Typ);
    Procedure Lock;
    Procedure Unlock;
    Function  isLocked:      Boolean;     // by another thread
    Function  Peek:          Typ;         // only if locked
    Property  Item[Index: Integer]: Typ;  // only if locked (read only)
  End;

Hab den kleinen allerdings mit einem dynamischen Array versehn, als Speicher.
Wollte erst eine verkettete Liste nehmen, aber so war einiges einfacher zu lösen.
So muß ich mich an vielen Stellen nicht selber um die Speicherverwaltung kümmern
(vorallen beim Einfügen und Entfernen von Elementen und natürlich auch beim Löschen des Stacks,
also abgesehn vom Shifting kümmert sich die Compilermagic um den Speicher)

Push > Element anhängen
Pop > letztes Element wieder rausholen

Shift > Element vorne einfügen
Unshift > erstes Element vorne rausziehen

Die Function von Pop und Unshift geben True zurück, wenn sie etwas vom Stack holen konnten und geben dieses, im Erfolgsfall, über den Var-Parameter aus.
Die entsprechenden Prozeduren erzeugen in soeinem Fall eine Exception (ERangeError),

Count > gibt die Anzahl der enthaltenen Elemente zurück
Empty > sagt True, wenn nichts auf dem Stack liegt

Und nun noch ein paar Funktionen, wenn man mal mehrere Dinge zusammenhängend machen möchte.

Lock > sperrt den Stack
Unlock > gibt ihn wieder frei
isLocked > gibt Bescheid, ob grade er gesperrt ist (durch einen anderen Thread)

Es wird jeweils nur für andere Threads gesperrt.
Der eigene sperrende Thread kann machen, was er will.
Und die Sperrungen sind kumulativ.

Auf die letzten nun folgenden Funktionen ist nur zugreifbar, wenn der Stack/Queue gelockt ist.

Peek > oberstes Item ( Item[Count-1] ) auslesen
Item > beliebiges Item auslesen

Im Prinzip kümmert sich diese Klasse bei Allem, was kein Pointer/Objekt ist, um die komplette Speicherverwaltung.
Also bei String, Arrays, Interfaces und Records ... dort wird eine interne Kopie angelegt, bzw. die Referenzzählung erhöht, so daß die Klasse "komplett" im Besizt der Daten ist.

Delphi-Quellcode:

Type TStringStack = TGenStack<String>;

Var St: TStringStack;
  S: String;

St := TStringStack.Create;
St.Push(S);
...
S := St.Pop;
St.Free;

//////////////////////////////////

Var St: TGenStack<TMyRecord>;
  S: TMyRecord;

St := TGenStack<TMyRecord>.Create;
...

Im Prinzip könnte es hier gut mit dazupassen :-D
Stack für beliebige Daten


Schlagwörter: TStack TQueue Stack Queue Deque (Double-Ended QUEue) Stapel Keller Schlange Stapelspeicher Kellerspeicher Warteschlange

[XXcD]

Ich weiß jetzt nicht genau ob das richtig ist hier Fragen zu stellen, aber was hat nen Stack genau für ein Vorteil?
Meiner Meinung nach wäre doch ne TList oder TStringlist hier angebrachter oder was sehe ich da falsch?

[omata]

Wieso ist das angebrachter?

Hier wurde ein Beispiel veröffentlicht, wie man einen allgemeinen Stack realisieren kann.

Vor- und Nachteile bzw. wann dieser sinnvoll ist, muss jeder nunmal selbst entscheiden und das kommt auf die Aufgabe bzw. das Problem an vor dem man steht bzw. was man lösen muss.

Also wie jetzt?

Edit: klick

[himitsu]

Joar, also ... ähhhhhhmmmmm ... ja :lol:

Im Prinzip ist es schon eine Liste, aber mit dem Unterschied einer etwas anderen Verwaltung.

Bei einem Stack/Queue greift man im Allgemeinen erstmal nur auf die Enden des Speichers.
Und er ist vorallem als Zwischenspeicher ausgelegt.

Dieser hier ist jetzt zusätzlich noch threadsicher ausgelegt, was auch noch etwas Arbeit erspart.
Abgesehn davon haben die Generics gegenüber 'ner "einfachen" TList noch ein/zwei Vorteile.

Ich weiß ja nicht, wie oft du mit TList und Co. gearbeitet hast, aber bei der Speicherverwaltung muß man schon etwas aufpassen. (gut, wenn man hier Objekte oder Pointer in den Stack packt, dann ändert sich daran nicht viel)


Man könnte sich z.B. in einem Programm 'ne Aufgabenverteilung überlegen.
Das Hauptprogramm trägt dabei nur die zu erledigenden Aufgaben in den Queue ein
und im Hintergrund warten ein oder gar mehrere Threads darauf, daß Arbeit anliegt
und wenn, dann arbeiten sie langsam die im Stack abgelegten Aufgaben ab.

Delphi-Quellcode:

Type TMyRec = Record
    Name:  String;
    Blubb: Irgendwas;
  End;
  TMyStack = TGenStack<TMyRec>

Var MyQueue: TMyStack;
  MyRec: TMyRec;

// Haupprogramm
MyQueue.Push(MyRec);

// Workerthread
Repeat
  If MyQueue.Unshift(MyRec) Then Begin
    ...
  End Else Sleep(100);
Until Terminated;

[XXcD]

Ok

das hat mir schonmal weiter geholfen, war jetzt nur nen wenig überfordert was ein stack überhaupt für einen Sinn ergibt.
Hab auch schon bei Wikipedia nachgeschaut, aber das hat auch nicht weiter geholfen.
Die Antworten haben mir jetzt aber die erleuchtung gebracht :-D

Danke für die Antworten

[Namenloser]

Habe leider kein Delphi 2007, aber interessant finde ich, dass du die Klasse von TCriticalSection abgeleitet hast. Das habe ich so bisher noch nicht gesehen.

[himitsu]

Der Code wurde noch etwas erweitert ... jetzt kann man auch mal in den Stack/Queue reingucken, ohne das Item erst rausholen zu müssen,
aber zur Sicherheit muß dafür der Stack gesperrt werden.
Ich hoffe mal dieses funktioniert auch so, wie es geplant ist.

Zitat:

Zitat von NamenLozer

Habe leider kein Delphi 2007, aber interessant finde ich, dass du die Klasse von TCriticalSection abgeleitet hast. Das habe ich so bisher noch nicht gesehen.

Ist auch mein erstes Mal, daß ich überhaupt direkt TCriticalSection verwende.
Hab sonst immer direkt mit der WinAPI gearbeitet.

Im Prinzip hätte ich auch ein Feld in meiner Klasse anlegen können und dann im Konstuktor/Destruktor die TCriticalSektion selber erstellen/freigeben können.
Aber da es eh keinen Vorfahren gibt, konnte ich von der CS ableiten, hab auch gleich ihre Funktionen geerbt und kann nun ihre Funktionen auch direkt verwenden (siehe Enter und Leave).

Ich geb's zu ... ich, bzw. meine Klasse ist stinkend faul, :lol:
aber es ist schon praktisch, wenn man sich z.B. so etwas Arbeit und Code spart.
Macht das Ganze gleich viel übersichtlicher.

Als reinen einfachen und dennoch threadsicheren Stack kommt man so mit nur 2 winzigkleinen Funktionen aus ...
den Rest übernimmt Delphi für einen.

Delphi-Quellcode:

Unit GenStack;

Interface
  Uses SyncObjs;

  Type TGenStack<Typ> = Class(TCriticalSection)
    Private
      _List: Array of Typ;
    Public
      Procedure Push (Const X: Typ);
      Function  Pop  (Var   X: Typ): Boolean;
    End;

Implementation
  Procedure TGenStack<Typ>.Push(Const X: Typ);
    Begin
      Enter;
      Try
        SetLength(_List, Length(_List) + 1);
        _List[High(_List)] := X;
      Finally
        Leave;
      End;
    End;

  Function TGenStack<Typ>.Pop(Var X: Typ): Boolean;
    Begin
      Enter;
      Try
        Result := Length(_List) > 0;
        If Result Then Begin
          X := _List[High(_List)];
          SetLength(_List, Length(_List) - 1);
        End;
      Finally
        Leave;
      End;
    End;

End.

Joar, ist schon schade mit dem TD ... dabei sind die Generics 'ne ganz feine Sache

Hier z.B. ein Assiziatives Array, wie man es z.B. aus'm PHP kennt.
http://www.delphipraxis.net/internal...t.php?t=156343
Klar, man könnte es auch über eine Klasse lösen, aber so ist es genauso nutzbar, wie ein stinknormales dynamisches Array und man muß sich nicht um die Speicherverwaltung kümmern (.Create und .Free).

[bernau]

@XXcD: Ein Stack z.B. ist dazu da, einen aktuellen Status zu sichern und nach Abarbeitung wieder herzustellen.

Ich mache das gerne mit einem Cursor. Wenn eine Procedure den Cursor verändert, dann muss dieser ja irgendwo zwischengespeichert werden, damit am ende der Procedure die alte Cursor wieder hergestellt wird. Mir war das zu lästig, immer eine Variable anzulegen, in dem der Cursor zwischengespeichert wird. Habe einfach eine Unit geschrieben, in dem es die Funktionen PushCorsor und PopCursor gibt. In der Procedure wird dann am Anfang einfach pushcursor(crhourglass) aufgerufen und am Ende der Procedure wird einfach popcursor aufgerufen, und der vorher angezeigte cursor ist wieder hergestellt.


Gerd

[Meflin]

@himi: Willste die array Größe nicht auf nen bestimmten Wert initialisieren und dann die "Größe verdoppeln bei voll"-Methode anwenden? Das würde die Sache doch performanter machen :stupid:

[himitsu]

Zitat:

Zitat von Meflin

@himi: Willste die array Größe nicht auf nen bestimmten Wert initialisieren und dann die "Größe verdoppeln bei voll"-Methode anwenden? Das würde die Sache doch performanter machen :stupid:

Nein ... keine Lust.

Diese Klasse gefällt mir eigentlich so, wie sie ist ... also schööööööön Einfach. :stupid:
(einfach = weniger Fehlerquellen)

Abgesehn davon haben wir ja rausgefunden, daß es oftmals garnicht nötig ist, wenn hier etwas "verbessert" wird.
siehe http://www.delphipraxis.net/internal...t.php?t=167283

Also, solange jetzt keiner kommt und dadurch wirklich Probleme hat, dann würde ich es erstmal so lassen. :nerd:
(ändern kann man das später immernoch)

[add]
'ne, es gibt leider immer wieder einige Probleme, wenn man innerhalb der Klasse z.B. SizeOf verwenden möchte, denn dieses ist im Fall der Generics keine "Konstanten"-Funktion. :wall:
Sowas geht also nicht,

Delphi-Quellcode:

Const Reserved = {$IF (SizeOf(Typ) < 1024)}1024{$ELSE}128{$IFEND};

aber ich hoff die Ausweichlösung läuft so halbwegs.