C++Talk.NET

Oliver S. · Guest

Ich hab ja wie bereits in einem Vorangegangenen Posting gesagt eine
Aversion gegen std::string, denn wenn das Teil mit dem std::allocator
arbeitet, dann ist die Performance auf eigentlich allen Implementatio-
nen ziemlich schlecht im Vergleich zu einfachen C-Strings auf dem Stack.
Alerdings ist std::string natülich um eine Größenordnung einfacher in
der Handhabung und ermöglicht Buffer-Overflow-freien Code bei korrekter
Benutzung einfacher als das mit C-Strings möglich wäre.
Daher dachte ich mir, daß ich mir einen eigenen Allocator bastle, der
mit Buffern arbeitet die auf dem Stack liegen. Die Buffer dieses Allo-
cators sollten sowohl in ihrer Anzahl als auch in ihrer Größe konfigu-
rierbar sein. Sollte eine Allokations-Anforderung fehlschlagen weil
der Allocator keinen eigenen Buffer mehr vorfindet oder die Buffer
zu klein sind, dann solte er in solchen Fällen zu std::allocator<T>
als Fallback zurückgreifen.
Man könnte jetzt hingehen und einen Allocator basteln der als Template
-Parameter den Basis-Typen, Größe und die Anzahl der internen Buffern
hat. Das würde aber für jede Konstellation dieser Parameter eine Menge
Code-Bloat erzeugen und das noch ausweiten weil für jede dieser mögli-
chen Konstellationen ein eigener STL-Container kompiliert würde. Daher
habe ich mich dafür entschieden, einen Allocator zu definieren der als
Konstruktor-Parameter eine Referenz auf ein Interface eines Buffers
erhält (wie man sieht ist mein lallocator von std::allocator abgeleitet
um eine Menge Datentypen und Methoden nicht selbst definieren zu müs-
sen):

template<typename T>
class lallocator : public std::allocator<T>
{
public:
lallocator( lallocator_buffer_if<T> *plbi );

//...
};

Die Klasse für das lallocator-Buffer-Interface sieht im wesentlichen
so aus:

template<typename T>
class lallocator_buffer_if
{
protected:
template<typename T>
friend class lallocator;

lallocator_buffer_if() {}
T *pop_buffer();
void push_buffer( T *pt );
bool is_yours( T *pt );
};

Der lallocator ist also ein Freund dieser Klasse damit er die internen
Methoden pop_buffer, push_buffer und is_yours verwenden kann. pop_buffer
holt einen Buffer und reserviert sich den (intern sind die Buffer als
ein Stack verkettet), push_buffer gibt den wieder zurück und is_yours
ist da damit der lallocator nachfragen kann ob ein ein Zeiger zu einem
der internen Buffern gehört; damit kann er erkennen ob ein Block bei
einer deallocate()-Operation über einen Buffer befriedigt werden konnte
oder der über den std::allocator<T>-Fallback beschafft werden musste um
somit den Block ggf bei std::allocator<T>::dealocate() abzugeben.
Von dem lallocator_buffer_if ist dann die konkrete Buffer-Klasse abge-
leitet die als Template-Parameter den Datentypen, die Anzahl der Buffer
und die Größe eines Buffers enthält:

template<typename T, std::size_t buffers, std::size_t buffer_size>
class lallocator_buffer : public lallocator_buffer_if<T>
{
public:
lallocator_buffer();
//..
};

Der Konstruktor initialisiert private Elemente der Basisklasse lallo-
cator_buffer_if so daß diese weiß, wie groß die Buffer sind, wieviele
es davon gibt und wie sie diese Finden kann (es wird also der interne
Stack initialisiert).

Sieht doch nett, aus nicht? Und bringt STL-Operationen auf std::basic
_string<> sicher superschnell; so schnell, daß man damit in diese selbe
Größenordnung wie die C-Strings kommt.

So, und nun für die, die's interessier hier der komplette Source des
lallocators. Das Ding ist sicher noch nicht 100% STL-Konform, aber
sollten sich dadurch Probleme ergeben, so werde ich die ganze Sache
sicher noch aufblasen. Übrigens: bitte nicht weinen wenn ich religiö-
sen Ansprüchen an die C++-Konformität nicht gerecht geworden bin (hab
an einer Stelle etwas rumgetrickst).

