absbtree.pas

Absolute Database 是来替代BDE[Borland数据库引擎]的用于Delphi 和 C++ Builder 开发用的数据库引擎. 它小巧, 高速, 健壮, 易于使用. 它能直接编译进

unit ABSBTree;

{$I ABSVer.inc}

interface

uses SysUtils, Classes, Math,

// AbsoluteDatabase units

     {$IFDEF DEBUG_LOG}
     ABSDebug,
     {$ENDIF}
     ABSPage,
     ABSBaseEngine,
     ABSExcept,
     ABSBase,
     ABSConverts,
     ABSMemory,
     ABSTypes,
     ABSVariant,
     ABSConst;

  //===============================================
  // B-tree page structure
  //===============================================
  // +--------------------------------------------+
  // | PageHeader                                 |
  // +--------------------------------------------+
  // | BTree PageHeader                           |
  // +--------------------------------------------+
  // | Page Prefix (optional)                     |
  // +--------------------------------------------+
  // | Entries                                    |
  // +--------------------------------------------+
  // | Empty space                                |
  // +--------------------------------------------+

  //===============================================
  // Entry structure
  //===============================================
  // +--------------------------------------------+
  // | KeyPrefix | Suffix (opt) | Reference (opt) |
  // +--------------------------------------------+

  //===============================================
  // Key Prefix structure
  //===============================================
  // +--------------------------------------------------------+
  // | Field1IsNull (byte) | Field1 data | Field2IsNull | ... |
  // +--------------------------------------------------------+


type

  TABSBTreeLeafController = class;
  TABSBTreeNodeController = class;
  TABSBTreeRecordIndex = class;

  // BTree PageHeader
  TABSBTreePageHeader = packed record
     IsRoot:           Boolean;
     IsLeaf:           Boolean;
     LeftPageNo:       TABSPageNo;
     RightPageNo:      TABSPageNo;
     HasKeys:          Boolean;
     HasSuffixes:      Boolean;
     KeyPrefixSize:    Word;
     EntryCount:         Word;
     PagePrefixSize:   Word;
  end;
  PABSBTreePageHeader = ^TABSBTreePageHeader;


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeKeyPath
//
////////////////////////////////////////////////////////////////////////////////

  // key path position
  TABSKeyPathPosition = (
    kppUnknown,
    kppOnKey,
    kppBeforeKey,
    kppAfterKey,
    kppBOF,
    kppEOF);
  PABSKeyPathPosition = ^TABSKeyPathPosition;

  TABSKeyPathItem = record
    PageNo:       TABSPageNo;
    EntryNo:      Integer;
    EntryCount:   Integer;
  end;

  TABSKeyPath = class (TObject)
   public
    Items: array [0..31] of TABSKeyPathItem;
    Count: Integer;
    ItemNo: Integer;
    PositionType: TABSKeyPathPosition;
    IndexState: Integer;

    constructor Create;
    procedure Clear;
    procedure Assign(KeyPath: TABSKeyPath);
    procedure AddItem(aPageNo: TABSPageNo; aEntryNo, aEntryCount: Integer);
    procedure DeleteLastItem;
    procedure IncLevel;
    procedure DecLevel;
    function GetCurrentPageNo: TABSPageNo;
    procedure SetCurrentPageNo(Value: TABSPageNo);
    function PageExists(aPageNo: TABSPageNo): Boolean;
    // return 0, 1, -1 if (Self = aKeyPath), (Self > aKeyPath), (Self < aKeyPath)
    function Compare(aKeyPath: TABSKeyPath): Integer;
    function GetApproxRecNoInPercents: double;
    function GetBitmapRecNoByIndexPosition(MaxEntriesPerPage: Integer): TABSRecordNo;
    procedure FillItemsByBitmapRecNo(RecordNo, MaxEntriesPerPage: Integer);

    property  CurrentPageNo: TABSPageNo read GetCurrentPageNo write SetCurrentPageNo;
  end;


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeKeyRef
//
////////////////////////////////////////////////////////////////////////////////

  TABSKeyPart = record
   OffsetInShortKeyBuffer: Integer;
   OffsetInFullKeyBuffer:  Integer;
   OffsetInRecordBuffer:   Integer; // optional
   FieldNo:                Integer;  // optional
   ShortSize:              Integer;
   FullSize:               Integer;
   AddedSize:          Integer;
   DataType:               TABSBaseFieldType;
   Descending:             Boolean;
   CaseInsensitive:        Boolean;
  end;

   TABSBTreeKeyRef = class (TObject)
   private
     FShortKeySize:       Integer;
     FFullKeySize:        Integer;
     FReferenceSize:      Word;
     FKeyIsReference:     Boolean;
     FCompareFieldCount:  Integer;

     function GetPartCount: Integer;
   protected
     procedure SetPartCount(Value: Integer); virtual;

   public
     Parts: array of TABSKeyPart;

     function AllocShortKeyBuffer: PChar;
     function AllocFullKeyBuffer: PChar;
     procedure FreeAndNilKeyBuffer(var Buffer: PChar);
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: PChar;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: PChar=nil; Reference2: PChar=nil): Integer; virtual; abstract;
     function CompareFullKeys(KeyBuffer1, KeyBuffer2: PChar): Integer; virtual; abstract;
     function CompareReferences(Reference1, Reference2: PChar; Size: Integer): Integer;

     property PartCount: Integer read GetPartCount write SetPartCount;
     property ShortKeySize: Integer read FShortKeySize;
     property FullKeySize: Integer read FFullKeySize;
     property ReferenceSize: Word read FReferenceSize write FReferenceSize;
     property KeyIsReference: Boolean read FKeyIsReference write FKeyIsReference;
     property CompareFieldCount: Integer read FCompareFieldCount write FCompareFieldCount;
  end;


