Bu::Myriad now only uses BitString during initialization, and I'm going to

replace that with just an array, no problem.  It's many, many, many times
faster while streams are growing, and it should be constant time, not linear
like it was before.

It also handles myriad files in excess of 2gb correctly now, at least, it
seems to just fine :)

5 files changed, 111 insertions, 56 deletions

diff --git a/default.bld b/default.bld
index 6b6bbc3..c1b93af 100644
--- a/default.bld
+++ b/default.bld
@@ -14,8 +14,8 @@
 include "gensigs.bld";
 
 CXXFLAGS += "-ggdb -W -Wall -I.";
-// CXXFLAGS += "-pg";
-// LDFLAGS += "-pg";
+//CXXFLAGS += "-pg";
+//LDFLAGS += "-pg";
 
 action "default"
 {
@@ -151,7 +151,7 @@ target "viewcsv"
         LDFLAGS += "-lncurses";
 }
 
-target ["myriad", "myriadfs", "tests/myriad", "tests/myriadfs", "unit/myriad"]
+target ["myriad", "myriadfs", "tests/myriad", "tests/myriadfs", "unit/myriad", "tests/bigmyriad"]
 {
         LDFLAGS += "-lpthread";
 }
diff --git a/src/stable/file.cpp b/src/stable/file.cpp
index 33420f1..14e4f3c 100644
--- a/src/stable/file.cpp
+++ b/src/stable/file.cpp
@@ -91,7 +91,11 @@ Bu::size Bu::File::tell()
         if( fd < 0 )
                 throw FileException("File not open.");
 
+#ifdef USE_64BIT_IO
+        return lseek64( fd, 0, SEEK_CUR );
+#else
         return lseek( fd, 0, SEEK_CUR );
+#endif
 }
 
 void Bu::File::seek( Bu::size offset )
@@ -99,7 +103,11 @@ void Bu::File::seek( Bu::size offset )
         if( fd < 0 )
                 throw FileException("File not open.");
 
+#ifdef USE_64BIT_IO
+        lseek64( fd, offset, SEEK_CUR );
+#else
         lseek( fd, offset, SEEK_CUR );
+#endif
         bEos = false;
 }
 
@@ -108,7 +116,11 @@ void Bu::File::setPos( Bu::size pos )
         if( fd < 0 )
                 throw FileException("File not open.");
 
+#ifdef USE_64BIT_IO
+        lseek64( fd, pos, SEEK_SET );
+#else
         lseek( fd, pos, SEEK_SET );
+#endif
         bEos = false;
 }
 
@@ -117,7 +129,7 @@ void Bu::File::setPosEnd( Bu::size pos )
         if( fd < 0 )
                 throw FileException("File not open.");
         
-        lseek( fd, pos, SEEK_END );
+        lseek64( fd, pos, SEEK_END );
         bEos = false;
 }
 
diff --git a/src/stable/myriad.cpp b/src/stable/myriad.cpp
index 7246df3..4f65583 100644
--- a/src/stable/myriad.cpp
+++ b/src/stable/myriad.cpp
@@ -84,8 +84,9 @@ void Bu::Myriad::sync()
 void Bu::Myriad::initialize()
 {
         MutexLocker mLock( mHeader );
+        lFreeBlocks.clear();
         sStore.setPosEnd( 0 );
-        int iSize = sStore.tell();
+        Bu::size iSize = sStore.tell();
         sStore.setPos( 0 );
 
         unsigned char buf[4];
@@ -131,8 +132,11 @@ void Bu::Myriad::initialize()
         {
                 pFakeHdr->aBlocks.append( j );
         }
-        
-        bsBlockUsed.setSize( iBlocks, true );
+
+//      sio << "Blocks: " << iBlocks << " (size = " << iSize << "/" << iBlockSize
+//              << ")" << sio.nl;
+        Bu::BitString bsBlockUsed( iBlocks, false );
+        bsBlockUsed.clear();
 
 //      bool bCanSkip = false; // Can skip around, post initial header stream i/o
         MyriadStream *pIn = new MyriadStream( *this, pFakeHdr );
@@ -174,12 +178,21 @@ void Bu::Myriad::initialize()
         }
         delete pIn;
 
