/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 1996-2009. All Rights Reserved.
*
* 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.
*
* %CopyrightEnd%
*/
/*
** General hash functions
**
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#include "hash.h"
/*
** List of sizes (all are primes)
*/
static const int h_size_table[] = {
2, 5, 11, 23, 47, 97, 197, 397, 797, /* double upto here */
1201, 1597,
2411, 3203,
4813, 6421,
9643, 12853,
19289, 25717,
51437,
102877,
205759,
411527,
823117,
1646237,
3292489,
6584983,
13169977,
26339969,
52679969,
-1
};
/*
** Get info about hash
**
*/
void hash_get_info(HashInfo *hi, Hash *h)
{
int size = h->size;
int i;
int max_depth = 0;
int objects = 0;
for (i = 0; i < size; i++) {
int depth = 0;
HashBucket* b = h->bucket[i];
while (b != (HashBucket*) 0) {
objects++;
depth++;
b = b->next;
}
if (depth > max_depth)
max_depth = depth;
}
hi->name = h->name;
hi->size = h->size;
hi->used = h->used;
hi->objs = objects;
hi->depth = max_depth;
}
/*
** Display info about hash
**
*/
void hash_info(int to, void *arg, Hash* h)
{
HashInfo hi;
hash_get_info(&hi, h);
erts_print(to, arg, "=hash_table:%s\n", hi.name);
erts_print(to, arg, "size: %d\n", hi.size);
erts_print(to, arg, "used: %d\n", hi.used);
erts_print(to, arg, "objs: %d\n", hi.objs);
erts_print(to, arg, "depth: %d\n", hi.depth);
}
/*
* Returns size of table in bytes. Stored objects not included.
*/
int
hash_table_sz(Hash *h)
{
int i;
for(i=0;h->name[i];i++);
i++;
return sizeof(Hash) + h->size*sizeof(HashBucket*) + i;
}
/*
** init a pre allocated or static hash structure
** and allocate buckets.
*/
Hash* hash_init(ErtsAlcType_t type, Hash* h, char* name, int size, HashFunctions fun)
{
int sz;
int ix = 0;
h->type = type;
while (h_size_table[ix] != -1 && h_size_table[ix] < size)
ix++;
if (h_size_table[ix] == -1)
erl_exit(1, "panic: too large hash table size (%d)\n", size);
size = h_size_table[ix];
sz = size*sizeof(HashBucket*);
h->bucket = (HashBucket**) erts_alloc(h->type, sz);
sys_memzero(h->bucket, sz);
h->is_allocated = 0;
h->name = name;
h->fun = fun;
h->size = size;
h->size20percent = h->size/5;
h->size80percent = (4*h->size)/5;
h->ix = ix;
h->used = 0;
return h;
}
/*
** Create a new hash table
*/
Hash* hash_new(ErtsAlcType_t type, char* name, int size, HashFunctions fun)
{
Hash* h;
h = erts_alloc(type, sizeof(Hash));
h = hash_init(type, h, name, size, fun);
h->is_allocated = 1;
return h;
}
/*
** Delete hash table and all objects
*/
void hash_delete(Hash* h)
{
int old_size = h->size;
int i;
for (i = 0; i < old_size; i++) {
HashBucket* b = h->bucket[i];
while (b != (HashBucket*) 0) {
HashBucket* b_next = b->next;
h->fun.free((void*) b);
b = b_next;
}
}
erts_free(h->type, h->bucket);
if (h->is_allocated)
erts_free(h->type, (void*) h);
}
/*
** Rehash all objects
*/
static void rehash(Hash* h, int grow)
{
int sz;
int old_size = h->size;
HashBucket** new_bucket;
int i;
if (grow) {
if ((h_size_table[h->ix+1]) == -1)
return;
h->ix++;
}
else {
if (h->ix == 0)
return;
h->ix--;
}
h->size = h_size_table[h->ix];
h->size20percent = h->size/5;
h->size80percent = (4*h->size)/5;
sz = h->size*sizeof(HashBucket*);
new_bucket = (HashBucket **) erts_alloc(h->type, sz);
sys_memzero(new_bucket, sz);
h->used = 0;
for (i = 0; i < old_size; i++) {
HashBucket* b = h->bucket[i];
while (b != (HashBucket*) 0) {
HashBucket* b_next = b->next;
int ix = b->hvalue % h->size;
if (new_bucket[ix] == NULL)
h->used++;
b->next = new_bucket[ix];
new_bucket[ix] = b;
b = b_next;
}
}
erts_free(h->type, (void *) h->bucket);
h->bucket = new_bucket;
}
/*
** Find an object in the hash table
**
*/
void* hash_get(Hash* h, void* tmpl)
{
HashValue hval = h->fun.hash(tmpl);
int ix = hval % h->size;
HashBucket* b = h->bucket[ix];
while(b != (HashBucket*) 0) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0))
return (void*) b;
b = b->next;
}
return (void*) 0;
}
/*
** Find or insert an object in the hash table
*/
void* hash_put(Hash* h, void* tmpl)
{
HashValue hval = h->fun.hash(tmpl);
int ix = hval % h->size;
HashBucket* b = h->bucket[ix];
while(b != (HashBucket*) 0) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0))
return (void*) b;
b = b->next;
}
b = (HashBucket*) h->fun.alloc(tmpl);
if (h->bucket[ix] == NULL)
h->used++;
b->hvalue = hval;
b->next = h->bucket[ix];
h->bucket[ix] = b;
if (h->used > h->size80percent) /* rehash at 80% */
rehash(h, 1);
return (void*) b;
}
static void
hash_insert_entry(Hash* h, HashBucket* entry)
{
HashValue hval = entry->hvalue;
int ix = hval % h->size;
HashBucket* b = h->bucket[ix];
while (b != (HashBucket*) 0) {
if ((b->hvalue == hval) && (h->fun.cmp((void*)entry, (void*)b) == 0)) {
abort(); /* Should not happen */
}
b = b->next;
}
if (h->bucket[ix] == NULL)
h->used++;
entry->next = h->bucket[ix];
h->bucket[ix] = entry;
if (h->used > h->size80percent) /* rehash at 80% */
rehash(h, 1);
}
/*
* Move all entries in src into dst; empty src.
* Entries in src must not exist in dst.
*/
void
erts_hash_merge(Hash* src, Hash* dst)
{
int limit = src->size;
HashBucket** bucket = src->bucket;
int i;
src->used = 0;
for (i = 0; i < limit; i++) {
HashBucket* b = bucket[i];
HashBucket* next;
bucket[i] = NULL;
while (b) {
next = b->next;
hash_insert_entry(dst, b);
b = next;
}
}
}
/*
** Erase hash entry return template if erased
** return 0 if not erased
*/
void* hash_erase(Hash* h, void* tmpl)
{
HashValue hval = h->fun.hash(tmpl);
int ix = hval % h->size;
HashBucket* b = h->bucket[ix];
HashBucket* prev = 0;
while(b != 0) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0)) {
if (prev != 0)
prev->next = b->next;
else
h->bucket[ix] = b->next;
h->fun.free((void*)b);
if (h->bucket[ix] == NULL)
h->used--;
if (h->used < h->size20percent) /* rehash at 20% */
rehash(h, 0);
return tmpl;
}
prev = b;
b = b->next;
}
return (void*)0;
}
/*
** Remove hash entry from table return entry if removed
** return NULL if not removed
** NOTE: hash_remove() differs from hash_erase() in that
** it returns entry (not the template) and does
** *not* call the free() callback.
*/
void *
hash_remove(Hash *h, void *tmpl)
{
HashValue hval = h->fun.hash(tmpl);
int ix = hval % h->size;
HashBucket *b = h->bucket[ix];
HashBucket *prev = NULL;
while (b) {
if ((b->hvalue == hval) && (h->fun.cmp(tmpl, (void*)b) == 0)) {
if (prev)
prev->next = b->next;
else
h->bucket[ix] = b->next;
if (h->bucket[ix] == NULL)
h->used--;
if (h->used < h->size20percent) /* rehash at 20% */
rehash(h, 0);
return (void *) b;
}
prev = b;
b = b->next;
}
return NULL;
}
void hash_foreach(Hash* h, void (*func)(void *, void *), void *func_arg2)
{
int i;
for (i = 0; i < h->size; i++) {
HashBucket* b = h->bucket[i];
while(b != (HashBucket*) 0) {
(*func)((void *) b, func_arg2);
b = b->next;
}
}
}
