src/shared/tests/test_hash.dpr

   1 {$INCLUDE ../a_modes.inc}
   2 // tests for hash table
   3 {$DEFINE EXCESSIVE_CHECKS}
   4 uses
   5   SysUtils,
   6   hashtbl in '../hashtable.pas';
   7
   8 const
   9   MaxItems = 16384;
  10
  11
  12 var
  13   its: array [0..MaxItems-1] of Integer;
  14   marks: array [0..MaxItems-1] of Boolean;
  15   hash: THashIntInt;
  16   i, v, hv: Integer;
  17   del: Boolean;
  18
  19 procedure checkHash (dump: Boolean=false);
  20 var
  21   i, v: Integer;
  22   flag: Boolean;
  23   count: Integer = 0;
  24 begin
  25   if dump then writeln('====== CHECK ======');
  26   for i := 0 to High(its) do
  27   begin
  28     if dump then
  29     begin
  30       v := -1;
  31       flag := hash.get(i, v);
  32       writeln(' check #', i, '; v=', v, '; flag=', flag);
  33     end;
  34     if (its[i] >= 0) then
  35     begin
  36       Inc(count);
  37       if not hash.has(i) then raise Exception.Create('(0.0) fuuuuuuuuuuuu');
  38       if not hash.get(i, v) then raise Exception.Create('(0.1) fuuuuuuuuuuuu');
  39       if (v <> its[i]) then raise Exception.Create('(0.2) fuuuuuuuuuuuu');
  40     end
  41     else
  42     begin
  43       if hash.has(i) then raise Exception.Create('(0.3) fuuuuuuuuuuuu');
  44     end;
  45   end;
  46   if (count <> hash.count) then raise Exception.Create('(0.4) fuuuuuuuuuuuu');
  47   if dump then writeln('------');
  48 end;
  49
  50
  51 procedure testIterator ();
  52 var
  53   i, count: Integer;
  54
  55   function iter (constref k: Integer; constref v: Integer): Boolean;
  56   begin
  57     result := false; // don't stop
  58     //writeln('key=', k, '; value=', v);
  59     if marks[k] then raise Exception.Create('duplicate entry in iterator');
  60     if (its[k] <> v) then raise Exception.Create('invalid entry in iterator');
  61     marks[k] := true;
  62     Inc(count);
  63   end;
  64
  65 begin
  66   count := 0;
  67   for i := 0 to High(marks) do marks[i] := false;
  68   hash.forEach(iter);
  69   if (count <> hash.count) then
  70   begin
  71     writeln('0: count=', count, '; hash.count=', hash.count);
  72     //raise Exception.Create('lost entries in iterator');
  73   end;
  74   count := 0;
  75   for i := 0 to High(marks) do if marks[i] then Inc(count);
  76   if (count <> hash.count) then
  77   begin
  78     writeln('1: count=', count, '; hash.count=', hash.count);
  79     raise Exception.Create('lost entries in iterator');
  80   end;
  81 end;
  82
  83
  84 var
  85   xcount: Integer;
  86 begin
  87   for i := 0 to High(its) do its[i] := -1;
  88
  89   hash := THashIntInt.Create();
  90
  91   Randomize();
  92
  93   writeln('testing: insertion');
  94   xcount := 0;
  95   for i := 0 to MaxItems-1 do
  96   begin
  97     v := Random(MaxItems);
  98     //writeln('i=', i, '; v=', v, '; its[v]=', its[v]);
  99     if (its[v] >= 0) then
 100     begin
 101       if not hash.has(v) then raise Exception.Create('(1.0) fuuuuuuuuuuuu');
 102       if not hash.get(v, hv) then raise Exception.Create('(1.1) fuuuuuuuuuuuu');
 103       if (hv <> its[v]) then raise Exception.Create('(1.2) fuuuuuuuuuuuu');
 104     end
 105     else
 106     begin
 107       its[v] := i;
 108       if hash.put(v, i) then raise Exception.Create('(1.3) fuuuuuuuuuuuu');
 109       Inc(xcount);
 110       if (xcount <> hash.count) then raise Exception.Create('(1.4) fuuuuuuuuuuuu');
 111     end;
 112     {$IFDEF EXCESSIVE_CHECKS}checkHash();{$ENDIF}
 113     {$IFDEF EXCESSIVE_CHECKS}testIterator();{$ENDIF}
 114   end;
 115   if (xcount <> hash.count) then raise Exception.Create('(1.4) fuuuuuuuuuuuu');
 116   checkHash();
 117   testIterator();
 118
 119   writeln('testing: deletion');
 120   for i := 0 to MaxItems*8 do
 121   begin
 122     v := Random(MaxItems);
 123     //writeln('trying to delete ', v, '; its[v]=', its[v]);
 124     del := hash.del(v);
 125     //writeln('  del=', del);
 126     if del then
 127     begin
 128       if (its[v] < 0) then raise Exception.Create('(2.0) fuuuuuuuuuuuu');
 129       Dec(xcount);
 130     end
 131     else
 132     begin
 133       if (its[v] >= 0) then raise Exception.Create('(2.1) fuuuuuuuuuuuu');
 134     end;
 135     its[v] := -1;
 136     if (xcount <> hash.count) then raise Exception.Create('(1.4) fuuuuuuuuuuuu');
 137     hash.compact();
 138     if (xcount <> hash.count) then raise Exception.Create('(1.4) fuuuuuuuuuuuu');
 139     {$IFDEF EXCESSIVE_CHECKS}checkHash();{$ENDIF}
 140     {$IFDEF EXCESSIVE_CHECKS}testIterator();{$ENDIF}
 141     if (hash.count = 0) then break;
 142   end;
 143
 144   writeln('testing: complete');
 145   checkHash();
 146   testIterator();
 147 end.