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: TAbsPByte;
     function AllocFullKeyBuffer: TAbsPByte;
     procedure FreeAndNilKeyBuffer(var Buffer: TAbsPByte);
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: TAbsPByte;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: TAbsPByte=nil; Reference2: TAbsPByte=nil): Integer; virtual; abstract;
     function CompareFullKeys(KeyBuffer1, KeyBuffer2: TAbsPByte): Integer; virtual; abstract;
     function CompareReferences(Reference1, Reference2: TAbsPByte; 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: TAbsPByte;
     LTableData:    Pointer;
     FCompareLengths: array of integer;

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

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



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

  TABSPageKeyRef = class (TABSBTreeKeyRef)
   public
     constructor Create;
     function CompareShortKeys(KeyBuffer1, KeyBuffer2: TAbsPByte;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: TAbsPByte=nil; Reference2: TAbsPByte=nil): Integer; override;
     function CompareFullKeys(KeyBuffer1, KeyBuffer2: TAbsPByte): 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: TAbsPByte; KeyPath: TABSKeyPath);
     procedure InsertNodeEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath);
     function DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath): Boolean;
     procedure DeleteNodeEntry(
                        SessionID:     TABSSessionID;
                        KeyPath:       TABSKeyPath;
                        MergeWithLeft: Boolean
                              );
     function FindEntry(
                        SessionID: TABSSessionID;
                        Key:       TAbsPByte;
                        Reference: TAbsPByte;
                        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:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean;

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

     //--- 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;
     property PagePrefixSize: Word read GetPagePrefixSize write SetPagePrefixSize;
     // calculated
     property EntrySize:     Integer read GetEntrySize;
     property ReferenceSize: Integer read GetReferenceSize;
     property EntriesOffset: Integer read GetEntriesOffset;
     property SuffixPtrSize: Integer read GetSuffixPtrSize;

     property KeyRef: TABSBTreeKeyRef read LKeyRef write LKeyRef;
  end;



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePageController
//
////////////////////////////////////////////////////////////////////////////////


  TABSBTreePageController = class(TObject)
   protected
     FPage:                  TABSBTreePage;

     function GetKeyRef: TABSBTreeKeyRef;
     function CanAddEntry: Boolean;
     function IsOverflow: Boolean;
     function CanUnderflow: Boolean;
     function CanMergeWithPage(Page: TABSBTreePage): Boolean;
     procedure EnlargePageBuffer;
     function CompareKeys(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Key2Index: Word): Integer;
     function CompareReferences(Reference1: TAbsPByte; Reference2Index: Word): Integer;
     function CompareEntries(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Reference1: TAbsPByte;
                          Entry2Index: Word): Integer; virtual; abstract;
     function GetKeyPosition(
                       MayUseFullKeys: Boolean;
                       SessionID: TABSSessionID;
                       Key: TAbsPByte;
                       Reference: TAbsPByte; // if finding entry
                       StartPosition: Integer = 0;
                       PositionType: PABSKeyPathPosition = nil;
                       SearchType: TABSKeySearchType = kstAny
                             ): Word;
     procedure InsertEntry(Key, Reference: TAbsPByte; Position: Integer);
     procedure DeleteEntry(Position: Integer);
     procedure RootSplit(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
     procedure NonRootSplit(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
     function TryMergeWithPage(
                        SessionID: TABSSessionID;
                        MergePageNo: TABSPageNo;
                        KeyPath: TABSKeyPath
                               ): Boolean;
     function TryMerge(SessionID: TABSSessionID; KeyPath: TABSKeyPath): Boolean;
     procedure MergeWithLeftPage(
                        SessionID: TABSSessionID;
                        LeftPage: TABSBTreePage;
                        KeyPath: TABSKeyPath
                                );
     procedure MergeWithRightPage(
                        SessionID: TABSSessionID;
                        RightPage: TABSBTreePage;
                        KeyPath: TABSKeyPath
                                );
   public
     constructor Create(aPage: TABSBTreePage);
     procedure InsertLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath); virtual; abstract;
     function DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath): Boolean; virtual; abstract;
     procedure FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean); virtual; abstract;
     procedure CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath); virtual; abstract;
     function FindEntry(
                        SessionID: TABSSessionID;
                        Key:       TAbsPByte;
                        Reference: TAbsPByte;
                        Position:  TABSKeyPath
                       ): Boolean; virtual; abstract;
     function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; virtual; abstract;
     function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; virtual; abstract;
     function FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean; virtual; abstract;
     function GetPKey(KeyPosition: Integer): TAbsPByte;
     function GetPReference(RefPosition: Integer): TAbsPByte;
     procedure GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte); virtual; abstract;
     procedure GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte); virtual; abstract;
     procedure GetFirstEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); virtual; abstract;
     procedure GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); virtual; abstract;
     procedure Split(SessionID: TABSSessionID; KeyPath: TABSKeyPath);

     property KeyRef: TABSBTreeKeyRef read GetKeyRef;
  end;// TABSBTreePageController



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeLeafController
//
////////////////////////////////////////////////////////////////////////////////


  TABSBTreeLeafController = class(TABSBTreePageController)
   private
     function FindEntryOnPage(SessionID: TABSSessionID;
                              Key, Reference: TAbsPByte; var EntryNo: Integer): Boolean;
     function FindFirstByCondition(
                                    SessionID: TABSSessionID;
                                    Key:       TAbsPByte;
                                    Operator:  TABSSearchCondition;
                                    Position:  TABSKeyPath
                                  ): Boolean;
     function FindLastByCondition(
                                    SessionID: TABSSessionID;
                                    Key:       TAbsPByte;
                                    Operator:  TABSSearchCondition;
                                    Position:  TABSKeyPath
                                  ): Boolean;
   protected
     function CompareEntries(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Reference1: TAbsPByte;
                          Entry2Index: Word): Integer; override;

   public
     procedure InsertLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath); override;
     function DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath): Boolean; override;
     procedure GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte); override;
     procedure GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte); override;
     procedure GetFirstEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); override;
     procedure GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); override;
     function FindEntry(
                          SessionID: TABSSessionID;
                          Key:       TAbsPByte;
                          Reference: TAbsPByte;
                          Position:  TABSKeyPath
                       ): Boolean; override;
     function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; override;
     function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; override;
     function FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean; override;
     procedure FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean); override;
     procedure CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath); override;
  end;// TABSBTreeLeafController



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeNodeController
//
////////////////////////////////////////////////////////////////////////////////


  TABSBTreeNodeController = class(TABSBTreePageController)
   private
    function FindByConditionOnOneOfPages(
                                    SessionID:    TABSSessionID;
                                    First:        Boolean; // if False => Last
                                    StartEntryNo: Integer;
                                    EndEntryNo:   Integer;
                                    Key:          TAbsPByte;
                                    Operator:     TABSSearchCondition;
                                    Position:     TABSKeyPath
                                  ): Boolean;
    function FindEntryOnOneOfPages(
                                    SessionID:    TABSSessionID;
                                    StartEntryNo: Integer;
                                    EndEntryNo:   Integer;
                                    Key:          TAbsPByte;
                                    Reference:    TAbsPByte;
                                    Position:     TABSKeyPath
                                  ): Boolean;
    procedure GetChildPagesToCheck(
                          SessionID:         TABSSessionID;
                          Key:               TAbsPByte;
                          SearchCondition:   TABSSearchCondition;
                          var StartEntryNo:  Integer;
                          var EndEntryNo:    Integer
                                    );
     procedure DecreaseTreeDepth(SessionID: TABSSessionID);

   protected
     function CompareEntries(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Reference1: TAbsPByte;
                          Entry2Index: Word): Integer; override;

   public
     procedure InsertLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath); override;
     procedure InsertNodeEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath);
     function DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath): Boolean; override;
     procedure DeleteNodeEntry(
                        SessionID:     TABSSessionID;
                        KeyPath:       TABSKeyPath;
                        MergeWithLeft: Boolean
                              );
     procedure GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte); override;
     procedure GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte); override;
     procedure GetFirstEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); override;
     procedure GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte); override;
     function FindEntry(
                          SessionID: TABSSessionID;
                          Key:       TAbsPByte;
                          Reference: TAbsPByte;
                          Position:  TABSKeyPath
                       ): Boolean; override;
     function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; override;
     function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean; override;
     function FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean; override;
     procedure FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean); override;
     procedure CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath); override;
  end;// TABSBTreeNodeController



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeRecordIndex
//
////////////////////////////////////////////////////////////////////////////////

  TABSBTreeSearchInfo = packed record
     GoForward:       Boolean;
     IsFilled:        Boolean;
     EndKeyPath:      TABSKeyPath;
     CurrentKeyPath:  TABSKeyPath;
  end;
  PABSBTreeSearchInfo = ^TABSBTreeSearchInfo;

  TABSBTreeRecordIndex = class (TABSIndex)
   private
    FRootPage:          TABSBTreePage;
    FKeyRef:            TABSRecordKeyRef;

    function AddIndexPage(SessionID: TABSSessionID): TABSBTreePage;
    function GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo): TABSBTreePage;
    procedure PutIndexPage(Page: TABSBTreePage);

    function GetRecordID(SessionID: TABSSessionID; Position: TABSKeyPath): TABSRecordID;
    function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetNextPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetPriorPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetPosition(SessionID: TABSSessionID; Restart, GoForward: Boolean; Position: TABSKeyPath): Boolean;

   public
    constructor Create(aIndexManager: TABSBaseIndexManager);
    destructor Destroy; override;

    procedure CreateIndex(Cursor: TABSCursor; aIndexDef: TABSIndexDef); override;
    procedure DropIndex(SessionID: TABSSessionID); override;
    procedure EmptyIndex(SessionID: TABSSessionID); override;
    procedure OpenIndex(aIndexDef: TABSIndexDef); override;
    procedure RebuildTemporaryIndex(Cursor: TABSCursor); override;

    procedure GetRecordBuffer(
                               SessionID:          TABSSessionID;
                               var NavigationInfo: TABSNavigationInfo;
                               IndexPositionCache: TABSIndexPositionCache;
                               TableState:         Integer
                             ); override;
    procedure GetClosestRecordBuffer(
                              SessionID:          TABSSessionID;
                              var NavigationInfo: TABSNavigationInfo;
                               IndexPositionCache: TABSIndexPositionCache;
                               TableState:         Integer
                               ); override;
    function CreateIndexPosition: TABSIndexPosition; override;
    procedure FreeIndexPosition(var IndexPosition: TABSIndexPosition); override;
    function GetIndexPosition(
                               SessionID:      TABSSessionID;
                               RecordID:       TABSRecordID;
                               RecordBuffer:   TABSRecordBuffer;
                               IndexPosition:  TABSIndexPosition
                             ): Boolean; override;
    // return 0, 1, -1 if (Pos1 = Pos2), (Pos1 > Pos2), (Pos1 < Pos2)
    function CompareRecordPositionsInIndex(
                        RecordPosition1: TABSIndexPosition;
                        RecordPosition2: TABSIndexPosition
                                          ): Integer; override;
    function GetRecNoByRecordID(
                                SessionID:      TABSSessionID;
                                RecordID:       TABSRecordID;
                                RecordBuffer:   TABSRecordBuffer
                               ): TABSRecordNo; override;
    function GetRecordIDByRecNo(
                                SessionID:      TABSSessionID;
                                RecNo:          TABSRecordNo
                               ): TABSRecordID; override;
    procedure ApplyDistinctToRecordBitmap(
                                SessionID:      TABSSessionID;
                                Bitmap:         TABSRecordBitmap;
                                DistinctFieldCount: Integer
                                         ); override;
    function CreateSearchInfo: TABSSearchInfo; override;
    procedure FreeSearchInfo(SearchInfo: TABSSearchInfo); override;
   private
    function GetCurrentPosition(
                                 SessionID:           TABSSessionID;
                                 Restart:             Boolean;
                                 GoForward:           Boolean;
                                 StartScanCondition:  TABSScanSearchCondition;
                                 RecordBuffer:        TABSRecordBuffer;
                                 RecordID:            TABSRecordID;
                                 SearchInfo:          TABSSearchInfo
                               ): Boolean;
    function GetEndPosition(
                                 SessionID:           TABSSessionID;
                                 GoForward:           Boolean;
                                 StartScanCondition:  TABSScanSearchCondition;
                                 EndScanCondition:    TABSScanSearchCondition;
                                 SearchInfo:          TABSSearchInfo
                               ): Boolean;
   public
    function FindRecord(
                       SessionID:           TABSSessionID;
                       Restart:             Boolean;
                       GoForward:           Boolean;
                       StartScanCondition:  TABSScanSearchCondition;
                       EndScanCondition:    TABSScanSearchCondition;
                       RecordBuffer:        TABSRecordBuffer;
                       var RecordID:        TABSRecordID;
                       SearchInfo:          TABSSearchInfo
                       ): Boolean; override;
    // return 0 if record buffers are equal in this index
    // return 1 if Buffer1 is higher than Buffer 2 (Pos1 > Pos2)
    // return -1 if Buffer1 is lower than Buffer 2 (Pos1 < Pos2)
    function CompareRecordBuffersByIndex(
                        Buffer1: TABSRecordBuffer;
                        Buffer2: TABSRecordBuffer;
                        IndexFieldCount: Integer
                                        ): Integer; override;

    // return 0 if conditions are equal in this index
    // return 1 if Condition1 is higher than Condition2
    // return -1 if Condition1 is lower than Condition2
    function CompareConditions(
                    Condition1:   TABSScanSearchCondition;
                    Condition2:   TABSScanSearchCondition
                              ): Integer; override;
    // approximate record count between range conditions
    function GetApproxRangeRecordCount(
                    SessionID:         TABSSessionID;
                    TableRecordCount:  TABSRecordNo;
                    RangeCondition1:   TABSScanSearchCondition;
                    RangeCondition2:   TABSScanSearchCondition
                                      ): TABSRecordNo; override;

    function CanInsertRecord(
                    SessionID:      TABSSessionID;
                    RecordBuffer:   TABSRecordBuffer
                            ): Boolean; override;
    function CanUpdateRecord(
                    SessionID:                        TABSSessionID;
                    OldRecordBuffer, NewRecordBuffer: TABSRecordBuffer
                            ): Boolean; override;
    procedure InsertRecord(Cursor: TABSCursor); override;
    procedure UpdateRecord(Cursor: TABSCursor; BeforeNewRecordIsStored: Boolean); override;
    procedure DeleteRecord(Cursor: TABSCursor); override;

    function GetMaxEntriesPerPage: Integer; override;
    procedure GetRecordIDByIndexPosition(SessionID: TABSSessionID; IndexPos: TABSIndexPosition; var RecordID: TABSRecordID); override;

    property KeyRef: TABSRecordKeyRef read FKeyRef;
  end; // TABSBTreeRecordIndex


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePageIndex
//
////////////////////////////////////////////////////////////////////////////////

  TABSBTreePageIndex = class (TObject)
   protected
    FRootPageNo:        TABSPageNo;
    FKeyRef:            TABSPageKeyRef;
    LPageManager:       TABSPageManager;
    FMaxRecordsOnPage:  Integer;

    function AddIndexPage(SessionID: TABSSessionID): TABSBTreePage;
    function GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo): TABSBTreePage;
    procedure PutIndexPage(Page: TABSBTreePage);
    function GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetNextPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetPriorPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
    function GetPosition(SessionID: TABSSessionID; PageNo: TABSPageNo; Position: TABSKeyPath): Boolean;
    function GetPageValue(SessionID: TABSSessionID; Position: TABSKeyPath): Word;
    procedure SetPageValue(SessionID: TABSSessionID; Position: TABSKeyPath; Value: Word);
    function GetPageNo(SessionID: TABSSessionID; Position: TABSKeyPath): TABSPageNo;
    function CanAddNewItem(OldValue: Integer; NewItemSize: Integer): Boolean; virtual; abstract;
    function FindPageForNewItem(SessionID: TABSSessionID; ItemSize: Integer; var PageNo: TABSPageNo): Boolean;
    procedure AddPageItem(SessionID: TABSSessionID; ItemSize: Integer; PageNo: TABSPageNo);
    procedure DeletePageItem(SessionID: TABSSessionID; ItemSize: Integer; PageNo: TABSPageNo; NewItemCount: Integer);

   public
    constructor Create(PageManager: TABSPageManager);
    destructor Destroy; override;

    procedure CreateIndex(SessionID: TABSSessionID);
    procedure DropIndex(SessionID: TABSSessionID);
    procedure EmptyIndex(SessionID: TABSSessionID);
    procedure OpenIndex(RootPageNo: TABSPageNo);

    property KeyRef: TABSPageKeyRef read FKeyRef;
    property RootPageNo: TABSPageNo read FRootPageNo;
  end; // TABSBTreePageIndex


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeRecordPageIndex
//
////////////////////////////////////////////////////////////////////////////////

  TABSBTreeRecordPageIndex = class (TABSBTreePageIndex)
   private
    FMaxRecordsOnPage:  Integer;

    function GetPageRecordCount(SessionID: TABSSessionID; Position: TABSKeyPath): Word;

   protected
    function CanAddNewItem(OldValue: Integer; NewItemSize: Integer): Boolean; override;

   public
    function FindPageForNewRecord(SessionID: TABSSessionID; var PageNo: TABSPageNo): Boolean;
    procedure AddRecord(SessionID: TABSSessionID; PageNo: TABSPageNo; AddCount: Integer = 1);
    procedure DeleteRecord(SessionID: TABSSessionID; PageNo: TABSPageNo; NewItemCount: Integer);

    function GetFirstRecordPage(SessionID: TABSSessionID; var PageNo: TABSPageNo): Boolean;
    function GetLastRecordPage(SessionID: TABSSessionID; var PageNo: TABSPageNo): Boolean;
    function GetNextRecordPage(SessionID: TABSSessionID; CurrentPageNo: TABSPageNo; var NextPageNo: TABSPageNo): Boolean;
    function GetPriorRecordPage(SessionID: TABSSessionID; CurrentPageNo: TABSPageNo; var PriorPageNo: TABSPageNo): Boolean;

    procedure GetRecordByRecNo(SessionID: TABSSessionID; RecNo: TABSRecordNo; var PageNo: TABSPageNo; var RecNoOnPage: Integer);
    procedure GetRecNoByRecord(SessionID: TABSSessionID; PageNo: TABSPageNo; RecNoOnPage: Integer; var RecNo: TABSRecordNo);

    procedure Validate(SessionID: TABSSessionID; StoredRecordCount: Integer);

    property MaxRecordsOnPage: Integer read FMaxRecordsOnPage write FMaxRecordsOnPage;
  end; // TABSBTreeRecordPageIndex


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeBlobPageIndex
//
////////////////////////////////////////////////////////////////////////////////

  TABSBTreeBlobPageIndex = class (TABSBTreePageIndex)
   protected
    function CanAddNewItem(OldValue: Integer; NewItemSize: Integer): Boolean; override;

   public
    function FindPageForNewBlob(SessionID: TABSSessionID; BlobSize: Integer; var PageNo: TABSPageNo): Boolean;
    procedure AddBlob(SessionID: TABSSessionID; BlobSize: Integer; PageNo: TABSPageNo);
    procedure DeleteBlob(SessionID: TABSSessionID; BlobSize: Integer; PageNo: TABSPageNo);
    function GetBlobPageAllocatedSpace(SessionID: TABSSessionID; PageNo: TABSPageNo): Integer;
  end; // TABSBTreeBlobPageIndex


implementation

uses ABSLocalEngine;

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


//------------------------------------------------------------------------------
// constructor
//------------------------------------------------------------------------------
constructor TABSKeyPath.Create;
begin
  Clear;
end;// Create


//------------------------------------------------------------------------------
// Clear
//------------------------------------------------------------------------------
procedure TABSKeyPath.Clear;
begin
  Count := 0;
  ItemNo := 0;
end;// Clear


//------------------------------------------------------------------------------
// Assign
//------------------------------------------------------------------------------
procedure TABSKeyPath.Assign(KeyPath: TABSKeyPath);
begin
  Count := KeyPath.Count;
  ItemNo := KeyPath.ItemNo;
  PositionType := KeyPath.PositionType;
  IndexState := KeyPath.IndexState;
  Move(KeyPath.Items[0], Items[0], Count * sizeof(Items[0]));
end;// Assign


//------------------------------------------------------------------------------
// AddItem
//------------------------------------------------------------------------------
procedure TABSKeyPath.AddItem(aPageNo: TABSPageNo; aEntryNo, aEntryCount: Integer);
begin
  Items[ItemNo].PageNo := aPageNo;
  Items[ItemNo].EntryNo := aEntryNo;
  Items[ItemNo].EntryCount := aEntryCount;
  Inc(ItemNo);
  Inc(Count);
end;// AddItem


//------------------------------------------------------------------------------
// DeleteLastItem
//------------------------------------------------------------------------------
procedure TABSKeyPath.DeleteLastItem;
begin
  Dec(ItemNo);
  Dec(Count);
end;// DeleteLastItem


//------------------------------------------------------------------------------
// IncLevel
//------------------------------------------------------------------------------
procedure TABSKeyPath.IncLevel;
begin
  Inc(ItemNo);
end;// IncLevel


//------------------------------------------------------------------------------
// DecLevel
//------------------------------------------------------------------------------
procedure TABSKeyPath.DecLevel;
begin
  Dec(ItemNo);
end;// DecLevel

//------------------------------------------------------------------------------
// GetCurrentPageNo
//------------------------------------------------------------------------------
function TABSKeyPath.GetCurrentPageNo: TABSPageNo;
begin
  Result := Items[ItemNo].PageNo;
end;// GetCurrentPageNo


//------------------------------------------------------------------------------
// SetCurrentPageNo
//------------------------------------------------------------------------------
procedure TABSKeyPath.SetCurrentPageNo(Value: TABSPageNo);
begin
  Items[ItemNo].PageNo := Value;
end;// SetCurrentPageNo


//------------------------------------------------------------------------------
// PageExists
//------------------------------------------------------------------------------
function TABSKeyPath.PageExists(aPageNo: TABSPageNo): Boolean;
var
  i: Integer;
begin
  Result := False;
  for i := 0 to Count-1 do
   if (Items[i].PageNo = aPageNo) then
    begin
     Result := True;
     break;
    end;
end;// PageExists


//------------------------------------------------------------------------------
// return 0, 1, -1 if (Self = aKeyPath), (Self > aKeyPath), (Self < aKeyPath)
//------------------------------------------------------------------------------
function TABSKeyPath.Compare(aKeyPath: TABSKeyPath): Integer;
var
  i: Integer;
begin
  if (Count <> aKeyPath.Count) then
   raise EABSException.Create(20051, ErrorAInvalidIndexKeyPath);
  Result := 0;
  for i := 0 to Count-1 do
   begin
     if (Items[i].PageNo <> aKeyPath.Items[i].PageNo) then
      raise EABSException.Create(20052, ErrorAInvalidIndexKeyPath);
     if (Items[i].EntryNo < aKeyPath.Items[i].EntryNo) then
      begin
       Result := -1;
       break;
      end
     else
      if (Items[i].EntryNo > aKeyPath.Items[i].EntryNo) then
       begin
        Result := 1;
        break;
       end;
   end;
end;// Compare


//------------------------------------------------------------------------------
// GetApproxRecNoInPercents
//------------------------------------------------------------------------------
function TABSKeyPath.GetApproxRecNoInPercents: double;
var
  i:               Integer;
  ApproxRecNo:     TABSRecordNo;
  ApproxRecCount:  TABSRecordNo;
begin
  ApproxRecNo := 0;
  ApproxRecCount := 1;
  for i := Count-1 downto 0 do
   begin
     ApproxRecNo := Items[i].EntryNo * ApproxRecCount + ApproxRecNo;
     ApproxRecCount := Items[i].EntryCount * ApproxRecCount;
   end;
  Result := ApproxRecNo / ApproxRecCount;
end;// GetApproxRecNoInPercents


//------------------------------------------------------------------------------
// GetBitmapRecNoByIndexPosition
//------------------------------------------------------------------------------
function TABSKeyPath.GetBitmapRecNoByIndexPosition(MaxEntriesPerPage: Integer): TABSRecordNo;
var
  i: Integer;
begin
  Result := 0;
  Inc(MaxEntriesPerPage);
  // encode IndexPos to RecNo
  for i := Count-1 downto 0 do
    Result := Result + (Items[(Count-1)-i].EntryNo+1) * Round(Power(MaxEntriesPerPage, i));
end;// GetBitmapRecNoByIndexPosition


//------------------------------------------------------------------------------
// FillItemsByBitmapRecNo
//------------------------------------------------------------------------------
procedure TABSKeyPath.FillItemsByBitmapRecNo(RecordNo, MaxEntriesPerPage: Integer);
var
  i, rn: Integer;
begin
  Clear;
  Inc(MaxEntriesPerPage);
  // calc count
  rn := RecordNo;
  Count := 0;
  while (rn > 0) do
    begin
      Inc(Count);
      rn := rn div MaxEntriesPerPage;
    end;
  // decode RecordNo to IndexPos
  i := 0;
  repeat
    inc(i);
    Items[Count-i].EntryNo := (RecordNo mod MaxEntriesPerPage)-1;
    Items[Count-i].PageNo := INVALID_PAGE_NO;
    Items[Count-i].EntryCount := 0;
    RecordNo := RecordNo div MaxEntriesPerPage;
  until (RecordNo = 0);
end;// FillItemsByBitmapRecNo


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


//------------------------------------------------------------------------------
// get count of key parts
//------------------------------------------------------------------------------
function TABSBTreeKeyRef.GetPartCount: Integer;
begin
  Result := Length(Parts);
end;// GetPartCount


//------------------------------------------------------------------------------
// set size of array
//------------------------------------------------------------------------------
procedure TABSBTreeKeyRef.SetPartCount(Value: Integer);
begin
  SetLength(Parts, Value);
end;// SetPartCount


//------------------------------------------------------------------------------
// allocate buffer for short key
//------------------------------------------------------------------------------
function TABSBTreeKeyRef.AllocShortKeyBuffer: TAbsPByte;
begin
  Result := MemoryManager.AllocMem(FShortKeySize);
end;// AllocShortKeyBuffer


//------------------------------------------------------------------------------
// allocate buffer for full key
//------------------------------------------------------------------------------
function TABSBTreeKeyRef.AllocFullKeyBuffer: TAbsPByte;
begin
  Result := MemoryManager.AllocMem(FFullKeySize);
end;// AllocFullKeyBuffer


//------------------------------------------------------------------------------
// free key buffer
//------------------------------------------------------------------------------
procedure TABSBTreeKeyRef.FreeAndNilKeyBuffer(var Buffer: TAbsPByte);
begin
  MemoryManager.FreeAndNillMem(Buffer);
end;// FreeAndNilKeyBuffer


//------------------------------------------------------------------------------
// CompareReferences
//------------------------------------------------------------------------------
function TABSBTreeKeyRef.CompareReferences(Reference1, Reference2: TAbsPByte; Size: Integer): Integer;
var
  i: Integer;
begin
  Result := 0;
  if (Size = sizeof(TABSRecordID)) then
    begin
      if (PABSRecordID(Reference1)^.PageNo < PABSRecordID(Reference2)^.PageNo) then
        Result := -1
      else
       if (PABSRecordID(Reference1)^.PageNo > PABSRecordID(Reference2)^.PageNo) then
         Result := 1
       else
         if (PABSRecordID(Reference1)^.PageItemNo < PABSRecordID(Reference2)^.PageItemNo) then
           Result := -1
         else
           if (PABSRecordID(Reference1)^.PageItemNo > PABSRecordID(Reference2)^.PageItemNo) then
             Result := 1
           else
             Result := 0;
    end
  else
    for i := 0 to Size-1 do
     if ((Reference1+i)^ < (Reference2+i)^) then
      begin
       Result := -1;
       break;
      end
     else
     if ((Reference1+i)^ > (Reference2+i)^) then
      begin
       Result := 1;
       break;
      end
end;// CompareReferences


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


//------------------------------------------------------------------------------
// RetrieveFullKeyByRecordID
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.RetrieveFullKeyByRecordID(RecordID: TABSRecordID; FullKey: TAbsPByte;
                                         SessionID: TABSSessionID);
var
  NavigationInfo: TABSNavigationInfo;
begin
  NavigationInfo.GetRecordMode := grmCurrent;
  NavigationInfo.RecordID := RecordID;
  NavigationInfo.FirstPosition := False;
  NavigationInfo.LastPosition := False;
  NavigationInfo.RecordBuffer := MemoryManager.AllocMem(
     TABSTableData(LTableData).FieldManager.FieldDefs.GetMemoryRecordBufferSize);
  try
    TABSTableData(LTableData).RecordManager.GetRecordBuffer(SessionID, NavigationInfo);
    if (NavigationInfo.GetRecordResult <> grrOK) then
      raise EABSException.Create(20170, ErrorACannotRetreiveRecord);
    // make full key from fetched record buffer
    MakeFullKeyFromRecordBuffer(NavigationInfo.RecordBuffer, FullKey);
  finally
    MemoryManager.FreeAndNillMem(NavigationInfo.RecordBuffer);
  end;
end;// RetrieveFullKeyByRecordID


//------------------------------------------------------------------------------
// SetPartCount
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.SetPartCount(Value: Integer);
var
  i: Integer;
begin
  inherited SetPartCount(Value);
  SetLength(FCompareLengths, PartCount);
  for i:=0 to Length(FCompareLengths)-1 do
    FCompareLengths[i] := -1;
end;// SetPartCount


//------------------------------------------------------------------------------
// constructor
//------------------------------------------------------------------------------
constructor TABSRecordKeyRef.Create;
begin
  PartCount := 0;
  FShortKeySize := 0;
  FFullKeySize := 0;
  FKeyIsReference := False;
  FReferenceSize := 0;
  FCompareFieldCount := 0;
  LTableData := nil;
  LRecordBuffer := nil;
end;// Create


//------------------------------------------------------------------------------
// assign IndexDef
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.Assign(IndexDef: TABSIndexDef; aTableData: Pointer);
var
  i: Integer;
  OffsetInShortKeyBuffer: Integer;
  OffsetInFullKeyBuffer: Integer;
  TableData: TABSTableData;
  FieldDef: TABSFieldDef;
begin
  LTableData := aTableData;
  TableData := TABSTableData(LTableData);
  PartCount := IndexDef.ColumnCount;
  FCompareFieldCount := PartCount;
  OffsetInShortKeyBuffer := 0;
  OffsetInFullKeyBuffer := 0;
  FShortKeySize := 0;
  FFullKeySize := 0;
  if (TableData.FieldManager = nil) then
    raise EABSException.Create(20044, ErrorANilPointer);
  if (TableData.FieldManager.FieldDefs = nil) then
    raise EABSException.Create(20045, ErrorANilPointer);
  for i := 0 to IndexDef.ColumnCount-1 do
   begin
    Parts[i].OffsetInShortKeyBuffer := OffsetInShortKeyBuffer;
    Parts[i].OffsetInFullKeyBuffer := OffsetInFullKeyBuffer;
    FieldDef := TableData.FieldManager.FieldDefs.GetFieldDefByName(
                                                 IndexDef.Columns[i].FieldName);
    if (FieldDef = nil) then
     raise EABSException.Create(20043, ErrorACannotFindIndexField,
                                [IndexDef.Columns[i].FieldName]);

    if (IsBLOBFieldType(FieldDef.BaseFieldType)) then
     raise EABSException.Create(20295, ErrorACannotIndexBlobField,
                                [IndexDef.Columns[i].FieldName]);
    Parts[i].OffsetInRecordBuffer := FieldDef.MemoryOffset;
    Parts[i].FieldNo := TableData.FieldManager.FieldDefs.GetDefNumberByName(
          IndexDef.Columns[i].FieldName);

    Parts[i].AddedSize := 0;
    // short index
    if (IndexDef.Columns[i].MaxIndexedSize < FieldDef.MemoryDataSize) then
      begin
        Parts[i].AddedSize := 2;
        Parts[i].ShortSize := IndexDef.Columns[i].MaxIndexedSize+2+BTreeNullFlagSize;
      end
    else
      Parts[i].ShortSize := FieldDef.MemoryDataSize+BTreeNullFlagSize;
    OffsetInShortKeyBuffer := OffsetInShortKeyBuffer + Parts[i].ShortSize;
    FShortKeySize := FShortKeySize + Parts[i].ShortSize;

    // full index
    Parts[i].FullSize := FieldDef.MemoryDataSize+BTreeNullFlagSize;
    OffsetInFullKeyBuffer := OffsetInFullKeyBuffer + Parts[i].FullSize;
    FFullKeySize := FFullKeySize + Parts[i].FullSize;

    Parts[i].DataType := FieldDef.BaseFieldType;
    Parts[i].Descending := IndexDef.Columns[i].Descending;
    Parts[i].CaseInsensitive := IndexDef.Columns[i].CaseInsensitive;
   end;
end;// Assign


//------------------------------------------------------------------------------
// MakeShortKeyFromRecordBuffer
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.MakeShortKeyFromRecordBuffer(RecordBuffer: TAbsPByte; KeyBuffer: TAbsPByte);
var
  i: Integer;
begin
  LRecordBuffer := RecordBuffer;
  for i := 0 to PartCount-1 do
   begin
    if (CheckNullFlag(Parts[i].FieldNo, RecordBuffer)) then
     PAnsiChar(KeyBuffer+Parts[i].OffsetInShortKeyBuffer)^ := BTreeKeyIsNull
    else
     begin
      PAnsiChar(KeyBuffer+Parts[i].OffsetInShortKeyBuffer)^ := BTreeKeyIsNotNull;
      Move((RecordBuffer+Parts[i].OffsetInRecordBuffer)^,
           (KeyBuffer+Parts[i].OffsetInShortKeyBuffer+BTreeNullFlagSize)^,
           Parts[i].ShortSize-Parts[i].AddedSize-BTreeNullFlagSize);
     end;
   end;
end;// MakeShortKeyFromRecordBuffer


//------------------------------------------------------------------------------
// MakeFullKeyFromRecordBuffer
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.MakeFullKeyFromRecordBuffer(RecordBuffer: TAbsPByte; KeyBuffer: TAbsPByte);
var
  i: Integer;
begin
  for i := 0 to PartCount-1 do
   begin
    if (CheckNullFlag(Parts[i].FieldNo, RecordBuffer)) then
     PAnsiChar(KeyBuffer+Parts[i].OffsetInFullKeyBuffer)^ := BTreeKeyIsNull
    else
     begin
      PAnsiChar(KeyBuffer+Parts[i].OffsetInFullKeyBuffer)^ := BTreeKeyIsNotNull;
      Move((RecordBuffer+Parts[i].OffsetInRecordBuffer)^,
           (KeyBuffer+Parts[i].OffsetInFullKeyBuffer+BTreeNullFlagSize)^,
           Parts[i].FullSize-BTreeNullFlagSize);
     end;
   end;
end;// MakeFullKeyFromRecordBuffer


//------------------------------------------------------------------------------
// compare two short keys in index order sense
//------------------------------------------------------------------------------
function TABSRecordKeyRef.CompareShortKeys(KeyBuffer1, KeyBuffer2: TAbsPByte;
                                           MayUseFullKeys: Boolean=False;
                                           SessionID: TABSSessionID = INVALID_SESSION_ID;
                                           Reference1: TAbsPByte=nil; Reference2: TAbsPByte=nil): Integer;
var
  i: Integer;
  IsNull1, IsNull2: Boolean;
  FullKey1, FullKey2: TAbsPByte;
  bGetFullKeys: Boolean;
begin
  Result := 0;
  for i := 0 to CompareFieldCount-1 do
   begin
    IsNull1 := (PAnsiChar(KeyBuffer1 + Parts[i].OffsetInShortKeyBuffer)^ = BTreeKeyIsNull);
    IsNull2 := (PAnsiChar(KeyBuffer2 + Parts[i].OffsetInShortKeyBuffer)^ = BTreeKeyIsNull);
    Result := CompareValueBuffersForOrder(
               KeyBuffer1 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize,
               KeyBuffer2 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize,
               Parts[i].DataType,
               Parts[i].DataType,
               IsNull1,
               IsNull2,
               Min(FCompareLengths[i],Parts[i].ShortSize-Parts[i].AddedSize),
               Parts[i].CaseInsensitive);

    // if short keys are equal, and cannot compare Full keys => assume equal
    if ((Result = 0) and (not MayUseFullKeys) and (Parts[i].AddedSize <> 0)) then
      break
    else
    // if short keys are equal, can compare Full keys?
    if ((Result = 0) and (MayUseFullKeys) and (Parts[i].AddedSize <> 0) and
        (Reference2 <> nil)) then
      begin
        // check whether the full strings are really equal (not only truncated)
        PByte(KeyBuffer1 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize +
        Parts[i].ShortSize - Parts[i].AddedSize-1)^ := 1;
        try
          bGetFullKeys := (CompareValueBuffersForOrder(
                 KeyBuffer1 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize,
                 KeyBuffer2 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize,
                 Parts[i].DataType,
                 Parts[i].DataType,
                 IsNull1,
                 IsNull2,
                 Min(FCompareLengths[i],Parts[i].ShortSize-Parts[i].AddedSize),
                 Parts[i].CaseInsensitive) <> 0);
        finally
          PByte(KeyBuffer1 + Parts[i].OffsetInShortKeyBuffer + BTreeNullFlagSize +
           Parts[i].ShortSize - Parts[i].AddedSize-1)^ := 0;
        end;

        if (bGetFullKeys) then
          begin
            FullKey1 := AllocFullKeyBuffer;
            FullKey2 := AllocFullKeyBuffer;
            try
              // make full key 1 from assigned record buffer?
              if (Reference1 = nil) then
                MakeFullKeyFromRecordBuffer(LRecordBuffer, FullKey1)
              else
                // retreive full key2 by reference in index page
                RetrieveFullKeyByRecordID(PABSRecordID(Reference1)^, FullKey1, SessionID);
              // retreive full key2 by reference in index page
              RetrieveFullKeyByRecordID(PABSRecordID(Reference2)^, FullKey2, SessionID);
              Result := CompareFullKeys(FullKey1, FullKey2);
            finally
              FreeAndNilKeyBuffer(FullKey1);
              FreeAndNilKeyBuffer(FullKey2);
            end;
            break;
          end;
      end
    else
      begin
        if (Parts[i].Descending) then
         Result := -Result;

        if (Result <> 0) then
         break;
      end;
   end;
end;// CompareShortKeys


//------------------------------------------------------------------------------
// compare two keys in index order sense
//------------------------------------------------------------------------------
function TABSRecordKeyRef.CompareFullKeys(KeyBuffer1, KeyBuffer2: TAbsPByte): Integer;
var
  i: Integer;
  IsNull1, IsNull2: Boolean;
begin
  Result := 0;
  for i := 0 to CompareFieldCount-1 do
   begin
    IsNull1 := (PAnsiChar(KeyBuffer1 + Parts[i].OffsetInFullKeyBuffer)^ = BTreeKeyIsNull);
    IsNull2 := (PAnsiChar(KeyBuffer2 + Parts[i].OffsetInFullKeyBuffer)^ = BTreeKeyIsNull);
    Result := CompareValueBuffersForOrder(
               KeyBuffer1 + Parts[i].OffsetInFullKeyBuffer + BTreeNullFlagSize,
               KeyBuffer2 + Parts[i].OffsetInFullKeyBuffer + BTreeNullFlagSize,
               Parts[i].DataType,
               Parts[i].DataType,
               IsNull1,
               IsNull2,
               FCompareLengths[i],
               Parts[i].CaseInsensitive);
    if (Parts[i].Descending) then
     Result := -Result;
    if (Result <> 0) then
     break;
   end;
end;// CompareFullKeys


//------------------------------------------------------------------------------
// SetPartialCompare
//------------------------------------------------------------------------------
procedure TABSRecordKeyRef.SetPartialCompare(RecordBuffer: TAbsPByte; PartialCompare: Boolean);
var
  i: Integer;
begin
  for i := 0 to PartCount-1 do
    begin
      if PartialCompare and (not CheckNullFlag(Parts[i].FieldNo, RecordBuffer)) then
        begin
          if (IsStringFieldType(Parts[i].DataType)) then
            if (IsWideStringFieldType(Parts[i].DataType)) then
              FCompareLengths[i] := Length(WideString(PWideChar(RecordBuffer+Parts[i].OffsetInRecordBuffer)))
            else
              FCompareLengths[i] := StrLen(PAnsiChar(RecordBuffer+Parts[i].OffsetInRecordBuffer))
          else
            FCompareLengths[i] := -1;
        end
      else
        FCompareLengths[i] := -1;
    end;
end;// SetPartialCompare




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


//------------------------------------------------------------------------------
// Create
//------------------------------------------------------------------------------
constructor TABSPageKeyRef.Create;
begin
  PartCount := 1;
  Parts[0].OffsetInShortKeyBuffer := 0;
  Parts[0].OffsetInFullKeyBuffer := 0;
  Parts[0].ShortSize := sizeof(TABSPageNo);
  Parts[0].FullSize := sizeof(TABSPageNo);
  Parts[0].AddedSize := 0;
  Parts[0].DataType := bftSignedInt32;
  Parts[0].Descending := False;
  FShortKeySize := sizeof(TABSPageNo);
  FFullKeySize := sizeof(TABSPageNo);
  FKeyIsReference := False;
  FReferenceSize := sizeof(Word);
end;// Create


//------------------------------------------------------------------------------
// CompareShortKeys
//------------------------------------------------------------------------------
function TABSPageKeyRef.CompareShortKeys(KeyBuffer1, KeyBuffer2: TAbsPByte;
                          MayUseFullKeys: Boolean=False;
                          SessionID: TABSSessionID = INVALID_SESSION_ID;
                          Reference1: TAbsPByte=nil; Reference2: TAbsPByte=nil): Integer;
begin
  if (PABSPageNo(KeyBuffer1)^ < PABSPageNo(KeyBuffer2)^) then
    Result := -1
  else
  if (PABSPageNo(KeyBuffer1)^ > PABSPageNo(KeyBuffer2)^) then
    Result := 1
  else
    Result := 0;
end;// CompareShortKeys


//------------------------------------------------------------------------------
// CompareFullKeys
//------------------------------------------------------------------------------
function TABSPageKeyRef.CompareFullKeys(KeyBuffer1, KeyBuffer2: TAbsPByte): Integer;
begin
  Result := CompareShortKeys(KeyBuffer1, KeyBuffer2);
end;// CompareFullKeys




////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePageController
//
////////////////////////////////////////////////////////////////////////////////

//------------------------------------------------------------------------------
// get IsRoot
//------------------------------------------------------------------------------
function TABSBTreePage.GetIsRoot: Boolean;
begin
  Result := PABSBTreePageHeader(PageData)^.IsRoot;
end;// GetIsRoot


