_hashtable.inc_pas

Delphi Generic Algorytms library - Maps, Lists, Hashmaps, Datastructures.

(*
 * DGL(The Delphi Generic Library)
 *
 * Copyright (c) 2004
 * [e-mail]
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 *)
        
//------------------------------------------------------------------------------
// _THashTableBase\_THashBaseIterator的实现
// Create by HouSisong, 2004.03.05
//------------------------------------------------------------------------------

//_HashTable.inc_pas ; _HashTable.inc_h

{$ifndef __HashTable_inc_pas_}
{$define __HashTable_inc_pas_}

{$I DGLIntf.inc_pas}


{ _THashTableBase }

procedure _THashTableBase.UniqueInsert(const Key: _HashKeyType;const Value: _HashValueType);
begin
  self.UniqueInsertNode(FindItem(Key).pPNode,Key,Value);
end;

procedure  _THashTableBase.DisposeNode(const PHashNode: _PHashNode);
begin
  {$ifdef _DGL_ObjValue_Key}
  _Free_Key(PHashNode.Key);
  {$endif}
  {$ifdef _DGL_ObjValue_Value}
    if not F_DGL_OnlySet then
      _Free_Value(PHashNode.Value);
  {$endif}

  if F_DGL_OnlySet then
    system.Dispose(_PHashNode_OnlySet(PHashNode))
  else
    system.Dispose(PHashNode);

  //dec(testTHashNodeCount);
end;



function GetBigHashCapacityIndex(const Capacity:Cardinal;const CapacityIndex:Byte=_csDefaultHashCapacityIndex):Byte;
var
  i : integer;
begin
  Assert(Capacity<=_csHashCapacityList[high(_csHashCapacityList)]);
  for i:=CapacityIndex to high(_csHashCapacityList) do
  begin
    if _csHashCapacityList[i]>=Capacity then
    begin
      result:=i;
      exit;
    end;
  end;
  result:=_csDefaultHashCapacityIndex;
end;

procedure _THashTableBase.Clear;
var
  i         : Cardinal;
  PNode     : _PHashNode;
  PNodeTemp : _PHashNode;
begin
  if (self.FCount>0) then
  begin
    for i:=low(self.FDataList) to high(self.FDataList) do
    begin
      PNode:=self.FDataList[i];
      while (PNode<>nil) do
      begin
        PNodeTemp:=PNode.PNext;
        DisposeNode(PNode);
        PNode:=PNodeTemp;
      end;
    end;
  end;
  self.FCount:=0;

  if FAlwaysReserveIndex=0 then
  begin
    FCapacityIndex:=_csDefaultHashCapacityIndex;
    self.FCapacity:=_csHashCapacityList[FCapacityIndex];
    self.FDataList:=nil;
  end
  else
  begin
    FCapacityIndex:=FAlwaysReserveIndex;
    self.FCapacity:=_csHashCapacityList[FCapacityIndex];
    i:=length(FDataList);
    if FCapacity<i then
      i:=FCapacity;
    fillchar((@FDataList[0])^,i*sizeof(_PHashNode),0);
  end;
  setlength(self.FDataList,self.FCapacity);
end;

constructor _THashTableBase.Create(const IsOnlySet : boolean);
begin
  inherited Create;
  self.F_DGL_OnlySet:=IsOnlySet;
  self.Clear();
end;

destructor _THashTableBase.Destroy;
begin
  self.Clear();
  inherited;
end;

function _THashTableBase.GetItemValue(const Key: _HashKeyType): _HashValueType;
var
  PHashNode: _PHashNode ;
begin
  PHashNode:=self.FindItem(Key).pPNode^;
  if (PHashNode<>nil) then
    result:=PHashNode.Value
  else
    raise EHashKeyRangeError.Create(csHashKey_Error);
    //raise EHashKeyRangeError.Create();
end;


