2
* This file is part of libESMTP, a library for submission of RFC 2822
3
* formatted electronic mail messages using the SMTP protocol described
6
* Copyright (C) 2001,2002 Brian Stafford <brian@stafford.uklinux.net>
8
* This library is free software; you can redistribute it and/or
9
* modify it under the terms of the GNU Lesser General Public
10
* License as published by the Free Software Foundation; either
11
* version 2.1 of the License, or (at your option) any later version.
13
* This library is distributed in the hope that it will be useful,
14
* but WITHOUT ANY WARRANTY; without even the implied warranty of
15
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16
* Lesser General Public License for more details.
18
* You should have received a copy of the GNU Lesser General Public
19
* License along with this library; if not, write to the Free Software
20
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
29
/* A simplistic hash table implementation using hashing and chaining.
30
The table is always 256 entries long although this is an arbitrary
31
choice and there is nothing in the code to prevent other table sizes
32
or hash functions from working.
34
Case insensitive searching is performed.
41
#include <missing.h> /* declarations for missing library functions */
47
struct h_node *next; /* Next node in chain for this hash value */
48
char *name; /* Node name */
53
static const unsigned char shuffle[HASHSIZE] =
55
215, 207, 188, 72, 82, 194, 89, 230,
56
17, 49, 127, 179, 139, 200, 104, 114,
57
233, 52, 138, 42, 175, 159, 142, 77,
58
247, 3, 185, 54, 157, 19, 153, 14,
59
112, 184, 32, 220, 20, 148, 251, 141,
60
66, 195, 174, 150, 246, 76, 242, 227,
61
145, 84, 7, 5, 144, 211, 31, 71,
62
123, 217, 134, 243, 152, 137, 67, 213,
63
83, 223, 203, 119, 110, 113, 99, 158,
64
156, 61, 85, 187, 151, 90, 6, 237,
65
177, 45, 133, 87, 27, 106, 15, 68,
66
50, 80, 239, 250, 108, 253, 199, 124,
67
2, 210, 205, 21, 209, 252, 29, 196,
68
219, 78, 86, 178, 22, 53, 74, 9,
69
155, 91, 122, 235, 65, 129, 64, 206,
70
41, 46, 245, 125, 198, 189, 94, 79,
71
101, 160, 193, 43, 216, 128, 44, 70,
72
147, 229, 167, 186, 96, 166, 255, 146,
73
204, 224, 171, 149, 97, 102, 1, 165,
74
39, 222, 56, 12, 191, 202, 111, 103,
75
120, 24, 69, 100, 34, 164, 135, 197,
76
225, 18, 40, 236, 131, 231, 140, 63,
77
181, 170, 73, 244, 58, 25, 98, 183,
78
75, 57, 176, 118, 30, 226, 37, 36,
79
130, 33, 55, 26, 10, 161, 107, 38,
80
221, 234, 201, 121, 249, 116, 143, 62,
81
190, 59, 115, 93, 92, 228, 192, 109,
82
51, 8, 47, 13, 117, 173, 214, 81,
83
169, 241, 182, 162, 0, 95, 218, 23,
84
248, 132, 48, 232, 136, 240, 28, 154,
85
126, 208, 60, 11, 16, 105, 4, 163,
86
172, 238, 254, 88, 180, 168, 212, 35,
90
hashi (const char *string, int length)
94
assert (string != NULL);
96
for (h1 = 0; length-- > 0; h1 = shuffle[h1 ^ c])
105
/* Insert a new node into the table. It is not an error for an entry with
106
the same name to be already present in the table. The new entry will
107
be found when searching the table. When removed, the former entry
108
will be found on a subsequent search */
110
h_insert (struct h_node **table, const char *name, int namelen, size_t size)
115
assert (table != NULL && name != NULL);
118
namelen = strlen (name);
119
size += sizeof (struct h_node);
120
if ((node = malloc (size)) == NULL)
122
memset (node, 0, size);
123
if ((node->name = malloc (namelen)) == NULL)
128
memcpy (node->name, name, namelen);
129
hv = hashi (node->name, namelen);
130
node->next = table[hv];
135
/* Remove the node from the table.
138
h_remove (struct h_node **table, void *data)
140
struct h_node *node = (struct h_node *) data - 1;
144
assert (table != NULL && node != NULL);
146
hv = hashi (node->name, strlen (node->name));
147
if (table[hv] == node)
148
table[hv] = node->next;
150
for (p = table[hv]; p != NULL; p = p->next)
153
p->next = node->next;
161
/* Search for a node in the table.
164
h_search (struct h_node **table, const char *name, int namelen)
168
assert (table != NULL && name != NULL);
171
namelen = strlen (name);
172
for (p = table[hashi (name, namelen)]; p != NULL; p = p->next)
173
if (strncasecmp (name, p->name, namelen) == 0)
178
/* For each entry in the hash table, call the specified callback.
179
Entries are located in no particular order. */
181
h_enumerate (struct h_node **table,
182
void (*cb) (const char *name, void *data, void *arg), void *arg)
187
assert (table != NULL && cb != NULL);
189
for (i = 0; i < HASHSIZE; i++)
190
for (p = table[i]; p != NULL; p = p->next)
191
(*cb) (p->name, p + 1, arg);
194
/* Create a new hash table.
199
return calloc (HASHSIZE, sizeof (struct h_node *));
202
/* Destroy the hash table. This frees all memory allocated to the table,
203
nodes and names. It also calls the callback function for each item in the
204
table just before freeing its other resources.
207
h_destroy (struct h_node **table,
208
void (*cb) (const char *name, void *data, void *arg), void *arg)
210
struct h_node *p, *next;
213
assert (table != NULL);
215
for (i = 0; i < HASHSIZE; i++)
216
for (p = table[i]; p != NULL; p = next)
220
(*cb) (p->name, p + 1, arg);
added
removed
htable.c
