| 1 |
{ Copyright (C) 2005 Bas Steendijk and Peter Green
|
| 2 |
For conditions of distribution and use, see copyright notice in zlib_license.txt
|
| 3 |
which is included in the package
|
| 4 |
----------------------------------------------------------------------------- }
|
| 5 |
|
| 6 |
{actually a hashtable. it was a tree in earlier versions}
|
| 7 |
|
| 8 |
unit bsearchtree;
|
| 9 |
|
| 10 |
{$ifdef fpc}
|
| 11 |
{$mode delphi}
|
| 12 |
{$endif}
|
| 13 |
interface
|
| 14 |
|
| 15 |
uses blinklist;
|
| 16 |
|
| 17 |
const
|
| 18 |
hashtable_size=$4000;
|
| 19 |
|
| 20 |
type
|
| 21 |
thashitem=class(tlinklist)
|
| 22 |
hash:integer;
|
| 23 |
s:ansistring;
|
| 24 |
p:pointer;
|
| 25 |
end;
|
| 26 |
thashtable=array[0..hashtable_size-1] of thashitem;
|
| 27 |
phashtable=^thashtable;
|
| 28 |
|
| 29 |
{adds "item" to the tree for name "s". the name must not exist (no checking done)}
|
| 30 |
procedure addtree(t:phashtable;s:ansistring;item:pointer);
|
| 31 |
|
| 32 |
{removes name "s" from the tree. the name must exist (no checking done)}
|
| 33 |
procedure deltree(t:phashtable;s:ansistring);
|
| 34 |
|
| 35 |
{returns the item pointer for s, or nil if not found}
|
| 36 |
function findtree(t:phashtable;s:ansistring):pointer;
|
| 37 |
|
| 38 |
{clear a hashtable, deallocating all used resources}
|
| 39 |
procedure cleartree(t:phashtable);
|
| 40 |
|
| 41 |
implementation
|
| 42 |
|
| 43 |
//FNV-1a hash function
|
| 44 |
function makehash(s:ansistring):integer;
|
| 45 |
const
|
| 46 |
shifter=6;
|
| 47 |
var
|
| 48 |
a,b:integer;
|
| 49 |
h:longword;
|
| 50 |
begin
|
| 51 |
result := 0;
|
| 52 |
b := length(s);
|
| 53 |
h := 216613626;
|
| 54 |
for a := 1 to b do begin
|
| 55 |
h := (h xor byte(s[a])) * 16777619;
|
| 56 |
end;
|
| 57 |
result := h and (hashtable_size-1);
|
| 58 |
end;
|
| 59 |
|
| 60 |
procedure addtree(t:phashtable;s:ansistring;item:pointer);
|
| 61 |
var
|
| 62 |
hash:integer;
|
| 63 |
p:thashitem;
|
| 64 |
begin
|
| 65 |
hash := makehash(s);
|
| 66 |
p := thashitem.create;
|
| 67 |
p.hash := hash;
|
| 68 |
p.s := s;
|
| 69 |
p.p := item;
|
| 70 |
linklistadd(tlinklist(t[hash]),tlinklist(p));
|
| 71 |
end;
|
| 72 |
|
| 73 |
procedure deltree(t:phashtable;s:ansistring);
|
| 74 |
var
|
| 75 |
p,p2:thashitem;
|
| 76 |
hash:integer;
|
| 77 |
begin
|
| 78 |
hash := makehash(s);
|
| 79 |
p := t[hash];
|
| 80 |
p2 := nil;
|
| 81 |
while p <> nil do begin
|
| 82 |
if p.s = s then begin
|
| 83 |
p2 := p;
|
| 84 |
break;
|
| 85 |
end;
|
| 86 |
p := thashitem(p.next);
|
| 87 |
end;
|
| 88 |
linklistdel(tlinklist(t[hash]),tlinklist(p2));
|
| 89 |
p2.destroy;
|
| 90 |
end;
|
| 91 |
|
| 92 |
|
| 93 |
function findtree(t:phashtable;s:ansistring):pointer;
|
| 94 |
var
|
| 95 |
p:thashitem;
|
| 96 |
hash:integer;
|
| 97 |
begin
|
| 98 |
result := nil;
|
| 99 |
hash := makehash(s);
|
| 100 |
p := t[hash];
|
| 101 |
while p <> nil do begin
|
| 102 |
if p.s = s then begin
|
| 103 |
result := p.p;
|
| 104 |
exit;
|
| 105 |
end;
|
| 106 |
p := thashitem(p.next);
|
| 107 |
end;
|
| 108 |
end;
|
| 109 |
|
| 110 |
procedure cleartree(t:phashtable);
|
| 111 |
var
|
| 112 |
hash:integer;
|
| 113 |
p,p2:thashitem;
|
| 114 |
begin
|
| 115 |
for hash := 0 to hashtable_size-1 do begin
|
| 116 |
p := t[hash];
|
| 117 |
while p <> nil do begin
|
| 118 |
p2 := thashitem(p.next);
|
| 119 |
linklistdel(tlinklist(t[hash]),tlinklist(p));
|
| 120 |
p.destroy;
|
| 121 |
p := thashitem(p2);
|
| 122 |
end;
|
| 123 |
end;
|
| 124 |
end;
|
| 125 |
|
| 126 |
end.
|
Parent Directory
| 
Revision Log