//------------------------------------------------------------------------------
// set IsRoot
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetIsRoot(Value: Boolean);
begin
  PABSBTreePageHeader(PageData)^.IsRoot := Value;
end;// SetIsRoot


//------------------------------------------------------------------------------
// get IsLeaf
//------------------------------------------------------------------------------
function TABSBTreePage.GetIsLeaf: Boolean;
begin
  Result := PABSBTreePageHeader(PageData)^.IsLeaf;
end;// GetIsLeaf


//------------------------------------------------------------------------------
// set IsLeaf
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetIsLeaf(Value: Boolean);
begin
  PABSBTreePageHeader(PageData)^.IsLeaf := Value;
end;// SetIsLeaf


//------------------------------------------------------------------------------
// get Left page No
//------------------------------------------------------------------------------
function TABSBTreePage.GetLeftPageNo: TABSPageNo;
begin
  Result := PABSBTreePageHeader(PageData)^.LeftPageNo;
end;// GetLeftPageNo


//------------------------------------------------------------------------------
// set LeftPageNo
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetLeftPageNo(Value: TABSPageNo);
begin
  PABSBTreePageHeader(PageData)^.LeftPageNo := Value;
end;// SetLeft


//------------------------------------------------------------------------------
// get right PageNo
//------------------------------------------------------------------------------
function TABSBTreePage.GetRightPageNo: TABSPageNo;
begin
  Result := PABSBTreePageHeader(PageData)^.RightPageNo;
end;// GetRightPageNo


//------------------------------------------------------------------------------
// set Right PageNo
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetRightPageNo(Value: TABSPageNo);
begin
  PABSBTreePageHeader(PageData)^.RightPageNo := Value;
end;// SetRightPageNo


//------------------------------------------------------------------------------
// get (page has keys or only references?)
//------------------------------------------------------------------------------
function TABSBTreePage.GetHasKeys: Boolean;
begin
  Result := PABSBTreePageHeader(PageData)^.HasKeys;
end;// GetHasKeys


//------------------------------------------------------------------------------
// set HasKeys
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetHasKeys(Value: Boolean);
begin
  PABSBTreePageHeader(PageData)^.HasKeys := Value;
end;// SetHasKeys


//------------------------------------------------------------------------------
// get (key has suffix?)
//------------------------------------------------------------------------------
function TABSBTreePage.GetHasSuffixes: Boolean;
begin
  Result := PABSBTreePageHeader(PageData)^.HasSuffixes;
end;// GetHasSuffixes


//------------------------------------------------------------------------------
// set KeyHasSuffix
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetHasSuffixes(Value: Boolean);
begin
  PABSBTreePageHeader(PageData)^.HasSuffixes := Value;
end;// SetHasSuffixes


//------------------------------------------------------------------------------
// get key prefix size
//------------------------------------------------------------------------------
function TABSBTreePage.GetKeyPrefixSize: Word;
begin
  Result := PABSBTreePageHeader(PageData)^.KeyPrefixSize;
end;// GetKeyPrefixSize


//------------------------------------------------------------------------------
// set key prefix size
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetKeyPrefixSize(Value: Word);
begin
  PABSBTreePageHeader(PageData)^.KeyPrefixSize := Value;
end;// SetKeyPrefixSize


//------------------------------------------------------------------------------
// get entry count
//------------------------------------------------------------------------------
function TABSBTreePage.GetEntryCount: Integer;
begin
  Result := PABSBTreePageHeader(PageData)^.EntryCount;
end;// GetEntryCount


//------------------------------------------------------------------------------
// set Entry count
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetEntryCount(Value: Integer);
begin
  PABSBTreePageHeader(PageData)^.EntryCount := Value;
end;// SetEntryCount


//------------------------------------------------------------------------------
// get page prefix size
//------------------------------------------------------------------------------
function TABSBTreePage.GetPagePrefixSize: Word;
begin
  Result := PABSBTreePageHeader(PageData)^.PagePrefixSize;
end;// GetPagePrefixSize


//------------------------------------------------------------------------------
// set page prefix size
//------------------------------------------------------------------------------
procedure TABSBTreePage.SetPagePrefixSize(Value: Word);
begin
  PABSBTreePageHeader(PageData)^.PagePrefixSize := Value;
end;// GetPagePrefixSize


//------------------------------------------------------------------------------
// GetEntrySize
//------------------------------------------------------------------------------
function TABSBTreePage.GetEntrySize: Integer;
begin
  Result := KeyPrefixSize + ReferenceSize;
  if (HasSuffixes) then
    Result := Result + SuffixPtrSize;
end;// GetEntrySize


//------------------------------------------------------------------------------
// GetReferenceSize
//------------------------------------------------------------------------------
function TABSBTreePage.GetReferenceSize: Integer;
begin
  if (IsLeaf) then
   Result := LKeyRef.ReferenceSize
  else
   Result := sizeof(TABSPageNo);
end;// GetReferenceSize


//------------------------------------------------------------------------------
// GetEntriesOffset
//------------------------------------------------------------------------------
function TABSBTreePage.GetEntriesOffset: Integer;
begin
  Result := sizeof(TABSBTreePageHeader) + PagePrefixSize;
end;// GetEntriesOffset


//------------------------------------------------------------------------------
// GetSuffixPtrSize
//------------------------------------------------------------------------------
function TABSBTreePage.GetSuffixPtrSize: Integer;
begin
  Result := sizeof(TABSPageItemID);
end;// GetSuffixPtrSize


//------------------------------------------------------------------------------
// create
//------------------------------------------------------------------------------
constructor TABSBTreePage.Create(PageManager: TABSPageManager; KeyRef: TABSBTreeKeyRef);
begin
  LPageManager := PageManager;
  LKeyRef := KeyRef;
  FLeafController := TABSBTreeLeafController.Create(Self);
  FNodeController := TABSBTreeNodeController.Create(Self);
end;// Create


//------------------------------------------------------------------------------
// destructor
//------------------------------------------------------------------------------
destructor TABSBTreePage.Destroy;
begin
  FLeafController.Free;
  FNodeController.Free;
  inherited Destroy;
end;// Destroy


//------------------------------------------------------------------------------
// AddIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreePage.AddIndexPage(SessionID: TABSSessionID; var Page: TABSBTreePage);
begin
  Page := TABSBTreePage.Create(LPageManager, LKeyRef);
  try
    Page.Page := LPageManager.AddPage(SessionID, ptTableIndex);
    Page.Init;
  except
    Page.Free;
    raise;
  end;
end;// AddIndexPage


//------------------------------------------------------------------------------
// RemoveIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreePage.RemoveIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo);
begin
  LPageManager.RemovePage(SessionID, PageNo);
end;// RemoveIndexPage


//------------------------------------------------------------------------------
// GetIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreePage.GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo;
                                     var Page: TABSBTreePage);
begin
  Page := TABSBTreePage.Create(LPageManager, LKeyRef);
  try
    Page.Page := LPageManager.GetPage(SessionID, PageNo, ptTableIndex);
  except
    Page.Free;
    raise;
  end;
end;// GetIndexPage


//------------------------------------------------------------------------------
// PutIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreePage.PutIndexPage(Page: TABSBTreePage);
begin
  LPageManager.PutPage(Page.Page);
  Page.Free;
end;// PutIndexPage


//------------------------------------------------------------------------------
// init data
//------------------------------------------------------------------------------
procedure TABSBTreePage.Init;
begin
  IsRoot := False;
  IsLeaf := False;
  LeftPageNo := INVALID_PAGE_NO;
  RightPageNo := INVALID_PAGE_NO;
  HasKeys := False;
  HasSuffixes := False;
  KeyPrefixSize := 0;
  EntryCount := 0;
  PagePrefixSize := 0;
end;// Init


//------------------------------------------------------------------------------
// init as root leaf
//------------------------------------------------------------------------------
procedure TABSBTreePage.InitAsRoot;
begin
  Init;
  IsRoot := True;
  IsLeaf := True;
  HasKeys := True;
  HasSuffixes := False;
  PagePrefixSize := 0;
  KeyPrefixSize := LKeyRef.ShortKeySize;
end;// InitAsRoot


//------------------------------------------------------------------------------
// CopyFrom
//------------------------------------------------------------------------------
procedure TABSBTreePage.CopyFrom(Source: TABSBTreePage; StartNo, Count: Integer);
begin
  Move(
       Source.PageData^,
       PageData^,
       EntriesOffset);
  Move((Source.PageData+Source.EntriesOffset+StartNo*Source.EntrySize)^,
       (PageData+EntriesOffset)^,
       Source.EntrySize * Count);
  EntryCount := Count;
end;// CopyFrom


//------------------------------------------------------------------------------
// AppendFrom
//------------------------------------------------------------------------------
procedure TABSBTreePage.AppendFrom(Source: TABSBTreePage; StartNo, Count: Integer);
begin
  Move((Source.PageData+Source.EntriesOffset+StartNo*Source.EntrySize)^,
       (PageData+EntriesOffset+EntryCount*EntrySize)^,
       Source.EntrySize*Count);
  EntryCount := EntryCount + Count;
end;// AppendFrom


//------------------------------------------------------------------------------
// InsertFrom
//------------------------------------------------------------------------------
procedure TABSBTreePage.InsertFrom(Source: TABSBTreePage; StartNo, Count: Integer);
begin
  ABSMove(
          (PageData + EntriesOffset)^,
          (PageData + EntriesOffset + Count * EntrySize)^,
          EntrySize * EntryCount
         );

  Move((Source.PageData+Source.EntriesOffset+StartNo*Source.EntrySize)^,
       (PageData+EntriesOffset)^,
       Source.EntrySize*Count);
  EntryCount := EntryCount + Count;
end;// InsertFrom


//------------------------------------------------------------------------------
// InsertLeafEntry
//------------------------------------------------------------------------------
procedure TABSBTreePage.InsertLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath);
begin
  if (IsLeaf) then
    FLeafController.InsertLeafEntry(SessionID, Key, Reference, KeyPath)
  else
    FNodeController.InsertLeafEntry(SessionID, Key, Reference, KeyPath);
end;// InsertLeafEntry


//------------------------------------------------------------------------------
// InsertNodeEntry
//------------------------------------------------------------------------------
procedure TABSBTreePage.InsertNodeEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath);
begin
  if (IsLeaf) then
    raise EABSException.Create(20020, ErrorABTreeInvalidCall)
  else
    FNodeController.InsertNodeEntry(SessionID, Key, Reference, KeyPath);
end;// InsertNodeEntry


//------------------------------------------------------------------------------
// DeleteLeafEntry
//------------------------------------------------------------------------------
function TABSBTreePage.DeleteLeafEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte; KeyPath: TABSKeyPath): Boolean;
begin
  if (IsLeaf) then
    Result := FLeafController.DeleteLeafEntry(SessionID, Key, Reference, KeyPath)
  else
    Result := FNodeController.DeleteLeafEntry(SessionID, Key, Reference, KeyPath);
end;// DeleteLeafEntry


//------------------------------------------------------------------------------
// DeleteNodeEntry
//------------------------------------------------------------------------------
procedure TABSBTreePage.DeleteNodeEntry(
                  SessionID:     TABSSessionID;
                  KeyPath:       TABSKeyPath;
                  MergeWithLeft: Boolean
                        );
begin
  if (IsLeaf) then
    raise EABSException.Create(20024, ErrorABTreeInvalidCall)
  else
    FNodeController.DeleteNodeEntry(SessionID, KeyPath, MergeWithLeft);
end;// DeleteNodeEntry


//------------------------------------------------------------------------------
// FindEntry
//------------------------------------------------------------------------------
function TABSBTreePage.FindEntry(
                          SessionID: TABSSessionID;
                          Key:       TAbsPByte;
                          Reference: TAbsPByte;
                          Position:  TABSKeyPath
                         ): Boolean;
begin
  if (IsLeaf) then
    Result := FLeafController.FindEntry(SessionID, Key, Reference, Position)
  else
    Result := FNodeController.FindEntry(SessionID, Key, Reference, Position)
end;// FindEntry


//------------------------------------------------------------------------------
// GetFirstPosition
//------------------------------------------------------------------------------
function TABSBTreePage.GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
begin
  if (IsLeaf) then
    Result := FLeafController.GetFirstPosition(SessionID, Position)
  else
    Result := FNodeController.GetFirstPosition(SessionID, Position);
end;// GetFirstPosition


//------------------------------------------------------------------------------
// GetLastPosition
//------------------------------------------------------------------------------
function TABSBTreePage.GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
begin
  if (IsLeaf) then
    Result := FLeafController.GetLastPosition(SessionID, Position)
  else
    Result := FNodeController.GetLastPosition(SessionID, Position);
end;// Last


//------------------------------------------------------------------------------
// FindByCondition
//------------------------------------------------------------------------------
function TABSBTreePage.FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean;
begin
  if (EntryCount = 0) then
    Result := False
  else
   if (IsLeaf) then
     Result := FLeafController.FindByCondition(SessionID, First, Key, Operator, Position)
   else
     Result := FNodeController.FindByCondition(SessionID, First, Key, Operator, Position);
end;// FindByCondition


//------------------------------------------------------------------------------
// FreeAllPages
//------------------------------------------------------------------------------
procedure TABSBTreePage.FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean);
begin
  if (IsLeaf) then
    FLeafController.FreeAllPages(SessionID, KeepRootPage)
  else
    FNodeController.FreeAllPages(SessionID, KeepRootPage);
end;// FreeAllPages


//------------------------------------------------------------------------------
// CheckIntegrity
//------------------------------------------------------------------------------
procedure TABSBTreePage.CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
begin
  if (IsLeaf) then
    FLeafController.CheckIntegrity(SessionID, KeyPath)
  else
    FNodeController.CheckIntegrity(SessionID, KeyPath);
end;// CheckIntegrity


//------------------------------------------------------------------------------
// GetPKey
//------------------------------------------------------------------------------
function TABSBTreePage.GetPKey(KeyPosition: Integer): TAbsPByte;
begin
  Result := PageData+EntriesOffset+KeyPosition*EntrySize;
end;// GetPKey


//------------------------------------------------------------------------------
// GetPReference
//------------------------------------------------------------------------------
function TABSBTreePage.GetPReference(RefPosition: Integer): TAbsPByte;
begin
  Result := GetPKey(RefPosition) + KeyPrefixSize;
end;// GetPReference


//------------------------------------------------------------------------------
// GetFirstKey
//------------------------------------------------------------------------------
procedure TABSBTreePage.GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte);
begin
  if (IsLeaf) then
    FLeafController.GetFirstKey(SessionID, Key)
  else
    FNodeController.GetFirstKey(SessionID, Key);
end;// GetFirstKey


//------------------------------------------------------------------------------
// GetLastKey
//------------------------------------------------------------------------------
procedure TABSBTreePage.GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte);
begin
  if (IsLeaf) then
    FLeafController.GetLastKey(SessionID, Key)
  else
    FNodeController.GetLastKey(SessionID, Key);
end;// GetLastKey


//------------------------------------------------------------------------------
// GetFirstEntry
//------------------------------------------------------------------------------
procedure TABSBTreePage.GetFirstEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte);
begin
  if (IsLeaf) then
    FLeafController.GetFirstEntry(SessionID, Key, Reference)
  else
    FNodeController.GetFirstEntry(SessionID, Key, Reference);
end;// GetFirstEntry


//------------------------------------------------------------------------------
// GetLastEntry
//------------------------------------------------------------------------------
procedure TABSBTreePage.GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte);
begin
  if (IsLeaf) then
    FLeafController.GetLastEntry(SessionID, Key, Reference)
  else
    FNodeController.GetLastEntry(SessionID, Key, Reference);
end;// GetLastEntry


//------------------------------------------------------------------------------
// UpdateKey
//------------------------------------------------------------------------------
procedure TABSBTreePage.UpdateKey(Position: Integer; Key: TAbsPByte);
begin
  Move(Key^, GetPKey(Position)^, KeyPrefixSize);
end;// UpdateKey


//------------------------------------------------------------------------------
// Updtae Reference
//------------------------------------------------------------------------------
procedure TABSBTreePage.UpdateReference(Position: Integer; Reference: TAbsPByte);
begin
  Move(Reference^, GetPReference(Position)^, ReferenceSize);
end;// UpdateReference




////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePageController
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// GetKeyRef
//------------------------------------------------------------------------------
function TABSBTreePageController.GetKeyRef: TABSBTreeKeyRef;
begin
  Result := FPage.KeyRef;
end;// GetKeyRef


//------------------------------------------------------------------------------
// Can Add Entry?
//------------------------------------------------------------------------------
function TABSBTreePageController.CanAddEntry: Boolean;
begin
  if (FPage.PageDataSize >= sizeof(TABSBTreePageHeader) + FPage.PagePrefixSize +
                       (FPage.EntryCount+1)*FPage.EntrySize) then
    Result := True
  else
    Result := False;
end;// CanAddEntry


//------------------------------------------------------------------------------
// IsOverflow
//------------------------------------------------------------------------------
function TABSBTreePageController.IsOverflow: Boolean;
begin
  if (FPage.PageDataSize < sizeof(TABSBTreePageHeader) + FPage.PagePrefixSize +
                       FPage.EntryCount*FPage.EntrySize) then
    Result := True
  else
    Result := False;
end;// IsOverflow


//------------------------------------------------------------------------------
// CanUnderflow
//------------------------------------------------------------------------------
function TABSBTreePageController.CanUnderflow: Boolean;
begin
  if ((FPage.PageDataSize - sizeof(TABSBTreePageHeader) - FPage.PagePrefixSize) div 2 >
                       FPage.EntryCount*FPage.EntrySize) then
    Result := True
  else
    Result := False;
end;// CanUnderflow


//------------------------------------------------------------------------------
// CanMergeWithPage
//------------------------------------------------------------------------------
function TABSBTreePageController.CanMergeWithPage(Page: TABSBTreePage): Boolean;
begin
  Result := (Page.PageDataSize >
             FPage.EntriesOffset + (FPage.EntryCount+Page.EntryCount)*FPage.EntrySize);
end;// CanMergeWithPage


//------------------------------------------------------------------------------
// EnlargePageData
//------------------------------------------------------------------------------
procedure TABSBTreePageController.EnlargePageBuffer;
begin
  FPage.EnlargePageBuffer(FPage.PageSize + FPage.EntrySize);
end;// EnlargePageBuffer


//------------------------------------------------------------------------------
// Compare Keys
//------------------------------------------------------------------------------
function TABSBTreePageController.CompareKeys(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Key2Index: Word): Integer;
begin
  Result := KeyRef.CompareShortKeys(Key1, GetPKey(Key2Index), MayUseFullKeys,
                                    SessionID, nil, GetPReference(Key2Index));
end;// CompareKeys


//------------------------------------------------------------------------------
// CompareReferences
//------------------------------------------------------------------------------
function TABSBTreePageController.CompareReferences(
                             Reference1: TAbsPByte; Reference2Index: Word): Integer;
begin
  Result := KeyRef.CompareReferences(Reference1,
                                     GetPReference(Reference2Index),
                                     FPage.ReferenceSize);
end;// CompareReferences


//------------------------------------------------------------------------------
// get key position for insert (binary search)
//------------------------------------------------------------------------------
function TABSBTreePageController.GetKeyPosition(
                       MayUseFullKeys: Boolean;
                       SessionID: TABSSessionID;
                       Key: TAbsPByte;
                       Reference: TAbsPByte; // if finding entry
                       StartPosition: Integer = 0;
                       PositionType: PABSKeyPathPosition = nil;
                       SearchType: TABSKeySearchType = kstAny
                                ): Word;
var
  Lb, Ub, M: Integer;
  CmpRes, Pos, Delta: integer;
begin
  Pos := -1;
  Delta := 0;
  if (FPage.EntryCount = 0) then
   begin
    Result := 0;
    if (PositionType <> nil) then
     PositionType^ := kppEOF;
   end
  else
   begin
    Lb := StartPosition;
    Ub := FPage.EntryCount-1;
    repeat
      M := (Lb + Ub) div 2;
      CmpRes := CompareKeys(MayUseFullKeys, SessionID, Key, M);
      if ((CmpRes = 0) and (Reference <> nil)) then
        CmpRes := CompareEntries(MayUseFullKeys, SessionID, Key, Reference, M);
      if (CmpRes < 0) then
        Ub := M - 1
      else if (CmpRes > 0) then
        Lb := M + 1
      else
       begin
        Pos := M;
        if (PositionType <> nil) then
         PositionType^ := kppOnKey;
        case (SearchType) of
         kstFirst:
          Delta := -1;
         kstLast:
          Delta := 1;
         kstAny:
          Delta := 0;
         end;
        if (Delta <> 0) then
         repeat
          M := M + Delta;
          if ((M < StartPosition) or
              (M > FPage.EntryCount-1)) then
           break;
          CmpRes := CompareKeys(MayUseFullKeys, SessionID, Key, M);
          if (CmpRes = 0) then
           Pos := M
         until (CmpRes <> 0);
        break;
       end;
      if (Lb > Ub) then
       begin
         Pos := Lb;
         if (PositionType <> nil) then
          PositionType^ := kppBeforeKey;
         break;
       end;
    until False;
    Result := Pos;
   end;
end;// GetKeyPosition


//------------------------------------------------------------------------------
// InsertEntry
//------------------------------------------------------------------------------
procedure TABSBTreePageController.InsertEntry(
                  Key, Reference: TAbsPByte;
                  Position: Integer
                                              );