template<typename T>
class lallocator_buffer_if
{
protected:
template<typename T, std::size_t buffers, std::size_t buffer_size>
friend class lallocator_buffer;

template<typename T>
friend class lallocator;

private:
lallocator_buffer_if() {}
T *pop_buffer();
void push_buffer( T *pt );
bool is_yours( T *pt );

protected:
union buffer_header
{
buffer_header *pbhNextFree;
T at[1];
};

protected:
std::size_t m_buffer_size;
buffer_header *m_pbhBufferEnd;
buffer_header *m_pbhFirstFree;
};

template<typename T>
inline
T *lallocator_buffer_if<T>::pop_buffer()
{
buffer_header *pbh;

if( (pbh = m_pbhFirstFree) == NULL )
return NULL;

return m_pbhFirstFree = pbh->pbhNextFree,
&pbh->at[0];
}

template<typename T>
inline
void lallocator_buffer_if<T>::push_buffer( T *pt )
{
buffer_header *pbh;

pbh = (buffer_header *)pt;
pbh->pbhNextFree = pbh;
m_pbhFirstFree = pbh;
}

template<typename T>
inline
bool lallocator_buffer_if<T>::is_yours( T *pt )
{
return (void*)pt >= (void *)this &&
pt < &m_pbhBufferEnd->at[0];
}

template<typename T, std::size_t buffers, std::size_t buffer_size>
class lallocator_buffer : public lallocator_buffer_if<T>
{
public:
lallocator_buffer();

private:
union buffer
{
buffer_header bh;
T at[buffer_size];
};

private:
buffer aBuffers[buffers];
};

template<typename T, std::size_t buffers, std::size_t buffer_size>
inline
lallocator_buffer<T, buffers, buffer_size>::lallocator_buffer()
{
buffer *pbuf,
*pbufNext;

for( (pbuf = &aBuffers[buffers - 1],
pbufNext = NULL);
pbuf >= aBuffers;
(pbuf -= 1,
pbufNext = pbuf) )
pbuf->bh.pbhNextFree = &pbufNext->bh;

m_buffer_size = buffer_size;
m_pbhBufferEnd = &aBuffers[buffers].bh;
m_pbhFirstFree = &aBuffers[0].bh;
}

template<typename T>
class lallocator : public std::allocator<T>
{
public:
lallocator( lallocator_buffer_if<T> *plbi );
lallocator( lallocator const &l );
~lallocator() {};
pointer allocate( size_type count, void *hint = NULL );
void deallocate( pointer ptr, size_type count );
lallocator &operator =( lallocator &la );

public:
template<class Other>
struct rebind
{
typedef lallocator<Other> other;
};

private:
lallocator_buffer_if<T> *m_plbi;
};

template<typename T>
inline
lallocator<T>::lallocator( lallocator_buffer_if<T> *plbi ) :
std::allocator<T>()
{
m_plbi = plbi;
}

template<typename T>
inline
lallocator<T>::lallocator( lallocator const &l ) :
std::allocator<T>( l )
{
m_plbi = l.m_plbi;
}

template<typename T>
inline
typename lallocator<T>::pointer lallocator<T>::allocate( size_type count,
void *hint )
{
T *pt;

if( count > m_plbi->m_buffer_size ||
(pt = m_plbi->pop_buffer()) == NULL )
return std::allocator<T>::allocate( count ); // , hint );

return pt;
}

template<typename T>
inline
void lallocator<T>::deallocate( pointer ptr, size_type count )
{
if( !m_plbi->is_yours( ptr ) )
return std::allocator<T>::deallocate( ptr, count );

m_plbi->push_buffer( ptr );
}

template<typename T>
inline
typename lallocator<T> &lallocator<T>::operator =( lallocator &la )
{
plb = la.plb;
}

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

Oliver S. · Guest

