DEADSOFTWARE

cosmetix
[d2df-sdl.git] / 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';
8 const
9 MaxItems = 16384;
12 {
13 function hequ (constref a, b: Integer): Boolean; begin result := (a = b); end;
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 }
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;
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;
63 procedure testIterator ();
64 var
65 i, count: Integer;
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;
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;
96 var
97 xcount: Integer;
98 begin
99 for i := 0 to High(its) do its[i] := -1;
101 //hash := THashInt.Create(hhash, hequ);
102 hash := hashNewIntInt();
104 Randomize();
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();
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;
157 writeln('testing: complete');
158 checkHash();
159 testIterator();
160 end.