using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace RaptorDB
{
internal class IndexFile
{
FileStream file = null;
private byte[] FileHeader = new byte[] {
(byte)'M', (byte)'G', (byte)'I',
0, // 3 = [keysize] max 255
0,0, // 4 = [node size] max 65536
0,0,0,0,0,0,0,0, // 6 = [root page num]
0, // 14 = Index file type : 0=BTREE 1=HASH
0,0,0,0 // 15 = bucket count
};
private byte[] BlockHeader = new byte[] {
(byte)'P',(byte)'A',(byte)'G',(byte)'E',
0, // 4 = [Flag] = 0=free 1=leaf 2=root 4=revisionpage --8=bucket 16=revisionbucket
0,0, // 5 = [item count]
0,0,0,0,0,0,0,0, // 7 = [parent page number] / [bucket number]
0,0,0,0,0,0,0,0 // 15 = [right page number] / [next page number]
};
internal byte _maxKeySize;
internal short _PageNodeCount = 50;
private long _LastPageNumber = 0;
private int _PageLength;
private long _CurrentRootPage = 0;
private int _rowSize;
internal int _DuplicatesPerPage = 1;
internal int _BucketCount = 11;
internal INDEXTYPE _indexType = INDEXTYPE.BTREE;
public IndexFile(string filename, byte maxKeySize, short pageNodeCount, int bucketcount, INDEXTYPE type)
{
_maxKeySize = maxKeySize;
_PageNodeCount = pageNodeCount;
_rowSize = (_maxKeySize + 1 + 8 + 8);
_BucketCount = bucketcount;
_indexType = type;
string path = Path.GetDirectoryName(filename);
Directory.CreateDirectory(path);
if (File.Exists(filename))
{
// if file exists open and read header
file = File.Open(filename, FileMode.Open, FileAccess.ReadWrite);
ReadFileHeader();
// compute last page number from file length
_PageLength = (BlockHeader.Length + _rowSize * (_PageNodeCount));
_LastPageNumber = (file.Length - FileHeader.Length - bucketcount * 8) / _PageLength;
}
else
{
// else create new file
file = File.Open(filename, FileMode.Create, FileAccess.ReadWrite);
_PageLength = (BlockHeader.Length + _rowSize * (_PageNodeCount));
CreateFileHeader();
_LastPageNumber = (file.Length - FileHeader.Length - bucketcount * 8) / _PageLength;
}
_DuplicatesPerPage = (_PageLength - BlockHeader.Length - 4) / 8;
// FIX : if index chk exists rollback changes to index
}
#region [ C o m m o n ]
private void CreateFileHeader()
{
// max key size
byte[] b = Helper.GetBytes(_maxKeySize);
Buffer.BlockCopy(b, 0, FileHeader, 3, 1);
// page node count
b = Helper.GetBytes(_PageNodeCount);
Buffer.BlockCopy(b, 0, FileHeader, 4, 2);
// bucket count
b = Helper.GetBytes(_BucketCount);
Buffer.BlockCopy(b, 0, FileHeader, 15, 4);
if (_indexType == INDEXTYPE.HASH)
FileHeader[14] = 1;
file.Seek(0L, SeekOrigin.Begin);
file.Write(FileHeader, 0, FileHeader.Length);
//file.Flush();
// write bucket lookup
b = new byte[_BucketCount * 8];
for (int i = 0; i < b.Length; i++)
b[i] = 255;
file.Write(b, 0, b.Length);
file.Flush();
if (_indexType == INDEXTYPE.BTREE)
{
Node n = new Node(3, -1, new List<KeyPointer>(), null, 0, -1);
SaveNode(n);
}
}
private void WriteHeader(long rootpage)
{
byte[] b = Helper.GetBytes(rootpage);
Buffer.BlockCopy(b, 0, FileHeader, 6, 8);
file.Seek(0L, SeekOrigin.Begin);
file.Write(FileHeader, 0, FileHeader.Length);
file.Flush();
}
private bool ReadFileHeader()
{
file.Seek(0L, SeekOrigin.Begin);
byte[] b = new byte[FileHeader.Length];
file.Read(b, 0, FileHeader.Length);
if (b[0] == FileHeader[0] && b[1] == FileHeader[1] && b[2] == FileHeader[2])
{
byte maxks = b[3];
short nodes = Helper.ToInt16(b, 4);
long root = Helper.ToInt64(b, 6);
_maxKeySize = maxks;
_PageNodeCount = nodes;
_CurrentRootPage = root;
FileHeader = b;
if (b[14] == (int)_indexType)
return true;
else
throw new Exception("Index type does not match file index type");
}
return false;
}
public long GetNewPageNumber()
{
return _LastPageNumber++;
}
private void SeekPage(long pnum)
{
long offset = FileHeader.Length + _BucketCount * 8;
offset += pnum * _PageLength;
if (offset > file.Length)
throw new Exception("file seek out of bounds =" + offset + " file len = " + file.Length);
file.Seek(offset, SeekOrigin.Begin);
}
public void Shutdown()
{
file.Flush();
file.Close();
}
#endregion
#region [ N O D E S ]
public Node GetRoot()
{
return LoadNodeFromPageNumber(_CurrentRootPage);
}
public bool Commit(IDictionary<long, Node> nodes)
{
foreach (Node n in nodes.Values)
{
if (n.isDirty)
{
SaveNode(n);
if (n.isRootPage)
{
WriteHeader(n.DiskPageNumber);
_CurrentRootPage = n.DiskPageNumber;
}
}
}
return true;
}
private void SaveNode(Node node)
{
long pnum = node.DiskPageNumber;
if (pnum > _LastPageNumber)
throw new Exception("should not be here: page out of bounds");
SeekPage(pnum);
byte[] page = new byte[_PageLength];
Buffer.BlockCopy(BlockHeader, 0, page, 0, BlockHeader.Length);
// node type
if (node.isLeafPage)
page[4] = 1;
if (node.isRootPage)
page[4] += 2;
if (node.isDuplicatePage)
page[4] += 4;
// node count
byte[] b = Helper.GetBytes(node.Count);
Buffer.BlockCopy(b, 0, page, 5, b.Length);
// node parent
b = Helper.GetBytes(node.ParentPageNumber);
Buffer.BlockCopy(b, 0, page, 7, b.Length);
// right page number
b = Helper.GetBytes(node.RightPageNumber);
Buffer.BlockCopy(b, 0, page, 15, b.Length);
int index = BlockHeader.Length;
if (node.isDuplicatePage == true)
{
b = Helper.GetBytes(node.Duplicates.Count);
Buffer.BlockCopy(b, 0, page, index, b.Length);
index += b.Length;
foreach (long p in node.Duplicates)
{
b = Helper.GetBytes(p);
Buffer.BlockCopy(b, 0, page, index, b.Length);
index += b.Length;
}
}
else
{
// node children
for (int i = 0; i < node.Count; i++)
{
KeyPointer kp = node.ChildPointers[i];
int idx = index + _rowSize * i;
// key size = 1 byte
page[idx] = (byte)kp.Key.val.Length;
// key bytes
Buffer.BlockCopy(node.ChildPointers[i].Key.val, 0, page, idx + 1, page[idx]);
// offset = 8 bytes
b = Helper.GetBytes(kp.Offset);
Buffer.BlockCopy(b, 0, page, idx + 1 + _maxKeySize, b.Length);
// duplicatepage = 8 bytes
b = Helper.GetBytes(kp.DuplicatesPage);
Buffer.BlockCopy(b, 0, page, idx + 1 + _maxKeySize + 8, b.Length);
}
}
file.Write(page, 0, page.Length);
file.Flush();
}
public Node LoadNodeFromPageNumber(long number)
{
SeekPage(number);
byte[] b = new byte[_PageLength];
file.Read(b, 0, _PageLength);
if (b[0] == BlockHeader[0] && b[1] == BlockHeader[1] && b[2] == BlockHeader[2] && b[3] == BlockHeader[3])
{
// create node here
long parentpage = Helper.ToInt64(b, 7);
List<KeyPointer> list = new List<KeyPointer>();
List<long> dups = new List<long>();
short count = Helper.ToInt16(b, 5);
if (count > _PageNodeCount)
throw new Exception("Count > node size");
long rightpage = Helper.ToInt64(b, 15);
int index = BlockHeader.Length;
if ((b[4] & 4) == 4)
{
int dupc = Helper.ToInt32(b, index);
index += 4;
for (int i = 0; i < dupc; i++)
{
long l = Helper.ToInt64(b, index);
dups.Add(l);
index += 8;
}
}
else
{
for (int i = 0; i < count; i++)
{
int idx = index + _rowSize * i;
byte ks = b[idx];
byte[] key = new byte[ks];
Buffer.BlockCopy(b, idx + 1, key, 0, ks);
long offset = Helper.ToInt64(b, idx + 1 + _maxKeySize);
long duppage = Helper.ToInt64(b, idx + 1 + _maxKeySize + 8);
KeyPointer kp = new KeyPointer(new bytearr(key), offset, duppage);
list.Add(kp);
}
}
Node n = new Node(b[4], parentpage, list, dups, number, rightpage);
return n;
}
else
throw new Exception("Page read error");
}
#endregion
#region [ B U C K E T S ]
public List<long> GetBucketList()
{
file.Seek(FileHeader.Length, SeekOrigin.Begin);
byte[] b = new byte[_BucketCount * 8];
file.Read(b, 0, b.Length);
List<long> list = new List<long>();
for (int i = 0; i < _BucketCount; i++)
{
long l = Helper.ToInt64(b, i * 8);
list.Add(l);
}
return list;
}
public void SaveBucketList(List<long> list)
{
byte[] b = new byte[list.Count * 8];
int idx = 0;
foreach (long l in list)
{
byte[] bb = Helper.GetBytes(l);
Buffer.BlockCopy(bb, 0, b, idx, bb.Length);
idx += bb.Length;
}
file.Seek(FileHeader.Length, SeekOrigin.Begin);
file.Write(b, 0, b.Length);
file.Flush();
}
public void SaveBucket(Bucket bucket)
{
long pnum = bucket.DiskPageNumber;
if (pnum > _LastPageNumber)
throw new Exception("should not be here: page out of bounds");
SeekPage(pnum);
byte[] page = new byte[_PageLength];
Buffer.BlockCopy(BlockHeader, 0, page, 0, BlockHeader.Length);
// bucket type
if (bucket.isBucket)
page[4] = 8;
if (bucket.isOverflow)
page[4] += 16;
// bucket count
byte[] b = Helper.GetBytes(bucket.Count);
Buffer.BlockCopy(b, 0, page, 5, b.Length);
// bucket number
b = Helper.GetBytes(bucket.BucketNumber);
Buffer.BlockCopy(b, 0, page, 7, b.Length);
// next page number
b = Helper.GetBytes(bucket.NextPageNumber);
Buffer.BlockCopy(b, 0, page, 15, b.Length);
int index = BlockHeader.Length;
if (bucket.isOverflow == true)
{
b = Helper.GetBytes(bucket.Duplicates.Count);
Buffer.BlockCopy(b, 0, page, index, b.Length);
index += b.Length;
foreach (long p in bucket.Duplicates)
{
b = Helper.GetBytes(p);
Buffer.BlockCopy(b, 0, page, index, b.Length);
index += b.Length;
}
}
else
{
// bucket children
for (int i = 0; i < bucket.Count; i++)
{
KeyPointer kp = bucket.Pointers[i];
int idx = index + _rowSize * i;
// key size = 1 byte
page[idx] = (byte)kp.Key.val.Length;
// key bytes
Buffer.BlockCopy(bucket.Pointers[i].Key.val, 0, page, idx + 1, page[idx]);
// offset = 8 bytes
b = Helper.GetBytes(kp.Offset);
Buffer.BlockCopy(b, 0, page, idx + 1 + _maxKeySize, b.Length);
// duplicatepage = 8 bytes
b = Helper.GetBytes(kp.DuplicatesPage);
Buffer.BlockCopy(b, 0, page, idx + 1 + _maxKeySize + 8, b.Length);
}
}
bucket.isOverflow = false;
file.Write(page, 0, page.Length);
file.Flush();
}
public Bucket LoadBucketFromPage(long page)
{
SeekPage(page);
byte[] b = new byte[_PageLength];
file.Read(b, 0, _PageLength);
if (b[0] == BlockHeader[0] && b[1] == BlockHeader[1] && b[2] == BlockHeader[2] && b[3] == BlockHeader[3])
{
// create node here
int bucketnum = Helper.ToInt32(b, 7);
List<KeyPointer> list = new List<KeyPointer>();
List<long> dups = new List<long>();
short count = Helper.ToInt16(b, 5);
if (count > _PageNodeCount)
throw new Exception("Count > node size");
long nextpage = Helper.ToInt64(b, 15);
int index = BlockHeader.Length;
if ((b[4] & 4) == 4)
{
int dupc = Helper.ToInt32(b, index);
index += 4;
for (int i = 0; i < dupc; i++)
{
long l = Helper.ToInt64(b, index);
dups.Add(l);
index += 8;
}
}
else
{
for (int i = 0; i < count; i++)
{
int idx = index + _rowSize * i;
byte ks = b[idx];
byte[] key = new byte[ks];
Buffer.BlockCopy(b, idx + 1, key, 0, ks);
long offset = Helper.ToInt64(b, idx + 1 + _maxKeySize);
long duppage = Helper.ToInt64(b, idx + 1 + _maxKeySize + 8);
KeyPointer kp = new KeyPointer(new bytearr(key), offset, duppage);
list.Add(kp);
}
}
Bucket n = new Bucket(b[4], bucketnum, list, dups, page, nextpage);
return n;
}
else
throw new Exception("Page read error");
}
public bool Commit(IDictionary<long, Bucket> buckets)
{
foreach (Bucket n in buckets.Values)
{
if (n.isDirty)
SaveBucket(n);
}
return true;
}
#endregion
}
}