apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ami Ganguli <hse_...@yahoo.co.uk>
Subject [PATCH] RFC: allow custom hash functions
Date Sat, 17 Apr 2004 18:53:52 GMT
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
<rse@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

Mime
View raw message