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