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

Annotation of /trunk/bsearchtree.pas

Parent Directory Parent Directory | Revision Log Revision Log


Revision 79 - (hide annotations)
Tue Feb 16 22:51:30 2010 UTC (10 years, 5 months ago) by zipplet
File size: 2199 byte(s)
Merged with delphi 2010 branch
1 plugwash 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 zipplet 79 s:ansistring;
21 plugwash 1 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 zipplet 79 procedure addtree(t:phashtable;s:ansistring;item:pointer);
28 plugwash 1
29     {removes name "s" from the tree. the name must exist (no checking done)}
30 zipplet 79 procedure deltree(t:phashtable;s:ansistring);
31 plugwash 1
32     {returns the item pointer for s, or nil if not found}
33 zipplet 79 function findtree(t:phashtable;s:ansistring):pointer;
34 plugwash 1
35     implementation
36    
37 zipplet 79 function makehash(s:ansistring):integer;
38 plugwash 1 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 zipplet 79 procedure addtree(t:phashtable;s:ansistring;item:pointer);
52 plugwash 1 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 zipplet 79 procedure deltree(t:phashtable;s:ansistring);
65 plugwash 1 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 zipplet 79 function findtree(t:phashtable;s:ansistring):pointer;
85 plugwash 1 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:eol-style CRLF

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