-        //sio << "Myriad: Blocks used: " << bsBlockUsed.toString() << sio.nl;
+        for( int j = 0; j < iBlocks; j++ )
+        {
+                if( bsBlockUsed.getBit( j ) == false )
+                {
+//                      sio << "Preinitialized block " << j << " is free." << sio.nl;
+                        lFreeBlocks.append( j );
+                }
+        }
+//      sio << "Myriad: Blocks used: " << bsBlockUsed.toString() << sio.nl;
 }
 
 void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate )
 {
         MutexLocker mLock( mHeader );
+        lFreeBlocks.clear();
 
         for( StreamArray::iterator i = aStreams.begin(); i; i++ )
         {
@@ -207,7 +220,7 @@ void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate )
         //sio << "Myriad: iHeaderSize=" << iHeaderSize << ", iBlockSize="
         //      << iBlockSize << ", iHeaderBlocks=" << iHeaderBlocks << sio.nl;
         
-        bsBlockUsed.setSize( iPreAllocate, true );
+//      bsBlockUsed.setSize( iPreAllocate, true );
         iUsed++;
 
         char *pBlock = new char[iBlockSize];
@@ -255,10 +268,16 @@ void Bu::Myriad::initialize( int iBlockSize, int iPreAllocate )
         pStr->iSize = iHeaderSize;
         for( int j = 0; j < iHeaderBlocks; j++ )
         {
+//              sio << "Started block " << j << " is header." << sio.nl;
                 pStr->aBlocks.append( j );
-                bsBlockUsed.setBit( j );
+//              bsBlockUsed.setBit( j );
                 iUsed++;
         }
+        for( int j = iHeaderBlocks; j < this->iBlocks; j++ )
+        {
+//              sio << "Started block " << j << " is free." << sio.nl;
+                lFreeBlocks.append( j );
+        }
 
         aStreams.append( pStr );
 
@@ -302,7 +321,7 @@ void Bu::Myriad::updateHeader()
 //              sio << "Myriad: updateHeader: Appending block " << iBlock
 //                      << " to header." << sio.nl;
                 aStreams[0]->aBlocks.append( iBlock );
-                bsBlockUsed.setBit( iBlock );
+//              bsBlockUsed.setBit( iBlock );
                 iUsed++;
                 iHeaderSize += 4;
                 iNewBlocks = blkDiv( iHeaderSize, iBlockSize );
@@ -361,7 +380,7 @@ int Bu::Myriad::createStream( int iPreAllocate )
                 int iFreeBlock = findEmptyBlock();
 //              sio << "Myriad: Adding block " << iFreeBlock << sio.nl;
                 pStr->aBlocks.append( iFreeBlock );
-                bsBlockUsed.setBit( iFreeBlock );
+//              bsBlockUsed.setBit( iFreeBlock );
                 iUsed++;
         }
 
@@ -408,7 +427,7 @@ int Bu::Myriad::createStreamWithId( int iId, int iPreAllocate )
                         int iFreeBlock = findEmptyBlock();
         //              sio << "Myriad: Adding block " << iFreeBlock << sio.nl;
                         pStr->aBlocks.append( iFreeBlock );
-                        bsBlockUsed.setBit( iFreeBlock );
+//                      bsBlockUsed.setBit( iFreeBlock );
                         iUsed++;
                 }
 
@@ -422,26 +441,15 @@ int Bu::Myriad::findEmptyBlock()
 {
         bHeaderChanged = true;
 
-        for( int j = 0; j < bsBlockUsed.getSize(); j++ )
+        if( lFreeBlocks.isEmpty() )
         {
-                if( bsBlockUsed.getBit( j ) == false )
-                        return j;
+                sStore.setSize( (iBlocks+1)*(Bu::size)iBlockSize );
+                return iBlocks++;
+        }
+        else
+        {
+                return lFreeBlocks.dequeue();
         }
-//      sio << "Myriad: findEmptyBlock(): No empty blocks, adding new one." << sio.nl;
-
-        bsBlockUsed.setSize( bsBlockUsed.getSize()+1, false );
-        /*
-        sStore.setPos( iBlockSize*iBlocks );
-
-        char *pBlock = new char[iBlockSize];
-        memset( pBlock, 0, iBlockSize );
-        sStore.write( pBlock, iBlockSize );
-        delete[] pBlock;
-        */
-
-        sStore.setSize( (iBlocks+1)*iBlockSize );
-
-        return iBlocks++;
 }
 
 void Bu::Myriad::deleteStream( int iId )
@@ -461,7 +469,8 @@ void Bu::Myriad::deleteStream( int iId )
                         Stream *pStream = *i;
                         for( BlockArray::iterator j = pStream->aBlocks.begin(); j; j++ )
                         {
-                                bsBlockUsed.setBit( *j, false );
+                                lFreeBlocks.append( *j );
+//                              bsBlockUsed.setBit( *j, false );
                                 iUsed--;
                         }
                         aStreams.erase( i );
@@ -536,11 +545,11 @@ int Bu::Myriad::getNumUsedBlocks()
         return iUsed;
 }
 
-int Bu::Myriad::getTotalUsedBytes()
+Bu::size Bu::Myriad::getTotalUsedBytes()
 {
         MutexLocker mLock( mHeader );
 
-        int iTotalSize = 0;
+        Bu::size iTotalSize = 0;
         for( StreamArray::iterator i = aStreams.begin(); i; i++ )
         {
                 iTotalSize += (*i)->iSize;
@@ -548,23 +557,23 @@ int Bu::Myriad::getTotalUsedBytes()
         return iTotalSize;
 }
 
-int Bu::Myriad::getTotalUnusedBytes()
+Bu::size Bu::Myriad::getTotalUnusedBytes()
 {
         MutexLocker mLock( mHeader );
 
-        int iTotalSize = (iBlocks-iUsed)*iBlockSize;
+        Bu::size iTotalSize = (iBlocks-iUsed)*iBlockSize;
         for( StreamArray::iterator i = aStreams.begin(); i; i++ )
         {
-                iTotalSize += iBlockSize - ((*i)->iSize%iBlockSize);
+                iTotalSize += iBlockSize - ((Bu::size)(*i)->iSize%iBlockSize);
         }
         return iTotalSize;
 }
 
-int Bu::Myriad::getTotalUnusedBytes( int iFakeBlockSize )
+Bu::size Bu::Myriad::getTotalUnusedBytes( int iFakeBlockSize )
 {
         MutexLocker mLock( mHeader );
 
-        int iTotalSize = (iBlocks-iUsed)*iFakeBlockSize;
+        Bu::size iTotalSize = (iBlocks-iUsed)*iFakeBlockSize;
         for( StreamArray::iterator i = aStreams.begin(); i; i++ )
         {
                 iTotalSize += iFakeBlockSize - ((*i)->iSize%iFakeBlockSize);
@@ -592,7 +601,7 @@ Bu::Myriad::Block *Bu::Myriad::getBlock( int iBlock )
 //              << iBlockSize*iBlock << "-" << iBlockSize*(iBlock+1) << sio.nl;
         Block *pBlock = new Block;
         pBlock->pData = new char[iBlockSize];
-        sStore.setPos( iBlockSize * iBlock );
+        sStore.setPos( iBlockSize * (Bu::size)iBlock );
         sStore.read( pBlock->pData, iBlockSize );
         pBlock->bChanged = false;
         pBlock->iBlockIndex = iBlock;
@@ -623,7 +632,7 @@ void Bu::Myriad::syncBlock( Block *pBlock )
         if( pBlock->bChanged )
         {
 //              sio << "Myriad:    - Block changed, writing back to stream." << sio.nl;
-                sStore.setPos( iBlockSize * pBlock->iBlockIndex );
+                sStore.setPos( iBlockSize * (Bu::size)pBlock->iBlockIndex );
                 sStore.write( pBlock->pData, iBlockSize );
                 pBlock->bChanged = false;
         }
@@ -635,8 +644,8 @@ int Bu::Myriad::streamAddBlock( Stream *pStream )
 
         int iBlock = findEmptyBlock();
         pStream->aBlocks.append( iBlock );
-        bsBlockUsed.setBit( iBlock );
-        bHeaderChanged = true;
+//      bsBlockUsed.setBit( iBlock );
+//      bHeaderChanged = true;
         iUsed++;
         return iBlock;
 }
@@ -655,11 +664,12 @@ void Bu::Myriad::setStreamSize( Stream *pStream, long iSize )
                 for( int iNewSize = pStream->aBlocks.getSize()*iBlockSize;
                          iNewSize-iBlockSize > iSize; iNewSize -= iBlockSize )
                 {
-                        if( bsBlockUsed.getBit( pStream->aBlocks.last() ) )
+//                      if( bsBlockUsed.getBit( pStream->aBlocks.last() ) )
                                 iUsed--;
-                        else
-                                sio << "Unused block used in stream? " << pStream->aBlocks.last() << sio.nl;
-                        bsBlockUsed.setBit( pStream->aBlocks.last(), false );
+//                      else
+//                              sio << "Unused block used in stream? " << pStream->aBlocks.last() << sio.nl;
+                        lFreeBlocks.enqueue( pStream->aBlocks.last() );
+//                      bsBlockUsed.setBit( pStream->aBlocks.last(), false );
                         pStream->aBlocks.eraseLast();
                 }
                 pStream->iSize = iSize;
@@ -674,8 +684,8 @@ void Bu::Myriad::setStreamSize( Stream *pStream, long iSize )
                         //streamAddBlock( pStream );
                         int iBlock = findEmptyBlock();
                         pStream->aBlocks.append( iBlock );
-                        bsBlockUsed.setBit( iBlock );
-                        bHeaderChanged = true;
+//                      bsBlockUsed.setBit( iBlock );
+//                      bHeaderChanged = true;
                         iUsed++;
                 }
                 pStream->iSize = iSize;
@@ -712,8 +722,13 @@ bool Bu::Myriad::isMyriad( Bu::Stream &sStore, uint8_t &uTmp )
         return true;
 }
 