procedure _THashTableBase.SetCapacityIndex(const NewCapacityIndex: Byte);
var
  OldDataList : _TPHashNodeDArray;
  pNode       : _PHashNode;
  pNodeTemp   : _PHashNode;
  i           : integer;

  procedure   move_insert(pMoveNode : _PHashNode);
  var
    pPHashNode: _PPHashNode ;
  begin
    pPHashNode:=self.FindItem(pMoveNode.Key).pPNode;
    pMoveNode.PNext:=pPHashNode^;
    pPHashNode^:=pMoveNode;
  end;
begin
  FCapacityIndex:=NewCapacityIndex;
  self.FCapacity:=_csHashCapacityList[FCapacityIndex];

  //setlength(OldDataList,length(self.FDataList));
  //for i:=low(OldDataList) to high(OldDataList) do
  //  OldDataList[i]:=self.FDataList[i];
  //setlength(self.FDataList,0);
  //setlength(self.FDataList,FCapacity);
  OldDataList:=FDataList;
  FDataList:=nil;
  setlength(self.FDataList,FCapacity);

  //
  for i:=low(OldDataList) to high(OldDataList) do
  begin
    pNode:=OldDataList[i];
    while (pNode<>nil) do
    begin
      pNodeTemp:=PNode.PNext;
      move_insert(PNode);
      PNode:=pNodeTemp;
    end;
  end;
end;

//找到返回节点指针
//没有找到返回插入位置节点指针
function _THashTableBase.FindItem(const Key: _HashKeyType):_TTagHashIterator;
var
  PNode : _PHashNode;
begin                             //1103515245 or 41 or 1
  result.ArrayIndex:=( {$ifdef _DGL_NotHashFunction}1*Cardinal
       {$else}_HashValue{$endif}(Key)) mod self.FCapacity;
  result.pPNode:=@self.FDataList[result.ArrayIndex];
  PNode:=result.pPNode^;
  if (PNode<>nil) then //节点还没有使用
  begin
    repeat
      {$ifdef _DGL_Compare_Key}
      if (_IsEqual_Key(Key,PNode.Key)) then  //找到
      {$else}
      if ((Key=PNode.Key)) then  //找到
      {$endif}
      begin
        exit;
      end;
      result.pPNode:=@PNode.PNext;
      PNode:=result.pPNode^;
    until (PNode=nil);
  end;
end;


procedure _THashTableBase.DeleteNode(const pPHashNode: _PPHashNode);
var
  ptmpNode : _PHashNode;
begin
  if (pPHashNode^<>nil) then
  begin
    ptmpNode:= (pPHashNode^).PNext;
    DisposeNode(pPHashNode^);
    pPHashNode^:=ptmpNode;
    dec(self.FCount);
  end
  else
    raise EHashKeyRangeError.Create(csHashKey_Error);
    //raise EHashKeyRangeError.Create();
end;

procedure _THashTableBase.MultiInsert(const Key: _HashKeyType;const Value: _HashValueType);
begin
  self.MultiInsertNode(FindItem(Key).pPNode,Key,Value);
end;

procedure _THashTableBase.Swap(HastTable: _THashTableBase);
var
  tempi     : integer;
  tempArray : _TPHashNodeDArray;
begin
  if self=HastTable then exit;
  
  Assert(F_DGL_OnlySet=HastTable.F_DGL_OnlySet);
  //tempi:=FAlwaysReserveIndex; FAlwaysReserveIndex:=HastTable.FAlwaysReserveIndex; HastTable.FAlwaysReserveIndex:=tempi;

  tempi:=FCount;  FCount:=HastTable.FCount; HastTable.FCount:=tempi;
  tempi:=FCapacityIndex; FCapacityIndex:=HastTable.FCapacityIndex; HastTable.FCapacityIndex:=tempi;
  tempi:=FCapacity; FCapacity:=HastTable.FCapacity; HastTable.FCapacity:=tempi;
  tempArray:=FDataList; FDataList:=HastTable.FDataList; HastTable.FDataList:=tempArray;
end;


function _THashTableBase.ItBegin: _TTagHashIterator;
var
  i :integer;
