unit dhashmapsimple;

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

interface

type
THashMapSimple = object
public type
  TKey = AnsiString;
  TValue = Pointer;
public
  procedure Init;
  procedure Done;
  procedure Clear;
  function Put(const Key: TKey; const Value: TValue): Boolean;
  procedure Remove(const Key: TKey);
  function Find(const Key: TKey; out Value: TValue): Boolean;
private
  FTable: Pointer;
  FSize: SizeUInt;
end;

implementation

function _djb2(Key, KeyEnd: PAnsiChar; Hash: UInt32): UInt32;
begin
  while Key < KeyEnd do begin
    Hash := ((Hash shl 5) + Hash) + Ord(Key^); // hash * 33 + c
    Inc(Key);
  end;
  Exit(Hash);
end;

function GetHash(const Key: THashMapSimple.TKey): UInt32; inline;
begin
  Exit(_djb2(@Key[1], @Key[1] + Length(Key), 5381));
end;

type
PEntry = ^TEntry;
TEntry = record
  Hash: UInt32;
  Key: THashMapSimple.TKey;
  Value: THashMapSimple.TValue;
  Next: PEntry;
end;

PBucket = ^PEntry;

function _AllocateTable(Size: SizeUInt; Table, TableEnd: PBucket): PBucket;
begin
  if Size = 0 then
    Exit(nil);
  Size := Size * SizeOf(TBucket);
  Table := GetMem(Size);
  TableEnd := Pointer(Table) + Size;
  Result := Table;
  while Table < TableEnd do begin
    Table^ := nil;
    Inc(Table);
  end;
end;

procedure PutEntry(Entry: PEntry; Dst: PBucket; DstLength: SizeUInt); inline;
begin
  Dst := Dst + (Entry^.Hash mod DstLength);
  Entry^.Next := Dst^;
  Dst^ := Entry;
end;

procedure Rehash(Src, SrcEnd, Dst: PBucket; DstLength: SizeUInt);
var
  Entry, Next: PEntry;
begin
  while Src < SrcEnd do begin
    Entry := Src^;
    while Entry <> nil do begin
      Next := Entry^.Next;
      PutEntry(Src^, Dst, DstEnd);
      Entry := Next;
    end;
    Inc(Src);
  end;
end;

function ReallocTable(Table: PBucket; OldSize, NewSize: SizeUInt): PBucket;
var
  NewTable: PBucket;
begin
  if OldSize = NewSize then
    Exit(Table);
  if NewSize = 0 then begin
    FreeMem(Table);
    Exit(nil);
  end;
  NewTable := _AllocateTable(Table, NewSize);
  if (Table = nil) or (OldSize = 0) then
    Exit(NewTable);
  Rehash(Table, Table + OldSize, NewTable, NewSize);
  Exit(NewTable);
end;

procedure THashMapSimple.Init;
begin
  FTable := nil;
end;

procedure THashMapSimple.Done;
begin
  if FTable <> nil then
    Clear;
end;

procedure THashMapSimple.Clear;
begin
end;

function THashMapSimple.Put(const Key: TKey; const Value: TValue): Boolean;
begin
end;

procedure THashMapSimple.Remove(const Key: TKey);
begin
end;

function THashMapSimple.Find(const Key: TKey; out Value: TValue): Boolean;
begin
end;

end.
