aht.c

web服务器访问统计

			if (n.table[h]) {
				n.collisions++;
				while(1) {
					h = (h+1) & n.sizemask;
					if (!n.table[h])
						break;
					n.collisions++;
				}
			}
			/* Move the element */
			n.table[h] = t->table[i];
			t->used--;
		}
	}
	assert(t->used == 0);
	free(t->table);

	/* Remap the new hashtable in the old */
	*t = n;
	return HT_OK;
}

/* Add an element, discarding the old if the key already exists */
int ht_replace(struct hashtable *t, void *key, void *data)
{
	int ret;
	unsigned int index;

	/* Try to add the element */
	ret = ht_add(t, key, data);
	if (ret == HT_OK || ret != HT_BUSY)
		return ret;
	/* It already exists, get the index */
	ret = ht_search(t, key, &index);
	assert(ret == HT_FOUND);
	/* Remove the old */
	ret = ht_free(t, index);
	assert(ret == HT_OK);
	/* And add the new */
	return ht_add(t, key, data);
}

/* Add an element to the target hash table */
int ht_add(struct hashtable *t, void *key, void *data)
{
	int ret;
	unsigned int index;

	/* If the element isn't in the table ht_insert() will store
	 * the index of the free ht_ele in the integer pointer by *index */
	ret = ht_insert(t, key, &index);
	if (ret != HT_OK)
		return ret;

	/* Allocates the memory and stores key */
	if ((t->table[index] = malloc(sizeof(struct ht_ele))) == NULL)
		return HT_NOMEM;
	/* Store the pointers */
	t->table[index]->key = key;
	t->table[index]->data = data;
	t->used++;
	return HT_OK;
}

/* search and remove an element */
int ht_rm(struct hashtable *t, void *key)
{
	int ret;
	unsigned int index;

	if ((ret = ht_search(t, key, &index)) != HT_FOUND)
		return ret;
	return ht_free(t, index);
}

/* Destroy an entire hash table */
int ht_destroy(struct hashtable *t)
{
	unsigned int i;

	/* Free all the elements */
	for (i = 0; i < t->size && t->used > 0; i++) {
		if (t->table[i] != NULL && t->table[i] != ht_free_element) {
			if (t->key_destructor)
				t->key_destructor(t->table[i]->key);
			if (t->val_destructor)
				t->val_destructor(t->table[i]->data);
			free(t->table[i]);
			t->used--;
		}
	}
	/* Free the table and the allocated cache structure */
	free(t->table);
	/* Re-initialize the table */
	ht_reset(t);
	return HT_OK; /* Actually ht_destroy never fails */
}

/* Free an element in the hash table */
int ht_free(struct hashtable *t, unsigned int index)
{
	if (index >= t->size)
		return HT_IOVERFLOW; /* Index overflow */
	/* ht_free() calls against non-existent elements are ignored */
	if (t->table[index] != NULL && t->table[index] != ht_free_element) {
		/* release the key */
		if (t->key_destructor)
			t->key_destructor(t->table[index]->key);
		/* release the value */
		if (t->val_destructor)
			t->val_destructor(t->table[index]->data);
		/* free the element structure */
		free(t->table[index]);
		/* mark the element as freed */
		t->table[index] = ht_free_element;
		t->used--;
	}
	return HT_OK;
}

/* Search the element with the given key */
int ht_search(struct hashtable *t, void *key, unsigned int *found_index)
{
	int ret;
	u_int32_t h;

	/* Expand the hashtable if needed */
	if (t->size == 0) {
		if ((ret = ht_expand_if_needed(t)) != HT_OK)
			return ret;
	}

	/* Try using the first hash functions */
	h = t->hashf(key) & t->sizemask;
	/* this handles the removed elements */
	if (!t->table[h])
		return HT_NOTFOUND;
	if (t->table[h] != ht_free_element &&
	    t->key_compare(key, t->table[h]->key))
	{
		*found_index = h;
		return HT_FOUND;
	}

	while(1) {
		h = (h+1) & t->sizemask;
		/* this handles the removed elements */
		if (t->table[h] == ht_free_element)
			continue;
		if (!t->table[h])
			return HT_NOTFOUND;
		if (t->key_compare(key, t->table[h]->key)) {
			*found_index = h;
			return HT_FOUND;
		}
	}
}

/* This function is used to run the entire hash table,
 * it returns:
 * 1  if the element with the given index is valid
 * 0  if the element with the given index is empty or marked free
 * -1 if the element if out of the range */
int ht_get_byindex(struct hashtable *t, unsigned int index)
{
	if (index >= t->size)
		return -1;
	if (t->table[index] == NULL || t->table[index] == ht_free_element)
		return 0;
	return 1;
}

