X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=libopkg%2Fhash_table.c;h=2d42d911f741f4d07cb30e63024d5fe500adcaf2;hb=b65cb493330307f8028e7e8ae88f312cb47842b3;hp=41877c2f3e60993a00324b6ddf93ffba62ba4126;hpb=4b0b7ca249bfa4ecc099c2ca56527eb91776f198;p=oweals%2Fopkg-lede.git diff --git a/libopkg/hash_table.c b/libopkg/hash_table.c index 41877c2..2d42d91 100644 --- a/libopkg/hash_table.c +++ b/libopkg/hash_table.c @@ -15,72 +15,94 @@ General Public License for more details. */ -#include #include #include #include #include "hash_table.h" #include "opkg_message.h" +#include "libbb/libbb.h" -static int hash_index(hash_table_t *hash, const char *pkg_name); -static int rotating(const char *key, int len, int prime); - -static int hash_index(hash_table_t *hash, const char *pkg_name) +static unsigned long +djb2_hash(const unsigned char *str) { - return rotating(pkg_name, strlen(pkg_name), hash->n_entries); + unsigned long hash = 5381; + int c; + while ((c = *str++)) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + return hash; } - -static int rotating(const char *key, int len, int prime) + +static int +hash_index(hash_table_t *hash, const char *key) { - unsigned int hash, i; - for (hash=len, i=0; i>28)^key[i]; - return (hash % prime); + return djb2_hash((const unsigned char *)key) % hash->n_buckets; } - /* * this is an open table keyed by strings */ -int hash_table_init(const char *name, hash_table_t *hash, int len) +void +hash_table_init(const char *name, hash_table_t *hash, int len) { - static int primes_table[] = { - 379, 761, 983, 1423, 2711, 3361, 3931, 4679, 5519, 6701, 9587, - 19471, 23143, 33961, 46499, 49727, 99529, 0 - }; - int *picker; - - if (hash->entries != NULL) { - /* we have been here already */ - return 0; - } + if (hash->entries != NULL) { + fprintf(stderr, "ERROR: %s called on a non empty hash table\n", + __FUNCTION__); + return; + } - hash->name = name; - hash->entries = NULL; - hash->n_entries = 0; - hash->hash_entry_key = NULL; - - picker = primes_table; - while(*picker && (*picker++ < len)); - if(!*picker) - fprintf(stderr, "%s: primes table might not be big enough (! << %d)\n", __FUNCTION__, len); - --picker; - - hash->n_entries = *picker; - hash->entries = (hash_entry_t *)calloc(hash->n_entries, sizeof(hash_entry_t)); - if (hash->entries == NULL) { - fprintf(stderr, "%s: Out of memory.\n", __FUNCTION__); - return ENOMEM; - } - return 0; + memset(hash, 0, sizeof(hash_table_t)); + + hash->name = name; + hash->n_buckets = len; + hash->entries = xcalloc(hash->n_buckets, sizeof(hash_entry_t)); +} + +void +hash_print_stats(hash_table_t *hash) +{ + printf("hash_table: %s, %d bytes\n" + "\tn_buckets=%d, n_elements=%d, n_collisions=%d\n" + "\tmax_bucket_len=%d, n_used_buckets=%d, ave_bucket_len=%.2f\n" + "\tn_hits=%d, n_misses=%d\n", + hash->name, + hash->n_buckets*(int)sizeof(hash_entry_t), + hash->n_buckets, + hash->n_elements, + hash->n_collisions, + hash->max_bucket_len, + hash->n_used_buckets, + (hash->n_used_buckets ? + ((float)hash->n_elements)/hash->n_used_buckets : 0.0f), + hash->n_hits, + hash->n_misses); } void hash_table_deinit(hash_table_t *hash) { - free(hash->entries); + int i; + if (!hash) + return; + + /* free the reminaing entries */ + for (i = 0; i < hash->n_buckets; i++) { + hash_entry_t *hash_entry = (hash->entries + i); + free (hash_entry->key); + /* skip the first entry as this is part of the array */ + hash_entry = hash_entry->next; + while (hash_entry) + { + hash_entry_t *old = hash_entry; + hash_entry = hash_entry->next; + free (old->key); + free (old); + } + } + + free (hash->entries); + hash->entries = NULL; - hash->n_entries = 0; + hash->n_buckets = 0; } void *hash_table_get(hash_table_t *hash, const char *key) @@ -93,23 +115,24 @@ void *hash_table_get(hash_table_t *hash, const char *key) { if (strcmp(key, hash_entry->key) == 0) { // opkg_message(NULL, OPKG_DEBUG, "Function: %s. Key found for '%s' \n", __FUNCTION__, key); + hash->n_hits++; return hash_entry->data; } } hash_entry = hash_entry->next; } + hash->n_misses++; return NULL; } int hash_table_insert(hash_table_t *hash, const char *key, void *value) { + int bucket_len = 0; int ndx= hash_index(hash, key); hash_entry_t *hash_entry = hash->entries + ndx; - if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Inserting in hash for '%s' \n", __FUNCTION__, key); if (hash_entry->key) { if (strcmp(hash_entry->key, key) == 0) { /* alread in table, update the value */ - if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash for '%s' \n", __FUNCTION__, key); hash_entry->data = value; return 0; } else { @@ -118,24 +141,63 @@ int hash_table_insert(hash_table_t *hash, const char *key, void *value) * then add a new entry * before we can hook up the value */ - if (0) opkg_message(NULL, OPKG_DEBUG2, "Function: %s. Value already in hash by collision for '%s' \n", __FUNCTION__, key); - while (hash_entry->next) + while (hash_entry->next) { hash_entry = hash_entry->next; - hash_entry->next = (hash_entry_t *)malloc(sizeof(hash_entry_t)); - if (!hash_entry->next) { - return -ENOMEM; - } + if (strcmp(hash_entry->key, key) == 0) { + hash_entry->data = value; + return 0; + } + bucket_len++; + } + hash_entry->next = xcalloc(1, sizeof(hash_entry_t)); hash_entry = hash_entry->next; hash_entry->next = NULL; + + hash->n_collisions++; + if (++bucket_len > hash->max_bucket_len) + hash->max_bucket_len = bucket_len; } - } + } else + hash->n_used_buckets++; + hash->n_elements++; - hash_entry->key = strdup(key); + hash_entry->key = xstrdup(key); hash_entry->data = value; return 0; } +int hash_table_remove(hash_table_t *hash, const char *key) +{ + int ndx= hash_index(hash, key); + hash_entry_t *hash_entry = hash->entries + ndx; + hash_entry_t *next_entry=NULL, *last_entry=NULL; + while (hash_entry) + { + if (hash_entry->key) + { + if (strcmp(key, hash_entry->key) == 0) { + free(hash_entry->key); + if (last_entry) { + last_entry->next = hash_entry->next; + free(hash_entry); + } else { + next_entry = hash_entry->next; + if (next_entry) { + memmove(hash_entry, next_entry, sizeof(hash_entry_t)); + free(next_entry); + } else { + memset(hash_entry, 0 , sizeof(hash_entry_t)); + } + } + return 1; + } + } + last_entry = hash_entry; + hash_entry = hash_entry->next; + } + return 0; +} void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *entry, void *data), void *data) { @@ -143,7 +205,7 @@ void hash_table_foreach(hash_table_t *hash, void (*f)(const char *key, void *ent if (!hash || !f) return; - for (i = 0; i < hash->n_entries; i++) { + for (i = 0; i < hash->n_buckets; i++) { hash_entry_t *hash_entry = (hash->entries + i); do { if(hash_entry->key) {