begin
  if (not CanAddEntry ) then
   EnlargePageBuffer;
  ABSMove(
           GetPKey(Position)^,
           GetPKey(Position+1)^,
           (FPage.EntryCount - Position) * FPage.EntrySize
         );
  FillChar(GetPKey(Position)^, FPage.KeyPrefixSize, #0);
  if (Key <> nil) then
   Move(Key^, GetPKey(Position)^, FPage.KeyPrefixSize);
  Move(Reference^, GetPReference(Position)^, FPage.ReferenceSize);
  FPage.EntryCount := FPage.EntryCount + 1;
end;// InsertEntry


//------------------------------------------------------------------------------
// DeleteEntry
//------------------------------------------------------------------------------
procedure TABSBTreePageController.DeleteEntry(Position: Integer);
begin
  if (FPage.EntryCount > 0) then
   begin
    ABSMove(
            GetPKey(Position+1)^,
            GetPKey(Position)^,
            (FPage.EntryCount-1 - Position) * FPage.EntrySize
           );
    FPage.EntryCount := FPage.EntryCount - 1;
   end
  else
   raise EABSException.Create(20025, ErrorABTreeEmptyPage);
end;// DeleteEntry


//------------------------------------------------------------------------------
// RootSplit
//------------------------------------------------------------------------------
procedure TABSBTreePageController.RootSplit(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
var
  MiddleEntryNo: Integer;
  LeftPage, RightPage: TABSBTreePage;
  LeftPageNo, RightPageNo: Integer;
begin
  FPage.AddIndexPage(SessionID, LeftPage);
  FPage.AddIndexPage(SessionID, RightPage);
  try
   MiddleEntryNo := FPage.EntryCount div 2;
   LeftPage.CopyFrom(FPage, 0, MiddleEntryNo);
   RightPage.CopyFrom(FPage, MiddleEntryNo, FPage.EntryCount-MiddleEntryNo);
   LeftPage.IsRoot := False;
   RightPage.IsRoot := False;
   LeftPage.RightPageNo := RightPage.PageNo;
   RightPage.LeftPageNo := LeftPage.PageNo;
   LeftPage.IsDirty := True;
   RightPage.IsDirty := True;

   FPage.IsLeaf := False;
   FPage.EntryCount := 0;
   LeftPageNo := LeftPage.PageNo;
   FPage.InsertNodeEntry(
            SessionID,
            nil,
            @LeftPageNo,
            KeyPath);
   LeftPage.PageNo := LeftPageNo;
   RightPageNo := RightPage.PageNo;
   FPage.InsertNodeEntry(
            SessionID,
            RightPage.GetPKey(0),
            @RightPageNo,
            KeyPath);
   RightPage.PageNo := RightPageNo;
   FPage.IsDirty := True;
  finally
   FPage.PutIndexPage(LeftPage);
   FPage.PutIndexPage(RightPage);
  end;
end;// RootSplit


//------------------------------------------------------------------------------
// NonRootSplit
//------------------------------------------------------------------------------
procedure TABSBTreePageController.NonRootSplit(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
var
  MiddleEntryNo: Integer;
  ParentPage, NewRightPage, PrevRightPage: TABSBTreePage;
  RightPageNo: Integer;
begin
  ParentPage := nil;
  PrevRightPage := nil;
  FPage.AddIndexPage(SessionID, NewRightPage);
  try
   MiddleEntryNo := FPage.EntryCount div 2;
   NewRightPage.CopyFrom(FPage, MiddleEntryNo, FPage.EntryCount-MiddleEntryNo);
   NewRightPage.RightPageNo := FPage.RightPageNo;
   NewRightPage.LeftPageNo := FPage.PageNo;
   NewRightPage.IsDirty := True;
   if (NewRightPage.RightPageNo <> INVALID_PAGE_NO) then
    begin
     FPage.GetIndexPage(SessionID, NewRightPage.RightPageNo, PrevRightPage);
     PrevRightPage.LeftPageNo := NewRightPage.PageNo;
     PrevRightPage.IsDirty := True;
    end;
   FPage.RightPageNo := NewRightPage.PageNo;
   FPage.EntryCount := MiddleEntryNo;
   FPage.IsDirty := True;

   KeyPath.DecLevel;
   FPage.GetIndexPage(SessionID, KeyPath.CurrentPageNo, ParentPage);
   RightPageNo := NewRightPage.PageNo;
   ParentPage.InsertNodeEntry(
            SessionID,
            NewRightPage.GetPKey(0),
            @RightPageNo,
            KeyPath);
   NewRightPage.PageNo := RightPageNo;
   ParentPage.IsDirty := True;
   KeyPath.IncLevel;
  finally
   if (NewRightPage <> nil) then
    FPage.PutIndexPage(NewRightPage);
   if (PrevRightPage <> nil) then
    FPage.PutIndexPage(PrevRightPage);
   if (ParentPage <> nil) then
    FPage.PutIndexPage(ParentPage);
  end;
end;// NonRootSplit


//------------------------------------------------------------------------------
// TryMergeWithPage
//------------------------------------------------------------------------------
function TABSBTreePageController.TryMergeWithPage(
                        SessionID:   TABSSessionID;
                        MergePageNo: TABSPageNo;
                        KeyPath:     TABSKeyPath
                                                  ): Boolean;
var
  MergePage: TABSBTreePage;
begin
  MergePage := nil;
  try
    FPage.GetIndexPage(SessionID, MergePageNo, MergePage);
    Result := CanMergeWithPage(MergePage);
    if (Result) then
     begin
       if (MergePageNo = FPage.LeftPageNo) then
        MergeWithLeftPage(SessionID, MergePage, KeyPath)
       else
        MergeWithRightPage(SessionID, MergePage, KeyPath);
       FPage.RemoveIndexPage(SessionID, FPage.PageNo);
     end;
  finally
   if (MergePage <> nil) then
    FPage.PutIndexPage(MergePage);
  end;
end;// TryMergeWithPage


//------------------------------------------------------------------------------
// TryMerge
//------------------------------------------------------------------------------
function TABSBTreePageController.TryMerge(SessionID: TABSSessionID; KeyPath: TABSKeyPath): Boolean;
begin
  Result := False;
  if (not FPage.IsRoot) then
   begin
     if (FPage.LeftPageNo <> INVALID_PAGE_NO) then
      Result := TryMergeWithPage(SessionID, FPage.LeftPageNo, KeyPath);
     if (not Result) then
      if (FPage.RightPageNo <> INVALID_PAGE_NO) then
       Result := TryMergeWithPage(SessionID, FPage.RightPageNo, KeyPath);
   end;
end;// TryMerge


//------------------------------------------------------------------------------
// MergeWithLeftPage
//------------------------------------------------------------------------------
procedure TABSBTreePageController.MergeWithLeftPage(
                        SessionID: TABSSessionID;
                        LeftPage: TABSBTreePage;
                        KeyPath: TABSKeyPath
                                );
var
  ParentPage: TABSBTreePage;
  RightPage:  TABSBTreePage;
  ChildPage:  TABSBTreePage;
begin
  ParentPage := nil;
  RightPage := nil;
  ChildPage := nil;
  try
    if (FPage.RightPageNo <> INVALID_PAGE_NO) then
     begin
       FPage.GetIndexPage(SessionID, FPage.RightPageNo, RightPage);
       RightPage.LeftPageNo := FPage.LeftPageNo;
       RightPage.IsDirty := True;
     end;

    KeyPath.DecLevel;
    FPage.GetIndexPage(SessionID, KeyPath.CurrentPageNo, ParentPage);
    if (not FPage.IsLeaf) then
      GetFirstKey(SessionID, GetPKey(0));
    LeftPage.AppendFrom(FPage, 0, FPage.EntryCount);
    LeftPage.RightPageNo := FPage.RightPageNo;
    LeftPage.IsDirty := True;
    ParentPage.DeleteNodeEntry(SessionID, KeyPath, True);
  finally
   if (ParentPage <> nil) then
    FPage.PutIndexPage(ParentPage);
   if (RightPage <> nil) then
    FPage.PutIndexPage(RightPage);
   if (ChildPage <> nil) then
    FPage.PutIndexPage(ChildPage);
  end;
end;// MergeWithLeftPage


//------------------------------------------------------------------------------
// MergeWithRightPage
//------------------------------------------------------------------------------
procedure TABSBTreePageController.MergeWithRightPage(
                        SessionID: TABSSessionID;
                        RightPage: TABSBTreePage;
                        KeyPath: TABSKeyPath
                                );
var
  ParentPage: TABSBTreePage;
  LeftPage:  TABSBTreePage;
begin
  ParentPage := nil;
  try
    if (FPage.LeftPageNo <> INVALID_PAGE_NO) then
     begin
       FPage.GetIndexPage(SessionID, FPage.LeftPageNo, LeftPage);
       LeftPage.RightPageNo := FPage.RightPageNo;
       LeftPage.IsDirty := True;
       FPage.PutIndexPage(LeftPage);
     end;

    KeyPath.DecLevel;
    FPage.GetIndexPage(SessionID, KeyPath.CurrentPageNo, ParentPage);
    if (not FPage.IsLeaf) then
      RightPage.GetFirstKey(SessionID, RightPage.GetPKey(0));
    RightPage.InsertFrom(FPage, 0, FPage.EntryCount);
    RightPage.LeftPageNo := FPage.LeftPageNo;
    RightPage.IsDirty := True;
    ParentPage.DeleteNodeEntry(SessionID, KeyPath, False);
  finally
   if (ParentPage <> nil) then
    FPage.PutIndexPage(ParentPage);
  end;
end;// MergeWithRightPage


//------------------------------------------------------------------------------
// constructor
//------------------------------------------------------------------------------
constructor TABSBTreePageController.Create(aPage: TABSBTreePage);
begin
  FPage := aPage;
end;// Create


//------------------------------------------------------------------------------
// GetPKey
//------------------------------------------------------------------------------
function TABSBTreePageController.GetPKey(KeyPosition: Integer): TAbsPByte;
begin
  Result := FPage.GetPKey(KeyPosition);
end;// GetPKey


//------------------------------------------------------------------------------
// GetPReference
//------------------------------------------------------------------------------
function TABSBTreePageController.GetPReference(RefPosition: Integer): TAbsPByte;
begin
  Result := FPage.GetPReference(RefPosition);
end;// GetPReference


//------------------------------------------------------------------------------
// Split
//------------------------------------------------------------------------------
procedure TABSBTreePageController.Split(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
begin
  if (FPage.IsRoot) then
   RootSplit(SessionID, KeyPath)
  else
   NonRootSplit(SessionID, KeyPath);
end;// Split




////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeLeafController
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// FindEntry
//------------------------------------------------------------------------------
function TABSBTreeLeafController.FindEntryOnPage(
                                           SessionID: TABSSessionID;
                                           Key, Reference: TAbsPByte;
                                           var EntryNo: Integer
                                          ): Boolean;
var
  Position: Integer;
  PositionType: TABSKeyPathPosition;
begin
  Result := False;
  EntryNo := -1;
  if (Key <> nil) then
    begin
      Position := GetKeyPosition(True, SessionID, Key, Reference,
                                 0, @PositionType, kstFirst);
      if (PositionType = kppOnKey) then
       begin
         repeat
           if (CompareReferences(Reference, Position) = 0) then
            begin
              EntryNo := Position;
              Result := True;
              break;
            end
           else
            Inc(Position);
           if (Position >= FPage.EntryCount) then
            break;
         until (CompareKeys(False, INVALID_SESSION_ID, Key, Position) <> 0);
       end;
    end
  else
   begin
     Position := 0;
     repeat
       if (CompareReferences(Reference, Position) = 0) then
        begin
          EntryNo := Position;
          Result := True;
          break;
        end
       else
        Inc(Position);
       if (Position >= FPage.EntryCount) then
        break;
     until (False);
   end;
end;// FindEntryOnPage


//------------------------------------------------------------------------------
// FindFirstByCondition
//------------------------------------------------------------------------------
function TABSBTreeLeafController.FindFirstByCondition(
                              SessionID: TABSSessionID;
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                            ): Boolean;
var
  PositionType: TABSKeyPathPosition;
  EntryNo:     Integer;
begin
  EntryNo := 0;
  Result := True;
  case Operator of
    scEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstFirst);
        if (PositionType = kppOnKey) then
          Result := True
        else
          Result := False;
      end;
    scLower:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstFirst);
        if ((PositionType = kppOnKey) or (PositionType = kppBeforeKey)) then
          Dec(EntryNo);
        if (EntryNo >= 0) then
          begin
            EntryNo := 0;
            Result := True;
          end
        else
          Result := False;
      end;
    scGreater:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstLast);
        if (PositionType = kppOnKey) then
          Inc(EntryNo);
        if (EntryNo < FPage.EntryCount) then
          Result := True
        else
          Result := False;
      end;
    scLowerEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstFirst);
        if (PositionType = kppBeforeKey) then
          Dec(EntryNo);
        if (EntryNo >= 0) then
          begin
            EntryNo := 0;
            Result := True;
          end
        else
          Result := False;
      end;
    scGreaterEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstFirst);
        if (EntryNo < FPage.EntryCount) then
          Result := True
        else
          Result := False;
      end;
  end;// case

  if (Result) then
    Position.AddItem(FPage.PageNo, EntryNo, FPage.EntryCount);
end;// FindFirstByCondition


//------------------------------------------------------------------------------
// FindLastByCondition
//------------------------------------------------------------------------------
function TABSBTreeLeafController.FindLastByCondition(
                              SessionID: TABSSessionID;
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                            ): Boolean;
var
  PositionType: TABSKeyPathPosition;
  EntryNo:     Integer;
begin
  EntryNo := 0;
  Result := False;
  case Operator of
    scNone:
      begin
        EntryNo := FPage.EntryCount-1;
        Result := True;
      end;
    scEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstLast);
        if (PositionType = kppOnKey) then
          Result := True
        else
          Result := False;
      end;
    scLower:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstFirst);
        if ((PositionType = kppOnKey) or (PositionType = kppBeforeKey)) then
          Dec(EntryNo);
        if (EntryNo >= 0) then
          Result := True
        else
          Result := False;
      end;
    scGreater:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstLast);
        if (PositionType = kppOnKey) then
          Inc(EntryNo);
        if (EntryNo < FPage.EntryCount) then
          begin
            EntryNo := FPage.EntryCount-1;
            Result := True;
          end
        else
          Result := False;
      end;
    scLowerEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstLast);
        if (PositionType = kppBeforeKey) then
          Dec(EntryNo);
        if (EntryNo >= 0) then
          Result := True
        else
          Result := False;
      end;
    scGreaterEqual:
      begin
        EntryNo := GetKeyPosition(True, SessionID, Key, nil, 0, @PositionType, kstAny);
        if (EntryNo < FPage.EntryCount) then
          begin
            EntryNo := FPage.EntryCount-1;
            Result := True;
          end
        else
          Result := False;
      end;
  end;// case

  if (Result) then
    Position.AddItem(FPage.PageNo, EntryNo, FPage.EntryCount);
end;// FindLastByCondition


//------------------------------------------------------------------------------
// Compare Entries (we assume that keys in entries are equal
// and we need to compare references only)
//------------------------------------------------------------------------------
function TABSBTreeLeafController.CompareEntries(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Reference1: TAbsPByte;
                          Entry2Index: Word): Integer;
begin
  Result := CompareReferences(Reference1, Entry2Index);
end;// CompareEntries


//------------------------------------------------------------------------------
// Add Leaf Entry (key, ref)
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.InsertLeafEntry(
                     SessionID: TABSSessionID;
                     Key, Reference: TAbsPByte;
                     KeyPath: TABSKeyPath
                                               );
var
  Pos: Word;
begin
  Pos := GetKeyPosition(True, SessionID, Key, Reference);
  InsertEntry(Key, Reference, Pos);
  if (not IsOverflow) then
    begin
      FPage.IsDirty := True;
      KeyPath.AddItem(FPage.PageNo, Pos, FPage.EntryCount);
    end
  else
    Split(SessionID, KeyPath);
end;// InsertLeafEntry


//------------------------------------------------------------------------------
// DeleteLeafEntry
//------------------------------------------------------------------------------
function TABSBTreeLeafController.DeleteLeafEntry(
                      SessionID: TABSSessionID;
                      Key, Reference: TAbsPByte;
                      KeyPath: TABSKeyPath
                                                ): Boolean;
var
  EntryNo: Integer;
begin
  if (FindEntryOnPage(SessionID, Key, Reference, EntryNo)) then
   begin
      DeleteEntry(EntryNo);
{      if (not CanUnderflow) then
       FPage.IsDirty := True
      else
       begin
        if (not TryMerge(SessionID, KeyPath)) then
          FPage.IsDirty := True;
       end;}
      // 4.86 bug fix: removed by merge page was dirty, but left in shared pages
      FPage.IsDirty := True;
      if (CanUnderflow) then
        TryMerge(SessionID, KeyPath);

      Result := True;
   end
  else
   Result := False;
end;// DeleteLeafEntry


//------------------------------------------------------------------------------
// GetFirstKey
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte);
begin
  Move(GetPKey(0)^, Key^, FPage.KeyPrefixSize);
end;// GetFirstKey


//------------------------------------------------------------------------------
// GetLastKey
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte);
begin
  Move(GetPKey(FPage.EntryCount-1)^, Key^, FPage.KeyPrefixSize);
end;// GetLastKey


//------------------------------------------------------------------------------
// GetFirstEntry
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.GetFirstEntry(SessionID: TABSSessionID;
                                                Key, Reference: TAbsPByte);
begin
  Move(GetPKey(0)^, Key^, FPage.KeyPrefixSize);
  Move(GetPReference(0)^, Reference^, FPage.LKeyRef.ReferenceSize);
end;// GetFirstEntry


//------------------------------------------------------------------------------
// GetLastEntry
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte);
begin
  Move(GetPKey(FPage.EntryCount-1)^, Key^, FPage.KeyPrefixSize);
  Move(GetPReference(FPage.EntryCount-1)^, Reference^, FPage.LKeyRef.ReferenceSize);
end;// GetLastEntry


//------------------------------------------------------------------------------
// FindEntry
//------------------------------------------------------------------------------
function TABSBTreeLeafController.FindEntry(
                    SessionID: TABSSessionID;
                    Key:       TAbsPByte;
                    Reference: TAbsPByte;
                    Position:  TABSKeyPath
                   ): Boolean;
var
  EntryNo: Integer;
begin
  Result := FindEntryOnPage(SessionID, Key, Reference, EntryNo);
  if (Result) then
   Position.AddItem(FPage.PageNo, EntryNo, FPage.EntryCount);
end;// FindEntry


//------------------------------------------------------------------------------
// GetFirstPosition
//------------------------------------------------------------------------------
function TABSBTreeLeafController.GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
begin
  Result := (FPage.EntryCount > 0);
  if (Result) then
    Position.AddItem(FPage.PageNo, 0, FPage.EntryCount);
end;// GetFirstPosition


//------------------------------------------------------------------------------
// GetLastPosition
//------------------------------------------------------------------------------
function TABSBTreeLeafController.GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
begin
  Result := (FPage.EntryCount > 0);
  if (Result) then
   Position.AddItem(FPage.PageNo, FPage.EntryCount-1, FPage.EntryCount);
end;// GetLastPosition


//------------------------------------------------------------------------------
// FindByCondition
//------------------------------------------------------------------------------
function TABSBTreeLeafController.FindByCondition(
                        SessionID: TABSSessionID;
                        First:     Boolean; // if False => Last
                        Key:       TAbsPByte;
                        Operator:  TABSSearchCondition;
                        Position:  TABSKeyPath
                                                ): Boolean;
begin
  if (First) then
    Result := FindFirstByCondition(SessionID, Key, Operator, Position)
  else
    Result := FindLastByCondition(SessionID, Key, Operator, Position);
end;// FindByCondition


//------------------------------------------------------------------------------
// FreeAllPages
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean);
begin
  if ((not FPage.IsRoot) or (not KeepRootPage)) then
    FPage.RemoveIndexPage(SessionID, FPage.PageNo);
end;// FreeAllPages


//------------------------------------------------------------------------------
// CheckIntegrity
//------------------------------------------------------------------------------
procedure TABSBTreeLeafController.CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
var
  i: Integer;
  res1, res2: integer;
  err: Boolean;
begin
  for i := 0 to FPage.EntryCount-2 do
   begin
    res1 := CompareKeys(False, INVALID_SESSION_ID, GetPKey(i), i+1);
    res2 := CompareReferences(GetPReference(i), i+1);
    if (FPage.LKeyRef.FShortKeySize = FPage.LKeyRef.FFullKeySize) then
      err := (res1 > 0) or ((res1 = 0) and (res2 >= 0))
    else
      err := (res1 > 0);

    if (err) then
     raise EABSException.Create(20028 ,ErrorAIndexIntegrityViolated, [FPage.PageNo, i]);
   end;
end;// CheckIntegrity



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeNodeController
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// FindByConditionOnOneOfPages
//------------------------------------------------------------------------------
function TABSBTreeNodeController.FindByConditionOnOneOfPages(
                                    SessionID:    TABSSessionID;
                                    First:        Boolean; // if False => Last
                                    StartEntryNo: Integer;
                                    EndEntryNo:   Integer;
                                    Key:          TAbsPByte;
                                    Operator:     TABSSearchCondition;
                                    Position:     TABSKeyPath
                                                      ): Boolean;
var
  Pos, Step, MinPos, MaxPos: Integer;
  ChildPage:                 TABSBTreePage;