/* Returns the hash table as an array of paris of key/value void* pointers.
 * The array is allocated with malloc() and should be freed when no
 * longer useful. The key and value pointers should not be freed or
 * altered in any way, they will be handled by the hash table structure.
 *
 * This function is mainly useful to sort the hashtable's content
 * without to alter the hashtable itself.
 *
 * Returns NULL on out of memory. */
void **ht_get_array(struct hashtable *t)
{
	int used = ht_used(t);
	void **table, **tptr;
	long idx;

	if ((table = (void**) malloc(sizeof(void*)*(used*2))) == NULL)
		return NULL;
	tptr = table;
	for (idx = 0; ;idx++) {
		int type = ht_get_byindex(t, idx);
		if (type == -1) break;
		if (type == 0) continue;
		*tptr++ = ht_key(t, idx);
		*tptr++ = ht_value(t, idx);
	}
	return table;
}
/* ------------------------- private functions ------------------------------ */

/* Expand the hash table if needed */
static int ht_expand_if_needed(struct hashtable *t)
{
	/* If the hash table is empty expand it to the intial size,
	 * if the table is half-full redobule its size. */
	if (t->size == 0)
		return ht_expand(t, HT_INITIAL_SIZE);
	if (t->size <= t->used*2)
		return ht_expand(t, t->size * 2);
	return HT_OK;
}

/* Our hash table capability is a power of two */
static unsigned int next_power(unsigned int size)
{
	unsigned int i = 256;

	if (size >= 2147483648U)
		return 2147483648U;
	while(1) {
		if (i >= size)
			return i;
		i *= 2;
	}
}

/* the insert function to add elements out of ht expansion */
static int ht_insert(struct hashtable *t, void *key, unsigned int *avail_index)
{
	int ret;
	u_int32_t h;

	/* Expand the hashtable if needed */
	if ((ret = ht_expand_if_needed(t)) != HT_OK)
		return ret;

	/* Try using the first hash functions */
	h = t->hashf(key) & t->sizemask;
	/* this handles the removed elements */
	if (!t->table[h] || t->table[h] == ht_free_element) {
		*avail_index = h;
		return HT_OK;
	}
	t->collisions++;
	if (t->key_compare(key, t->table[h]->key))
		return HT_BUSY;

	while(1) {
		h = (h+1) & t->sizemask;
		/* this handles the removed elements */
		if (!t->table[h] || t->table[h] == ht_free_element) {
			*avail_index = h;
			return HT_OK;
		}
		t->collisions++;
		if (t->key_compare(key, t->table[h]->key))
			return HT_BUSY;
	}
}

/* ------------------------- provided destructors --------------------------- */

/* destructor for heap allocated keys/values */
void ht_destructor_free(void *obj)
{
	free(obj);
}

/* ------------------------- provided comparators --------------------------- */

/* default key_compare method */
int ht_compare_ptr(void *key1, void *key2)
{
	return (key1 == key2);
}

/* key compare for nul-terminated strings */
int ht_compare_string(void *key1, void *key2)
{
	return (strcmp(key1, key2) == 0) ? 1 : 0;
}

/* -------------------- hash functions for common data types --------------- */

/* We make this global to allow hash function randomization,
 * as security measure against attacker-induced worst case behaviuor.
 *
 * Note that being H_i the strong hash function with init value of i
 * and H_i' the same hash function with init value of i' than:
 *
 * if H_i(StringOne) is equal to H_i(CollidingStringTwo)
 *
 *    it is NOT true that
 *
 *  H_i'(StringOne) is equal to H_i''(CollidingStringTwo)
 */
static u_int32_t strong_hash_init_val = 0xF937A21;

/* Set the secret initialization value. It should be set from
 * a secure PRNG like /dev/urandom at program initialization time */
void ht_set_strong_hash_init_val(u_int32_t secret)
{
	strong_hash_init_val = secret;
}

/* __ht_strong_hash wrapper that mix a user-provided initval
 * with the global strong_hash_init_val. __ht_strong_hash is
 * even exported directly. */
u_int32_t ht_strong_hash(u_int8_t *k, u_int32_t length, u_int32_t initval)
{
	return __ht_strong_hash(k, length, initval^strong_hash_init_val);
}

/* Hash function suitable for C strings and other data types using
 * a 0-byte as terminator */
u_int32_t ht_hash_string(void *key)
{
	return __ht_strong_hash(key, strlen(key), strong_hash_init_val);
}

/* This one is to hash the value of the pointer itself. */
u_int32_t ht_hash_pointer(void *key)
{
	return __ht_strong_hash((void*)&key, sizeof(void*), strong_hash_init_val);
}