aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--bnftest18
-rw-r--r--bnftest.224
-rw-r--r--default.bld16
-rw-r--r--src/archive.cpp9
-rw-r--r--src/archive.h4
-rw-r--r--src/archivebase.h5
-rw-r--r--src/array.h29
-rw-r--r--src/cachestorefiles.h2
-rw-r--r--src/cachestoremyriad.h2
-rw-r--r--src/client.cpp9
-rw-r--r--src/client.h8
-rw-r--r--src/fastcgi.cpp22
-rw-r--r--src/fastcgi.h18
-rw-r--r--src/fbasicstring.h241
-rw-r--r--src/file.cpp1
-rw-r--r--src/hash.h1057
-rw-r--r--src/heap.h300
-rw-r--r--src/httpget.h4
-rw-r--r--src/itoserver.cpp12
-rw-r--r--src/itoserver.h6
-rw-r--r--src/lexer.h4
-rw-r--r--src/list.h29
-rw-r--r--src/listhash.cpp8
-rw-r--r--src/listhash.h54
-rw-r--r--src/myriad.h2
-rw-r--r--src/myriadfs.cpp78
-rw-r--r--src/myriadfs.h54
-rw-r--r--src/newline.h2
-rw-r--r--src/paramproc.cpp523
-rw-r--r--src/paramproc.h163
-rw-r--r--src/parser.cpp34
-rw-r--r--src/parser.h5
-rw-r--r--src/ringbuffer.h209
-rw-r--r--src/server.cpp14
-rw-r--r--src/server.h6
-rw-r--r--src/set.h760
-rw-r--r--src/sharedcore.h77
-rw-r--r--src/tcpserversocket.cpp (renamed from src/serversocket.cpp)36
-rw-r--r--src/tcpserversocket.h (renamed from src/serversocket.h)18
-rw-r--r--src/tcpsocket.cpp (renamed from src/socket.cpp)148
-rw-r--r--src/tcpsocket.h (renamed from src/socket.h)31
-rw-r--r--src/tests/sharedcore.cpp2
-rw-r--r--src/tests/socketblock.cpp10
-rw-r--r--src/tests/socketbreak.cpp10
-rw-r--r--src/tests/tcpsocket.cpp (renamed from src/tests/socket.cpp)4
-rw-r--r--src/tools/bnfcompile.cpp410
-rw-r--r--src/tools/myriadfs.cpp38
-rw-r--r--src/tools/parser.cpp89
-rw-r--r--src/unit/fstring.unit9
-rw-r--r--src/unit/hash.unit13
-rw-r--r--src/utfstring.cpp29
-rw-r--r--src/utfstring.h24
-rw-r--r--src/variant.h18
53 files changed, 2221 insertions, 2477 deletions
diff --git a/bnftest b/bnftest
new file mode 100644
index 0000000..7e61b1a
--- /dev/null
+++ b/bnftest
@@ -0,0 +1,18 @@
1tokens = tokPlus tokMinus tokMult tokDivide tokOpenParen tokCloseParen
2 tokEquals tokNumber;
3
4input: input line
5 |
6 ;
7
8line: expr tokEquals {print}
9 ;
10
11expr: expr tokPlus expr {add}
12 | expr tokMinus expr {subtract}
13 | expr tokMult expr {multiply}
14 | expr tokDivide expr {divide}
15 | tokOpenParen expr tokCloseParen
16 | [tokNumber]
17 ;
18
diff --git a/bnftest.2 b/bnftest.2
new file mode 100644
index 0000000..229943b
--- /dev/null
+++ b/bnftest.2
@@ -0,0 +1,24 @@
1tokens = tokPlus tokMinus tokMult tokDivide tokOpenParen tokCloseParen
2 tokEquals tokNumber;
3
4input: line input#
5 |
6 ;
7
8input#: line input#
9 |
10 ;
11
12line: expr tokEquals {print}
13 ;
14
15expr: tokOpenParen expr tokCloseParen expr#
16 | [tokNumber] expr#
17 ;
18
19expr#: tokPlus expr {add} expr#
20 | tokMinus expr {subtract} expr#
21 | tokMult expr {multiply} expr#
22 | tokDivide expr {divide} expr#
23 |
24 ;
diff --git a/default.bld b/default.bld
index 857e988..50baefb 100644
--- a/default.bld
+++ b/default.bld
@@ -82,6 +82,22 @@ target "viewcsv"
82} 82}
83 83
84// 84//
85// This shouldn't be. Basically, if you set a property on a top level target
86// that has children it seems like the items should apply to the children.
87// I'm honestly not 100% sure what the policy should be yet, but this seems like
88// I shouldn't have to do it this way.
89//
90target "src/tools/myriadfs.o"
91{
92 CXXFLAGS += "-D_FILE_OFFSET_BITS=64";
93}
94
95target "myriadfs"
96{
97 LDFLAGS += "-lfuse";
98}
99
100//
85// General Tests 101// General Tests
86// 102//
87 103
diff --git a/src/archive.cpp b/src/archive.cpp
index 69d4a0c..7a10921 100644
--- a/src/archive.cpp
+++ b/src/archive.cpp
@@ -22,20 +22,15 @@ Bu::Archive::~Archive()
22{ 22{
23} 23}
24 24
25void Bu::Archive::write( const void *pData, int32_t nSize ) 25void Bu::Archive::write( const void *pData, size_t nSize )
26{ 26{
27 if( nSize == 0 || pData == NULL ) 27 if( nSize == 0 || pData == NULL )
28 return; 28 return;
29 29
30// Bu::sio << "Writing starting at pos: " << rStream.tell() << " - "
31// << Bu::sio.flush;
32
33 rStream.write( (const char *)pData, nSize ); 30 rStream.write( (const char *)pData, nSize );
34//
35// Bu::sio << rStream.tell() << " (" << nSize << "b)" << Bu::sio.nl;
36} 31}
37 32
38void Bu::Archive::read( void *pData, int32_t nSize ) 33void Bu::Archive::read( void *pData, size_t nSize )
39{ 34{
40 if( nSize == 0 || pData == NULL ) 35 if( nSize == 0 || pData == NULL )
41 return; 36 return;
diff --git a/src/archive.h b/src/archive.h
index bd85113..9d2aee2 100644
--- a/src/archive.h
+++ b/src/archive.h
@@ -83,8 +83,8 @@ namespace Bu
83 virtual ~Archive(); 83 virtual ~Archive();
84 virtual void close(); 84 virtual void close();
85 85
86 virtual void write(const void *, int32_t); 86 virtual void write( const void *pData, size_t iSize );
87 virtual void read(void *, int32_t); 87 virtual void read( void *pData, size_t iSize );
88 88
89 /** 89 /**
90 * For storage, get an ID for the pointer to the object you're going to 90 * For storage, get an ID for the pointer to the object you're going to
diff --git a/src/archivebase.h b/src/archivebase.h
index c871bb5..18591f0 100644
--- a/src/archivebase.h
+++ b/src/archivebase.h
@@ -9,6 +9,7 @@
9#define BU_ARCHIVE_BASE_H 9#define BU_ARCHIVE_BASE_H
10 10
11#include <stdint.h> 11#include <stdint.h>
12#include <unistd.h>
12 13
13namespace Bu 14namespace Bu
14{ 15{
@@ -19,8 +20,8 @@ namespace Bu
19 virtual ~ArchiveBase(); 20 virtual ~ArchiveBase();
20 21
21 virtual void close()=0; 22 virtual void close()=0;
22 virtual void write( const void *pData, int32_t iLength )=0; 23 virtual void write( const void *pData, size_t iLength )=0;
23 virtual void read( void *pData, int32_t iLength )=0; 24 virtual void read( void *pData, size_t iLength )=0;
24 virtual bool isLoading()=0; 25 virtual bool isLoading()=0;
25 }; 26 };
26 27
diff --git a/src/array.h b/src/array.h
index eeee677..f225c97 100644
--- a/src/array.h
+++ b/src/array.h
@@ -18,9 +18,18 @@ namespace Bu
18 subExceptionDecl( ArrayException ) 18 subExceptionDecl( ArrayException )
19 19
20 template<typename value, int inc, typename valuealloc> 20 template<typename value, int inc, typename valuealloc>
21 class Array;
22
23 /** @cond DEVEL */
24 template<typename value, int inc, typename valuealloc>
21 class ArrayCore 25 class ArrayCore
22 { 26 {
23 public: 27 friend class Array<value, inc, valuealloc>;
28 friend class SharedCore<
29 Array<value, inc, valuealloc>,
30 ArrayCore<value, inc, valuealloc>
31 >;
32 private:
24 ArrayCore() : 33 ArrayCore() :
25 pData( NULL ), 34 pData( NULL ),
26 iSize( 0 ), 35 iSize( 0 ),
@@ -99,6 +108,7 @@ namespace Bu
99 long iSize; 108 long iSize;
100 long iCapacity; 109 long iCapacity;
101 }; 110 };
111 /** @endcond */
102 112
103 /** 113 /**
104 * Array type container, just like a normal array only flexible and keeps 114 * Array type container, just like a normal array only flexible and keeps
@@ -110,16 +120,20 @@ namespace Bu
110 *@ingroup Containers 120 *@ingroup Containers
111 */ 121 */
112 template<typename value, int inc=10, typename valuealloc=std::allocator<value> > 122 template<typename value, int inc=10, typename valuealloc=std::allocator<value> >
113 class Array : public SharedCore<ArrayCore<value, inc, valuealloc> > 123 class Array : public SharedCore<
124 Array<value, inc, valuealloc>,
125 ArrayCore<value, inc, valuealloc>
126 >
114 { 127 {
115 private: 128 private:
116 typedef class Array<value, inc, valuealloc> MyType; 129 typedef class Array<value, inc, valuealloc> MyType;
117 typedef class ArrayCore<value, inc, valuealloc> Core; 130 typedef class ArrayCore<value, inc, valuealloc> Core;
118 131
119 protected: 132 protected:
120 using SharedCore< Core >::core; 133 using SharedCore<MyType, Core>::core;
121 using SharedCore< Core >::_hardCopy; 134 using SharedCore<MyType, Core>::_hardCopy;
122 using SharedCore< Core >::_allocateCore; 135 using SharedCore<MyType, Core>::_resetCore;
136 using SharedCore<MyType, Core>::_allocateCore;
123 137
124 public: 138 public:
125 struct const_iterator; 139 struct const_iterator;
@@ -130,7 +144,7 @@ namespace Bu
130 } 144 }
131 145
132 Array( const MyType &src ) : 146 Array( const MyType &src ) :
133 SharedCore< Core >( src ) 147 SharedCore<MyType, Core >( src )
134 { 148 {
135 } 149 }
136 150
@@ -168,8 +182,7 @@ namespace Bu
168 */ 182 */
169 void clear() 183 void clear()
170 { 184 {
171 _hardCopy(); 185 _resetCore();
172 core->clear();
173 } 186 }
174 187
175 MyType &append( const value &rVal ) 188 MyType &append( const value &rVal )
diff --git a/src/cachestorefiles.h b/src/cachestorefiles.h
index 1906b13..c2cf091 100644
--- a/src/cachestorefiles.h
+++ b/src/cachestorefiles.h
@@ -83,7 +83,7 @@ namespace Bu
83 } 83 }
84 } 84 }
85 85
86 virtual void unload( obtype *pObj, const keytype &key ) 86 virtual void unload( obtype *pObj, const keytype & )
87 { 87 {
88 delete pObj; 88 delete pObj;
89 } 89 }
diff --git a/src/cachestoremyriad.h b/src/cachestoremyriad.h
index b90793d..21c84e6 100644
--- a/src/cachestoremyriad.h
+++ b/src/cachestoremyriad.h
@@ -85,7 +85,7 @@ namespace Bu
85 return pOb; 85 return pOb;
86 } 86 }
87 87
88 virtual void unload( obtype *pObj, const keytype &key ) 88 virtual void unload( obtype *pObj, const keytype & )
89 { 89 {
90 delete pObj; 90 delete pObj;
91 } 91 }
diff --git a/src/client.cpp b/src/client.cpp
index becd1bd..b635c8b 100644
--- a/src/client.cpp
+++ b/src/client.cpp
@@ -6,7 +6,7 @@
6 */ 6 */
7 7
8#include "bu/client.h" 8#include "bu/client.h"
9#include "bu/socket.h" 9#include "bu/tcpsocket.h"
10#include <stdlib.h> 10#include <stdlib.h>
11#include <errno.h> 11#include <errno.h>
12#include "bu/protocol.h" 12#include "bu/protocol.h"
@@ -16,7 +16,8 @@
16/** Read buffer size. */ 16/** Read buffer size. */
17#define RBS (1024*2) 17#define RBS (1024*2)
18 18
19Bu::Client::Client( Bu::Socket *pSocket, class Bu::ClientLinkFactory *pfLink ) : 19Bu::Client::Client( Bu::TcpSocket *pSocket,
20 class Bu::ClientLinkFactory *pfLink ) :
20 pTopStream( pSocket ), 21 pTopStream( pSocket ),
21 pSocket( pSocket ), 22 pSocket( pSocket ),
22 pProto( NULL ), 23 pProto( NULL ),
@@ -59,7 +60,7 @@ void Bu::Client::processInput()
59 break; 60 break;
60 } 61 }
61 } 62 }
62 catch( Bu::SocketException &e ) 63 catch( Bu::TcpSocketException &e )
63 { 64 {
64 pTopStream->close(); 65 pTopStream->close();
65 bWantsDisconnect = true; 66 bWantsDisconnect = true;
@@ -195,7 +196,7 @@ long Bu::Client::getOutputSize()
195 return qbWrite.getSize(); 196 return qbWrite.getSize();
196} 197}
197 198
198const Bu::Socket *Bu::Client::getSocket() const 199const Bu::TcpSocket *Bu::Client::getSocket() const
199{ 200{
200 return pSocket; 201 return pSocket;
201} 202}
diff --git a/src/client.h b/src/client.h
index f336524..096df2f 100644
--- a/src/client.h
+++ b/src/client.h
@@ -17,7 +17,7 @@ namespace Bu
17{ 17{
18 class Protocol; 18 class Protocol;
19 class Stream; 19 class Stream;
20 class Socket; 20 class TcpSocket;
21 class ClientLinkFactory; 21 class ClientLinkFactory;
22 22
23 /** 23 /**
@@ -26,7 +26,7 @@ namespace Bu
26 class Client : public Bu::Stream 26 class Client : public Bu::Stream
27 { 27 {
28 public: 28 public:
29 Client( Bu::Socket *pSocket, Bu::ClientLinkFactory *pfLink ); 29 Client( Bu::TcpSocket *pSocket, Bu::ClientLinkFactory *pfLink );
30 virtual ~Client(); 30 virtual ~Client();
31 31
32 void processInput(); 32 void processInput();
@@ -58,7 +58,7 @@ namespace Bu
58 void close(); 58 void close();
59 void tick(); 59 void tick();
60 60
61 const Bu::Socket *getSocket() const; 61 const Bu::TcpSocket *getSocket() const;
62 62
63 void disconnect(); 63 void disconnect();
64 bool wantsDisconnect(); 64 bool wantsDisconnect();
@@ -117,7 +117,7 @@ namespace Bu
117 typedef Bu::List<Bu::Stream *> FilterList; 117 typedef Bu::List<Bu::Stream *> FilterList;
118 FilterList lFilts; 118 FilterList lFilts;
119 Bu::Stream *pTopStream; 119 Bu::Stream *pTopStream;
120 Bu::Socket *pSocket; 120 Bu::TcpSocket *pSocket;
121 Bu::Protocol *pProto; 121 Bu::Protocol *pProto;
122 Bu::QueueBuf qbRead; 122 Bu::QueueBuf qbRead;
123 Bu::QueueBuf qbWrite; 123 Bu::QueueBuf qbWrite;
diff --git a/src/fastcgi.cpp b/src/fastcgi.cpp
index 8168928..ca3010e 100644
--- a/src/fastcgi.cpp
+++ b/src/fastcgi.cpp
@@ -24,14 +24,14 @@ Bu::FastCgi::FastCgi() :
24 pSrv( NULL ), 24 pSrv( NULL ),
25 bRunning( true ) 25 bRunning( true )
26{ 26{
27 pSrv = new Bu::ServerSocket( STDIN_FILENO, false ); 27 pSrv = new Bu::TcpServerSocket( STDIN_FILENO, false );
28} 28}
29 29
30Bu::FastCgi::FastCgi( int iPort ) : 30Bu::FastCgi::FastCgi( int iPort ) :
31 pSrv( NULL ), 31 pSrv( NULL ),
32 bRunning( true ) 32 bRunning( true )
33{ 33{
34 pSrv = new Bu::ServerSocket( iPort ); 34 pSrv = new Bu::TcpServerSocket( iPort );
35} 35}
36 36
37Bu::FastCgi::~FastCgi() 37Bu::FastCgi::~FastCgi()
@@ -64,17 +64,17 @@ bool Bu::FastCgi::isEmbedded()
64#endif 64#endif
65} 65}
66 66
67void Bu::FastCgi::read( Bu::Socket &s, Bu::FastCgi::Record &r ) 67void Bu::FastCgi::read( Bu::TcpSocket &s, Bu::FastCgi::Record &r )
68{ 68{
69 int iRead = s.read( &r, sizeof(Record) ); 69 int iRead = s.read( &r, sizeof(Record) );
70 if( iRead != sizeof(Record) ) 70 if( iRead != sizeof(Record) )
71 throw Bu::SocketException("Hey, the size %d is wrong for Record. (%s)", 71 throw Bu::TcpSocketException("Hey, the size %d is wrong for Record. (%s)",
72 iRead, strerror( errno ) ); 72 iRead, strerror( errno ) );
73 r.uRequestId = ntohs( r.uRequestId ); 73 r.uRequestId = ntohs( r.uRequestId );
74 r.uContentLength = ntohs( r.uContentLength ); 74 r.uContentLength = ntohs( r.uContentLength );
75} 75}
76 76
77void Bu::FastCgi::write( Bu::Socket &s, Bu::FastCgi::Record r ) 77void Bu::FastCgi::write( Bu::TcpSocket &s, Bu::FastCgi::Record r )
78{ 78{
79// sio << "Out -> " << r << sio.nl; 79// sio << "Out -> " << r << sio.nl;
80 r.uRequestId = htons( r.uRequestId ); 80 r.uRequestId = htons( r.uRequestId );
@@ -82,19 +82,19 @@ void Bu::FastCgi::write( Bu::Socket &s, Bu::FastCgi::Record r )
82 s.write( &r, sizeof(Record) ); 82 s.write( &r, sizeof(Record) );
83} 83}
84 84
85void Bu::FastCgi::read( Bu::Socket &s, Bu::FastCgi::BeginRequestBody &b ) 85void Bu::FastCgi::read( Bu::TcpSocket &s, Bu::FastCgi::BeginRequestBody &b )
86{ 86{
87 s.read( &b, sizeof(BeginRequestBody) ); 87 s.read( &b, sizeof(BeginRequestBody) );
88 b.uRole = ntohs( b.uRole ); 88 b.uRole = ntohs( b.uRole );
89} 89}
90 90
91void Bu::FastCgi::write( Bu::Socket &s, Bu::FastCgi::EndRequestBody b ) 91void Bu::FastCgi::write( Bu::TcpSocket &s, Bu::FastCgi::EndRequestBody b )
92{ 92{
93 b.uStatus = htonl( b.uStatus ); 93 b.uStatus = htonl( b.uStatus );
94 s.write( &b, sizeof(b) ); 94 s.write( &b, sizeof(b) );
95} 95}
96 96
97uint32_t Bu::FastCgi::readLen( Bu::Socket &s, uint16_t &uRead ) 97uint32_t Bu::FastCgi::readLen( Bu::TcpSocket &s, uint16_t &uRead )
98{ 98{
99 uint8_t uByte[4]; 99 uint8_t uByte[4];
100 s.read( uByte, 1 ); 100 s.read( uByte, 1 );
@@ -107,7 +107,7 @@ uint32_t Bu::FastCgi::readLen( Bu::Socket &s, uint16_t &uRead )
107 return ((uByte[0]&0x7f)<<24)|(uByte[1]<<16)|(uByte[2]<<8)|(uByte[3]); 107 return ((uByte[0]&0x7f)<<24)|(uByte[1]<<16)|(uByte[2]<<8)|(uByte[3]);
108} 108}
109 109
110void Bu::FastCgi::readPair( Bu::Socket &s, StrHash &hParams, uint16_t &uRead ) 110void Bu::FastCgi::readPair( Bu::TcpSocket &s, StrHash &hParams, uint16_t &uRead )
111{ 111{
112 uint32_t uName = readLen( s, uRead ); 112 uint32_t uName = readLen( s, uRead );
113 uint32_t uValue = readLen( s, uRead ); 113 uint32_t uValue = readLen( s, uRead );
@@ -162,7 +162,7 @@ void Bu::FastCgi::run()
162 if( iSock < 0 ) 162 if( iSock < 0 )
163 continue; 163 continue;
164 164
165 Bu::Socket s( iSock ); 165 Bu::TcpSocket s( iSock );
166 s.setBlocking( true ); 166 s.setBlocking( true );
167// sio << "Got connection, blocking? " << s.isBlocking() << sio.nl; 167// sio << "Got connection, blocking? " << s.isBlocking() << sio.nl;
168 try 168 try
@@ -362,7 +362,7 @@ void Bu::FastCgi::run()
362 } 362 }
363 } 363 }
364 } 364 }
365 catch( Bu::SocketException &e ) 365 catch( Bu::TcpSocketException &e )
366 { 366 {
367// sio << "Bu::SocketException: " << e.what() << sio.nl << 367// sio << "Bu::SocketException: " << e.what() << sio.nl <<
368// "\tSocket open: " << s.isOpen() << sio.nl; 368// "\tSocket open: " << s.isOpen() << sio.nl;
diff --git a/src/fastcgi.h b/src/fastcgi.h
index 262872c..7c1c04c 100644
--- a/src/fastcgi.h
+++ b/src/fastcgi.h
@@ -11,8 +11,8 @@
11#include "bu/fstring.h" 11#include "bu/fstring.h"
12#include "bu/hash.h" 12#include "bu/hash.h"
13#include "bu/array.h" 13#include "bu/array.h"
14#include "bu/socket.h" 14#include "bu/tcpsocket.h"
15#include "bu/serversocket.h" 15#include "bu/tcpserversocket.h"
16 16
17namespace Bu 17namespace Bu
18{ 18{
@@ -109,18 +109,18 @@ namespace Bu
109 virtual void onUninit() { }; 109 virtual void onUninit() { };
110 110
111 private: 111 private:
112 void read( Bu::Socket &s, Record &r ); 112 void read( Bu::TcpSocket &s, Record &r );
113 void read( Bu::Socket &s, BeginRequestBody &b ); 113 void read( Bu::TcpSocket &s, BeginRequestBody &b );
114 uint32_t readLen( Bu::Socket &s, uint16_t &uUsed ); 114 uint32_t readLen( Bu::TcpSocket &s, uint16_t &uUsed );
115 void readPair( Bu::Socket &s, StrHash &hParams, uint16_t &uUsed ); 115 void readPair( Bu::TcpSocket &s, StrHash &hParams, uint16_t &uUsed );
116 116
117 void write( Bu::Socket &s, Record r ); 117 void write( Bu::TcpSocket &s, Record r );
118 void write( Bu::Socket &s, EndRequestBody b ); 118 void write( Bu::TcpSocket &s, EndRequestBody b );
119 119
120 bool hasChannel( int iChan ); 120 bool hasChannel( int iChan );
121 121
122 private: 122 private:
123 Bu::ServerSocket *pSrv; 123 Bu::TcpServerSocket *pSrv;
124 bool bRunning; 124 bool bRunning;
125 Bu::Array<Channel *> aChannel; 125 Bu::Array<Channel *> aChannel;
126 }; 126 };
diff --git a/src/fbasicstring.h b/src/fbasicstring.h
index 4c33479..064ff16 100644
--- a/src/fbasicstring.h
+++ b/src/fbasicstring.h
@@ -25,6 +25,7 @@
25 25
26namespace Bu 26namespace Bu
27{ 27{
28 /** @cond DEVEL */
28 template< typename chr > 29 template< typename chr >
29 struct FStringChunk 30 struct FStringChunk
30 { 31 {
@@ -34,10 +35,55 @@ namespace Bu
34 }; 35 };
35 36
36#define cpy( dest, src, size ) Bu::memcpy( dest, src, size*sizeof(chr) ) 37#define cpy( dest, src, size ) Bu::memcpy( dest, src, size*sizeof(chr) )
38
39 template< typename chr, int nMinSize, typename chralloc,
40 typename chunkalloc> class FBasicString;
41
42 template<typename chr>
43 size_t strlen( const chr *pData )
44 {
45 for( size_t tLen = 0;; ++tLen )
46 {
47 if( pData[tLen] == (chr)0 )
48 return tLen;
49 }
50 return -1;
51 }
52
53 template<char>
54 size_t strlen( const char *pData )
55 {
56 return ::strlen( pData );
57 }
58
59 template<typename chr>
60 int strncmp( const chr *a, const chr *b, size_t iLen )
61 {
62 for( size_t iPos = 0; iPos < iLen; iPos++ )
63 {
64 if( a[iPos] != b[iPos] )
65 {
66 return a[iPos]-b[iPos];
67 }
68 }
69 return 0;
70 }
71
72 template<char>
73 int strncmp( const char *a, const char *b, size_t iLen )
74 {
75 return ::strncmp( a, b, iLen );
76 }
37 77
38 template<typename chr, int nMinSize, typename chralloc, typename chunkalloc> 78 template<typename chr, int nMinSize, typename chralloc, typename chunkalloc>
39 struct FStringCore 79 struct FStringCore
40 { 80 {
81 friend class FBasicString<chr, nMinSize, chralloc, chunkalloc>;
82 friend class SharedCore<
83 FBasicString<chr, nMinSize, chralloc, chunkalloc>,
84 FStringCore<chr, nMinSize, chralloc, chunkalloc>
85 >;
86 private:
41 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> MyType; 87 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> MyType;
42 typedef struct FStringChunk<chr> Chunk; 88 typedef struct FStringChunk<chr> Chunk;
43 FStringCore() : 89 FStringCore() :
@@ -157,6 +203,7 @@ namespace Bu
157 nLength += pNewChunk->nLength; 203 nLength += pNewChunk->nLength;
158 } 204 }
159 }; 205 };
206 /** @endcond */
160 207
161 /** 208 /**
162 * Flexible String class. This class was designed with string passing and 209 * Flexible String class. This class was designed with string passing and
@@ -174,55 +221,24 @@ namespace Bu
174 *@param chralloc (typename) Memory Allocator for chr 221 *@param chralloc (typename) Memory Allocator for chr
175 *@param chunkalloc (typename) Memory Allocator for chr chunks 222 *@param chunkalloc (typename) Memory Allocator for chr chunks
176 */ 223 */
177 template< typename chr, int nMinSize=256, typename chralloc=std::allocator<chr>, typename chunkalloc=std::allocator<struct FStringChunk<chr> > > 224 template< typename chr, int nMinSize=256,
178 class FBasicString : public SharedCore< FStringCore<chr, nMinSize, chralloc, chunkalloc> > 225 typename chralloc=std::allocator<chr>,
226 typename chunkalloc=std::allocator<struct FStringChunk<chr> > >
227 class FBasicString : public SharedCore<
228 FBasicString<chr, nMinSize, chralloc, chunkalloc>,
229 FStringCore<chr, nMinSize, chralloc, chunkalloc> >
179 { 230 {
180 protected: 231 protected:
181 typedef struct FStringChunk<chr> Chunk; 232 typedef struct FStringChunk<chr> Chunk;
182 typedef struct FBasicString<chr, nMinSize, chralloc, chunkalloc> MyType; 233 typedef struct FBasicString<chr, nMinSize, chralloc, chunkalloc> MyType;
183 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> Core; 234 typedef struct FStringCore<chr, nMinSize, chralloc, chunkalloc> Core;
184 235
185 using SharedCore< Core >::core; 236 using SharedCore<MyType, Core >::core;
186 using SharedCore< Core >::_hardCopy; 237 using SharedCore<MyType, Core >::_hardCopy;
187
188 public:
189 FBasicString()
190 {
191 }
192
193 FBasicString( const chr *pData )
194 {
195 append( pData );
196 }
197
198 FBasicString( const chr *pData, long nLength )
199 {
200 append( pData, nLength );
201 }
202 238
203 FBasicString( const MyType &rSrc ) : 239 public: // Iterators
204 SharedCore<Core>( rSrc )
205 {
206 }
207
208 FBasicString( const MyType &rSrc, long nLength )
209 {
210 append( rSrc, nLength );
211 }
212
213 FBasicString( const MyType &rSrc, long nStart, long nLength )
214 {
215 append( rSrc, nStart, nLength );
216 }
217
218 FBasicString( long nSize )
219 {
220 core->pFirst = core->pLast = core->newChunk( nSize );
221 core->nLength = nSize;
222 }
223
224 struct iterator; 240 struct iterator;
225 struct const_iterator 241 typedef struct const_iterator
226 { 242 {
227 friend class FBasicString<chr, nMinSize, chralloc, chunkalloc>; 243 friend class FBasicString<chr, nMinSize, chralloc, chunkalloc>;
228 friend struct iterator; 244 friend struct iterator;
@@ -243,7 +259,7 @@ namespace Bu
243 { 259 {
244 } 260 }
245 261
246 const_iterator( const iterator &i ) : 262 const_iterator( const struct iterator &i ) :
247 pChunk( i.pChunk ), 263 pChunk( i.pChunk ),
248 iPos( i.iPos ) 264 iPos( i.iPos )
249 { 265 {
@@ -454,7 +470,7 @@ namespace Bu
454 } 470 }
455 return const_iterator( NULL, 0 ); 471 return const_iterator( NULL, 0 );
456 } 472 }
457 }; 473 } const_iterator;
458 474
459 typedef struct iterator 475 typedef struct iterator
460 { 476 {
@@ -702,11 +718,41 @@ namespace Bu
702 } 718 }
703 } iterator; 719 } iterator;
704 720
705 typedef struct const_iterator const_iterator; 721 public:
722 FBasicString()
723 {
724 }
725
726 FBasicString( const chr *pData )
727 {
728 append( pData );
729 }
730
731 FBasicString( const chr *pData, long nLength )
732 {
733 append( pData, nLength );
734 }
735
736 FBasicString( const MyType &rSrc ) :
737 SharedCore<MyType, Core>( rSrc )
738 {
739 }
706 740
707 //typedef chr *iterator; 741 FBasicString( const MyType &rSrc, long nLength )
708// typedef const chr *const_iterator; 742 {
709 // typedef iterator const_iterator; 743 append( rSrc, nLength );
744 }
745
746 FBasicString( const MyType &rSrc, long nStart, long nLength )
747 {
748 append( rSrc, nStart, nLength );
749 }
750
751 FBasicString( long nSize )
752 {
753 core->pFirst = core->pLast = core->newChunk( nSize );
754 core->nLength = nSize;
755 }
710 756
711 FBasicString( const const_iterator &s ) 757 FBasicString( const const_iterator &s )
712 { 758 {
@@ -731,14 +777,8 @@ namespace Bu
731 if( !pData ) return; 777 if( !pData ) return;
732 long nLen; 778 long nLen;
733 for( nLen = 0; pData[nLen] != (chr)0; nLen++ ) { } 779 for( nLen = 0; pData[nLen] != (chr)0; nLen++ ) { }
734 if( nLen == 0 )
735 return;
736
737 Chunk *pNew = core->newChunk( nLen );
738 cpy( pNew->pData, pData, nLen );
739 780
740 _hardCopy(); 781 append( pData, 0, nLen );
741 core->appendChunk( pNew );
742 } 782 }
743 783
744 /** 784 /**
@@ -748,15 +788,7 @@ namespace Bu
748 */ 788 */
749 void append( const chr *pData, long nLen ) 789 void append( const chr *pData, long nLen )
750 { 790 {
751 if( nLen == 0 ) 791 append( pData, 0, nLen );
752 return;
753
754 Chunk *pNew = core->newChunk( nLen );
755
756 cpy( pNew->pData, pData, nLen );
757
758 _hardCopy();
759 core->appendChunk( pNew );
760 } 792 }
761 793
762 /** 794 /**
@@ -767,15 +799,37 @@ namespace Bu
767 */ 799 */
768 void append( const chr *pData, long nStart, long nLen ) 800 void append( const chr *pData, long nStart, long nLen )
769 { 801 {
770 if( nLen == 0 ) 802 if( !pData ) return;
803 if( nLen <= 0 )
771 return; 804 return;
772 805
773 Chunk *pNew = core->newChunk( nLen ); 806 pData += nStart;
774
775 cpy( pNew->pData, pData+nStart, nLen );
776 807
777 _hardCopy(); 808 _hardCopy();
778 core->appendChunk( pNew ); 809
810 if( core->pLast && core->pLast->nLength < nMinSize )
811 {
812 int nAmnt = nMinSize - core->pLast->nLength;
813 if( nAmnt > nLen )
814 nAmnt = nLen;
815 cpy(
816 core->pLast->pData+core->pLast->nLength,
817 pData,
818 nAmnt
819 );
820 pData += nAmnt;
821 core->pLast->nLength += nAmnt;
822 nLen -= nAmnt;
823 core->nLength += nAmnt;
824 }
825
826 if( nLen > 0 )
827 {
828 Chunk *pNew = core->newChunk( nLen );
829 cpy( pNew->pData, pData, nLen );
830 core->appendChunk( pNew );
831// core->nLength += nLen;
832 }
779 } 833 }
780 834
781 /** 835 /**
@@ -804,7 +858,7 @@ namespace Bu
804 */ 858 */
805 void append( const MyType & sData ) 859 void append( const MyType & sData )
806 { 860 {
807 append( sData.getStr(), sData.getSize() ); 861 append( sData.getStr(), 0, sData.getSize() );
808 } 862 }
809 863
810 /** 864 /**
@@ -815,7 +869,7 @@ namespace Bu
815 */ 869 */
816 void append( const MyType & sData, long nLen ) 870 void append( const MyType & sData, long nLen )
817 { 871 {
818 append( sData.getStr(), nLen ); 872 append( sData.getStr(), 0, nLen );
819 } 873 }
820 874
821 /** 875 /**
@@ -1029,7 +1083,7 @@ namespace Bu
1029 */ 1083 */
1030 void insert( long nPos, const chr *pData ) 1084 void insert( long nPos, const chr *pData )
1031 { 1085 {
1032 insert( nPos, pData, strlen( pData ) ); 1086 insert( nPos, pData, Bu::strlen( pData ) );
1033 } 1087 }
1034 1088
1035 void remove( long nPos, long nLen ) 1089 void remove( long nPos, long nLen )
@@ -1155,13 +1209,13 @@ namespace Bu
1155 if( iStart < 0 ) 1209 if( iStart < 0 )
1156 iStart = 0; 1210 iStart = 0;
1157 if( iStart >= core->nLength ) 1211 if( iStart >= core->nLength )
1158 return ""; 1212 return (const chr[]){(chr)0};
1159 if( iSize < 0 ) 1213 if( iSize < 0 )
1160 iSize = core->nLength; 1214 iSize = core->nLength;
1161 if( iStart+iSize > core->nLength ) 1215 if( iStart+iSize > core->nLength )
1162 iSize = core->nLength-iStart; 1216 iSize = core->nLength-iStart;
1163 if( iSize == 0 ) 1217 if( iSize == 0 )
1164 return ""; 1218 return (const chr[]){(chr)0};
1165 1219
1166 flatten(); 1220 flatten();
1167 MyType ret( core->pFirst->pData+iStart, iSize ); 1221 MyType ret( core->pFirst->pData+iStart, iSize );
@@ -1212,37 +1266,6 @@ namespace Bu
1212 } 1266 }
1213 } 1267 }
1214 1268
1215 /**
1216 * (std::string compatability) Get a pointer to the string array.
1217 *@returns (chr *) The string data.
1218 */
1219 DEPRECATED
1220 chr *c_str()
1221 {
1222 if( core->pFirst == NULL || core->nLength == 0 )
1223 return NULL;
1224
1225 flatten();
1226 _hardCopy();
1227 core->pFirst->pData[core->nLength] = (chr)0;
1228 return core->pFirst->pData;
1229 }
1230
1231 /**
1232 * (std::string compatability) Get a const pointer to the string array.
1233 *@returns (const chr *) The string data.
1234 */
1235 DEPRECATED
1236 const chr *c_str() const
1237 {
1238 if( core->pFirst == NULL || core->nLength == 0 )
1239 return NULL;
1240
1241 flatten();
1242 core->pFirst->pData[core->nLength] = (chr)0;
1243 return core->pFirst->pData;
1244 }
1245
1246 Bu::List<MyType> split( const chr c ) const 1269 Bu::List<MyType> split( const chr c ) const
1247 { 1270 {
1248 Bu::List<MyType> ret; 1271 Bu::List<MyType> ret;
@@ -1423,11 +1446,11 @@ namespace Bu
1423 wordexp_t result; 1446 wordexp_t result;
1424 1447
1425 /* Expand the string for the program to run. */ 1448 /* Expand the string for the program to run. */
1426 switch (wordexp (core->pFirst->pData, &result, 0)) 1449 switch (wordexp ((char *)core->pFirst->pData, &result, 0))
1427 { 1450 {
1428 case 0: /* Successful. */ 1451 case 0: /* Successful. */
1429 { 1452 {
1430 set( result.we_wordv[0] ); 1453 set( (chr *)result.we_wordv[0] );
1431 wordfree( &result ); 1454 wordfree( &result );
1432 return; 1455 return;
1433 } 1456 }
@@ -1941,7 +1964,7 @@ namespace Bu
1941 long iLen = vsnprintf( NULL, 0, sFrmt, ap ); 1964 long iLen = vsnprintf( NULL, 0, sFrmt, ap );
1942 1965
1943 Chunk *pNew = core->newChunk( iLen ); 1966 Chunk *pNew = core->newChunk( iLen );
1944 vsnprintf( pNew->pData, iLen+1, sFrmt, ap ); 1967 vsnprintf( (char *)pNew->pData, iLen+1, sFrmt, ap );
1945 core->appendChunk( pNew ); 1968 core->appendChunk( pNew );
1946 1969
1947 va_end( ap ); 1970 va_end( ap );
@@ -1958,7 +1981,7 @@ namespace Bu
1958 long iLen = vsnprintf( NULL, 0, sFrmt, ap ); 1981 long iLen = vsnprintf( NULL, 0, sFrmt, ap );
1959 1982
1960 Chunk *pNew = core->newChunk( iLen ); 1983 Chunk *pNew = core->newChunk( iLen );
1961 vsnprintf( pNew->pData, iLen+1, sFrmt, ap ); 1984 vsnprintf( (char *)pNew->pData, iLen+1, sFrmt, ap );
1962 core->appendChunk( pNew ); 1985 core->appendChunk( pNew );
1963 1986
1964 va_end( ap ); 1987 va_end( ap );
@@ -1975,7 +1998,7 @@ namespace Bu
1975 long iLen = vsnprintf( NULL, 0, sFrmt, ap ); 1998 long iLen = vsnprintf( NULL, 0, sFrmt, ap );
1976 1999
1977 Chunk *pNew = core->newChunk( iLen ); 2000 Chunk *pNew = core->newChunk( iLen );
1978 vsnprintf( pNew->pData, iLen+1, sFrmt, ap ); 2001 vsnprintf( (char *)pNew->pData, iLen+1, sFrmt, ap );
1979 core->prependChunk( pNew ); 2002 core->prependChunk( pNew );
1980 2003
1981 va_end( ap ); 2004 va_end( ap );
diff --git a/src/file.cpp b/src/file.cpp
index 0566ee8..008b88e 100644
--- a/src/file.cpp
+++ b/src/file.cpp
@@ -11,7 +11,6 @@
11#include <sys/stat.h> 11#include <sys/stat.h>
12#include <fcntl.h> 12#include <fcntl.h>
13#include <unistd.h> 13#include <unistd.h>
14#include <stdlib.h> // for mkstemp
15#include <time.h> 14#include <time.h>
16 15
17#include "bu/config.h" 16#include "bu/config.h"
diff --git a/src/hash.h b/src/hash.h
index 1cb539b..354569e 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -12,7 +12,8 @@
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/list.h" 13#include "bu/list.h"
14#include "bu/util.h" 14#include "bu/util.h"
15#include "archivebase.h" 15#include "bu/archivebase.h"
16#include "bu/sharedcore.h"
16 17
17#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0)) 18#define bitsToBytes( n ) (n/32+(n%32>0 ? 1 : 0))
18 19
@@ -49,138 +50,357 @@ namespace Bu
49 } 50 }
50 }; 51 };
51 52
52 template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<value>, typename challoc = std::allocator<uint32_t> > 53 template<typename key, typename value, typename sizecalc, typename keyalloc,
54 typename valuealloc, typename challoc>
53 class Hash; 55 class Hash;
54 56
55 template< typename key, typename _value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<_value>, typename challoc = std::allocator<uint32_t> > 57 /** @cond DEVEL */
56 struct HashProxy 58 template<typename key, typename value, typename sizecalc, typename keyalloc,
59 typename valuealloc, typename challoc >
60 class HashCore
57 { 61 {
58 friend class Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc>; 62 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
63 friend class SharedCore<
64 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
65 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
66 >;
59 private: 67 private:
60 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, const key *k, uint32_t nPos, uint32_t hash ) : 68 HashCore() :
61 hsh( h ), 69 nCapacity( 0 ),
62 pKey( k ), 70 nFilled( 0 ),
63 nPos( nPos ), 71 nDeleted( 0 ),
64 hash( hash ), 72 bFilled( NULL ),
65 bFilled( false ) 73 bDeleted( NULL ),
74 aKeys( NULL ),
75 aValues( NULL ),
76 aHashCodes( NULL )
66 { 77 {
67 } 78 }
68 79
69 HashProxy( Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &h, uint32_t nPos, _value *pValue ) : 80 virtual ~HashCore()
70 hsh( h ),
71 nPos( nPos ),
72 pValue( pValue ),
73 bFilled( true )
74 { 81 {
82 clear();
75 } 83 }
76 84
77 Hash<key, _value, sizecalc, keyalloc, valuealloc, challoc> &hsh; 85 void init()
78 const key *pKey; 86 {
79 uint32_t nPos; 87 if( nCapacity > 0 )
80 _value *pValue; 88 return;
81 uint32_t hash;
82 bool bFilled;
83 89
84 public: 90 nCapacity = 11;
85 /** 91 nKeysSize = bitsToBytes( nCapacity );
86 * Cast operator for HashProxy. 92 bFilled = ca.allocate( nKeysSize );
87 *@returns (value_type &) The value the HashProxy is pointing to. 93 bDeleted = ca.allocate( nKeysSize );
88 */ 94 clearBits();
89 operator _value &() 95
96 aHashCodes = ca.allocate( nCapacity );
97 aKeys = ka.allocate( nCapacity );
98 aValues = va.allocate( nCapacity );
99 }
100
101 void clearBits()
90 { 102 {
91 if( bFilled == false ) 103 if( nCapacity == 0 )
92 throw HashException( 104 return;
93 excodeNotFilled, 105
94 "No data assosiated with that key." 106 for( uint32_t j = 0; j < nKeysSize; j++ )
95 ); 107 {
96 return *pValue; 108 bFilled[j] = bDeleted[j] = 0;
109 }
97 } 110 }
98 111
99 /** 112 void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
100 * Direct function for retrieving a value out of the HashProxy.
101 *@returns (value_type &) The value pointed to by this HashProxy.
102 */
103 DEPRECATED
104 _value &value()
105 { 113 {
106 if( bFilled == false ) 114 init();
107 throw HashException( 115
108 excodeNotFilled, 116 bFilled[loc/32] |= (1<<(loc%32));
109 "No data assosiated with that key." 117 va.construct( &aValues[loc], v );
110 ); 118 ka.construct( &aKeys[loc], k );
111 return *pValue; 119 aHashCodes[loc] = hash;
120 nFilled++;
121 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
122 // nFilled, nDeleted, nCapacity );
123 }
124
125 void _erase( uint32_t loc )
126 {
127 if( nCapacity == 0 )
128 return;
129
130 bDeleted[loc/32] |= (1<<(loc%32));
131 va.destroy( &aValues[loc] );
132 ka.destroy( &aKeys[loc] );
133 nDeleted++;
134 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
135 // nFilled, nDeleted, nCapacity );
136 }
137
138 key &getKeyAtPos( uint32_t nPos )
139 {
140 if( nPos >= nCapacity )
141 throw HashException("Referenced position invalid.");
142 return aKeys[nPos];
112 } 143 }
113 144
114 /** 145 const key &getKeyAtPos( uint32_t nPos ) const
115 * Direct function for retrieving a value out of the HashProxy.
116 *@returns (value_type &) The value pointed to by this HashProxy.
117 */
118 _value &getValue()
119 { 146 {
120 if( bFilled == false ) 147 if( nPos >= nCapacity )
121 throw HashException( 148 throw HashException("Referenced position invalid.");
122 excodeNotFilled, 149 return aKeys[nPos];
123 "No data assosiated with that key." 150 }
124 ); 151
125 return *pValue; 152 value &getValueAtPos( uint32_t nPos )
153 {
154 if( nPos >= nCapacity )
155 throw HashException("Referenced position invalid.");
156 return aValues[nPos];
157 }
158
159 const value &getValueAtPos( uint32_t nPos ) const
160 {
161 if( nPos >= nCapacity )
162 throw HashException("Referenced position invalid.");
163 return aValues[nPos];
126 } 164 }
127 165
128 /** 166 uint32_t getFirstPos( bool &bFinished ) const
129 * Whether this HashProxy points to something real or not. 167 {
130 */ 168 for( uint32_t j = 0; j < nCapacity; j++ )
131 bool isFilled() 169 {
170 if( isFilled( j ) )
171 if( !isDeleted( j ) )
172 return j;
173 }
174
175 bFinished = true;
176 return 0;
177 }
178
179 uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
132 { 180 {
133 return bFilled; 181 for( uint32_t j = nPos+1; j < nCapacity; j++ )
182 {
183 if( isFilled( j ) )
184 if( !isDeleted( j ) )
185 return j;
186 }
187
188 bFinished = true;
189 return 0;
134 } 190 }
135 191
136 /** 192 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
137 * Erase the data pointed to by this HashProxy.
138 */
139 void erase()
140 { 193 {
141 if( bFilled ) 194 init();
195
196 uint32_t nCur = hash%nCapacity;
197
198 // First we scan to see if the key is already there, abort if we
199 // run out of probing room, or we find a non-filled entry
200 int8_t j;
201 for( j = 0;
202 isFilled( nCur ) && j < 32;
203 nCur = (nCur + (1<<j))%nCapacity, j++
204 )
205 {
206 // Is this the same hash code we were looking for?
207 if( hash == aHashCodes[nCur] )
208 {
209 // Skip over deleted entries. Deleted entries are also filled,
210 // so we only have to do this check here.
211 if( isDeleted( nCur ) )
212 continue;
213
214 // Is it really the same key? (for safety)
215 if( __cmpHashKeys( aKeys[nCur], k ) == true )
216 {
217 bFill = true;
218 return nCur;
219 }
220 }
221 }
222
223 // This is our insurance, if the table is full, then go ahead and
224 // rehash, then try again.
225 if( (isFilled( nCur ) || j == 32) && rehash == true )
142 { 226 {
143 hsh._erase( nPos ); 227 reHash( szCalc( nCapacity, nFilled, nDeleted ) );
144 hsh.onDelete(); 228
229 // This is potentially dangerous, and could cause an infinite loop.
230 // Be careful writing probe, eh?
231 return probe( hash, k, bFill );
145 } 232 }
233
234 bFill = false;
235 return nCur;
146 } 236 }
237
238 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
239 {
240 if( nCapacity == 0 )
241 throw Bu::ExceptionBase("Probe in empty hash table.");
147 242
148 /** 243 uint32_t nCur = hash%nCapacity;
149 * Assign data to this point in the hash table. 244
150 *@param nval (value_type) the data to assign. 245 // First we scan to see if the key is already there, abort if we
151 */ 246 // run out of probing room, or we find a non-filled entry
152 _value operator=( _value nval ) 247 for( int8_t j = 0;
248 isFilled( nCur ) && j < 32;
249 nCur = (nCur + (1<<j))%nCapacity, j++
250 )
251 {
252 // Is this the same hash code we were looking for?
253 if( hash == aHashCodes[nCur] )
254 {
255 // Skip over deleted entries. Deleted entries are also filled,
256 // so we only have to do this check here.
257 if( isDeleted( nCur ) )
258 continue;
259
260 // Is it really the same key? (for safety)
261 if( __cmpHashKeys( aKeys[nCur], k ) == true )
262 {
263 bFill = true;
264 return nCur;
265 }
266 }
267 }
268
269 bFill = false;
270 return nCur;
271 }
272
273 void insert( const key &k, const value &v )
153 { 274 {
154 if( bFilled ) 275 uint32_t hash = __calcHashCode( k );
276 bool bFill;
277 uint32_t nPos = probe( hash, k, bFill );
278
279 if( bFill )
155 { 280 {
156 hsh.va.destroy( &hsh.aValues[nPos] ); 281 va.destroy( &aValues[nPos] );
157 hsh.va.construct( &hsh.aValues[nPos], nval ); 282 va.construct( &aValues[nPos], v );
158 hsh.onUpdate();
159 } 283 }
160 else 284 else
161 { 285 {
162 hsh.fill( nPos, *pKey, nval, hash ); 286 fill( nPos, k, v, hash );
163 hsh.onInsert(); 287 }
288 }
289
290 void reHash( uint32_t nNewSize )
291 {
292 //printf("---REHASH---");
293 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
294 // nFilled, nDeleted, nCapacity );
295
296 // Save all the old data
297 uint32_t nOldCapacity = nCapacity;
298 uint32_t *bOldFilled = bFilled;
299 uint32_t *aOldHashCodes = aHashCodes;
300 uint32_t nOldKeysSize = nKeysSize;
301 uint32_t *bOldDeleted = bDeleted;
302 value *aOldValues = aValues;
303 key *aOldKeys = aKeys;
304
305 // Calculate new sizes
306 nCapacity = nNewSize;
307 nKeysSize = bitsToBytes( nCapacity );
308
309 // Allocate new memory + prep
310 bFilled = ca.allocate( nKeysSize );
311 bDeleted = ca.allocate( nKeysSize );
312 clearBits();
313
314 aHashCodes = ca.allocate( nCapacity );
315 aKeys = ka.allocate( nCapacity );
316 aValues = va.allocate( nCapacity );
317
318 nDeleted = nFilled = 0;
319
320 // Re-insert all of the old data (except deleted items)
321 for( uint32_t j = 0; j < nOldCapacity; j++ )
322 {
323 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
324 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
325 {
326 insert( aOldKeys[j], aOldValues[j] );
327 }
328 }
329
330 // Delete all of the old data
331 for( uint32_t j = 0; j < nOldCapacity; j++ )
332 {
333 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
334 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
335 {
336 va.destroy( &aOldValues[j] );
337 ka.destroy( &aOldKeys[j] );
338 }
164 } 339 }
340 va.deallocate( aOldValues, nOldCapacity );
341 ka.deallocate( aOldKeys, nOldCapacity );
342 ca.deallocate( bOldFilled, nOldKeysSize );
343 ca.deallocate( bOldDeleted, nOldKeysSize );
344 ca.deallocate( aOldHashCodes, nOldCapacity );
345 }
165 346
166 return nval; 347 bool isFilled( uint32_t loc ) const
348 {
349 if( loc >= nCapacity )
350 throw HashException("Referenced position invalid.");
351 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
167 } 352 }
168 353
169 /** 354 bool isDeleted( uint32_t loc ) const
170 * Pointer extraction operator. Access to members of data pointed to
171 * by HashProxy.
172 *@returns (value_type *)
173 */
174 _value *operator->()
175 { 355 {
176 if( bFilled == false ) 356 if( loc >= nCapacity )
177 throw HashException( 357 throw HashException("Referenced position invalid.");
178 excodeNotFilled, 358 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
179 "No data assosiated with that key." 359 }
180 ); 360
181 return pValue; 361 void clear()
362 {
363 for( uint32_t j = 0; j < nCapacity; j++ )
364 {
365 if( isFilled( j ) )
366 if( !isDeleted( j ) )
367 {
368 va.destroy( &aValues[j] );
369 ka.destroy( &aKeys[j] );
370 }
371 }
372 va.deallocate( aValues, nCapacity );
373 ka.deallocate( aKeys, nCapacity );
374 ca.deallocate( bFilled, nKeysSize );
375 ca.deallocate( bDeleted, nKeysSize );
376 ca.deallocate( aHashCodes, nCapacity );
377
378 bFilled = NULL;
379 bDeleted = NULL;
380 aKeys = NULL;
381 aValues = NULL;
382 aHashCodes = NULL;
383
384 nCapacity = 0;
385 nFilled = 0;
386 nDeleted = 0;
182 } 387 }
388
389 uint32_t nCapacity;
390 uint32_t nFilled;
391 uint32_t nDeleted;
392 uint32_t *bFilled;
393 uint32_t *bDeleted;
394 uint32_t nKeysSize;
395 key *aKeys;
396 value *aValues;
397 uint32_t *aHashCodes;
398 valuealloc va;
399 keyalloc ka;
400 challoc ca;
401 sizecalc szCalc;
183 }; 402 };
403 /** @endcond */
184 404
185 /** 405 /**
186 * Libbu++ Template Hash Table. This is your average hash table, that uses 406 * Libbu++ Template Hash Table. This is your average hash table, that uses
@@ -224,119 +444,38 @@ namespace Bu
224 *@param challoc (typename) Byte allocator for bitflags 444 *@param challoc (typename) Byte allocator for bitflags
225 *@ingroup Containers 445 *@ingroup Containers
226 */ 446 */
227 template<typename key, typename value, typename sizecalc, typename keyalloc, typename valuealloc, typename challoc > 447 template<typename key, typename value,
228 class Hash 448 typename sizecalc = __calcNextTSize_fast,
449 typename keyalloc = std::allocator<key>,
450 typename valuealloc = std::allocator<value>,
451 typename challoc = std::allocator<uint32_t>
452 >
453 class Hash : public SharedCore<
454 Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>,
455 HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc>
456 >
229 { 457 {
230 friend struct HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>; 458 private:
459 typedef class HashCore<key, value, sizecalc, keyalloc, valuealloc, challoc> Core;
231 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType; 460 typedef class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc> MyType;
461 protected:
462 using SharedCore<MyType, Core>::core;
463 using SharedCore<MyType, Core>::_hardCopy;
464 using SharedCore<MyType, Core>::_resetCore;
465 using SharedCore<MyType, Core>::_allocateCore;
466
232 public: 467 public:
233 Hash() : 468 Hash()
234 nCapacity( 11 ),
235 nFilled( 0 ),
236 nDeleted( 0 ),
237 bFilled( NULL ),
238 bDeleted( NULL ),
239 aKeys( NULL ),
240 aValues( NULL ),
241 aHashCodes( NULL )
242 {
243 nKeysSize = bitsToBytes( nCapacity );
244 bFilled = ca.allocate( nKeysSize );
245 bDeleted = ca.allocate( nKeysSize );
246 clearBits();
247
248 aHashCodes = ca.allocate( nCapacity );
249 aKeys = ka.allocate( nCapacity );
250 aValues = va.allocate( nCapacity );
251 }
252
253 Hash( const Hash &src ) :
254 nCapacity( src.nCapacity ),
255 nFilled( 0 ),
256 nDeleted( 0 ),
257 bFilled( NULL ),
258 bDeleted( NULL ),
259 aKeys( NULL ),
260 aValues( NULL ),
261 aHashCodes( NULL )
262 { 469 {
263 nKeysSize = bitsToBytes( nCapacity );
264 bFilled = ca.allocate( nKeysSize );
265 bDeleted = ca.allocate( nKeysSize );
266 clearBits();
267
268 aHashCodes = ca.allocate( nCapacity );
269 aKeys = ka.allocate( nCapacity );
270 aValues = va.allocate( nCapacity );
271
272 for( uint32_t j = 0; j < src.nCapacity; j++ )
273 {
274 if( src.isFilled( j ) && !src.isDeleted( j ) )
275 {
276 insert( src.aKeys[j], src.aValues[j] );
277 }
278 }
279 } 470 }
280 471
281 /** 472 Hash( const MyType &src ) :
282 * Hashtable assignment operator. Clears this hashtable and 473 SharedCore<MyType, Core >( src )
283 * copies RH into it.
284 */
285 Hash &operator=( const Hash &src )
286 { 474 {
287 for( uint32_t j = 0; j < nCapacity; j++ )
288 {
289 if( isFilled( j ) && !isDeleted( j ) )
290 {
291 va.destroy( &aValues[j] );
292 ka.destroy( &aKeys[j] );
293 }
294 }
295 va.deallocate( aValues, nCapacity );
296 ka.deallocate( aKeys, nCapacity );
297 ca.deallocate( bFilled, nKeysSize );
298 ca.deallocate( bDeleted, nKeysSize );
299 ca.deallocate( aHashCodes, nCapacity );
300
301 nFilled = 0;
302 nDeleted = 0;
303 nCapacity = src.nCapacity;
304 nKeysSize = bitsToBytes( nCapacity );
305 bFilled = ca.allocate( nKeysSize );
306 bDeleted = ca.allocate( nKeysSize );
307 clearBits();
308
309 aHashCodes = ca.allocate( nCapacity );
310 aKeys = ka.allocate( nCapacity );
311 aValues = va.allocate( nCapacity );
312
313 for( uint32_t j = 0; j < src.nCapacity; j++ )
314 {
315 if( src.isFilled( j ) && !src.isDeleted( j ) )
316 {
317 insert( src.aKeys[j], src.aValues[j] );
318 }
319 }
320
321 return *this;
322 } 475 }
323 476
324 virtual ~Hash() 477 virtual ~Hash()
325 { 478 {
326 for( uint32_t j = 0; j < nCapacity; j++ )
327 {
328 if( isFilled( j ) )
329 if( !isDeleted( j ) )
330 {
331 va.destroy( &aValues[j] );
332 ka.destroy( &aKeys[j] );
333 }
334 }
335 va.deallocate( aValues, nCapacity );
336 ka.deallocate( aKeys, nCapacity );
337 ca.deallocate( bFilled, nKeysSize );
338 ca.deallocate( bDeleted, nKeysSize );
339 ca.deallocate( aHashCodes, nCapacity );
340 } 479 }
341 480
342 /** 481 /**
@@ -345,7 +484,7 @@ namespace Bu
345 */ 484 */
346 uint32_t getCapacity() const 485 uint32_t getCapacity() const
347 { 486 {
348 return nCapacity; 487 return core->nCapacity;
349 } 488 }
350 489
351 /** 490 /**
@@ -355,7 +494,7 @@ namespace Bu
355 */ 494 */
356 uint32_t getFill() const 495 uint32_t getFill() const
357 { 496 {
358 return nFilled; 497 return core->nFilled;
359 } 498 }
360 499
361 /** 500 /**
@@ -364,12 +503,12 @@ namespace Bu
364 */ 503 */
365 uint32_t getSize() const 504 uint32_t getSize() const
366 { 505 {
367 return nFilled-nDeleted; 506 return core->nFilled-core->nDeleted;
368 } 507 }
369 508
370 bool isEmpty() const 509 bool isEmpty() const
371 { 510 {
372 return (nFilled-nDeleted) == 0; 511 return (core->nFilled-core->nDeleted) == 0;
373 } 512 }
374 513
375 /** 514 /**
@@ -379,27 +518,140 @@ namespace Bu
379 */ 518 */
380 uint32_t getDeleted() const 519 uint32_t getDeleted() const
381 { 520 {
382 return nDeleted; 521 return core->nDeleted;
383 } 522 }
384 523
524 struct HashProxy
525 {
526 friend class Hash<key, value, sizecalc, keyalloc, valuealloc, challoc>;
527 private:
528 HashProxy( MyType &h, const key *k, uint32_t nPos, uint32_t hash ) :
529 hsh( h ),
530 pKey( k ),
531 nPos( nPos ),
532 hash( hash ),
533 bFilled( false )
534 {
535 }
536
537 HashProxy( MyType &h, uint32_t nPos, value *pValue ) :
538 hsh( h ),
539 nPos( nPos ),
540 pValue( pValue ),
541 bFilled( true )
542 {
543 }
544
545 MyType &hsh;
546 const key *pKey;
547 uint32_t nPos;
548 value *pValue;
549 uint32_t hash;
550 bool bFilled;
551
552 public:
553 /**
554 * Cast operator for HashProxy.
555 *@returns (value_type &) The value the HashProxy is pointing to.
556 */
557 operator value &()
558 {
559 if( bFilled == false )
560 throw HashException(
561 excodeNotFilled,
562 "No data assosiated with that key."
563 );
564 return *pValue;
565 }
566
567 /**
568 * Direct function for retrieving a value out of the HashProxy.
569 *@returns (value_type &) The value pointed to by this HashProxy.
570 */
571 value &getValue()
572 {
573 if( bFilled == false )
574 throw HashException(
575 excodeNotFilled,
576 "No data assosiated with that key."
577 );
578 return *pValue;
579 }
580
581 /**
582 * Whether this HashProxy points to something real or not.
583 */
584 bool isFilled()
585 {
586 return bFilled;
587 }
588
589 /**
590 * Erase the data pointed to by this HashProxy.
591 */
592 void erase()
593 {
594 if( bFilled )
595 {
596 hsh.core->_erase( nPos );
597 }
598 }
599
600 /**
601 * Assign data to this point in the hash table.
602 *@param nval (value_type) the data to assign.
603 */
604 value operator=( value nval )
605 {
606 if( bFilled )
607 {
608 hsh.core->va.destroy( &hsh.core->aValues[nPos] );
609 hsh.core->va.construct( &hsh.core->aValues[nPos], nval );
610 }
611 else
612 {
613 hsh.core->fill( nPos, *pKey, nval, hash );
614 }
615
616 return nval;
617 }
618
619 /**
620 * Pointer extraction operator. Access to members of data pointed to
621 * by HashProxy.
622 *@returns (value_type *)
623 */
624 value *operator->()
625 {
626 if( bFilled == false )
627 throw HashException(
628 excodeNotFilled,
629 "No data assosiated with that key."
630 );
631 return pValue;
632 }
633 };
634
385 /** 635 /**
386 * Hash table index operator 636 * Hash table index operator
387 *@param k (key_type) Key of data to be retrieved. 637 *@param k (key_type) Key of data to be retrieved.
388 *@returns (HashProxy) Proxy pointing to the data. 638 *@returns (HashProxy) Proxy pointing to the data.
389 */ 639 */
390 virtual HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc> operator[]( const key &k ) 640 HashProxy operator[]( const key &k )
391 { 641 {
642 _hardCopy();
643
392 uint32_t hash = __calcHashCode( k ); 644 uint32_t hash = __calcHashCode( k );
393 bool bFill; 645 bool bFill;
394 uint32_t nPos = probe( hash, k, bFill ); 646 uint32_t nPos = core->probe( hash, k, bFill );
395 647
396 if( bFill ) 648 if( bFill )
397 { 649 {
398 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, nPos, &aValues[nPos] ); 650 return HashProxy( *this, nPos, &core->aValues[nPos] );
399 } 651 }
400 else 652 else
401 { 653 {
402 return HashProxy<key, value, sizecalc, keyalloc, valuealloc, challoc>( *this, &k, nPos, hash ); 654 return HashProxy( *this, &k, nPos, hash );
403 } 655 }
404 } 656 }
405 657
@@ -408,39 +660,28 @@ namespace Bu
408 *@param k (key_type) Key to list the value under. 660 *@param k (key_type) Key to list the value under.
409 *@param v (value_type) Value to store in the hash table. 661 *@param v (value_type) Value to store in the hash table.
410 */ 662 */
411 virtual void insert( const key &k, const value &v ) 663 void insert( const key &k, const value &v )
412 { 664 {
413 uint32_t hash = __calcHashCode( k ); 665 _hardCopy();
414 bool bFill;
415 uint32_t nPos = probe( hash, k, bFill );
416 666
417 if( bFill ) 667 core->insert( k, v );
418 {
419 va.destroy( &aValues[nPos] );
420 va.construct( &aValues[nPos], v );
421 onUpdate();
422 }
423 else
424 {
425 fill( nPos, k, v, hash );
426 onInsert();
427 }
428 } 668 }
429 669
430 /** 670 /**
431 * Remove a value from the hash table. 671 * Remove a value from the hash table.
432 *@param k (key_type) The data under this key will be erased. 672 *@param k (key_type) The data under this key will be erased.
433 */ 673 */
434 virtual void erase( const key &k ) 674 void erase( const key &k )
435 { 675 {
676 _hardCopy();
677
436 uint32_t hash = __calcHashCode( k ); 678 uint32_t hash = __calcHashCode( k );
437 bool bFill; 679 bool bFill;
438 uint32_t nPos = probe( hash, k, bFill ); 680 uint32_t nPos = core->probe( hash, k, bFill );
439 681
440 if( bFill ) 682 if( bFill )
441 { 683 {
442 _erase( nPos ); 684 core->_erase( nPos );
443 onDelete();
444 } 685 }
445 } 686 }
446 687
@@ -450,14 +691,16 @@ namespace Bu
450 * Remove a value from the hash pointed to from an iterator. 691 * Remove a value from the hash pointed to from an iterator.
451 *@param i (iterator &) The data to be erased. 692 *@param i (iterator &) The data to be erased.
452 */ 693 */
453 virtual void erase( struct iterator &i ) 694 void erase( struct iterator &i )
454 { 695 {
455 if( this != i.hsh ) 696 if( this != i.hsh )
456 throw HashException("This iterator didn't come from this Hash."); 697 throw HashException("This iterator didn't come from this Hash.");
457 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) ) 698
699 _hardCopy();
700
701 if( core->isFilled( i.nPos ) && !core->isDeleted( i.nPos ) )
458 { 702 {
459 _erase( i.nPos ); 703 core->_erase( i.nPos );
460 onDelete();
461 } 704 }
462 } 705 }
463 706
@@ -466,17 +709,7 @@ namespace Bu
466 */ 709 */
467 virtual void clear() 710 virtual void clear()
468 { 711 {
469 for( uint32_t j = 0; j < nCapacity; j++ ) 712 _resetCore();
470 {
471 if( isFilled( j ) )
472 if( !isDeleted( j ) )
473 {
474 _erase( j );
475 onDelete();
476 }
477 }
478
479 clearBits();
480 } 713 }
481 714
482 /** 715 /**
@@ -484,15 +717,17 @@ namespace Bu
484 *@param k (key_type) Key pointing to the data to be retrieved. 717 *@param k (key_type) Key pointing to the data to be retrieved.
485 *@returns (value_type &) The data pointed to by (k). 718 *@returns (value_type &) The data pointed to by (k).
486 */ 719 */
487 virtual value &get( const key &k ) 720 value &get( const key &k )
488 { 721 {
722 _hardCopy();
723
489 uint32_t hash = __calcHashCode( k ); 724 uint32_t hash = __calcHashCode( k );
490 bool bFill; 725 bool bFill;
491 uint32_t nPos = probe( hash, k, bFill, false ); 726 uint32_t nPos = core->probe( hash, k, bFill, false );
492 727
493 if( bFill ) 728 if( bFill )
494 { 729 {
495 return aValues[nPos]; 730 return core->aValues[nPos];
496 } 731 }
497 else 732 else
498 { 733 {
@@ -509,15 +744,15 @@ namespace Bu
509 *@returns (const value_type &) A const version of the data pointed 744 *@returns (const value_type &) A const version of the data pointed
510 * to by (k). 745 * to by (k).
511 */ 746 */
512 virtual const value &get( const key &k ) const 747 const value &get( const key &k ) const
513 { 748 {
514 uint32_t hash = __calcHashCode( k ); 749 uint32_t hash = __calcHashCode( k );
515 bool bFill; 750 bool bFill;
516 uint32_t nPos = probe( hash, k, bFill ); 751 uint32_t nPos = core->probe( hash, k, bFill );
517 752
518 if( bFill ) 753 if( bFill )
519 { 754 {
520 return aValues[nPos]; 755 return core->aValues[nPos];
521 } 756 }
522 else 757 else
523 { 758 {
@@ -533,18 +768,10 @@ namespace Bu
533 *@param k (key_type) The key to check. 768 *@param k (key_type) The key to check.
534 *@returns (bool) Whether there was an item in the hash under key (k). 769 *@returns (bool) Whether there was an item in the hash under key (k).
535 */ 770 */
536 virtual bool has( const key &k ) 771 bool has( const key &k ) const
537 { 772 {
538 bool bFill; 773 bool bFill;
539 probe( __calcHashCode( k ), k, bFill, false ); 774 core->probe( __calcHashCode( k ), k, bFill );
540
541 return bFill;
542 }
543
544 virtual bool has( const key &k ) const
545 {
546 bool bFill;
547 probe( __calcHashCode( k ), k, bFill );
548 775
549 return bFill; 776 return bFill;
550 } 777 }
@@ -561,7 +788,7 @@ namespace Bu
561 nPos( 0 ), 788 nPos( 0 ),
562 bFinished( false ) 789 bFinished( false )
563 { 790 {
564 nPos = hsh->getFirstPos( bFinished ); 791 nPos = hsh->core->getFirstPos( bFinished );
565 } 792 }
566 793
567 iterator( MyType *hsh, bool bDone ) : 794 iterator( MyType *hsh, bool bDone ) :
@@ -590,11 +817,6 @@ namespace Bu
590 { 817 {
591 } 818 }
592 819
593 DEPRECATED bool isActive() const
594 {
595 return !bFinished;
596 }
597
598 bool isValid() const 820 bool isValid() const
599 { 821 {
600 return !bFinished; 822 return !bFinished;
@@ -611,7 +833,7 @@ namespace Bu
611 iterator operator++( int ) 833 iterator operator++( int )
612 { 834 {
613 if( bFinished == false ) 835 if( bFinished == false )
614 nPos = hsh->getNextPos( nPos, bFinished ); 836 nPos = hsh->core->getNextPos( nPos, bFinished );
615 837
616 return *this; 838 return *this;
617 } 839 }
@@ -622,7 +844,7 @@ namespace Bu
622 iterator operator++() 844 iterator operator++()
623 { 845 {
624 if( bFinished == false ) 846 if( bFinished == false )
625 nPos = hsh->getNextPos( nPos, bFinished ); 847 nPos = hsh->core->getNextPos( nPos, bFinished );
626 848
627 return *this; 849 return *this;
628 } 850 }
@@ -671,21 +893,22 @@ namespace Bu
671 */ 893 */
672 value &operator *() 894 value &operator *()
673 { 895 {
674 return hsh->getValueAtPos( nPos ); 896 hsh->_hardCopy();
897 return hsh->core->getValueAtPos( nPos );
675 } 898 }
676 899
677 const value &operator *() const 900 const value &operator *() const
678 { 901 {
679 return hsh->getValueAtPos( nPos ); 902 return hsh->core->getValueAtPos( nPos );
680 } 903 }
681 904
682 /** 905 /**
683 * Get the key behind this iterator. 906 * Get the key behind this iterator.
684 *@returns (key_type &) The key behind this iterator. 907 *@returns (key_type &) The key behind this iterator.
685 */ 908 */
686 key &getKey() 909 const key &getKey() const
687 { 910 {
688 return hsh->getKeyAtPos( nPos ); 911 return hsh->core->getKeyAtPos( nPos );
689 } 912 }
690 913
691 /** 914 /**
@@ -694,7 +917,17 @@ namespace Bu
694 */ 917 */
695 value &getValue() 918 value &getValue()
696 { 919 {
697 return hsh->getValueAtPos( nPos ); 920 hsh->_hardCopy();
921 return hsh->core->getValueAtPos( nPos );
922 }
923
924 /**
925 * Get the value behind this iterator.
926 *@returns (value_type &) The value behind this iterator.
927 */
928 const value &getValue() const
929 {
930 return hsh->core->getValueAtPos( nPos );
698 } 931 }
699 } iterator; 932 } iterator;
700 933
@@ -710,7 +943,7 @@ namespace Bu
710 nPos( 0 ), 943 nPos( 0 ),
711 bFinished( false ) 944 bFinished( false )
712 { 945 {
713 nPos = hsh->getFirstPos( bFinished ); 946 nPos = hsh->core->getFirstPos( bFinished );
714 } 947 }
715 948
716 const_iterator( const MyType *hsh, bool bDone ) : 949 const_iterator( const MyType *hsh, bool bDone ) :
@@ -762,7 +995,7 @@ namespace Bu
762 const_iterator operator++( int ) 995 const_iterator operator++( int )
763 { 996 {
764 if( bFinished == false ) 997 if( bFinished == false )
765 nPos = hsh->getNextPos( nPos, bFinished ); 998 nPos = hsh->core->getNextPos( nPos, bFinished );
766 999
767 return *this; 1000 return *this;
768 } 1001 }
@@ -773,7 +1006,7 @@ namespace Bu
773 const_iterator operator++() 1006 const_iterator operator++()
774 { 1007 {
775 if( bFinished == false ) 1008 if( bFinished == false )
776 nPos = hsh->getNextPos( nPos, bFinished ); 1009 nPos = hsh->core->getNextPos( nPos, bFinished );
777 1010
778 return *this; 1011 return *this;
779 } 1012 }
@@ -822,7 +1055,7 @@ namespace Bu
822 */ 1055 */
823 const value &operator *() const 1056 const value &operator *() const
824 { 1057 {
825 return hsh->getValueAtPos( nPos ); 1058 return hsh->core->getValueAtPos( nPos );
826 } 1059 }
827 1060
828 /** 1061 /**
@@ -831,7 +1064,7 @@ namespace Bu
831 */ 1064 */
832 const key &getKey() const 1065 const key &getKey() const
833 { 1066 {
834 return hsh->getKeyAtPos( nPos ); 1067 return hsh->core->getKeyAtPos( nPos );
835 } 1068 }
836 1069
837 /** 1070 /**
@@ -840,7 +1073,7 @@ namespace Bu
840 */ 1073 */
841 const value &getValue() const 1074 const value &getValue() const
842 { 1075 {
843 return hsh->getValueAtPos( nPos ); 1076 return hsh->core->getValueAtPos( nPos );
844 } 1077 }
845 } const_iterator; 1078 } const_iterator;
846 1079
@@ -883,13 +1116,13 @@ namespace Bu
883 { 1116 {
884 Bu::List<key> lKeys; 1117 Bu::List<key> lKeys;
885 1118
886 for( uint32_t j = 0; j < nCapacity; j++ ) 1119 for( uint32_t j = 0; j < core->nCapacity; j++ )
887 { 1120 {
888 if( isFilled( j ) ) 1121 if( core->isFilled( j ) )
889 { 1122 {
890 if( !isDeleted( j ) ) 1123 if( !core->isDeleted( j ) )
891 { 1124 {
892 lKeys.append( aKeys[j] ); 1125 lKeys.append( core->aKeys[j] );
893 } 1126 }
894 } 1127 }
895 } 1128 }
@@ -901,13 +1134,13 @@ namespace Bu
901 { 1134 {
902 Bu::List<value> lValues; 1135 Bu::List<value> lValues;
903 1136
904 for( uint32_t j = 0; j < nCapacity; j++ ) 1137 for( uint32_t j = 0; j < core->nCapacity; j++ )
905 { 1138 {
906 if( isFilled( j ) ) 1139 if( core->isFilled( j ) )
907 { 1140 {
908 if( !isDeleted( j ) ) 1141 if( !core->isDeleted( j ) )
909 { 1142 {
910 lValues.append( aValues[j] ); 1143 lValues.append( core->aValues[j] );
911 } 1144 }
912 } 1145 }
913 } 1146 }
@@ -915,244 +1148,74 @@ namespace Bu
915 return lValues; 1148 return lValues;
916 } 1149 }
917 1150
918 protected: 1151 bool operator==( const MyType &rhs ) const
919 virtual void onInsert() {}
920 virtual void onUpdate() {}
921 virtual void onDelete() {}
922 virtual void onReHash() {}
923
924 virtual void clearBits()
925 {
926 for( uint32_t j = 0; j < nKeysSize; j++ )
927 {
928 bFilled[j] = bDeleted[j] = 0;
929 }
930 }
931
932 virtual void fill( uint32_t loc, const key &k, const value &v, uint32_t hash )
933 {
934 bFilled[loc/32] |= (1<<(loc%32));
935 va.construct( &aValues[loc], v );
936 ka.construct( &aKeys[loc], k );
937 aHashCodes[loc] = hash;
938 nFilled++;
939 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
940 // nFilled, nDeleted, nCapacity );
941 }
942
943 virtual void _erase( uint32_t loc )
944 {
945 bDeleted[loc/32] |= (1<<(loc%32));
946 va.destroy( &aValues[loc] );
947 ka.destroy( &aKeys[loc] );
948 nDeleted++;
949 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
950 // nFilled, nDeleted, nCapacity );
951 }
952
953 virtual key &getKeyAtPos( uint32_t nPos )
954 {
955 return aKeys[nPos];
956 }
957
958 virtual const key &getKeyAtPos( uint32_t nPos ) const
959 {
960 return aKeys[nPos];
961 }
962
963 virtual value &getValueAtPos( uint32_t nPos )
964 {
965 return aValues[nPos];
966 }
967
968 virtual const value &getValueAtPos( uint32_t nPos ) const
969 {
970 return aValues[nPos];
971 }
972
973 virtual uint32_t getFirstPos( bool &bFinished ) const
974 {
975 for( uint32_t j = 0; j < nCapacity; j++ )
976 {
977 if( isFilled( j ) )
978 if( !isDeleted( j ) )
979 return j;
980 }
981
982 bFinished = true;
983 return 0;
984 }
985
986 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
987 { 1152 {
988 for( uint32_t j = nPos+1; j < nCapacity; j++ ) 1153 if( this == &rhs )
989 { 1154 return true;
990 if( isFilled( j ) ) 1155 if( core == rhs.core )
991 if( !isDeleted( j ) ) 1156 return true;
992 return j; 1157 if( core == NULL || rhs.core == NULL )
993 } 1158 return false;
994 1159 if( getSize() != rhs.getSize() )
995 bFinished = true; 1160 return false;
996 return 0; 1161
997 } 1162 for( uint32_t j = 0; j < core->nCapacity; j++ )
998
999 uint32_t probe( uint32_t hash, const key &k, bool &bFill, bool rehash=true )
1000 {
1001 uint32_t nCur = hash%nCapacity;
1002
1003 // First we scan to see if the key is already there, abort if we
1004 // run out of probing room, or we find a non-filled entry
1005 int8_t j;
1006 for( j = 0;
1007 isFilled( nCur ) && j < 32;
1008 nCur = (nCur + (1<<j))%nCapacity, j++
1009 )
1010 { 1163 {
1011 // Is this the same hash code we were looking for? 1164 if( core->isFilled( j ) )
1012 if( hash == aHashCodes[nCur] )
1013 { 1165 {
1014 // Skip over deleted entries. Deleted entries are also filled, 1166 if( !core->isDeleted( j ) )
1015 // so we only have to do this check here.
1016 if( isDeleted( nCur ) )
1017 continue;
1018
1019 // Is it really the same key? (for safety)
1020 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1021 { 1167 {
1022 bFill = true; 1168 // Check to see if this key is in the other hash
1023 return nCur; 1169 if( rhs.has( core->aKeys[j] ) )
1170 {
1171 if( !(core->aValues[j] == rhs.get( core->aKeys[j]) ) )
1172 {
1173 return false;
1174 }
1175 }
1176 else
1177 {
1178 return false;
1179 }
1024 } 1180 }
1025 } 1181 }
1026 } 1182 }
1027 1183
1028 // This is our insurance, if the table is full, then go ahead and 1184 return true;
1029 // rehash, then try again.
1030 if( (isFilled( nCur ) || j == 32) && rehash == true )
1031 {
1032 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
1033
1034 // This is potentially dangerous, and could cause an infinite loop.
1035 // Be careful writing probe, eh?
1036 return probe( hash, k, bFill );
1037 }
1038
1039 bFill = false;
1040 return nCur;
1041 } 1185 }
1042
1043 uint32_t probe( uint32_t hash, key k, bool &bFill ) const
1044 {
1045 uint32_t nCur = hash%nCapacity;
1046
1047 // First we scan to see if the key is already there, abort if we
1048 // run out of probing room, or we find a non-filled entry
1049 for( int8_t j = 0;
1050 isFilled( nCur ) && j < 32;
1051 nCur = (nCur + (1<<j))%nCapacity, j++
1052 )
1053 {
1054 // Is this the same hash code we were looking for?
1055 if( hash == aHashCodes[nCur] )
1056 {
1057 // Skip over deleted entries. Deleted entries are also filled,
1058 // so we only have to do this check here.
1059 if( isDeleted( nCur ) )
1060 continue;
1061
1062 // Is it really the same key? (for safety)
1063 if( __cmpHashKeys( aKeys[nCur], k ) == true )
1064 {
1065 bFill = true;
1066 return nCur;
1067 }
1068 }
1069 }
1070 1186
1071 bFill = false; 1187 bool operator!=( const MyType &rhs ) const
1072 return nCur; 1188 {
1189 return !(*this == rhs);
1073 } 1190 }
1074 1191
1075 void reHash( uint32_t nNewSize ) 1192 protected:
1193 virtual Core *_copyCore( Core *src )
1076 { 1194 {
1077 //printf("---REHASH---"); 1195 Core *pRet = _allocateCore();
1078 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
1079 // nFilled, nDeleted, nCapacity );
1080
1081 // Save all the old data
1082 uint32_t nOldCapacity = nCapacity;
1083 uint32_t *bOldFilled = bFilled;
1084 uint32_t *aOldHashCodes = aHashCodes;
1085 uint32_t nOldKeysSize = nKeysSize;
1086 uint32_t *bOldDeleted = bDeleted;
1087 value *aOldValues = aValues;
1088 key *aOldKeys = aKeys;
1089
1090 // Calculate new sizes
1091 nCapacity = nNewSize;
1092 nKeysSize = bitsToBytes( nCapacity );
1093
1094 // Allocate new memory + prep
1095 bFilled = ca.allocate( nKeysSize );
1096 bDeleted = ca.allocate( nKeysSize );
1097 clearBits();
1098 1196
1099 aHashCodes = ca.allocate( nCapacity ); 1197 pRet->nFilled = 0;
1100 aKeys = ka.allocate( nCapacity ); 1198 pRet->nDeleted = 0;
1101 aValues = va.allocate( nCapacity ); 1199 pRet->nCapacity = src->nCapacity;
1102 1200 pRet->nKeysSize = bitsToBytes( pRet->nCapacity );
1103 nDeleted = nFilled = 0; 1201 pRet->bFilled = pRet->ca.allocate( pRet->nKeysSize );
1202 pRet->bDeleted = pRet->ca.allocate( pRet->nKeysSize );
1203 pRet->clearBits();
1104 1204
1105 // Re-insert all of the old data (except deleted items) 1205 pRet->aHashCodes = pRet->ca.allocate( pRet->nCapacity );
1106 for( uint32_t j = 0; j < nOldCapacity; j++ ) 1206 pRet->aKeys = pRet->ka.allocate( pRet->nCapacity );
1107 { 1207 pRet->aValues = pRet->va.allocate( pRet->nCapacity );
1108 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
1109 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1110 {
1111 insert( aOldKeys[j], aOldValues[j] );
1112 }
1113 }
1114 1208
1115 // Delete all of the old data 1209 for( uint32_t j = 0; j < src->nCapacity; j++ )
1116 for( uint32_t j = 0; j < nOldCapacity; j++ )
1117 { 1210 {
1118 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 && 1211 if( src->isFilled( j ) && !src->isDeleted( j ) )
1119 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
1120 { 1212 {
1121 va.destroy( &aOldValues[j] ); 1213 pRet->insert( src->aKeys[j], src->aValues[j] );
1122 ka.destroy( &aOldKeys[j] );
1123 } 1214 }
1124 } 1215 }
1125 va.deallocate( aOldValues, nOldCapacity );
1126 ka.deallocate( aOldKeys, nOldCapacity );
1127 ca.deallocate( bOldFilled, nOldKeysSize );
1128 ca.deallocate( bOldDeleted, nOldKeysSize );
1129 ca.deallocate( aOldHashCodes, nOldCapacity );
1130 }
1131 1216
1132 virtual bool isFilled( uint32_t loc ) const 1217 return pRet;
1133 {
1134 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
1135 }
1136
1137 virtual bool isDeleted( uint32_t loc ) const
1138 {
1139 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
1140 } 1218 }
1141
1142 protected:
1143 uint32_t nCapacity;
1144 uint32_t nFilled;
1145 uint32_t nDeleted;
1146 uint32_t *bFilled;
1147 uint32_t *bDeleted;
1148 uint32_t nKeysSize;
1149 key *aKeys;
1150 value *aValues;
1151 uint32_t *aHashCodes;
1152 valuealloc va;
1153 keyalloc ka;
1154 challoc ca;
1155 sizecalc szCalc;
1156 }; 1219 };
1157 1220
1158 template<typename T> uint32_t __calcHashCode( const T &k ) 1221 template<typename T> uint32_t __calcHashCode( const T &k )
diff --git a/src/heap.h b/src/heap.h
index 9df4121..31c2435 100644
--- a/src/heap.h
+++ b/src/heap.h
@@ -13,76 +13,93 @@
13#include "bu/exceptionbase.h" 13#include "bu/exceptionbase.h"
14#include "bu/util.h" 14#include "bu/util.h"
15#include "bu/queue.h" 15#include "bu/queue.h"
16#include "bu/sharedcore.h"
16 17
17namespace Bu 18namespace Bu
18{ 19{
19 subExceptionDecl( HeapException ); 20 subExceptionDecl( HeapException );
20 21
21 /** 22 template<typename item, typename cmpfunc, typename itemalloc>
22 * A priority queue that allows for an unlimited number of priorities. All 23 class Heap;
23 * objects enqueued must support less-than-comparison. Then every time an 24
24 * item is dequeued it is always the least item in the heap. The heap 25 /** @cond DEVEL */
25 * operates using a binary tree for storage, which allows most operations 26 template<typename item, typename cmpfunc, typename itemalloc>
26 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins 27 class HeapCore
27 * whereas peeking is constant time.
28 *
29 * This heap implementation allows iterating, however please note that any
30 * enqueue or dequeue operation will invalidate the iterator and make it
31 * unusable (if it still works, you shouldn't trust the results). Also,
32 * the items are not stored in memory in order, they are optomized into a
33 * tree. This means that the items will be in effectively random order
34 * while iterating through them, and the order cannot be trusted. Also,
35 * modifying an item in the heap will not cause that item to be re-sorted.
36 * If you want to change the position of an item in the heap you will have
37 * to dequeue every item before it, dequeue that item, change it, and
38 * re-enqueue all of the items removed.
39 */
40 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
41 class Heap : public Queue<item>
42 { 28 {
43 public: 29 friend class Heap<item, cmpfunc, itemalloc>;
44 Heap() : 30 friend class SharedCore<
45 iSize( 7 ), 31 Heap<item, cmpfunc, itemalloc>, HeapCore<item, cmpfunc, itemalloc>
32 >;
33 private:
34 HeapCore() :
35 iSize( 0 ),
46 iFill( 0 ), 36 iFill( 0 ),
47 aItem( ia.allocate( iSize ) ) 37 aItem( NULL )
48 { 38 {
49 } 39 }
50 40
51 Heap( cmpfunc cmpin ) : 41 virtual ~HeapCore()
52 iSize( 7 ),
53 iFill( 0 ),
54 aItem( ia.allocate( iSize ) ),
55 cmp( cmpin )
56 { 42 {
43 clear();
57 } 44 }
58 45
59 Heap( int iInitialCapacity ) : 46 void init()
60 iSize( 0 ),
61 iFill( 0 ),
62 aItem( NULL )
63 { 47 {
64 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } 48 if( iSize > 0 )
49 return;
50
51 iSize = 7;
52 iFill = 0;
65 aItem = ia.allocate( iSize ); 53 aItem = ia.allocate( iSize );
66 } 54 }
67 55
68 Heap( cmpfunc cmpin, int iInitialCapacity ) : 56 void init( int iCap )
69 iSize( 0 ),
70 iFill( 0 ),
71 aItem( NULL ),
72 cmp( cmpin )
73 { 57 {
74 for( iSize = 1; iSize < iInitialCapacity; iSize=iSize*2+1 ) { } 58 if( iSize > 0 )
59 return;
60
61 for( iSize = 1; iSize < iCap; iSize=iSize*2+1 ) { }
62 iFill = 0;
75 aItem = ia.allocate( iSize ); 63 aItem = ia.allocate( iSize );
76 } 64 }
77 65
78 virtual ~Heap() 66 void clear()
79 { 67 {
68 if( iSize == 0 )
69 return;
70
80 for( int j = 0; j < iFill; j++ ) 71 for( int j = 0; j < iFill; j++ )
81 ia.destroy( &aItem[j] ); 72 ia.destroy( &aItem[j] );
82 ia.deallocate( aItem, iSize ); 73 ia.deallocate( aItem, iSize );
83 aItem = NULL; 74 aItem = NULL;
75 iSize = 0;
76 iFill = 0;
84 } 77 }
78
79 void upSize()
80 {
81 if( iSize == 0 )
82 {
83 init();
84 return;
85 }
85 86
87 item *aNewItems = ia.allocate( iSize*2+1 );
88 //
89 // We cannot use a memcopy here because we don't know what kind
90 // of datastructures are being used, we have to copy them one at
91 // a time.
92 //
93 for( int j = 0; j < iFill; j++ )
94 {
95 ia.construct( &aNewItems[j], aItem[j] );
96 ia.destroy( &aItem[j] );
97 }
98 ia.deallocate( aItem, iSize );
99 aItem = aNewItems;
100 iSize = iSize*2+1;
101 }
102
86 virtual void enqueue( const item &it ) 103 virtual void enqueue( const item &it )
87 { 104 {
88 item i = it; // TODO: This is a silly workaround, put the i item 105 item i = it; // TODO: This is a silly workaround, put the i item
@@ -126,20 +143,6 @@ namespace Bu
126 iFill++; 143 iFill++;
127 } 144 }
128 145
129 virtual item &peek()
130 {
131 if( iFill == 0 )
132 throw HeapException("Heap empty.");
133 return aItem[0];
134 }
135
136 virtual const item &peek() const
137 {
138 if( iFill == 0 )
139 throw HeapException("Heap empty.");
140 return aItem[0];
141 }
142
143 virtual item dequeue() 146 virtual item dequeue()
144 { 147 {
145 if( iFill == 0 ) 148 if( iFill == 0 )
@@ -174,14 +177,118 @@ namespace Bu
174 return iRet; 177 return iRet;
175 } 178 }
176 179
180 private:
181 int iSize;
182 int iFill;
183 item *aItem;
184 cmpfunc cmp;
185 itemalloc ia;
186 };
187 /** @endcond */
188
189 /**
190 * A priority queue that allows for an unlimited number of priorities. All
191 * objects enqueued must support less-than-comparison. Then every time an
192 * item is dequeued it is always the least item in the heap. The heap
193 * operates using a binary tree for storage, which allows most operations
194 * to be very fast. Enqueueing and dequeueing are both O(log(N)) operatoins
195 * whereas peeking is constant time.
196 *
197 * This heap implementation allows iterating, however please note that any
198 * enqueue or dequeue operation will invalidate the iterator and make it
199 * unusable (if it still works, you shouldn't trust the results). Also,
200 * the items are not stored in memory in order, they are optomized into a
201 * tree. This means that the items will be in effectively random order
202 * while iterating through them, and the order cannot be trusted. Also,
203 * modifying an item in the heap will not cause that item to be re-sorted.
204 * If you want to change the position of an item in the heap you will have
205 * to dequeue every item before it, dequeue that item, change it, and
206 * re-enqueue all of the items removed.
207 */
208 template<typename item, typename cmpfunc=__basicLTCmp<item>, typename itemalloc=std::allocator<item> >
209 class Heap : public Queue<item>, public SharedCore<
210 Heap<item, cmpfunc, itemalloc>,
211 HeapCore<item, cmpfunc, itemalloc>
212 >
213 {
214 private:
215 typedef class Heap<item,cmpfunc,itemalloc> MyType;
216 typedef class HeapCore<item,cmpfunc,itemalloc> Core;
217
218 protected:
219 using SharedCore<MyType, Core>::core;
220 using SharedCore<MyType, Core>::_hardCopy;
221 using SharedCore<MyType, Core>::_resetCore;
222 using SharedCore<MyType, Core>::_allocateCore;
223
224 public:
225 Heap()
226 {
227 }
228
229 Heap( cmpfunc cmpin )
230 {
231 core->cmp = cmpin;
232 }
233
234 Heap( int iInitialCapacity )
235 {
236 core->init( iInitialCapacity );
237 }
238
239 Heap( cmpfunc cmpin, int iInitialCapacity )
240 {
241 core->cmp = cmpin;
242 core->init( iInitialCapacity );
243 }
244
245 Heap( const MyType &rSrc ) :
246 SharedCore<MyType, Core>( rSrc )
247 {
248 }
249
250 virtual ~Heap()
251 {
252 }
253
254 virtual void enqueue( const item &it )
255 {
256 _hardCopy();
257
258 core->enqueue( it );
259 }
260
261 virtual item &peek()
262 {
263 _hardCopy();
264
265 if( core->iFill == 0 )
266 throw HeapException("Heap empty.");
267 return core->aItem[0];
268 }
269
270 virtual const item &peek() const
271 {
272 if( core->iFill == 0 )
273 throw HeapException("Heap empty.");
274 return core->aItem[0];
275 }
276
277 virtual item dequeue()
278 {
279 _hardCopy();
280
281 return core->dequeue();
282 }
283
177 virtual bool isEmpty() const 284 virtual bool isEmpty() const
178 { 285 {
179 return (iFill==0); 286 return (core->iFill==0);
180 } 287 }
181 288
182 virtual int getSize() const 289 virtual int getSize() const
183 { 290 {
184 return iFill; 291 return core->iFill;
185 } 292 }
186 293
187 class iterator 294 class iterator
@@ -201,7 +308,7 @@ namespace Bu
201 { 308 {
202 if( pHeap == NULL ) 309 if( pHeap == NULL )
203 throw Bu::ExceptionBase("Iterator not initialized."); 310 throw Bu::ExceptionBase("Iterator not initialized.");
204 if( iIndex < 0 || iIndex >= pHeap->iFill ) 311 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
205 throw Bu::ExceptionBase("Iterator out of bounds."); 312 throw Bu::ExceptionBase("Iterator out of bounds.");
206 } 313 }
207 314
@@ -230,12 +337,16 @@ namespace Bu
230 337
231 item &operator*() 338 item &operator*()
232 { 339 {
233 return pHeap->aItem[iIndex]; 340 pHeap->_hardCopy();
341
342 return pHeap->core->aItem[iIndex];
234 } 343 }
235 344
236 item *operator->() 345 item *operator->()
237 { 346 {
238 return &(pHeap->aItem[iIndex]); 347 pHeap->_hardCopy();
348
349 return &(pHeap->core->aItem[iIndex]);
239 } 350 }
240 351
241 iterator &operator++() 352 iterator &operator++()
@@ -260,7 +371,7 @@ namespace Bu
260 { 371 {
261 checkValid(); 372 checkValid();
262 iIndex++; 373 iIndex++;
263 if( iIndex >= pHeap->iFill ) 374 if( iIndex >= pHeap->core->iFill )
264 iIndex = -1; 375 iIndex = -1;
265 376
266 return *this; 377 return *this;
@@ -279,7 +390,7 @@ namespace Bu
279 checkValid(); 390 checkValid();
280 iterator ret( *this ); 391 iterator ret( *this );
281 ret.iIndex += iDelta; 392 ret.iIndex += iDelta;
282 if( ret.iIndex >= pHeap->iFill ) 393 if( ret.iIndex >= pHeap->core->iFill )
283 ret.iIndex = -1; 394 ret.iIndex = -1;
284 return ret; 395 return ret;
285 } 396 }
@@ -294,12 +405,12 @@ namespace Bu
294 return ret; 405 return ret;
295 } 406 }
296 407
297 operator bool() 408 operator bool() const
298 { 409 {
299 return iIndex != -1; 410 return iIndex != -1;
300 } 411 }
301 412
302 bool isValid() 413 bool isValid() const
303 { 414 {
304 return iIndex != -1; 415 return iIndex != -1;
305 } 416 }
@@ -328,7 +439,7 @@ namespace Bu
328 { 439 {
329 if( pHeap == NULL ) 440 if( pHeap == NULL )
330 throw Bu::ExceptionBase("Iterator not initialized."); 441 throw Bu::ExceptionBase("Iterator not initialized.");
331 if( iIndex < 0 || iIndex >= pHeap->iFill ) 442 if( iIndex < 0 || iIndex >= pHeap->core->iFill )
332 throw Bu::ExceptionBase("Iterator out of bounds."); 443 throw Bu::ExceptionBase("Iterator out of bounds.");
333 } 444 }
334 445
@@ -363,19 +474,23 @@ namespace Bu
363 474
364 const item &operator*() 475 const item &operator*()
365 { 476 {
366 return pHeap->aItem[iIndex]; 477 pHeap->_hardCopy();
478
479 return pHeap->core->aItem[iIndex];
367 } 480 }
368 481
369 const item *operator->() 482 const item *operator->()
370 { 483 {
371 return &(pHeap->aItem[iIndex]); 484 pHeap->_hardCopy();
485
486 return &(pHeap->core->aItem[iIndex]);
372 } 487 }
373 488
374 const_iterator &operator++() 489 const_iterator &operator++()
375 { 490 {
376 checkValid(); 491 checkValid();
377 iIndex++; 492 iIndex++;
378 if( iIndex >= pHeap->iFill ) 493 if( iIndex >= pHeap->core->iFill )
379 iIndex = -1; 494 iIndex = -1;
380 495
381 return *this; 496 return *this;
@@ -393,7 +508,7 @@ namespace Bu
393 { 508 {
394 checkValid(); 509 checkValid();
395 iIndex++; 510 iIndex++;
396 if( iIndex >= pHeap->iFill ) 511 if( iIndex >= pHeap->core->iFill )
397 iIndex = -1; 512 iIndex = -1;
398 513
399 return *this; 514 return *this;
@@ -427,12 +542,12 @@ namespace Bu
427 return ret; 542 return ret;
428 } 543 }
429 544
430 operator bool() 545 operator bool() const
431 { 546 {
432 return iIndex != -1; 547 return iIndex != -1;
433 } 548 }
434 549
435 bool isValid() 550 bool isValid() const
436 { 551 {
437 return iIndex != -1; 552 return iIndex != -1;
438 } 553 }
@@ -452,14 +567,14 @@ namespace Bu
452 567
453 iterator begin() 568 iterator begin()
454 { 569 {
455 if( iFill == 0 ) 570 if( core->iFill == 0 )
456 return end(); 571 return end();
457 return iterator( this, 0 ); 572 return iterator( this, 0 );
458 } 573 }
459 574
460 const_iterator begin() const 575 const_iterator begin() const
461 { 576 {
462 if( iFill == 0 ) 577 if( core->iFill == 0 )
463 return end(); 578 return end();
464 return const_iterator( this, 0 ); 579 return const_iterator( this, 0 );
465 } 580 }
@@ -475,31 +590,22 @@ namespace Bu
475 } 590 }
476 591
477 592
478 private: 593 protected:
479 void upSize() 594 virtual Core *_copyCore( Core *src )
480 { 595 {
481 item *aNewItems = ia.allocate( iSize*2+1 ); 596 Core *pRet = _allocateCore();
482 // 597
483 // We cannot use a memcopy here because we don't know what kind 598 pRet->iSize = src->iSize;
484 // of datastructures are being used, we have to copy them one at 599 pRet->iFill = src->iFill;
485 // a time. 600 pRet->cmp = src->cmp;
486 // 601 pRet->aItem = pRet->ia.allocate( pRet->iSize );
487 for( int j = 0; j < iFill; j++ ) 602 for( int j = 0; j < pRet->iFill; j++ )
488 { 603 {
489 ia.construct( &aNewItems[j], aItem[j] ); 604 pRet->ia.construct( &pRet->aItem[j], src->aItem[j] );
490 ia.destroy( &aItem[j] );
491 } 605 }
492 ia.deallocate( aItem, iSize );
493 aItem = aNewItems;
494 iSize = iSize*2+1;
495 }
496 606
497 private: 607 return pRet;
498 int iSize; 608 }
499 int iFill;
500 item *aItem;
501 cmpfunc cmp;
502 itemalloc ia;
503 }; 609 };
504}; 610};
505 611
diff --git a/src/httpget.h b/src/httpget.h
index 410914c..783f880 100644
--- a/src/httpget.h
+++ b/src/httpget.h
@@ -11,7 +11,7 @@
11#include "bu/stream.h" 11#include "bu/stream.h"
12#include "bu/fstring.h" 12#include "bu/fstring.h"
13#include "bu/url.h" 13#include "bu/url.h"
14#include "bu/socket.h" 14#include "bu/tcpsocket.h"
15#include "bu/hash.h" 15#include "bu/hash.h"
16 16
17namespace Bu 17namespace Bu
@@ -52,7 +52,7 @@ namespace Bu
52 private: 52 private:
53 Bu::Url uSrc; 53 Bu::Url uSrc;
54 Bu::FString sMethod; 54 Bu::FString sMethod;
55 Bu::Socket sSrv; 55 Bu::TcpSocket sSrv;
56 typedef Bu::Hash<Bu::FString,Bu::FString> MimeHash; 56 typedef Bu::Hash<Bu::FString,Bu::FString> MimeHash;
57 MimeHash hMimeIn; 57 MimeHash hMimeIn;
58 MimeHash hMimeOut; 58 MimeHash hMimeOut;
diff --git a/src/itoserver.cpp b/src/itoserver.cpp
index a1d804a..ea737bf 100644
--- a/src/itoserver.cpp
+++ b/src/itoserver.cpp
@@ -7,9 +7,9 @@
7 7
8#include "bu/itoserver.h" 8#include "bu/itoserver.h"
9#include <errno.h> 9#include <errno.h>
10#include "bu/serversocket.h" 10#include "bu/tcpserversocket.h"
11#include "bu/client.h" 11#include "bu/client.h"
12#include "bu/socket.h" 12#include "bu/tcpsocket.h"
13 13
14#include "bu/config.h" 14#include "bu/config.h"
15 15
@@ -41,7 +41,7 @@ Bu::ItoServer::~ItoServer()
41 41
42void Bu::ItoServer::addPort( int nPort, int nPoolSize ) 42void Bu::ItoServer::addPort( int nPort, int nPoolSize )
43{ 43{
44 ServerSocket *s = new ServerSocket( nPort, nPoolSize ); 44 TcpServerSocket *s = new TcpServerSocket( nPort, nPoolSize );
45 int nSocket = s->getSocket(); 45 int nSocket = s->getSocket();
46 FD_SET( nSocket, &fdActive ); 46 FD_SET( nSocket, &fdActive );
47 hServers.insert( nSocket, s ); 47 hServers.insert( nSocket, s );
@@ -49,7 +49,7 @@ void Bu::ItoServer::addPort( int nPort, int nPoolSize )
49 49
50void Bu::ItoServer::addPort( const FString &sAddr, int nPort, int nPoolSize ) 50void Bu::ItoServer::addPort( const FString &sAddr, int nPort, int nPoolSize )
51{ 51{
52 ServerSocket *s = new ServerSocket( sAddr, nPort, nPoolSize ); 52 TcpServerSocket *s = new TcpServerSocket( sAddr, nPort, nPoolSize );
53 int nSocket = s->getSocket(); 53 int nSocket = s->getSocket();
54 FD_SET( nSocket, &fdActive ); 54 FD_SET( nSocket, &fdActive );
55 hServers.insert( nSocket, s ); 55 hServers.insert( nSocket, s );
@@ -92,7 +92,7 @@ void Bu::ItoServer::run()
92 { 92 {
93 if( FD_ISSET( i.getKey(), &fdRead ) ) 93 if( FD_ISSET( i.getKey(), &fdRead ) )
94 { 94 {
95 ServerSocket *pSrv = i.getValue(); 95 TcpServerSocket *pSrv = i.getValue();
96 addClient( pSrv->accept(), pSrv->getPort() ); 96 addClient( pSrv->accept(), pSrv->getPort() );
97 } 97 }
98 } 98 }
@@ -126,7 +126,7 @@ Bu::ItoServer::ItoClient::ItoClient( ItoServer &rSrv, int iSocket, int iPort,
126 FD_SET( iSocket, &fdActive ); 126 FD_SET( iSocket, &fdActive );
127 127
128 pClient = new Client( 128 pClient = new Client(
129 new Bu::Socket( iSocket ), 129 new Bu::TcpSocket( iSocket ),
130 new SrvClientLinkFactory( rSrv ) 130 new SrvClientLinkFactory( rSrv )
131 ); 131 );
132} 132}
diff --git a/src/itoserver.h b/src/itoserver.h
index c08d453..81e42cc 100644
--- a/src/itoserver.h
+++ b/src/itoserver.h
@@ -26,8 +26,8 @@
26 26
27namespace Bu 27namespace Bu
28{ 28{
29 class ServerSocket; 29 class TcpServerSocket;
30 class Socket; 30 class TcpSocket;
31 class Client; 31 class Client;
32 32
33 /** 33 /**
@@ -126,7 +126,7 @@ namespace Bu
126 int nTimeoutSec; 126 int nTimeoutSec;
127 int nTimeoutUSec; 127 int nTimeoutUSec;
128 fd_set fdActive; 128 fd_set fdActive;
129 typedef Hash<int,ServerSocket *> ServerHash; 129 typedef Hash<int,TcpServerSocket *> ServerHash;
130 ServerHash hServers; 130 ServerHash hServers;
131 typedef Hash<int,ItoClient *> ClientHash; 131 typedef Hash<int,ItoClient *> ClientHash;
132 typedef ItoQueue<ItoClient *> ClientQueue; 132 typedef ItoQueue<ItoClient *> ClientQueue;
diff --git a/src/lexer.h b/src/lexer.h
index 2cb5f51..9840afe 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -36,6 +36,10 @@ namespace Bu
36 } 36 }
37 TokenType iToken; 37 TokenType iToken;
38 Bu::Variant vExtra; 38 Bu::Variant vExtra;
39 int iStartCol;
40 int iStartRow;
41 int iEndCol;
42 int iEndRow;
39 }; 43 };
40 44
41 virtual Token *nextToken()=0; 45 virtual Token *nextToken()=0;
diff --git a/src/list.h b/src/list.h
index 9b95983..b1e0d0f 100644
--- a/src/list.h
+++ b/src/list.h
@@ -16,6 +16,7 @@
16 16
17namespace Bu 17namespace Bu
18{ 18{
19 /** @cond DEVEL */
19 template<typename value> 20 template<typename value>
20 struct ListLink 21 struct ListLink
21 { 22 {
@@ -24,10 +25,18 @@ namespace Bu
24 ListLink *pPrev; 25 ListLink *pPrev;
25 }; 26 };
26 27
27 template<typename value, typename valuealloc, 28 template<typename value, typename valuealloc, typename linkalloc>
28 typename linkalloc> 29 class List;
30
31 template<typename value, typename valuealloc, typename linkalloc>
29 struct ListCore 32 struct ListCore
30 { 33 {
34 friend class List<value, valuealloc, linkalloc>;
35 friend class SharedCore<
36 List<value, valuealloc, linkalloc>,
37 ListCore<value, valuealloc, linkalloc>
38 >;
39 private:
31 typedef struct ListLink<value> Link; 40 typedef struct ListLink<value> Link;
32 ListCore() : 41 ListCore() :
33 pFirst( NULL ), 42 pFirst( NULL ),
@@ -177,6 +186,7 @@ namespace Bu
177 } 186 }
178 } 187 }
179 }; 188 };
189 /** @endcond */
180 190
181 /** 191 /**
182 * Linked list template container. This class is similar to the stl list 192 * Linked list template container. This class is similar to the stl list
@@ -189,12 +199,15 @@ namespace Bu
189 *@param value (typename) The type of data to store in your list 199 *@param value (typename) The type of data to store in your list
190 *@param valuealloc (typename) Memory Allocator for your value type 200 *@param valuealloc (typename) Memory Allocator for your value type
191 *@param linkalloc (typename) Memory Allocator for the list links. 201 *@param linkalloc (typename) Memory Allocator for the list links.
202 *@extends SharedCore
192 *@ingroup Containers 203 *@ingroup Containers
193 */ 204 */
194 template<typename value, typename valuealloc=std::allocator<value>, 205 template<typename value, typename valuealloc=std::allocator<value>,
195 typename linkalloc=std::allocator<struct ListLink<value> > > 206 typename linkalloc=std::allocator<struct ListLink<value> > >
196 class List : public SharedCore< struct ListCore<value, valuealloc, 207 class List /** @cond */ : public SharedCore<
197 linkalloc> > 208 List<value, valuealloc, linkalloc>,
209 ListCore<value, valuealloc, linkalloc>
210 > /** @endcond */
198 { 211 {
199 private: 212 private:
200 typedef struct ListLink<value> Link; 213 typedef struct ListLink<value> Link;
@@ -202,9 +215,9 @@ namespace Bu
202 typedef struct ListCore<value, valuealloc, linkalloc> Core; 215 typedef struct ListCore<value, valuealloc, linkalloc> Core;
203 216
204 protected: 217 protected:
205 using SharedCore< Core >::core; 218 using SharedCore<MyType, Core>::core;
206 using SharedCore< Core >::_hardCopy; 219 using SharedCore<MyType, Core>::_hardCopy;
207 using SharedCore< Core >::_allocateCore; 220 using SharedCore<MyType, Core>::_allocateCore;
208 221
209 public: 222 public:
210 struct const_iterator; 223 struct const_iterator;
@@ -215,7 +228,7 @@ namespace Bu
215 } 228 }
216 229
217 List( const MyType &src ) : 230 List( const MyType &src ) :
218 SharedCore< Core >( src ) 231 SharedCore<MyType, Core >( src )
219 { 232 {
220 } 233 }
221 234
diff --git a/src/listhash.cpp b/src/listhash.cpp
deleted file mode 100644
index b798a1f..0000000
--- a/src/listhash.cpp
+++ /dev/null
@@ -1,8 +0,0 @@
1/*
2 * Copyright (C) 2007-2010 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8
diff --git a/src/listhash.h b/src/listhash.h
deleted file mode 100644
index e5ec4ee..0000000
--- a/src/listhash.h
+++ /dev/null
@@ -1,54 +0,0 @@
1/*
2 * Copyright (C) 2007-2010 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_LIST_HASH_H
9#define BU_LIST_HASH_H
10
11#include "bu/hash.h"
12#include "bu/list.h"
13
14namespace Bu
15{
16 template<typename key, typename value, typename sizecalc = __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename valuealloc = std::allocator<Bu::List<value> >, typename challoc = std::allocator<uint32_t> >
17 class ListHash : public Hash<key, Bu::List<value>, sizecalc, keyalloc, valuealloc, challoc>
18 {
19 typedef Hash<key, Bu::List<value>, sizecalc, keyalloc, valuealloc, challoc> ParentType;
20 public:
21 ListHash()
22 {
23 }
24
25 ListHash( const ListHash &src ) :
26 ParentType( src )
27 {
28 }
29
30 virtual ~ListHash()
31 {
32 }
33
34 ListHash &operator=( const ListHash &src )
35 {
36 *dynamic_cast<ParentType *>(this) =
37 dynamic_cast<ParentType &>(src);
38 }
39
40 virtual void insert( const key &k, const value &v )
41 {
42 if( !has( k ) )
43 {
44 ParentType::insert( k, List<value>() );
45 }
46 get( k ).append( v );
47 }
48
49 private:
50 };
51
52};
53
54#endif
diff --git a/src/myriad.h b/src/myriad.h
index 3d203bb..582d310 100644
--- a/src/myriad.h
+++ b/src/myriad.h
@@ -46,7 +46,7 @@ namespace Bu
46 * Header format is as follows: 46 * Header format is as follows:
47 * 47 *
48 * MMMMvBssssSSSS* 48 * MMMMvBssssSSSS*
49 * M = Magic number (FFC399BD) 49 * M = Magic number (0AD3FA84)
50 * v = version number 50 * v = version number
51 * B = Bits per int 51 * B = Bits per int
52 * s = Blocksize in bytes 52 * s = Blocksize in bytes
diff --git a/src/myriadfs.cpp b/src/myriadfs.cpp
new file mode 100644
index 0000000..af60c08
--- /dev/null
+++ b/src/myriadfs.cpp
@@ -0,0 +1,78 @@
1#include "bu/myriadfs.h"
2#include "bu/myriadstream.h"
3
4#include <string.h>
5#include <unistd.h>
6
7namespace Bu { subExceptionDef( MyriadFsException ) }
8
9#define Myriad_Fs_MAGIC_CODE ((char *)"\xa7\x18\x8b\x39")
10
11Bu::MyriadFs::MyriadFs( Bu::Stream &rStore, int iBlockSize ) :
12 rStore( rStore ),
13 mStore( rStore, iBlockSize )
14{
15 if( mStore.hasStream( 1 ) )
16 {
17 // Check to see if this is a MyriadFs stream.
18 Bu::MyriadStream ms = mStore.openStream( 1 );
19 char sMagic[4];
20 if( ms.read( sMagic, 4 ) < 4 )
21 throw MyriadFsException("The provided stream does not appear to be "
22 "a MyriadFs stream.");
23 if( ::strncmp( sMagic, Myriad_Fs_MAGIC_CODE, 4 ) )
24 throw MyriadFsException("The provided stream does not appear to be "
25 "a MyriadFs stream.");
26
27 int8_t iVer;
28 }
29 else
30 {
31 // Create initial header stream
32 {
33 mStore.createStream( 1 );
34 Bu::MyriadStream ms = mStore.openStream( 1 );
35 ms.write( Myriad_Fs_MAGIC_CODE, 4 );
36 int8_t iVer = 1;
37 int32_t iTmp = 1;
38 ms.write( &iVer, 1 );
39 ms.write( &iBlockSize, 4 );
40 ms.write( &iTmp, 4 ); // iNumNodes
41 iTmp = 0;
42 ms.write( &iTmp, 4 ); // iInode
43 ms.write( &iTmp, 0 ); // iPosition
44 }
45
46 // Create initial inode stream, with one root node.
47 {
48 mStore.createStream( 2 );
49 Bu::MyriadStream ms = mStore.openStream( 2 );
50 int32_t iUser = 0, iGroup = 0;
51#ifndef WIN32
52 iUser = getuid();
53 iGroup = getgid();
54#endif
55 int32_t iTmp32 = 0;
56 int16_t iTmp16 = 0;
57 ms.write( &iUser, 4 );
58 ms.write( &iGroup, 4 );
59 ms.write( &iTmp16, 2 );
60 ms.write( &iTmp16, 2 );
61 iTmp32 = 3;
62 ms.write( &iTmp32, 4 );
63 iTmp32 = 0;
64 ms.write( &iTmp32, 4 );
65 ms.write( &iTmp16, 2 );
66 }
67
68 // Create inode 0's storage stream.
69 {
70 mStore.createStream( 3 );
71 }
72 }
73}
74
75Bu::MyriadFs::~MyriadFs()
76{
77}
78
diff --git a/src/myriadfs.h b/src/myriadfs.h
new file mode 100644
index 0000000..42a3493
--- /dev/null
+++ b/src/myriadfs.h
@@ -0,0 +1,54 @@
1#ifndef MYRIAD_FS_H
2#define MYRIAD_FS_H
3
4#include "bu/myriad.h"
5
6namespace Bu
7{
8 class Stream;
9
10 subExceptionDecl( MyriadFsException );
11
12 /**
13 * A POSIX compliant, node based filesystem built on top of Myriad.
14 *
15 * A header is placed into stream 1.
16 * Header format:
17 * int32_t iMagicHeader (A7188B39)
18 * int8_t iVersion (1)
19 * int32_t iNodeSize
20 * int32_t iNumNodes
21 * NodeLookup[iNumNodes] nNode
22 *
23 * Node lookup:
24 * int32_t iInode
25 * int32_t iPosition
26 *
27 * The node headers or inode structures have a base size of 22 bytes.
28 * Everything else in the block is used for the name. I.e. if you have
29 * a blocksize of 512 bytes then you wind up with a max name size of
30 * 512-22=490 characters, or a blocksize of 256 gives you 234 chraacters
31 * as a max. The node headers are all stored in stream 2.
32 * Basic node header format:
33 * int32_t iUser
34 * int32_t iGroup
35 * int16_t iMeta
36 * int16_t iPerms
37 * int32_t iStreamIndex
38 * int32_t iParentNode
39 * int16_t iNameSize
40 * char[iNameSize] sName
41 */
42 class MyriadFs
43 {
44 public:
45 MyriadFs( Bu::Stream &rStore, int iBlockSize=512 );
46 virtual ~MyriadFs();
47
48 private:
49 Bu::Stream &rStore;
50 Bu::Myriad mStore;
51 };
52};
53
54#endif
diff --git a/src/newline.h b/src/newline.h
index b69cdb5..243c876 100644
--- a/src/newline.h
+++ b/src/newline.h
@@ -14,7 +14,7 @@ namespace Bu
14{ 14{
15 /** 15 /**
16 * Converts new-line characters from any standard convention into linefeeds 16 * Converts new-line characters from any standard convention into linefeeds
17 * (\n) on reading, and converts them to either your OS's standard or a 17 * (\\n) on reading, and converts them to either your OS's standard or a
18 * specified standard, depending on how you construct the class. 18 * specified standard, depending on how you construct the class.
19 * 19 *
20 * If you're reading in a text file, then this filter is practically 20 * If you're reading in a text file, then this filter is practically
diff --git a/src/paramproc.cpp b/src/paramproc.cpp
deleted file mode 100644
index f4fd36e..0000000
--- a/src/paramproc.cpp
+++ /dev/null
@@ -1,523 +0,0 @@
1/*
2 * Copyright (C) 2007-2010 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#include "bu/paramproc.h"
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12
13#define ptrtype( iitype, iiname ) \
14 Bu::ParamProc::ParamPtr::ParamPtr( iitype *iiname ) : \
15 type( vt ##iiname ) { val.iiname = iiname; }
16
17Bu::ParamProc::ParamPtr::ParamPtr()
18{
19 val.str = NULL;
20 type = vtunset;
21}
22
23ptrtype( Bu::FString, str );
24ptrtype( uint64_t, uint64 );
25ptrtype( uint32_t, uint32 );
26ptrtype( uint16_t, uint16 );
27ptrtype( uint8_t, uint8 );
28ptrtype( int64_t, int64 );
29ptrtype( int32_t, int32 );
30ptrtype( int16_t, int16 );
31ptrtype( int8_t, int8 );
32ptrtype( float, float32 );
33ptrtype( double, float64 );
34ptrtype( long double, float96 );
35ptrtype( bool, bln );
36
37Bu::ParamProc::ParamPtr &Bu::ParamProc::ParamPtr::operator=( ParamProc::ParamPtr &ptr )
38{
39 val = ptr.val;
40 type = ptr.type;
41
42 return *this;
43}
44
45bool Bu::ParamProc::ParamPtr::isSet()
46{
47 return type != vtunset;
48}
49
50Bu::ParamProc::ParamPtr &Bu::ParamProc::ParamPtr::operator=( const char *str )
51{
52 if( !isSet() ) return *this;
53 switch( type )
54 {
55 case vtstr:
56 (*val.str) = str;
57 break;
58
59 case vtuint64:
60 (*val.uint64) = strtoull( str, NULL, 10 );
61 break;
62
63 case vtuint32:
64 (*val.uint32) = strtoul( str, NULL, 10 );
65 break;
66
67 case vtuint16:
68 (*val.uint16) = (uint16_t)strtoul( str, NULL, 10 );
69 break;
70
71 case vtuint8:
72 (*val.uint8) = (uint8_t)strtoul( str, NULL, 10 );
73 break;
74
75 case vtint64:
76 (*val.int64) = strtoll( str, NULL, 10 );
77 break;
78
79 case vtint32:
80 (*val.int32) = strtol( str, NULL, 10 );
81 break;
82
83 case vtint16:
84 (*val.int16) = (int16_t)strtol( str, NULL, 10 );
85 break;
86
87 case vtint8:
88 (*val.int8) = (int8_t)strtol( str, NULL, 10 );
89 break;
90
91 case vtfloat32:
92 (*val.float32) = strtof( str, NULL );
93 break;
94
95 case vtfloat64:
96 (*val.float64) = strtod( str, NULL );
97 break;
98
99 case vtfloat96:
100 (*val.float96) = strtold( str, NULL );
101 break;
102
103 case vtbln:
104 if( strcasecmp("yes", str ) == 0 ||
105 strcasecmp("true", str ) == 0 )
106 {
107 (*val.bln) = true;
108 }
109 else
110 {
111 (*val.bln) = false;
112 }
113 break;
114 }
115
116 return *this;
117}
118
119Bu::ParamProc::ParamProc()
120{
121}
122
123Bu::ParamProc::~ParamProc()
124{
125 for( Bu::List<ArgSpec *>::iterator i = lArg.begin();
126 i != lArg.end(); i++ )
127 {
128 delete *i;
129 }
130
131 for( Bu::List<Banner *>::iterator i = lBan.begin();
132 i != lBan.end(); i++ )
133 {
134 delete *i;
135 }
136
137}
138/*
139void Bu::ParamProc::addParam( const char *lpWord, char cChar, Proc proc, ParamPtr val )
140{
141 printf("Calling callback...\n");
142 val = "Hello there, this is set in the ParamProc";
143 (this->*proc)();
144}*/
145
146void Bu::ParamProc::addParam( const char *lpWord, char cChar, Proc proc,
147 ParamPtr val, const char *lpDesc, const char *lpExtra,
148 const char *lpValue )
149{
150 ArgSpec *as = new ArgSpec;
151 if( lpWord )
152 as->sWord = lpWord;
153
154 as->cChar = cChar;
155 as->proc = proc;
156 as->val = val;
157 if( lpDesc )
158 as->sDesc = lpDesc;
159 if( lpExtra )
160 as->sExtra = lpExtra;
161 if( lpValue )
162 as->sValue = lpValue;
163
164 lArg.append( as );
165
166 if( !lBan.isEmpty() )
167 {
168 if( lBan.last()->pBefore == NULL )
169 lBan.last()->pBefore = as;
170 }
171}
172
173void Bu::ParamProc::addParam( const char *lpWord, char cChar, Proc proc,
174 const char *lpDesc, const char *lpExtra,
175 const char *lpValue )
176{
177 addParam( lpWord, cChar, proc, ParamPtr(), lpDesc, lpExtra, lpValue );
178}
179
180void Bu::ParamProc::addParam( const char *lpWord, char cChar, ParamPtr val,
181 const char *lpDesc, const char *lpExtra,
182 const char *lpValue )
183{
184 addParam( lpWord, cChar, NULL, val, lpDesc, lpExtra, lpValue );
185}
186
187void Bu::ParamProc::addParam( const char *lpWord, Proc proc, ParamPtr val,
188 const char *lpDesc, const char *lpExtra,
189 const char *lpValue )
190{
191 addParam( lpWord, '\0', proc, val, lpDesc, lpExtra, lpValue );
192}
193
194void Bu::ParamProc::addParam( const char *lpWord, Proc proc,
195 const char *lpDesc, const char *lpExtra,
196 const char *lpValue )
197{
198 addParam( lpWord, '\0', proc, ParamPtr(), lpDesc, lpExtra, lpValue );
199}
200
201void Bu::ParamProc::addParam( const char *lpWord, ParamPtr val,
202 const char *lpDesc, const char *lpExtra,
203 const char *lpValue )
204{
205 addParam( lpWord, '\0', NULL, val, lpDesc, lpExtra, lpValue );
206}
207
208void Bu::ParamProc::addParam( char cChar, Proc proc, ParamPtr val,
209 const char *lpDesc, const char *lpExtra,
210 const char *lpValue )
211{
212 addParam( NULL, cChar, proc, val, lpDesc, lpExtra, lpValue );
213}
214
215void Bu::ParamProc::addParam( char cChar, Proc proc,
216 const char *lpDesc, const char *lpExtra,
217 const char *lpValue )
218{
219 addParam( NULL, cChar, proc, ParamPtr(), lpDesc, lpExtra, lpValue );
220}
221
222void Bu::ParamProc::addParam( char cChar, ParamPtr val,
223 const char *lpDesc, const char *lpExtra,
224 const char *lpValue )
225{
226 addParam( NULL, cChar, NULL, val, lpDesc, lpExtra, lpValue );
227}
228
229void Bu::ParamProc::process( int argc, char *argv[] )
230{
231 for( int arg = 1; arg < argc; arg++ )
232 {
233 //printf(":::%d:::%s\n", arg, argv[arg] );
234 if( argv[arg][0] == '-' )
235 {
236 if( argv[arg][1] == '-' )
237 {
238 ArgSpec *s = checkWord( argv[arg]+2 );
239 if( s )
240 {
241 if( argv[arg][s->sWord.getSize()+2] == '=' )
242 {
243 if( s->val.isSet() )
244 {
245 if( s->sValue == "" )
246 {
247 s->val = argv[arg]+s->sWord.getSize()+3;
248 }
249 else
250 {
251 s->val = s->sValue.getStr();
252 }
253 }
254 if( s->proc )
255 {
256 char **tmp = new char*[argc-arg];
257 tmp[0] = argv[arg]+s->sWord.getSize()+3;
258 for( int k = 1; k < argc-arg; k++ )
259 tmp[k] = argv[arg+k];
260 int ret = (this->*s->proc)( argc-arg, tmp );
261 if( ret > 0 )
262 {
263 arg += ret-1;
264 }
265 delete tmp;
266 }
267 }
268 else
269 {
270 int add = 0;
271 if( s->val.isSet() )
272 {
273 if( s->sValue == "" )
274 {
275 if( arg+1 >= argc )
276 {
277 return;
278 }
279 s->val = argv[arg+1];
280 add++;
281 }
282 else
283 {
284 s->val = s->sValue.getStr();
285 }
286 }
287 if( s->proc )
288 {
289 int ret = (this->*s->proc)(
290 argc-arg-1, argv+arg+1 );
291
292 if( ret > add )
293 add = 0;
294 else
295 add -= ret;
296 arg += ret;
297 }
298 arg += add;
299 }
300 continue;
301 }
302 else
303 {
304 unknownParam( argc-arg, argv+arg );
305 }
306 }
307 else
308 {
309 for( int chr = 1; argv[arg][chr]; chr++ )
310 {
311 ArgSpec *s = checkLetr( argv[arg][chr] );
312 if( s )
313 {
314 if( argv[arg][chr+1] != '\0' )
315 {
316 bool bUsed = false;
317 if( s->val.isSet() )
318 {
319 if( s->sValue == "" )
320 {
321 s->val = argv[arg]+chr+1;
322 bUsed = true;
323 }
324 else
325 {
326 s->val = s->sValue.getStr();
327 }
328 }
329 if( s->proc )
330 {
331 char **tmp = new char*[argc-arg];
332 tmp[0] = argv[arg]+chr+1;
333 for( int k = 1; k < argc-arg; k++ )
334 tmp[k] = argv[arg+k];
335 int ret = (this->*s->proc)( argc-arg, tmp );
336 if( ret > 0 )
337 {
338 arg += ret - 1;
339 delete tmp;
340 break;
341 }
342 delete tmp;
343 }
344 if( bUsed )
345 {
346 break;
347 }
348 }
349 else
350 {
351 bool bUsed = false;
352 if( s->val.isSet() )
353 {
354 if( s->sValue == "" )
355 {
356 s->val = argv[arg+1];
357 bUsed = true;
358 }
359 else
360 {
361 s->val = s->sValue.getStr();
362 }
363 }
364 if( s->proc )
365 {
366 int ret = (this->*s->proc)(
367 argc-arg-1, argv+arg+1
368 );
369 if( ret > 0 )
370 {
371 arg += ret;
372 break;
373 }
374 }
375 if( bUsed )
376 {
377 arg++;
378 break;
379 }
380 }
381 }
382 else
383 {
384 unknownParam( argc-arg, argv+arg );
385 }
386 }
387 }
388 }
389 else
390 {
391 cmdParam( argc-arg, argv+arg );
392 }
393 }
394}
395
396Bu::ParamProc::ArgSpec *Bu::ParamProc::checkWord( const char *arg )
397{
398 //printf("Checking \"%s\"...\n", arg );
399 Bu::List<ArgSpec *>::const_iterator i = lArg.begin();
400 for( ; i != lArg.end(); i++ )
401 {
402 if( (*i)->sWord == "" )
403 continue;
404
405 if( !strcmp( (*i)->sWord.getStr(), arg ) )
406 return *i;
407
408 if( (*i)->val.isSet() )
409 {
410 if( !strncmp( (*i)->sWord.getStr(), arg, (*i)->sWord.getSize() ) &&
411 arg[(*i)->sWord.getSize()] == '=' )
412 {
413 return *i;
414 }
415 }
416 }
417
418 return NULL;
419}
420
421Bu::ParamProc::ArgSpec *Bu::ParamProc::checkLetr( const char arg )
422{
423 //printf("Checking \'%c\'...\n", arg );
424 Bu::List<ArgSpec *>::const_iterator i = lArg.begin();
425 for( ; i != lArg.end(); i++ )
426 {
427 if( (*i)->cChar == '\0' )
428 continue;
429
430 if( (*i)->cChar == arg )
431 {
432 return *i;
433 }
434 }
435
436 return NULL;
437}
438
439int Bu::ParamProc::cmdParam( int /*argc*/, char *argv[] )
440{
441 printf("Unhandled command parameter \"%s\" found!\n", argv[0] );
442 return 0;
443}
444
445int Bu::ParamProc::unknownParam( int /*argc*/, char *argv[] )
446{
447 printf("Unknown parameter \"%s\" found!\n", argv[0] );
448 return 0;
449}
450
451int Bu::ParamProc::help( int /*argc*/, char * /*argv*/ [] )
452{
453 Bu::List<Banner *>::const_iterator b = lBan.begin();
454 Bu::List<ArgSpec *>::const_iterator i = lArg.begin();
455 int len=0;
456 for( ; i != lArg.end(); i++ )
457 {
458 if( len < (*i)->sWord.getSize() + (*i)->sExtra.getSize() )
459 len = (*i)->sWord.getSize() + (*i)->sExtra.getSize();
460 }
461 char fmt[10];
462 sprintf( fmt, "%%-%ds ", len );
463
464 for( i = lArg.begin(); i != lArg.end(); i++ )
465 {
466 if( b != lBan.end() )
467 {
468 if( (*b)->pBefore == (*i) )
469 {
470 printf( (*b)->sBanner.getStr() );
471 b++;
472 }
473 }
474 printf(" ");
475 if( (*i)->cChar )
476 {
477 if( (*i)->sWord.getStr() )
478 {
479 printf("-%c, ", (*i)->cChar );
480 }
481 else
482 {
483 printf("-%c ", (*i)->cChar );
484 }
485 }
486 else
487 {
488 printf(" ");
489 }
490 if( (*i)->sWord.getStr() )
491 {
492 printf("--");
493 Bu::FString sTmp = (*i)->sWord.getStr();
494 if( (*i)->sExtra.getStr() )
495 sTmp += (*i)->sExtra.getStr();
496 printf( fmt, sTmp.getStr() );
497 }
498 else
499 {
500 printf(" ");
501 printf(fmt, "" );
502 }
503 printf("%s\n", (*i)->sDesc.getStr() );
504 }
505 if( b != lBan.end() )
506 {
507 if( (*b)->pBefore == NULL )
508 {
509 printf( (*b)->sBanner.getStr() );
510 }
511 }
512
513 exit( 0 );
514}
515
516void Bu::ParamProc::addHelpBanner( const char *sHelpBanner )
517{
518 Banner *pBan = new Banner;
519 pBan->sBanner = sHelpBanner;
520 pBan->pBefore = NULL;
521 lBan.append( pBan );
522}
523
diff --git a/src/paramproc.h b/src/paramproc.h
deleted file mode 100644
index ddc1876..0000000
--- a/src/paramproc.h
+++ /dev/null
@@ -1,163 +0,0 @@
1/*
2 * Copyright (C) 2007-2010 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_PARAM_PROC_H
9#define BU_PARAM_PROC_H
10
11#include <stdint.h>
12#include "bu/list.h"
13#include "bu/fstring.h"
14
15namespace Bu
16{
17 class ParamProc
18 {
19 public:
20 class ParamPtr
21 {
22 public:
23 ParamPtr();
24 ParamPtr( Bu::FString *str );
25 ParamPtr( uint64_t *uint64 );
26 ParamPtr( uint32_t *uint32 );
27 ParamPtr( uint16_t *uint16 );
28 ParamPtr( uint8_t *uint8 );
29 ParamPtr( int64_t *int64 );
30 ParamPtr( int32_t *int32 );
31 ParamPtr( int16_t *int16 );
32 ParamPtr( int8_t *int8 );
33 ParamPtr( float *float32 );
34 ParamPtr( double *float64 );
35 ParamPtr( long double *float96 );
36 ParamPtr( bool *bln );
37
38 enum
39 {
40 vtunset,
41 vtstr,
42 vtuint64,
43 vtuint32,
44 vtuint16,
45 vtuint8,
46 vtint64,
47 vtint32,
48 vtint16,
49 vtint8,
50 vtfloat32,
51 vtfloat64,
52 vtfloat96,
53 vtbln,
54 };
55 ParamPtr &operator=( ParamPtr &ptr );
56 ParamPtr &operator=( const char *str );
57
58 bool isSet();
59
60 private:
61 int type;
62 union
63 {
64 Bu::FString *str;
65 uint64_t *uint64;
66 uint32_t *uint32;
67 uint16_t *uint16;
68 uint8_t *uint8;
69 int64_t *int64;
70 int32_t *int32;
71 int16_t *int16;
72 int8_t *int8;
73 float *float32;
74 double *float64;
75 long double *float96;
76 bool *bln;
77 } val;
78 };
79
80 typedef int (ParamProc::*Proc)( int, char *[] );
81
82 typedef struct ArgSpec
83 {
84 uint8_t nFlags;
85 Bu::FString sWord;
86 char cChar;
87 Proc proc;
88 ParamProc::ParamPtr val;
89 Bu::FString sExtra;
90 Bu::FString sDesc;
91 Bu::FString sValue;
92 } ArgSpec;
93
94 public:
95 DEPRECATED
96 ParamProc();
97 virtual ~ParamProc();
98
99 void addParam( const char *lpWord, char cChar, Proc proc, ParamPtr val,
100 const char *lpDesc=NULL, const char *lpExtra=NULL,
101 const char *lpValue=NULL
102 );
103 void addParam( const char *lpWord, char cChar, Proc proc,
104 const char *lpDesc=NULL, const char *lpExtra=NULL,
105 const char *lpValue=NULL
106 );
107 void addParam( const char *lpWord, char cChar, ParamPtr val,
108 const char *lpDesc=NULL, const char *lpExtra=NULL,
109 const char *lpValue=NULL
110 );
111
112 void addParam( const char *lpWord, Proc proc, ParamPtr val,
113 const char *lpDesc=NULL, const char *lpExtra=NULL,
114 const char *lpValue=NULL
115 );
116 void addParam( const char *lpWord, Proc proc,
117 const char *lpDesc=NULL, const char *lpExtra=NULL,
118 const char *lpValue=NULL
119 );
120 void addParam( const char *lpWord, ParamPtr val,
121 const char *lpDesc=NULL, const char *lpExtra=NULL,
122 const char *lpValue=NULL
123 );
124
125 void addParam( char cChar, Proc proc, ParamPtr val,
126 const char *lpDesc=NULL, const char *lpExtra=NULL,
127 const char *lpValue=NULL
128 );
129 void addParam( char cChar, Proc proc,
130 const char *lpDesc=NULL, const char *lpExtra=NULL,
131 const char *lpValue=NULL
132 );
133 void addParam( char cChar, ParamPtr val,
134 const char *lpDesc=NULL, const char *lpExtra=NULL,
135 const char *lpValue=NULL
136 );
137
138 void process( int argc, char *argv[] );
139 void addHelpBanner( const char *sHelpBanner );
140
141 private:
142 ArgSpec *checkWord( const char *arg );
143 ArgSpec *checkLetr( const char arg );
144
145 public:
146 virtual int cmdParam( int argc, char *argv[] );
147 virtual int unknownParam( int argc, char *argv[] );
148 virtual int help( int argc, char *argv[] );
149
150 private:
151 typedef struct Banner
152 {
153 Bu::FString sBanner;
154 ArgSpec *pBefore;
155 } Banner;
156 Bu::List<Banner *> lBan;
157 Bu::List<ArgSpec *> lArg;
158 };
159}
160
161#define mkproc( cls ) static_cast<int (Bu::ParamProc::*)( int, char *[])>(&cls)
162
163#endif
diff --git a/src/parser.cpp b/src/parser.cpp
index e4e8ae5..4ad4ff9 100644
--- a/src/parser.cpp
+++ b/src/parser.cpp
@@ -22,16 +22,25 @@ void Bu::Parser::popLexer()
22 delete sLexer.peekPop(); 22 delete sLexer.peekPop();
23} 23}
24 24
25Lexer::Token *Bu::Parser::popToken()
26{
27 return sToken.peekPop();
28}
29
30void Bu::Parser::pushToken( Lexer::Token *pTok )
31{
32 sToken.push( pTok );
33}
34
25void Bu::Parser::parse() 35void Bu::Parser::parse()
26{ 36{
27 int iCurNt = iRootNonTerminal; 37 int iCurNt = iRootNonTerminal;
28 Lexer::Token *ptCur = sLexer.peek()->nextToken(); 38 Lexer::Token *ptCur = sLexer.peek()->nextToken();
29 sio << "Token: " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl; 39 sio << "Token(a): " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl;
30 selectProduction( iCurNt, ptCur ); 40 selectProduction( iCurNt, ptCur );
31 41
32 while( !sState.isEmpty() ) 42 while( !sState.isEmpty() )
33 { 43 {
34 sio << "Currently: " << *sState.peek() << sio.nl;
35 switch( (*sState.peek()).eType ) 44 switch( (*sState.peek()).eType )
36 { 45 {
37 case State::typeTerminal: 46 case State::typeTerminal:
@@ -42,7 +51,7 @@ void Bu::Parser::parse()
42 advanceState(); 51 advanceState();
43 delete ptCur; 52 delete ptCur;
44 ptCur = sLexer.peek()->nextToken(); 53 ptCur = sLexer.peek()->nextToken();
45 sio << "Token: " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl; 54 sio << "Token(b): " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl;
46 } 55 }
47 else 56 else
48 { 57 {
@@ -59,7 +68,7 @@ void Bu::Parser::parse()
59 sToken.push( ptCur ); 68 sToken.push( ptCur );
60 69
61 ptCur = sLexer.peek()->nextToken(); 70 ptCur = sLexer.peek()->nextToken();
62 sio << "Token: " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl; 71 sio << "Token(c): " << sLexer.peek()->tokenToString( *ptCur ) << sio.nl;
63 } 72 }
64 else 73 else
65 { 74 {
@@ -72,7 +81,7 @@ void Bu::Parser::parse()
72 << (*sState.peek()).iIndex << sio.nl; 81 << (*sState.peek()).iIndex << sio.nl;
73 { 82 {
74 int iNt = (*sState.peek()).iIndex; 83 int iNt = (*sState.peek()).iIndex;
75 advanceState(); 84 sio << "Current state: " << *sState.peek() << sio.nl;
76 if( !selectProduction( iNt, ptCur ) ) 85 if( !selectProduction( iNt, ptCur ) )
77 { 86 {
78 throw Bu::ExceptionBase("Error parsing code."); 87 throw Bu::ExceptionBase("Error parsing code.");
@@ -132,7 +141,11 @@ bool Bu::Parser::selectProduction( int iNt, Lexer::Token *ptCur )
132 } 141 }
133 } 142 }
134 if( nt.bCanSkip ) 143 if( nt.bCanSkip )
144 {
145 sio << "Nothing matches, skipping non-terminal." << sio.nl;
146 advanceState();
135 return true; 147 return true;
148 }
136 sio << "-->(Found nothing)" << sio.nl; 149 sio << "-->(Found nothing)" << sio.nl;
137 return false; 150 return false;
138} 151}
@@ -148,6 +161,7 @@ void Bu::Parser::advanceState()
148 sio.decIndent(); 161 sio.decIndent();
149 sState.pop(); 162 sState.pop();
150 sio << "State advanced, End of production." << sio.nl; 163 sio << "State advanced, End of production." << sio.nl;
164 advanceState();
151 return; 165 return;
152 } 166 }
153 sio << "State advanced, now: " << *(sState.peek()) << sio.nl; 167 sio << "State advanced, now: " << *(sState.peek()) << sio.nl;
@@ -191,6 +205,11 @@ int Bu::Parser::getNonTerminalId( const Bu::FString &sName )
191 return hNonTerminalName.get( sName ); 205 return hNonTerminalName.get( sName );
192} 206}
193 207
208bool Bu::Parser::hasNonTerminal( const Bu::FString &sName )
209{
210 return hNonTerminalName.has( sName );
211}
212
194int Bu::Parser::addReduction( const Bu::FString &sName, const Reduction &r ) 213int Bu::Parser::addReduction( const Bu::FString &sName, const Reduction &r )
195{ 214{
196 int iId = aReduction.getSize(); 215 int iId = aReduction.getSize();
@@ -217,6 +236,11 @@ int Bu::Parser::getReductionId( const Bu::FString &sName )
217 return hReductionName.get( sName ); 236 return hReductionName.get( sName );
218} 237}
219 238
239bool Bu::Parser::hasReduction( const Bu::FString &sName )
240{
241 return hReductionName.has( sName );
242}
243
220// 244//
221// Bu::Parser::State 245// Bu::Parser::State
222// 246//
diff --git a/src/parser.h b/src/parser.h
index 5b5d4a8..a925188 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -34,6 +34,9 @@ namespace Bu
34 */ 34 */
35 void popLexer(); 35 void popLexer();
36 36
37 Lexer::Token *popToken();
38 void pushToken( Lexer::Token *pTok );
39
37 /** 40 /**
38 * Execute a parse. 41 * Execute a parse.
39 */ 42 */
@@ -88,11 +91,13 @@ namespace Bu
88 int addNonTerminal( const Bu::FString &sName ); 91 int addNonTerminal( const Bu::FString &sName );
89 void setNonTerminal( const Bu::FString &sName, NonTerminal &nt ); 92 void setNonTerminal( const Bu::FString &sName, NonTerminal &nt );
90 int getNonTerminalId( const Bu::FString &sName ); 93 int getNonTerminalId( const Bu::FString &sName );
94 bool hasNonTerminal( const Bu::FString &sName );
91 95
92 int addReduction( const Bu::FString &sName, const Reduction &r ); 96 int addReduction( const Bu::FString &sName, const Reduction &r );
93 int addReduction( const Bu::FString &sName ); 97 int addReduction( const Bu::FString &sName );
94 void setReduction( const Bu::FString &sName, const Reduction &r ); 98 void setReduction( const Bu::FString &sName, const Reduction &r );
95 int getReductionId( const Bu::FString &sName ); 99 int getReductionId( const Bu::FString &sName );
100 bool hasReduction( const Bu::FString &sName );
96 101
97 private: 102 private:
98 bool selectProduction( int iNt, Lexer::Token *ptCur ); 103 bool selectProduction( int iNt, Lexer::Token *ptCur );
diff --git a/src/ringbuffer.h b/src/ringbuffer.h
index e984d18..f4fd58c 100644
--- a/src/ringbuffer.h
+++ b/src/ringbuffer.h
@@ -10,97 +10,218 @@
10 10
11#include <memory> 11#include <memory>
12#include "bu/exceptionbase.h" 12#include "bu/exceptionbase.h"
13#include "bu/queue.h"
14#include "bu/sharedcore.h"
13 15
14namespace Bu 16namespace Bu
15{ 17{
16 /** 18 template<typename value, typename valuealloc> class RingBuffer;
17 *@ingroup Containers 19
18 */ 20 /** @cond DEVEL */
19 template<typename value, typename valuealloc=std::allocator<value> > 21 template<typename value, typename valuealloc>
20 class RingBuffer 22 class RingBufferCore
21 { 23 {
22 public: 24 friend class RingBuffer<value, valuealloc>;
23 RingBuffer( int nCapacity ) : 25 friend class SharedCore<RingBuffer<value, valuealloc>,
24 nCapacity( nCapacity ), 26 RingBufferCore<value, valuealloc> >;
25 nStart( -1 ), 27 private:
26 nEnd( -2 ) 28 RingBufferCore() :
29 iCapacity( 0 ),
30 iStart( -1 ),
31 iEnd( -2 ),
32 aData( NULL )
27 { 33 {
28 aData = va.allocate( nCapacity );
29 } 34 }
30 35
31 virtual ~RingBuffer() 36 virtual ~RingBufferCore()
32 { 37 {
33 for( int j = nStart; j < nEnd; j=(j+1%nCapacity) ) 38 clear();
34 {
35 va.destroy( &aData[j] );
36 }
37 va.deallocate( aData, nCapacity );
38 } 39 }
39 40
40 int getCapacity() 41 void init( int iNewCapacity )
41 { 42 {
42 return nCapacity; 43 if( iCapacity > 0 )
43 } 44 return;
44 45
45 bool isFilled() 46 iCapacity = iNewCapacity;
46 { 47 iStart = -1;
47 return (nStart == nEnd); 48 iEnd = -2;
49 aData = va.allocate( iCapacity );
48 } 50 }
49 51
50 bool isEmpty() 52 void clear()
51 { 53 {
52 return (nStart == -1); 54 for( int j = iStart; j < iEnd; j=(j+1%iCapacity) )
55 {
56 va.destroy( &aData[j] );
57 }
58 va.deallocate( aData, iCapacity );
59 aData = NULL;
60 iCapacity = 0;
53 } 61 }
54 62
55 void enqueue( const value &v ) 63 void enqueue( const value &v )
56 { 64 {
57 if( nStart == -1 ) 65 if( iStart == -1 )
58 { 66 {
59 nStart = 0; 67 iStart = 0;
60 nEnd = 1; 68 iEnd = 1;
61 va.construct( &aData[0], v ); 69 va.construct( &aData[0], v );
62 } 70 }
63 else if( nStart == nEnd ) 71 else if( iStart == iEnd )
64 { 72 {
65 throw ExceptionBase("Hey, it's full!"); 73 throw ExceptionBase("Hey, it's full!");
66 } 74 }
67 else 75 else
68 { 76 {
69 va.construct( &aData[nEnd], v ); 77 va.construct( &aData[iEnd], v );
70 nEnd = (nEnd+1)%nCapacity; 78 iEnd = (iEnd+1)%iCapacity;
71 } 79 }
72 } 80 }
73 81
74 value dequeue() 82 value dequeue()
75 { 83 {
76 if( nStart == -1 ) 84 if( iStart == -1 )
77 { 85 {
78 throw ExceptionBase("No data"); 86 throw ExceptionBase("No data");
79 } 87 }
80 else 88 else
81 { 89 {
82 value &v = aData[nStart]; 90 value &v = aData[iStart];
83 va.destroy( &aData[nStart] ); 91 va.destroy( &aData[iStart] );
84 nStart = (nStart+1)%nCapacity; 92 iStart = (iStart+1)%iCapacity;
85 if( nStart == nEnd ) 93 if( iStart == iEnd )
86 { 94 {
87 nStart = -1; 95 iStart = -1;
88 nEnd = -2; 96 iEnd = -2;
89 } 97 }
90 return v; 98 return v;
91 } 99 }
92 } 100 }
93 101
94 value &operator[]( int nIndex ) 102 value &get( int iIndex )
95 { 103 {
96 return aData[(nIndex+nStart)%nCapacity]; 104 return aData[(iIndex+iStart)%iCapacity];
97 } 105 }
98 106
99 private: 107 int getSize()
100 int nCapacity; 108 {
109 if( iStart < 0 )
110 return 0;
111 if( iEnd == iStart )
112 return iCapacity;
113 if( iEnd < iStart )
114 return iEnd-iStart;
115 return iCapacity-(iEnd-iStart);
116 }
117
118 int iCapacity;
119 int iStart, iEnd;
101 value *aData; 120 value *aData;
102 valuealloc va; 121 valuealloc va;
103 int nStart, nEnd; 122 };
123 /** @endcond */
124
125 /**
126 *@ingroup Containers
127 */
128 template<typename value, typename valuealloc=std::allocator<value> >
129 class RingBuffer : public Queue<value>, public SharedCore<
130 RingBuffer<value, valuealloc>,
131 RingBufferCore<value, valuealloc>
132 >
133 {
134 private:
135 typedef RingBuffer<value, valuealloc> MyType;
136 typedef RingBufferCore<value, valuealloc> Core;
137
138 protected:
139 using SharedCore<MyType, Core>::core;
140 using SharedCore<MyType, Core>::_hardCopy;
141 using SharedCore<MyType, Core>::_allocateCore;
142
143 public:
144 RingBuffer( int iCapacity )
145 {
146 core->init( iCapacity );
147 }
148
149 RingBuffer( const RingBuffer &rSrc ) :
150 SharedCore<MyType, Core>( rSrc )
151 {
152 }
153
154 virtual ~RingBuffer()
155 {
156 }
157
158 int getCapacity() const
159 {
160 return core->iCapacity;
161 }
162
163 bool isFilled() const
164 {
165 return (core->iStart == core->iEnd);
166 }
167
168 bool isEmpty() const
169 {
170 return (core->iStart == -1);
171 }
172
173 virtual void enqueue( const value &v )
174 {
175 _hardCopy();
176
177 core->enqueue( v );
178 }
179
180 virtual value dequeue()
181 {
182 _hardCopy();
183
184 return core->dequeue();
185 }
186
187 virtual int getSize() const
188 {
189 return core->getSize();
190 }
191
192 virtual value &peek()
193 {
194 _hardCopy();
195
196 return core->get( 0 );
197 }
198
199 virtual const value &peek() const
200 {
201 return core->get( 0 );
202 }
203
204 value &operator[]( int iIndex )
205 {
206 _hardCopy();
207
208 return core->get( iIndex );
209 }
210
211 protected:
212 virtual Core *_copyCore( Core *src )
213 {
214 Core *pRet = _allocateCore();
215
216 pRet->init( src->iCapacity );
217 int iSize = src->getSize();
218 for( int j = 0; j < iSize; j++ )
219 {
220 pRet->enqueue( src->get( j ) );
221 }
222
223 return pRet;
224 }
104 }; 225 };
105} 226}
106 227
diff --git a/src/server.cpp b/src/server.cpp
index 51c056a..e701a69 100644
--- a/src/server.cpp
+++ b/src/server.cpp
@@ -8,9 +8,9 @@
8#include "bu/server.h" 8#include "bu/server.h"
9#include <errno.h> 9#include <errno.h>
10#include <unistd.h> 10#include <unistd.h>
11#include "bu/serversocket.h" 11#include "bu/tcpserversocket.h"
12#include "bu/client.h" 12#include "bu/client.h"
13#include "bu/socket.h" 13#include "bu/tcpsocket.h"
14#include "bu/config.h" 14#include "bu/config.h"
15 15
16Bu::Server::Server() : 16Bu::Server::Server() :
@@ -28,7 +28,7 @@ Bu::Server::~Server()
28 28
29void Bu::Server::addPort( int nPort, int nPoolSize ) 29void Bu::Server::addPort( int nPort, int nPoolSize )
30{ 30{
31 ServerSocket *s = new ServerSocket( nPort, nPoolSize ); 31 TcpServerSocket *s = new TcpServerSocket( nPort, nPoolSize );
32 int nSocket = s->getSocket(); 32 int nSocket = s->getSocket();
33 FD_SET( nSocket, &fdActive ); 33 FD_SET( nSocket, &fdActive );
34 hServers.insert( nSocket, s ); 34 hServers.insert( nSocket, s );
@@ -36,7 +36,7 @@ void Bu::Server::addPort( int nPort, int nPoolSize )
36 36
37void Bu::Server::addPort( const FString &sAddr, int nPort, int nPoolSize ) 37void Bu::Server::addPort( const FString &sAddr, int nPort, int nPoolSize )
38{ 38{
39 ServerSocket *s = new ServerSocket( sAddr, nPort, nPoolSize ); 39 TcpServerSocket *s = new TcpServerSocket( sAddr, nPort, nPoolSize );
40 int nSocket = s->getSocket(); 40 int nSocket = s->getSocket();
41 FD_SET( nSocket, &fdActive ); 41 FD_SET( nSocket, &fdActive );
42 hServers.insert( nSocket, s ); 42 hServers.insert( nSocket, s );
@@ -75,7 +75,7 @@ void Bu::Server::scan()
75 { 75 {
76 if( hServers.has( j ) ) 76 if( hServers.has( j ) )
77 { 77 {
78 ServerSocket *pSrv = hServers.get( j ); 78 TcpServerSocket *pSrv = hServers.get( j );
79 addClient( pSrv->accept(), pSrv->getPort() ); 79 addClient( pSrv->accept(), pSrv->getPort() );
80 } 80 }
81 else 81 else
@@ -97,7 +97,7 @@ void Bu::Server::scan()
97 { 97 {
98 pClient->processOutput(); 98 pClient->processOutput();
99 } 99 }
100 catch( Bu::SocketException &e ) 100 catch( Bu::TcpSocketException &e )
101 { 101 {
102 closeClient( j ); 102 closeClient( j );
103 } 103 }
@@ -136,7 +136,7 @@ void Bu::Server::addClient( int nSocket, int nPort )
136 FD_SET( nSocket, &fdActive ); 136 FD_SET( nSocket, &fdActive );
137 137
138 Client *c = new Client( 138 Client *c = new Client(
139 new Bu::Socket( nSocket ), 139 new Bu::TcpSocket( nSocket ),
140 new SrvClientLinkFactory() 140 new SrvClientLinkFactory()
141 ); 141 );
142 hClients.insert( nSocket, c ); 142 hClients.insert( nSocket, c );
diff --git a/src/server.h b/src/server.h
index 74ee99a..d6726fd 100644
--- a/src/server.h
+++ b/src/server.h
@@ -25,8 +25,8 @@
25 25
26namespace Bu 26namespace Bu
27{ 27{
28 class ServerSocket; 28 class TcpServerSocket;
29 class Socket; 29 class TcpSocket;
30 class Client; 30 class Client;
31 31
32 /** 32 /**
@@ -97,7 +97,7 @@ namespace Bu
97 int nTimeoutSec; 97 int nTimeoutSec;
98 int nTimeoutUSec; 98 int nTimeoutUSec;
99 fd_set fdActive; 99 fd_set fdActive;
100 typedef Hash<int,ServerSocket *> SrvHash; 100 typedef Hash<int,TcpServerSocket *> SrvHash;
101 SrvHash hServers; 101 SrvHash hServers;
102 typedef Hash<int,Client *> ClientHash; 102 typedef Hash<int,Client *> ClientHash;
103 ClientHash hClients; 103 ClientHash hClients;
diff --git a/src/set.h b/src/set.h
index 6a2abce..047ff7f 100644
--- a/src/set.h
+++ b/src/set.h
@@ -24,17 +24,10 @@ namespace Bu
24{ 24{
25 subExceptionDecl( SetException ) 25 subExceptionDecl( SetException )
26 26
27 template<typename T>
28 uint32_t __calcHashCode( const T &k );
29
30 template<typename T>
31 bool __cmpHashKeys( const T &a, const T &b );
32
33 template<typename key, typename sizecalc = struct __calcNextTSize_fast, typename keyalloc = std::allocator<key>, typename challoc = std::allocator<uint32_t> >
34 class Set;
35
36 /** 27 /**
37 * Libbu Template Set 28 *@todo Set should be rewritten, possibly using a b-tree as ordered storage
29 * in the backend. It should use either a b-tree or array for storage and
30 * allow set intersections, unions, etc.
38 *@param key (typename) The datatype of the hashtable keys 31 *@param key (typename) The datatype of the hashtable keys
39 *@param sizecalc (typename) Functor to compute new table size on rehash 32 *@param sizecalc (typename) Functor to compute new table size on rehash
40 *@param keyalloc (typename) Memory allocator for hashtable keys 33 *@param keyalloc (typename) Memory allocator for hashtable keys
@@ -45,754 +38,7 @@ namespace Bu
45 class Set 38 class Set
46 { 39 {
47 public: 40 public:
48 Set() :
49 nCapacity( 11 ),
50 nFilled( 0 ),
51 nDeleted( 0 ),
52 bFilled( NULL ),
53 bDeleted( NULL ),
54 aKeys( NULL ),
55 aHashCodes( NULL )
56 {
57 nKeysSize = bitsToBytes( nCapacity );
58 bFilled = ca.allocate( nKeysSize );
59 bDeleted = ca.allocate( nKeysSize );
60 clearBits();
61
62 aHashCodes = ca.allocate( nCapacity );
63 aKeys = ka.allocate( nCapacity );
64 }
65
66 Set( const Set &src ) :
67 nCapacity( src.nCapacity ),
68 nFilled( 0 ),
69 nDeleted( 0 ),
70 bFilled( NULL ),
71 bDeleted( NULL ),
72 aKeys( NULL ),
73 aHashCodes( NULL )
74 {
75 nKeysSize = bitsToBytes( nCapacity );
76 bFilled = ca.allocate( nKeysSize );
77 bDeleted = ca.allocate( nKeysSize );
78 clearBits();
79
80 aHashCodes = ca.allocate( nCapacity );
81 aKeys = ka.allocate( nCapacity );
82
83 for( uint32_t j = 0; j < src.nCapacity; j++ )
84 {
85 if( src.isFilled( j ) )
86 {
87 insert( src.aKeys[j] );
88 }
89 }
90 }
91
92 /**
93 * Set assignment operator. Clears this hashtable and
94 * copies RH into it.
95 */
96 Set &operator=( const Set &src )
97 {
98 for( uint32_t j = 0; j < nCapacity; j++ )
99 {
100 if( isFilled( j ) )
101 if( !isDeleted( j ) )
102 {
103 ka.destroy( &aKeys[j] );
104 }
105 }
106 ka.deallocate( aKeys, nCapacity );
107 ca.deallocate( bFilled, nKeysSize );
108 ca.deallocate( bDeleted, nKeysSize );
109 ca.deallocate( aHashCodes, nCapacity );
110
111 nFilled = 0;
112 nDeleted = 0;
113 nCapacity = src.nCapacity;
114 nKeysSize = bitsToBytes( nCapacity );
115 bFilled = ca.allocate( nKeysSize );
116 bDeleted = ca.allocate( nKeysSize );
117 clearBits();
118
119 aHashCodes = ca.allocate( nCapacity );
120 aKeys = ka.allocate( nCapacity );
121
122 for( uint32_t j = 0; j < src.nCapacity; j++ )
123 {
124 if( src.isFilled( j ) )
125 {
126 insert( src.aKeys[j] );
127 }
128 }
129
130 return *this;
131 }
132
133 virtual ~Set()
134 {
135 for( uint32_t j = 0; j < nCapacity; j++ )
136 {
137 if( isFilled( j ) )
138 if( !isDeleted( j ) )
139 {
140 ka.destroy( &aKeys[j] );
141 }
142 }
143 ka.deallocate( aKeys, nCapacity );
144 ca.deallocate( bFilled, nKeysSize );
145 ca.deallocate( bDeleted, nKeysSize );
146 ca.deallocate( aHashCodes, nCapacity );
147 }
148
149 /**
150 * Get the current hash table capacity. (Changes at re-hash)
151 *@returns (uint32_t) The current capacity.
152 */
153 uint32_t getCapacity()
154 {
155 return nCapacity;
156 }
157
158 /**
159 * Get the number of hash locations spoken for. (Including
160 * not-yet-cleaned-up deleted items.)
161 *@returns (uint32_t) The current fill state.
162 */
163 uint32_t getFill()
164 {
165 return nFilled;
166 }
167
168 /**
169 * Get the number of items stored in the hash table.
170 *@returns (uint32_t) The number of items stored in the hash table.
171 */
172 uint32_t getSize()
173 {
174 return nFilled-nDeleted;
175 }
176
177 /**
178 * Get the number of items which have been deleted, but not yet
179 * cleaned up.
180 *@returns (uint32_t) The number of deleted items.
181 */
182 uint32_t getDeleted()
183 {
184 return nDeleted;
185 }
186
187 /**
188 * Insert key (k) into the set
189 *@param k (key_type) Key to list the value under.
190 */
191 virtual void insert( key k )
192 {
193 uint32_t hash = __calcHashCode( k );
194 bool bFill;
195 uint32_t nPos = probe( hash, k, bFill );
196
197 if( bFill )
198 {
199 onUpdate();
200 }
201 else
202 {
203 fill( nPos, k, hash );
204 onInsert();
205 }
206 }
207
208 /**
209 * Remove a value from the hash table.
210 *@param k (key_type) The data under this key will be erased.
211 */
212 virtual void erase( key k )
213 {
214 uint32_t hash = __calcHashCode( k );
215 bool bFill;
216 uint32_t nPos = probe( hash, k, bFill );
217
218 if( bFill )
219 {
220 _erase( nPos );
221 onDelete();
222 }
223 }
224
225 struct iterator;
226
227 /**
228 * Remove a value from the hash pointed to from an iterator.
229 *@param i (iterator &) The data to be erased.
230 */
231 virtual void erase( struct iterator &i )
232 {
233 if( this != &i.hsh )
234 throw SetException("This iterator didn't come from this Hash.");
235 if( isFilled( i.nPos ) && !isDeleted( i.nPos ) )
236 {
237 _erase( i.nPos );
238 onDelete();
239 }
240 }
241
242 /**
243 * Remove all data from the hash table.
244 */
245 virtual void clear()
246 {
247 for( uint32_t j = 0; j < nCapacity; j++ )
248 {
249 if( isFilled( j ) )
250 if( !isDeleted( j ) )
251 {
252 _erase( j );
253 onDelete();
254 }
255 }
256
257 clearBits();
258 }
259
260 /**
261 * Does the hash table contain an item under key (k).
262 *@param k (key_type) The key to check.
263 *@returns (bool) Whether there was an item in the hash under key (k).
264 */
265 virtual bool has( key k )
266 {
267 bool bFill;
268 probe( __calcHashCode( k ), k, bFill, false );
269
270 return bFill;
271 }
272
273 /**
274 * Iteration structure for iterating through the hash.
275 */
276 typedef struct iterator
277 {
278 friend class Set<key, sizecalc, keyalloc, challoc>;
279 private:
280 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh ) :
281 hsh( hsh ),
282 nPos( 0 ),
283 bFinished( false )
284 {
285 nPos = hsh.getFirstPos( bFinished );
286 }
287
288 iterator( Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
289 hsh( hsh ),
290 nPos( 0 ),
291 bFinished( bDone )
292 {
293 }
294
295 Set<key, sizecalc, keyalloc, challoc> &hsh;
296 uint32_t nPos;
297 bool bFinished;
298
299 public:
300 /**
301 * Iterator incrementation operator. Move the iterator forward.
302 */
303 iterator operator++( int )
304 {
305 if( bFinished == false )
306 nPos = hsh.getNextPos( nPos, bFinished );
307
308 return *this;
309 }
310
311 /**
312 * Iterator incrementation operator. Move the iterator forward.
313 */
314 iterator operator++()
315 {
316 if( bFinished == false )
317 nPos = hsh.getNextPos( nPos, bFinished );
318
319 return *this;
320 }
321
322 /**
323 * Iterator equality comparison operator. Iterators the same?
324 */
325 bool operator==( const iterator &oth ) const
326 {
327 if( bFinished != oth.bFinished )
328 return false;
329 if( bFinished == true )
330 {
331 return true;
332 }
333 else
334 {
335 if( oth.nPos == nPos )
336 return true;
337 return false;
338 }
339 }
340
341 /**
342 * Iterator not equality comparison operator. Not the same?
343 */
344 bool operator!=( const iterator &oth ) const
345 {
346 return !(*this == oth );
347 }
348
349 /**
350 * Iterator assignment operator.
351 */
352 iterator operator=( const iterator &oth )
353 {
354 if( &hsh != &oth.hsh )
355 throw SetException(
356 "Cannot mix iterators from different set objects.");
357 nPos = oth.nPos;
358 bFinished = oth.bFinished;
359 }
360
361 /**
362 * Iterator dereference operator... err.. get the value
363 *@returns (value_type &) The value behind this iterator.
364 */
365 key &operator *()
366 {
367 return hsh.getKeyAtPos( nPos );
368 }
369
370 const key &operator *() const
371 {
372 return hsh.getKeyAtPos( nPos );
373 }
374
375 bool isValid() const
376 {
377 return !bFinished;
378 }
379
380 operator bool() const
381 {
382 return !bFinished;
383 }
384 } iterator;
385
386 /**
387 * Iteration structure for iterating through the set (const).
388 */
389 typedef struct const_iterator
390 {
391 friend class Set<key, sizecalc, keyalloc, challoc>;
392 private:
393 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh ) :
394 hsh( hsh ),
395 nPos( 0 ),
396 bFinished( false )
397 {
398 nPos = hsh.getFirstPos( bFinished );
399 }
400
401 const_iterator( const Set<key, sizecalc, keyalloc, challoc> &hsh, bool bDone ) :
402 hsh( hsh ),
403 nPos( 0 ),
404 bFinished( bDone )
405 {
406 }
407
408 const Set<key, sizecalc, keyalloc, challoc> &hsh;
409 uint32_t nPos;
410 bool bFinished;
411
412 public:
413 /**
414 * Iterator incrementation operator. Move the iterator forward.
415 */
416 const_iterator operator++( int )
417 {
418 if( bFinished == false )
419 nPos = hsh.getNextPos( nPos, bFinished );
420
421 return *this;
422 }
423
424 /**
425 * Iterator incrementation operator. Move the iterator forward.
426 */
427 const_iterator operator++()
428 {
429 if( bFinished == false )
430 nPos = hsh.getNextPos( nPos, bFinished );
431
432 return *this;
433 }
434
435 /**
436 * Iterator equality comparison operator. Iterators the same?
437 */
438 bool operator==( const const_iterator &oth ) const
439 {
440 if( bFinished != oth.bFinished )
441 return false;
442 if( bFinished == true )
443 {
444 return true;
445 }
446 else
447 {
448 if( oth.nPos == nPos )
449 return true;
450 return false;
451 }
452 }
453
454 /**
455 * Iterator not equality comparison operator. Not the same?
456 */
457 bool operator!=( const const_iterator &oth ) const
458 {
459 return !(*this == oth );
460 }
461
462 /**
463 * Iterator assignment operator.
464 */
465 const_iterator operator=( const const_iterator &oth )
466 {
467 if( &hsh != &oth.hsh )
468 throw SetException(
469 "Cannot mix iterators from different hash objects.");
470 nPos = oth.nPos;
471 bFinished = oth.bFinished;
472 }
473
474 /**
475 * Iterator dereference operator... err.. get the value
476 *@returns (value_type &) The value behind this iterator.
477 */
478 const key &operator *() const
479 {
480 return hsh.getKeyAtPos( nPos );
481 }
482
483 bool isValid() const
484 {
485 return !bFinished;
486 }
487
488 operator bool() const
489 {
490 return !bFinished;
491 }
492 } const_iterator;
493
494 /**
495 * Get an iterator pointing to the first item in the hash table.
496 *@returns (iterator) An iterator pointing to the first item in the
497 * hash table.
498 */
499 iterator begin()
500 {
501 return iterator( *this );
502 }
503
504 const_iterator begin() const
505 {
506 return const_iterator( *this );
507 }
508
509 /**
510 * Get an iterator pointing to a point just past the last item in the
511 * hash table.
512 *@returns (iterator) An iterator pointing to a point just past the
513 * last item in the hash table.
514 */
515 iterator end()
516 {
517 return iterator( *this, true );
518 }
519
520 const_iterator end() const
521 {
522 return const_iterator( *this, true );
523 }
524
525 /**
526 * Get a list of all the keys in the hash table.
527 *@returns (std::list<key_type>) The list of keys in the hash table.
528 */
529 Bu::List<key> getKeys() const
530 {
531 Bu::List<key> lKeys;
532
533 for( uint32_t j = 0; j < nCapacity; j++ )
534 {
535 if( isFilled( j ) )
536 {
537 if( !isDeleted( j ) )
538 {
539 lKeys.append( aKeys[j] );
540 }
541 }
542 }
543
544 return lKeys;
545 }
546
547 protected:
548 virtual void onInsert() {}
549 virtual void onUpdate() {}
550 virtual void onDelete() {}
551 virtual void onReHash() {}
552
553 virtual void clearBits()
554 {
555 for( uint32_t j = 0; j < nKeysSize; j++ )
556 {
557 bFilled[j] = bDeleted[j] = 0;
558 }
559 }
560
561 virtual void fill( uint32_t loc, key &k, uint32_t hash )
562 {
563 bFilled[loc/32] |= (1<<(loc%32));
564 ka.construct( &aKeys[loc], k );
565 aHashCodes[loc] = hash;
566 nFilled++;
567 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
568 // nFilled, nDeleted, nCapacity );
569 }
570
571 virtual void _erase( uint32_t loc )
572 {
573 bDeleted[loc/32] |= (1<<(loc%32));
574 ka.destroy( &aKeys[loc] );
575 nDeleted++;
576 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
577 // nFilled, nDeleted, nCapacity );
578 }
579
580 virtual key &getKeyAtPos( uint32_t nPos )
581 {
582 return aKeys[nPos];
583 }
584
585 virtual const key &getKeyAtPos( uint32_t nPos ) const
586 {
587 return aKeys[nPos];
588 }
589
590 virtual uint32_t getFirstPos( bool &bFinished ) const
591 {
592 for( uint32_t j = 0; j < nCapacity; j++ )
593 {
594 if( isFilled( j ) )
595 if( !isDeleted( j ) )
596 return j;
597 }
598
599 bFinished = true;
600 return 0;
601 }
602
603 virtual uint32_t getNextPos( uint32_t nPos, bool &bFinished ) const
604 {
605 for( uint32_t j = nPos+1; j < nCapacity; j++ )
606 {
607 if( isFilled( j ) )
608 if( !isDeleted( j ) )
609 return j;
610 }
611
612 bFinished = true;
613 return 0;
614 }
615
616 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true )
617 {
618 uint32_t nCur = hash%nCapacity;
619
620 // First we scan to see if the key is already there, abort if we
621 // run out of probing room, or we find a non-filled entry
622 int8_t j;
623 for( j = 0;
624 isFilled( nCur ) && j < 32;
625 nCur = (nCur + (1<<j))%nCapacity, j++
626 )
627 {
628 // Is this the same hash code we were looking for?
629 if( hash == aHashCodes[nCur] )
630 {
631 // Skip over deleted entries. Deleted entries are also filled,
632 // so we only have to do this check here.
633 if( isDeleted( nCur ) )
634 continue;
635
636 // Is it really the same key? (for safety)
637 if( __cmpHashKeys( aKeys[nCur], k ) == true )
638 {
639 bFill = true;
640 return nCur;
641 }
642 }
643 }
644
645 // This is our insurance, if the table is full, then go ahead and
646 // rehash, then try again.
647 if( (isFilled( nCur ) || j == 32) && rehash == true )
648 {
649 reHash( szCalc(getCapacity(), getFill(), getDeleted()) );
650
651 // This is potentially dangerous, and could cause an infinite loop.
652 // Be careful writing probe, eh?
653 return probe( hash, k, bFill );
654 }
655
656 bFill = false;
657 return nCur;
658 }
659
660 uint32_t probe( uint32_t hash, key k, bool &bFill, bool rehash=true ) const
661 {
662 uint32_t nCur = hash%nCapacity;
663
664 // First we scan to see if the key is already there, abort if we
665 // run out of probing room, or we find a non-filled entry
666 for( int8_t j = 0;
667 isFilled( nCur ) && j < 32;
668 nCur = (nCur + (1<<j))%nCapacity, j++
669 )
670 {
671 // Is this the same hash code we were looking for?
672 if( hash == aHashCodes[nCur] )
673 {
674 // Skip over deleted entries. Deleted entries are also filled,
675 // so we only have to do this check here.
676 if( isDeleted( nCur ) )
677 continue;
678
679 // Is it really the same key? (for safety)
680 if( __cmpHashKeys( aKeys[nCur], k ) == true )
681 {
682 bFill = true;
683 return nCur;
684 }
685 }
686 }
687
688 bFill = false;
689 return nCur;
690 }
691
692 void reHash( uint32_t nNewSize )
693 {
694 //printf("---REHASH---");
695 //printf("Filled: %d, Deleted: %d, Capacity: %d\n",
696 // nFilled, nDeleted, nCapacity );
697
698 // Save all the old data
699 uint32_t nOldCapacity = nCapacity;
700 uint32_t *bOldFilled = bFilled;
701 uint32_t *aOldHashCodes = aHashCodes;
702 uint32_t nOldKeysSize = nKeysSize;
703 uint32_t *bOldDeleted = bDeleted;
704 key *aOldKeys = aKeys;
705
706 // Calculate new sizes
707 nCapacity = nNewSize;
708 nKeysSize = bitsToBytes( nCapacity );
709
710 // Allocate new memory + prep
711 bFilled = ca.allocate( nKeysSize );
712 bDeleted = ca.allocate( nKeysSize );
713 clearBits();
714
715 aHashCodes = ca.allocate( nCapacity );
716 aKeys = ka.allocate( nCapacity );
717
718 nDeleted = nFilled = 0;
719
720 // Re-insert all of the old data (except deleted items)
721 for( uint32_t j = 0; j < nOldCapacity; j++ )
722 {
723 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 &&
724 (bOldDeleted[j/32]&(1<<(j%32)))==0 )
725 {
726 insert( aOldKeys[j] );
727 }
728 }
729
730 // Delete all of the old data
731 for( uint32_t j = 0; j < nOldCapacity; j++ )
732 {
733 if( (bOldFilled[j/32]&(1<<(j%32)))!=0 )
734 {
735 ka.destroy( &aOldKeys[j] );
736 }
737 }
738 ka.deallocate( aOldKeys, nOldCapacity );
739 ca.deallocate( bOldFilled, nOldKeysSize );
740 ca.deallocate( bOldDeleted, nOldKeysSize );
741 ca.deallocate( aOldHashCodes, nOldCapacity );
742 }
743
744 virtual bool isFilled( uint32_t loc ) const
745 {
746 return (bFilled[loc/32]&(1<<(loc%32)))!=0;
747 }
748
749 virtual bool isDeleted( uint32_t loc ) const
750 {
751 return (bDeleted[loc/32]&(1<<(loc%32)))!=0;
752 }
753
754 protected:
755 uint32_t nCapacity;
756 uint32_t nFilled;
757 uint32_t nDeleted;
758 uint32_t *bFilled;
759 uint32_t *bDeleted;
760 uint32_t nKeysSize;
761 key *aKeys;
762 uint32_t *aHashCodes;
763 keyalloc ka;
764 challoc ca;
765 sizecalc szCalc;
766 }; 41 };
767
768 template<typename key, typename b, typename c, typename d>
769 Archive &operator<<( Archive &ar, const Set<key, b, c, d> &h )
770 {
771 ar << h.getSize();
772 for( typename Set<key, b, c, d>::const_iterator i = h.begin(); i != h.end(); i++ )
773 {
774 ar << (*i);
775 }
776
777 return ar;
778 }
779
780 template<typename key, typename b, typename c, typename d>
781 Archive &operator>>( Archive &ar, Set<key, b, c, d> &h )
782 {
783 h.clear();
784 long nSize;
785 ar >> nSize;
786
787 for( long j = 0; j < nSize; j++ )
788 {
789 key v;
790 ar >> v;
791 h.insert( v );
792 }
793
794 return ar;
795 }
796} 42}
797 43
798#endif 44#endif
diff --git a/src/sharedcore.h b/src/sharedcore.h
index 5a44df9..1887ca2 100644
--- a/src/sharedcore.h
+++ b/src/sharedcore.h
@@ -15,10 +15,57 @@
15 15
16namespace Bu 16namespace Bu
17{ 17{
18 template<typename Core> 18 /**
19 * A mechanism for creating classes that perform lazy copies. The concept
20 * behind this is that instead of copying a large object when it is assigned
21 * or passed into a copy constructor we simply copy a pointer internally.
22 * The assumption is that many times when an object is passed by value we
23 * don't really want to keep the object around, we want the recipient to
24 * take ownership without allocating a new object. This allows that to
25 * happen.
26 *
27 * When used properly this makes object copying essentially free (O(1),
28 * that is) and performs the actual copy when a user tries to modify the
29 * object.
30 *
31 * For example, lets look at something like the getKeys function in
32 * Bu::Hash. When this function is called it creates a Bu::List of
33 * appropriate type, fills it with keys, and returns it. This is a good
34 * way for this function to behave, there may be additional issues if the
35 * List object were allocated with new and not on the stack. However,
36 * returning the List at the end of the function could potentially take
37 * a very long time depending on the size of the list and the type of the
38 * key. In this case the getKeys function doesn't want ownership of the
39 * List object, and when it returns it, it's local copy will be destroyed.
40 *
41 * However, List inherits from SharedCore, which means that when it is
42 * returned all we do is copy a pointer to the "core" of the list, which
43 * is a very fast operatorion. For a brief moment, before anyone can do
44 * anything else, there are two objects referencing the core of that single
45 * list. However, the getKeys() function will destroy it's local copy
46 * before the calling function can use it's new copy. That means that by
47 * the time the calling function can use it's new List of keys it is the
48 * only one with a reference to the core, and no copy will need to happen.
49 *
50 * Using SharedCore on your own classes is fairly straight forward. There
51 * are only a couple of steps. First, break the class into two classes.
52 * Move every variable from the original class (generally everything that's
53 * private) into the new class. Then make the original class inherit from
54 * SharedCore. The SharedCore template takes 2 parameters, first is the
55 * class it's inheriting from, second is the new core class. Now, in your
56 * original class you will have one class variable, a pointer named core.
57 * All of your original variables will be accessable through core. The next
58 * step is to access everything you used to through core, and to find
59 * every function that may change data in the core. At the top of every
60 * function that may change data you want to call _hardCopy().
61 *
62 * That's more or less it. A more detailed guide will be written soon.
63 * @todo Write a guide for this.
64 */
65 template<typename Shell, typename Core>
19 class SharedCore 66 class SharedCore
20 { 67 {
21 typedef class SharedCore<Core> _SharedType; 68 typedef class SharedCore<Shell, Core> _SharedType;
22 public: 69 public:
23 SharedCore() : 70 SharedCore() :
24 core( NULL ), 71 core( NULL ),
@@ -54,6 +101,18 @@ namespace Bu
54 return *iRefCount; 101 return *iRefCount;
55 } 102 }
56 103
104 Shell clone() const
105 {
106 Shell s( dynamic_cast<const Shell &>(*this) );
107 s._hardCopy();
108 return s;
109 }
110
111 bool isCoreShared( const Shell &rOther ) const
112 {
113 return rOther.core == core;
114 }
115
57 protected: 116 protected:
58 Core *core; 117 Core *core;
59 void _hardCopy() 118 void _hardCopy()
@@ -68,6 +127,20 @@ namespace Bu
68 iRefCount = new int( 1 ); 127 iRefCount = new int( 1 );
69 } 128 }
70 129
130 /**
131 * Reset core acts like a hard copy, except instead of providing a
132 * standalone copy of the shared core, it provides a brand new core.
133 *
134 * Very useful in functions used to reset the state of an object.
135 */
136 void _resetCore()
137 {
138 if( core )
139 _deref();
140 core = _allocateCore();
141 iRefCount = new int( 1 );
142 }
143
71 virtual Core *_allocateCore() 144 virtual Core *_allocateCore()
72 { 145 {
73 return new Core(); 146 return new Core();
diff --git a/src/serversocket.cpp b/src/tcpserversocket.cpp
index 87d0035..7d7f6e4 100644
--- a/src/serversocket.cpp
+++ b/src/tcpserversocket.cpp
@@ -21,13 +21,13 @@
21#include <sys/types.h> 21#include <sys/types.h>
22//#include <termios.h> 22//#include <termios.h>
23#include <fcntl.h> 23#include <fcntl.h>
24#include "bu/serversocket.h" 24#include "bu/tcpserversocket.h"
25 25
26#include "bu/config.h" 26#include "bu/config.h"
27 27
28namespace Bu { subExceptionDef( ServerSocketException ) } 28namespace Bu { subExceptionDef( TcpServerSocketException ) }
29 29
30Bu::ServerSocket::ServerSocket( int nPort, int nPoolSize ) : 30Bu::TcpServerSocket::TcpServerSocket( int nPort, int nPoolSize ) :
31 nPort( nPort ) 31 nPort( nPort )
32{ 32{
33#ifdef WIN32 33#ifdef WIN32
@@ -48,7 +48,7 @@ Bu::ServerSocket::ServerSocket( int nPort, int nPoolSize ) :
48 startServer( name, nPoolSize ); 48 startServer( name, nPoolSize );
49} 49}
50 50
51Bu::ServerSocket::ServerSocket(const FString &sAddr,int nPort, int nPoolSize) : 51Bu::TcpServerSocket::TcpServerSocket(const FString &sAddr,int nPort, int nPoolSize) :
52 nPort( nPort ) 52 nPort( nPort )
53{ 53{
54#ifdef WIN32 54#ifdef WIN32
@@ -72,7 +72,7 @@ Bu::ServerSocket::ServerSocket(const FString &sAddr,int nPort, int nPoolSize) :
72 startServer( name, nPoolSize ); 72 startServer( name, nPoolSize );
73} 73}
74 74
75Bu::ServerSocket::ServerSocket( int nServer, bool bInit, int nPoolSize ) : 75Bu::TcpServerSocket::TcpServerSocket( int nServer, bool bInit, int nPoolSize ) :
76 nServer( nServer ), 76 nServer( nServer ),
77 nPort( 0 ) 77 nPort( 0 )
78{ 78{
@@ -95,7 +95,7 @@ Bu::ServerSocket::ServerSocket( int nServer, bool bInit, int nPoolSize ) :
95 } 95 }
96} 96}
97 97
98Bu::ServerSocket::ServerSocket( const ServerSocket &rSrc ) 98Bu::TcpServerSocket::TcpServerSocket( const TcpServerSocket &rSrc )
99{ 99{
100#ifdef WIN32 100#ifdef WIN32
101 Bu::Winsock2::getInstance(); 101 Bu::Winsock2::getInstance();
@@ -107,20 +107,20 @@ Bu::ServerSocket::ServerSocket( const ServerSocket &rSrc )
107 FD_SET( nServer, &fdActive ); 107 FD_SET( nServer, &fdActive );
108} 108}
109 109
110Bu::ServerSocket::~ServerSocket() 110Bu::TcpServerSocket::~TcpServerSocket()
111{ 111{
112 if( nServer > -1 ) 112 if( nServer > -1 )
113 ::close( nServer ); 113 ::close( nServer );
114} 114}
115 115
116void Bu::ServerSocket::startServer( struct sockaddr_in &name, int nPoolSize ) 116void Bu::TcpServerSocket::startServer( struct sockaddr_in &name, int nPoolSize )
117{ 117{
118 /* Create the socket. */ 118 /* Create the socket. */
119 nServer = bu_socket( PF_INET, SOCK_STREAM, 0 ); 119 nServer = bu_socket( PF_INET, SOCK_STREAM, 0 );
120 120
121 if( nServer < 0 ) 121 if( nServer < 0 )
122 { 122 {
123 throw Bu::ServerSocketException("Couldn't create a listen socket."); 123 throw Bu::TcpServerSocketException("Couldn't create a listen socket.");
124 } 124 }
125 125
126 int opt = 1; 126 int opt = 1;
@@ -135,16 +135,16 @@ void Bu::ServerSocket::startServer( struct sockaddr_in &name, int nPoolSize )
135 initServer( name, nPoolSize ); 135 initServer( name, nPoolSize );
136} 136}
137 137
138void Bu::ServerSocket::initServer( struct sockaddr_in &name, int nPoolSize ) 138void Bu::TcpServerSocket::initServer( struct sockaddr_in &name, int nPoolSize )
139{ 139{
140 if( bu_bind( nServer, (struct sockaddr *) &name, sizeof(name) ) < 0 ) 140 if( bu_bind( nServer, (struct sockaddr *) &name, sizeof(name) ) < 0 )
141 { 141 {
142 throw Bu::ServerSocketException("Couldn't bind to the listen socket."); 142 throw Bu::TcpServerSocketException("Couldn't bind to the listen socket.");
143 } 143 }
144 144
145 if( bu_listen( nServer, nPoolSize ) < 0 ) 145 if( bu_listen( nServer, nPoolSize ) < 0 )
146 { 146 {
147 throw Bu::ServerSocketException( 147 throw Bu::TcpServerSocketException(
148 "Couldn't begin listening to the server socket." 148 "Couldn't begin listening to the server socket."
149 ); 149 );
150 } 150 }
@@ -154,12 +154,12 @@ void Bu::ServerSocket::initServer( struct sockaddr_in &name, int nPoolSize )
154 FD_SET( nServer, &fdActive ); 154 FD_SET( nServer, &fdActive );
155} 155}
156 156
157int Bu::ServerSocket::getSocket() 157int Bu::TcpServerSocket::getSocket()
158{ 158{
159 return nServer; 159 return nServer;
160} 160}
161 161
162int Bu::ServerSocket::accept( int nTimeoutSec, int nTimeoutUSec ) 162int Bu::TcpServerSocket::accept( int nTimeoutSec, int nTimeoutUSec )
163{ 163{
164 fd_set fdRead = fdActive; 164 fd_set fdRead = fdActive;
165 165
@@ -171,7 +171,7 @@ int Bu::ServerSocket::accept( int nTimeoutSec, int nTimeoutUSec )
171 if( TEMP_FAILURE_RETRY( 171 if( TEMP_FAILURE_RETRY(
172 bu_select( nServer+1, &fdRead, NULL, NULL, &xT )) < 0 ) 172 bu_select( nServer+1, &fdRead, NULL, NULL, &xT )) < 0 )
173 { 173 {
174 throw Bu::ServerSocketException( 174 throw Bu::TcpServerSocketException(
175 "Error scanning for new connections: %s", strerror( errno ) 175 "Error scanning for new connections: %s", strerror( errno )
176 ); 176 );
177 } 177 }
@@ -200,7 +200,7 @@ int Bu::ServerSocket::accept( int nTimeoutSec, int nTimeoutUSec )
200#endif /* WIN32 */ 200#endif /* WIN32 */
201 if( nClient < 0 ) 201 if( nClient < 0 )
202 { 202 {
203 throw Bu::ServerSocketException( 203 throw Bu::TcpServerSocketException(
204 "Error accepting a new connection: %s", strerror( errno ) 204 "Error accepting a new connection: %s", strerror( errno )
205 ); 205 );
206 } 206 }
@@ -219,7 +219,7 @@ int Bu::ServerSocket::accept( int nTimeoutSec, int nTimeoutUSec )
219 flags |= O_NONBLOCK; 219 flags |= O_NONBLOCK;
220 if( fcntl( nClient, F_SETFL, flags ) < 0) 220 if( fcntl( nClient, F_SETFL, flags ) < 0)
221 { 221 {
222 throw Bu::ServerSocketException( 222 throw Bu::TcpServerSocketException(
223 "Error setting option on client socket: %s", 223 "Error setting option on client socket: %s",
224 strerror( errno ) 224 strerror( errno )
225 ); 225 );
@@ -242,7 +242,7 @@ int Bu::ServerSocket::accept( int nTimeoutSec, int nTimeoutUSec )
242 return -1; 242 return -1;
243} 243}
244 244
245int Bu::ServerSocket::getPort() 245int Bu::TcpServerSocket::getPort()
246{ 246{
247 return nPort; 247 return nPort;
248} 248}
diff --git a/src/serversocket.h b/src/tcpserversocket.h
index ee357a4..b1d7e02 100644
--- a/src/serversocket.h
+++ b/src/tcpserversocket.h
@@ -5,8 +5,8 @@
5 * terms of the license contained in the file LICENSE. 5 * terms of the license contained in the file LICENSE.
6 */ 6 */
7 7
8#ifndef BU_SERVER_SOCKET_H 8#ifndef BU_TCP_SERVER_SOCKET_H
9#define BU_SERVER_SOCKET_H 9#define BU_TCP_SERVER_SOCKET_H
10 10
11#include <stdint.h> 11#include <stdint.h>
12#include "bu/fstring.h" 12#include "bu/fstring.h"
@@ -20,7 +20,7 @@
20 20
21namespace Bu 21namespace Bu
22{ 22{
23 subExceptionDecl( ServerSocketException ); 23 subExceptionDecl( TcpServerSocketException );
24 24
25 /** 25 /**
26 * A single tcp/ip server socket. When created the server socket will bind 26 * A single tcp/ip server socket. When created the server socket will bind
@@ -34,14 +34,14 @@ namespace Bu
34 * 34 *
35 *@ingroup Serving 35 *@ingroup Serving
36 */ 36 */
37 class ServerSocket 37 class TcpServerSocket
38 { 38 {
39 public: 39 public:
40 ServerSocket( int nPort, int nPoolSize=40 ); 40 TcpServerSocket( int nPort, int nPoolSize=40 );
41 ServerSocket( const FString &sAddr, int nPort, int nPoolSize=40 ); 41 TcpServerSocket( const FString &sAddr, int nPort, int nPoolSize=40 );
42 ServerSocket( int nSocket, bool bInit, int nPoolSize=40 ); 42 TcpServerSocket( int nSocket, bool bInit, int nPoolSize=40 );
43 ServerSocket( const ServerSocket &rSrc ); 43 TcpServerSocket( const TcpServerSocket &rSrc );
44 virtual ~ServerSocket(); 44 virtual ~TcpServerSocket();
45 45
46 int accept( int nTimeoutSec=0, int nTimeoutUSec=0 ); 46 int accept( int nTimeoutSec=0, int nTimeoutUSec=0 );
47 int getSocket(); 47 int getSocket();
diff --git a/src/socket.cpp b/src/tcpsocket.cpp
index baf3be3..bbd9cf5 100644
--- a/src/socket.cpp
+++ b/src/tcpsocket.cpp
@@ -14,7 +14,7 @@
14#include <sys/time.h> 14#include <sys/time.h>
15#include <errno.h> 15#include <errno.h>
16#include <fcntl.h> 16#include <fcntl.h>
17#include "bu/socket.h" 17#include "bu/tcpsocket.h"
18 18
19#include "bu/config.h" 19#include "bu/config.h"
20 20
@@ -29,10 +29,10 @@
29 29
30#define RBS (1024*2) 30#define RBS (1024*2)
31 31
32namespace Bu { subExceptionDef( SocketException ) } 32namespace Bu { subExceptionDef( TcpSocketException ) }
33 33
34Bu::Socket::Socket( int nSocket ) : 34Bu::TcpSocket::TcpSocket( int nTcpSocket ) :
35 nSocket( nSocket ), 35 nTcpSocket( nTcpSocket ),
36 bActive( true ), 36 bActive( true ),
37 bBlocking( true ) 37 bBlocking( true )
38{ 38{
@@ -42,8 +42,9 @@ Bu::Socket::Socket( int nSocket ) :
42 setAddress(); 42 setAddress();
43} 43}
44 44
45Bu::Socket::Socket( const Bu::FString &sAddr, int nPort, int nTimeout ) : 45Bu::TcpSocket::TcpSocket( const Bu::FString &sAddr, int nPort, int nTimeout,
46 nSocket( 0 ), 46 bool bBlocking ) :
47 nTcpSocket( 0 ),
47 bActive( false ), 48 bActive( false ),
48 bBlocking( true ) 49 bBlocking( true )
49{ 50{
@@ -52,9 +53,9 @@ Bu::Socket::Socket( const Bu::FString &sAddr, int nPort, int nTimeout ) :
52#endif 53#endif
53 54
54 /* Create the socket. */ 55 /* Create the socket. */
55 nSocket = bu_socket( PF_INET, SOCK_STREAM, 0 ); 56 nTcpSocket = bu_socket( PF_INET, SOCK_STREAM, 0 );
56 57
57 if( nSocket < 0 ) 58 if( nTcpSocket < 0 )
58 { 59 {
59 throw ExceptionBase("Couldn't create socket.\n"); 60 throw ExceptionBase("Couldn't create socket.\n");
60 } 61 }
@@ -78,12 +79,12 @@ Bu::Socket::Socket( const Bu::FString &sAddr, int nPort, int nTimeout ) :
78 sAddr.getStr(), ibuf, &aiHints, &pAddr )) != 0 ) 79 sAddr.getStr(), ibuf, &aiHints, &pAddr )) != 0 )
79 { 80 {
80 close(); 81 close();
81 throw Bu::SocketException("Couldn't resolve hostname %s (%s).\n", 82 throw Bu::TcpSocketException("Couldn't resolve hostname %s (%s).\n",
82 sAddr.getStr(), bu_gai_strerror(ret)); 83 sAddr.getStr(), bu_gai_strerror(ret));
83 } 84 }
84 85
85 bu_connect( 86 bu_connect(
86 nSocket, 87 nTcpSocket,
87 pAddr->ai_addr, 88 pAddr->ai_addr,
88 pAddr->ai_addrlen 89 pAddr->ai_addrlen
89 ); 90 );
@@ -101,17 +102,17 @@ Bu::Socket::Socket( const Bu::FString &sAddr, int nPort, int nTimeout ) :
101 int retval; 102 int retval;
102 103
103 FD_ZERO(&rfds); 104 FD_ZERO(&rfds);
104 FD_SET(nSocket, &rfds); 105 FD_SET(nTcpSocket, &rfds);
105 FD_ZERO(&wfds); 106 FD_ZERO(&wfds);
106 FD_SET(nSocket, &wfds); 107 FD_SET(nTcpSocket, &wfds);
107 FD_ZERO(&efds); 108 FD_ZERO(&efds);
108 FD_SET(nSocket, &efds); 109 FD_SET(nTcpSocket, &efds);
109 110
110 struct timeval tv; 111 struct timeval tv;
111 tv.tv_sec = nTimeout; 112 tv.tv_sec = nTimeout;
112 tv.tv_usec = 0; 113 tv.tv_usec = 0;
113 114
114 retval = bu_select( nSocket+1, &rfds, &wfds, &efds, &tv ); 115 retval = bu_select( nTcpSocket+1, &rfds, &wfds, &efds, &tv );
115 116
116 if( retval == 0 ) 117 if( retval == 0 )
117 { 118 {
@@ -120,51 +121,54 @@ Bu::Socket::Socket( const Bu::FString &sAddr, int nPort, int nTimeout ) :
120 } 121 }
121 read( NULL, 0 ); // See if we can get any errors out of the way early. 122 read( NULL, 0 ); // See if we can get any errors out of the way early.
122 } 123 }
124
125 if( bBlocking )
126 setBlocking( bBlocking );
123} 127}
124 128
125Bu::Socket::~Socket() 129Bu::TcpSocket::~TcpSocket()
126{ 130{
127 close(); 131 close();
128} 132}
129 133
130void Bu::Socket::close() 134void Bu::TcpSocket::close()
131{ 135{
132 if( bActive ) 136 if( bActive )
133 { 137 {
134#ifndef WIN32 138#ifndef WIN32
135 fsync( nSocket ); 139 fsync( nTcpSocket );
136#endif 140#endif
137#ifdef WIN32 141#ifdef WIN32
138 #ifndef SHUT_RDWR 142 #ifndef SHUT_RDWR
139 #define SHUT_RDWR (SD_BOTH) 143 #define SHUT_RDWR (SD_BOTH)
140 #endif 144 #endif
141#endif 145#endif
142 bu_shutdown( nSocket, SHUT_RDWR ); 146 bu_shutdown( nTcpSocket, SHUT_RDWR );
143 ::close( nSocket ); 147 ::close( nTcpSocket );
144 } 148 }
145 bActive = false; 149 bActive = false;
146} 150}
147 151
148size_t Bu::Socket::read( void *pBuf, size_t nBytes ) 152size_t Bu::TcpSocket::read( void *pBuf, size_t nBytes )
149{ 153{
150 fd_set rfds; 154 fd_set rfds;
151 FD_ZERO(&rfds); 155 FD_ZERO(&rfds);
152 FD_SET(nSocket, &rfds); 156 FD_SET(nTcpSocket, &rfds);
153 struct timeval tv = {0, 0}; 157 struct timeval tv = {0, 0};
154 if( bu_select( nSocket+1, &rfds, NULL, NULL, &tv ) < 0 ) 158 if( bu_select( nTcpSocket+1, &rfds, NULL, NULL, &tv ) < 0 )
155 { 159 {
156 int iErr = errno; 160 int iErr = errno;
157 close(); 161 close();
158 throw SocketException( SocketException::cRead, strerror(iErr) ); 162 throw TcpSocketException( TcpSocketException::cRead, strerror(iErr) );
159 } 163 }
160 if( FD_ISSET( nSocket, &rfds ) || bBlocking ) 164 if( FD_ISSET( nTcpSocket, &rfds ) || bBlocking )
161 { 165 {
162 int nRead = TEMP_FAILURE_RETRY( 166 int nRead = TEMP_FAILURE_RETRY(
163 bu_recv( nSocket, (char *) pBuf, nBytes, 0 ) ); 167 bu_recv( nTcpSocket, (char *) pBuf, nBytes, 0 ) );
164 if( nRead == 0 ) 168 if( nRead == 0 )
165 { 169 {
166 close(); 170 close();
167 throw SocketException( SocketException::cClosed, "Socket closed."); 171 throw TcpSocketException( TcpSocketException::cClosed, "TcpSocket closed.");
168 } 172 }
169 if( nRead < 0 ) 173 if( nRead < 0 )
170 { 174 {
@@ -176,14 +180,14 @@ size_t Bu::Socket::read( void *pBuf, size_t nBytes )
176 if( errno == ENETRESET || errno == ECONNRESET ) 180 if( errno == ENETRESET || errno == ECONNRESET )
177 { 181 {
178 close(); 182 close();
179 throw SocketException( SocketException::cClosed, 183 throw TcpSocketException( TcpSocketException::cClosed,
180 strerror(errno) ); 184 strerror(errno) );
181 } 185 }
182 if( errno == EAGAIN ) 186 if( errno == EAGAIN )
183 return 0; 187 return 0;
184 int iErr = errno; 188 int iErr = errno;
185 close(); 189 close();
186 throw SocketException( SocketException::cRead, strerror(iErr) ); 190 throw TcpSocketException( TcpSocketException::cRead, strerror(iErr) );
187#endif 191#endif
188 } 192 }
189 return nRead; 193 return nRead;
@@ -191,7 +195,7 @@ size_t Bu::Socket::read( void *pBuf, size_t nBytes )
191 return 0; 195 return 0;
192} 196}
193 197
194size_t Bu::Socket::read( void *pBuf, size_t nBytes, 198size_t Bu::TcpSocket::read( void *pBuf, size_t nBytes,
195 uint32_t nSec, uint32_t nUSec ) 199 uint32_t nSec, uint32_t nUSec )
196{ 200{
197 struct timeval tv; 201 struct timeval tv;
@@ -199,7 +203,7 @@ size_t Bu::Socket::read( void *pBuf, size_t nBytes,
199 203
200 fd_set rfds; 204 fd_set rfds;
201 FD_ZERO(&rfds); 205 FD_ZERO(&rfds);
202 FD_SET(nSocket, &rfds); 206 FD_SET(nTcpSocket, &rfds);
203 207
204#ifdef WIN32 208#ifdef WIN32
205 DWORD dwStart = GetTickCount(); 209 DWORD dwStart = GetTickCount();
@@ -216,7 +220,7 @@ size_t Bu::Socket::read( void *pBuf, size_t nBytes,
216 { 220 {
217 tv.tv_sec = nSec; 221 tv.tv_sec = nSec;
218 tv.tv_usec = nUSec; 222 tv.tv_usec = nUSec;
219 bu_select( nSocket+1, &rfds, NULL, NULL, &tv ); 223 bu_select( nTcpSocket+1, &rfds, NULL, NULL, &tv );
220 nRead += read( ((char *)pBuf)+nRead, nBytes-nRead ); 224 nRead += read( ((char *)pBuf)+nRead, nBytes-nRead );
221 if( nRead >= nBytes ) 225 if( nRead >= nBytes )
222 break; 226 break;
@@ -235,13 +239,13 @@ size_t Bu::Socket::read( void *pBuf, size_t nBytes,
235 return nRead; 239 return nRead;
236} 240}
237 241
238size_t Bu::Socket::write( const void *pBuf, size_t nBytes ) 242size_t Bu::TcpSocket::write( const void *pBuf, size_t nBytes )
239{ 243{
240//#ifdef WIN32 244//#ifdef WIN32
241 int nWrote = TEMP_FAILURE_RETRY( 245 int nWrote = TEMP_FAILURE_RETRY(
242 bu_send( nSocket, (const char *) pBuf, nBytes, 0 ) ); 246 bu_send( nTcpSocket, (const char *) pBuf, nBytes, 0 ) );
243//#else 247//#else
244// int nWrote = TEMP_FAILURE_RETRY( ::write( nSocket, pBuf, nBytes ) ); 248// int nWrote = TEMP_FAILURE_RETRY( ::write( nTcpSocket, pBuf, nBytes ) );
245//#endif 249//#endif
246 if( nWrote < 0 ) 250 if( nWrote < 0 )
247 { 251 {
@@ -252,19 +256,19 @@ size_t Bu::Socket::write( const void *pBuf, size_t nBytes )
252#else 256#else
253 if( errno == EAGAIN ) return 0; 257 if( errno == EAGAIN ) return 0;
254#endif 258#endif
255 throw SocketException( SocketException::cWrite, strerror(errno) ); 259 throw TcpSocketException( TcpSocketException::cWrite, strerror(errno) );
256 } 260 }
257 return nWrote; 261 return nWrote;
258} 262}
259 263
260size_t Bu::Socket::write( const void *pBuf, size_t nBytes, uint32_t nSec, uint32_t nUSec ) 264size_t Bu::TcpSocket::write( const void *pBuf, size_t nBytes, uint32_t nSec, uint32_t nUSec )
261{ 265{
262 struct timeval tv; 266 struct timeval tv;
263 size_t nWrote = 0; 267 size_t nWrote = 0;
264 268
265 fd_set wfds; 269 fd_set wfds;
266 FD_ZERO(&wfds); 270 FD_ZERO(&wfds);
267 FD_SET(nSocket, &wfds); 271 FD_SET(nTcpSocket, &wfds);
268 272
269#ifdef WIN32 273#ifdef WIN32
270 DWORD dwStart = GetTickCount(); 274 DWORD dwStart = GetTickCount();
@@ -281,7 +285,7 @@ size_t Bu::Socket::write( const void *pBuf, size_t nBytes, uint32_t nSec, uint32
281 { 285 {
282 tv.tv_sec = nSec; 286 tv.tv_sec = nSec;
283 tv.tv_usec = nUSec; 287 tv.tv_usec = nUSec;
284 bu_select( nSocket+1, NULL, &wfds, NULL, &tv ); 288 bu_select( nTcpSocket+1, NULL, &wfds, NULL, &tv );
285 nWrote += write( ((char *)pBuf)+nWrote, nBytes-nWrote ); 289 nWrote += write( ((char *)pBuf)+nWrote, nBytes-nWrote );
286 if( nWrote >= nBytes ) 290 if( nWrote >= nBytes )
287 break; 291 break;
@@ -300,101 +304,101 @@ size_t Bu::Socket::write( const void *pBuf, size_t nBytes, uint32_t nSec, uint32
300 return nWrote; 304 return nWrote;
301} 305}
302 306
303long Bu::Socket::tell() 307long Bu::TcpSocket::tell()
304{ 308{
305 throw UnsupportedException(); 309 throw UnsupportedException();
306} 310}
307 311
308void Bu::Socket::seek( long ) 312void Bu::TcpSocket::seek( long )
309{ 313{
310 throw UnsupportedException(); 314 throw UnsupportedException();
311} 315}
312 316
313void Bu::Socket::setPos( long ) 317void Bu::TcpSocket::setPos( long )
314{ 318{
315 throw UnsupportedException(); 319 throw UnsupportedException();
316} 320}
317 321
318void Bu::Socket::setPosEnd( long ) 322void Bu::TcpSocket::setPosEnd( long )
319{ 323{
320 throw UnsupportedException(); 324 throw UnsupportedException();
321} 325}
322 326
323bool Bu::Socket::isEos() 327bool Bu::TcpSocket::isEos()
324{ 328{
325 return !bActive; 329 return !bActive;
326} 330}
327 331
328bool Bu::Socket::canRead() 332bool Bu::TcpSocket::canRead()
329{ 333{
330 fd_set rfds; 334 fd_set rfds;
331 FD_ZERO(&rfds); 335 FD_ZERO(&rfds);
332 FD_SET(nSocket, &rfds); 336 FD_SET(nTcpSocket, &rfds);
333 struct timeval tv = { 0, 0 }; 337 struct timeval tv = { 0, 0 };
334 int retval = bu_select( nSocket+1, &rfds, NULL, NULL, &tv ); 338 int retval = bu_select( nTcpSocket+1, &rfds, NULL, NULL, &tv );
335 if( retval == -1 ) 339 if( retval == -1 )
336 throw SocketException( 340 throw TcpSocketException(
337 SocketException::cBadRead, 341 TcpSocketException::cBadRead,
338 "Bad Read error" 342 "Bad Read error"
339 ); 343 );
340 344
341 if( !FD_ISSET( nSocket, &rfds ) ) 345 if( !FD_ISSET( nTcpSocket, &rfds ) )
342 return false; 346 return false;
343 return true; 347 return true;
344} 348}
345 349
346bool Bu::Socket::canWrite() 350bool Bu::TcpSocket::canWrite()
347{ 351{
348 fd_set wfds; 352 fd_set wfds;
349 FD_ZERO(&wfds); 353 FD_ZERO(&wfds);
350 FD_SET(nSocket, &wfds); 354 FD_SET(nTcpSocket, &wfds);
351 struct timeval tv = { 0, 0 }; 355 struct timeval tv = { 0, 0 };
352 int retval = bu_select( nSocket+1, NULL, &wfds, NULL, &tv ); 356 int retval = bu_select( nTcpSocket+1, NULL, &wfds, NULL, &tv );
353 if( retval == -1 ) 357 if( retval == -1 )
354 throw SocketException( 358 throw TcpSocketException(
355 SocketException::cBadRead, 359 TcpSocketException::cBadRead,
356 "Bad Read error" 360 "Bad Read error"
357 ); 361 );
358 if( !FD_ISSET( nSocket, &wfds ) ) 362 if( !FD_ISSET( nTcpSocket, &wfds ) )
359 return false; 363 return false;
360 return true; 364 return true;
361} 365}
362 366
363bool Bu::Socket::isReadable() 367bool Bu::TcpSocket::isReadable()
364{ 368{
365 return true; 369 return true;
366} 370}
367 371
368bool Bu::Socket::isWritable() 372bool Bu::TcpSocket::isWritable()
369{ 373{
370 return true; 374 return true;
371} 375}
372 376
373bool Bu::Socket::isSeekable() 377bool Bu::TcpSocket::isSeekable()
374{ 378{
375 return false; 379 return false;
376} 380}
377 381
378bool Bu::Socket::isBlocking() 382bool Bu::TcpSocket::isBlocking()
379{ 383{
380#ifndef WIN32 384#ifndef WIN32
381 return ((fcntl( nSocket, F_GETFL, 0 ) & O_NONBLOCK) != O_NONBLOCK); 385 return ((fcntl( nTcpSocket, F_GETFL, 0 ) & O_NONBLOCK) != O_NONBLOCK);
382#else 386#else
383 return false; 387 return false;
384#endif 388#endif
385} 389}
386 390
387void Bu::Socket::setBlocking( bool bBlocking ) 391void Bu::TcpSocket::setBlocking( bool bBlocking )
388{ 392{
389 this->bBlocking = bBlocking; 393 this->bBlocking = bBlocking;
390#ifndef WIN32 394#ifndef WIN32
391 if( bBlocking ) 395 if( bBlocking )
392 { 396 {
393 fcntl( nSocket, F_SETFL, fcntl( nSocket, F_GETFL, 0 ) & (~O_NONBLOCK) ); 397 fcntl( nTcpSocket, F_SETFL, fcntl( nTcpSocket, F_GETFL, 0 ) & (~O_NONBLOCK) );
394 } 398 }
395 else 399 else
396 { 400 {
397 fcntl( nSocket, F_SETFL, fcntl( nSocket, F_GETFL, 0 ) | O_NONBLOCK ); 401 fcntl( nTcpSocket, F_SETFL, fcntl( nTcpSocket, F_GETFL, 0 ) | O_NONBLOCK );
398 } 402 }
399#else 403#else
400 u_long iMode; 404 u_long iMode;
@@ -408,39 +412,39 @@ void Bu::Socket::setBlocking( bool bBlocking )
408 // socket based on the numerical value of iMode. 412 // socket based on the numerical value of iMode.
409 // If iMode = 0, blocking is enabled; 413 // If iMode = 0, blocking is enabled;
410 // If iMode != 0, non-blocking mode is enabled. 414 // If iMode != 0, non-blocking mode is enabled.
411 bu_ioctlsocket(nSocket, FIONBIO, &iMode); 415 bu_ioctlsocket(nTcpSocket, FIONBIO, &iMode);
412#endif 416#endif
413} 417}
414 418
415void Bu::Socket::setSize( long ) 419void Bu::TcpSocket::setSize( long )
416{ 420{
417} 421}
418 422
419void Bu::Socket::flush() 423void Bu::TcpSocket::flush()
420{ 424{
421} 425}
422 426
423bool Bu::Socket::isOpen() 427bool Bu::TcpSocket::isOpen()
424{ 428{
425 return bActive; 429 return bActive;
426} 430}
427 431
428void Bu::Socket::setAddress() 432void Bu::TcpSocket::setAddress()
429{ 433{
430 struct sockaddr_in addr; 434 struct sockaddr_in addr;
431 socklen_t len = sizeof(addr); 435 socklen_t len = sizeof(addr);
432 addr.sin_family = AF_INET; 436 addr.sin_family = AF_INET;
433 bu_getpeername( nSocket, (sockaddr *)(&addr), &len ); 437 bu_getpeername( nTcpSocket, (sockaddr *)(&addr), &len );
434 sAddress = bu_inet_ntoa( addr.sin_addr ); 438 sAddress = bu_inet_ntoa( addr.sin_addr );
435} 439}
436 440
437Bu::FString Bu::Socket::getAddress() const 441Bu::FString Bu::TcpSocket::getAddress() const
438{ 442{
439 return sAddress; 443 return sAddress;
440} 444}
441 445
442Bu::Socket::operator int() const 446Bu::TcpSocket::operator int() const
443{ 447{
444 return nSocket; 448 return nTcpSocket;
445} 449}
446 450
diff --git a/src/socket.h b/src/tcpsocket.h
index c8f78f0..3361e84 100644
--- a/src/socket.h
+++ b/src/tcpsocket.h
@@ -5,8 +5,8 @@
5 * terms of the license contained in the file LICENSE. 5 * terms of the license contained in the file LICENSE.
6 */ 6 */
7 7
8#ifndef BU_SOCKET_H 8#ifndef BU_TCP_SOCKET_H
9#define BU_SOCKET_H 9#define BU_TCP_SOCKET_H
10 10
11#include <stdint.h> 11#include <stdint.h>
12 12
@@ -16,7 +16,7 @@
16 16
17namespace Bu 17namespace Bu
18{ 18{
19 subExceptionDeclBegin( SocketException ); 19 subExceptionDeclBegin( TcpSocketException );
20 enum { 20 enum {
21 cRead, 21 cRead,
22 cWrite, 22 cWrite,
@@ -40,28 +40,29 @@ namespace Bu
40 * Please note that there is a condition that will occur eventually (at 40 * Please note that there is a condition that will occur eventually (at
41 * least on *nix systems) that will trigger a SIGPIPE condition. This 41 * least on *nix systems) that will trigger a SIGPIPE condition. This
42 * will terminate your program immediately unless handled properly. Most 42 * will terminate your program immediately unless handled properly. Most
43 * people doing any connections with Socket will want to put this in their 43 * people doing any connections with TcpSocket will want to put this in
44 * program somewhere before they use it: 44 * their program somewhere before they use it:
45 *@code 45 *@code
46 #include <signal.h> 46 #include <signal.h>
47 ... 47 ...
48 ... 48 ...
49 ... 49 ...
50 sigset( SIGPIPE, SIG_IGN ); // do this before you use a Bu::Socket 50 sigset( SIGPIPE, SIG_IGN ); // do this before you use a Bu::TcpSocket
51 @endcode 51 @endcode
52 * When this is done, Bu::Socket will simply throw a broken pipe exception 52 * When this is done, Bu::TcpSocket will simply throw a broken pipe
53 * just like every other error condition, allowing your program to handle 53 * exception just like every other error condition, allowing your program
54 * it sanely. 54 * to handle it sanely.
55 * 55 *
56 *@ingroup Serving 56 *@ingroup Serving
57 *@ingroup Streams 57 *@ingroup Streams
58 */ 58 */
59 class Socket : public Stream 59 class TcpSocket : public Stream
60 { 60 {
61 public: 61 public:
62 Socket( int nSocket ); 62 TcpSocket( int nTcpSocket );
63 Socket( const FString &sAddr, int nPort, int nTimeout=30 ); 63 TcpSocket( const FString &sAddr, int nPort, int nTimeout=30,
64 virtual ~Socket(); 64 bool bBlocking=true );
65 virtual ~TcpSocket();
65 66
66 virtual void close(); 67 virtual void close();
67 //virtual void read(); 68 //virtual void read();
@@ -101,9 +102,9 @@ namespace Bu
101 void setAddress(); 102 void setAddress();
102 103
103#ifdef WIN32 104#ifdef WIN32
104 unsigned int nSocket; 105 unsigned int nTcpSocket;
105#else 106#else
106 int nSocket; 107 int nTcpSocket;
107#endif 108#endif
108 bool bActive; 109 bool bActive;
109 bool bBlocking; 110 bool bBlocking;
diff --git a/src/tests/sharedcore.cpp b/src/tests/sharedcore.cpp
index 1d0c16e..9b0a0ec 100644
--- a/src/tests/sharedcore.cpp
+++ b/src/tests/sharedcore.cpp
@@ -14,7 +14,7 @@ struct ShintCore
14{ 14{
15 int val; 15 int val;
16}; 16};
17class Shint : public Bu::SharedCore<struct ShintCore> 17class Shint : public Bu::SharedCore<Shint, struct ShintCore>
18{ 18{
19public: 19public:
20 Shint() 20 Shint()
diff --git a/src/tests/socketblock.cpp b/src/tests/socketblock.cpp
index a1ea18d..793ef96 100644
--- a/src/tests/socketblock.cpp
+++ b/src/tests/socketblock.cpp
@@ -6,8 +6,8 @@
6 */ 6 */
7 7
8#include "bu/ito.h" 8#include "bu/ito.h"
9#include "bu/socket.h" 9#include "bu/tcpsocket.h"
10#include "bu/serversocket.h" 10#include "bu/tcpserversocket.h"
11#include <stdio.h> 11#include <stdio.h>
12#include <unistd.h> 12#include <unistd.h>
13 13
@@ -21,7 +21,7 @@ public:
21 21
22 virtual void run() 22 virtual void run()
23 { 23 {
24 Bu::Socket c = s.accept( 45, 0 ); 24 Bu::TcpSocket c = s.accept( 45, 0 );
25 printf("TstServer: Accetped connection.\n"); fflush( stdout ); 25 printf("TstServer: Accetped connection.\n"); fflush( stdout );
26 26
27 sleep( 1 ); 27 sleep( 1 );
@@ -35,7 +35,7 @@ public:
35 c.close(); 35 c.close();
36 } 36 }
37 37
38 Bu::ServerSocket s; 38 Bu::TcpServerSocket s;
39}; 39};
40 40
41int main() 41int main()
@@ -45,7 +45,7 @@ int main()
45 ts.start(); 45 ts.start();
46 46
47 printf("main: Connecting to server.\n"); fflush( stdout ); 47 printf("main: Connecting to server.\n"); fflush( stdout );
48 Bu::Socket s( "localhost", 55678 ); 48 Bu::TcpSocket s( "localhost", 55678 );
49 49
50 printf("main: Sending 4 bytes.\n"); fflush( stdout ); 50 printf("main: Sending 4 bytes.\n"); fflush( stdout );
51 s.write( "aoeu", 4 ); 51 s.write( "aoeu", 4 );
diff --git a/src/tests/socketbreak.cpp b/src/tests/socketbreak.cpp
index 8339630..7d3c71a 100644
--- a/src/tests/socketbreak.cpp
+++ b/src/tests/socketbreak.cpp
@@ -5,17 +5,17 @@
5 * terms of the license contained in the file LICENSE. 5 * terms of the license contained in the file LICENSE.
6 */ 6 */
7 7
8#include "bu/serversocket.h" 8#include "bu/tcpserversocket.h"
9#include "bu/socket.h" 9#include "bu/tcpsocket.h"
10#include <unistd.h> 10#include <unistd.h>
11 11
12int main() 12int main()
13{ 13{
14 Bu::ServerSocket sSrv( 9987 ); 14 Bu::TcpServerSocket sSrv( 9987 );
15 15
16 Bu::Socket sSend("localhost", 9987 ); 16 Bu::TcpSocket sSend("localhost", 9987 );
17 17
18 Bu::Socket sRecv( sSrv.accept() ); 18 Bu::TcpSocket sRecv( sSrv.accept() );
19 19
20 printf("Connected sockets.\n"); 20 printf("Connected sockets.\n");
21 21
diff --git a/src/tests/socket.cpp b/src/tests/tcpsocket.cpp
index ba4e9b9..30dd22f 100644
--- a/src/tests/socket.cpp
+++ b/src/tests/tcpsocket.cpp
@@ -5,7 +5,7 @@
5 * terms of the license contained in the file LICENSE. 5 * terms of the license contained in the file LICENSE.
6 */ 6 */
7 7
8#include <bu/socket.h> 8#include <bu/tcpsocket.h>
9#include <bu/sio.h> 9#include <bu/sio.h>
10 10
11#include <sys/time.h> 11#include <sys/time.h>
@@ -17,7 +17,7 @@ bool isUp()
17{ 17{
18 try 18 try
19 { 19 {
20 Socket s("xagasoft.com", 9898, 1 ); 20 TcpSocket s("xagasoft.com", 9898, 1 );
21 21
22 char buf[5]; 22 char buf[5];
23 buf[s.read(buf, 2, 1, 0)] = '\0'; 23 buf[s.read(buf, 2, 1, 0)] = '\0';
diff --git a/src/tools/bnfcompile.cpp b/src/tools/bnfcompile.cpp
new file mode 100644
index 0000000..16e75a5
--- /dev/null
+++ b/src/tools/bnfcompile.cpp
@@ -0,0 +1,410 @@
1#include <bu/sio.h>
2#include <bu/lexer.h>
3#include <bu/parser.h>
4#include <bu/file.h>
5#include <bu/queuebuf.h>
6
7using namespace Bu;
8
9enum TokenType
10{
11 tokIdentifier,
12 tokColon,
13 tokOr,
14 tokSemiColon,
15 tokTokens,
16 tokEquals,
17 tokOpenCurly,
18 tokCloseCurly,
19 tokOpenSquare,
20 tokCloseSquare,
21
22 tokEos=-1
23};
24
25class BnfLexer : public Lexer
26{
27public:
28 BnfLexer( Stream &rSrc ) :
29 rSrc( rSrc )
30 {
31 }
32
33 virtual ~BnfLexer()
34 {
35 }
36
37 virtual Token *nextToken()
38 {
39 char cBuf;
40
41 for(;;)
42 {
43 if( qbIn.getSize() == 0 )
44 {
45 char buf[4096];
46 qbIn.write( buf, rSrc.read( buf, 4096 ) );
47
48 if( rSrc.isEos() && qbIn.getSize() == 0 )
49 return new Token( tokEos );
50 }
51 qbIn.peek( &cBuf, 1 );
52 if( (cBuf >= 'a' && cBuf <= 'z') ||
53 (cBuf >= 'A' && cBuf <= 'Z') ||
54 (cBuf >= '0' && cBuf <= '9') ||
55 cBuf == '_' )
56 {
57 sBuf.append( cBuf );
58 qbIn.seek( 1 );
59 }
60 else if( sBuf.isSet() )
61 {
62 if( sBuf == "tokens" )
63 {
64 sBuf.clear();
65 return new Token( tokTokens );
66 }
67 else
68 {
69 Token *pRet = new Token( tokIdentifier, sBuf );
70 sBuf.clear();
71 return pRet;
72 }
73 }
74 else
75 {
76 switch( cBuf )
77 {
78 case ' ':
79 case '\t':
80 case '\n':
81 case '\r':
82 qbIn.seek( 1 );
83 continue;
84
85 case ':':
86 qbIn.seek( 1 );
87 return new Token( tokColon );
88
89 case ';':
90 qbIn.seek( 1 );
91 return new Token( tokSemiColon );
92
93 case '|':
94 qbIn.seek( 1 );
95 return new Token( tokOr );
96
97 case '=':
98 qbIn.seek( 1 );
99 return new Token( tokEquals );
100
101 case '[':
102 qbIn.seek( 1 );
103 return new Token( tokOpenSquare );
104
105 case ']':
106 qbIn.seek( 1 );
107 return new Token( tokCloseSquare );
108
109 case '{':
110 qbIn.seek( 1 );
111 return new Token( tokOpenCurly );
112
113 case '}':
114 qbIn.seek( 1 );
115 return new Token( tokCloseCurly );
116
117 default:
118 throw ExceptionBase("Unexpected character '%c'.",
119 cBuf );
120 break;
121 }
122 }
123 }
124 }
125
126 virtual FString tokenToString( const Token &t )
127 {
128 switch( (TokenType)t.iToken )
129 {
130 case tokIdentifier: return "tokIdentifier";
131 case tokColon: return "tokColon";
132 case tokOr: return "tokOr";
133 case tokSemiColon: return "tokSemiColon";
134 case tokTokens: return "tokTokens";
135 case tokEquals: return "tokEquals";
136 case tokOpenCurly: return "tokOpenCurly";
137 case tokCloseCurly: return "tokCloseCurly";
138 case tokOpenSquare: return "tokOpenSquare";
139 case tokCloseSquare: return "tokCloseSquare";
140 case tokEos: return "tokEos";
141 }
142
143 return "???";
144 }
145
146private:
147 Stream &rSrc;
148 QueueBuf qbIn;
149 FString sBuf;
150};
151
152class BnfParser
153{
154public:
155 BnfParser( BnfLexer &l ) :
156 l( l ),
157 pCur( NULL ),
158 iLastToken( 0 )
159 {
160 }
161
162 virtual ~BnfParser()
163 {
164 delete pCur;
165 pCur = NULL;
166 }
167
168 void parse()
169 {
170 for(;;)
171 {
172 next();
173 switch( pCur->iToken )
174 {
175 case tokTokens:
176 tokens();
177 break;
178
179 case tokIdentifier:
180 nonTerminal();
181 break;
182
183 case tokEos:
184 return;
185 break;
186
187 default:
188 tokenError("tokTokens, tokIdentifier, or tokEos");
189 }
190 }
191 }
192
193private:
194 void tokens()
195 {
196 next();
197 if( pCur->iToken != tokEquals )
198 tokenError("tokEquals");
199 for(;;)
200 {
201 next();
202 if( pCur->iToken == tokIdentifier )
203 {
204 hTokens.insert( pCur->vExtra.get<Bu::FString>(), ++iLastToken );
205 sio << "Added token[" << iLastToken << "]: "
206 << pCur->vExtra.get<Bu::FString>() << sio.nl;
207 }
208 else if( pCur->iToken == tokSemiColon )
209 break;
210 else
211 tokenError("tokIdentifier or tokSemiColon");
212 }
213 }
214
215 void nonTerminal()
216 {
217 Bu::FString sNtName = pCur->vExtra.get<Bu::FString>();
218 Parser::NonTerminal nt;
219 p.addNonTerminal( sNtName );
220 sio.incIndent();
221 sio << "Created non-terminal: " << sNtName << sio.nl;
222
223 next();
224 if( pCur->iToken != tokColon )
225 tokenError("tokColon");
226 production( nt );
227 for(;;)
228 {
229 switch( pCur->iToken )
230 {
231 case tokOr:
232 production( nt );
233 break;
234
235 case tokSemiColon:
236 p.setNonTerminal( sNtName, nt );
237 sio.decIndent();
238 sio << "Closing non-terminal." << sio.nl;
239 return;
240
241 default:
242 tokenError("tkOr or tokSemiColon");
243 break;
244 }
245 }
246 }
247
248 void production( Parser::NonTerminal &nt )
249 {
250 sio.incIndent();
251 sio << "Adding new production:" << sio.nl;
252 Parser::Production pr;
253 bool bAnything = false;
254 for(;;)
255 {
256 next();
257 switch( pCur->iToken )
258 {
259 case tokIdentifier:
260 {
261 const Bu::FString &sName =
262 pCur->vExtra.get<Bu::FString>();
263 if( hTokens.has( sName ) )
264 {
265 pr.append(
266 Parser::State(
267 Parser::State::typeTerminal,
268 hTokens.get( sName )
269 )
270 );
271 sio << "Added terminal " << sName << sio.nl;
272 }
273 else
274 {
275 if( !p.hasNonTerminal( sName ) )
276 {
277 p.addNonTerminal( sName );
278 }
279 pr.append(
280 Parser::State(
281 Parser::State::typeNonTerminal,
282 p.getNonTerminalId( sName )
283 )
284 );
285 sio << "Added non-terminal " << sName << sio.nl;
286 }
287 }
288 break;
289
290 case tokOpenSquare:
291 {
292 next();
293 if( pCur->iToken != tokIdentifier )
294 tokenError("tokIdentifier");
295 Bu::FString sName =
296 pCur->vExtra.get<Bu::FString>();
297 next();
298 if( pCur->iToken != tokCloseSquare )
299 tokenError("tokCloseSquare");
300
301 if( !hTokens.has( sName ) )
302 throw ExceptionBase("Only token names may be "
303 "enclosed in square brackets.");
304
305 pr.append(
306 Parser::State(
307 Parser::State::typeTerminalPush,
308 hTokens.get( sName )
309 )
310 );
311 sio << "Added terminal-push " << sName << sio.nl;
312 }
313 break;
314
315 case tokOpenCurly:
316 {
317 next();
318 if( pCur->iToken != tokIdentifier )
319 tokenError("tokIdentifier");
320 Bu::FString sName =
321 pCur->vExtra.get<Bu::FString>();
322 next();
323 if( pCur->iToken != tokCloseCurly )
324 tokenError("tokCloseCurly");
325
326 if( !p.hasReduction( sName ) )
327 p.addReduction( sName );
328
329 pr.append(
330 Parser::State(
331 Parser::State::typeReduction,
332 p.getReductionId( sName )
333 )
334 );
335 sio << "Added reduction " << sName << sio.nl;
336 }
337 break;
338
339 case tokOr:
340 case tokSemiColon:
341 if( bAnything )
342 {
343 nt.addProduction( pr );
344 sio.decIndent();
345 sio << "Closing production." << sio.nl;
346 }
347 else
348 {
349 nt.setCanSkip();
350 sio.decIndent();
351 sio << "Closing empty production." << sio.nl;
352 }
353 return;
354
355 default:
356 tokenError("tokIdentifier, tokOpenSquare, tokOr, "
357 "tokOpenCurly, or tokSemiColon");
358 }
359 }
360 }
361
362private:
363 void next()
364 {
365 delete pCur;
366 pCur = l.nextToken();
367 }
368
369 void tokenError( const FString &s )
370 {
371 throw ExceptionBase( ("Expected " + s + " but found "
372 + l.tokenToString( *pCur ) + ".").getStr() );
373 }
374
375private:
376 typedef Bu::Hash<Bu::FString, int> TokenHash;
377 TokenHash hTokens;
378 BnfLexer &l;
379 BnfLexer::Token *pCur;
380 int iLastToken;
381 Parser p;
382};
383
384int main( int argc, char *argv[] )
385{
386 File fIn( argv[1], File::Read );
387
388 BnfLexer bl( fIn );
389 BnfParser parser( bl );
390
391 parser.parse();
392
393/*
394 for(;;)
395 {
396 Lexer::Token *pTok = bl.nextToken();
397 sio << bl.tokenToString(*pTok);
398 if( pTok->vExtra.isSet() )
399 {
400 sio << " - " << pTok->vExtra;
401 }
402 sio << sio.nl;
403 if( pTok->iToken == tokEos )
404 break;
405 }
406*/
407
408 return 0;
409}
410
diff --git a/src/tools/myriadfs.cpp b/src/tools/myriadfs.cpp
new file mode 100644
index 0000000..66955a5
--- /dev/null
+++ b/src/tools/myriadfs.cpp
@@ -0,0 +1,38 @@
1#define FUSE_USE_VERSION 26
2
3#include <fuse.h>
4
5#include <string.h>
6
7extern "C" {
8 static int myriadfs_getattr( const char *sPath, struct stat *stbuf )
9 {
10
11 }
12
13 static int myriadfs_readdir( const char *sPath, void *buf,
14 fuse_fill_dir_t filler, off_t offset, struct fuse_file_info *fi )
15 {
16 }
17
18 static int myriadfs_open( const char *sPath, struct fuse_file_info *fi )
19 {
20 }
21
22 static int myriadfs_read( const char *sPath, char *buf, size_t iSize,
23 off_t iOffset, struct fuse_file_info *fi )
24 {
25 }
26
27 static struct fuse_operations myriadfs_oper;
28
29 int main( int argc, char *argv[] )
30 {
31 memset( &myriadfs_oper, sizeof(myriadfs_oper), 0 );
32 myriadfs_oper.getattr = myriadfs_getattr;
33 myriadfs_oper.readdir = myriadfs_readdir;
34 myriadfs_oper.open = myriadfs_open;
35 myriadfs_oper.read = myriadfs_read;
36 return fuse_main( argc, argv, &myriadfs_oper, NULL );
37 }
38}
diff --git a/src/tools/parser.cpp b/src/tools/parser.cpp
index 76d4a72..7933f31 100644
--- a/src/tools/parser.cpp
+++ b/src/tools/parser.cpp
@@ -151,10 +151,43 @@ private:
151 151
152void redAdd( Bu::Parser &p ) 152void redAdd( Bu::Parser &p )
153{ 153{
154 Lexer::Token *a = p.popToken();
155 Lexer::Token *b = p.popToken();
156
157 sio << "Add! " << b->vExtra.get<double>() << " + "
158 << a->vExtra.get<double>() << sio.nl;
159
160 Lexer::Token *c = new Lexer::Token( tokNumber,
161 b->vExtra.get<double>() + a->vExtra.get<double>()
162 );
163 p.pushToken( c );
164
165 delete a;
166 delete b;
167}
168
169void redSubtract( Bu::Parser &p )
170{
171 Lexer::Token *a = p.popToken();
172 Lexer::Token *b = p.popToken();
173
174 sio << "Subtract! " << b->vExtra.get<double>() << " - "
175 << a->vExtra.get<double>() << sio.nl;
176
177 Lexer::Token *c = new Lexer::Token( tokNumber,
178 b->vExtra.get<double>() - a->vExtra.get<double>()
179 );
180 p.pushToken( c );
181
182 delete a;
183 delete b;
154} 184}
155 185
156void redPrint( Bu::Parser &p ) 186void redPrint( Bu::Parser &p )
157{ 187{
188 Lexer::Token *a = p.popToken();
189 sio << "Print! = " << a->vExtra.get<double>() << sio.nl;
190 delete a;
158} 191}
159 192
160/* Basic grammer example: 193/* Basic grammer example:
@@ -170,14 +203,15 @@ void redPrint( Bu::Parser &p )
170 * The problem is, that we can't actually make something left hand recursive, 203 * The problem is, that we can't actually make something left hand recursive,
171 * so we break it into two exprs: 204 * so we break it into two exprs:
172 * 205 *
173 * expr': '(' expr ')' 206 * expr-sub1: '(' expr ')'
174 * | NUMBER 207 * | NUMBER
175 * ; 208 * ;
176 * 209 *
177 * expr: expr' expr'' 210 * expr: expr-sub1 expr-sub2
178 * ; 211 * ;
179 * 212 *
180 * expr'': '+' expr 213 * expr-sub2: '+' expr
214 * | '-' expr
181 * | 215 * |
182 * ; 216 * ;
183 * 217 *
@@ -191,8 +225,8 @@ int main( int argc, char *argv[] )
191 Parser p; 225 Parser p;
192 226
193 p.addNonTerminal("expr"); 227 p.addNonTerminal("expr");
194 p.addNonTerminal("expr'"); 228 p.addNonTerminal("expr-sub1");
195 p.addNonTerminal("expr''"); 229 p.addNonTerminal("expr-sub2");
196 { 230 {
197 Parser::NonTerminal nt; 231 Parser::NonTerminal nt;
198 nt.addProduction( 232 nt.addProduction(
@@ -215,10 +249,28 @@ int main( int argc, char *argv[] )
215 ); 249 );
216 nt.addProduction( 250 nt.addProduction(
217 Parser::Production( 251 Parser::Production(
252 Parser::State(
253 Parser::State::typeTerminal,
254 tokMinus
255 )
256 ).append(
257 Parser::State(
258 Parser::State::typeNonTerminal,
259 p.getNonTerminalId("expr")
260 )
261 ).append(
262 Parser::State(
263 Parser::State::typeReduction,
264 p.addReduction("subtract")
265 )
266 )
267 );
268 nt.addProduction(
269 Parser::Production(
218 ) 270 )
219 ); 271 );
220 nt.setCanSkip(); 272 nt.setCanSkip();
221 p.setNonTerminal("expr''", nt ); 273 p.setNonTerminal("expr-sub2", nt );
222 } 274 }
223 { 275 {
224 Parser::NonTerminal nt; 276 Parser::NonTerminal nt;
@@ -230,7 +282,25 @@ int main( int argc, char *argv[] )
230 ) 282 )
231 ) 283 )
232 ); 284 );
233 p.setNonTerminal("expr'", nt ); 285 nt.addProduction(
286 Parser::Production(
287 Parser::State(
288 Parser::State::typeTerminal,
289 tokOpenParen
290 )
291 ).append(
292 Parser::State(
293 Parser::State::typeNonTerminal,
294 p.getNonTerminalId("expr")
295 )
296 ).append(
297 Parser::State(
298 Parser::State::typeTerminal,
299 tokCloseParen
300 )
301 )
302 );
303 p.setNonTerminal("expr-sub1", nt );
234 } 304 }
235 { 305 {
236 Parser::NonTerminal nt; 306 Parser::NonTerminal nt;
@@ -238,12 +308,12 @@ int main( int argc, char *argv[] )
238 Parser::Production( 308 Parser::Production(
239 Parser::State( 309 Parser::State(
240 Parser::State::typeNonTerminal, 310 Parser::State::typeNonTerminal,
241 p.getNonTerminalId("expr'") 311 p.getNonTerminalId("expr-sub1")
242 ) 312 )
243 ).append( 313 ).append(
244 Parser::State( 314 Parser::State(
245 Parser::State::typeNonTerminal, 315 Parser::State::typeNonTerminal,
246 p.getNonTerminalId("expr''") 316 p.getNonTerminalId("expr-sub2")
247 ) 317 )
248 ) 318 )
249 ); 319 );
@@ -275,6 +345,7 @@ int main( int argc, char *argv[] )
275 p.setRootNonTerminal("input"); 345 p.setRootNonTerminal("input");
276 346
277 p.setReduction("add", Bu::slot( &redAdd ) ); 347 p.setReduction("add", Bu::slot( &redAdd ) );
348 p.setReduction("subtract", Bu::slot( &redSubtract ) );
278 p.setReduction("print", Bu::slot( &redPrint ) ); 349 p.setReduction("print", Bu::slot( &redPrint ) );
279 350
280 p.pushLexer( new MathLexer( fIn ) ); 351 p.pushLexer( new MathLexer( fIn ) );
diff --git a/src/unit/fstring.unit b/src/unit/fstring.unit
index 00b6eed..c6d7414 100644
--- a/src/unit/fstring.unit
+++ b/src/unit/fstring.unit
@@ -339,4 +339,13 @@ suite FString
339 a = "This is a test."; 339 a = "This is a test.";
340 unitTest( a.replace("i", "ooo") == "Thooos ooos a test." ); 340 unitTest( a.replace("i", "ooo") == "Thooos ooos a test." );
341 } 341 }
342
343 test coreDerefBug1
344 {
345 Bu::FString a, b;
346 a = "bob";
347 a.setSize( 0 );
348 b = a;
349 b.getStr();
350 }
342} 351}
diff --git a/src/unit/hash.unit b/src/unit/hash.unit
index e3d7e42..124b074 100644
--- a/src/unit/hash.unit
+++ b/src/unit/hash.unit
@@ -84,4 +84,17 @@ suite Hash
84 printf(" - \"%s\" = %d\n", i.getKey().getStr(), i.getValue() ); 84 printf(" - \"%s\" = %d\n", i.getKey().getStr(), i.getValue() );
85 } */ 85 } */
86 } 86 }
87
88 test copy
89 {
90 StrIntHash h;
91 h.insert("hello", 55 );
92 h.insert("goodbye", -1812 );
93
94 StrIntHash h2 = h;
95 unitTest( h2.isCoreShared( h ) );
96
97 StrIntHash h3 = h.clone();
98 unitTest( !h3.isCoreShared( h ) );
99 }
87} 100}
diff --git a/src/utfstring.cpp b/src/utfstring.cpp
new file mode 100644
index 0000000..ae5efaf
--- /dev/null
+++ b/src/utfstring.cpp
@@ -0,0 +1,29 @@
1#include "bu/utfstring.h"
2
3template class Bu::FBasicString<short>;
4
5template<> uint32_t Bu::__calcHashCode<Bu::UtfString>( const Bu::UtfString &k )
6{
7 long j, sz = k.getSize()*2;
8 const char *s = (const char *)k.getStr();
9
10 long nPos = 0;
11 for( j = 0; j < sz; j++, s++ )
12 {
13 nPos = *s + (nPos << 6) + (nPos << 16) - nPos;
14 }
15
16 return nPos;
17}
18
19template<> bool Bu::__cmpHashKeys<Bu::UtfString>(
20 const Bu::UtfString &a, const Bu::UtfString &b )
21{
22 return a == b;
23}
24
25template<> void Bu::__tracer_format<Bu::UtfString>( const Bu::UtfString &v )
26{
27 printf("(%ld)\"%s\"", v.getSize(), (const char *)v.getStr() );
28}
29
diff --git a/src/utfstring.h b/src/utfstring.h
new file mode 100644
index 0000000..bbacb74
--- /dev/null
+++ b/src/utfstring.h
@@ -0,0 +1,24 @@
1#ifndef BU_UTF_STRING_H
2#define BU_UTF_STRING_H
3
4#include "bu/fbasicstring.h"
5
6namespace Bu
7{
8 typedef FBasicString<short> UtfString;
9
10 template<typename T>
11 uint32_t __calcHashCode( const T &k );
12
13 template<typename T>
14 bool __cmpHashKeys( const T &a, const T &b );
15
16 template<> uint32_t __calcHashCode<UtfString>( const UtfString &k );
17 template<> bool __cmpHashKeys<UtfString>(
18 const UtfString &a, const UtfString &b );
19
20 template<typename t> void __tracer_format( const t &v );
21 template<> void __tracer_format<UtfString>( const UtfString &v );
22}
23
24#endif
diff --git a/src/variant.h b/src/variant.h
index 8e1203c..f659ad2 100644
--- a/src/variant.h
+++ b/src/variant.h
@@ -17,6 +17,7 @@ namespace Bu
17{ 17{
18 class Formatter; 18 class Formatter;
19 class Variant; 19 class Variant;
20 /** @cond DEVEL */
20 template<class t> class VariantType; 21 template<class t> class VariantType;
21 22
22 class VariantTypeRoot 23 class VariantTypeRoot
@@ -92,7 +93,22 @@ namespace Bu
92 private: 93 private:
93 t data; 94 t data;
94 }; 95 };
95 96 /** @endcond */
97
98 /**
99 * Store any data type and access it safely. Variant gives you a way to
100 * pass arbitrary data types around without having to worry about what
101 * type a variable is. It allows code to be easily extended and to manage
102 * data without having to know what type it is ahead of time.
103 *
104 * Because of the generic method that this class was implemented it may seem
105 * to have some drawbacks compared to other Variant classes you may have
106 * seen, however it is fairly easy to get it to do just about anything you
107 * may need. It is also very low overhead. On most compilers the class
108 * itself has only 3 words of overhead + the size of the variable you store
109 * in it. And, since many parts of it are templatized they can often be
110 * optimized quite a bit.
111 */
96 class Variant 112 class Variant
97 { 113 {
98 public: 114 public: