path: root/src/stable/myriad.h

/*
 * Copyright (C) 2007-2014 Xagasoft, All rights reserved.
 *
 * This file is part of the libbu++ library and is released under the
 * terms of the license contained in the file LICENSE.
 */

#ifndef BU_MYRIAD_H
#define BU_MYRIAD_H

#include <stdint.h>
#include "bu/bitstring.h"
#include "bu/exceptionbase.h"
#include "bu/array.h"
#include "bu/hash.h"
#include "bu/mutex.h"
#include "bu/extratypes.h"

namespace Bu
{
    class Stream;
    class MyriadStream;

    subExceptionDeclBegin( MyriadException )
        enum
        {
            emptyStream,
            invalidFormat,
            badVersion,
            invalidWordSize,
            noSuchStream,
            streamExists,
            invalidStreamId,
            protectedStream
        };
    subExceptionDeclEnd();

    /**
     * Myriad block-allocated stream multiplexing system.  This is a system for
     * creating streams that contain other streams in a flexible and lightweight
     * manner.  Basically, you can create a file (or any other stream) that can
     * store any number of flexible, growing streams.  The streams within the
     * Myriad stream are automatically numbered, not named.  This works more
     * or less like a filesystem, but without the extra layer for managing
     * file and directory links.  This would actually be very easy to add
     * on top of Myriad, but is not required.
     *
     * Header format is as follows:
     *
     * MMMMvBssssSSSS*
     * M = Magic number (0AD3FA84)
     * v = version number
     * B = Bits per int
     * s = Blocksize in bytes
     * S = Number of Streams
     * 
     * The * represents the Stream headers, one per stream, as follows:
     * IIIIssss$
     * I = Id number of the stream
     * s = size of stream in bytes
     *
     * The $ represents the Block headers, one per used block, as  follows:
     * IIII
     * I = Index of the block
     *
     * The stream/block data is interleaved in the header, so all blocks stored
     * with one stream are together.  The block headers are in order, and the
     * data in them is required to be "solid" you cannot fill partial blocks
     * mid-way through a stream.
     *
     * The initial block starts with the nids header, and is both the zero block
     * and the zero stream.  For now, the minimum block size is the size needed
     * to store the base header, the zero stream header, and the first two
     * blocks of the zero stream, so 30 bytes.  Since it's reccomended to use
     * a size that will fit evenly into filesystem blocks, then a size of 32 is
     * probably the smallest reccomended size because all powers of two equal
     * to or greater than 32 are evenly divisible by 32.
     *
     * I have had a thought that if the block size were smaller than 42 bytes
     * the header would consume the first N blocks where N * block size is
     * enough space to house the initial header, the first stream header, and
     * the first N block headers.  This, of course, causes you to hit an
     * infinite header if the block size is small enough.
     */
    class Myriad
    {
        friend class MyriadStream;
    public:
        /**
         * Create a Myriad object that uses the given stream to store data.
         * This stream must be random access.  The block size and preallocate
         * values passed in are values that will be used if the given stream
         * is empty.  In that case the stream will be "formatted" for myriad
         * with the specified block size.  If there is already a viable Myriad
         * format present in the stream, then the blocksize and preallocate
         * values will be ignored and the values from the stream will be used
         * instead.  If the stream doesn't appear to be Myriad formatted an
         * exception will be thrown.
         */
        Myriad( Bu::Stream &sStore, int iBlockSize=512, int iPreallocate=8 );
        virtual ~Myriad();

        /**
         * Destroy whatever data may be in the base stream and create a new
         * Myriad system there with the given blocksize.  Use this with care,
         * it will destroy anything that was already in the stream, and
         * generally, should not ever have to be used.
         */
        void initialize( int iBlockSize, int iPreAllocate=1 );

        /**
         * Create a new stream within the Myriad system.  The ID of the new
         * stream is returned.
         */
        int createStream( int iPreAllocate=1 );

        /**
         * Create a new stream within the Myriad system with a given id.  The
         * id that you provide will be the new id of the stream unless it's
         * already used, in which case an error is thrown.  This is primarilly
         * useful when copying an old Myriad file into a new one.
         */
        int createStreamWithId( int iId, int iPreAllocate=1 );

        /**
         * Delete a stream that's already within the Myriad.
         */
        void deleteStream( int iId );

        /**
         * Return a new Stream object assosiated with the given stream ID.
         */
        MyriadStream openStream( int iId );

        Bu::Array<int> getStreamIds();
        int getStreamSize( int iId );
        bool hasStream( int iId );

        int getNumStreams();
        int getBlockSize();
        int getNumBlocks();
        int getNumUsedBlocks();
        Bu::size getTotalUsedBytes();
        Bu::size getTotalUnusedBytes();
        Bu::size getTotalUnusedBytes( int iFakeBlockSize );

        /**
         * Syncronize the header data, etc. with the storage stream.  It's not
         * a bad idea to call this periodically.
         */
        void sync();

        /**
         * Read the first few bytes from the given stream and return true/false
         * depending on weather or not it's a Myriad stream.  This will throw
         * an exception if the stream is empty, or is not random access.
         */
        static bool isMyriad( Bu::Stream &sStore, uint8_t &uVer );
        
        /**
         * Read the first few bytes from the given stream and return true/false
         * depending on weather or not it's a Myriad stream.  This will throw
         * an exception if the stream is empty, or is not random access.
         */
        static bool isMyriad( Bu::Stream &sStore );

        const Bu::BitString getBlocksUsed() const;

    private:
        /**
         * Initialize this object based on the data already in the assosiated
         * stream.  This will be called automatically for you if you forget,
         * but if you want to pre-initialize for some reason, just call this
         * once before you actually start doing anything with your Myriad.
         */
        void initialize();

        enum
        {
            blockUnused =   0xFFFFFFFFUL
        };
        
        typedef Bu::Array<int> BlockArray;
        class Stream
        {
        public:
            int iId;
            int iSize;
            BlockArray aBlocks;
        };
        typedef Bu::Array<Stream *> StreamArray;

        class Block
        {
        public:
            char *pData;
            bool bChanged;
            int iBlockIndex;
        };

        void updateHeader();
        int findEmptyBlock();

        /**
         *@todo Change this to use a binary search, it's nicer.
         */
        Stream *findStream( int iId );

        Block *getBlock( int iBlock );
        void releaseBlock( Block *pBlock );
        void syncBlock( Block *pBlock );

        int streamAddBlock( Stream *pStream );
        void setStreamSize( Stream *pStream, long iSize );

        void headerChanged();

    private:
        Bu::Stream &sStore;
        int iBlockSize;
        int iBlocks;
        int iUsed;
        typedef Bu::List<int> IndexList;
        IndexList lFreeBlocks;
//      Bu::BitString bsBlockUsed;
        StreamArray aStreams;
        typedef Bu::Hash<int, Block *> BlockHash;
        BlockHash hActiveBlocks;
        bool bHeaderChanged;

        Bu::Mutex mHeader;
        Bu::Mutex mActiveBlocks;
    };
};

#endif