u_hashtable.pas

linux program to read packet data

(*
 * One Way Network Sniffer (OWNS)
 * Copyright (C) 2001-2002 OWNS
 *
 * http://owns.sourceforge.net/
 * http://www.owns.st
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *)
(*
 * $Id: u_HashTable.pas,v 1.2 2001/08/10 11:07:00 owns Exp $
 * a structure of type THashTable will contain the TCP connections
 *)
unit u_HashTable;
interface
uses u_DebugPacket,Sysutils,u_ConnectionTCP, u_TCPPacket;



type
// Values for hash table operations.
  THashInsertValues = (hashInsertOk, hashInsertTableFull,
                       hashInsertDuplicateKey);

  TMethodIterator = procedure(const Obj : TObject;const index : LongInt) of object;

  THashTypeArray = array [0..1000000] of TConnectionTCP;
  PHashTypeArray = ^THashTypeArray;

  // A hash table with open addressing and linear probing.
  THashTable = class(TObject)
  private
    HashTable : PHashTypeArray;
    NumItems  : Longint;
    NumUsed   : Longint;
    function getValue(p_Index : LongInt) : TConnectionTCP;
    function areKeysEqual(p_ConnectionTCP1 : TConnectionTCP;p_ConnectionTCP2 : TConnectionTCP) : boolean;
  public
    constructor Create(size : Longint);
    destructor Destroy; override;
    function AddItemLinear(p_ConnectionTCP: TConnectionTCP): THashInsertValues;
    function FindItemLinear(p_TCPPacket: TTCPPacket) : LongInt;
    function AddItemRandom(p_ConnectionTCP: TConnectionTCP): THashInsertValues;
    function FindItemRandom(p_TCPPacket: TTCPPacket) : LongInt;
    function deleteValue(p_Index : LongInt) : TConnectionTCP;
    procedure ForEachCallMethod(const ProcIterator : TMethodIterator);
    property value[p_Index : LongInt] : TConnectionTCP read getValue;
  end;

implementation


// Allocate the hash table.
constructor THashTable.Create(size: Longint);
var
  i : Longint;
begin
   inherited Create;

   // Allocate the hash table entries.
  NumUsed := 0;
  NumItems := size;
  GetMem(HashTable, NumItems * SizeOf(Pointer));

   // Initialize the hash table entries to Unassigned.
   for i := 0 to NumItems - 1 do
    HashTable[i] := nil;
end;

// Free the hash table.
// free all the members of the hashtable too
destructor THashTable.Destroy;
var
  i : Longint;
begin
   if (HashTable <> nil) then
   begin
     for i := 0 to NumItems - 1 do
       HashTable[i].free;
    FreeMem(HashTable);
   end;
   inherited Destroy;
end;

function THashTable.areKeysEqual(p_ConnectionTCP1 : TConnectionTCP;p_ConnectionTCP2 : TConnectionTCP) : boolean;
begin
  result := (p_ConnectionTCP1.keySrc = p_ConnectionTCP2.KeySrc) and (p_ConnectionTCP1.keyDest = p_ConnectionTCP2.KeyDest);
end;

// Add an item into the hash table. Return hashInsertOk,
// hashInsertTableFull, or hashInsertDuplicateKey to
// indicate our success or failure.
function THashTable.AddItemLinear(p_ConnectionTCP : TConnectionTCP): THashInsertValues;
var
  probe : Longint;
begin
   // Make sure there is room.
   if (NumUsed >= NumItems) then
     begin
       // The table is full.
       result := hashInsertTableFull;
     end
   else
     begin
       // Find the first probe sequence value.
      probe := p_ConnectionTCP.hashValue mod NumItems;

       // While that position is occupied, try the next one.
       while (HashTable[probe] <> nil) do
       begin
        // Make sure this key value is not already in use.
        if (areKeysEqual(HashTable^[probe],p_ConnectionTCP)) then
          Break;
        // Check the next position in the probe sequence.
        probe := (probe + 1) mod NumItems;
       end;

       // See if we found an empty position.
       if (HashTable[probe] = nil) then
        begin
          // Insert the item.
          HashTable[probe] := p_ConnectionTCP;
          Result := hashInsertOk;
          // Keep track of the number of entries used.
          NumUsed := NumUsed + 1;
        end
      else
        begin
          // The key is already used.
          Result := hashInsertDuplicateKey;
        end;
     end; // End (NumUsed >= NumItems) ... else ...
