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

Annotation of /trunk/bsearchtree.pas

Parent Directory Parent Directory | Revision Log Revision Log


Revision 64 - (hide annotations)
Fri Feb 5 03:32:29 2010 UTC (10 years, 6 months ago) by plugwash
File size: 2167 byte(s)
remove executable property

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     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:eol-style CRLF

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