aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/hash.c')
-rw-r--r--erts/emulator/beam/hash.c188
1 files changed, 69 insertions, 119 deletions
diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c
index afaf32f8ce..8548e30e8b 100644
--- a/erts/emulator/beam/hash.c
+++ b/erts/emulator/beam/hash.c
@@ -1,18 +1,19 @@
/*
* %CopyrightBegin%
*
- * Copyright Ericsson AB 1996-2009. All Rights Reserved.
+ * Copyright Ericsson AB 1996-2016. All Rights Reserved.
*
- * The contents of this file are subject to the Erlang Public License,
- * Version 1.1, (the "License"); you may not use this file except in
- * compliance with the License. You should have received a copy of the
- * Erlang Public License along with this software. If not, it can be
- * retrieved online at http://www.erlang.org/.
- *
- * Software distributed under the License is distributed on an "AS IS"
- * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
- * the License for the specific language governing rights and limitations
- * under the License.
+ * 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%
*/
@@ -26,8 +27,6 @@
#endif
#include "sys.h"
-#include "erl_vm.h"
-#include "global.h"
#include "hash.h"
/*
@@ -36,9 +35,9 @@
static const int h_size_table[] = {
2, 5, 11, 23, 47, 97, 197, 397, 797, /* double upto here */
1201, 1597,
- 2411, 3203,
+ 2411, 3203,
4813, 6421,
- 9643, 12853,
+ 9643, 12853,
19289, 25717,
51437,
102877,
@@ -50,8 +49,8 @@ static const int h_size_table[] = {
6584983,
13169977,
26339969,
- 52679969,
- -1
+ 52679969,
+ -1
};
/*
@@ -65,24 +64,29 @@ void hash_get_info(HashInfo *hi, Hash *h)
int i;
int max_depth = 0;
int objects = 0;
+ int used = 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;
+ if (depth) {
+ used++;
+ if (depth > max_depth)
+ max_depth = depth;
+ }
}
+ ASSERT(objects == h->nobjs);
hi->name = h->name;
hi->size = h->size;
- hi->used = h->used;
- hi->objs = objects;
+ hi->used = used;
+ hi->objs = h->nobjs;
hi->depth = max_depth;
}
@@ -91,24 +95,24 @@ void hash_get_info(HashInfo *hi, Hash *h)
**
*/
-void hash_info(int to, void *arg, Hash* h)
+void hash_info(fmtfn_t 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);
+ h->fun.meta_print(to, arg, "=hash_table:%s\n", hi.name);
+ h->fun.meta_print(to, arg, "size: %d\n", hi.size);
+ h->fun.meta_print(to, arg, "used: %d\n", hi.used);
+ h->fun.meta_print(to, arg, "objs: %d\n", hi.objs);
+ h->fun.meta_print(to, arg, "depth: %d\n", hi.depth);
}
/*
* Returns size of table in bytes. Stored objects not included.
*/
-int
+int
hash_table_sz(Hash *h)
{
int i;
@@ -118,47 +122,56 @@ hash_table_sz(Hash *h)
}
+static ERTS_INLINE void set_thresholds(Hash* h)
+{
+ h->grow_threshold = (8*h->size)/5; /* grow at 160% load */
+ if (h->size_ix > h->min_size_ix)
+ h->shrink_threshold = h->size / 5; /* shrink at 20% load */
+ else
+ h->shrink_threshold = -1; /* never shrink below inital size */
+}
+
/*
** 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)
+Hash* hash_init(int type, Hash* h, char* name, int size, HashFunctions fun)
{
int sz;
int ix = 0;
- h->type = type;
+ h->meta_alloc_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);
+ return NULL;
size = h_size_table[ix];
sz = size*sizeof(HashBucket*);
- h->bucket = (HashBucket**) erts_alloc(h->type, sz);
+ h->bucket = (HashBucket**) fun.meta_alloc(h->meta_alloc_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;
+ h->size_ix = ix;
+ h->min_size_ix = ix;
+ h->nobjs = 0;
+ set_thresholds(h);
return h;
}
/*
** Create a new hash table
*/
-Hash* hash_new(ErtsAlcType_t type, char* name, int size, HashFunctions fun)
+Hash* hash_new(int type, char* name, int size, HashFunctions fun)
{
Hash* h;
- h = erts_alloc(type, sizeof(Hash));
+ h = fun.meta_alloc(type, sizeof(Hash));
h = hash_init(type, h, name, size, fun);
h->is_allocated = 1;
@@ -177,14 +190,14 @@ void hash_delete(Hash* h)
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);
+ h->fun.meta_free(h->meta_alloc_type, h->bucket);
if (h->is_allocated)
- erts_free(h->type, (void*) h);
+ h->fun.meta_free(h->meta_alloc_type, (void*) h);
}
/*
@@ -198,39 +211,34 @@ static void rehash(Hash* h, int grow)
int i;
if (grow) {
- if ((h_size_table[h->ix+1]) == -1)
+ if ((h_size_table[h->size_ix+1]) == -1)
return;
- h->ix++;
+ h->size_ix++;
}
else {
- if (h->ix == 0)
+ if (h->size_ix == 0)
return;
- h->ix--;
+ h->size_ix--;
}
- h->size = h_size_table[h->ix];
- h->size20percent = h->size/5;
- h->size80percent = (4*h->size)/5;
+ h->size = h_size_table[h->size_ix];
sz = h->size*sizeof(HashBucket*);
- new_bucket = (HashBucket **) erts_alloc(h->type, sz);
+ new_bucket = (HashBucket **) h->fun.meta_alloc(h->meta_alloc_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->fun.meta_free(h->meta_alloc_type, (void *) h->bucket);
h->bucket = new_bucket;
+ set_thresholds(h);
}
/*
@@ -242,7 +250,7 @@ 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;
@@ -267,68 +275,15 @@ void* hash_put(Hash* h, void* tmpl)
}
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% */
+ if (++h->nobjs > h->grow_threshold)
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
@@ -339,7 +294,7 @@ void* hash_erase(Hash* h, void* 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)
@@ -347,9 +302,7 @@ void* hash_erase(Hash* h, void* tmpl)
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% */
+ if (--h->nobjs < h->shrink_threshold)
rehash(h, 0);
return tmpl;
}
@@ -373,16 +326,14 @@ hash_remove(Hash *h, void *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% */
+ if (--h->nobjs < h->shrink_threshold)
rehash(h, 0);
return (void *) b;
}
@@ -404,4 +355,3 @@ void hash_foreach(Hash* h, void (*func)(void *, void *), void *func_arg2)
}
}
}
-
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-27 23:39:34 +0000