end; // End function AddItem.


// Find an item in the hash table. Return the item's
// value or Unassigned if it is not here.
function THashTable.FindItemLinear(p_TCPPacket: TTCPPacket) : LongInt;
var
  trial, probe: Longint;
begin
   // Find the first probe sequence value.
  probe := p_TCPPacket.HashValue mod NumItems;

   // Search positions until we find the target, an entry
   // that is unused, or we have checked the entire table.
   for trial := 1 to NumItems do begin
     // See if this entry is unused.
     if (HashTable[probe] = nil) then
     begin
       result := -1; exit;
     end;
     // See if this entry is the target.
     if (HashTable[probe].isSameConnection(p_TCPPacket)) then
     begin
       result := probe; exit;
     end;
      Break;
     // Consider the next item in the probe sequence.
    probe := (probe + 1) mod NumItems;
   end;

   result := -1;
end;

// get the TCPConnection at index. The caller is now responsible for freeing it.
// This value is not in the hashtable anymore
function THashTable.deleteValue(p_Index : LongInt) : TConnectionTCP;
begin
  result := HashTable[p_Index];
  HashTable[p_Index] := nil;
end;

// for each tcp connection in the hashtable, call ProcIterator
procedure THashTable.ForEachCallMethod(const ProcIterator : TMethodIterator);
var
  i : Longint;
begin
  for i := 0 to NumItems - 1 do
  begin
    if (Value[i] <> nil) then
      ProcIterator(Value[i],i);
  end;
end;

// Add an item into the hash table. Return hashInsertOk,
// hashInsertTableFull, or hashInsertDuplicateKey to
// indicate our success or failure.
function THashTable.AddItemRandom(p_ConnectionTCP: TConnectionTCP): THashInsertValues;
var
  trial, probe: Longint;
begin
  // Initialize the random number generator for the key.
  RandSeed := p_ConnectionTCP.HashValue;

  // Try up to NumItems times to find an open position or this key.
  for trial := 1 to NumItems do
  begin
    // Find the next probe sequence value.
    probe := (p_ConnectionTCP.HashValue + Random(NumItems)) mod NumItems;

    // See if the position is unoccupied.
    if (HashTable[probe] = nil) then
    begin
      // It is. Take this position.
      HashTable[probe] := p_ConnectionTCP;
      Result := hashInsertOk;
      Exit;
    end;

    // See if this is the target key.
    if (areKeysEqual(HashTable[probe],p_ConnectionTCP)) then
    begin
      // It is. The key is already here.
      Result := hashInsertDuplicateKey;
      Exit;
    end;

  end;

  // If we get here, we failed to find room.
  Result := hashInsertTableFull;
end; // End function AddItem.

// Find an item in the hash table. Return the item's
// value or Unassigned if it is not here.
function THashTable.FindItemRandom(p_TCPPacket: TTCPPacket) : LongInt;
var
  trial, probe : Longint;
begin
   // Initialize the random number generator for the key.
  RandSeed := p_TCPPacket.HashValue;

  // Search positions until we find the target, an entry
  // that is unused, or we have tried NumItems times.
  for trial := 1 to NumItems do
  begin
    // Calculate the next probe sequence value.
    probe := (p_TCPPacket.HashValue + Random(NumItems)) mod NumItems;

    // See if this entry is unused.
    if (HashTable[probe] = nil) then
    begin
      // The value is not here. Return Unassigned.
      result := -1;
      Exit;
    end;

    // See if this entry is the target.
    if (HashTable[probe].isSameConnection(p_TCPPacket)) then
    begin
      // We found it. Return the value.
      result := probe;
      Exit;
    end;

  end;
  // If we get here, we failed to find the item.
  result := -1;
end;

// get the tcpCOnnection at index. This tcpconnection still belongs to the hashtable
function THashTable.getValue(p_Index : LongInt) : TConnectionTCP;
begin
  if (p_Index = -1) then
    result := nil
  else
  begin
    result := HashTable[p_Index];
  end;
end;

end.