ArchWizard

DGD/

source navigation ]
diff markup ]
identifier search ]
file search ]
Version: [ 1.0.a0 ] [ 1.1 ] [ 1.2 ] [ 1.2p1 ] [ 1.2p2 ] [ 1.2p3 ] [ 1.2p4 ] [ 1.2.151 ]

  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 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.