////////////////////////////////////////////////////////////////////////////////
//
// TABSRecordKeyRef
//
////////////////////////////////////////////////////////////////////////////////

  TABSRecordKeyRef = class (TABSBTreeKeyRef)
   private
     LRecordBuffer: PChar;
     LTableData:    Pointer;
     FCompareLengths: array of integer;

     procedure RetrieveFullKeyByRecordID(RecordID: TABSRecordID; FullKey: PChar;
                                         SessionID: TABSSessionID);
   protected
     procedure SetPartCount(Value: Integer); override;

   public
     constructor Create;
     procedure Assign(IndexDef: TABSIndexDef; aTableData: Pointer);
     procedure MakeShortKeyFromRecordBuffer(RecordBuffer: PChar; KeyBuffer: PChar);
     procedure MakeFullKeyFromRecordBuffer(RecordBuffer: PChar; KeyBuffer: PChar);
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: PChar;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: PChar=nil; Reference2: PChar=nil): Integer; override;
     function CompareFullKeys(KeyBuffer1, KeyBuffer2: PChar): Integer; override;
     procedure SetPartialCompare(RecordBuffer: PChar; PartialCompare: Boolean);
  end;



////////////////////////////////////////////////////////////////////////////////
//
// TABSPageKeyRef
//
////////////////////////////////////////////////////////////////////////////////

  TABSPageKeyRef = class (TABSBTreeKeyRef)
   public
     constructor Create;
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: PChar;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: PChar=nil; Reference2: PChar=nil): Integer; override;
     function CompareFullKeys(KeyBuffer1, KeyBuffer2: PChar): Integer; override;
  end;



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePage
//
////////////////////////////////////////////////////////////////////////////////

  TABSBTreePage = class(TABSPageController)
   private
     LKeyRef:               TABSBTreeKeyRef;
     LPageManager:          TABSPageManager;
     FLeafController:       TABSBTreeLeafController;
     FNodeController:       TABSBTreeNodeController;

     function GetIsRoot: Boolean;
     procedure SetIsRoot(Value: Boolean);
     function GetIsLeaf: Boolean;
     procedure SetIsLeaf(Value: Boolean);
     function GetLeftPageNo: TABSPageNo;
     procedure SetLeftPageNo(Value: TABSPageNo);
     function GetRightPageNo: TABSPageNo;
     procedure SetRightPageNo(Value: TABSPageNo);
     function GetHasKeys: Boolean;
     procedure SetHasKeys(Value: Boolean);
     function GetHasSuffixes: Boolean;
     procedure SetHasSuffixes(Value: Boolean);
     function GetKeyPrefixSize: Word;
     procedure SetKeyPrefixSize(Value: Word);
     function GetEntryCount: Integer;
     procedure SetEntryCount(Value: Integer);
     function GetPagePrefixSize: Word;
     procedure SetPagePrefixSize(Value: Word);
     //-------------------------------------
     function GetEntrySize: Integer;
     function GetReferenceSize: Integer;
     function GetEntriesOffset: Integer;
     function GetSuffixPtrSize: Integer;

   public
     constructor Create(PageManager: TABSPageManager; KeyRef: TABSBTreeKeyRef);
     destructor Destroy; override;
     procedure AddIndexPage(SessionID: TABSSessionID; var Page: TABSBTreePage);
     procedure RemoveIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo);
     procedure GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo; var Page: TABSBTreePage);
     procedure PutIndexPage(Page: TABSBTreePage);
     procedure Init;
     procedure InitAsRoot;
     procedure CopyFrom(Source: TABSBTreePage; StartNo, Count: Integer);
     procedure AppendFrom(Source: TABSBTreePage; StartNo, Count: Integer);
     procedure InsertFrom(Source: TABSBTreePage; StartNo, Count: Integer);
     procedure InsertLeafEntry(SessionID: TABSSessionID; Key, Reference: PChar; KeyPath: TABSKeyPath);
     procedure InsertNodeEntry(SessionID: TABSSessionID; Key, Reference: PChar; KeyPath: TABSKeyPath);
     function DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: PChar; KeyPath: TABSKeyPath): Boolean;
     procedure DeleteNodeEntry(
                        SessionID:     TABSSessionID;
                        KeyPath:       TABSKeyPath;
                        MergeWithLeft: Boolean
                              );
     function FindEntry(
                        SessionID: TABSSessionID;
                        Key:       PChar;
                        Reference: PChar;
                        Position:  TABSKeyPath
                       ): Boolean;
     function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
     function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
     function FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       PChar;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean;

     procedure FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean);
     procedure CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
     function GetPKey(KeyPosition: Integer): PChar;
     function GetPReference(RefPosition: Integer): PChar;
     procedure GetFirstKey(SessionID: TABSSessionID; Key: PChar);
     procedure GetLastKey(SessionID: TABSSessionID; Key: PChar);
     procedure GetFirstEntry(SessionID: TABSSessionID; Key, Reference: PChar);
     procedure GetLastEntry(SessionID: TABSSessionID; Key, Reference: PChar);
     procedure UpdateKey(Position: Integer; Key: PChar);
     procedure UpdateReference(Position: Integer; Reference: PChar);

     //--- BTree page header ---
     property IsRoot: Boolean read GetIsRoot write SetIsRoot;
     property IsLeaf: Boolean read GetIsLeaf write SetIsLeaf;
     property LeftPageNo: TABSPageNo read GetLeftPageNo write SetLeftPageNo;
     property RightPageNo: TABSPageNo read GetRightPageNo write SetRightPageNo;
     property HasKeys: Boolean read GetHasKeys write SetHasKeys;
     property HasSuffixes: Boolean read GetHasSuffixes write SetHasSuffixes;
     property KeyPrefixSize: Word read GetKeyPrefixSize write SetKeyPrefixSize;
     property EntryCount: Integer read GetEntryCount write SetEntryCount;