/*
 * Copyright (C) 2007 François Pesce : francois.pesce (at) gmail (dot) com
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 * 	http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "lookup3.h"
#include "debug.h"
#include "napr_hash.h"

#define hashsize(n) ((apr_size_t)1<<(n))
#define hashmask(n) (hashsize(n)-1)

static const void *str_get_key(const void *opaque)
{
    return opaque;
}

static apr_size_t str_get_key_len(const void *opaque)
{
    const char *str = opaque;
    return strlen(str);
}

static int str_key_cmp(const void *opaque1, const void *opaque2, apr_size_t len)
{
    const char *str1 = opaque1;
    const char *str2 = opaque2;

    return memcmp(str1, str2, len);
}

static apr_uint32_t str_hash(register const void *opaque, register apr_size_t len)
{
    return hashlittle(opaque, len, 0x1337cafe);
}

struct napr_hash_index_t
{
    napr_hash_t *hash;
    apr_size_t bucket;
    apr_size_t element;		/* of a bucket */
};

struct napr_hash_t
{
    /* void *table[size][ffactor] */
    void ***table;
    /* apr_size_t table[size] contain the number of element for each bucket */
    apr_size_t *filling_table;
    /* parent pool */
    apr_pool_t *pool;
    /* own pool that will be cleaned if a grow of the table occured */
    apr_pool_t *own_pool;
    /* Function to get the key from the datum */
    get_key_callback_fn_t *get_key;
    /* Function to get the key len from the datum */
    get_key_len_callback_fn_t *get_key_len;
    /* Function to compare two keys */
    key_cmp_callback_fn_t *key_cmp;
    /* hash function */
    hash_callback_fn_t *hash;

    /* the number of element contained in all the buckets of the table */
    apr_size_t nel;
    /* the number of buckets */
    apr_size_t size;
    /* desired density */
    apr_size_t ffactor;
    /* the binary mask to apply to the result of a hash function that return a
     * number < size */
    apr_uint32_t mask;
    /* size of the hash is hashsize(power) as mask is hashmask(power) */
    unsigned char power;
};

extern napr_hash_t *napr_hash_str_make(apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor)
{
    return napr_hash_make(pool, nel, ffactor, str_get_key, str_get_key_len, str_key_cmp, str_hash);
}

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,
				   get_key_len_callback_fn_t get_key_len, key_cmp_callback_fn_t key_cmp,
				   hash_callback_fn_t hash)
{
    napr_hash_t *result;
    apr_status_t status;

    if (NULL == (result = apr_pcalloc(pool, sizeof(struct napr_hash_t)))) {
	DEBUG_ERR("allocation error");
	return NULL;
    }

    while (hashsize(result->power) < nel)
	result->power++;

    result->size = hashsize(result->power);
    result->mask = hashmask(result->power);
    result->ffactor = ffactor;
    result->get_key = get_key;
    result->get_key_len = get_key_len;
    result->key_cmp = key_cmp;
    result->hash = hash;
    result->pool = pool;

    if (APR_SUCCESS != (status = apr_pool_create(&(result->own_pool), pool))) {
	char errbuf[128];
	DEBUG_ERR("error calling apr_pool_create: %s", apr_strerror(status, errbuf, 128));
	return NULL;
    }
    /*DEBUG_DBG("readjusting size to %" APR_SIZE_T_FMT " to store %" APR_SIZE_T_FMT " elements", result->size, nel); */
    /*DEBUG_DBG("bit mask will be 0x%x", result->mask); */

    if (NULL == (result->table = apr_pcalloc(result->own_pool, result->size * sizeof(void **)))) {
	DEBUG_ERR("allocation error");
	return NULL;
    }

    if (NULL == (result->filling_table = apr_pcalloc(result->own_pool, result->size * sizeof(apr_size_t)))) {
	DEBUG_ERR("allocation error");
	return NULL;
    }

    return result;
}

extern void *napr_hash_search(napr_hash_t *hash, const void *key, apr_size_t key_len, apr_uint32_t *hash_value)
{
    apr_uint32_t key_hash;
    apr_size_t i, nel, bucket;

    key_hash = hash->hash(key, key_len);

    if (NULL != hash_value)
	*hash_value = key_hash;

    bucket = key_hash & hash->mask;
    if (0 != (nel = hash->filling_table[bucket])) {
	for (i = 0; i < nel; i++) {
	    /*DEBUG_DBG( "key[%p] bucket[%"APR_SIZE_T_FMT"][%"APR_SIZE_T_FMT"]=[%p]", key, bucket, i, hash->get_key(hash->table[bucket][i])); */
	    if (key_len == hash->get_key_len(hash->table[bucket][i]))
		if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len)))
		    return hash->table[bucket][i];
	}
    }

    return NULL;
}

static inline apr_status_t napr_hash_rebuild(napr_hash_t *hash)
{
    napr_hash_t *tmp;
    apr_size_t i, j;
    apr_status_t status;

    if (NULL ==
	(tmp =
	 napr_hash_make(hash->pool, hashsize(hash->power + 1), hash->ffactor, hash->get_key, hash->get_key_len,
			hash->key_cmp, hash->hash))) {
	DEBUG_ERR("error calling napr_hash_init");
	return APR_EGENERAL;
    }

    for (i = 0; i < hash->size; i++) {
	for (j = 0; j < hash->filling_table[i]; j++) {
	    /*
	     * no need to do doublon test here as we take data directly from a
	     * hash table
	     */
	    if (APR_SUCCESS !=
		(status =
		 napr_hash_set(tmp, hash->table[i][j],
			       hash->hash(hash->get_key(hash->table[i][j]), hash->get_key_len(hash->table[i][j]))))) {
		char errbuf[128];
		DEBUG_ERR("error calling napr_hash_set: %s", apr_strerror(status, errbuf, 128));
		return status;
	    }
	}
    }
    hash->table = tmp->table;
    hash->filling_table = tmp->filling_table;
    hash->nel = tmp->nel;
    hash->size = tmp->size;
    hash->mask = tmp->mask;
    hash->power = tmp->power;
    apr_pool_destroy(hash->own_pool);
    hash->own_pool = tmp->own_pool;

    return APR_SUCCESS;
}

