|
|
1 # include "dgd.h"
2 # include "hash.h"
3
4 /*
5 * Generic string hash table.
6 */
7
8 char strhashtab[] = {
9 '\001', '\127', '\061', '\014', '\260', '\262', '\146', '\246',
10 '\171', '\301', '\006', '\124', '\371', '\346', '\054', '\243',
11 '\016', '\305', '\325', '\265', '\241', '\125', '\332', '\120',
12 '\100', '\357', '\030', '\342', '\354', '\216', '\046', '\310',
13 '\156', '\261', '\150', '\147', '\215', '\375', '\377', '\062',
14 '\115', '\145', '\121', '\022', '\055', '\140', '\037', '\336',
15 '\031', '\153', '\276', '\106', '\126', '\355', '\360', '\042',
16 '\110', '\362', '\024', '\326', '\364', '\343', '\225', '\353',
17 '\141', '\352', '\071', '\026', '\074', '\372', '\122', '\257',
18 '\320', '\005', '\177', '\307', '\157', '\076', '\207', '\370',
19 '\256', '\251', '\323', '\072', '\102', '\232', '\152', '\303',
20 '\365', '\253', '\021', '\273', '\266', '\263', '\000', '\363',
21 '\204', '\070', '\224', '\113', '\200', '\205', '\236', '\144',
22 '\202', '\176', '\133', '\015', '\231', '\366', '\330', '\333',
23 '\167', '\104', '\337', '\116', '\123', '\130', '\311', '\143',
24 '\172', '\013', '\134', '\040', '\210', '\162', '\064', '\012',
25 '\212', '\036', '\060', '\267', '\234', '\043', '\075', '\032',
26 '\217', '\112', '\373', '\136', '\201', '\242', '\077', '\230',
27 '\252', '\007', '\163', '\247', '\361', '\316', '\003', '\226',
28 '\067', '\073', '\227', '\334', '\132', '\065', '\027', '\203',
29 '\175', '\255', '\017', '\356', '\117', '\137', '\131', '\020',
30 '\151', '\211', '\341', '\340', '\331', '\240', '\045', '\173',
31 '\166', '\111', '\002', '\235', '\056', '\164', '\011', '\221',
32 '\206', '\344', '\317', '\324', '\312', '\327', '\105', '\345',
33 '\033', '\274', '\103', '\174', '\250', '\374', '\052', '\004',
34 '\035', '\154', '\025', '\367', '\023', '\315', '\047', '\313',
35 '\351', '\050', '\272', '\223', '\306', '\300', '\233', '\041',
36 '\244', '\277', '\142', '\314', '\245', '\264', '\165', '\114',
37 '\214', '\044', '\322', '\254', '\051', '\066', '\237', '\010',
38 '\271', '\350', '\161', '\304', '\347', '\057', '\222', '\170',
39 '\063', '\101', '\034', '\220', '\376', '\335', '\135', '\275',
40 '\302', '\213', '\160', '\053', '\107', '\155', '\270', '\321',
41 };
42
43 /*
44 * NAME: hashtab->new()
45 * DESCRIPTION: create a hashtable of size "size", where "maxlen" characters
46 * of each string are significant
47 */
48 hashtab *ht_new(size, maxlen)
49 register unsigned int size;
50 unsigned int maxlen;
51 {
52 register hashtab *ht;
53
54 ht = (hashtab *) ALLOC(char, sizeof(hashtab) + sizeof(hte*) * (size - 1));
55 ht->size = size;
56 ht->maxlen = maxlen;
57 memset(ht->table, '\0', size * sizeof(hte*));
58
59 return ht;
60 }
61
62 /*
63 * NAME: hashtab->del()
64 * DESCRIPTION: delete a hash table
65 */
66 void ht_del(ht)
67 hashtab *ht;
68 {
69 FREE(ht);
70 }
71
72 /*
73 * NAME: hashstr()
74 * DESCRIPTION: Hash string s, considering at most len characters. Return
75 * an unsigned modulo size.
76 * Based on Peter K. Pearson's article in CACM 33-6, pp 677.
77 */
78 unsigned short hashstr(s, len)
79 register char *s;
80 register unsigned int len;
81 {
82 register char h, l;
83
84 h = l = 0;
85 while (*s != '\0' && len > 0) {
86 h = l;
87 l = strhashtab[UCHAR(l ^ *s++)];
88 --len;
89 }
90 return (unsigned short) ((UCHAR(h) << 8) | UCHAR(l));
91 }
92
93 /*
94 * NAME: hashtab->lookup()
95 * DESCRIPTION: lookup a name in a hashtable, return the address of the entry
96 * or &NULL if none found
97 */
98 hte **ht_lookup(ht, name, move)
99 hashtab *ht;
100 register char *name;
101 int move;
102 {
103 register hte **first, **e, *next;
104
105 first = e = &(ht->table[hashstr(name, ht->maxlen) % ht->size]);
106 while (*e != (hte *) NULL) {
107 if (strcmp((*e)->name, name) == 0) {
108 if (move && e != first) {
109 /* move to first position */
110 next = (*e)->next;
111 (*e)->next = *first;
112 *first = *e;
113 *e = next;
114 return first;
115 }
116 break;
117 }
118 e = &((*e)->next);
119 }
120 return e;
121 }
122
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.