begin
  Result := False;
  Pos := StartEntryNo;
  if (EndEntryNo >= StartEntryNo) then
   Step := 1
  else
   Step := -1;
  MinPos := Min(StartEntryNo, EndEntryNo);
  MaxPos := Max(StartEntryNo, EndEntryNo);
  while ((Pos >= MinPos) and (Pos <= MaxPos)) do
    begin
      FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(Pos))^, ChildPage);
      Position.AddItem(FPage.PageNo, Pos, FPage.EntryCount);
      Result := ChildPage.FindByCondition(SessionID, First, Key, Operator, Position);
      FPage.PutIndexPage(ChildPage);
      if (Result) then
        break
      else
        Position.DeleteLastItem;
      Pos := Pos + Step;
    end;
end;// FindByConditionOnOneOfPages


//------------------------------------------------------------------------------
// FindEntryOnOneOfPages
//------------------------------------------------------------------------------
function TABSBTreeNodeController.FindEntryOnOneOfPages(
                                    SessionID:    TABSSessionID;
                                    StartEntryNo: Integer;
                                    EndEntryNo:   Integer;
                                    Key:          TAbsPByte;
                                    Reference:    TAbsPByte;
                                    Position:     TABSKeyPath
                                  ): Boolean;
var
  Pos, Step, MinPos, MaxPos: Integer;
  ChildPage:                 TABSBTreePage;
begin
  Result := False;
  Pos := StartEntryNo;
  if (EndEntryNo >= StartEntryNo) then
   Step := 1
  else
   Step := -1;
  MinPos := Min(StartEntryNo, EndEntryNo);
  MaxPos := Max(StartEntryNo, EndEntryNo);
  while ((Pos >= MinPos) and (Pos <= MaxPos)) do
    begin
      FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(Pos))^, ChildPage);
      Position.AddItem(FPage.PageNo, Pos, FPage.EntryCount);
      Result := ChildPage.FindEntry(SessionID, Key, Reference, Position);
      FPage.PutIndexPage(ChildPage);
      if (Result) then
        break
      else
        Position.DeleteLastItem;
      Pos := Pos + Step;
    end;
end;// FindEntryOnOneOfPages


//------------------------------------------------------------------------------
// GetChildPagessToCheck
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.GetChildPagesToCheck(
                          SessionID:         TABSSessionID;
                          Key:               TAbsPByte;
                          SearchCondition:   TABSSearchCondition;
                          var StartEntryNo:  Integer;
                          var EndEntryNo:    Integer
                                                      );
var
  PositionType: TABSKeyPathPosition;
begin
  if (Key = nil) then
   begin
     StartEntryNo := 0;
     EndEntryNo := FPage.EntryCount-1;
   end
  else
    case SearchCondition of
      scEqual:
        begin
          StartEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstFirst);
          if (PositionType <> kppOnKey) then
           begin
             if (PositionType = kppBeforeKey) then
              Dec(StartEntryNo);
             EndEntryNo := StartEntryNo;
           end
          else
           begin
             Dec(StartEntryNo);
             if (StartEntryNo < 0) then
              StartEntryNo := 0;
             EndEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstLast);
           end;
        end;

      scLower:
        begin
          StartEntryNo := 0;
          EndEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstFirst);
          if ((PositionType = kppBeforeKey) or (PositionType = kppOnKey)) then
            Dec(EndEntryNo);
        end;

      scGreater:
        begin
          EndEntryNo := FPage.EntryCount-1;
          StartEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstLast);
          if (PositionType = kppBeforeKey) then
            Dec(StartEntryNo);
        end;

      scLowerEqual:
        begin
          StartEntryNo := 0;
          EndEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstLast);
          if (PositionType = kppBeforeKey) then
            Dec(EndEntryNo);
        end;

      scGreaterEqual:
        begin
          EndEntryNo := FPage.EntryCount-1;
          StartEntryNo := GetKeyPosition(False, SessionID, Key, nil, 1, @PositionType, kstFirst);
          if ((PositionType = kppBeforeKey) or (PositionType = kppOnKey)) then
            Dec(StartEntryNo);
        end;
    end;
end;// GetChildPagesToCheck


//------------------------------------------------------------------------------
// DecreaseTreeDepth
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.DecreaseTreeDepth(SessionID: TABSSessionID);
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(0))^, ChildPage);
  FPage.CopyFrom(ChildPage, 0, ChildPage.EntryCount);
  FPage.IsRoot := True;
  FPage.IsDirty := True;
  ChildPage.RemoveIndexPage(SessionID, ChildPage.PageNo);
  FPage.PutIndexPage(ChildPage);
end;// DecreaseTreeDepth


//------------------------------------------------------------------------------
// Compare Entry (Key, Ref) with first entry in Entry2 subtree
//------------------------------------------------------------------------------
function TABSBTreeNodeController.CompareEntries(MayUseFullKeys: Boolean;
                          SessionID: TABSSessionID;
                          Key1: TAbsPByte; Reference1: TAbsPByte;
                          Entry2Index: Word): Integer;
var
  Key2, Reference2: TAbsPByte;
  ChildPage: TABSBTreePage;
begin
  Key2 := MemoryManager.AllocMem(KeyRef.ShortKeySize);
  Reference2 := MemoryManager.AllocMem(KeyRef.ReferenceSize);
  try
    FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(Entry2Index))^, ChildPage);
    try
      ChildPage.GetFirstEntry(SessionID, Key2, Reference2);
    finally
      FPage.PutIndexPage(ChildPage);
    end;
    Result := KeyRef.CompareShortKeys(Key1, Key2, True,
                                      SessionID, Reference1, Reference2);// 4.88 bug fix
//                                      SessionID, nil, Reference2);
    if (Result = 0) then
      Result := KeyRef.CompareReferences(Reference1, Reference2, KeyRef.ReferenceSize);
  finally
    MemoryManager.FreeAndNillMem(Key2);
    MemoryManager.FreeAndNillMem(Reference2);
  end;
end;// CompareEntries


//------------------------------------------------------------------------------
// InsertLeafEntry
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.InsertLeafEntry(
                        SessionID: TABSSessionID;
                        Key, Reference: TAbsPByte;
                        KeyPath: TABSKeyPath
                                               );
var
  PositionType: TABSKeyPathPosition;
  Pos:          Word;
  ChildPage:    TABSBTreePage;
begin
  Pos := GetKeyPosition(False, SessionID, Key, Reference, 1, @PositionType);
  if (PositionType = kppBeforeKey) then
   Dec(Pos);
  KeyPath.AddItem(FPage.PageNo, Pos, FPage.EntryCount);
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(Pos))^, ChildPage);
  try
   ChildPage.InsertLeafEntry(SessionID, Key, Reference, KeyPath);
  finally
   FPage.PutIndexPage(ChildPage);
  end;
end;// InsertLeafEntry


//------------------------------------------------------------------------------
// InsertNodeEntry
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.InsertNodeEntry(
                        SessionID: TABSSessionID;
                        Key, Reference: TAbsPByte;
                        KeyPath: TABSKeyPath
                                               );
var
  Pos: Word;
begin
  if (FPage.EntryCount < 2) then
    Pos := FPage.EntryCount
  else
    Pos := KeyPath.Items[KeyPath.ItemNo].EntryNo+1;

  InsertEntry(Key, Reference, Pos);
  if (not IsOverflow) then
   FPage.IsDirty := True
  else
   Split(SessionID, KeyPath);
end;// InsertNodeEntry


//------------------------------------------------------------------------------
// DeleteLeafEntry
//------------------------------------------------------------------------------
function TABSBTreeNodeController.DeleteLeafEntry(
                        SessionID: TABSSessionID;
                        Key, Reference: TAbsPByte;
                        KeyPath: TABSKeyPath
                                                 ): Boolean;
var
  PositionType: TABSKeyPathPosition;
  Pos:          Word;
  ChildPage:    TABSBTreePage;
begin
  Pos := GetKeyPosition(False, SessionID, Key, Reference, 1, @PositionType);
  if (PositionType = kppBeforeKey) then
   Dec(Pos);
  KeyPath.AddItem(FPage.PageNo, Pos, FPage.EntryCount);
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(Pos))^, ChildPage);
  try
    Result := ChildPage.DeleteLeafEntry(SessionID, Key, Reference, KeyPath);
  finally
    FPage.PutIndexPage(ChildPage);
  end;
end;// DeleteLeafEntry


//------------------------------------------------------------------------------
// DeleteNodeEntry
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.DeleteNodeEntry(
                        SessionID:     TABSSessionID;
                        KeyPath:       TABSKeyPath;
                        MergeWithLeft: Boolean
                                                );
var
  ParentPage: TABSBTreePage;
  EntryNo:    Integer;
  CurLevel:   Integer;
begin
  if (MergeWithLeft) then
   begin
     CurLevel := KeyPath.ItemNo;
     while ((KeyPath.Items[CurLevel].EntryNo = 0) and
         (CurLevel > 0)) do
      begin
        Dec(CurLevel);
        if (KeyPath.Items[CurLevel].EntryNo > 0) then
         begin
          FPage.GetIndexPage(SessionID, KeyPath.Items[CurLevel].PageNo, ParentPage);
          ParentPage.UpdateKey(
                          KeyPath.Items[CurLevel].EntryNo,
                          GetPKey(1));
          ParentPage.IsDirty := True;
          FPage.PutIndexPage(ParentPage);
          break;
         end;
      end;
   end
  else
   begin
     CurLevel := KeyPath.ItemNo;
     while (CurLevel >= 0) do
       begin
        if (KeyPath.Items[CurLevel].EntryNo = KeyPath.Items[CurLevel].EntryCount-1) then
          Dec(CurLevel);
        if (CurLevel >= 0) then
          if (KeyPath.Items[CurLevel].EntryNo <
              KeyPath.Items[CurLevel].EntryCount-1) then
            begin
              EntryNo := KeyPath.Items[CurLevel].EntryNo+1;
              FPage.GetIndexPage(SessionID, KeyPath.Items[CurLevel].PageNo, ParentPage);
              ParentPage.UpdateKey(
                                   EntryNo,
                                   GetPKey(KeyPath.Items[KeyPath.ItemNo].EntryNo));
              ParentPage.IsDirty := True;
              FPage.PutIndexPage(ParentPage);
              break;
            end;
       end;
   end;
  DeleteEntry(KeyPath.Items[KeyPath.ItemNo].EntryNo);
  FPage.IsDirty := True;
  if (CanUnderflow) then
    if (not TryMerge(SessionID, KeyPath)) then
      if (FPage.IsRoot) then
        if (FPage.EntryCount = 1) then
          DecreaseTreeDepth(SessionID);
end;// DeleteNodeEntry


//------------------------------------------------------------------------------
// GetFirstKey
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.GetFirstKey(SessionID: TABSSessionID; Key: TAbsPByte);
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(0))^, ChildPage);
  ChildPage.GetFirstKey(SessionID, Key);
  FPage.PutIndexPage(ChildPage);
end;// GetFirstKey


//------------------------------------------------------------------------------
// GetLastKey
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.GetLastKey(SessionID: TABSSessionID; Key: TAbsPByte);
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(FPage.EntryCount-1))^, ChildPage);
  ChildPage.GetLastKey(SessionID, Key);
  FPage.PutIndexPage(ChildPage);
end;// GetLastKey


//------------------------------------------------------------------------------
// GetFirstEntry
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.GetFirstEntry(SessionID: TABSSessionID;
                                                Key, Reference: TAbsPByte);
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(0))^, ChildPage);
  ChildPage.GetFirstEntry(SessionID, Key, Reference);
  FPage.PutIndexPage(ChildPage);
end;// GetFirstEntry


//------------------------------------------------------------------------------
// GetLastEntry
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.GetLastEntry(SessionID: TABSSessionID; Key, Reference: TAbsPByte);
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(FPage.EntryCount-1))^, ChildPage);
  ChildPage.GetLastEntry(SessionID, Key, Reference);
  FPage.PutIndexPage(ChildPage);
end;// GetLastEntry


//------------------------------------------------------------------------------
// FindEntry
//------------------------------------------------------------------------------
function TABSBTreeNodeController.FindEntry(
                          SessionID: TABSSessionID;
                          Key:       TAbsPByte;
                          Reference: TAbsPByte;
                          Position:  TABSKeyPath
                         ): Boolean;
var
  StartEntryNo, EndEntryNo: Integer;
begin
  GetChildPagesToCheck(SessionID, Key, scEqual, StartEntryNo, EndEntryNo);
  Result := FindEntryOnOneOfPages(SessionID, StartEntryNo, EndEntryNo, Key, Reference, Position);
end;// FindEntry


//------------------------------------------------------------------------------
// GetFirstPosition
//------------------------------------------------------------------------------
function TABSBTreeNodeController.GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(0))^, ChildPage);
  try
   Position.AddItem(FPage.PageNo, 0, FPage.EntryCount);
   Result := ChildPage.GetFirstPosition(SessionID, Position);
  finally
   FPage.PutIndexPage(ChildPage);
  end;
end;// GetFirstPosition


//------------------------------------------------------------------------------
// GetLastPosition
//------------------------------------------------------------------------------
function TABSBTreeNodeController.GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  ChildPage: TABSBTreePage;
begin
  FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(FPage.EntryCount-1))^, ChildPage);
  try
   Position.AddItem(FPage.PageNo, FPage.EntryCount-1, FPage.EntryCount);
   Result := ChildPage.GetLastPosition(SessionID, Position);
  finally
   FPage.PutIndexPage(ChildPage);
  end;
end;// GetLastPosition


//------------------------------------------------------------------------------
// FindByCondition
//------------------------------------------------------------------------------
function TABSBTreeNodeController.FindByCondition(
                              SessionID: TABSSessionID;
                              First:     Boolean; // if False => Last
                              Key:       TAbsPByte;
                              Operator:  TABSSearchCondition;
                              Position:  TABSKeyPath
                             ): Boolean;
var
  StartEntryNo, EndEntryNo: Integer;
begin
  GetChildPagesToCheck(SessionID, Key, Operator, StartEntryNo, EndEntryNo);
  if (First) then
    Result := FindByConditionOnOneOfPages(SessionID, First, StartEntryNo, EndEntryNo, Key, Operator, Position)
  else
    Result := FindByConditionOnOneOfPages(SessionID, First, EndEntryNo, StartEntryNo, Key, Operator, Position);
end;// FindByCondition


//------------------------------------------------------------------------------
// FreeAllPages
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.FreeAllPages(SessionID: TABSSessionID; KeepRootPage: Boolean);
var
  i: Integer;
  ChildPage: TABSBTreePage;
begin
  if (FPage.PageNo <> INVALID_PAGE_NO) then
   begin
     for i := 0 to FPage.EntryCount-1 do
       begin
         FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(i))^, ChildPage);
         ChildPage.FreeAllPages(SessionID, KeepRootPage);
         FPage.PutIndexPage(ChildPage);
       end;
     if ((not FPage.IsRoot) or (not KeepRootPage))  then
       FPage.RemoveIndexPage(SessionID, FPage.PageNo);
   end;
end;// FreeAllPages


//------------------------------------------------------------------------------
// CheckIntegrity
//------------------------------------------------------------------------------
procedure TABSBTreeNodeController.CheckIntegrity(SessionID: TABSSessionID; KeyPath: TABSKeyPath);
var
  i:         Integer;
  ChildPage: TABSBTreePage;
  KeyBuffer: TAbsPByte;
  KeyBuffer2: TAbsPByte;
  Ref1, Ref2: TABSRecordID;
begin
  KeyBuffer := KeyRef.AllocShortKeyBuffer;
  KeyBuffer2 := KeyRef.AllocShortKeyBuffer;
  try
    for i := 0 to FPage.EntryCount-1 do
     begin
       if (KeyPath.PageExists(FPage.PageNo)) then
        raise EABSException.Create(20032 ,ErrorAIndexIntegrityCircularLinks, [FPage.PageNo, i]);

       KeyPath.AddItem(FPage.PageNo, i, FPage.EntryCount);
       FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(i))^, ChildPage);
       if (i > 0) then
        if (ChildPage.LeftPageNo <> PABSPageNo(GetPReference(i-1))^) then
         raise EABSException.Create(20033, ErrorAIndexIntegrityLeafLinks, [FPage.PageNo, i]);
       if (i < FPage.EntryCount-1) then
        if (ChildPage.RightPageNo <> PABSPageNo(GetPReference(i+1))^) then
         raise EABSException.Create(20034, ErrorAIndexIntegrityLeafLinks, [FPage.PageNo, i]);

       ChildPage.CheckIntegrity(SessionID, KeyPath);
       FPage.PutIndexPage(ChildPage);
       KeyPath.DeleteLastItem;
     end;
    for i := 1 to FPage.EntryCount-2 do
     begin
       if (CompareKeys(False, INVALID_SESSION_ID, GetPKey(i), i+1) > 0) then
        raise EABSException.Create(20029 ,ErrorAIndexIntegrityViolated, [FPage.PageNo, i]);

       FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(i-1))^, ChildPage);
       ChildPage.GetLastEntry(SessionID, KeyBuffer, @Ref1);
       if (CompareKeys(False, INVALID_SESSION_ID, KeyBuffer, i) > 0) then
        raise EABSException.Create(20030 ,ErrorAIndexIntegrityViolated, [FPage.PageNo, i]);
       FPage.PutIndexPage(ChildPage);

       FPage.GetIndexPage(SessionID, PABSPageNo(GetPReference(i+1))^, ChildPage);
       ChildPage.GetFirstEntry(SessionID, KeyBuffer2, @Ref2);
       if (CompareKeys(False, INVALID_SESSION_ID, KeyBuffer2, i+1) < 0) then
        raise EABSException.Create(20031 ,ErrorAIndexIntegrityViolated, [FPage.PageNo, i]);
       FPage.PutIndexPage(ChildPage);

       if (FPage.LKeyRef.ShortKeySize = FPage.LKeyRef.FullKeySize) then
        if (FPage.LKeyRef.CompareShortKeys(KeyBuffer, KeyBuffer2) = 0) then
          if (FPage.LKeyRef.CompareReferences(@Ref1, @Ref2, sizeof(TABSRecordID)) >= 0) then
            raise EABSException.Create(20194, ErrorAIndexIntegrityViolated, [FPage.PageNo, i]);

     end;
  finally
    KeyRef.FreeAndNilKeyBuffer(KeyBuffer);
    KeyRef.FreeAndNilKeyBuffer(KeyBuffer2);
  end;
end;// CheckIntegrity


////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeRecordIndex
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// AddIndexPage
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.AddIndexPage(SessionID: TABSSessionID): TABSBTreePage;
var
  PageManager: TABSPageManager;
begin
  PageManager := IndexManager.GetPageManager(Self);
  Result := TABSBTreePage.Create(PageManager, FKeyRef);
  try
    Result.Page := PageManager.AddPage(SessionID, ptTableIndex);
  except
    Result.Free;
    raise;
  end;
end;// AddIndexPage


//------------------------------------------------------------------------------
// GetIndexPage
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo): TABSBTreePage;
var
  PageManager: TABSPageManager;
begin
  PageManager := IndexManager.GetPageManager(Self);
  Result := TABSBTreePage.Create(PageManager, FKeyRef);
  try
   Result.Page := PageManager.GetPage(SessionID, PageNo, ptTableIndex);
  except
    Result.Free;
    raise;
  end;
end;// GetIndexPage


//------------------------------------------------------------------------------
// PutIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.PutIndexPage(Page: TABSBTreePage);
begin
  IndexManager.GetPageManager(Self).PutPage(Page.Page);
  Page.Free;
end;// PutIndexPage


//------------------------------------------------------------------------------
// GetRecordID
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetRecordID(SessionID: TABSSessionID; Position: TABSKeyPath): TABSRecordID;
var
  Page: TABSBTreePage;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20068, ErrorABTreeInvalidPosition);
  Page := GetIndexPage(SessionID, Position.Items[Position.Count-1].PageNo);
  try
    Move(
      Page.GetPReference(Position.Items[Position.Count-1].EntryNo)^,
      Result,
      Page.ReferenceSize
        );
  finally
    PutIndexPage(Page);
  end;
end;// GetRecordID


//------------------------------------------------------------------------------
// GetFirstPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  Page: TABSBTreePage;
begin
  if (IndexDef.RootPageNo <> INVALID_PAGE_NO) then
    begin
      Position.Clear;
      Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
      try
        Result := Page.GetFirstPosition(SessionID, Position);
      finally
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20121, ErrorAInvalidPageNo);
end;// GetFirstPosition


//------------------------------------------------------------------------------
// GetLastPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  Page: TABSBTreePage;
begin
  if (IndexDef.RootPageNo <> INVALID_PAGE_NO) then
    begin
      Position.Clear;
      Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
      try
        Result := Page.GetLastPosition(SessionID, Position);
      finally
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20122, ErrorAInvalidPageNo);
end;// GetLastPosition


//------------------------------------------------------------------------------
// GetNextPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetNextPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  i:            Integer;
  CurrentLevel: Integer;
  Page:         TABSBTreePage;
  NextPageNo:   TABSPageNo;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20069, ErrorABTreeInvalidPosition);
  CurrentLevel := Position.Count-1;
  Result := False;

  repeat
    if (Position.Items[CurrentLevel].EntryNo <
        Position.Items[CurrentLevel].EntryCount-1) then
     begin
      Inc(Position.Items[CurrentLevel].EntryNo);
      Result := True;
      break;
     end
    else
     Dec(CurrentLevel);
  until (CurrentLevel < 0);

  if (Result) then
    for i := CurrentLevel+1 to Position.Count-1 do
      begin
        Page := GetIndexPage(SessionID, Position.Items[i].PageNo);
        NextPageNo := Page.RightPageNo;
        PutIndexPage(Page);
        if (NextPageNo = INVALID_PAGE_NO) then
          raise EABSException.Create(20070, ErrorABTreeInvalidPage);
        Page := GetIndexPage(SessionID, NextPageNo);
        try
          Position.Items[i].PageNo := NextPageNo;
          Position.Items[i].EntryNo := 0;
          Position.Items[i].EntryCount := Page.EntryCount;
        finally
          PutIndexPage(Page);
        end;
      end;
