"Fossies" - the Fresh Open Source Software Archive

Member "ftwin-master/src/napr_hash.c" (15 Feb 2015, 10407 Bytes) of package /linux/privat/ftwin-master.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /*
    2  * Copyright (C) 2007 Fran├žois Pesce : francois.pesce (at) gmail (dot) com
    3  *
    4  * Licensed under the Apache License, Version 2.0 (the "License");
    5  * you may not use this file except in compliance with the License.
    6  * You may obtain a copy of the License at
    7  * 
    8  *  http://www.apache.org/licenses/LICENSE-2.0
    9  * 
   10  * Unless required by applicable law or agreed to in writing, software
   11  * distributed under the License is distributed on an "AS IS" BASIS,
   12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   13  * See the License for the specific language governing permissions and
   14  * limitations under the License.
   15  */
   16 
   17 #include "lookup3.h"
   18 #include "debug.h"
   19 #include "napr_hash.h"
   20 
   21 #define hashsize(n) ((apr_size_t)1<<(n))
   22 #define hashmask(n) (hashsize(n)-1)
   23 
   24 static const void *str_get_key(const void *opaque)
   25 {
   26     return opaque;
   27 }
   28 
   29 static apr_size_t str_get_key_len(const void *opaque)
   30 {
   31     const char *str = opaque;
   32     return strlen(str);
   33 }
   34 
   35 static int str_key_cmp(const void *opaque1, const void *opaque2, apr_size_t len)
   36 {
   37     const char *str1 = opaque1;
   38     const char *str2 = opaque2;
   39 
   40     return memcmp(str1, str2, len);
   41 }
   42 
   43 static apr_uint32_t str_hash(register const void *opaque, register apr_size_t len)
   44 {
   45     return hashlittle(opaque, len, 0x1337cafe);
   46 }
   47 
   48 struct napr_hash_index_t
   49 {
   50     napr_hash_t *hash;
   51     apr_size_t bucket;
   52     apr_size_t element;     /* of a bucket */
   53 };
   54 
   55 struct napr_hash_t
   56 {
   57     /* void *table[size][ffactor] */
   58     void ***table;
   59     /* apr_size_t table[size] contain the number of element for each bucket */
   60     apr_size_t *filling_table;
   61     /* parent pool */
   62     apr_pool_t *pool;
   63     /* own pool that will be cleaned if a grow of the table occured */
   64     apr_pool_t *own_pool;
   65     /* Function to get the key from the datum */
   66     get_key_callback_fn_t *get_key;
   67     /* Function to get the key len from the datum */
   68     get_key_len_callback_fn_t *get_key_len;
   69     /* Function to compare two keys */
   70     key_cmp_callback_fn_t *key_cmp;
   71     /* hash function */
   72     hash_callback_fn_t *hash;
   73 
   74     /* the number of element contained in all the buckets of the table */
   75     apr_size_t nel;
   76     /* the number of buckets */
   77     apr_size_t size;
   78     /* desired density */
   79     apr_size_t ffactor;
   80     /* the binary mask to apply to the result of a hash function that return a
   81      * number < size */
   82     apr_uint32_t mask;
   83     /* size of the hash is hashsize(power) as mask is hashmask(power) */
   84     unsigned char power;
   85 };
   86 
   87 extern napr_hash_t *napr_hash_str_make(apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor)
   88 {
   89     return napr_hash_make(pool, nel, ffactor, str_get_key, str_get_key_len, str_key_cmp, str_hash);
   90 }
   91 
   92 extern napr_hash_t *napr_hash_make(apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor, get_key_callback_fn_t get_key,
   93                    get_key_len_callback_fn_t get_key_len, key_cmp_callback_fn_t key_cmp,
   94                    hash_callback_fn_t hash)
   95 {
   96     napr_hash_t *result;
   97     apr_status_t status;
   98 
   99     if (NULL == (result = apr_pcalloc(pool, sizeof(struct napr_hash_t)))) {
  100     DEBUG_ERR("allocation error");
  101     return NULL;
  102     }
  103 
  104     while (hashsize(result->power) < nel)
  105     result->power++;
  106 
  107     result->size = hashsize(result->power);
  108     result->mask = hashmask(result->power);
  109     result->ffactor = ffactor;
  110     result->get_key = get_key;
  111     result->get_key_len = get_key_len;
  112     result->key_cmp = key_cmp;
  113     result->hash = hash;
  114     result->pool = pool;
  115 
  116     if (APR_SUCCESS != (status = apr_pool_create(&(result->own_pool), pool))) {
  117     char errbuf[128];
  118     DEBUG_ERR("error calling apr_pool_create: %s", apr_strerror(status, errbuf, 128));
  119     return NULL;
  120     }
  121     /*DEBUG_DBG("readjusting size to %" APR_SIZE_T_FMT " to store %" APR_SIZE_T_FMT " elements", result->size, nel); */
  122     /*DEBUG_DBG("bit mask will be 0x%x", result->mask); */
  123 
  124     if (NULL == (result->table = apr_pcalloc(result->own_pool, result->size * sizeof(void **)))) {
  125     DEBUG_ERR("allocation error");
  126     return NULL;
  127     }
  128 
  129     if (NULL == (result->filling_table = apr_pcalloc(result->own_pool, result->size * sizeof(apr_size_t)))) {
  130     DEBUG_ERR("allocation error");
  131     return NULL;
  132     }
  133 
  134     return result;
  135 }
  136 
  137 extern void *napr_hash_search(napr_hash_t *hash, const void *key, apr_size_t key_len, apr_uint32_t *hash_value)
  138 {
  139     apr_uint32_t key_hash;
  140     apr_size_t i, nel, bucket;
  141 
  142     key_hash = hash->hash(key, key_len);
  143 
  144     if (NULL != hash_value)
  145     *hash_value = key_hash;
  146 
  147     bucket = key_hash & hash->mask;
  148     if (0 != (nel = hash->filling_table[bucket])) {
  149     for (i = 0; i < nel; i++) {
  150         /*DEBUG_DBG( "key[%p] bucket[%"APR_SIZE_T_FMT"][%"APR_SIZE_T_FMT"]=[%p]", key, bucket, i, hash->get_key(hash->table[bucket][i])); */
  151         if (key_len == hash->get_key_len(hash->table[bucket][i]))
  152         if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len)))
  153             return hash->table[bucket][i];
  154     }
  155     }
  156 
  157     return NULL;
  158 }
  159 
  160 static inline apr_status_t napr_hash_rebuild(napr_hash_t *hash)
  161 {
  162     napr_hash_t *tmp;
  163     apr_size_t i, j;
  164     apr_status_t status;
  165 
  166     if (NULL ==
  167     (tmp =
  168      napr_hash_make(hash->pool, hashsize(hash->power + 1), hash->ffactor, hash->get_key, hash->get_key_len,
  169             hash->key_cmp, hash->hash))) {
  170     DEBUG_ERR("error calling napr_hash_init");
  171     return APR_EGENERAL;
  172     }
  173 
  174     for (i = 0; i < hash->size; i++) {
  175     for (j = 0; j < hash->filling_table[i]; j++) {
  176         /*
  177          * no need to do doublon test here as we take data directly from a
  178          * hash table
  179          */
  180         if (APR_SUCCESS !=
  181         (status =
  182          napr_hash_set(tmp, hash->table[i][j],
  183                    hash->hash(hash->get_key(hash->table[i][j]), hash->get_key_len(hash->table[i][j]))))) {
  184         char errbuf[128];
  185         DEBUG_ERR("error calling napr_hash_set: %s", apr_strerror(status, errbuf, 128));
  186         return status;
  187         }
  188     }
  189     }
  190     hash->table = tmp->table;
  191     hash->filling_table = tmp->filling_table;
  192     hash->nel = tmp->nel;
  193     hash->size = tmp->size;
  194     hash->mask = tmp->mask;
  195     hash->power = tmp->power;
  196     apr_pool_destroy(hash->own_pool);
  197     hash->own_pool = tmp->own_pool;
  198 
  199     return APR_SUCCESS;
  200 }
  201 
  202 extern void napr_hash_remove(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
  203 {
  204     apr_size_t nel, bucket, i, key_len;
  205     const void *key;
  206 
  207     bucket = hash_value & hash->mask;
  208     key = hash->get_key(data);
  209     key_len = hash->get_key_len(data);
  210     if (0 != (nel = hash->filling_table[bucket])) {
  211     for (i = 0; i < nel; i++) {
  212         //DEBUG_DBG( "key[%.*s] bucket[%i]=[%.*s]", key_len, key, i, hash->get_key_len(hash->table[bucket][i]), hash->get_key(hash->table[bucket][i]));
  213         if (key_len == hash->get_key_len(hash->table[bucket][i]))
  214         if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len))) {
  215             /* Remove it, by replacing with the last element if present */
  216             if (i != nel - 1) {
  217             hash->table[bucket][i] = hash->table[bucket][nel - 1];
  218             hash->table[bucket][nel - 1] = NULL;
  219             }
  220             else {
  221             hash->table[bucket][i] = NULL;
  222             }
  223             hash->filling_table[bucket]--;
  224             hash->nel--;
  225             break;
  226         }
  227     }
  228     }
  229     else {
  230     DEBUG_DBG("try to remove something that is not here");
  231     }
  232 }
  233 
  234 extern apr_status_t napr_hash_set(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
  235 {
  236     apr_size_t nel, bucket;
  237     apr_status_t status;
  238 
  239     bucket = hash_value & hash->mask;
  240 
  241     if ((0 == (nel = hash->filling_table[bucket])) & (NULL == hash->table[bucket])) {
  242     hash->table[bucket] = (void **) apr_pcalloc(hash->own_pool, hash->ffactor * sizeof(void *));
  243     }
  244     // DEBUG_DBG( "set data %.*s in bucket %u at nel %u", hash->datum_get_key_len(data), hash->datum_get_key(data), bucket, nel);
  245     hash->table[bucket][nel] = data;
  246     hash->filling_table[bucket]++;
  247     hash->nel++;
  248 
  249     if (hash->ffactor <= hash->filling_table[bucket]) {
  250     // int i;
  251     // DEBUG_DBG( "rebuilding hash table, because there's %u element in bucket %u ffactor is %u (total element = %u)", 
  252     //      hash->filling_table[bucket], bucket, hash->ffactor, hash->nel);
  253     // for(i = 0; i < hash->ffactor; i++) {
  254     //     DEBUG_DBG( "%.*s", hash->datum_get_key_len(hash->table[bucket][i]), hash->datum_get_key(hash->table[bucket][i]));
  255     // }
  256 
  257     if (APR_SUCCESS != (status = napr_hash_rebuild(hash))) {
  258         char errbuf[128];
  259         DEBUG_ERR("error calling napr_hash_rebuild: %s", apr_strerror(status, errbuf, 128));
  260         return status;
  261     }
  262     }
  263 
  264     return APR_SUCCESS;
  265 }
  266 
  267 extern apr_status_t napr_hash_apply_function(const napr_hash_t *hash, function_callback_fn_t function, void *param)
  268 {
  269     apr_size_t i, j;
  270     apr_status_t status;
  271 
  272     if (NULL != hash) {
  273     for (i = 0; i < hash->size; i++) {
  274         for (j = 0; j < hash->filling_table[i]; j++) {
  275         if (APR_SUCCESS != (status = function(hash->table[i][j], param))) {
  276             char errbuf[128];
  277             DEBUG_ERR("error calling function: %s", apr_strerror(status, errbuf, 128));
  278             return status;
  279         }
  280         }
  281     }
  282     }
  283 
  284     return APR_SUCCESS;
  285 }
  286 
  287 extern apr_size_t napr_hash_get_size(const napr_hash_t *hash)
  288 {
  289     return hash->size;
  290 }
  291 
  292 extern apr_size_t napr_hash_get_nel(const napr_hash_t *hash)
  293 {
  294     return hash->nel;
  295 }
  296 
  297 apr_pool_t *napr_hash_pool_get(const napr_hash_t *thehash)
  298 {
  299     return thehash->pool;
  300 }
  301 
  302 napr_hash_index_t *napr_hash_first(apr_pool_t *pool, napr_hash_t *hash)
  303 {
  304     napr_hash_index_t *hash_index;
  305     hash_index = apr_palloc(pool, sizeof(struct napr_hash_index_t));
  306     hash_index->hash = hash;
  307     hash_index->bucket = 0;
  308     hash_index->element = 0;
  309 
  310     if (hash->filling_table[0] > 0)
  311     return hash_index;
  312 
  313     return napr_hash_next(hash_index);
  314 }
  315 
  316 napr_hash_index_t *napr_hash_next(napr_hash_index_t *hash_index)
  317 {
  318     if ((0 != hash_index->hash->filling_table[hash_index->bucket])
  319     && (hash_index->element < (hash_index->hash->filling_table[hash_index->bucket] - 1))) {
  320     hash_index->element++;
  321     return hash_index;
  322     }
  323     else {
  324     hash_index->element = 0;
  325     for (hash_index->bucket += 1; hash_index->bucket < hash_index->hash->size; hash_index->bucket++) {
  326         if (0 != hash_index->hash->filling_table[hash_index->bucket])
  327         break;
  328     }
  329     if (hash_index->bucket < hash_index->hash->size)
  330         return hash_index;
  331     }
  332 
  333     return NULL;
  334 }
  335 
  336 void napr_hash_this(napr_hash_index_t *hi, const void **key, apr_size_t *klen, void **val)
  337 {
  338     if (key)
  339     *key = hi->hash->get_key(hi->hash->table[hi->bucket][hi->element]);
  340     if (klen)
  341     *klen = hi->hash->get_key_len(hi->hash->table[hi->bucket][hi->element]);
  342     if (val)
  343     *val = hi->hash->table[hi->bucket][hi->element];
  344 }