You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Ami Ganguli <hs...@yahoo.co.uk> on 2004/04/17 20:53:52 UTC
[PATCH] RFC: allow custom hash functions
The following patch adds a new function:
apr_hash_t *
apr_hash_make_custom(
apr_pool_t *pool,
apr_hashfunc_t hash_func
);
and function pointer typedef:
typedef unsigned int (*apr_hashfunc_t)(
const char *key,
apr_ssize_t klen
);
"apr_hash_t" is expanded to include a reference to the
hash function (set to NULL by default). "find_entry"
is updated to use the hash function if it exists,
otherwise it falls back to the existing hash.
Please review for inclusion.
Regards,
Ami.
-------------
diff --unified --recursive --new-file
apr-0.9.4-old/include/apr_hash.h
apr-0.9.4/include/apr_hash.h
--- apr-0.9.4-old/include/apr_hash.h 2003-03-05
23:22:26.000000000 +0200
+++ apr-0.9.4/include/apr_hash.h 2004-04-18
01:36:16.000000000 +0300
@@ -99,6 +99,11 @@
typedef struct apr_hash_index_t apr_hash_index_t;
/**
+ * Callback functions for calculating hash values.
+ */
+typedef unsigned int (*apr_hashfunc_t)(const char
*key, apr_ssize_t klen);
+
+/**
* Create a hash table.
* @param pool The pool to allocate the hash table
out of
* @return The hash table just created
@@ -106,6 +111,15 @@
APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t
*pool);
/**
+ * Create a hash table with a custom hash function
+ * @param pool The pool to allocate the hash table
out of
+ * @param hash_func A custom hash function.
+ * @return The hash table just created
+ */
+APR_DECLARE(apr_hash_t *)
apr_hash_make_custom(apr_pool_t *pool,
+
apr_hashfunc_t hash_func);
+
+/**
* Make a copy of a hash table
* @param pool The pool from which to allocate the
new hash table
* @param h The hash table to clone
diff --unified --recursive --new-file
apr-0.9.4-old/tables/apr_hash.c
apr-0.9.4/tables/apr_hash.c
--- apr-0.9.4-old/tables/apr_hash.c 2003-01-13
20:52:07.000000000 +0200
+++ apr-0.9.4/tables/apr_hash.c 2004-04-18
01:23:02.000000000 +0300
@@ -115,6 +115,7 @@
apr_hash_entry_t **array;
apr_hash_index_t iterator; /* For
apr_hash_first(NULL, ...) */
unsigned int count, max;
+ apr_hashfunc_t hash_func;
};
#define INITIAL_MAX 15 /* tunable == 2^n - 1 */
@@ -137,6 +138,20 @@
ht->count = 0;
ht->max = INITIAL_MAX;
ht->array = alloc_array(ht, ht->max);
+ ht->hash_func = NULL;
+ return ht;
+}
+
+APR_DECLARE(apr_hash_t *)
apr_hash_make_custom(apr_pool_t *pool,
+
apr_hashfunc_t hash_func)
+{
+ apr_hash_t *ht;
+ ht = apr_palloc(pool, sizeof(apr_hash_t));
+ ht->pool = pool;
+ ht->count = 0;
+ ht->max = INITIAL_MAX;
+ ht->array = alloc_array(ht, ht->max);
+ ht->hash_func = hash_func;
return ht;
}
@@ -261,16 +276,21 @@
*
* -- Ralf S. Engelschall
<rs...@engelschall.com>
*/
- hash = 0;
- if (klen == APR_HASH_KEY_STRING) {
- for (p = key; *p; p++) {
- hash = hash * 33 + *p;
- }
- klen = p - (const unsigned char *)key;
+ if (ht->hash_func) {
+ hash = ht->hash_func( key, klen );
}
else {
- for (p = key, i = klen; i; i--, p++) {
- hash = hash * 33 + *p;
+ hash = 0;
+ if (klen == APR_HASH_KEY_STRING) {
+ for (p = key; *p; p++) {
+ hash = hash * 33 + *p;
+ }
+ klen = p - (const unsigned char *)key;
+ }
+ else {
+ for (p = key, i = klen; i; i--, p++) {
+ hash = hash * 33 + *p;
+ }
}
}
@@ -310,6 +330,7 @@
ht->pool = pool;
ht->count = orig->count;
ht->max = orig->max;
+ ht->hash_func = orig->hash_func;
ht->array = (apr_hash_entry_t **)((char *)ht +
sizeof(apr_hash_t));
new_vals = (apr_hash_entry_t *)((char *)(ht) +
sizeof(apr_hash_t) +
diff --unified --recursive --new-file
apr-0.9.4-old/test/testhash.c
apr-0.9.4/test/testhash.c
--- apr-0.9.4-old/test/testhash.c 2003-01-01
02:01:56.000000000 +0200
+++ apr-0.9.4/test/testhash.c 2004-04-18
01:45:03.000000000 +0300
@@ -150,6 +150,33 @@
CuAssertStrEquals(tc, "same", result);
}
+static unsigned int hash_custom( const char *key,
apr_ssize_t klen)
+{
+ unsigned int hash = 0;
+ while( klen ) {
+ klen --;
+ hash = hash * 33 + key[ klen ];
+ }
+ return hash;
+}
+
+static void same_value_custom(CuTest *tc)
+{
+ apr_hash_t *h = NULL;
+ char *result = NULL;
+
+ h = apr_hash_make_custom(p, hash_custom);
+ CuAssertPtrNotNull(tc, h);
+
+ apr_hash_set(h, "same1", 5, "same");
+ result = apr_hash_get(h, "same1", 5);
+ CuAssertStrEquals(tc, "same", result);
+
+ apr_hash_set(h, "same2", 5, "same");
+ result = apr_hash_get(h, "same2", 5);
+ CuAssertStrEquals(tc, "same", result);
+}
+
static void key_space(CuTest *tc)
{
apr_hash_t *h = NULL;
@@ -422,6 +449,7 @@
SUITE_ADD_TEST(suite, hash_set);
SUITE_ADD_TEST(suite, hash_reset);
SUITE_ADD_TEST(suite, same_value);
+ SUITE_ADD_TEST(suite, same_value_custom);
SUITE_ADD_TEST(suite, key_space);
SUITE_ADD_TEST(suite, delete_key);
____________________________________________________________
Yahoo! Messenger - Communicate instantly..."Ping"
your friends today! Download Messenger Now
http://uk.messenger.yahoo.com/download/index.html
Re: [PATCH] RFC: allow custom hash functions
Posted by Ami Ganguli <hs...@yahoo.co.uk>.
It seems Yahoo reformats my mail. Here's the patch as
an attachment.
... Ami.
____________________________________________________________
Yahoo! Messenger - Communicate instantly..."Ping"
your friends today! Download Messenger Now
http://uk.messenger.yahoo.com/download/index.html