extern void napr_hash_remove(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
{
    apr_size_t nel, bucket, i, key_len;
    const void *key;

    bucket = hash_value & hash->mask;
    key = hash->get_key(data);
    key_len = hash->get_key_len(data);
    if (0 != (nel = hash->filling_table[bucket])) {
	for (i = 0; i < nel; i++) {
	    //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]));
	    if (key_len == hash->get_key_len(hash->table[bucket][i]))
		if (0 == (hash->key_cmp(key, hash->get_key(hash->table[bucket][i]), key_len))) {
		    /* Remove it, by replacing with the last element if present */
		    if (i != nel - 1) {
			hash->table[bucket][i] = hash->table[bucket][nel - 1];
			hash->table[bucket][nel - 1] = NULL;
		    }
		    else {
			hash->table[bucket][i] = NULL;
		    }
		    hash->filling_table[bucket]--;
		    hash->nel--;
		    break;
		}
	}
    }
    else {
	DEBUG_DBG("try to remove something that is not here");
    }
}

extern apr_status_t napr_hash_set(napr_hash_t *hash, void *data, apr_uint32_t hash_value)
{
    apr_size_t nel, bucket;
    apr_status_t status;

    bucket = hash_value & hash->mask;

    if ((0 == (nel = hash->filling_table[bucket])) & (NULL == hash->table[bucket])) {
	hash->table[bucket] = apr_pcalloc(hash->own_pool, hash->ffactor * sizeof(void *));
    }
    // DEBUG_DBG( "set data %.*s in bucket %u at nel %u", hash->datum_get_key_len(data), hash->datum_get_key(data), bucket, nel);
    hash->table[bucket][nel] = data;
    hash->filling_table[bucket]++;
    hash->nel++;

    if (hash->ffactor <= hash->filling_table[bucket]) {
	// int i;
	// DEBUG_DBG( "rebuilding hash table, because there's %u element in bucket %u ffactor is %u (total element = %u)", 
	//      hash->filling_table[bucket], bucket, hash->ffactor, hash->nel);
	// for(i = 0; i < hash->ffactor; i++) {
	//     DEBUG_DBG( "%.*s", hash->datum_get_key_len(hash->table[bucket][i]), hash->datum_get_key(hash->table[bucket][i]));
	// }

	if (APR_SUCCESS != (status = napr_hash_rebuild(hash))) {
	    char errbuf[128];
	    DEBUG_ERR("error calling napr_hash_rebuild: %s", apr_strerror(status, errbuf, 128));
	    return status;
	}
    }

    return APR_SUCCESS;
}

extern apr_status_t napr_hash_apply_function(const napr_hash_t *hash, function_callback_fn_t function, void *param)
{
    apr_size_t i, j;
    apr_status_t status;

    if (NULL != hash) {
	for (i = 0; i < hash->size; i++) {
	    for (j = 0; j < hash->filling_table[i]; j++) {
		if (APR_SUCCESS != (status = function(hash->table[i][j], param))) {
		    char errbuf[128];
		    DEBUG_ERR("error calling function: %s", apr_strerror(status, errbuf, 128));
		    return status;
		}
	    }
	}
    }

    return APR_SUCCESS;
}

extern apr_size_t napr_hash_get_size(const napr_hash_t *hash)
{
    return hash->size;
}

extern apr_size_t napr_hash_get_nel(const napr_hash_t *hash)
{
    return hash->nel;
}

apr_pool_t *napr_hash_pool_get(const napr_hash_t *thehash)
{
    return thehash->pool;
}

napr_hash_index_t *napr_hash_first(apr_pool_t *pool, napr_hash_t *hash)
{
    napr_hash_index_t *hash_index;
    hash_index = apr_palloc(pool, sizeof(struct napr_hash_index_t));
    hash_index->hash = hash;
    hash_index->bucket = 0;
    hash_index->element = 0;

    if (hash->filling_table[0] > 0)
	return hash_index;

    return napr_hash_next(hash_index);
}

napr_hash_index_t *napr_hash_next(napr_hash_index_t *hash_index)
{
    if ((0 != hash_index->hash->filling_table[hash_index->bucket])
	&& (hash_index->element < (hash_index->hash->filling_table[hash_index->bucket] - 1))) {
	hash_index->element++;
	return hash_index;
    }
    else {
	hash_index->element = 0;
	for (hash_index->bucket += 1; hash_index->bucket < hash_index->hash->size; hash_index->bucket++) {
	    if (0 != hash_index->hash->filling_table[hash_index->bucket])
		break;
	}
	if (hash_index->bucket < hash_index->hash->size)
	    return hash_index;
    }

    return NULL;
}

void napr_hash_this(napr_hash_index_t *hi, const void **key, apr_size_t *klen, void **val)
{
    if (key)
	*key = hi->hash->get_key(hi->hash->table[hi->bucket][hi->element]);
    if (klen)
	*klen = hi->hash->get_key_len(hi->hash->table[hi->bucket][hi->element]);
    if (val)
	*val = hi->hash->table[hi->bucket][hi->element];
}