unit Index16;

interface

uses
  RyuLibBase, BTree, CompareBytes, DynamicQueue,
  Windows, Classes, SysUtils, SRWLock;

type
  /// TIndex16에서 인덱싱을 하기 위해 각 레코드가 제공해야 할 정보
  IRecord16 = interface
    ['{F433FEB5-4F7B-4A92-8CB9-9BED5873C307}']

    /// Key에 대한 CRC16의 값.  CRC16으로 해싱처리해서 검색을 위한 반복 작업을 줄인다.
    function GetCRC:word;

    {*
      충돌하는 데이터에 대해서는 실제 Key를 이용해서 서로 구별한다.
      다양한 Key의 데이터타입을 처리하기 위해서 데이터의 레퍼런스(포인터)를 취급한다.
    }
    function GetKey:pointer;

    /// Key가 포인터로 처리되었기 때문에, Key의 실제 데이터 크기를 알아야 한다.
    function GetKeySize:integer;
  end;

  TIndex16Array = array [0..$FFFF] of pointer;
  PIndex16Array = ^TIndex16Array;

  /// 16비트 CRC를 이용한 고속 데이터 인덱싱 처리
  TIndex16 = class
  private
    FIndex : PIndex16Array;
    FPool : TDynamicQueue;
    FAllowDuplicatedKey: boolean;
  public
    constructor Create;
    destructor Destroy; override;

    procedure Clear;
    function Add(ARecord16:IRecord16):boolean;
    procedure Remove(ARecord16:IRecord16);
    function Find(ACRC16:word; AKey:pointer; AKeySize:integer):IRecord16;

    property AllowDuplicatedKey : boolean read FAllowDuplicatedKey write FAllowDuplicatedKey;
  end;

implementation

type
  TRecord16 = class (TInterfaceBase, IRecord16)
  private
    FCRC : word;
    FKey : pointer;
    FKeySize : integer;
  public
    function GetCRC:word;
    function GetKey:pointer;
    function GetKeySize:integer;
  end;

  TIndexListItem = class (TBTreeItem)
  private
  protected
    function Compare(ACompareTo:TBTreeItem):integer; override;
    procedure Copy(ACopyTo:TBTreeItem); override;
  public
    Record16 : IRecord16;
  end;

  TIndexList = class
  private
    FIndex16 : TIndex16;
    FLock : TSRWLock;
    FBTree : TBTree;
  public
    constructor Create(AIndex16:TIndex16); reintroduce;
    destructor Destroy; override;

    function IsEmpty:boolean;

    procedure Clear;
    function Add(ARecord16:IRecord16):boolean;
    procedure Remove(ARecord16:IRecord16);
    function RemoveFirst:IRecord16;
    function Find(ACRC16:word; AKey:pointer; AKeySize:integer):IRecord16;
  end;

{ TIndex16 }

function TIndex16.Add(ARecord16: IRecord16): boolean;
var
  List, OldList : TIndexList;
begin
  if ARecord16 = nil then Exit;

  if not FPool.Pop(Pointer(List)) then List := TIndexList.Create(Self);

  OldList := InterlockedCompareExchangePointer(FIndex^[ARecord16.GetCRC], List, nil);
  if OldList <> nil then begin
    FPool.Push(List);
    List := OldList;
  end;

  Result := List.Add(ARecord16);
end;

procedure TIndex16.Clear;
var
  Loop: Integer;
  List : TIndexList;
begin
  for Loop := Low(FIndex^) to High(FIndex^) do begin
    List := InterlockedExchangePointer(FIndex^[Loop], nil);
    if List <> nil then begin
      List.Clear;
      FPool.Push(List);
    end;
  end;
end;

