unit MYLDBBTree;

{$I MYLDBVer.inc}

interface

uses SysUtils, Classes, Math,

// MYLDBoluteDatabase units

     {$IFDEF DEBUG_LOG}
     MYLDBDebug,
     {$ENDIF}
     MYLDBPage,
     MYLDBBaseEngine,
     MYLDBExcept,
     MYLDBBase,
     MYLDBConverts,
     MYLDBMemory,
     MYLDBTypes,
     MYLDBVariant,
     MYLDBConst;

  //===============================================
  // 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

  TMYLDBBTreeLeafController = class;
  TMYLDBBTreeNodeController = class;
  TMYLDBBTreeRecordIndex = class;

  // BTree PageHeader
  TMYLDBBTreePageHeader = packed record
     IsRoot:           Boolean;
     IsLeaf:           Boolean;
     LeftPageNo:       TMYLDBPageNo;
     RightPageNo:      TMYLDBPageNo;
     HasKeys:          Boolean;
     HasSuffixes:      Boolean;
     KeyPrefixSize:    Word;
     EntryCount:         Word;
     PagePrefixSize:   Word;
  end;
  PMYLDBBTreePageHeader = ^TMYLDBBTreePageHeader;


////////////////////////////////////////////////////////////////////////////////
//
// TMYLDBBTreeKeyPath
//
////////////////////////////////////////////////////////////////////////////////

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

  TMYLDBKeyPathItem = record
    PageNo:       TMYLDBPageNo;
    EntryNo:      Integer;
    EntryCount:   Integer;
  end;

  TMYLDBKeyPath = class (TObject)
   public
    Items: array [0..31] of TMYLDBKeyPathItem;
    Count: Integer;
    ItemNo: Integer;
    PositionType: TMYLDBKeyPathPosition;
    IndexState: Integer;

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

    property  CurrentPageNo: TMYLDBPageNo read GetCurrentPageNo write SetCurrentPageNo;
  end;


////////////////////////////////////////////////////////////////////////////////
//
// TMYLDBBTreeKeyRef
//
////////////////////////////////////////////////////////////////////////////////

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

   TMYLDBBTreeKeyRef = 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 TMYLDBKeyPart;

     function AllocShortKeyBuffer: PChar;
     function AllocFullKeyBuffer: PChar;
     procedure FreeAndNilKeyBuffer(var Buffer: PChar);
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: PChar;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TMYLDBSessionID = 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;


////////////////////////////////////////////////////////////////////////////////
//
// TMYLDBRecordKeyRef
//
////////////////////////////////////////////////////////////////////////////////

  TMYLDBRecordKeyRef = class (TMYLDBBTreeKeyRef)
   private
     LRecordBuffer: PChar;
     LTableData:    Pointer;
     FCompareLengths: array of integer;

     procedure RetrieveFullKeyByRecordID(RecordID: TMYLDBRecordID; FullKey: PChar;
                                         SessionID: TMYLDBSessionID);
   protected
     procedure SetPartCount(Value: Integer); override;

   public
     constructor Create;
     procedure Assign(IndexDef: TMYLDBIndexDef; aTableData: Pointer);
     procedure MakeShortKeyFromRecordBuffer(RecordBuffer: PChar; KeyBuffer: PChar);
     procedure MakeFullKeyFromRecordBuffer(RecordBuffer: PChar; KeyBuffer: PChar);
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: PChar;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TMYLDBSessionID = 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;



////////////////////////////////////////////////////////////////////////////////
//
// TMYLDBPageKeyRef
//
////////////////////////////////////////////////////////////////////////////////

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



////////////////////////////////////////////////////////////////////////////////
//
// TMYLDBBTreePage
//
////////////////////////////////////////////////////////////////////////////////

  TMYLDBBTreePage = class(TMYLDBPageController)
   private
     LKeyRef:               TMYLDBBTreeKeyRef;
     LPageManager:          TMYLDBPageManager;
     FLeafController:       TMYLDBBTreeLeafController;
     FNodeController:       TMYLDBBTreeNodeController;

     function GetIsRoot: Boolean;
     procedure SetIsRoot(Value: Boolean);
     function GetIsLeaf: Boolean;
     procedure SetIsLeaf(Value: Boolean);
     function GetLeftPageNo: TMYLDBPageNo;
     procedure SetLeftPageNo(Value: TMYLDBPageNo);
     function GetRightPageNo: TMYLDBPageNo;
     procedure SetRightPageNo(Value: TMYLDBPageNo);
     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: TMYLDBPageManager; KeyRef: TMYLDBBTreeKeyRef);
     destructor Destroy; override;
     procedure AddIndexPage(SessionID: TMYLDBSessionID; var Page: TMYLDBBTreePage);
     procedure RemoveIndexPage(SessionID: TMYLDBSessionID; PageNo: TMYLDBPageNo);
     procedure GetIndexPage(SessionID: TMYLDBSessionID; PageNo: TMYLDBPageNo; var Page: TMYLDBBTreePage);
     procedure PutIndexPage(Page: TMYLDBBTreePage);
     procedure Init;
     procedure InitAsRoot;
     procedure CopyFrom(Source: TMYLDBBTreePage; StartNo, Count: Integer);
     procedure AppendFrom(Source: TMYLDBBTreePage; StartNo, Count: Integer);
     procedure InsertFrom(Source: TMYLDBBTreePage; StartNo, Count: Integer);
     procedure InsertLeafEntry(SessionID: TMYLDBSessionID; Key, Reference: PChar; KeyPath: TMYLDBKeyPath);
     procedure InsertNodeEntry(SessionID: TMYLDBSessionID; Key, Reference: PChar; KeyPath: TMYLDBKeyPath);
     function DeleteLeafEntry(SessionID: TMYLDBSessionID; Key, Reference: PChar; KeyPath: TMYLDBKeyPath): Boolean;
     procedure DeleteNodeEntry(
                        SessionID:     TMYLDBSessionID;
                        KeyPath:       TMYLDBKeyPath;
                        MergeWithLeft: Boolean
                              );
     function FindEntry(
                        SessionID: TMYLDBSessionID;
                        Key:       PChar;
                        Reference: PChar;
                        Position:  TMYLDBKeyPath
                       ): Boolean;
     function GetFirstPosition(SessionID: TMYLDBSessionID; Position: TMYLDBKeyPath): Boolean;
     function GetLastPosition(SessionID: TMYLDBSessionID; Position: TMYLDBKeyPath): Boolean;
     function FindByCondition(
                              SessionID: TMYLDBSessionID;
                              First:     Boolean; // if False => Last
                              Key:       PChar;
                              Operator:  TMYLDBSearchCondition;
                              Position:  TMYLDBKeyPath
                             ): Boolean;

     procedure FreeAllPages(SessionID: TMYLDBSessionID; KeepRootPage: Boolean);
     procedure CheckIntegrity(SessionID: TMYLDBSessionID; KeyPath: TMYLDBKeyPath);
     function GetPKey(KeyPosition: Integer): PChar;
     function GetPReference(RefPosition: Integer): PChar;
     procedure GetFirstKey(SessionID: TMYLDBSessionID; Key: PChar);
     procedure GetLastKey(SessionID: TMYLDBSessionID; Key: PChar);
     procedure GetFirstEntry(SessionID: TMYLDBSessionID; Key, Reference: PChar);
     procedure GetLastEntry(SessionID: TMYLDBSessionID; 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: TMYLDBPageNo read GetLeftPageNo write SetLeftPageNo;