Scheiße, hab das Ding etwas auf die Schnelle runtergeschrieben und
dabei zwei fette Bugs einebaut - und das bei so einer einfachen Sache.
Zu meiner Ehrenrettung muss ich aber sagen, daß ich schon fast 15h
programmiert hatte als ich das Ding gebastelt hatte (ich bin nicht
erst aufgestanden als ich um 7:Irgendwas Uhr das Ding gepostet habe.

Daher hier die gefixte Version:

template<typename T>
class lallocator_buffer_if
{
protected:
template<typename T, std::size_t buffers, std::size_t buffer_size>
friend class lallocator_buffer;

template<typename T>
friend class lallocator;

private:
lallocator_buffer_if() {}
T *pop_buffer();
void push_buffer( T *pt );
bool is_yours( T *pt );

protected:
union buffer_header
{
buffer_header *pbhNextFree;
T at[1];
};

protected:
std::size_t m_buffer_size;
buffer_header *m_pbhFirstFree;
buffer_header *m_pbhBufferEnd;
};

template<typename T>
inline
T *lallocator_buffer_if<T>::pop_buffer()
{
buffer_header *pbh;

if( (pbh = m_pbhFirstFree) == NULL )
return NULL;

return m_pbhFirstFree = pbh->pbhNextFree,
&pbh->at[0];
}

template<typename T>
inline
void lallocator_buffer_if<T>::push_buffer( T *pt )
{
buffer_header *pbh;

pbh = (buffer_header *)pt;
pbh->pbhNextFree = m_pbhFirstFree;
m_pbhFirstFree = pbh;
}

template<typename T>
inline
bool lallocator_buffer_if<T>::is_yours( T *pt )
{
return (void*)pt >= (void *)this &&
pt < &m_pbhBufferEnd->at[0];
}

template<typename T, std::size_t buffers, std::size_t buffer_size>
class lallocator_buffer : public lallocator_buffer_if<T>
{
public:
lallocator_buffer();

private:
union buffer
{
buffer_header bh;
T atUnReferenced[buffer_size];
};

private:
buffer aBuffers[buffers];
};

template<typename T, std::size_t buffers, std::size_t buffer_size>
inline
lallocator_buffer<T, buffers, buffer_size>::lallocator_buffer()
{
buffer *pbuf,
*pbufNext;

for( (pbuf = &aBuffers[buffers - 1],
pbufNext = NULL);
pbuf >= aBuffers;
(pbufNext = pbuf,
pbuf -= 1) )
pbuf->bh.pbhNextFree = &pbufNext->bh;

m_buffer_size = buffer_size;
m_pbhBufferEnd = &aBuffers[buffers].bh;
m_pbhFirstFree = &aBuffers[0].bh;
}

template<typename T>
class lallocator : public std::allocator<T>
{
public:
lallocator( lallocator_buffer_if<T> *plbi );
lallocator( lallocator const &lc );
~lallocator() {};
pointer allocate( size_type count, void *hint = NULL );
void deallocate( pointer ptr, size_type count );
lallocator &operator =( lallocator const &lc );

public:
template<class Other>
struct rebind
{
typedef lallocator<Other> other;
};

private:
lallocator_buffer_if<T> *m_plbi;
};

template<typename T>
inline
lallocator<T>::lallocator( lallocator_buffer_if<T> *plbi ) :
std::allocator<T>()
{
m_plbi = plbi;
}

template<typename T>
inline
lallocator<T>::lallocator( lallocator const &lc ) :
std::allocator<T>( lc )
{
m_plbi = lc.m_plbi;
}

template<typename T>
inline
typename lallocator<T>::pointer lallocator<T>::allocate( size_type count,
void *hint )
{
T *pt;

if( count > m_plbi->m_buffer_size ||
(pt = m_plbi->pop_buffer()) == NULL )
return std::allocator<T>::allocate( count );

return pt;
}

template<typename T>
inline
void lallocator<T>::deallocate( pointer ptr, size_type count )
{
if( !m_plbi->is_yours( ptr ) )
return (void)std::allocator<T>::deallocate( ptr, count );

m_plbi->push_buffer( ptr );
}

template<typename T>
inline
typename lallocator<T> &lallocator<T>::operator =( lallocator const &lc )
{
return m_plbi = lc.m_plbi,
*this;
}

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

albrecht.fritzsche · Guest

Oliver S. wrote:

Oliver S. · Guest

albrecht.fritzsche · Guest

Oliver S. wrote:

Oliver S. · Guest

albrecht.fritzsche · Guest

Hm, ich bin immer noch nicht weiter mit dem Verstaendnis

Oliver S. wrote:

Oliver S. · Guest

albrecht.fritzsche · Guest

Oliver S. wrote: