From 96d69ecd5b1e5090db05efee7c992e2b2b1e3062 Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Sun, 30 Dec 2007 12:46:01 +0000 Subject: [PATCH] Moved generic string and data hashing and comparison functions to silchashtable.[ch]. Added case insensitive and case sensitive string hashing and comparison functions. Changed the string and data hashing to use Bob Jenkin's one-at-a-time hash function. --- lib/silccore/silcpacket.c | 8 +- lib/silcskr/silcskr.c | 2 +- lib/silcssh/silcssh.c | 8 +- lib/silcutil/silchashtable.c | 133 ++++++++++++++++++++++++++++++ lib/silcutil/silchashtable.h | 154 +++++++++++++++++++++++++++++++++++ lib/silcutil/silcmime.c | 8 +- lib/silcutil/silcutil.c | 97 ---------------------- lib/silcutil/silcutil.h | 113 ------------------------- 8 files changed, 300 insertions(+), 223 deletions(-) diff --git a/lib/silccore/silcpacket.c b/lib/silccore/silcpacket.c index af437c2f..d2696bbe 100644 --- a/lib/silccore/silcpacket.c +++ b/lib/silccore/silcpacket.c @@ -771,10 +771,10 @@ SilcPacketStream silc_packet_stream_create(SilcPacketEngine engine, /* If this is UDP stream, allocate UDP remote stream hash table */ if (!engine->udp_remote && silc_socket_stream_is_udp(stream, NULL)) - engine->udp_remote = silc_hash_table_alloc(NULL, 0, silc_hash_string, NULL, - silc_hash_string_compare, NULL, - silc_packet_engine_hash_destr, - NULL, TRUE); + engine->udp_remote = + silc_hash_table_alloc(NULL, 0, silc_hash_string_case, NULL, + silc_hash_string_case_compare, NULL, + silc_packet_engine_hash_destr, NULL, TRUE); silc_mutex_unlock(engine->lock); diff --git a/lib/silcskr/silcskr.c b/lib/silcskr/silcskr.c index be2f8692..7459d432 100644 --- a/lib/silcskr/silcskr.c +++ b/lib/silcskr/silcskr.c @@ -168,7 +168,7 @@ static SilcUInt32 silc_skr_hash(void *key, void *user_context) break; } - return type->type + silc_hash_string(type->data, user_context); + return type->type + silc_hash_string_case(type->data, user_context); } /* Hash table comparison function for key entries */ diff --git a/lib/silcssh/silcssh.c b/lib/silcssh/silcssh.c index 6cb849fc..89c5d1a3 100644 --- a/lib/silcssh/silcssh.c +++ b/lib/silcssh/silcssh.c @@ -71,8 +71,8 @@ SilcBool silc_ssh_parse_line(SilcBuffer key, SilcBuffer line, SilcHashTable silc_ssh_allocate_fields(void) { - return silc_hash_table_alloc(NULL, 0, silc_hash_string, NULL, - silc_hash_string_compare, NULL, + return silc_hash_table_alloc(NULL, 0, silc_hash_string_case, NULL, + silc_hash_string_case_compare, NULL, silc_ssh_field_dest, NULL, TRUE); } @@ -416,8 +416,8 @@ SilcBool silc_ssh_public_key_add_field(SilcSshPublicKey public_key, if (!public_key->fields) { public_key->fields = - silc_hash_table_alloc(NULL, 0, silc_hash_string, NULL, - silc_hash_string_compare, NULL, + silc_hash_table_alloc(NULL, 0, silc_hash_string_case, NULL, + silc_hash_string_case_compare, NULL, silc_ssh_field_dest, NULL, TRUE); if (!public_key->fields) return FALSE; diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index 4a82a515..13c655e7 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -988,3 +988,136 @@ SilcBool silc_hash_table_get(SilcHashTableList *htl, void **key, return TRUE; } + +/**************************** Utility functions *****************************/ + +/* Case sensitive hashing */ + +SilcUInt32 silc_hash_string(void *key, void *user_context) +{ + char *s = (char *)key; + SilcUInt32 h = 0; + + while (*s != '\0') { + h += *s++; + h += (h << 10); + h ^= (h >> 6); + } + + h += (h << 3); + h ^= (h >> 11); + h += (h << 15); + + return h; +} + +/* Case-insensitive hashing */ + +SilcUInt32 silc_hash_string_case(void *key, void *user_context) +{ + char *s = (char *)key; + SilcUInt32 h = 0; + + while (*s != '\0') { + h += tolower((int)*s); + h += (h << 10); + h ^= (h >> 6); + s++; + } + + h += (h << 3); + h ^= (h >> 11); + h += (h << 15); + + return h; +} + +/* Hash UTF-8 string */ + +SilcUInt32 silc_hash_utf8_string(void *key, void *user_context) +{ + char *s = (char *)key; + SilcUInt32 h = 0; + + while (*s != '\0') { + h += *s++; + h += (h << 10); + h ^= (h >> 6); + } + + h += (h << 3); + h ^= (h >> 11); + h += (h << 15); + + return h; +} + +/* Basic hash function to hash integers. */ + +SilcUInt32 silc_hash_uint(void *key, void *user_context) +{ + return SILC_PTR_TO_32(key); +} + +/* Basic hash funtion to hash pointers. */ + +SilcUInt32 silc_hash_ptr(void *key, void *user_context) +{ + return SILC_PTR_TO_32(key); +} + +/* Hash binary data. The `user_context' is the data length. */ + +SilcUInt32 silc_hash_data(void *key, void *user_context) +{ + SilcUInt32 len = SILC_PTR_TO_32(user_context), h, i; + unsigned char *data = (char *)key; + + h = (data[0] * data[len - 1] + 1) * len; + + for (i = 0; i < len; i++) { + h += data[i]; + h += (h << 10); + h ^= (h >> 6); + } + + h += (h << 3); + h ^= (h >> 11); + h += (h << 15); + + return h; +} + +/* Compares two strings. */ + +SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context) +{ + return !strcmp((char *)key1, (char *)key2); +} + +/* Compares two strings, ignores case. */ + +SilcBool silc_hash_string_case_compare(void *key1, void *key2, + void *user_context) +{ + return !strcasecmp((char *)key1, (char *)key2); +} + +/* Compares binary data. */ + +SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context) +{ + SilcUInt32 len = SILC_PTR_TO_32(user_context); + return !memcmp(key1, key2, len); +} + +/* Compares UTF-8 string. */ + +SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context) +{ + int l1 = strlen((char *)key1); + int l2 = strlen((char *)key2); + if (l1 != l2) + return FALSE; + return !memcmp(key1, key2, l2); +} diff --git a/lib/silcutil/silchashtable.h b/lib/silcutil/silchashtable.h index f7d7f21a..966ffc46 100644 --- a/lib/silcutil/silchashtable.h +++ b/lib/silcutil/silchashtable.h @@ -741,4 +741,158 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size, SilcHashFunction hash, void *hash_user_context); +/* Hash functions */ + +/****f* silcutil/SilcHashTableAPI/silc_hash_string + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_string(void *key, void *user_context); + * + * DESCRIPTION + * + * Basic hash function to hash strings. May be used with the SilcHashTable. + * This uses Bob Jenkin's one-at-a-time (described in Wikipedia) hash + * function. + * + ***/ +SilcUInt32 silc_hash_string(void *key, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_string_case + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_string_case(void *key, void *user_context); + * + * DESCRIPTION + * + * Basic hash function to hash strings. May be used with the SilcHashTable. + * This ignores the string's case, ie. 'Foo' and 'foo' will hash to same + * value. This uses Bob Jenkin's one-at-a-time (described in Wikipedia) + * hash function. + * + ***/ +SilcUInt32 silc_hash_string_case(void *key, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_utf8_string + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_utf8_string(void *key, void *user_context); + * + * DESCRIPTION + * + * Basic has function to hash UTF-8 strings. May be used with the + * SilcHashTable. Used with identifier strings. The key is + * expected to be casefolded. + * + ***/ +SilcUInt32 silc_hash_utf8_string(void *key, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_uint + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_uint(void *key, void *user_context); + * + * DESCRIPTION + * + * Basic hash function to hash integers. May be used with the SilcHashTable. + * Comparison function is not needed, the SilcHashTable will automatically + * compare integer values. + * + ***/ +SilcUInt32 silc_hash_uint(void *key, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_ptr + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_ptr(void *key, void *user_context); + * + * DESCRIPTION + * + * Basic hash funtion to hash pointers. May be used with the SilcHashTable. + * Comparison function is not needed, the SilcHashTable will automatically + * compare pointer values. + * + ***/ +SilcUInt32 silc_hash_ptr(void *key, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_data + * + * SYNOPSIS + * + * SilcUInt32 silc_hash_data(void *key, void *user_context); + * + * DESCRIPTION + * + * Hash binary data. The `user_context' is the data length. This uses Bob + * Jenkin's one-at-a-time (described in Wikipedia) hash function. + * + ***/ +SilcUInt32 silc_hash_data(void *key, void *user_context); + +/* Comparison functions */ + +/****f* silcutil/SilcHashTableAPI/silc_hash_string_compare + * + * SYNOPSIS + * + * SilcBool silc_hash_string_compare(void *key1, void *key2, + * void *user_context); + * + * DESCRIPTION + * + * Compares two strings. It may be used as SilcHashTable comparison + * function. + * + ***/ +SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_string_case_compare + * + * SYNOPSIS + * + * SilcBool silc_hash_string_case_compare(void *key1, void *key2, + * void *user_context); + * + * DESCRIPTION + * + * Compares two strings. This ignores the case while comparing. It may + * be used as SilcHashTable comparison function. + * + ***/ +SilcBool silc_hash_string_case_compare(void *key1, void *key2, + void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_utf8_compare + * + * SYNOPSIS + * + * SilcBool silc_hash_utf8_compare(void *key1, void *key2, + * void *user_context); + * + * DESCRIPTION + * + * Compares UTF-8 strings. Casefolded and NULL terminated strings are + * expected. May be used as SilcHashTable comparison function. + * + ***/ +SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context); + +/****f* silcutil/SilcHashTableAPI/silc_hash_data_compare + * + * SYNOPSIS + * + * SilcBool silc_hash_data_compare(void *key1, void *key2, + * void *user_context); + * + * DESCRIPTION + * + * Compares binary data. May be used as SilcHashTable comparison function. + * + ***/ +SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context); + #endif diff --git a/lib/silcutil/silcmime.c b/lib/silcutil/silcmime.c index 04b23adb..839eb354 100644 --- a/lib/silcutil/silcmime.c +++ b/lib/silcutil/silcmime.c @@ -64,7 +64,7 @@ static void silc_mime_assemble_dest(void *key, void *context, static SilcUInt32 silc_mime_hash_id(void *key, void *user_context) { SilcMimeFragmentId id = key; - return silc_hash_string(id->id, user_context); + return silc_hash_string_case(id->id, user_context); } /* MIME fragment ID comparing */ @@ -73,7 +73,7 @@ static SilcBool silc_mime_id_compare(void *key1, void *key2, void *user_context) { SilcMimeFragmentId id1 = key1, id2 = key2; - return silc_hash_string_compare(id1->id, id2->id, user_context); + return silc_hash_string_case_compare(id1->id, id2->id, user_context); } @@ -89,8 +89,8 @@ SilcMime silc_mime_alloc(void) if (!mime) return NULL; - mime->fields = silc_hash_table_alloc(NULL, 0, silc_hash_string, mime, - silc_hash_string_compare, mime, + mime->fields = silc_hash_table_alloc(NULL, 0, silc_hash_string_case, mime, + silc_hash_string_case_compare, mime, silc_mime_field_dest, mime, TRUE); if (!mime->fields) { silc_mime_free(mime); diff --git a/lib/silcutil/silcutil.c b/lib/silcutil/silcutil.c index fe012c6b..eb0d989e 100644 --- a/lib/silcutil/silcutil.c +++ b/lib/silcutil/silcutil.c @@ -232,61 +232,6 @@ char *silc_format(char *fmt, ...) return silc_strdup(buf); } -/* Basic has function to hash strings. May be used with the SilcHashTable. - Note that this lowers the characters of the string (with tolower()) so - this is used usually with nicknames, channel and server names to provide - case insensitive keys. */ - -SilcUInt32 silc_hash_string(void *key, void *user_context) -{ - char *s = (char *)key; - SilcUInt32 h = 0, g; - - while (*s != '\0') { - h = (h << 4) + tolower((int)*s); - if ((g = h & 0xf0000000)) { - h = h ^ (g >> 24); - h = h ^ g; - } - s++; - } - - return h; -} - -/* Hash UTF-8 string */ - -SilcUInt32 silc_hash_utf8_string(void *key, void *user_context) -{ - unsigned char *s = (unsigned char *)key; - SilcUInt32 h = 0, g; - - while (*s != '\0') { - h = (h << 4) + *s; - if ((g = h & 0xf0000000)) { - h = h ^ (g >> 24); - h = h ^ g; - } - s++; - } - - return h; -} - -/* Basic hash function to hash integers. May be used with the SilcHashTable. */ - -SilcUInt32 silc_hash_uint(void *key, void *user_context) -{ - return SILC_PTR_TO_32(key); -} - -/* Basic hash funtion to hash pointers. May be used with the SilcHashTable. */ - -SilcUInt32 silc_hash_ptr(void *key, void *user_context) -{ - return SILC_PTR_TO_32(key); -} - /* Hash a ID. The `user_context' is the ID type. */ SilcUInt32 silc_hash_id(void *key, void *user_context) @@ -355,29 +300,6 @@ SilcUInt32 silc_hash_client_id_hash(void *key, void *user_context) return h; } -/* Hash binary data. The `user_context' is the data length. */ - -SilcUInt32 silc_hash_data(void *key, void *user_context) -{ - SilcUInt32 len = SILC_PTR_TO_32(user_context), h = 0; - unsigned char *data = (unsigned char *)key; - int i; - - h = (data[0] * data[len - 1] + 1) * len; - for (i = 0; i < len; i++) - h ^= data[i]; - - return h; -} - -/* Compares two strings. It may be used as SilcHashTable comparison - function. */ - -SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context) -{ - return !strcasecmp((char *)key1, (char *)key2); -} - /* Compares two ID's. May be used as SilcHashTable comparison function. The Client ID's compares only the hash of the Client ID not any other part of the Client ID. Other ID's are fully compared. */ @@ -406,25 +328,6 @@ SilcBool silc_hash_client_id_compare(void *key1, void *key2, return SILC_ID_COMPARE_TYPE(key1, key2, SILC_ID_CLIENT); } -/* Compares binary data. May be used as SilcHashTable comparison function. */ - -SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context) -{ - SilcUInt32 len = SILC_PTR_TO_32(user_context); - return !memcmp(key1, key2, len); -} - -/* Compares UTF-8 string. */ - -SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context) -{ - int l1 = strlen((char *)key1); - int l2 = strlen((char *)key2); - if (l1 != l2) - return FALSE; - return !memcmp(key1, key2, l2); -} - /* Creates fingerprint from data, usually used with SHA1 digests */ char *silc_fingerprint(const unsigned char *data, SilcUInt32 data_len) diff --git a/lib/silcutil/silcutil.h b/lib/silcutil/silcutil.h index b4d9eb45..7aa40a4f 100644 --- a/lib/silcutil/silcutil.h +++ b/lib/silcutil/silcutil.h @@ -131,62 +131,6 @@ void silc_parse_command_line(unsigned char *buffer, ***/ char *silc_format(char *fmt, ...); -/****f* silcutil/SilcUtilAPI/silc_hash_string - * - * SYNOPSIS - * - * SilcUInt32 silc_hash_string(void *key, void *user_context); - * - * DESCRIPTION - * - * Basic has function to hash strings. May be used with the SilcHashTable. - * Note that this lowers the characters of the string (with tolower()) so - * this can be used to provide case-insensitive hashing. - * - ***/ -SilcUInt32 silc_hash_string(void *key, void *user_context); - -/****f* silcutil/SilcUtilAPI/silc_hash_utf8_string - * - * SYNOPSIS - * - * SilcUInt32 silc_hash_utf8_string(void *key, void *user_context); - * - * DESCRIPTION - * - * Basic has function to hash UTF-8 strings. May be used with the - * SilcHashTable. Used with identifier strings. The key is - * expected to be casefolded. - * - ***/ -SilcUInt32 silc_hash_utf8_string(void *key, void *user_context); - -/****f* silcutil/SilcUtilAPI/silc_hash_uint - * - * SYNOPSIS - * - * SilcUInt32 silc_hash_uint(void *key, void *user_context); - * - * DESCRIPTION - * - * Basic hash function to hash integers. May be used with the SilcHashTable. - * - ***/ -SilcUInt32 silc_hash_uint(void *key, void *user_context); - -/****f* silcutil/SilcUtilAPI/silc_hash_ptr - * - * SYNOPSIS - * - * SilcUInt32 silc_hash_ptr(void *key, void *user_context); - * - * DESCRIPTION - * - * Basic hash funtion to hash pointers. May be used with the SilcHashTable. - * - ***/ -SilcUInt32 silc_hash_ptr(void *key, void *user_context); - /****f* silcutil/SilcUtilAPI/silc_hash_id * * SYNOPSIS @@ -213,34 +157,6 @@ SilcUInt32 silc_hash_id(void *key, void *user_context); ***/ SilcUInt32 silc_hash_client_id_hash(void *key, void *user_context); -/****f* silcutil/SilcUtilAPI/silc_hash_data - * - * SYNOPSIS - * - * SilcUInt32 silc_hash_data(void *key, void *user_context); - * - * DESCRIPTION - * - * Hash binary data. The `user_context' is the data length. - * - ***/ -SilcUInt32 silc_hash_data(void *key, void *user_context); - -/****f* silcutil/SilcUtilAPI/silc_hash_string_compare - * - * SYNOPSIS - * - * SilcBool silc_hash_string_compare(void *key1, void *key2, - * void *user_context); - * - * DESCRIPTION - * - * Compares two strings. This ignores the case while comparing. It may - * be used as SilcHashTable comparison function. - * - ***/ -SilcBool silc_hash_string_compare(void *key1, void *key2, void *user_context); - /****f* silcutil/SilcUtilAPI/silc_hash_id_compare * * SYNOPSIS @@ -288,35 +204,6 @@ SilcBool silc_hash_id_compare_full(void *key1, void *key2, void *user_context); SilcBool silc_hash_client_id_compare(void *key1, void *key2, void *user_context); -/****f* silcutil/SilcUtilAPI/silc_hash_data_compare - * - * SYNOPSIS - * - * SilcBool silc_hash_data_compare(void *key1, void *key2, - * void *user_context); - * - * DESCRIPTION - * - * Compares binary data. May be used as SilcHashTable comparison function. - * - ***/ -SilcBool silc_hash_data_compare(void *key1, void *key2, void *user_context); - -/****f* silcutil/SilcUtilAPI/silc_hash_utf8_compare - * - * SYNOPSIS - * - * SilcBool silc_hash_utf8_compare(void *key1, void *key2, - * void *user_context); - * - * DESCRIPTION - * - * Compares UTF-8 strings. Casefolded and NULL terminated strings are - * expected. May be used as SilcHashTable comparison function. - * - ***/ -SilcBool silc_hash_utf8_compare(void *key1, void *key2, void *user_context); - /****f* silcutil/SilcUtilAPI/silc_fingerprint * * SYNOPSIS -- 2.24.0