1.0 Vorwort
Da Zeichenketten ein essentielles Element von Programmen sind existieren viele Klassen die verschiedene Funktionalitäten zur Zeichenkettenmanipulation kapseln. Thema dieses Tutorials ist es nicht eine weitere Stringklasse zu erstellen, viel mehr will ich speziell auf ein Unterthema eingehen, das Kopierverhalten von Stringobjekten.
Beim kopieren von Zeichenketten kann man zwischen zwei Verhalten unterscheiden. Zum einen das duplizieren der kompletten Objektresourcen, beim erstellen einer Kopie des Strings. Zum anderen das zählen von Referenzen auf die Ressourcen. Genau letzteres Verhalten soll Thema dieses Tutorials sein.
2.0 Referenzzählung
Um den Begriff nochmals kurz zu erläutern. Das zählen von Referenzen auf ein Objekt (engl. Reference counting) ermöglicht es zum einen eine Art Buchhaltung zu führen ob ein Objekt noch benötigt wird, oder nicht. Dies hat einige Vorteile, z.B. ist es möglich zu entscheiden ob ein Objekt gelöscht werden soll (Smartpointer) oder um allgemein festzustellen ob noch andere Referenzen auf ein Objekt existieren.
Es gibt einige Ansätze um dieses Pattern zu implementieren. Es ist z.B. möglich eine abstrakte Klasse für zählbare Objekte zu erzeugen und konkrete Implementationen an einem Smartpointer zu übergeben. Ein anderer Ansatz ist es den Zähler als geteilten Speicher (engl. shared memory) auf dem Heap direkt im Smartpointer zu halten. Jede der bekannten Techniken hat ihre Vor- und Nachteile, so erlaubt z.B. die zuerst genannte keine primitiven Datentypen als zählbare Objekte, letztere ist u.U. schwerer zu implementieren. Beide genannten Techniken finden aber Verwendung, so beruht die Smartpointer Implementierung von boost z.B. auf dem zuletzt genannten Ansatz.
Weitere Informationen zu dem Thema finden sich u. A. in Scott Meyers Buch „More effective c++“.
3.0 Reference counted Strings
Eins der Einsatzgebiete von Referenzzählung ist z.B. das zählen von Referenzen auf Stringobjekte. Es kommt nicht selten vor das ein Programm viele Zeichenkennten nutzt die sich exakt gleichen. Es entstehen oftmals (temporäre-) Kopien von Zeichenketten, und jede Kopie belegt gleich viel Speicher, nämlich im besten Fall genau ‚n‘ mal die Anzahl der Zeichen im String.
Besser wäre es aber wenn Strings, deren Inhalt sich genau gleicht, auf denselben Speicher zeigen, und einfach Buchhaltung über die Anzahl der Referenzen führen würden. Nach kurzen nachdenken wird man aber feststellen das, sobald zwei Strings sich speicher Teilen, eine Änderung an einem der Strings nicht mehr möglich ist, da die Änderung sich ja auf beide Objekte beziehen würde. Und genau das bringt uns zum nächsten Abschnitt, dem…
4.0 Lazy loading
Unter lazy loading versteht man ein Designpattern das es erlaubt Ressourcen spät möglichst zu laden (bzw, hier COW (copy on write)). Der späteste Zeitpunkt für ein Stringobjekt ist es, wenn das Objekt geändert werden soll. Das Vorgehen, speziell bei Strings, ist folgendermaßen.
• Prüfen ob andere Referenzen existieren
• Ist dies der Fall müssen die Ressourcen geladen, und der Referenzzähler auf eins gesetzt werden
• Andernfalls muss nichts passieren
Ist das Objekt „einzigartig“ können die Daten manipuliert werden ohne andere Objekte zu beeinflussen.
5.0 Designideen
Nun zum Praktischen Teil der trockenen Theorie.
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template< typename T >
class TString
{
class StringBuffer
{
~StringBuffer()
{
delete [] m_pData;
}
uint32 m_nAllocated;
uint32 m_nLen;
T* m_pData;
};
private:
SharedPtr< StringBuffer > m_pBuffer;
};
|
In diesem Beispiel werden die tatsächlichen Daten von einem Objekt vom Typ StringBuffer gehalten. Der String selbst hält nur einen Zeiger auf die Daten. Dies ermöglicht es gleiche Zeichenketten von mehreren Stringobjekten zu referenzieren. Theoretisch ist das Kopierverhalten des Strings schon korrekt, wäre da nicht die Problematik, welche in Abschnitt 4.0 besprochen wurde, dem späten laden von Ressourcen. Es muss also eine Möglichkeit geben ein Objekt aus der Referenzzählung abzukoppeln. Um die Kopie der Daten zu erzeugen bietet sich ein Kopierkonstruktor von StringBuffer an.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
|
StringBuffer( const StringBuffer& other ) : m_nAllocated( 0 ), m_nLen( 0 ), m_pData( NULL )
{
Resize( other.m_nAllocated );
TString< T >::_copy( m_pData, other.m_pData, other.m_nLen );
m_nLen = other.m_nLen;
m_pData[ m_nLen ] = 0;
}
|
Der Code ist selbsterklärend. Resize() vergrößert den Speicher und _copy() ist eine einfache Hilfsmethode um die Daten zu kopieren:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
|
template< typename T >
inline void TString< T >::_copy( T* dest, const T* source, uint32 count )
{
memcpy( dest, source, count * sizeof( T ) );
}
|
Jetzt sind alle nötigen Vorkehrungen getroffen um das Objekt abzukoppeln. Da dies an vielen Stellen passiert lohnt es sich auch hier eine Hilfsfunktion zu schreiben:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
|
template< typename T >
inline void TString< T >::_UniqueBuffer()
{
if ( IsShared() )
{
SharedPtr<StringBuffer>(
new StringBuffer(*m_pBuffer)).Swap(m_pBuffer);
}
}
|
Um ein korrekten „Reset“ des Zeigers zu gewährleisten kann, wie im obigen Code, das copy and swap Idiom verwendet werden. Es wird eine temporäre Kopie erzeugt anschließend die Inhalte der Kopie und dem eigentlichen Zeiger getauscht. Dieses Vorgehen hat u. A. auch den Vorteil das, beim zerstören der temporären Kopie, die Daten vom Smartpointer freigegeben werden, oder zumindest der Refernzzähler dekrementiert wird.
Bei vielen, aber nicht allen, Methoden wird es allerdings notwendig sein den Stringpuffer, nach dem Abkoppeln, noch zu vergrößern. Daher lohnt sich auch hier eine Hilfsmethode:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
|
template< typename T >
inline void TString< T >::_ModifyContent( uint32 size )
{
_UniqueBuffer();
m_pBuffer->Resize( size );
}
|
Es sind nun alle Werkzeuge da um einige wichtige Stringfunktionen zu implementieren. Zum Beispiel das Zuweisen eines Strings.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
|
template< typename T >
inline void TString< T >::_Assign( const T* str, uint32 len )
{
_ModifyContent( len );
_copy( m_pBuffer->m_pData, str, len );
m_pBuffer->m_pData[ len ] = 0;
m_pBuffer->m_nLen = len;
}
|
Die Durchführung ist sehr einfach. Das Objekt wird, falls notwendig, entkoppelt, auf die richtige Größe gebracht und schließlich die Daten kopiert. Will man einen nullterminierten String halten so muss, konsequent bei jeder notwendigen Funktion, eine weitere 0 an das Ende der Daten gehängt werden.
Für jede Funktion welche die Daten der Zeichenkette ändert ist die grundlegende Vorbereitung gleich der, bei _Assign(), vorgestellten. Der Unterschied liegt nur bei der Bearbeitung der Daten. Es ist aber nun mehr möglich Stringobjekte auf geteilten Speicher zeigen zu lassen, bis die Daten geändert werden sollen. Und das kann schon eine große Ersparnis Ressourcen sein.
6.0 Ausnahmen
Um Langeweile vorzubeugen muss es natürlich Ausnahmen geben. Will man z.B. Referenzen auf Stringdaten bereitstellen bekommt man spätestens dann Probleme wenn der String wieder mehrfach referenziert wird. Ein Beispiel:
|
|
C-/C++-Quelltext
|
1
2
3
4
|
String str1 = "Hallo Welt";
char& c = str1[ 1 ];
String str2 = str1;
c = 'e';
|
Der []-Operator kommt mit seiner nicht konstante Version häufig mit Referenzen als Rückgabewert. Dies macht ja Sinn, da der Operator eine Manipulation von internen Daten bezwecken soll. In diesem Fall birgt die Idee aber Risiken, da das Beispiel zu viel des Guten tut und sich die Änderung gleich auf alle Referenzierenden Stringobjekte bezieht.
Dieses Verhalten ist in den meisten Fällen nicht gewünscht. Und so muss eine Abhilfe her, falls der Operator unbedingt bereitgestellt werden soll. Die Idee ist es, das Kopierverhalten des Referenzierten Objekts zu verändern, selbiges nämlich als nicht Teilbar zu kennzeichnen. Wird eine Kopie eines solchen Objekts erzeugt so werden die Daten tatsächlich kopiert und nicht einfach der Referenzzähler inkrementiert. Um dies zu erreichen muss die Funktion _UniqueBuffer() leicht geändert werden:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
|
template< typename T >
inline void TString< T >::_UniqueBuffer( bool makeUnshareable )
{
if ( makeUnshareable || IsShared() )
{
SharedPtr< StringBuffer >(
new StringBuffer( *m_pBuffer ) ).Swap( m_pBuffer );
if ( makeUnshareable )
::MakeTargetUnshareable( m_pBuffer );
}
}
|
Beim abkoppeln des Objekts kann das Objekt nun gekennzeichnet werden. Dies ist notwendig um später feststellen zu können ob das Objekt kopiert werden muss. Nun ist es möglich den []-Operator zu implementieren ohne die oben genannten Probleme zu bekommen.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
|
template< typename T >
inline T& TString< T >::operator[]( uint32 index )
{
assert( index < m_pBuffer->m_nLen );
_UniqueBuffer( true );
return m_pBuffer->m_pData[ index ];
}
|
Das Problem ist nun aber, dass das Objekt zwar als nicht „shareable“ gekennzeichnet ist, das Kopierverhalten selbst aber noch nicht geändert wurde. Betroffen sind zwei Stellen, nämlich der Kopierkonstruktor und der Zuweisungsoperator.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
|
template< typename T >
inline void TString< T >::_SharedAssign( const TString< T >& str )
{
if ( !::IsTargetUnshareable( str.m_pBuffer ) )
m_pBuffer = str.m_pBuffer;
else
SharedPtr< StringBuffer >(
new StringBuffer( *str.m_pBuffer ) ).Swap( m_pBuffer );
}
|
Alles was getan werden muss ist zu überprüfen ob das Quellobjekt „teilbar“ ist. Ist dies der Fall kann wie gehabt fortgefahren werden. Ansonsten muss eine Kopie des Puffers erzeugt werden. Hiermit können Kopierkonstruktor und Zuweisungsoperator implementiert werden:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
template< typename T >
inline TString< T >::TString( const TString< T >& str )
{
Initialize();
Assign( str );
}
template< typename T >
inline TString< T >& TString< T >::operator=( const TString< T >& str )
{
if ( this != &str )
_SharedAssign( str );
return *this;
}
template< typename T >
inline TString< T >& TString< T >::Assign( const TString< T >& str )
{
_SharedAssign( str );
return *this;
}
|
7.0 Zusammenfassend
Ein Problem gibt es noch. Die Klasse StringBuffer ist kein zählbares Objekt. Die Funktionalität muss noch programmiert werden. Da es ja durchaus vorkommen Mag dass die Funktionalität an verschiedenen Stellen verwendet werden kann, lohnt es sich eine Basisklasse zu erzeugen, welche die grundlegende Funktionalität bereitstellt:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
template< typename T, T UnshareableTag >
class UnshareableRefTarget
{
public:
typedef T ReferenceType;
void AddReference( bool makeUnshareable = false )
{
if ( !makeUnshareable && m_nRefCount != UnshareableTag )
++m_nRefCount;
else
m_nRefCount = UnshareableTag;
}
void Release()
{
if ( m_nRefCount == UnshareableTag || --m_nRefCount <= 0 )
delete this;
}
const T& References() const
{
return m_nRefCount;
}
void MakeUnshareable()
{
m_nRefCount = UnshareableTag;
}
bool IsUnshareable() const
{
return m_nRefCount == UnshareableTag;
}
protected:
UnshareableRefTarget() : m_nRefCount( T() )
{
}
UnshareableRefTarget( const UnshareableRefTarget& ) : m_nRefCount( T() )
{
}
virtual ~UnshareableRefTarget()
{
}
UnshareableRefTarget& operator=( const UnshareableRefTarget& )
{
return *this;
}
private:
T m_nRefCount;
};
|
Außerdem werde zwei Funktion benötigt, um feststellen zu können ob ein Objekt „teilbar“ ist oder nicht und um ein solches als „nicht teilbar“ zu markieren.
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
|
template< typename Ptr >
inline void MakeTargetUnshareable( const Ptr& ptr )
{
ptr.m_pPtr->MakeUnshareable();
}
template< typename Ptr >
inline bool IsTargetUnshareable( const Ptr& ptr )
{
return ptr.m_pPtr->IsUnshareable();
}
|
Alles was nun noch getan werden muss ist die Klasse Stringbuffer als Spezialisierung von UnshareableRefTarget zu kennzeichnen:
|
|
C-/C++-Quelltext
|
1
|
class StringBuffer : public UnshareableRefTarget< int32, ( int32 )~0 >
|
8.0 Nachwort
Dieses Tutorial entstand nachdem ich in meinem Framework ein allgemeines String Template implementiert hatte. Da ich einiges an Zeit investiert habe um mich mit den bekannten (und nicht bekannten) Problemen zu befassen, habe ich beschlossen das Ganze mal zusammenzufassend als Tutorial zu schreiben. Ich hoffe das der Leser einige Informationen aus dem Text ziehen kann und hoffe auch das selbigen einiges an Informationssuche Aufwand erspart bleiben kann!
Zitat von »"rewb0rn"«
Sieht gut aus. Hab erst gestern den Artikel über referenzzählende Speicherverwaltungsobjekte in Effective C++ gelesen, da ist das ein guter Anschluss. Ich vertraue mal deinem Fachwissen dahingehend, dass das Tutorial ausgereift genug ist, um in das entsprechende Unterforum verschoben zu werden
28.04.2024, 20:57
Zum Seitenanfang