end;// GetNextPosition


//------------------------------------------------------------------------------
// GetPriorPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetPriorPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  i:            Integer;
  CurrentLevel: Integer;
  Page:         TABSBTreePage;
  PriorPageNo:   TABSPageNo;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20069, ErrorABTreeInvalidPosition);
  CurrentLevel := Position.Count-1;
  Result := False;

  repeat
    if (Position.Items[CurrentLevel].EntryNo > 0) then
     begin
      Dec(Position.Items[CurrentLevel].EntryNo);
      Result := True;
      break;
     end
    else
     Dec(CurrentLevel);
  until (CurrentLevel < 0);

  if (Result) then
    for i := CurrentLevel+1 to Position.Count-1 do
      begin
        Page := GetIndexPage(SessionID, Position.Items[i].PageNo);
        PriorPageNo := Page.LeftPageNo;
        PutIndexPage(Page);
        if (PriorPageNo = INVALID_PAGE_NO) then
          raise EABSException.Create(20071, ErrorABTreeInvalidPage);
        Page := GetIndexPage(SessionID, PriorPageNo);
        try
          Position.Items[i].PageNo := PriorPageNo;
          Position.Items[i].EntryNo := Page.EntryCount-1;
          Position.Items[i].EntryCount := Page.EntryCount;
        finally
          PutIndexPage(Page);
        end;
      end;
end;// GetPriorPosition


//------------------------------------------------------------------------------
// GetPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetPosition(SessionID: TABSSessionID; Restart, GoForward: Boolean; Position: TABSKeyPath): Boolean;
begin
  if (Restart) then
    if (GoForward) then
      Result := GetFirstPosition(SessionID, Position)
    else
      Result := GetLastPosition(SessionID, Position)
  else
    if (GoForward) then
      Result := GetNextPosition(SessionID, Position)
    else
      Result := GetPriorPosition(SessionID, Position);
end;// GetPosition


//------------------------------------------------------------------------------
// create
//------------------------------------------------------------------------------
constructor TABSBTreeRecordIndex.Create(aIndexManager: TABSBaseIndexManager);
begin
  inherited Create(aIndexManager);
  FRootPage := nil;
  FKeyRef := nil;
end;// Create


//------------------------------------------------------------------------------
// destroy
//------------------------------------------------------------------------------
destructor TABSBTreeRecordIndex.Destroy;
begin
  if (FKeyRef <> nil) then
   FKeyRef.Free;
  inherited Destroy;
end;// Destroy


//------------------------------------------------------------------------------
// create index
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.CreateIndex(Cursor: TABSCursor; aIndexDef: TABSIndexDef);
var
  RecordBuffer:   TABSRecordBuffer;
  TmpCursor:      TABSLocalCursor;
begin
  inherited CreateIndex(Cursor, aIndexDef);

  FKeyRef := TABSRecordKeyRef.Create;
  FKeyRef.Assign(IndexDef, IndexManager.TableData);
  FKeyRef.ReferenceSize := sizeof(TABSRecordID);

  if (Cursor <> nil) then
    FRootPage := AddIndexPage(Cursor.Session.SessionID)
  else
    FRootPage := AddIndexPage(SYSTEM_SESSION_ID);
  FRootPage.InitAsRoot;
  FRootPage.IsDirty := True;
  aIndexDef.RootPageNo := FRootPage.PageNo;
  IndexDef.RootPageNo := aIndexDef.RootPageNo;
  PutIndexPage(FRootPage);
  if (Cursor <> nil) then
   begin
    TmpCursor := TABSLocalCursor.Create;
    TmpCursor.Session := Cursor.Session;
    TmpCursor.TableName := Cursor.TableName;
    try
     TABSLocalCursor(TmpCursor).OpenTable(IndexManager.TableData);

     TmpCursor.CurrentRecordBuffer := TmpCursor.AllocateRecordBuffer;
     while (TmpCursor.GetRecordBuffer(grmNext) = grrOK) do
       InsertRecord(TmpCursor);
    finally
     RecordBuffer := TmpCursor.CurrentRecordBuffer;
     TmpCursor.FreeRecordBuffer(RecordBuffer);
     TmpCursor.CurrentRecordBuffer := nil;
     TmpCursor.Free;
    end;
   end;
end;// CreateIndex


//------------------------------------------------------------------------------
// DropIndex
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.DropIndex(SessionID: TABSSessionID);
begin
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20119, ErrorAInvalidPageNo);
  FRootPage := GetIndexPage(SessionID, IndexDef.RootPageNo);
  try
    FRootPage.FreeAllPages(SessionID, False);
  finally
    PutIndexPage(FRootPage);
  end;
end;// DropIndex


//------------------------------------------------------------------------------
// EmptyIndex
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.EmptyIndex(SessionID: TABSSessionID);
begin
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20120, ErrorAInvalidPageNo);
  FRootPage := GetIndexPage(SessionID, IndexDef.RootPageNo);
  try
    FRootPage.FreeAllPages(SessionID, True);
    FRootPage.InitAsRoot;
    FRootPage.IsDirty := True;
  finally
    PutIndexPage(FRootPage);
  end;
end;// EmptyIndex


//------------------------------------------------------------------------------
// open index
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.OpenIndex(aIndexDef: TABSIndexDef);
begin
  inherited OpenIndex(aIndexDef);

  FKeyRef := TABSRecordKeyRef.Create;
  FKeyRef.Assign(IndexDef, IndexManager.TableData);
  FKeyRef.ReferenceSize := sizeof(TABSRecordID);
end;// OpenIndex


//------------------------------------------------------------------------------
// RebuildTemporaryIndex
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.RebuildTemporaryIndex(Cursor: TABSCursor);
begin
  DropIndex(Cursor.Session.SessionID);
  CreateIndex(Cursor, FIndexDef);
end;// RebuildTemporaryIndex


//------------------------------------------------------------------------------
// GetRecordBuffer
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.GetRecordBuffer(
                               SessionID:          TABSSessionID;
                               var NavigationInfo: TABSNavigationInfo;
                               IndexPositionCache: TABSIndexPositionCache;
                               TableState:         Integer
                                         );
var
  KeyPath:            TABSKeyPath;
  Res1:               Boolean;
  Res2:               Boolean;
  GetRecordMode:      TABSGetRecordMode;
begin
  if (NavigationInfo.GetRecordMode = grmCurrent) then
   raise EABSException.Create(20053, ErrorAInvalidIndexGetRecordMode);
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20123, ErrorAInvalidPageNo);
  KeyPath := TABSKeyPath.Create;
  try
    Res2 := True;
    if (NavigationInfo.FirstPosition) then
      Res1 := GetFirstPosition(SessionID, KeyPath)
    else
     if (NavigationInfo.LastPosition) then
      Res1 := GetLastPosition(SessionID, KeyPath)
     else
      begin
       // use cached index position?
       if ((IndexPositionCache <> nil) and
           (IndexPositionCache.IndexID = FIndexDef.ObjectID) and
           (IndexPositionCache.RecordID.PageNo = NavigationInfo.RecordID.PageNo) and
           (IndexPositionCache.RecordID.PageItemNo = NavigationInfo.RecordID.PageItemNo) and
           (IndexPositionCache.TableState = TableState)) then
         begin
           Res1 := True;
           KeyPath.Assign(IndexPositionCache.Position);
         end
       else
        Res1 := GetIndexPosition(
                              SessionID,
                              NavigationInfo.RecordID,
                              NavigationInfo.RecordBuffer,
                              KeyPath
                             );
       if (Res1) then
        if (NavigationInfo.GetRecordMode = grmNext) then
          Res2 := GetNextPosition(SessionID, KeyPath)
        else
        if (NavigationInfo.GetRecordMode = grmPrior) then
          Res2 := GetPriorPosition(SessionID, KeyPath)
        else
          Res2 := True;
      end;

    if (not Res1) then
     NavigationInfo.GetRecordResult := grrError
    else
      if (not Res2) then
       if (NavigationInfo.GetRecordMode = grmNext) then
        begin
          NavigationInfo.GetRecordResult := grrEOF;
          NavigationInfo.FirstPosition := False;
          NavigationInfo.LastPosition := True;
        end
       else
        begin
          NavigationInfo.GetRecordResult := grrBOF;
          NavigationInfo.FirstPosition := True;
          NavigationInfo.LastPosition := False;
        end
      else
       begin
         NavigationInfo.GetRecordResult := grrOK;
         NavigationInfo.FirstPosition := False;
         NavigationInfo.LastPosition := False;
         NavigationInfo.RecordID := GetRecordID(SessionID, KeyPath);
         GetRecordMode := NavigationInfo.GetRecordMode;
         NavigationInfo.GetRecordMode := grmCurrent;
         IndexManager.TableData.
             RecordManager.GetRecordBuffer(SessionID, NavigationInfo);
         NavigationInfo.GetRecordMode := GetRecordMode;
         // fill position cache
         if (IndexPositionCache <> nil) then
           begin
             IndexPositionCache.IndexID := FIndexDef.ObjectID;
             IndexPositionCache.TableState := TableState;
             IndexPositionCache.RecordID := NavigationInfo.RecordID;
             TABSKeyPath(IndexPositionCache.Position).Assign(KeyPath);
           end;
       end;
  finally
    KeyPath.Free;
  end;
end;// GetRecordBuffer


//------------------------------------------------------------------------------
// GetClosestRecordBuffer
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.GetClosestRecordBuffer(
                        SessionID:          TABSSessionID;
                        var NavigationInfo: TABSNavigationInfo;
                        IndexPositionCache: TABSIndexPositionCache;
                        TableState:         Integer);
var
  KeyBuffer:             TAbsPByte;
  KeyPath:               TABSKeyPath;
  GetRecordMode:         TABSGetRecordMode;
  bFound:                Boolean;
  Operator:              TABSSearchCondition;
begin
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20293, ErrorAInvalidPageNo);
  KeyBuffer := FKeyRef.AllocShortKeyBuffer;
  KeyPath := TABSKeyPath.Create;
  FRootPage := nil;
  try
    FRootPage := GetIndexPage(SessionID, IndexDef.RootPageNo);
    FKeyRef.MakeShortKeyFromRecordBuffer(NavigationInfo.RecordBuffer, KeyBuffer);
    if (NavigationInfo.GetRecordMode = grmNext) then
      Operator := scGreater
    else
      Operator := scLower;
    bFound := FRootPage.FindByCondition(SessionID,(NavigationInfo.GetRecordMode=grmNext), KeyBuffer, Operator, KeyPath);
    if (bFound) then
      begin
         NavigationInfo.GetRecordResult := grrOK;
         NavigationInfo.FirstPosition := False;
         NavigationInfo.LastPosition := False;
         NavigationInfo.RecordID := GetRecordID(SessionID, KeyPath);
         GetRecordMode := NavigationInfo.GetRecordMode;
         NavigationInfo.GetRecordMode := grmCurrent;
         IndexManager.TableData.
             RecordManager.GetRecordBuffer(SessionID, NavigationInfo);
         NavigationInfo.GetRecordMode := GetRecordMode;
         // fill position cache
         if (IndexPositionCache <> nil) then
           begin
             IndexPositionCache.IndexID := FIndexDef.ObjectID;
             IndexPositionCache.TableState := TableState;
             IndexPositionCache.RecordID := NavigationInfo.RecordID;
             TABSKeyPath(IndexPositionCache.Position).Assign(KeyPath);
           end;
      end
    else
      if (NavigationInfo.GetRecordMode = grmNext) then
        begin
          NavigationInfo.GetRecordResult := grrEOF;
          NavigationInfo.FirstPosition := False;
          NavigationInfo.LastPosition := True;
        end
      else
        begin
          NavigationInfo.GetRecordResult := grrBOF;
          NavigationInfo.FirstPosition := True;
          NavigationInfo.LastPosition := False;
        end;
  finally
    if (FRootPage <> nil) then
      PutIndexPage(FRootPage);
    KeyPath.Free;
    FKeyRef.FreeAndNilKeyBuffer(KeyBuffer);
  end;
end;// GetClosestRecordBuffer


//------------------------------------------------------------------------------
// CreateIndexPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CreateIndexPosition: TABSIndexPosition;
begin
  Result := TABSKeyPath.Create;
end;// CreateIndexPosition


//------------------------------------------------------------------------------
// FreeIndexPosition
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.FreeIndexPosition(var IndexPosition: TABSIndexPosition);
begin
  if (IndexPosition <> nil) then
   TABSKeyPath(IndexPosition).Free;
  IndexPosition := nil;
end;// FreeIndexPosition


//------------------------------------------------------------------------------
// GetIndexPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetIndexPosition(
                                         SessionID:     TABSSessionID;
                                         RecordID:      TABSRecordID;
                                         RecordBuffer:  TABSRecordBuffer;
                                         IndexPosition: TABSIndexPosition
                                        ): Boolean;
var
  Page:       TABSBTreePage;
  KeyBuffer:  TAbsPByte;
begin
  if (IndexDef.RootPageNo <> INVALID_PAGE_NO) then
    begin
      TABSKeyPath(IndexPosition).Clear;
      Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
      KeyBuffer := FKeyRef.AllocShortKeyBuffer;
      try
        FKeyRef.MakeShortKeyFromRecordBuffer(RecordBuffer, KeyBuffer);
        Result := Page.FindEntry(SessionID, KeyBuffer, @RecordID, TABSKeyPath(IndexPosition));
      finally
        FKeyRef.FreeAndNilKeyBuffer(KeyBuffer);
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20124, ErrorAInvalidPageNo);
end;// GetIndexPosition


//------------------------------------------------------------------------------
// return 0, 1, -1 if (Pos1 = Pos2), (Pos1 > Pos2), (Pos1 < Pos2)
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CompareRecordPositionsInIndex(
                    RecordPosition1: TABSIndexPosition;
                    RecordPosition2: TABSIndexPosition
                                      ): Integer;
begin
 if (RecordPosition1 = nil) then
   raise EABSException.Create(10384,ErrorLNilPointer);
 if (RecordPosition2 = nil) then
   raise EABSException.Create(10385,ErrorLNilPointer);
 Result := TABSKeyPath(RecordPosition1).Compare(TABSKeyPath(RecordPosition2));
end; // CompareRecordPositionsInIndex


//------------------------------------------------------------------------------
// GetRecNoByRecordID
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetRecNoByRecordID(
                                SessionID:      TABSSessionID;
                                RecordID:       TABSRecordID;
                                RecordBuffer:   TABSRecordBuffer
                               ): TABSRecordNo;
var
  Position:       TABSKeyPath;
  ScanPage:       TABSBTreePage;
  ScanPageNo:     TABSPageNo;
  ScanEntryCount: Integer;
begin
  Position := TABSKeyPath.Create;
  try
    if (not GetIndexPosition(SessionID, RecordID, RecordBuffer, Position)) then
     Result := -1
    else
     begin
       Result := 0;
       ScanPageNo := Position.Items[Position.Count-1].PageNo;
       while (ScanPageNo <> INVALID_PAGE_NO) do
        begin
          ScanPage := GetIndexPage(SessionID, ScanPageNo);
          try
            if (ScanPage.PageNo <> Position.Items[Position.Count-1].PageNo) then
             ScanEntryCount := ScanPage.EntryCount
            else
             ScanEntryCount := Position.Items[Position.Count-1].EntryNo+1;
            Inc(Result, ScanEntryCount);
            ScanPageNo := ScanPage.LeftPageNo;
          finally
           PutIndexPage(ScanPage);
          end;
        end;
     end;
  finally
    Position.Free;
  end;
end;// GetRecNoByRecordID


//------------------------------------------------------------------------------
// GetRecordIDByRecNo
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetRecordIDByRecNo(
                                SessionID:      TABSSessionID;
                                RecNo:          TABSRecordNo
                               ): TABSRecordID;
var
  Position:       TABSKeyPath;
  ScanPage:       TABSBTreePage;
  ScanPageNo:     TABSPageNo;
  RecNoCounter:   TABSRecordNo;
  Found:          Boolean;
begin
  Position := TABSKeyPath.Create;
  try
    if (not GetFirstPosition(SessionID, Position)) then
     raise EABSException.Create(20074, ErrorACannotRetreiveRecordFromEmptyIndex)
    else
     begin
       RecNoCounter := 0;
       ScanPageNo := Position.Items[Position.Count-1].PageNo;
       Found := False;
       while ((ScanPageNo <> INVALID_PAGE_NO) and (not Found)) do
        begin
          ScanPage := GetIndexPage(SessionID, ScanPageNo);
          try
            if (RecNoCounter + ScanPage.EntryCount < RecNo) then
              Inc(RecNoCounter, ScanPage.EntryCount)
            else
              begin
                Found := True;
                Move(
                     ScanPage.GetPReference(RecNo-1-RecNoCounter)^,
                     Result,
                     ScanPage.ReferenceSize
                    );
                break;
              end;
            ScanPageNo := ScanPage.RightPageNo;
          finally
           PutIndexPage(ScanPage);
          end;
        end;
       if (not Found) then
        raise EABSException.Create(20075, ErrorACannotSetRecNoGreaterThanRecordCount);
     end;
  finally
    Position.Free;
  end;
end;// GetRecordIDByRecNo


//------------------------------------------------------------------------------
// ApplyDistinctToRecordBitmap
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.ApplyDistinctToRecordBitmap(
                                SessionID:      TABSSessionID;
                                Bitmap:         TABSRecordBitmap;
                                DistinctFieldCount: Integer
                                                    );
var
  Position:       TABSKeyPath;
  Key:            TAbsPByte;
  RecordID:       TABSRecordID;
  ScanPage:       TABSBTreePage;
  ScanPageNo:     TABSPageNo;
  i:              Integer;
  OldCompareFieldCount: Integer;
begin
  if (Bitmap = nil) then
    raise EABSException.Create(20076, ErrorANilPointer);

  Position := TABSKeyPath.Create;
  Key := nil;
  OldCompareFieldCount := KeyRef.CompareFieldCount;
  try
    KeyRef.CompareFieldCount := DistinctFieldCount;
    if (GetFirstPosition(SessionID, Position)) then
     begin
       ScanPageNo := Position.Items[Position.Count-1].PageNo;
       while (ScanPageNo <> INVALID_PAGE_NO) do
        begin
          ScanPage := GetIndexPage(SessionID, ScanPageNo);
          try
           for i := 0 to ScanPage.EntryCount-1 do
             begin
              if (Bitmap.IsRecordVisible(IndexDef.ObjectID, Position)) then
                begin
                  if (Key = nil) then
                   begin
                     Key := KeyRef.AllocShortKeyBuffer;
                     Move(ScanPage.GetPKey(i)^, Key^, KeyRef.ShortKeySize);
                     Move(ScanPage.GetPReference(i)^, RecordID, KeyRef.ReferenceSize);
                   end
                  else
                   if (KeyRef.CompareShortKeys(ScanPage.GetPKey(i), Key, True,
                        SessionID, ScanPage.GetPReference(i), @RecordID) = 0) then
                     Bitmap.HideRecord(IndexDef.ObjectID, Position)
                   else
                     begin
                       Move(ScanPage.GetPKey(i)^, Key^, KeyRef.ShortKeySize);
                       Move(ScanPage.GetPReference(i)^, RecordID, KeyRef.ReferenceSize);
                     end;
                end;
               GetNextPosition(SessionID, Position);
             end;
            ScanPageNo := ScanPage.RightPageNo;
          finally
            PutIndexPage(ScanPage);
          end;
        end;
     end;
  finally
    KeyRef.CompareFieldCount := OldCompareFieldCount;
    if (Key <> nil) then
      KeyRef.FreeAndNilKeyBuffer(Key);
    Position.Free;
  end;
end;// ApplyDistinctToRecordBitmap


//------------------------------------------------------------------------------
// CreateSearchInfo
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CreateSearchInfo: TABSSearchInfo;
begin
  New(PABSBTreeSearchInfo(Result));
  PABSBTreeSearchInfo(Result)^.IsFilled := False;
  PABSBTreeSearchInfo(Result)^.CurrentKeyPath := TABSKeyPath.Create;
  PABSBTreeSearchInfo(Result)^.EndKeyPath := nil;
end;// CreateSearchInfo


//------------------------------------------------------------------------------
// FreeSearchInfo
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.FreeSearchInfo(SearchInfo: TABSSearchInfo);
begin
  if (PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath <> nil) then
    PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath.Free;
  if (PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath <> nil) then
   PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath.Free;
  Dispose(PABSBTreeSearchInfo(SearchInfo));
end;// FreeSearchInfo


//------------------------------------------------------------------------------
// GetCurrentPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetCurrentPosition(
                             SessionID:           TABSSessionID;
                             Restart:             Boolean;
                             GoForward:           Boolean;
                             StartScanCondition:  TABSScanSearchCondition;
                             RecordBuffer:        TABSRecordBuffer;
                             RecordID:            TABSRecordID;
                             SearchInfo:          TABSSearchInfo
                                          ): Boolean;
var
  Page:        TABSBTreePage;
  KeyBuffer:  TAbsPByte;
  Pos:                           TABSKeyPath;
  Res:                           Integer;
  TakeFindFirstInsteadOfCurrent: Boolean;
