From 738c34d4bb8f1a3811acd00af8c6c12107f8315b Mon Sep 17 00:00:00 2001 From: Bruce Yinhe Date: Thu, 18 Jun 2015 11:31:02 +0200 Subject: Change license text to APLv2 --- erts/emulator/beam/hash.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index afaf32f8ce..e0fde337f2 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -3,16 +3,17 @@ * * Copyright Ericsson AB 1996-2009. 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% */ -- cgit v1.2.3 From 99e6213c0f0cebaa01f8310b6950a814cf4b21ee Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 13 Nov 2015 18:04:09 +0100 Subject: erts: Remove dead code erts_hash_merge --- erts/emulator/beam/hash.c | 50 ----------------------------------------------- 1 file changed, 50 deletions(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index e0fde337f2..636aafc108 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -280,56 +280,6 @@ void* hash_put(Hash* h, void* tmpl) 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 -- cgit v1.2.3 From 4b4c3d525a06309b7e23c7c3ccf7a358bd0f33f3 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Fri, 13 Nov 2015 18:12:32 +0100 Subject: erts: Redesign grow/shrink thresholds of hash.c 1. Use load factor as indicator, not used buckets. Used buckets is a bad indicator as it makes the situation even worse with a bad hash function. Set grow_threshold to load factor of 160% as it roughly corresponds to the old 80% used bucket limit. 2. Never shrink table below initial size. --- erts/emulator/beam/hash.c | 60 ++++++++++++++++++++++++----------------------- 1 file changed, 31 insertions(+), 29 deletions(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index 636aafc108..9d247db039 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -66,6 +66,7 @@ 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; @@ -76,14 +77,18 @@ void hash_get_info(HashInfo *hi, Hash *h) 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; } @@ -119,6 +124,15 @@ 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. @@ -145,10 +159,10 @@ Hash* hash_init(ErtsAlcType_t type, Hash* h, char* name, int size, HashFunctions 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; } @@ -199,32 +213,26 @@ 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); 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; @@ -232,6 +240,7 @@ static void rehash(Hash* h, int grow) } erts_free(h->type, (void *) h->bucket); h->bucket = new_bucket; + set_thresholds(h); } /* @@ -268,14 +277,11 @@ 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; } @@ -298,9 +304,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; } @@ -331,9 +335,7 @@ hash_remove(Hash *h, void *tmpl) 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; } -- cgit v1.2.3 From 2afa7580910050b9b087a188215f27553cc0aba3 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 30 Nov 2015 12:08:15 +0100 Subject: erts: Remove unused include files from hash.c Note that hash.c is quite "clean" from Erlang stuff and is used by erl_child_setup as well. --- erts/emulator/beam/hash.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index 9d247db039..75d091d11c 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -27,8 +27,6 @@ #endif #include "sys.h" -#include "erl_vm.h" -#include "global.h" #include "hash.h" /* -- cgit v1.2.3 From 17ecb94437bac6726044d299dde48d02dd2b2e9c Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 14 Jul 2015 15:20:16 +0200 Subject: erts: Refactor out erts functions from hash --- erts/emulator/beam/hash.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index e0fde337f2..acdec28e19 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -98,11 +98,11 @@ void hash_info(int to, void *arg, Hash* h) 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); } @@ -123,22 +123,22 @@ hash_table_sz(Hash *h) ** 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; @@ -155,11 +155,11 @@ Hash* hash_init(ErtsAlcType_t type, Hash* h, char* name, int size, HashFunctions /* ** 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; @@ -183,9 +183,9 @@ void hash_delete(Hash* h) 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); } /* @@ -213,7 +213,7 @@ static void rehash(Hash* h, int grow) h->size80percent = (4*h->size)/5; 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; @@ -230,7 +230,7 @@ static void rehash(Hash* h, int grow) 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; } -- cgit v1.2.3 From 6664eed554974336909d3ffe03f20349cc4c38fd Mon Sep 17 00:00:00 2001 From: Henrik Nord Date: Tue, 15 Mar 2016 15:19:56 +0100 Subject: update copyright-year --- erts/emulator/beam/hash.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts/emulator/beam/hash.c') diff --git a/erts/emulator/beam/hash.c b/erts/emulator/beam/hash.c index 5a0b93f693..e255b961f1 100644 --- a/erts/emulator/beam/hash.c +++ b/erts/emulator/beam/hash.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 1996-2009. All Rights Reserved. + * Copyright Ericsson AB 1996-2016. 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. -- cgit v1.2.3