begin
  for i:=low(self.FDataList) to high(self.FDataList) do
  begin
    if (self.FDataList[i]<>nil) then
    begin
      result.ArrayIndex:=i;
      result.pPNode:=@self.FDataList[i];
      exit;
    end;
  end;
  result.ArrayIndex:=high(self.FDataList);
  result.PPNode:=nil;
end;

function _THashTableBase.ItEnd: _TTagHashIterator;
begin
  result.ArrayIndex:=FCapacity-1;
  result.pPNode:=nil;
end;


procedure _THashTableBase.SetAlwaysReserve(const aAlwaysReserveSize: Cardinal);
begin
  FAlwaysReserveIndex:=GetBigHashCapacityIndex(aAlwaysReserveSize);
  self.Reserve(_csHashCapacityList[FAlwaysReserveIndex]);
end;

function _THashTableBase.getAlwaysReserveSize():Cardinal;
begin
  if FAlwaysReserveIndex=0 then
    result:=0
  else
    result:=_csHashCapacityList[FAlwaysReserveIndex];
end;

procedure _THashTableBase.Reserve(const ReserveSize: Cardinal);
begin
  if ReserveSize>self.FCapacity then
    self.SetCapacityIndex(GetBigHashCapacityIndex(ReserveSize,FCapacityIndex));
end;

function _THashTableBase.Size: Cardinal;
begin
  result:=self.FCount;
end;

procedure _THashTableBase.MultiInsert(const Key: _HashKeyType);
begin
  self.MultiInsertNode(FindItem(Key).pPNode,Key);
end;

procedure _THashTableBase.UniqueInsert(const Key: _HashKeyType);
begin
  self.UniqueInsertNode(FindItem(Key).pPNode,Key);
end;

procedure _THashTableBase.UniqueInsertNode(pPHashNode: _PPHashNode;
  const Key: _HashKeyType);
begin
  if (pPHashNode^=nil) then
    self.MultiInsertNode(pPHashNode,Key)
  else
  begin   //replace key
    {$ifdef _DGL_ObjValue_Key}
    _Assign_Key(pPHashNode^.Key,Key);
    {$else}
    pPHashNode^.Key:=Key;
    {$endif}
  end;
end;

function _THashTableBase.Count(const Key: _HashKeyType): integer;
var
  ItBegin,ItEnd: _TTagHashIterator;
begin
  result:=self.CountRange(Key,ItBegin,ItEnd);
end;

procedure _THashTableBase.EqualRange(const Key: _HashKeyType; out ItBegin,
  ItEnd: _TTagHashIterator);
begin
  self.CountRange(Key,ItBegin,ItEnd);
end;


function _DGL_Int_Min_HashTableBase(const x,y:integer):integer;  {$ifdef _DGL_Inline} inline; {$endif}
begin
  if x<y then
    result:=x
  else
    result:=y;
end;

procedure _THashTableBase.Erase(const ItBegin, ItEnd: _IIterator);
var
  It0,It1:_TTagHashIterator;
  tmp :_PHashNode;
  i : integer;
  MinIndex : integer;
begin
  It0:=_PtmpHashIt_Data(@ItBegin).FNodeIt;
  if self.IsEndIt(It0) then exit;
  It1:=_PtmpHashIt_Data(@ItEnd).FNodeIt;
  while true do
  begin
    if It0.ArrayIndex=It1.ArrayIndex then
    begin  //It1.pPNode<>nil
      tmp:=It1.pPNode^;
      while It0.pPNode^<>tmp do
      begin
        self.DeleteNode(It0.pPNode);
      end;
      DecCapacity();
      exit;   //出口
    end
    else
    begin
      while (It0.pPNode^<>nil)  do
        self.DeleteNode(It0.pPNode);
      MinIndex:=_DGL_Int_Min_HashTableBase(high(self.FDataList),It1.ArrayIndex);
      for i:=It0.ArrayIndex+1 to MinIndex do
      begin
        if self.FDataList[i]<>nil then
        begin
          It0.ArrayIndex:=i;
          It0.pPNode:=@self.FDataList[i];
        end;
      end;

    end;