-const Bu::BitString &Bu::Myriad::getBlocksUsed() const
+const Bu::BitString Bu::Myriad::getBlocksUsed() const
 {
-        return bsBlockUsed;
+        Bu::BitString bs( iBlocks, false );
+        for( int j = 0; j < iBlocks; j++ )
+                bs.setBit( j );
+        for( IndexList::const_iterator i = lFreeBlocks.begin(); i; i++ )
+                bs.setBit( *i, false );
+        return bs;
 }
 
diff --git a/src/stable/myriad.h b/src/stable/myriad.h
index 80b5c2b..6b1db41 100644
--- a/src/stable/myriad.h
+++ b/src/stable/myriad.h
@@ -14,6 +14,7 @@
 #include "bu/array.h"
 #include "bu/hash.h"
 #include "bu/mutex.h"
+#include "bu/extratypes.h"
 
 namespace Bu
 {
@@ -139,9 +140,9 @@ namespace Bu
                 int getBlockSize();
                 int getNumBlocks();
                 int getNumUsedBlocks();
-                int getTotalUsedBytes();
-                int getTotalUnusedBytes();
-                int getTotalUnusedBytes( int iFakeBlockSize );
+                Bu::size getTotalUsedBytes();
+                Bu::size getTotalUnusedBytes();
+                Bu::size getTotalUnusedBytes( int iFakeBlockSize );
 
                 /**
                  * Syncronize the header data, etc. with the storage stream.  It's not
@@ -163,7 +164,7 @@ namespace Bu
                  */
                 static bool isMyriad( Bu::Stream &sStore );
 
-                const Bu::BitString &getBlocksUsed() const;
+                const Bu::BitString getBlocksUsed() const;
 
         private:
                 /**
@@ -219,7 +220,9 @@ namespace Bu
                 int iBlockSize;
                 int iBlocks;
                 int iUsed;
-                Bu::BitString bsBlockUsed;
+                typedef Bu::List<int> IndexList;
+                IndexList lFreeBlocks;
+//              Bu::BitString bsBlockUsed;
                 StreamArray aStreams;
                 typedef Bu::Hash<int, Block *> BlockHash;
                 BlockHash hActiveBlocks;
diff --git a/src/tests/bigmyriad.cpp b/src/tests/bigmyriad.cpp
new file mode 100644
index 0000000..6661bf1
--- /dev/null
+++ b/src/tests/bigmyriad.cpp
@@ -0,0 +1,25 @@
+#include <bu/myriad.h>
+#include <bu/myriadstream.h>
+#include <bu/file.h>
+
+int main()
+{
+        Bu::File f("big.myr", Bu::File::Read|Bu::File::Write|Bu::File::Create );
+        Bu::Myriad m( f, 2048 );
+
+        char *buf = new char[1024*1024*10];
+        memset( buf, 0, 1024*1024*10 );
+
+        for( int j = 0; j < 250; j++ )
+        {
+                m.openStream( m.createStream() ).write( buf, 1024*1024*10 );
+//              m.sync();
+                printf("\r%03d%%", (j+1)*100/250 );
+                fflush( stdout );
+        }
+
+        printf("\n\n");
+
+        return 0;
+}
+