unit dhashbucket;

{$MODE FPC}
{$MODESWITCH DEFAULTPARAMETERS}
{$MODESWITCH OUT}
{$MODESWITCH RESULT}

interface

type
generic THashBucket<TKey, TKeyManager, TValue, TAllocator> = object
private type
  PItem = ^TItem;
  TItem = record
    Hash: PtrUInt;
    Key: TKey;
    Value: TValue;
    Next: PItem;
  end;
public type
  TStats = record
    Count: SizeUInt;
    Collisions: SizeUInt;
    AllocatedSize: SizeUInt;
    Size: SizeUInt;
  end;
private
  FList: PItem;
  FKeyManager: TKeyManager;
  FAllocator: TAllocator;
public
  procedure Init;
  procedure Done;
  procedure Clear;
  function Find(H: PtrUInt; const Key: TKey; out Value: TValue): Boolean;
  function Put(H: PtrUInt; const Key: TKey; Value: TValue): Boolean;
  function Remove(H: PtrUInt; const Key: TKey): Boolean;
end;

implementation

procedure THashBucket.Init;
begin
  FAllocator.Init;
  FKeyManager.Init;
  FList := nil;
end;

procedure THashBucket.Done;
begin
  Clear;
  FKeyManager.Done;
  FAllocator.Done;
end;

procedure THashBucket.Clear;
var
  It, Next: PItem;
begin
  It := FList;
  while It <> nil do begin
    Next := It^.Next;
    FKeyManager.Finalize(It^.Key);
    FAllocator.FreeMem(It);
    It := Next;
  end;
  FList := nil;
end;

function THashBucket.Find(H: PtrUInt; const Key: TKey; out Value: TValue): Boolean;
var
  It: PItem;
begin
  It := FList;
  while It <> nil do begin
    if (H = It^.Hash) and (FKeyManager.Compare(Key, It^.Key) = 0) then begin
      Value := It^.Value;
      Exit(True);
    end;
    It := It^.Next;
  end;
  Exit(False);
end;

function THashBucket.Put(H: PtrUInt; const Key: TKey; Value: TValue): Boolean;
var
  It: PItem;
begin
  It := FList;
  while It <> nil do begin
    if (H = It^.Hash) and (FKeyManager.Compare(Key, It^.Key) = 0) then begin
      It^.Value := Value;
      Exit(True);
    end;
    It := It^.Next;
  end;
  It := FAllocator.GetMem(SizeOf(TItem));
  if It = nil then
    Exit(False);
  It^.Hash := H;
  FKeyManager.Initialize(It^.Key);
  FKeyManager.Assign(It^.Key, Key);
  It^.Value := Value;
  Exit(True);
end;

function THashBucket.Remove(H: PtrUInt; const Key: TKey): Boolean;
var
  It, Next: PItem;
begin
  Result := False;
  It := FList;
  while It <> nil do begin
    if (H = It^.Hash) and (FKeyManager.Compare(Key, It^.Key) = 0) then begin
      Next := It^.Next;
      if FList = It then
        FList := Next;
      FKeyManager.Finalize(It^.Key);
      FAllocator.FreeMem(It);
      It := Next;
      Result := True;
    end else
      It := It^.Next;
  end;
end;

end.
