aboutsummaryrefslogtreecommitdiff
path: root/src/myriad.h
blob: 9bbc812e13250c5f43f389f8d676e0e383602a78 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/*
 * Copyright (C) 2007-2010 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"

namespace Bu
{
	class Stream;
	class MyriadStream;

	subExceptionDecl( MyriadException )

	/**
	 * Numerically Indexed Data Streams.  This is a working name so I can
	 * actually get some code written instead of agonizing over the name.
	 *
	 * This is a system for creating streams that contain other streams in
	 * a flexible block-allocated system.
	 *
	 * Header format is as follows:
	 *
	 * MMMMvBssssSSSS*
	 * M = Magic number (FFC399BD)
	 * 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:
		Myriad( Bu::Stream &sStore );
		virtual ~Myriad();

		/**
		 * 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();

		/**
		 * Create a new Myriad system in the assosiated stream.  This should be
		 * used carefully, it will destroy all data already within the stream.
		 * More options will probably be added soon.
		 */
		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 );

		/**
		 * 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 );

		int getBlockSize();
		int getNumBlocks();
		int getNumUsedBlocks();
		int getBlockOverhead();

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

	private:
		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 );

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

#endif