#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wstrict-prototypes"
#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/stdlib/strhash.c,v 1.10 2002/03/22 21:53:10 obrien Exp $");
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <strhash.h>
#define HASH_NULL (hash_table *)0
#define NODE_NULL (hash_node *)0
#define GENERIC_NULL (void *)0
#define HASH_SZ 97
static int _hash(int size, char *key);
static hash_node *list_find(caddr_t key, hash_node *head);
static int assign_key(char *key, hash_node *node);
hash_table *
hash_create(int size)
{
int i;
hash_table *new = (hash_table *)malloc(sizeof(hash_table));
if (!new || size < 0){
return HASH_NULL;
}
if (size == 0){
size = HASH_SZ;
}
if (!(new->buckets = (hash_node **)malloc(size * sizeof(hash_node *)))){
return HASH_NULL;
}
for (i = 0; i < size; i++){
new->buckets[i] = NODE_NULL;
}
new->size = size;
return new;
}
static hash_node *
list_find(caddr_t key, hash_node *head)
{
while (head){
if (!strcmp(head->key, key)){
return head;
}
head = head->next;
}
return NODE_NULL;
}
static int
_hash(int size, char *key)
{
unsigned int h = 0x0;
while (*key){
h = (h << 1) ^ (h ^ (unsigned char) *key++);
}
h %= size;
return h;
}
void
hash_destroy(hash_table *table, char *key, void (*nukefunc)())
{
int bucket = _hash(table->size, key);
hash_node *found = table->buckets[bucket];
hash_node *to_free = NODE_NULL;
if (!found) {
return;
}
if (!strcmp(found->key, key)) {
table->buckets[bucket] = found->next;
to_free = found;
}
else {
while (found->next) {
if (!strcmp(found->next->key, key)) {
to_free = found->next;
found->next = found->next->next;
break;
}
found = found->next;
}
if (!to_free){
return;
}
}
if (nukefunc)
(*nukefunc)(to_free->key, to_free->data);
free(to_free);
return;
}
void *
hash_search(hash_table *table, caddr_t key, void *datum,
void (*replace_func)())
{
int bucket = _hash(table->size, key);
hash_node *found = list_find(key, table->buckets[bucket]);
if (found){
if (!replace_func){
return found->data;
}
else{
(*replace_func)(found->data);
found->data = datum;
}
}
else{
if (datum){
hash_node *new = (hash_node *)malloc(sizeof(hash_node));
if (!new || !assign_key(key, new)){
return GENERIC_NULL;
}
new->data = datum;
new->next = table->buckets[bucket];
table->buckets[bucket] = new;
return new;
}
}
return GENERIC_NULL;
}
static int
assign_key(char *key, hash_node *node)
{
if (!node || !key){
return 0;
}
if (!(node->key = (char *)malloc(strlen(key) + 1))){
return 0;
}
node->key[0] = '\0';
strcat(node->key, key);
return 1;
}
void
hash_traverse(hash_table *table, int (*func)(), void *arg)
{
int i;
int size = table->size;
if (!func)
return;
for (i = 0; i < size; i++) {
hash_node *n = table->buckets[i];
while (n) {
if ((*func)(n->key, n->data, arg) == 0)
return;
n = n->next;
}
}
return;
}
void
hash_purge(hash_table *table, void (*purge_func)(char *p1, void *p2))
{
int i;
int size = table->size;
for (i = 0; i < size; i++) {
hash_node *n = table->buckets[i];
if (n) {
do {
hash_node *to_free = n;
if (purge_func) {
(*purge_func)(n->key, n->data);
}
n = n->next;
free(to_free);
} while (n);
table->buckets[i] = NODE_NULL;
}
}
}
#undef min
#define min(a, b) (a) < (b) ? (a) : (b)
void
hash_stats(hash_table *table, int verbose)
{
int i;
int total_elements = 0;
int non_empty_buckets = 0;
int max_count = 0;
int max_repeats = 0;
int *counts;
int size = table->size;
if (!(counts = (int *)malloc(size * sizeof(int)))){
fprintf(stderr, "malloc returns 0\n");
exit(1);
}
for (i = 0; i < size; i++){
int x = 0;
hash_node *n = table->buckets[i];
counts[i] = 0;
while (n){
if (!x){
x = 1;
non_empty_buckets++;
if (verbose){
printf("bucket %2d: ", i);
}
}
if (verbose){
printf(" %s", n->key);
}
counts[i]++;
n = n->next;
}
total_elements += counts[i];
if (counts[i] > max_count){
max_count = counts[i];
max_repeats = 1;
}
else if (counts[i] == max_count){
max_repeats++;
}
if (counts[i] && verbose){
printf(" (%d)\n", counts[i]);
}
}
printf("\n");
printf("%d element%s in storage.\n", total_elements, total_elements == 1 ? "" : "s");
if (total_elements){
printf("%d of %d (%.2f%%) buckets are in use\n", non_empty_buckets, size,
(double)100 * (double)non_empty_buckets / (double)(size));
printf("the maximum number of elements in a bucket is %d (%d times)\n", max_count, max_repeats);
printf("average per bucket is %f\n", (double)total_elements / (double)non_empty_buckets);
printf("optimal would be %f\n", (double)total_elements / (double)(min(size, total_elements)));
}
return;
}
#pragma clang diagnostic pop