📄 altbtree.cs
字号:
namespace Perst.Impl
{
using System;
using System.Collections;
using System.Diagnostics;
using Perst;
#if USE_GENERICS
using System.Collections.Generic;
using Link=Link<IPersistent>;
#endif
#if USE_GENERICS
class AltBtree<K,V>:PersistentCollection<V>, Index<K,V> where V:class,IPersistent
#else
class AltBtree:PersistentCollection, Index
#endif
{
const char MaxChar=(char)0xf800; // String.Comparemethid ignores Char.MaxChar character
public Type KeyType
{
get
{
#if USE_GENERICS
return typeof(K);
#else
return mapKeyType(type);
#endif
}
}
protected static Type mapKeyType(ClassDescriptor.FieldType type)
{
switch (type)
{
case ClassDescriptor.FieldType.tpBoolean:
return typeof(bool);
case ClassDescriptor.FieldType.tpByte:
return typeof(byte);
case ClassDescriptor.FieldType.tpSByte:
return typeof(sbyte);
case ClassDescriptor.FieldType.tpChar:
return typeof(char);
case ClassDescriptor.FieldType.tpShort:
return typeof(short);
case ClassDescriptor.FieldType.tpUShort:
return typeof(ushort);
case ClassDescriptor.FieldType.tpInt:
case ClassDescriptor.FieldType.tpOid:
return typeof(int);
case ClassDescriptor.FieldType.tpUInt:
return typeof(uint);
case ClassDescriptor.FieldType.tpLong:
return typeof(long);
case ClassDescriptor.FieldType.tpULong:
return typeof(ulong);
case ClassDescriptor.FieldType.tpFloat:
return typeof(float);
case ClassDescriptor.FieldType.tpDouble:
return typeof(double);
case ClassDescriptor.FieldType.tpString:
return typeof(string);
case ClassDescriptor.FieldType.tpDate:
return typeof(DateTime);
case ClassDescriptor.FieldType.tpObject:
return typeof(IPersistent);
case ClassDescriptor.FieldType.tpRaw:
return typeof(IComparable);
case ClassDescriptor.FieldType.tpGuid:
return typeof(Guid);
case ClassDescriptor.FieldType.tpDecimal:
return typeof(decimal);
case ClassDescriptor.FieldType.tpEnum:
return typeof(Enum);
default:
return null;
}
}
internal int height;
internal ClassDescriptor.FieldType type;
internal int nElems;
internal bool unique;
internal BtreePage root;
[NonSerialized()]
internal int updateCounter;
internal AltBtree()
{
}
#if USE_GENERICS
public override void OnLoad()
{
if (type != ClassDescriptor.getTypeCode(typeof(K))) {
throw new StorageError(StorageError.ErrorCode.INCOMPATIBLE_KEY_TYPE, typeof(K));
}
}
#endif
internal class BtreeKey
{
internal Key key;
internal IPersistent node;
internal IPersistent oldNode;
internal BtreeKey(Key key, IPersistent node)
{
this.key = key;
this.node = node;
}
}
internal abstract class BtreePage:Persistent
{
internal abstract Array Data{get;}
internal int nItems;
internal Link items;
internal const int BTREE_PAGE_SIZE = Page.pageSize - ObjectHeader.Sizeof - 4 * 3;
internal abstract object getKeyValue(int i);
internal abstract Key getKey(int i);
internal abstract int compare(Key key, int i);
internal abstract void insert(BtreeKey key, int i);
internal abstract BtreePage clonePage();
internal virtual void clearKeyValue(int i)
{
}
internal virtual bool find(Key firstKey, Key lastKey, int height, ArrayList result)
{
int l = 0, n = nItems, r = n;
height -= 1;
if (firstKey != null)
{
while (l < r)
{
int i = (l + r) >> 1;
if (compare(firstKey, i) >= firstKey.inclusion)
{
l = i + 1;
}
else
{
r = i;
}
}
Debug.Assert(r == l);
}
if (lastKey != null)
{
if (height == 0)
{
while (l < n)
{
if (-compare(lastKey, l) >= lastKey.inclusion)
{
return false;
}
result.Add(items[l]);
l += 1;
}
return true;
}
else
{
do
{
if (!((BtreePage) items[l]).find(firstKey, lastKey, height, result))
{
return false;
}
if (l == n)
{
return true;
}
}
while (compare(lastKey, l++) >= 0);
return false;
}
}
if (height == 0)
{
while (l < n)
{
result.Add(items[l]);
l += 1;
}
}
else
{
do
{
if (!((BtreePage) items[l]).find(firstKey, lastKey, height, result))
{
return false;
}
}
while (++l <= n);
}
return true;
}
internal static void memcpyData(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len)
{
Array.Copy(src_pg.Data, src_idx, dst_pg.Data, dst_idx, len);
}
internal static void memcpyItems(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len)
{
Array.Copy(src_pg.items.ToRawArray(), src_idx, dst_pg.items.ToRawArray(), dst_idx, len);
}
internal static void memcpy(BtreePage dst_pg, int dst_idx, BtreePage src_pg, int src_idx, int len)
{
memcpyData(dst_pg, dst_idx, src_pg, src_idx, len);
memcpyItems(dst_pg, dst_idx, src_pg, src_idx, len);
}
internal virtual void memset(int i, int len)
{
while (--len >= 0)
{
items[i++] = null;
}
}
internal virtual OperationResult insert(BtreeKey ins, int height, bool unique, bool overwrite)
{
OperationResult result;
int ahead = unique ? 1 : 0;
int l = 0, n = nItems, r = n;
while (l < r)
{
int i = (l + r) >> 1;
if (compare(ins.key, i) >= ahead)
{
l = i + 1;
}
else
{
r = i;
}
}
Debug.Assert(l == r);
/* insert before e[r] */
if (--height != 0)
{
result = ((BtreePage) items[r]).insert(ins, height, unique, overwrite);
Debug.Assert(result != OperationResult.NotFound);
if (result != OperationResult.Overflow)
{
return result;
}
n += 1;
}
else if (r < n && compare(ins.key, r) == 0)
{
if (overwrite)
{
ins.oldNode = items[r];
Modify();
items[r] = ins.node;
return OperationResult.Overwrite;
}
else if (unique)
{
ins.oldNode = items[r];
return OperationResult.Duplicate;
}
}
int max = items.Length;
Modify();
if (n < max)
{
memcpy(this, r + 1, this, r, n - r);
insert(ins, r);
nItems += 1;
return OperationResult.Done;
}
else
{
/* page is full then divide page */
BtreePage b = clonePage();
Debug.Assert(n == max);
int m = max / 2;
if (r < m)
{
memcpy(b, 0, this, 0, r);
memcpy(b, r + 1, this, r, m - r - 1);
memcpy(this, 0, this, m - 1, max - m + 1);
b.insert(ins, r);
}
else
{
memcpy(b, 0, this, 0, m);
memcpy(this, 0, this, m, r - m);
memcpy(this, r - m + 1, this, r, max - r);
insert(ins, r - m);
}
memset(max - m + 1, m - 1);
ins.node = b;
ins.key = b.getKey(m - 1);
if (height == 0)
{
nItems = max - m + 1;
b.nItems = m;
}
else
{
b.clearKeyValue(m - 1);
nItems = max - m;
b.nItems = m - 1;
}
return OperationResult.Overflow;
}
}
internal virtual OperationResult handlePageUnderflow(int r, BtreeKey rem, int height)
{
BtreePage a = (BtreePage) items[r];
a.Modify();
Modify();
int an = a.nItems;
if (r < nItems)
{
// exists greater page
BtreePage b = (BtreePage) items[r + 1];
int bn = b.nItems;
Debug.Assert(bn >= an);
if (height != 1)
{
memcpyData(a, an, this, r, 1);
an += 1;
bn += 1;
}
if (an + bn > items.Length)
{
// reallocation of nodes between pages a and b
int i = bn - ((an + bn) >> 1);
b.Modify();
memcpy(a, an, b, 0, i);
memcpy(b, 0, b, i, bn - i);
memcpyData(this, r, a, an + i - 1, 1);
if (height != 1)
{
a.clearKeyValue(an + i - 1);
}
b.memset(bn - i, i);
b.nItems -= i;
a.nItems += i;
return OperationResult.Done;
}
else
{
// merge page b to a
memcpy(a, an, b, 0, bn);
b.Deallocate();
memcpyData(this, r, this, r + 1, nItems - r - 1);
memcpyItems(this, r + 1, this, r + 2, nItems - r - 1);
items[nItems] = null;
a.nItems += bn;
nItems -= 1;
return nItems < (items.Size() >> 1) ? OperationResult.Underflow : OperationResult.Done;
}
}
else
{
// page b is before a
BtreePage b = (BtreePage) items[r - 1];
int bn = b.nItems;
Debug.Assert(bn >= an);
if (height != 1)
{
an += 1;
bn += 1;
}
if (an + bn > items.Size())
{
// reallocation of nodes between pages a and b
int i = bn - ((an + bn) >> 1);
b.Modify();
memcpy(a, i, a, 0, an);
memcpy(a, 0, b, bn - i, i);
if (height != 1)
{
memcpyData(a, i - 1, this, r - 1, 1);
}
memcpyData(this, r - 1, b, bn - i - 1, 1);
if (height != 1)
{
b.clearKeyValue(bn - i - 1);
}
b.memset(bn - i, i);
b.nItems -= i;
a.nItems += i;
return OperationResult.Done;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -