31
31
#include "helpers.h"
33
34
#if !defined(lint) && !defined(NO_RCSIDS)
34
35
static char rcsid[]="$Id: hash.c,v 1.12 2001/06/02 23:08:13 tmm Exp $";
37
38
/* This is not a perfect hash, but I hope it holds. It is designed for 1024 hash
38
* buckets, and hashes only strings with the allowed dns characters
39
* [a-zA-Z0-9\-\.] = 64, but with case-insensitivity = 38
39
* buckets, and hashes strings with case-insensitivity.
40
40
* It is position-aware in a limited way.
41
41
* It is exactly seen a two-way hash: because I do not want to exaggerate
42
42
* the hash buckets (i do have 1024), but I hash strings and string-comparisons
43
43
* are expensive, I save another 32 bit hash in each hash element that is checked
44
* before the string. The 32 bit hash is also used to order the entries in a hash chain.
45
45
* I hope not to have all too much collision concentration.
47
47
* The ip hash was removed. I don't think it concentrated the collisions too much.
50
50
* Some measurements seem to indicate that the hash algorithm is doing reasonable well.
53
static const unsigned char values[256]={
54
#include "hashconvtable.h"
58
* The hash structures are the same for an ip and an dns hash, so we use
59
* an additional element in debug mode to report misuse.
61
53
dns_hash_ent_t *hash_buckets[HASH_NUM_BUCKETS];
65
* Hash a dns name (dotted) to HASH_SZ bit.
67
static long dns_shash(const unsigned char *str)
72
for (i=0;(c=str[i]);i++) {
73
acc+=values[c]<<(i%(HASH_SZ-5));
75
acc=(acc&HASH_BITMASK)+((acc&(~HASH_BITMASK))>>HASH_SZ);
76
acc=(acc&HASH_BITMASK)+((acc&(~HASH_BITMASK))>>HASH_SZ);
78
printf("Diagnostic: dns hash for %s: %03lx\n",str,acc&HASH_BITMASK);
80
return acc&HASH_BITMASK;
84
* Hash a dns name (dotted) to 32 bit.
86
static unsigned long dns_rhash(const unsigned char *str)
91
for (i=0;(c=str[i]);i++) {
92
acc+=values[c]<<(i%25);
95
printf("Diagnostic: dns rhash for %s: %04lx\n",str,acc);
57
* Hash a dns name (length-byte string format) to HASH_SZ bit.
58
* *rhash is set to a long int hash.
60
static unsigned dns_hash(const unsigned char *str, unsigned long *rhash)
67
s+=lb<<(i%(HASH_SZ-5));
68
r+=((unsigned long)lb)<<(i%(8*sizeof(unsigned long)-7));
72
s+=c<<(i%(HASH_SZ-5));
73
r+=((unsigned long)c)<<(i%(8*sizeof(unsigned long)-7));
77
s=(s&HASH_BITMASK)+((s&(~HASH_BITMASK))>>HASH_SZ);
78
s=(s&HASH_BITMASK)+((s&(~HASH_BITMASK))>>HASH_SZ);
82
unsigned char buf[256];
83
printf("Diagnostic: hashes for %s: %03x,%04lx\n",rhn2str(str,buf,sizeof(buf)),s,r);
101
91
* Initialize hash to hold a dns hash table
103
/* void mk_dns_hash()
93
/* This is now defined as an inline function in hash.h */
106
98
for(i=0;i<HASH_NUM_BUCKETS;i++)
107
99
hash_buckets[i]=NULL;
111
* Add an entry to the hash. data->qname is your key, data will be returned
114
void add_dns_hash(dns_cent_t *data)
116
const unsigned char *key=data->qname;
117
int idx=dns_shash(key);
104
Lookup in the hash table for key. If it is found, return the pointer to the cache entry.
105
If no entry is found, return 0.
106
If loc is not NULL, it will used to store information about the location within the hash table
107
This can be used to add an entry with add_dns_hash() or delete the entry with del_dns_hash_ent().
109
dns_cent_t *dns_lookup(const unsigned char *key, dns_hash_loc_t *loc)
111
dns_cent_t *retval=NULL;
114
dns_hash_ent_t **hep,*he;
116
idx = dns_hash(key,&rh);
117
hep = &hash_buckets[idx];
118
while ((he= *hep) && he->rhash<=rh) {
119
if (he->rhash==rh && rhnicmp(key,he->data->qname)) {
133
Add an entry to the hash.
134
loc contains the location where the the new entry should be inserted
135
(this location can be obtained with dns_lookup).
137
void add_dns_hash(dns_cent_t *data, dns_hash_loc_t *loc)
118
139
dns_hash_ent_t *he;
119
141
he=malloc(sizeof(dns_hash_ent_t));
121
143
log_error("Out of memory.");
124
he->next=hash_buckets[idx];
125
he->rhash=dns_rhash(key);
127
hash_buckets[idx]=he;
146
he->next = *(loc->pos);
147
he->rhash = loc->rhash;
153
Delete the hash entry indentified by the location returned by dns_lookup().
155
dns_cent_t *del_dns_hash_ent(dns_hash_loc_t *loc)
157
dns_hash_ent_t *he = *(loc->pos);
160
*(loc->pos) = he->next;
134
170
dns_cent_t *del_dns_hash(const unsigned char *key)
136
int idx=dns_shash(key);
137
unsigned long rh=dns_rhash(key);
138
174
dns_hash_ent_t **hep,*he;
139
175
dns_cent_t *data;
140
hep=&hash_buckets[idx];
142
if (he->rhash==rh && stricomp(key,he->data->qname)) {
177
idx = dns_hash(key,&rh);
178
hep = &hash_buckets[idx];
179
while ((he= *hep) && he->rhash<=rh) {
180
if (he->rhash==rh && rhnicmp(key,he->data->qname)) {
150
return NULL; /* not found */
154
* Lookup in the hash table for key. If it is found, return the data pointer as given by
155
* add_dns_hash. If no entry is found, return 0.
157
dns_cent_t *dns_lookup(const unsigned char *key)
159
int idx=dns_shash(key);
160
unsigned long rh=dns_rhash(key);
162
he=hash_buckets[idx];
164
if (he->rhash==rh && stricomp(key,he->data->qname))
169
return NULL; /* not found */
188
return NULL; /* not found */
193
* Delete all entries in a hash bucket.
195
void free_dns_hash_bucket(int i)
197
dns_hash_ent_t *he,*hen;
200
hash_buckets[i]=NULL;
210
* Delete all entries in a hash bucket whose names match those in
211
* an include/exclude list.
213
void free_dns_hash_selected(int i, slist_array sla)
215
dns_hash_ent_t **hep,*he,*hen;
218
hep= &hash_buckets[i];
222
unsigned char *name=he->data->qname;
224
slist_t *sl=&DA_INDEX(sla,j);
226
domain_match(name,sl->domain,&nrem,&lrem);
227
if(!lrem && (!sl->exact || !nrem)) {
228
if(sl->rule==C_INCLUDED)
234
/* default policy is not to delete */
239
for (i=0; i<HASH_NUM_BUCKETS; i++) {
240
for (j=0, he=hash_buckets[i]; he; he=he->next, j++) ;
241
DEBUG_MSG("bucket %d: %d entries\n", i, j);
316
for (i=0; i<HASH_NUM_BUCKETS; i++) {
317
for (j=0, he=hash_buckets[i]; he; he=he->next, j++) ;
318
DEBUG_MSG("bucket %d: %d entries\n", i, j);
added
removed
src/hash.c
