hashtable.inc_pas

来自「delphi的范型代码库」· INC_PAS 代码 · 共 752 行 · 第 1/2 页

(*
 * 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
//------------------------------------------------------------------------------

{$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;

procedure _THashTableBase.Clear;
var
  i         : integer;
  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 FAlwaysReserveSize<=0 then
  begin
    if FCapacity=0 then
      self.FCapacity:=1 shl 5;
    self.FDataList:=nil;
  end
  else
  begin
    FCapacity:=FAlwaysReserveSize;
    i:=length(FDataList);
    if FAlwaysReserveSize<i then
      i:=FAlwaysReserveSize;
    fillchar((@FDataList[0])^,i*sizeof(_PHashNode),0);
  end;
  self.FHashMask:=self.FCapacity-1;
  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
  pPHashNode: _PPHashNode ;
begin
  pPHashNode:=self.FindItem(Key).pPNode;
  if (pPHashNode^<>nil) then
    result:=(pPHashNode^).Value
  else
    raise EHashKeyRangeError.Create(csHashKey_Error);
    //raise EHashKeyRangeError.Create();
end;


procedure _THashTableBase.SetCapacity(NewCapacity: integer);
var
  OldDataList : array of _PHashNode;
  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;
  function To2Power(x :integer):integer;
  var
    powi : integer;
  begin
    Assert(x>0);
    if x=1 then
      result:=2
    else
    begin
      //下面与此等价：result:=Round(math.IntPower(2,1+math.Floor(log2(x-1))));
      powi:=0;
      while (x>0) do
      begin
        x:=x shr 1;
        inc(powi);
      end;
      result:=1 shl powi;
      if result<x then result:=result shl 1;
    end;
  end;
begin
  self.FCapacity:=To2Power(NewCapacity);
  self.FHashMask:=self.FCapacity-1;

  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);

  //
  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;
begin
  result.ArrayIndex:=(_HashValue(Key)) and (self.FHashMask);
  result.pPNode:=@self.FDataList[result.ArrayIndex];
  if (result.pPNode^<>nil) then //节点还没有使用
  begin
    repeat
      {$ifdef _DGL_Compare_Key}
      if (_IsEqual_Key(Key,(result.pPNode^).Key)) then  //找到
      {$else}
      if ((Key=(result.pPNode^).Key)) then  //找到
      {$endif}
      begin
        exit;
      end;
      result.pPNode:=@(result.pPNode^).PNext;
    until (result.pPNode^=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 : array of _PHashNode;
begin

  tempi:=self.FCount;
  self.FCount:=HastTable.FCount;
  HastTable.FCount:=tempi;

  tempi:=self.FCapacity;
  self.FCapacity:=HastTable.FCapacity;
  HastTable.FCapacity:=tempi;

  tempi:=self.FHashMask;
  self.FHashMask:=HastTable.FHashMask;
  HastTable.FHashMask:=tempi;

  //tempArray:=self.FDataList;
  setlength(tempArray,length(self.FDataList));
  for tempi:=low(self.FDataList) to high(self.FDataList) do
    tempArray[tempi]:=self.FDataList[tempi];
  //self.FDataList:=HastTable.FDataList;
  setlength(self.FDataList,length(HastTable.FDataList));
  for tempi:=low(HastTable.FDataList) to high(HastTable.FDataList) do
    self.FDataList[tempi]:=HastTable.FDataList[tempi];
  //HastTable.FDataList:=tempArray;
  setlength(HastTable.FDataList,length(tempArray));
  for tempi:=low(tempArray) to high(tempArray) do
    HastTable.FDataList[tempi]:=tempArray[tempi];
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:=high(self.FDataList);
  result.pPNode:=nil;
end;

procedure _THashTableBase.AlwaysReserve(const aAlwaysReserveSize: integer);
begin
  self.Reserve(aAlwaysReserveSize);
  FAlwaysReserveSize:=FCapacity;
end;

procedure _THashTableBase.Reserve(const ReserveSize: integer);
begin
  if ReserveSize>self.FCount then
  begin
    self.SetCapacity(ReserveSize);
  end;
end;

function _THashTableBase.Size: integer;
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;