X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=libopkg%2Fhash_table.c;h=2d42d911f741f4d07cb30e63024d5fe500adcaf2;hb=b65cb493330307f8028e7e8ae88f312cb47842b3;hp=6de90856d8694ccf06aec96890f4f62e5d88d4b7;hpb=11af232b19155c76002b5ca1f2b0e89d75699d3a;p=oweals%2Fopkg-lede.git diff --git a/libopkg/hash_table.c b/libopkg/hash_table.c index 6de9085..2d42d91 100644 --- a/libopkg/hash_table.c +++ b/libopkg/hash_table.c @@ -15,7 +15,6 @@ General Public License for more details. */ -#include #include #include #include @@ -24,57 +23,59 @@ #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) @@ -84,7 +85,7 @@ void hash_table_deinit(hash_table_t *hash) return; /* free the reminaing entries */ - for (i = 0; i < hash->n_entries; i++) { + 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 */ @@ -101,7 +102,7 @@ void hash_table_deinit(hash_table_t *hash) 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) @@ -114,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 { @@ -139,22 +141,25 @@ 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) { hash_entry = hash_entry->next; if (strcmp(hash_entry->key, key) == 0) { hash_entry->data = value; return 0; } + bucket_len++; } - hash_entry->next = (hash_entry_t *)calloc(1, sizeof(hash_entry_t)); - if (!hash_entry->next) { - return -ENOMEM; - } + 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 = xstrdup(key); hash_entry->data = value; @@ -200,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) {