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