apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From r..@apache.org
Subject cvs commit: apr/test testhash.c
Date Sun, 18 Apr 2004 12:12:49 GMT
rbb         2004/04/18 05:12:49

  Modified:    .        CHANGES
               include  apr_hash.h
               tables   apr_hash.c
               test     testhash.c
  Log:
  Allow developers to specify their own hash function for hash tables using
  the apr_hash_make_custom API.
  
  Submitted by:   Ami Ganguli <hse_ami@yahoo.co.uk>
  Reviewed by:	Ryan Bloom <rbb@apache.org>
  
  Revision  Changes    Path
  1.461     +3 -0      apr/CHANGES
  
  Index: CHANGES
  ===================================================================
  RCS file: /home/cvs/apr/CHANGES,v
  retrieving revision 1.460
  retrieving revision 1.461
  diff -u -r1.460 -r1.461
  --- CHANGES	16 Apr 2004 17:14:16 -0000	1.460
  +++ CHANGES	18 Apr 2004 12:12:49 -0000	1.461
  @@ -7,6 +7,9 @@
   
   Changes with APR 1.0
   
  +  *) Add support for developers to use their own hashing function with
  +     apr_hash_make_custom.  [Ami Ganguli <hse_ami@yahoo.co.uk>]
  +
     *) Support "large files" by default on 32-bit Unix platforms which
        implement the LFS standard.  [Joe Orton]
   
  
  
  
  1.42      +21 -0     apr/include/apr_hash.h
  
  Index: apr_hash.h
  ===================================================================
  RCS file: /home/cvs/apr/include/apr_hash.h,v
  retrieving revision 1.41
  retrieving revision 1.42
  diff -u -r1.41 -r1.42
  --- apr_hash.h	13 Feb 2004 09:38:28 -0000	1.41
  +++ apr_hash.h	18 Apr 2004 12:12:49 -0000	1.42
  @@ -56,11 +56,32 @@
   typedef struct apr_hash_index_t apr_hash_index_t;
   
   /**
  + * Callback functions for calculating hash values.
  + * @param key The key.
  + * @param klen The length of the key, or APR_HASH_KEY_STRING to use the string length.
 If APR_HASH_KEY_STRING then returns the actual key length.
  + */
  +typedef unsigned int (*apr_hashfunc_t)(const char *key, apr_ssize_t *klen);
  +
  +/**
  + * The default hash function.
  + */
  +unsigned int apr_hashfunc_default( 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
     */
   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
  
  
  
  1.37      +41 -20    apr/tables/apr_hash.c
  
  Index: apr_hash.c
  ===================================================================
  RCS file: /home/cvs/apr/tables/apr_hash.c,v
  retrieving revision 1.36
  retrieving revision 1.37
  diff -u -r1.36 -r1.37
  --- apr_hash.c	13 Feb 2004 09:38:34 -0000	1.36
  +++ apr_hash.c	18 Apr 2004 12:12:49 -0000	1.37
  @@ -72,6 +72,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 */
  @@ -94,6 +95,15 @@
       ht->count = 0;
       ht->max = INITIAL_MAX;
       ht->array = alloc_array(ht, ht->max);
  +    ht->hash_func = apr_hashfunc_default;
  +    return ht;
  +}
  +
  +APR_DECLARE(apr_hash_t *) apr_hash_make_custom(apr_pool_t *pool,
  +                                               apr_hashfunc_t hash_func)
  +{
  +    ht = apr_hash_make(p);
  +    ht->hash_func = hash_func;
       return ht;
   }
   
  @@ -162,25 +172,12 @@
       ht->max = new_max;
   }
   
  -/*
  - * This is where we keep the details of the hash function and control
  - * the maximum collision rate.
  - *
  - * If val is non-NULL it creates and initializes a new hash entry if
  - * there isn't already one there; it returns an updatable pointer so
  - * that hash entries can be removed.
  - */
  -
  -static apr_hash_entry_t **find_entry(apr_hash_t *ht,
  -                                     const void *key,
  -                                     apr_ssize_t klen,
  -                                     const void *val)
  +unsigned int apr_hashfunc_default( const char *key, apr_ssize_t *klen)
   {
  -    apr_hash_entry_t **hep, *he;
  +    unsigned int hash = 0;
       const unsigned char *p;
  -    unsigned int hash;
       apr_ssize_t i;
  -
  +    
       /*
        * This is the popular `times 33' hash algorithm which is used by
        * perl and also appears in Berkeley DB. This is one of the best
  @@ -218,19 +215,42 @@
        *
        *                  -- Ralf S. Engelschall <rse@engelschall.com>
        */
  -    hash = 0;
  -    if (klen == APR_HASH_KEY_STRING) {
  +     
  +    if (*klen == APR_HASH_KEY_STRING) {
           for (p = key; *p; p++) {
               hash = hash * 33 + *p;
           }
  -        klen = p - (const unsigned char *)key;
  +        *klen = p - (const unsigned char *)key;
       }
       else {
  -        for (p = key, i = klen; i; i--, p++) {
  +        for (p = key, i = *klen; i; i--, p++) {
               hash = hash * 33 + *p;
           }
       }
   
  +    return hash;
  +}
  +
  +
  +/*
  + * This is where we keep the details of the hash function and control
  + * the maximum collision rate.
  + *
  + * If val is non-NULL it creates and initializes a new hash entry if
  + * there isn't already one there; it returns an updatable pointer so
  + * that hash entries can be removed.
  + */
  +
  +static apr_hash_entry_t **find_entry(apr_hash_t *ht,
  +                                     const void *key,
  +                                     apr_ssize_t klen,
  +                                     const void *val)
  +{
  +    apr_hash_entry_t **hep, *he;
  +    unsigned int hash;
  +
  +    hash = ht->hash_func( key, &klen );
  +
       /* scan linked list */
       for (hep = &ht->array[hash & ht->max], he = *hep;
            he; hep = &he->next, he = *hep) {
  @@ -267,6 +287,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) +
  
  
  
  1.8       +29 -1     apr/test/testhash.c
  
  Index: testhash.c
  ===================================================================
  RCS file: /home/cvs/apr/test/testhash.c,v
  retrieving revision 1.7
  retrieving revision 1.8
  diff -u -r1.7 -r1.8
  --- testhash.c	13 Feb 2004 09:38:34 -0000	1.7
  +++ testhash.c	18 Apr 2004 12:12:49 -0000	1.8
  @@ -111,6 +111,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;
  @@ -374,7 +401,7 @@
                             "Key base4 (5) Value value4\n"
                             "#entries 5\n", str);
   }
  -        
  +
   CuSuite *testhash(void)
   {
       CuSuite *suite = CuSuiteNew("Hash");
  @@ -383,6 +410,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);
   
  
  
  

Mime
View raw message