constructor TIndex16.Create;
begin
  inherited;

  FAllowDuplicatedKey := false;

  FPool := TDynamicQueue.Create(true);

  New(FIndex);
  FillChar(FIndex^, SizeOf(TIndex16Array), #0);
end;

destructor TIndex16.Destroy;
var
  List : TIndexList;
begin
  Clear;

  while FPool.Pop(Pointer(List)) do List.Free;

  Dispose(FIndex);
  FreeAndNil(FPool);

  inherited;
end;

function TIndex16.Find(ACRC16: word; AKey: pointer; AKeySize: integer): IRecord16;
var
  List : TIndexList;
begin
  Result := nil;

  List := FIndex^[ACRC16];
  if List = nil then Exit;

  Result := List.Find(ACRC16, AKey, AKeySize);
end;

procedure TIndex16.Remove(ARecord16: IRecord16);
var
  List : TIndexList;
begin
  if ARecord16 = nil then Exit;

  List := FIndex^[ARecord16.GetCRC];
  if List = nil then Exit;

  List.Remove(ARecord16);

  if List.IsEmpty then begin
    // 그 새 다른 것으로 교체 되었을 수도 있다.  따라서, 자신과 같은 경우에만 삭제
    InterlockedCompareExchangePointer(FIndex^[ARecord16.GetCRC], nil, List);

    // 그 새 데이터가 입력되었다면 바로 삭제 할 수가 없다.
    while not List.IsEmpty do Add(List.RemoveFirst);

    List.Free;
  end;
end;

{ TIndexListItem }

function TIndexListItem.Compare(ACompareTo: TBTreeItem): integer;
var
  CompareTo : TIndexListItem absolute ACompareTo;
begin
  if Record16.GetCRC = CompareTo.Record16.GetCRC then begin
    Result := CompareFastBytesEx(Record16.GetKey, Record16.GetKeySize, CompareTo.Record16.GetKey, CompareTo.Record16.GetKeySize);
  end else begin
    if Record16.GetCRC > CompareTo.Record16.GetCRC then Result := 1
    else Result := -1;
  end;
end;

procedure TIndexListItem.Copy(ACopyTo: TBTreeItem);
begin
  TIndexListItem(ACopyTo).Record16 := Record16;
end;

{ TIndexList }

function TIndexList.Add(ARecord16: IRecord16): boolean;
var
  Item : TIndexListItem;
begin
  Result := false;

  Item := TIndexListItem.Create;
  Item.Record16 := ARecord16;

  FLock.AcquireExclusive;
  try
    if (not FIndex16.FAllowDuplicatedKey) and FBTree.Search(Item) then begin
      Item.Free;
      raise Exception.Create('TIndexList.Add: Duplicated Key.');
    end;

    FBTree.Add(Item);
  finally
    FLock.ReleaseExclusive;
  end;
end;

procedure TIndexList.Clear;
begin
  FLock.AcquireExclusive;
  try
    while not FBTree.IsEmpty do FBTree.RemoveRoot;
  finally
    FLock.ReleaseExclusive;
  end;
end;

constructor TIndexList.Create(AIndex16:TIndex16);
begin
  inherited Create;

  FIndex16 := AIndex16;

  FLock := TSRWLock.Create;
  FBTree := TBTree.Create;
end;

destructor TIndexList.Destroy;
begin
  Clear;

  FreeAndNil(FLock);
  FreeAndNil(FBTree);

  inherited;
end;

function TIndexList.Find(ACRC16: word; AKey: pointer;
  AKeySize: integer): IRecord16;
var
  Record16 : TRecord16;
  Item, SearchResult : TIndexListItem;
begin
  Record16 := TRecord16.Create;
  Item := TIndexListItem.Create;
  try
    Record16.FCRC := ACRC16;
    Record16.FKey := AKey;
    Record16.FKeySize := AKeySize;

    Item.Record16 := Record16;

    FLock.AcquireShared;
    try
      FBTree.Search(Item, TBTreeItem(SearchResult));
      Result := SearchResult.Record16;
    finally
      FLock.ReleaseShared;
    end;
  finally
    Record16.Free;
    Item.Free;
  end;
end;

function TIndexList.IsEmpty: boolean;
begin
  FLock.AcquireShared;
  try
    Result := FBTree.IsEmpty;
  finally
    FLock.ReleaseShared;
  end;
end;

procedure TIndexList.Remove(ARecord16: IRecord16);
var
  Item : TIndexListItem;
begin
  FLock.AcquireExclusive;
  try
    Item := TIndexListItem.Create;
    try
      Item.Record16 := ARecord16;
      FBTree.Remove(Item);
    finally
      Item.Free;
    end;
  finally
    FLock.ReleaseExclusive;
  end;
end;

function TIndexList.RemoveFirst: IRecord16;
begin
  FLock.AcquireExclusive;
  try
    Result := TIndexListItem(FBTree.Root).Record16;
    FBTree.RemoveRoot;
  finally
    FLock.ReleaseExclusive;
  end;
end;

{ TRecord16 }

function TRecord16.GetCRC: word;
begin
  Result := FCRC;
end;

function TRecord16.GetKey: pointer;
begin
  Result := FKey;
end;

function TRecord16.GetKeySize: integer;
begin
  Result := FKeySize;
end;

end.