begin
   if (StartScanCondition = nil) then
     if (Restart) then
       Result := GetPosition(SessionID, Restart, GoForward,
                           PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath)
     else
       Result := GetIndexPosition(SessionID, RecordID, RecordBuffer,
                                PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath)
    else
      begin
        KeyBuffer := FKeyRef.AllocShortKeyBuffer;
        Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
        FKeyRef.CompareFieldCount := StartScanCondition.KeyFieldCount;
        try
          FKeyRef.MakeShortKeyFromRecordBuffer(StartScanCondition.KeyRecordBuffer, KeyBuffer);
          FKeyRef.SetPartialCompare(StartScanCondition.KeyRecordBuffer, StartScanCondition.PartialCompare);
          Result := Page.FindByCondition(
                              SessionID,
                              GoForward,
                              KeyBuffer,
                              StartScanCondition.Condition,
                              PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath
                                        );
        finally
          FKeyRef.SetPartialCompare(StartScanCondition.KeyRecordBuffer, False);
          FKeyRef.FreeAndNilKeyBuffer(KeyBuffer);
          FKeyRef.CompareFieldCount := FKeyRef.PartCount;
          PutIndexPage(Page);
        end;

      if (Result and (not Restart)) then
        begin
          Pos := TABSKeyPath.Create;
          TakeFindFirstInsteadOfCurrent := True;
          try
            Result := GetIndexPosition(SessionID, RecordID, RecordBuffer, Pos);
            if (Result) then
             begin
               Res := CompareRecordPositionsInIndex(
                                       Pos,
                                       PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath
                                                     );
               if (GoForward) then
                 TakeFindFirstInsteadOfCurrent := (Res < 0)
               else
                 TakeFindFirstInsteadOfCurrent := (Res > 0);
               if (not TakeFindFirstInsteadOfCurrent) then
                begin
                  PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath.Free;
                  PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath := Pos;
                end
               else
                if (GoForward) then
                  Result := GetPriorPosition(SessionID, PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath)
                else
                  Result := GetNextPosition(SessionID, PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath);
             end;
          finally
            if (TakeFindFirstInsteadOfCurrent) then
              Pos.Free;
          end;
        end;
    end;
end;// GetCurrentPosition


//------------------------------------------------------------------------------
// GetEndPosition
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetEndPosition(
                             SessionID:           TABSSessionID;
                             GoForward:           Boolean;
                             StartScanCondition:  TABSScanSearchCondition;
                             EndScanCondition:    TABSScanSearchCondition;
                             SearchInfo:          TABSSearchInfo
                                      ): Boolean;
var
  Page:    TABSBTreePage;
  EndCond: TABSScanSearchCondition;
  KeyBuffer:  TAbsPByte;
begin
  if (StartScanCondition <> nil) then
    begin
      KeyBuffer := FKeyRef.AllocShortKeyBuffer;
      Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
      try
        PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath := TABSKeyPath.Create;
        if (EndScanCondition <> nil) then
          EndCond := EndScanCondition
        else
          EndCond := StartScanCondition;
        FKeyRef.CompareFieldCount := EndCond.KeyFieldCount;
        FKeyRef.MakeShortKeyFromRecordBuffer(EndCond.KeyRecordBuffer, KeyBuffer);
        FKeyRef.SetPartialCompare(EndCond.KeyRecordBuffer, StartScanCondition.PartialCompare);
        Result := Page.FindByCondition(
                        SessionID,
                        not GoForward,
                        KeyBuffer,
                        EndCond.Condition,
                        PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath
                                      );
      finally
        FKeyRef.SetPartialCompare(EndCond.KeyRecordBuffer, False);
        FKeyRef.FreeAndNilKeyBuffer(KeyBuffer);
        FKeyRef.CompareFieldCount := FKeyRef.PartCount;
        PutIndexPage(Page);
      end;
    end
  else
    Result := True;
end;// GetEndPosition


//------------------------------------------------------------------------------
// FindRecord
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.FindRecord(
                   SessionID:           TABSSessionID;
                   Restart:             Boolean;
                   GoForward:           Boolean;
                   StartScanCondition:  TABSScanSearchCondition;
                   EndScanCondition:    TABSScanSearchCondition;
                   RecordBuffer:        TABSRecordBuffer;
                   var RecordID:        TABSRecordID;
                   SearchInfo:          TABSSearchInfo
                                  ): Boolean;
var
  Res:     Integer;
begin
  if (SearchInfo = nil) then
    raise EABSException.Create(20077, ErrorANilPointer);
  if ((Restart) and (PABSBTreeSearchInfo(SearchInfo)^.IsFilled)) then
    raise EABSException.Create(20078, ErrorABTreeInvalidParams);

  Result := True;
  if (Restart or (not PABSBTreeSearchInfo(SearchInfo)^.IsFilled)) then
    Result := GetCurrentPosition(SessionID, Restart, GoForward, StartScanCondition,
                                 RecordBuffer, RecordID, SearchInfo);

  if (Result and (not PABSBTreeSearchInfo(SearchInfo)^.IsFilled)) then
    if (not GetEndPosition(SessionID, GoForward, StartScanCondition, EndScanCondition, SearchInfo)) then
      Result := False;

  if (Result) then
   begin
    if (not Restart) then
      Result := GetPosition(SessionID, Restart, GoForward,
                            PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath);
    if (Result and (PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath <> nil)) then
     begin
       Res := CompareRecordPositionsInIndex(
                               PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath,
                               PABSBTreeSearchInfo(SearchInfo)^.EndKeyPath);
       if (GoForward) then
         Result := (Res <= 0)
       else
         Result := (Res >= 0);
     end;
   end;

  if (Result) then
    begin
      RecordID := GetRecordID(SessionID, PABSBTreeSearchInfo(SearchInfo)^.CurrentKeyPath);
      if (not PABSBTreeSearchInfo(SearchInfo)^.IsFilled) then
       begin
        PABSBTreeSearchInfo(SearchInfo)^.GoForward := GoForward;
        PABSBTreeSearchInfo(SearchInfo)^.IsFilled := True;
       end;
    end;
end;// FindRecord


//------------------------------------------------------------------------------
// return 0 if record buffers are equal in this index
// return 1 if Buffer1 is higher than Buffer 2 (Pos1 > Pos2)
// return -1 if Buffer1 is lower than Buffer 2 (Pos1 < Pos2)
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CompareRecordBuffersByIndex(
                        Buffer1: TABSRecordBuffer;
                        Buffer2: TABSRecordBuffer;
                        IndexFieldCount: Integer
                                    ): Integer;
var KeyBuffer1, KeyBuffer2: TAbsPByte;
begin
 KeyBuffer1 := FKeyRef.AllocFullKeyBuffer;
 KeyBuffer2 := FKeyRef.AllocFullKeyBuffer;
 FKeyRef.CompareFieldCount := IndexFieldCount;
 try
   FKeyRef.MakeFullKeyFromRecordBuffer(Buffer1, KeyBuffer1);
   FKeyRef.MakeFullKeyFromRecordBuffer(Buffer2, KeyBuffer2);
   Result := FKeyRef.CompareFullKeys(KeyBuffer1,KeyBuffer2);
 finally
   FKeyRef.CompareFieldCount := FKeyRef.PartCount;
   FKeyRef.FreeAndNilKeyBuffer(KeyBuffer1);
   FKeyRef.FreeAndNilKeyBuffer(KeyBuffer2);
 end;
end; // CompareRecordBuffersByIndex


//------------------------------------------------------------------------------
// return 0 if conditions are equal in this index
// return 1 if Condition1 is higher than Condition2
// return -1 if Condition1 is lower than Condition2
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CompareConditions(
                Condition1:   TABSScanSearchCondition;
                Condition2:   TABSScanSearchCondition
                          ): Integer;
begin
  if (Condition1.Condition in [scGreater, scGreaterEqual]) then
   Result := -1
  else
   if (Condition1.Condition in [scLower, scLowerEqual]) then
    Result := 1
   else
    Result := 0;
end;// CompareConditions


//------------------------------------------------------------------------------
// approximate record count between range conditions
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetApproxRangeRecordCount(
                SessionID:         TABSSessionID;
                TableRecordCount:  TABSRecordNo;
                RangeCondition1:   TABSScanSearchCondition;
                RangeCondition2:   TABSScanSearchCondition
                                  ): TABSRecordNo;
var
  FKeyBuffer:             TAbsPByte;
  KeyPath:                TABSKeyPath;
  RangeStartCondition:    TABSScanSearchCondition;
  RangeEndCondition:      TABSScanSearchCondition;
  ApproxRecNo1InPercents: double;
  ApproxRecNo2InPercents: double;
begin
  if (IndexDef.RootPageNo <> INVALID_PAGE_NO) then
   begin
    if (CompareConditions(RangeCondition1, RangeCondition2) < 0) then
     begin
       RangeStartCondition := RangeCondition1;
       RangeEndCondition := RangeCondition2;
     end
    else
     begin
       RangeStartCondition := RangeCondition2;
       RangeEndCondition := RangeCondition1;
     end;
    FKeyBuffer := FKeyRef.AllocShortKeyBuffer;
    KeyPath := TABSKeyPath.Create;
    FRootPage := nil;
    try
     FKeyRef.MakeShortKeyFromRecordBuffer(RangeStartCondition.KeyRecordBuffer, FKeyBuffer);
     FRootPage := GetIndexPage(SessionID, IndexDef.RootPageNo);
     FKeyRef.CompareFieldCount := RangeStartCondition.KeyFieldCount;
     if (not FRootPage.FindByCondition(SessionID, True, FKeyBuffer,
                                   RangeStartCondition.Condition, KeyPath)) then
       Result := 0
     else
      begin
         ApproxRecNo1InPercents := KeyPath.GetApproxRecNoInPercents;
         KeyPath.Clear;
         FKeyRef.MakeShortKeyFromRecordBuffer(RangeEndCondition.KeyRecordBuffer, FKeyBuffer);
         if (not FRootPage.FindByCondition(SessionID, False, FKeyBuffer,
                                       RangeEndCondition.Condition, KeyPath)) then
           Result := 0
         else
           begin
             ApproxRecNo2InPercents := KeyPath.GetApproxRecNoInPercents;
             Result := Round((ApproxRecNo2InPercents -
                              ApproxRecNo1InPercents) * TableRecordCount);
           end;
      end;
    finally
     if (FRootPage <> nil) then
      PutIndexPage(FRootPage);
     KeyPath.Free;
     FKeyRef.FreeAndNilKeyBuffer(FKeyBuffer);
     FKeyRef.CompareFieldCount := FKeyRef.PartCount;
    end; // try
   end
  else
    raise EABSException.Create(20125, ErrorAInvalidPageNo);
  if (Result < 0) then
   Result := 0;
  if (Result > TableRecordCount) then
   Result := TableRecordCount;
end;// GetApproxRangeRecordCount


//------------------------------------------------------------------------------
// CanInsertRecord
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CanInsertRecord(
                                 SessionID:      TABSSessionID;
                                 RecordBuffer:   TABSRecordBuffer
                                 ): Boolean;
var
  KeyBuffer:             TAbsPByte;
  KeyPath:               TABSKeyPath;
begin
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20126, ErrorAInvalidPageNo);
  if (IndexDef.Primary or IndexDef.Unique) then
   begin
    KeyBuffer := FKeyRef.AllocShortKeyBuffer;
    KeyPath := TABSKeyPath.Create;
    FRootPage := nil;
    try
      FRootPage := GetIndexPage(SessionID, IndexDef.RootPageNo);
      FKeyRef.MakeShortKeyFromRecordBuffer(RecordBuffer, KeyBuffer);
      Result := (not FRootPage.FindByCondition(SessionID, True, KeyBuffer, scEqual, KeyPath));
    finally
      if (FRootPage <> nil) then
        PutIndexPage(FRootPage);
      KeyPath.Free;
      FKeyRef.FreeAndNilKeyBuffer(KeyBuffer);
    end;
   end
  else
   Result := True;
end;// CanInsertRecord


//------------------------------------------------------------------------------
// CanUpdateRecord
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.CanUpdateRecord(
                     SessionID:                        TABSSessionID;
                     OldRecordBuffer, NewRecordBuffer: TABSRecordBuffer
                                       ): Boolean;
begin
  if (CompareRecordBuffersByIndex(OldRecordBuffer, NewRecordBuffer,
                                  FKeyRef.PartCount) <> 0) then
    Result := CanInsertRecord(SessionID, NewRecordBuffer)
  else
    Result := True;
end;// CanUpdateRecord


//------------------------------------------------------------------------------
// insert record
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.InsertRecord(Cursor: TABSCursor);
var
  FKeyBuffer: TAbsPByte;
  KeyPath: TABSKeyPath;
begin
  if (IndexDef.RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20127, ErrorAInvalidPageNo);
  FKeyBuffer := FKeyRef.AllocShortKeyBuffer;
  KeyPath := TABSKeyPath.Create;
  FRootPage := nil;
  try
   FKeyRef.MakeShortKeyFromRecordBuffer(Cursor.CurrentRecordBuffer, FKeyBuffer);
   FRootPage := GetIndexPage(Cursor.Session.SessionID, IndexDef.RootPageNo);
   FRootPage.InsertLeafEntry(Cursor.Session.SessionID, FKeyBuffer, @Cursor.CurrentRecordID, KeyPath);
   {$IFDEF DEBUG_INDEXES}
   KeyPath.Clear;
   FRootPage.CheckIntegrity(Cursor.Session.SessionID, KeyPath);
   {$ENDIF}
  finally
   if (FRootPage <> nil) then
     PutIndexPage(FRootPage);
   FKeyRef.FreeAndNilKeyBuffer(FKeyBuffer);
   KeyPath.Free;
  end;
end;// InsertRecord


//------------------------------------------------------------------------------
// UpdateRecord
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.UpdateRecord(Cursor: TABSCursor; BeforeNewRecordIsStored: Boolean);
var
  FOldKeyBuffer: TAbsPByte;
  FNewKeyBuffer: TAbsPByte;
  KeyPath:       TABSKeyPath;
begin
  FOldKeyBuffer := FKeyRef.AllocFullKeyBuffer;
  FNewKeyBuffer := FKeyRef.AllocFullKeyBuffer;
  KeyPath := TABSKeyPath.Create;
  FRootPage := nil;
  try
   FKeyRef.MakeFullKeyFromRecordBuffer(Cursor.EditRecordBuffer, FOldKeyBuffer);
   FKeyRef.MakeFullKeyFromRecordBuffer(Cursor.CurrentRecordBuffer, FNewKeyBuffer);
   if (FKeyRef.CompareFullKeys(FOldKeyBuffer, FNewKeyBuffer) <> 0) then
     begin
       FKeyRef.FreeAndNilKeyBuffer(FOldKeyBuffer);
       FKeyRef.FreeAndNilKeyBuffer(FNewKeyBuffer);
       FOldKeyBuffer := FKeyRef.AllocShortKeyBuffer;
       FNewKeyBuffer := FKeyRef.AllocShortKeyBuffer;

       FRootPage := GetIndexPage(Cursor.Session.SessionID, IndexDef.RootPageNo);
       if (BeforeNewRecordIsStored) then
         begin
           FKeyRef.MakeShortKeyFromRecordBuffer(Cursor.EditRecordBuffer, FOldKeyBuffer);
           if (not FRootPage.DeleteLeafEntry(Cursor.Session.SessionID, FOldKeyBuffer, @Cursor.CurrentRecordID, KeyPath)) then
             raise EABSException.Create(20250, ErrorABTreeDeleteEntryNotFound);
         end
       else
         begin
           FKeyRef.MakeShortKeyFromRecordBuffer(Cursor.CurrentRecordBuffer, FNewKeyBuffer);
           FRootPage.InsertLeafEntry(Cursor.Session.SessionID, FNewKeyBuffer, @Cursor.CurrentRecordID, KeyPath);
         end;

      {$IFDEF DEBUG_INDEXES}
       KeyPath.Clear;
       FRootPage.CheckIntegrity(Cursor.Session.SessionID, KeyPath);
      {$ENDIF}
     end;
  finally
   if (FRootPage <> nil) then
     PutIndexPage(FRootPage);
   FKeyRef.FreeAndNilKeyBuffer(FOldKeyBuffer);
   FKeyRef.FreeAndNilKeyBuffer(FNewKeyBuffer);
   KeyPath.Free;
  end;
end;// UpdateRecord


//------------------------------------------------------------------------------
// DeleteRecord
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.DeleteRecord(Cursor: TABSCursor);
var
  FKeyBuffer: TAbsPByte;
  KeyPath: TABSKeyPath;
begin
  FKeyBuffer := FKeyRef.AllocShortKeyBuffer;
  KeyPath := TABSKeyPath.Create;
  FRootPage := nil;
  try
   FKeyRef.MakeShortKeyFromRecordBuffer(Cursor.CurrentRecordBuffer, FKeyBuffer);
   FRootPage := GetIndexPage(Cursor.Session.SessionID, IndexDef.RootPageNo);
   if (not FRootPage.DeleteLeafEntry(Cursor.Session.SessionID, FKeyBuffer, @Cursor.CurrentRecordID, KeyPath)) then
     raise EABSException.Create(20027, ErrorABTreeDeleteEntryNotFound);

   {$IFDEF DEBUG_INDEXES}
   KeyPath.Clear;
   FRootPage.CheckIntegrity(Cursor.Session.SessionID, KeyPath);
  {$ENDIF}
  finally
   if (FRootPage <> nil) then
     PutIndexPage(FRootPage);
   FKeyRef.FreeAndNilKeyBuffer(FKeyBuffer);
   KeyPath.Free;
  end;
end;// DeleteRecord


//------------------------------------------------------------------------------
// GetMaxEntriesPerPage
//------------------------------------------------------------------------------
function TABSBTreeRecordIndex.GetMaxEntriesPerPage: Integer;
var
  PageManager: TABSPageManager;
begin
  PageManager := IndexManager.GetPageManager(Self);
  // page size div min_entry_size (key_size+reference_size)
  Result := PageManager.PageDataSize div (FKeyRef.ShortKeySize+4);
end;// GetMaxEntriesPerPage


//------------------------------------------------------------------------------
// GetRecordIDByIndexPosition
//------------------------------------------------------------------------------
procedure TABSBTreeRecordIndex.GetRecordIDByIndexPosition(SessionID: TABSSessionID; IndexPos: TABSIndexPosition; var RecordID: TABSRecordID);
var
  Page: TABSBTreePage;
  CurrentLevel: integer;
  PageNo: TABSPageNo;
begin
  // only EntryNo's are filled in IndexPos items, PageNo's are not filled
  Page := nil;
  try
   Page := GetIndexPage(SessionID, IndexDef.RootPageNo);
   CurrentLevel := 0;
   // go down by tree to the leaf
   while (CurrentLevel < TABSKeyPath(IndexPos).Count-1) do
     begin
       // get PageNo by EntryNo
       Move(Page.GetPReference(TABSKeyPath(IndexPos).Items[CurrentLevel].EntryNo)^,
            PageNo, Page.ReferenceSize);
       PutIndexPage(Page);
       Page := nil;
       Page := GetIndexPage(SessionID, PageNo);
       Inc(CurrentLevel);
     end;
   // get RecordID from Leaf page
   Move(Page.GetPReference(TABSKeyPath(IndexPos).Items[CurrentLevel].EntryNo)^,
        RecordID, Page.ReferenceSize);
  finally
   if (Page <> nil) then
     PutIndexPage(Page);
  end;
end;// GetRecordIDByIndexPosition



////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreePageIndex
//
////////////////////////////////////////////////////////////////////////////////

//------------------------------------------------------------------------------
// AddIndexPage
//------------------------------------------------------------------------------
function TABSBTreePageIndex.AddIndexPage(SessionID: TABSSessionID): TABSBTreePage;
begin
  Result := TABSBTreePage.Create(LPageManager, FKeyRef);
  try
    Result.Page := LPageManager.AddPage(SessionID, ptTableIndex);
  except
    Result.Free;
    raise;
  end;
end;// AddIndexPage


//------------------------------------------------------------------------------
// GetIndexPage
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetIndexPage(SessionID: TABSSessionID; PageNo: TABSPageNo): TABSBTreePage;
begin
  Result := TABSBTreePage.Create(LPageManager, FKeyRef);
  try
    Result.Page := LPageManager.GetPage(SessionID, PageNo, ptTableIndex);
  except
   Result.Free;
   raise;
  end;
end;// GetIndexPage


//------------------------------------------------------------------------------
// PutIndexPage
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.PutIndexPage(Page: TABSBTreePage);
begin
  LPageManager.PutPage(Page.Page);
  Page.Free;
end;// PutIndexPage


//------------------------------------------------------------------------------
// GetFirstPosition
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetFirstPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  Page: TABSBTreePage;
begin
  if (RootPageNo <> INVALID_PAGE_NO) then
    begin
      Position.Clear;
      Page := GetIndexPage(SessionID, RootPageNo);
      try
        Result := Page.GetFirstPosition(SessionID, Position);
      finally
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20115, ErrorABTreeInvalidPage);
end;// GetFirstPosition


//------------------------------------------------------------------------------
// GetLastPosition
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetLastPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  Page: TABSBTreePage;
begin
  if (RootPageNo <> INVALID_PAGE_NO) then
    begin
      Position.Clear;
      Page := GetIndexPage(SessionID, RootPageNo);
      try
        Result := Page.GetLastPosition(SessionID, Position);
      finally
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20116, ErrorABTreeInvalidPage);
end;// GetLastPosition


