From 033c41ed57348abb3a418166b1fb39bfad3312de Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Fri, 11 May 2007 07:51:40 +0000 Subject: Added a list template class, seems to work pretty well for now, I may have forgotten proper cleanup in the deconstructor, but besides that you can do almost everything you need. I'll make a slist/stack next, probably with the same basic code, just a different structure (not doubley-linked). The xml system from old-libbu++ is almost completely converted, I was going to re-write it, but this seemed easier at first, it may not have been, we'll see. It almost parses everything again, and almost outputs again, and it does use streams now. The FString is partway to doing minimum chunk allocations, so that adding single-characters will be really fast up to the minimum chunk size. I also figured out how to add this optimization without any extra variables taking up space, and it's optional in the template, which is cool. You can specify the size of the blocks (default 256 bytes), if it's 0 then they'll be like the old FString, 1 chunk per operation. The next FString update should be allowing efficient removal from the begining of the string by faking it, and simply moving a secondary base pointer ahead, and then optimizing appends after that fact to simply move the existing data around if you shouldn't have to re-allocate (alla FlexBuf). The final fun addition that I'm planning is a simple switch in the template (boolean) that will switch an FString into a thread-safe mode without changing the interface or anything that you can do with them at all. It may increasing memory usage, but they should still be better than std::strings, and totally thread-safe. The best part of that is that if it's done with a boolean template parameter and if statements that only test that parameter controlling flow, the code that you don't want (threadsafe/non-threadsafe) won't be included at all post-optimization. --- src/tests/list.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 src/tests/list.cpp (limited to 'src/tests/list.cpp') diff --git a/src/tests/list.cpp b/src/tests/list.cpp new file mode 100644 index 0000000..34ab656 --- /dev/null +++ b/src/tests/list.cpp @@ -0,0 +1,22 @@ +#include "bu/list.h" + +int main() +{ + Bu::List l; + + l.append( 0 ); + + for( int j = 3; j <= 21; j += 3 ) + { + l.append( j ); + l.prepend( -j ); + } + + for( Bu::List::iterator i = l.begin(); i != l.end(); i++ ) + { + printf("%d ", *i ); + } + + printf("\n\n"); +} + -- cgit v1.2.3 From dda94f3b53e02e117e6eb5758afa1410e1664c9f Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 15 May 2007 05:25:19 +0000 Subject: SPtr is now Bu::ified, and the List class now acts the way we think const lists should act, you can't change anything in there. I'm still debating changing the const_iterator to a constIterator, or something else that's more Bu::worthy. Heh, the namespaces are funny...ok...I'm really tired. --- src/list.h | 214 ++++++++++++++++++++++++++++++++++++++++++++++++----- src/old/sptr.cpp | 1 - src/old/sptr.h | 99 ------------------------- src/serversocket.h | 10 ++- src/sptr.cpp | 1 + src/sptr.h | 147 ++++++++++++++++++++++++++++++++++++ src/tests/list.cpp | 31 ++++++++ 7 files changed, 382 insertions(+), 121 deletions(-) delete mode 100644 src/old/sptr.cpp delete mode 100644 src/old/sptr.h create mode 100644 src/sptr.cpp create mode 100644 src/sptr.h (limited to 'src/tests/list.cpp') diff --git a/src/list.h b/src/list.h index ec63496..4d16872 100644 --- a/src/list.h +++ b/src/list.h @@ -13,6 +13,15 @@ namespace Bu ListLink *pNext; ListLink *pPrev; }; + + /** + * Linked list template container. This class is similar to the stl list + * class except for a few minor changes. First, it doesn't mimic a stack or + * queue, use the Stack or Queue clasess for that. Second, when const, all + * members are only accessable const. Third, erasing a location does not + * invalidate the iterator, it simply points to the next valid location, or + * end() if there are no more. + */ template, typename linkalloc=std::allocator > > class List { @@ -23,15 +32,59 @@ namespace Bu public: List() : pFirst( NULL ), - pLast( NULL ) + pLast( NULL ), + nSize( 0 ) + { + } + + List( const MyType &src ) : + pFirst( NULL ), + pLast( NULL ), + nSize( 0 ) + { + for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) + { + append( *pCur->pValue ); + } + } + + ~List() + { + clear(); + } + + MyType &operator=( const MyType &src ) { + clear(); + for( Link *pCur = src.pFirst; pCur; pCur = pCur->pNext ) + { + append( *pCur->pValue ); + } + } + + void clear() + { + Link *pCur = pFirst; + for(;;) + { + if( pCur == NULL ) break; + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + pCur = pTmp; + } + pFirst = pLast = NULL; + nSize = 0; } - void append( value v ) + void append( const value &v ) { Link *pNew = la.allocate( sizeof( Link ) ); pNew->pValue = va.allocate( sizeof( value ) ); va.construct( pNew->pValue, v ); + nSize++; if( pFirst == NULL ) { // Empty list @@ -47,11 +100,12 @@ namespace Bu } } - void prepend( value v ) + void prepend( const value &v ) { Link *pNew = la.allocate( sizeof( Link ) ); pNew->pValue = va.allocate( sizeof( value ) ); va.construct( pNew->pValue, v ); + nSize++; if( pFirst == NULL ) { // Empty list @@ -83,22 +137,22 @@ namespace Bu } public: - bool operator==( const iterator &oth ) + bool operator==( const iterator &oth ) const { return ( pLink == oth.pLink ); } - bool operator==( const Link *pOth ) + bool operator==( const Link *pOth ) const { return ( pLink == pOth ); } - bool operator!=( const iterator &oth ) + bool operator!=( const iterator &oth ) const { return ( pLink != oth.pLink ); } - bool operator!=( const Link *pOth ) + bool operator!=( const Link *pOth ) const { return ( pLink != pOth ); } @@ -110,40 +164,128 @@ namespace Bu value *operator->() { - return pLink->pValue(); + return pLink->pValue; } - iterator operator++() + iterator &operator++() { if( pLink != NULL ) pLink = pLink->pNext; return *this; } - iterator operator--() + iterator &operator--() { if( pLink != NULL ) pLink = pLink->pPrev; return *this; } - iterator operator++( int ) + iterator &operator++( int ) { if( pLink != NULL ) pLink = pLink->pNext; return *this; } - iterator operator--( int ) + iterator &operator--( int ) { if( pLink != NULL ) pLink = pLink->pPrev; return *this; } - iterator operator=( const iterator &oth ) + iterator &operator=( const iterator &oth ) { pLink = oth.pLink; + return *this; + } + }; + + typedef struct const_iterator + { + friend class List; + private: + Link *pLink; + const_iterator() : + pLink( NULL ) + { + } + + const_iterator( Link *pLink ) : + pLink( pLink ) + { + } + + public: + bool operator==( const const_iterator &oth ) const + { + return ( pLink == oth.pLink ); + } + + bool operator==( const Link *pOth ) const + { + return ( pLink == pOth ); + } + + bool operator!=( const const_iterator &oth ) const + { + return ( pLink != oth.pLink ); + } + + bool operator!=( const Link *pOth ) const + { + return ( pLink != pOth ); + } + + const value &operator*() + { + return *(pLink->pValue); + } + + const value *operator->() + { + return pLink->pValue; + } + + const_iterator &operator++() + { + if( pLink != NULL ) + pLink = pLink->pNext; + return *this; + } + + const_iterator &operator--() + { + if( pLink != NULL ) + pLink = pLink->pPrev; + return *this; + } + + const_iterator &operator++( int ) + { + if( pLink != NULL ) + pLink = pLink->pNext; + return *this; + } + + const_iterator &operator--( int ) + { + if( pLink != NULL ) + pLink = pLink->pPrev; + return *this; + } + + const_iterator &operator=( const iterator &oth ) + { + pLink = oth.pLink; + return *this; + } + + const_iterator &operator=( const const_iterator &oth ) + { + pLink = oth.pLink; + return *this; } }; @@ -152,17 +294,50 @@ namespace Bu return iterator( pFirst ); } - const Link *end() + const const_iterator begin() const + { + return const_iterator( pFirst ); + } + + const Link *end() const { return NULL; } - int getSize() + void erase( iterator &i ) + { + Link *pCur = i.pLink; + Link *pPrev = pCur->pPrev; + if( pPrev == NULL ) + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + pFirst = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + if( pFirst == NULL ) + pLast = NULL; + nSize--; + i.pLink = pFirst; + } + else + { + va.destroy( pCur->pValue ); + va.deallocate( pCur->pValue, sizeof( value ) ); + Link *pTmp = pCur->pNext; + la.destroy( pCur ); + la.deallocate( pCur, sizeof( Link ) ); + pPrev->pNext = pTmp; + if( pTmp != NULL ) + pTmp->pPrev = pPrev; + nSize--; + i.pLink = pTmp; + } + } + + int getSize() const { - int j = 0; - for( Link *pCur = pFirst; pCur; pCur = pCur->pNext ) - j++; - return j; + return nSize; } private: @@ -170,6 +345,7 @@ namespace Bu Link *pLast; linkalloc la; valuealloc va; + int nSize; }; } diff --git a/src/old/sptr.cpp b/src/old/sptr.cpp deleted file mode 100644 index 7f5e894..0000000 --- a/src/old/sptr.cpp +++ /dev/null @@ -1 +0,0 @@ -#include "sptr.h" diff --git a/src/old/sptr.h b/src/old/sptr.h deleted file mode 100644 index deae94d..0000000 --- a/src/old/sptr.h +++ /dev/null @@ -1,99 +0,0 @@ -#ifndef SPTR_H -#define SPTR_H - -#include -#include - -template -class SPtr -{ -public: - SPtr() : - pRefCnt( NULL ), - pData( NULL ) - { - } - - ~SPtr() - { - decCount(); - } - - SPtr( const SPtr &src ) : - pRefCnt( src.pRefCnt ), - pData( src.pData ) - { - if( pRefCnt ) - (*pRefCnt) += 1; - } - - SPtr( T *pSrc ) : - pRefCnt( NULL ), - pData( pSrc ) - { - pRefCnt = new int32_t; - (*pRefCnt) = 1; - } - - int32_t count() - { - return *pRefCnt; - } - - T *operator->() const - { - return pData; - } - - T *operator*() const - { - return pData; - } - - SPtr operator=( const SPtr &src ) - { - decCount(); - pRefCnt = src.pRefCnt; - pData = src.pData; - (*pRefCnt) += 1; - - return *this; - } - - bool operator==( const SPtr &src ) - { - return pData == src.pData; - } - - operator bool() - { - return pRefCnt != NULL; - } - - bool isSet() - { - return pRefCnt != NULL; - } - -private: - void decCount() - { - if( pRefCnt ) - { - (*pRefCnt) -= 1; - //printf("Decrementing ref-count to %d\n", *pRefCnt ); - if( (*pRefCnt) == 0 ) - { - delete pRefCnt; - delete pData; - pRefCnt = NULL; - pData = NULL; - } - } - } - - int32_t *pRefCnt; - T *pData; -}; - -#endif diff --git a/src/serversocket.h b/src/serversocket.h index 9a26e2d..f146d91 100644 --- a/src/serversocket.h +++ b/src/serversocket.h @@ -2,13 +2,19 @@ #define SERVER_SOCKET_H #include -#include "fstring.h" -#include "socket.h" +#include "bu/fstring.h" namespace Bu { /** + * A single tcp/ip server socket. When created the server socket will bind + * to the specified interface and port, and immediately begin listening for + * connections. When connections come in they are pooled by the networking + * drivers in the kernel until they are accepted, this means that failure + * to keep space in the connection pool will result in connection refusals. * + * Although the accept function returns an integral file descriptor, it is + * designed to be used with the Socket class. */ class ServerSocket { diff --git a/src/sptr.cpp b/src/sptr.cpp new file mode 100644 index 0000000..8ea7f8f --- /dev/null +++ b/src/sptr.cpp @@ -0,0 +1 @@ +#include "bu/sptr.h" diff --git a/src/sptr.h b/src/sptr.h new file mode 100644 index 0000000..faa8524 --- /dev/null +++ b/src/sptr.h @@ -0,0 +1,147 @@ +#ifndef SPTR_H +#define SPTR_H + +#include +#include + +namespace Bu +{ + template class SPtr; + template< typename Tb, typename Ta > SPtr SPtrCast( SPtr src ); + + template + class SPtr + { + template + friend SPtr SPtrCast( SPtr pt ); + public: + SPtr() : + pRefCnt( NULL ), + pData( NULL ) + { + } + + ~SPtr() + { + decCount(); + } + + SPtr( const SPtr &src ) : + pRefCnt( src.pRefCnt ), + pData( src.pData ) + { + if( pRefCnt ) + (*pRefCnt) += 1; + } + + SPtr( T *pSrc ) : + pRefCnt( NULL ), + pData( pSrc ) + { + if( pData ) + { + pRefCnt = new int32_t; + (*pRefCnt) = 1; + } + } + + int32_t count() const + { + return *pRefCnt; + } + + const T *operator->() const + { + return pData; + } + + const T &operator*() const + { + return *pData; + } + + T *operator->() + { + return pData; + } + + T &operator*() + { + return *pData; + } + + SPtr operator=( const SPtr &src ) + { + decCount(); + pRefCnt = src.pRefCnt; + pData = src.pData; + if( pRefCnt ) + (*pRefCnt) += 1; + + return *this; + } + + const SPtr operator=( const SPtr &src ) const + { + decCount(); + pRefCnt = src.pRefCnt; + pData = src.pData; + if( pRefCnt ) + (*pRefCnt) += 1; + + return *this; + } + + bool operator==( const SPtr &src ) const + { + return pData == src.pData; + } + + bool operator==( const T *src ) const + { + return pData == src; + } + + operator bool() const + { + return pRefCnt != NULL; + } + + bool isSet() const + { + return pRefCnt != NULL; + } + + private: + void decCount() const + { + if( pRefCnt ) + { + (*pRefCnt) -= 1; + //printf("Decrementing ref-count to %d\n", *pRefCnt ); + if( (*pRefCnt) == 0 ) + { + delete pRefCnt; + delete pData; + pRefCnt = NULL; + pData = NULL; + } + } + } + + mutable int32_t *pRefCnt; + mutable T *pData; + }; + + template< typename Tb, typename Ta > SPtr SPtrCast( SPtr src ) + { + SPtr ret; + ret.pRefCnt = src.pRefCnt; + ret.pData = dynamic_cast(src.pData); + if( ret.pRefCnt ) + (*(ret.pRefCnt)) += 1; + return ret; + } +} + +#endif diff --git a/src/tests/list.cpp b/src/tests/list.cpp index 34ab656..12807a5 100644 --- a/src/tests/list.cpp +++ b/src/tests/list.cpp @@ -1,4 +1,10 @@ #include "bu/list.h" +#include + +typedef struct Bob +{ + int nID; +} Bob; int main() { @@ -16,7 +22,32 @@ int main() { printf("%d ", *i ); } + printf("\n"); + for( Bu::List::iterator i = l.begin(); i != l.end(); i++ ) + { + l.erase( i ); + if( i != l.end() ) + printf("%d ", *i ); + } + + printf("\n\n"); + Bu::List lb; + for( int j = 0; j < 10; j++ ) + { + Bob b; + b.nID = j; + lb.append( b ); + } + + const Bu::List rb = lb; + + for( Bu::List::const_iterator i = rb.begin(); i != rb.end(); i++ ) + { + //i->nID += 2; + //(*i).nID = 4; + printf("%d ", i->nID ); + } printf("\n\n"); } -- cgit v1.2.3