/[lcore]/trunk/bsearchtree.pas
ViewVC logotype

Contents of /trunk/bsearchtree.pas

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations)
Fri Mar 28 02:26:58 2008 UTC (13 years, 6 months ago) by plugwash
File size: 2167 byte(s)
initial import

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 interface
11
12 uses blinklist;
13
14 const
15 hashtable_size=$4000;
16
17 type
18 thashitem=class(tlinklist)
19 hash:integer;
20 s:string;
21 p:pointer;
22 end;
23 thashtable=array[0..hashtable_size-1] of thashitem;
24 phashtable=^thashtable;
25
26 {adds "item" to the tree for name "s". the name must not exist (no checking done)}
27 procedure addtree(t:phashtable;s:string;item:pointer);
28
29 {removes name "s" from the tree. the name must exist (no checking done)}
30 procedure deltree(t:phashtable;s:string);
31
32 {returns the item pointer for s, or nil if not found}
33 function findtree(t:phashtable;s:string):pointer;
34
35 implementation
36
37 function makehash(s:string):integer;
38 const
39 shifter=6;
40 var
41 a,b:integer;
42 begin
43 result := 0;
44 b := length(s);
45 for a := 1 to b do begin
46 result := (result shl shifter) xor byte(s[a]);
47 end;
48 result := (result xor result shr 16) and (hashtable_size-1);
49 end;
50
51 procedure addtree(t:phashtable;s:string;item:pointer);
52 var
53 hash:integer;
54 p:thashitem;
55 begin
56 hash := makehash(s);
57 p := thashitem.create;
58 p.hash := hash;
59 p.s := s;
60 p.p := item;
61 linklistadd(tlinklist(t[hash]),tlinklist(p));
62 end;
63
64 procedure deltree(t:phashtable;s:string);
65 var
66 p,p2:thashitem;
67 hash:integer;
68 begin
69 hash := makehash(s);
70 p := t[hash];
71 p2 := nil;
72 while p <> nil do begin
73 if p.s = s then begin
74 p2 := p;
75 break;
76 end;
77 p := thashitem(p.next);
78 end;
79 linklistdel(tlinklist(t[hash]),tlinklist(p2));
80 p2.destroy;
81 end;
82
83
84 function findtree(t:phashtable;s:string):pointer;
85 var
86 p:thashitem;
87 hash:integer;
88 begin
89 result := nil;
90 hash := makehash(s);
91 p := t[hash];
92 while p <> nil do begin
93 if p.s = s then begin
94 result := p.p;
95 exit;
96 end;
97 p := thashitem(p.next);
98 end;
99 end;
100
101 end.

Properties

Name Value
svn:executable

No admin address has been configured">No admin address has been configured
ViewVC Help
Powered by ViewVC 1.1.26