//------------------------------------------------------------------------------
// GetNextPosition
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetNextPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  i:            Integer;
  CurrentLevel: Integer;
  Page:         TABSBTreePage;
  NextPageNo:   TABSPageNo;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20099, ErrorABTreeInvalidPosition);
  CurrentLevel := Position.Count-1;
  Result := False;

  repeat
    if (Position.Items[CurrentLevel].EntryNo <
        Position.Items[CurrentLevel].EntryCount-1) then
     begin
      Inc(Position.Items[CurrentLevel].EntryNo);
      Result := True;
      break;
     end
    else
     Dec(CurrentLevel);
  until (CurrentLevel < 0);

  if (Result) then
    for i := CurrentLevel+1 to Position.Count-1 do
      begin
        Page := GetIndexPage(SessionID, Position.Items[i].PageNo);
        NextPageNo := Page.RightPageNo;
        PutIndexPage(Page);
        if (NextPageNo = INVALID_PAGE_NO) then
          raise EABSException.Create(20100, ErrorABTreeInvalidPage);
        Page := GetIndexPage(SessionID, NextPageNo);
        try
          Position.Items[i].PageNo := NextPageNo;
          Position.Items[i].EntryNo := 0;
          Position.Items[i].EntryCount := Page.EntryCount;
        finally
          PutIndexPage(Page);
        end;
      end;
end;// GetNextPosition


//------------------------------------------------------------------------------
// GetPriorPosition
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetPriorPosition(SessionID: TABSSessionID; Position: TABSKeyPath): Boolean;
var
  i:            Integer;
  CurrentLevel: Integer;
  Page:         TABSBTreePage;
  PriorPageNo:   TABSPageNo;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20101, ErrorABTreeInvalidPosition);
  CurrentLevel := Position.Count-1;
  Result := False;

  repeat
    if (Position.Items[CurrentLevel].EntryNo > 0) then
     begin
      Dec(Position.Items[CurrentLevel].EntryNo);
      Result := True;
      break;
     end
    else
     Dec(CurrentLevel);
  until (CurrentLevel < 0);

  if (Result) then
    for i := CurrentLevel+1 to Position.Count-1 do
      begin
        Page := GetIndexPage(SessionID, Position.Items[i].PageNo);
        PriorPageNo := Page.LeftPageNo;
        PutIndexPage(Page);
        if (PriorPageNo = INVALID_PAGE_NO) then
          raise EABSException.Create(20102, ErrorABTreeInvalidPage);
        Page := GetIndexPage(SessionID, PriorPageNo);
        try
          Position.Items[i].PageNo := PriorPageNo;
          Position.Items[i].EntryNo := Page.EntryCount-1;
          Position.Items[i].EntryCount := Page.EntryCount;
        finally
          PutIndexPage(Page);
        end;
      end;
end;// GetPriorPosition


//------------------------------------------------------------------------------
// GetPosition
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetPosition(SessionID: TABSSessionID;
                      PageNo: TABSPageNo; Position: TABSKeyPath): Boolean;
var
  Page: TABSBTreePage;
begin
  if (RootPageNo <> INVALID_PAGE_NO) then
    begin
      Page := GetIndexPage(SessionID, RootPageNo);
      try
        Result := Page.FindByCondition(
                            SessionID,
                            True,
                            @PageNo,
                            scEqual,
                            Position);
      finally
        PutIndexPage(Page);
      end;
    end
  else
    raise EABSException.Create(20117, ErrorABTreeInvalidPage);
end;// GetPosition


//------------------------------------------------------------------------------
// GetPageValue
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetPageValue(SessionID: TABSSessionID;
                                                   Position: TABSKeyPath): Word;
var
  Page: TABSBTreePage;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20107, ErrorABTreeInvalidPosition);
  Page := GetIndexPage(SessionID, Position.Items[Position.Count-1].PageNo);
  try
    Move(Page.GetPReference(Position.Items[Position.Count-1].EntryNo)^,
         Result,
         sizeof(Result));
  finally
    PutIndexPage(Page);
  end;
end;// GetPageValue


//------------------------------------------------------------------------------
// SetPageValue
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.SetPageValue(SessionID: TABSSessionID;
                                      Position: TABSKeyPath; Value: Word);
var
  Page: TABSBTreePage;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20108, ErrorABTreeInvalidPosition);
  Page := GetIndexPage(SessionID, Position.Items[Position.Count-1].PageNo);
  try
    Page.UpdateReference(Position.Items[Position.Count-1].EntryNo, @Value);
    Page.IsDirty := True;
  finally
    PutIndexPage(Page);
  end;
end;// SetPageValue


//------------------------------------------------------------------------------
// GetPageNo
//------------------------------------------------------------------------------
function TABSBTreePageIndex.GetPageNo(SessionID: TABSSessionID; Position: TABSKeyPath): TABSPageNo;
var
  Page: TABSBTreePage;
begin
  if (Position.Count = 0) then
   raise EABSException.Create(20103, ErrorABTreeInvalidPosition);
  Page := GetIndexPage(SessionID, Position.Items[Position.Count-1].PageNo);
  try
    Move(Page.GetPKey(Position.Items[Position.Count-1].EntryNo)^,
         Result,
         sizeof(TABSPageNo));
  finally
    PutIndexPage(Page);
  end;
end;// GetPageNo


//------------------------------------------------------------------------------
// FindPageForNewItem
//------------------------------------------------------------------------------
function TABSBTreePageIndex.FindPageForNewItem(SessionID: TABSSessionID;
                           ItemSize: Integer; var PageNo: TABSPageNo): Boolean;
var
  Position: TABSKeyPath;
  AttemptCount: Integer;
  AttemptNo:    Integer;
  Page: TABSBTreePage;
  Value: Word;
begin
  Result := False;
  Position := TABSKeyPath.Create;
  try
    if (GetLastPosition(SessionID, Position)) then
     begin
       AttemptCount := Position.Items[Position.ItemNo-1].EntryCount;
       AttemptNo := 1;
       Page := GetIndexPage(SessionID, Position.Items[Position.ItemNo-1].PageNo);
       try
         repeat
           Move(Page.GetPReference(Position.Items[Position.Count-1].EntryNo)^,
                Value, sizeof(Value));
           if (CanAddNewItem(Value, ItemSize)) then
             begin
               Result := True;
               Move(Page.GetPKey(Position.Items[Position.Count-1].EntryNo)^,
                    PageNo, sizeof(PageNo));
               break;
             end;
           Inc(AttemptNo);
         until ((AttemptNo >= AttemptCount) or
                (not GetPriorPosition(SessionID, Position)));
       finally
         PutIndexPage(Page);
       end;
       if (not Result) then
        if (GetFirstPosition(SessionID, Position)) then
         begin
           AttemptCount := Position.Items[Position.ItemNo-1].EntryCount;
           AttemptNo := 1;
           Page := GetIndexPage(SessionID, Position.Items[Position.ItemNo-1].PageNo);
           try
             repeat
               Move(Page.GetPReference(Position.Items[Position.Count-1].EntryNo)^,
                    Value, sizeof(Value));
               if (CanAddNewItem(Value, ItemSize)) then
                 begin
                   Result := True;
                   Move(Page.GetPKey(Position.Items[Position.Count-1].EntryNo)^,
                        PageNo, sizeof(PageNo));
                   break;
                 end;
               Inc(AttemptNo);
             until ((AttemptNo >= AttemptCount) or
                    (not GetNextPosition(SessionID, Position)));
           finally
             PutIndexPage(Page);
           end;
         end;
     end;
  finally
    Position.Free;
  end;
end;// FindPageForNewItem


//------------------------------------------------------------------------------
// AddPageItem
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.AddPageItem(SessionID: TABSSessionID;
                   ItemSize: Integer; PageNo: TABSPageNo);
var
  KeyPath:     TABSKeyPath;
  Value:       Word;
  FRootPage:   TABSBTreePage;
begin
  if (RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20118, ErrorABTreeInvalidPage);
  KeyPath := TABSKeyPath.Create;
  try
   // existing PageItem page?
   if (GetPosition(SessionID, PageNo, KeyPath)) then
    begin
      // check if can add new page item (record/blob)
      Value := GetPageValue(SessionID, KeyPath);
      if (not CanAddNewItem(Value, ItemSize)) then
        raise EABSException.Create(20106, ErrorACannotAddItemOnPage);
      // update value
      Value := Value + ItemSize;
      SetPageValue(SessionID, KeyPath, Value);
    end
   else
    begin
     Value := ItemSize;
     FRootPage := GetIndexPage(SessionID, FRootPageNo);
     try
       FRootPage.InsertLeafEntry(SessionID, @PageNo, @Value, KeyPath);
     finally
       PutIndexPage(FRootPage);
     end;
    end;
  finally
   KeyPath.Free;
  end;
end;// AddPageItem


//------------------------------------------------------------------------------
// DeletePageItem
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.DeletePageItem(SessionID: TABSSessionID; ItemSize: Integer; PageNo: TABSPageNo; NewItemCount: Integer);
var
  KeyPath:     TABSKeyPath;
  Value:       Word;
  FRootPage:   TABSBTreePage;
begin
  if (RootPageNo = INVALID_PAGE_NO) then
    raise EABSException.Create(20110, ErrorAInvalidPageNo);

  KeyPath := TABSKeyPath.Create;
  try
   if (not GetPosition(SessionID, PageNo, KeyPath)) then
    raise EABSException.Create(20111, ErrorAInvalidPageNo);
   // update PageItem count
   if (NewItemCount >= 0) then
     Value := NewItemCount
   else
     begin
       // check current PageItem count / total size
       Value := GetPageValue(SessionID, KeyPath);
       if (Value = 0) then
         raise EABSException.Create(20112, ErrorABTreeEmptyPage);
       Value := Value - ItemSize;
     end;
   if (Value > 0) then
    SetPageValue(SessionID, KeyPath, Value)
   else
    // if PageItem page is empty => delete it
    begin
      Value := GetPageValue(SessionID, KeyPath);
      FRootPage := GetIndexPage(SessionID, RootPageNo);
      try
        FRootPage.DeleteLeafEntry(SessionID, @PageNo, @Value, KeyPath);
      finally
        PutIndexPage(FRootPage);
      end;
    end;
  finally
    KeyPath.Free;
  end;
end;// DeletePageItem


//------------------------------------------------------------------------------
// constructor
//------------------------------------------------------------------------------
constructor TABSBTreePageIndex.Create(PageManager: TABSPageManager);
begin
  LPageManager := PageManager;
  FRootPageNo := INVALID_PAGE_NO;
  FKeyRef := TABSPageKeyRef.Create;
end;// Create


//------------------------------------------------------------------------------
// Destroy
//------------------------------------------------------------------------------
destructor TABSBTreePageIndex.Destroy;
begin
  FKeyRef.Free;
end;// Destroy


//------------------------------------------------------------------------------
// CreateIndex
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.CreateIndex(SessionID: TABSSessionID);
var
  RootPage: TABSBTreePage;
begin
  RootPage := AddIndexPage(SessionID);
  FRootPageNo := RootPage.PageNo;
  try
    RootPage.InitAsRoot;
    RootPage.IsDirty := True;
  finally
    PutIndexPage(RootPage);
  end;
end;// CreateIndex


//------------------------------------------------------------------------------
// DropIndex
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.DropIndex(SessionID: TABSSessionID);
var
  RootPage: TABSBTreePage;
begin
  RootPage := GetIndexPage(SessionID, FRootPageNo);
  try
    RootPage.FreeAllPages(SessionID, False);
    FRootPageNo := INVALID_PAGE_NO;
  finally
    PutIndexPage(RootPage);
  end;
end;// DropIndex


//------------------------------------------------------------------------------
// EmptyIndex
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.EmptyIndex(SessionID: TABSSessionID);
var
  RootPage: TABSBTreePage;
begin
  RootPage := GetIndexPage(SessionID, FRootPageNo);
  try
    RootPage.FreeAllPages(SessionID, True);
    RootPage.InitAsRoot;
    RootPage.IsDirty := True;
  finally
    PutIndexPage(RootPage);
  end;
end;// EmptyIndex


//------------------------------------------------------------------------------
// OpenIndex
//------------------------------------------------------------------------------
procedure TABSBTreePageIndex.OpenIndex(RootPageNo: TABSPageNo);
begin
  FRootPageNo := RootPageNo;
end;// OpenIndex




////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeRecordPageIndex
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// GetPageRecordCount
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.GetPageRecordCount(SessionID: TABSSessionID;
                                                   Position: TABSKeyPath): Word;
begin
  Result := GetPageValue(SessionID, Position);
end;// GetPageRecordCount


//------------------------------------------------------------------------------
// CanAddNewItem
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.CanAddNewItem(OldValue: Integer; NewItemSize: Integer): Boolean;
begin
  Result := (OldValue < FMaxRecordsOnPage);
end;// CanAddNewItem


//------------------------------------------------------------------------------
// FindPageForNewRecord
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.FindPageForNewRecord(
                     SessionID: TABSSessionID; var PageNo: TABSPageNo): Boolean;
begin
  Result := FindPageForNewItem(SessionID, 1, PageNo);
end;// FindPageForNewRecord


//------------------------------------------------------------------------------
// AddRecord
//------------------------------------------------------------------------------
procedure TABSBTreeRecordPageIndex.AddRecord(SessionID: TABSSessionID; PageNo: TABSPageNo; AddCount: Integer = 1);
begin
  AddPageItem(SessionID, AddCount, PageNo);
end;// AddRecord


//------------------------------------------------------------------------------
// DeleteRecord
//------------------------------------------------------------------------------
procedure TABSBTreeRecordPageIndex.DeleteRecord(SessionID: TABSSessionID; PageNo: TABSPageNo; NewItemCount: Integer);
begin
  DeletePageItem(SessionID, 1, PageNo, NewItemCount);
end;// DeleteRecord


//------------------------------------------------------------------------------
// GetFirstRecordPage
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.GetFirstRecordPage(SessionID: TABSSessionID;
                                               var PageNo: TABSPageNo): Boolean;
var
  KeyPath: TABSKeyPath;
begin
  KeyPath := TABSKeyPath.Create;
  try
    Result := GetFirstPosition(SessionID, KeyPath);
    if (Result) then
      PageNo := GetPageNo(SessionID, KeyPath);
  finally
    KeyPath.Free;
  end;
end;// GetFirstRecordPage


//------------------------------------------------------------------------------
// GetLastRecordPage
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.GetLastRecordPage(SessionID: TABSSessionID;
                                              var PageNo: TABSPageNo): Boolean;
var
  KeyPath: TABSKeyPath;
begin
  KeyPath := TABSKeyPath.Create;
  try
    Result := GetLastPosition(SessionID, KeyPath);
    if (Result) then
      PageNo := GetPageNo(SessionID, KeyPath);
  finally
    KeyPath.Free;
  end;
end;// GetLastRecordPage


//------------------------------------------------------------------------------
// GetNextRecordPage
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.GetNextRecordPage(SessionID: TABSSessionID;
                                              CurrentPageNo: TABSPageNo;
                                              var NextPageNo: TABSPageNo): Boolean;
var
  KeyPath: TABSKeyPath;
begin
  KeyPath := TABSKeyPath.Create;
  Result := False;
  try
    if (not GetPosition(SessionID, CurrentPageNo, KeyPath)) then
      raise EABSException.Create(20104, ErrorAInvalidPageNo);
    Result := GetNextPosition(SessionID, KeyPath);
    if (Result) then
      NextPageNo := GetPageNo(SessionID, KeyPath);
  finally
    KeyPath.Free;
  end;
end;// GetNextRecordPage


//------------------------------------------------------------------------------
// GetPriorRecordPage
//------------------------------------------------------------------------------
function TABSBTreeRecordPageIndex.GetPriorRecordPage(SessionID: TABSSessionID;
                                               CurrentPageNo: TABSPageNo;
                                               var PriorPageNo: TABSPageNo): Boolean;
var
  KeyPath: TABSKeyPath;
begin
  KeyPath := TABSKeyPath.Create;
  Result := False;
  try
    if (not GetPosition(SessionID, CurrentPageNo, KeyPath)) then
      raise EABSException.Create(20105, ErrorAInvalidPageNo);
    Result := GetPriorPosition(SessionID, KeyPath);
    if (Result) then
      PriorPageNo := GetPageNo(SessionID, KeyPath);
  finally
    KeyPath.Free;
  end;
end;// GetPriorRecordPage


//------------------------------------------------------------------------------
// GetRecordByRecNo
//------------------------------------------------------------------------------
procedure TABSBTreeRecordPageIndex.GetRecordByRecNo(SessionID: TABSSessionID;
                                                    RecNo: TABSRecordNo;
                                                    var PageNo: TABSPageNo;
                                                    var RecNoOnPage: Integer);
var
  Position: TABSKeyPath;
  TotalRecordCount: Integer;
  PageRecordCount:  Integer;
  bFound: Boolean;
begin
  Position := TABSKeyPath.Create;
  bFound := False;
  try
    if (GetFirstPosition(SessionID, Position)) then
     begin
       TotalRecordCount := 0;
       repeat
         PageRecordCount := GetPageRecordCount(SessionID, Position);
         Inc(TotalRecordCount, PageRecordCount);
         if (TotalRecordCount > RecNo) then
           begin
             bFound := True;
             PageNo := GetPageNo(SessionID, Position);
             RecNoOnPage := RecNo - (TotalRecordCount-PageRecordCount);
             break;
           end;
       until (not GetNextPosition(SessionID, Position));
     end;
  finally
    Position.Free;
  end;
  if (not bFound) then
    raise EABSException.Create(20113, ErrorACannotSetRecNoGreaterThanRecordCount);
end;// GetRecordByRecNo


//------------------------------------------------------------------------------
// GetRecNoByRecord
//------------------------------------------------------------------------------
procedure TABSBTreeRecordPageIndex.GetRecNoByRecord(SessionID: TABSSessionID;
                                                    PageNo: TABSPageNo;
                                                    RecNoOnPage: Integer;
                                                    var RecNo: TABSRecordNo);
var
  Position: TABSKeyPath;
begin
  Position := TABSKeyPath.Create;
  try
    RecNo := 0;
    if (GetPosition(SessionID, PageNo, Position)) then
      while (GetPriorPosition(SessionID, Position)) do
        Inc(RecNo,GetPageRecordCount(SessionID, Position))
    else
      raise EABSException.Create(20114, ErrorAInvalidPageNo);
    Inc(RecNo, RecNoOnPage);
  finally
    Position.Free;
  end;
end;// GetRecNoByRecord


//------------------------------------------------------------------------------
// Validate
//------------------------------------------------------------------------------
procedure TABSBTreeRecordPageIndex.Validate(SessionID: TABSSessionID; StoredRecordCount: Integer);
var
  Position: TABSKeyPath;
  TotalRecordCount: Integer;
  PageRecordCount:  Integer;
begin
  TotalRecordCount := 0;
  Position := TABSKeyPath.Create;
  try
    if (GetFirstPosition(SessionID, Position)) then
     begin
       repeat
         PageRecordCount := GetPageRecordCount(SessionID, Position);
         Inc(TotalRecordCount, PageRecordCount);
       until (not GetNextPosition(SessionID, Position));
     end;
  finally
    Position.Free;
  end;
  if (TotalRecordCount <> StoredRecordCount) then
    raise EABSException.Create(20292, ErrorAInvalidRecordPageIndexOrMostUpdated, [TotalRecordCount,StoredRecordCount]);
end;// Validate




////////////////////////////////////////////////////////////////////////////////
//
// TABSBTreeBlobPageIndex
//
////////////////////////////////////////////////////////////////////////////////


//------------------------------------------------------------------------------
// CanAddNewItem
//------------------------------------------------------------------------------
function TABSBTreeBlobPageIndex.CanAddNewItem(OldValue: Integer; NewItemSize: Integer): Boolean;
begin
  Result := (OldValue + NewItemSize < LPageManager.PageDataSize - sizeof(Word));
end;// CanAddNewItem


//------------------------------------------------------------------------------
// FindPageForNewBlob
//------------------------------------------------------------------------------
function TABSBTreeBlobPageIndex.FindPageForNewBlob(SessionID: TABSSessionID; BlobSize: Integer; var PageNo: TABSPageNo): Boolean;
begin
  Result := FindPageForNewItem(SessionID, BlobSize, PageNo);
end;// FindPageForNewBlob


//------------------------------------------------------------------------------
// AddBlob
//------------------------------------------------------------------------------
procedure TABSBTreeBlobPageIndex.AddBlob(SessionID: TABSSessionID; BlobSize: Integer; PageNo: TABSPageNo);
begin
  AddPageItem(SessionID, BlobSize, PageNo);
end;// AddBlob


//------------------------------------------------------------------------------
// DeleteBlob
//------------------------------------------------------------------------------
procedure TABSBTreeBlobPageIndex.DeleteBlob(SessionID: TABSSessionID; BlobSize: Integer; PageNo: TABSPageNo);
begin
  DeletePageItem(SessionID, BlobSize, PageNo, -1);
end;// DeleteBlob


//------------------------------------------------------------------------------
// GetBlobPageAllocatedSpace
//------------------------------------------------------------------------------
function TABSBTreeBlobPageIndex.GetBlobPageAllocatedSpace(SessionID: TABSSessionID; PageNo: TABSPageNo): Integer;
var
  Position: TABSKeyPath;
  Page: TABSBTreePage;
  Value: Word;
begin
  Result := -1;
  Position := TABSKeyPath.Create;
  try
    if (GetPosition(SessionID,PageNo, Position)) then
      begin
       Page := GetIndexPage(SessionID, Position.Items[Position.ItemNo-1].PageNo);
       try
           Move(Page.GetPReference(Position.Items[Position.Count-1].EntryNo)^,
                Value, sizeof(Value));
           Result := Value;
       finally
         PutIndexPage(Page);
       end;
      end;
  finally
    Position.Free;
  end;
end;// GetBlobPageAllocatedSpace

end.
