/*
* %CopyrightBegin%
*
* Copyright Ericsson AB 1999-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.
*
* %CopyrightEnd%
*/
/*
* Code for process dictionaries.
*
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#include "erl_process.h" /* Will include erl_process_dict.h */
#include "error.h"
#include "erl_driver.h"
#include "bif.h"
#include "big.h"
#include "dist.h"
#include "erl_version.h"
/* #define HARDDEBUG */
/*
** Utility macros
*/
/* Flags to pd_get_hash */
#define PD_GET_OTHER_PROCESS 1UL
/* Hash constant macros */
#define MAX_HASH 1342177280UL
#define INITIAL_SIZE 10
/* Hash utility macros */
#define HASH_RANGE(PDict) ((PDict)->homeSize + (PDict)->splitPosition)
#define MAKE_HASH(Term) \
((is_small(Term)) ? unsigned_val(Term) : \
((is_atom(Term)) ? \
(atom_tab(atom_val(term))->slot.bucket.hvalue) : \
make_hash2(Term)))
#define PD_SZ2BYTES(Sz) (sizeof(ProcDict) + ((Sz) - 1)*sizeof(Eterm))
/* Memory allocation macros */
#define PD_ALLOC(Sz) \
erts_alloc(ERTS_ALC_T_PROC_DICT, (Sz))
#define PD_FREE(P, Sz) \
erts_free(ERTS_ALC_T_PROC_DICT, (P))
#define PD_REALLOC(P, OSz, NSz) \
erts_realloc(ERTS_ALC_T_PROC_DICT, (P), (NSz))
#define TCAR(Term) CAR(list_val(Term))
#define TCDR(Term) CDR(list_val(Term))
/* Array access macro */
#define ARRAY_GET(PDict, Index) (((PDict)->size > (Index)) ? \
(PDict)->data[Index] : NIL)
/*
* Forward decalarations
*/
static void pd_hash_erase(Process *p, Eterm id, Eterm *ret);
static void pd_hash_erase_all(Process *p);
static Eterm pd_hash_get_keys(Process *p, Eterm value);
static Eterm pd_hash_get_all(Process *p, ProcDict *pd);
static Eterm pd_hash_put(Process *p, Eterm id, Eterm value);
static void shrink(Process *p, Eterm* ret);
static void grow(Process *p);
static void array_shrink(ProcDict **ppd, unsigned int need);
static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term);
static unsigned int pd_hash_value(ProcDict *pdict, Eterm term);
static unsigned int next_array_size(unsigned int need);
/*
** Debugging prototypes and macros
*/
#ifdef HARDDEBUG
#include <stdarg.h>
static int hdebugf(char *format, ...);
static char *hdebugf_file = "";
static int hdebugf_line;
#define HDEBUGF(X) ((int) hdebugf_file = __FILE__, hdebugf_line = __LINE__, \
hdebugf X)
#ifndef DEBUG
#define DEBUG 1
#endif
#else /* !HARDDEBUG */
#define HDEBUGF(X) /* Nothing */
#endif /* HARDDEBUG (else) */
#ifdef DEBUG
static void pd_check(ProcDict *pd);
#define PD_CHECK(PD) pd_check(PD)
#else /* !DEBUG */
#define PD_CHECK(PD) /* Nothing */
#endif /* DEBUG (else) */
/*
** External interface
*/
/*
* Called from break handler
*/
void
erts_dictionary_dump(int to, void *to_arg, ProcDict *pd)
{
unsigned int i;
#ifdef DEBUG
/*PD_CHECK(pd);*/
if (pd == NULL)
return;
erts_print(to, to_arg, "(size = %d, used = %d, homeSize = %d, "
"splitPosition = %d, numElements = %d)\n",
pd->size, pd->used, pd->homeSize,
pd->splitPosition, (unsigned int) pd->numElements);
for (i = 0; i < HASH_RANGE(pd); ++i) {
erts_print(to, to_arg, "%d: %T\n", i, ARRAY_GET(pd, i));
}
#else /* !DEBUG */
int written = 0;
Eterm t;
erts_print(to, to_arg, "[");
if (pd != NULL) {
for (i = 0; i < HASH_RANGE(pd); ++i) {
t = ARRAY_GET(pd, i);
if (is_list(t)) {
for (; t != NIL; t = TCDR(t)) {
erts_print(to, to_arg, written++ ? ",%T" : "%T", TCAR(t));
}
} else if (is_tuple(t)) {
erts_print(to, to_arg, written++ ? ",%T" : "%T", t);
}
}
}
erts_print(to, to_arg, "]");
#endif /* DEBUG (else) */
}
void
erts_deep_dictionary_dump(int to, void *to_arg,
ProcDict* pd, void (*cb)(int, void *, Eterm))
{
unsigned int i;
Eterm t;
if (pd != NULL) {
for (i = 0; i < HASH_RANGE(pd); ++i) {
t = ARRAY_GET(pd, i);
if (is_list(t)) {
for (; t != NIL; t = TCDR(t)) {
(*cb)(to, to_arg, TCAR(t));
}
} else if (is_tuple(t)) {
(*cb)(to, to_arg, t);
}
}
}
}
Uint
erts_dicts_mem_size(Process *p)
{
Uint size = 0;
if (p->dictionary)
size += PD_SZ2BYTES(p->dictionary->size);
return size;
}
void
erts_erase_dicts(Process *p)
{
if (p->dictionary) {
pd_hash_erase_all(p);
p->dictionary = NULL;
}
}
/*
* Called from process_info/1,2.
*/
Eterm erts_dictionary_copy(Process *p, ProcDict *pd)
{
Eterm* hp;
Eterm* heap_start;
Eterm res = NIL;
Eterm tmp, tmp2;
unsigned int i, num;
if (pd == NULL) {
return res;
}
PD_CHECK(pd);
num = HASH_RANGE(pd);
heap_start = hp = (Eterm *) erts_alloc(ERTS_ALC_T_TMP,
sizeof(Eterm) * pd->numElements * 2);
for (i = 0; i < num; ++i) {
tmp = ARRAY_GET(pd, i);
if (is_boxed(tmp)) {
ASSERT(is_tuple(tmp));
res = CONS(hp, tmp, res);
hp += 2;
} else if (is_list(tmp)) {
while (tmp != NIL) {
tmp2 = TCAR(tmp);
res = CONS(hp, tmp2, res);
hp += 2;
tmp = TCDR(tmp);
}
}
}
res = copy_object(res, p);
erts_free(ERTS_ALC_T_TMP, (void *) heap_start);
return res;
}
/*
** BIF interface
*/
BIF_RETTYPE get_0(BIF_ALIST_0)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
BIF_RETTYPE get_1(BIF_ALIST_1)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
ret = erts_pd_hash_get(BIF_P, BIF_ARG_1);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
BIF_RETTYPE get_keys_1(BIF_ALIST_1)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
ret = pd_hash_get_keys(BIF_P, BIF_ARG_1);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
BIF_RETTYPE put_2(BIF_ALIST_2)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
ret = pd_hash_put(BIF_P, BIF_ARG_1, BIF_ARG_2);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
BIF_RETTYPE erase_0(BIF_ALIST_0)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
pd_hash_erase_all(BIF_P);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
BIF_RETTYPE erase_1(BIF_ALIST_1)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
pd_hash_erase(BIF_P, BIF_ARG_1, &ret);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
/*
* BIF implementations
*/
static void pd_hash_erase(Process *p, Eterm id, Eterm *ret)
{
unsigned int hval;
Eterm old;
Eterm tmp;
unsigned int range;
*ret = am_undefined;
if (p->dictionary == NULL) {
return;
}
hval = pd_hash_value(p->dictionary, id);
old = ARRAY_GET(p->dictionary, hval);
if (is_boxed(old)) { /* Tuple */
ASSERT(is_tuple(old));
if (EQ(tuple_val(old)[1], id)) {
array_put(&(p->dictionary), hval, NIL);
--(p->dictionary->numElements);
*ret = tuple_val(old)[2];
}
} else if (is_list(old)) {
/* Find cons cell for identical value */
Eterm* prev = &p->dictionary->data[hval];
for (tmp = *prev; tmp != NIL; prev = &TCDR(tmp), tmp = *prev) {
if (EQ(tuple_val(TCAR(tmp))[1], id)) {
*prev = TCDR(tmp);
*ret = tuple_val(TCAR(tmp))[2];
--(p->dictionary->numElements);
}
}
/* If there is only one element left in the list we must remove the list. */
old = ARRAY_GET(p->dictionary, hval);
ASSERT(is_list(old));
if (is_nil(TCDR(old))) {
array_put(&p->dictionary, hval, TCAR(old));
}
} else if (is_not_nil(old)) {
#ifdef DEBUG
erts_fprintf(stderr,
"Process dictionary for process %T is broken, trying to "
"display term found in line %d:\n"
"%T\n", p->id, __LINE__, old);
#endif
erl_exit(1, "Damaged process dictionary found during erase/1.");
}
if ((range = HASH_RANGE(p->dictionary)) > INITIAL_SIZE &&
range / 2 > (p->dictionary->numElements)) {
shrink(p, ret);
}
}
static void pd_hash_erase_all(Process *p)
{
if (p->dictionary != NULL) {
PD_FREE(p->dictionary, PD_SZ2BYTES(p->dictionary->size));
p->dictionary = NULL;
}
}
Eterm erts_pd_hash_get(Process *p, Eterm id)
{
unsigned int hval;
Eterm tmp;
ProcDict *pd = p->dictionary;
if (pd == NULL)
return am_undefined;
hval = pd_hash_value(pd, id);
tmp = ARRAY_GET(pd, hval);
if (is_boxed(tmp)) { /* Tuple */
ASSERT(is_tuple(tmp));
if (EQ(tuple_val(tmp)[1], id)) {
return tuple_val(tmp)[2];
}
} else if (is_list(tmp)) {
for (; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) {
;
}
if (tmp != NIL) {
return tuple_val(TCAR(tmp))[2];
}
} else if (is_not_nil(tmp)) {
#ifdef DEBUG
erts_fprintf(stderr,
"Process dictionary for process %T is broken, trying to "
"display term found in line %d:\n"
"%T\n", p->id, __LINE__, tmp);
#endif
erl_exit(1, "Damaged process dictionary found during get/1.");
}
return am_undefined;
}
static Eterm pd_hash_get_keys(Process *p, Eterm value)
{
Eterm *hp;
Eterm res = NIL;
ProcDict *pd = p->dictionary;
unsigned int i, num;
Eterm tmp, tmp2;
if (pd == NULL) {
return res;
}
num = HASH_RANGE(pd);
for (i = 0; i < num; ++i) {
tmp = ARRAY_GET(pd, i);
if (is_boxed(tmp)) {
ASSERT(is_tuple(tmp));
if (EQ(tuple_val(tmp)[2], value)) {
hp = HAlloc(p, 2);
res = CONS(hp, tuple_val(tmp)[1], res);
}
} else if (is_list(tmp)) {
while (tmp != NIL) {
tmp2 = TCAR(tmp);
if (EQ(tuple_val(tmp2)[2], value)) {
hp = HAlloc(p, 2);
res = CONS(hp, tuple_val(tmp2)[1], res);
}
tmp = TCDR(tmp);
}
}
}
return res;
}
static Eterm
pd_hash_get_all(Process *p, ProcDict *pd)
{
Eterm* hp;
Eterm res = NIL;
Eterm tmp, tmp2;
unsigned int i;
unsigned int num;
if (pd == NULL) {
return res;
}
num = HASH_RANGE(pd);
hp = HAlloc(p, pd->numElements * 2);
for (i = 0; i < num; ++i) {
tmp = ARRAY_GET(pd, i);
if (is_boxed(tmp)) {
ASSERT(is_tuple(tmp));
res = CONS(hp, tmp, res);
hp += 2;
} else if (is_list(tmp)) {
while (tmp != NIL) {
tmp2 = TCAR(tmp);
res = CONS(hp, tmp2, res);
hp += 2;
tmp = TCDR(tmp);
}
}
}
return res;
}
static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
{
unsigned int hval;
Eterm *hp;
Eterm tpl;
Eterm old;
Eterm tmp;
int needed;
int i = 0;
#ifdef DEBUG
Eterm *hp_limit;
#endif
if (p->dictionary == NULL) {
/* Create it */
array_put(&(p->dictionary), INITIAL_SIZE - 1, NIL);
p->dictionary->homeSize = INITIAL_SIZE;
}
hval = pd_hash_value(p->dictionary, id);
old = ARRAY_GET(p->dictionary, hval);
/*
* Calculate the number of heap words needed and garbage
* collect if necessary. (Might be a slight overestimation.)
*/
needed = 3; /* {Key,Value} tuple */
if (is_boxed(old)) {
/*
* We don't want to compare keys twice, so we'll always
* reserve the space for two CONS cells.
*/
needed += 2+2;
} else if (is_list(old)) {
i = 0;
for (tmp = old; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) {
++i;
}
if (is_nil(tmp)) {
i = -1;
needed += 2;
} else {
needed += 2*(i+1);
}
}
if (HeapWordsLeft(p) < needed) {
Eterm root[3];
root[0] = id;
root[1] = value;
root[2] = old;
BUMP_REDS(p, erts_garbage_collect(p, needed, root, 3));
id = root[0];
value = root[1];
old = root[2];
}
#ifdef DEBUG
hp_limit = p->htop + needed;
#endif
/*
* Create the {Key,Value} tuple.
*/
hp = HeapOnlyAlloc(p, 3);
tpl = TUPLE2(hp, id, value);
/*
* Update the dictionary.
*/
if (is_nil(old)) {
array_put(&(p->dictionary), hval, tpl);
++(p->dictionary->numElements);
} else if (is_boxed(old)) {
ASSERT(is_tuple(old));
if (EQ(tuple_val(old)[1],id)) {
array_put(&(p->dictionary), hval, tpl);
return tuple_val(old)[2];
} else {
hp = HeapOnlyAlloc(p, 4);
tmp = CONS(hp, old, NIL);
hp += 2;
++(p->dictionary->numElements);
array_put(&(p->dictionary), hval, CONS(hp, tpl, tmp));
hp += 2;
ASSERT(hp <= hp_limit);
}
} else if (is_list(old)) {
if (i == -1) {
/*
* New key. Simply prepend the tuple to the beginning of the list.
*/
hp = HeapOnlyAlloc(p, 2);
array_put(&(p->dictionary), hval, CONS(hp, tpl, old));
hp += 2;
ASSERT(hp <= hp_limit);
++(p->dictionary->numElements);
} else {
/*
* i = Number of CDRs to skip to reach the changed element in the list.
*
* Replace old value in list. To avoid pointers from the old generation
* to the new, we must rebuild the list from the beginning up to and
* including the changed element.
*/
Eterm nlist;
int j;
hp = HeapOnlyAlloc(p, (i+1)*2);
/* Find the list element to change. */
for (j = 0, nlist = old; j < i; j++, nlist = TCDR(nlist)) {
;
}
ASSERT(EQ(tuple_val(TCAR(nlist))[1], id));
nlist = TCDR(nlist); /* Unchanged part of list. */
/* Rebuild list before the updated element. */
for (tmp = old; i-- > 0; tmp = TCDR(tmp)) {
nlist = CONS(hp, TCAR(tmp), nlist);
hp += 2;
}
ASSERT(EQ(tuple_val(TCAR(tmp))[1], id));
/* Put the updated element first in the new list. */
nlist = CONS(hp, tpl, nlist);
hp += 2;
ASSERT(hp <= hp_limit);
array_put(&(p->dictionary), hval, nlist);
return tuple_val(TCAR(tmp))[2];
}
} else {
#ifdef DEBUG
erts_fprintf(stderr,
"Process dictionary for process %T is broken, trying to "
"display term found in line %d:\n"
"%T\n", p->id, __LINE__, old);
#endif
erl_exit(1, "Damaged process dictionary found during put/2.");
}
if (HASH_RANGE(p->dictionary) <= p->dictionary->numElements) {
grow(p);
}
return am_undefined;
}
/*
* Hash table utilities, rehashing
*/
static void shrink(Process *p, Eterm* ret)
{
unsigned int range = HASH_RANGE(p->dictionary);
unsigned int steps = (range*3) / 10;
Eterm hi, lo, tmp;
unsigned int i;
Eterm *hp;
#ifdef DEBUG
Eterm *hp_limit;
#endif
if (range - steps < INITIAL_SIZE) {
steps = range - INITIAL_SIZE;
}
for (i = 0; i < steps; ++i) {
ProcDict *pd = p->dictionary;
if (pd->splitPosition == 0) {
pd->homeSize /= 2;
pd->splitPosition = pd->homeSize;
}
--(pd->splitPosition);
hi = ARRAY_GET(pd, (pd->splitPosition + pd->homeSize));
lo = ARRAY_GET(pd, pd->splitPosition);
if (hi != NIL) {
if (lo == NIL) {
array_put(&(p->dictionary), pd->splitPosition, hi);
} else {
int needed = 4;
if (is_list(hi) && is_list(lo)) {
needed = 2*list_length(hi);
}
if (HeapWordsLeft(p) < needed) {
BUMP_REDS(p, erts_garbage_collect(p, needed, ret, 1));
hi = pd->data[(pd->splitPosition + pd->homeSize)];
lo = pd->data[pd->splitPosition];
}
#ifdef DEBUG
hp_limit = p->htop + needed;
#endif
if (is_tuple(lo)) {
if (is_tuple(hi)) {
hp = HeapOnlyAlloc(p, 4);
tmp = CONS(hp, hi, NIL);
hp += 2;
array_put(&(p->dictionary), pd->splitPosition,
CONS(hp,lo,tmp));
hp += 2;
ASSERT(hp <= hp_limit);
} else { /* hi is a list */
hp = HeapOnlyAlloc(p, 2);
array_put(&(p->dictionary), pd->splitPosition,
CONS(hp, lo, hi));
hp += 2;
ASSERT(hp <= hp_limit);
}
} else { /* lo is a list */
if (is_tuple(hi)) {
hp = HeapOnlyAlloc(p, 2);
array_put(&(p->dictionary), pd->splitPosition,
CONS(hp, hi, lo));
hp += 2;
ASSERT(hp <= hp_limit);
} else { /* Two lists */
hp = HeapOnlyAlloc(p, needed);
for (tmp = hi; tmp != NIL; tmp = TCDR(tmp)) {
lo = CONS(hp, TCAR(tmp), lo);
hp += 2;
}
ASSERT(hp <= hp_limit);
array_put(&(p->dictionary), pd->splitPosition, lo);
}
}
}
}
array_put(&(p->dictionary), (pd->splitPosition + pd->homeSize), NIL);
}
if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) {
array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2);
}
}
static void grow(Process *p)
{
unsigned int i,j;
unsigned int steps = p->dictionary->homeSize / 5;
Eterm l1,l2;
Eterm l;
Eterm *hp;
unsigned int pos;
unsigned int homeSize;
int needed = 0;
ProcDict *pd;
#ifdef DEBUG
Eterm *hp_limit;
#endif
HDEBUGF(("grow: steps = %d", steps));
if (steps == 0)
steps = 1;
/* Dont grow over MAX_HASH */
if ((MAX_HASH - steps) <= HASH_RANGE(p->dictionary)) {
return;
}
/*
* Calculate total number of heap words needed, and garbage collect
* if necessary.
*/
pd = p->dictionary;
pos = pd->splitPosition;
homeSize = pd->homeSize;
for (i = 0; i < steps; ++i) {
if (pos == homeSize) {
homeSize *= 2;
pos = 0;
}
l = ARRAY_GET(pd, pos);
pos++;
if (is_not_tuple(l)) {
while (l != NIL) {
needed += 2;
l = TCDR(l);
}
}
}
if (HeapWordsLeft(p) < needed) {
BUMP_REDS(p, erts_garbage_collect(p, needed, 0, 0));
}
#ifdef DEBUG
hp_limit = p->htop + needed;
#endif
/*
* Now grow.
*/
for (i = 0; i < steps; ++i) {
ProcDict *pd = p->dictionary;
if (pd->splitPosition == pd->homeSize) {
pd->homeSize *= 2;
pd->splitPosition = 0;
}
pos = pd->splitPosition;
++pd->splitPosition; /* For the hashes */
l = ARRAY_GET(pd, pos);
if (is_tuple(l)) {
if (pd_hash_value(pd, tuple_val(l)[1]) != pos) {
array_put(&(p->dictionary), pos +
p->dictionary->homeSize, l);
array_put(&(p->dictionary), pos, NIL);
}
} else {
l2 = NIL;
l1 = l;
for (j = 0; l1 != NIL; l1 = TCDR(l1))
j += 2;
hp = HeapOnlyAlloc(p, j);
while (l != NIL) {
if (pd_hash_value(pd, tuple_val(TCAR(l))[1]) == pos)
l1 = CONS(hp, TCAR(l), l1);
else
l2 = CONS(hp, TCAR(l), l2);
hp += 2;
l = TCDR(l);
}
if (l1 != NIL && TCDR(l1) == NIL)
l1 = TCAR(l1);
if (l2 != NIL && TCDR(l2) == NIL)
l2 = TCAR(l2);
ASSERT(hp <= hp_limit);
/* After array_put pd is no longer valid */
array_put(&(p->dictionary), pos, l1);
array_put(&(p->dictionary), pos +
p->dictionary->homeSize, l2);
}
}
#ifdef HARDDEBUG
dictionary_dump(p->dictionary,CERR);
#endif
}
/*
** Array oriented operations
*/
static void array_shrink(ProcDict **ppd, unsigned int need)
{
unsigned int siz = next_array_size(need);
HDEBUGF(("array_shrink: size = %d, used = %d, need = %d",
(*ppd)->size, (*ppd)->used, need));
if (siz > (*ppd)->size)
return; /* Only shrink */
*ppd = PD_REALLOC(((void *) *ppd),
PD_SZ2BYTES((*ppd)->size),
PD_SZ2BYTES(siz));
(*ppd)->size = siz;
if ((*ppd)->size < (*ppd)->used)
(*ppd)->used = (*ppd)->size;
}
static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term)
{
unsigned int i;
Eterm ret;
if (*ppdict == NULL) {
Uint siz = next_array_size(ndx+1);
ProcDict *p;
p = PD_ALLOC(PD_SZ2BYTES(siz));
for (i = 0; i < siz; ++i)
p->data[i] = NIL;
p->size = siz;
p->homeSize = p->splitPosition = p->numElements = p->used = 0;
*ppdict = p;
} else if (ndx >= (*ppdict)->size) {
Uint osize = (*ppdict)->size;
Uint nsize = next_array_size(ndx+1);
*ppdict = PD_REALLOC(((void *) *ppdict),
PD_SZ2BYTES(osize),
PD_SZ2BYTES(nsize));
for (i = osize; i < nsize; ++i)
(*ppdict)->data[i] = NIL;
(*ppdict)->size = nsize;
}
ret = (*ppdict)->data[ndx];
(*ppdict)->data[ndx] = term;
if ((ndx + 1) > (*ppdict)->used)
(*ppdict)->used = ndx + 1;
#ifdef HARDDEBUG
HDEBUGF(("array_put: (*ppdict)->size = %d, (*ppdict)->used = %d, ndx = %d",
(*ppdict)->size, (*ppdict)->used, ndx));
erts_fprintf(stderr, "%T", term);
#endif /* HARDDEBUG */
return ret;
}
/*
** Basic utilities
*/
static unsigned int pd_hash_value(ProcDict *pdict, Eterm term)
{
Uint hash, high;
hash = MAKE_HASH(term);
high = hash % (pdict->homeSize*2);
if (high >= HASH_RANGE(pdict))
return hash % pdict->homeSize;
return high;
}
static unsigned int next_array_size(unsigned int need)
{
static unsigned int tab[] =
{
10UL,
20UL,
40UL,
80UL,
160UL,
320UL,
640UL,
1280UL,
2560UL,
5120UL,
10240UL,
20480UL,
40960UL,
81920UL,
163840UL,
327680UL,
655360UL,
1310720UL,
2621440UL,
5242880UL,
10485760UL,
20971520UL,
41943040UL,
83886080UL,
167772160UL,
335544320UL,
671088640UL,
1342177280UL,
2684354560UL
};
int hi = sizeof(tab) / sizeof(Uint) - 1;
int lo = 1;
int cur = 4;
while (hi >= lo) {
if (tab[cur] >= need && tab[cur - 1] < need)
return tab[cur];
if (tab[cur] > need)
hi = cur - 1;
else
lo = cur + 1;
cur = (hi + lo) / 2;
}
return need;
}
/*
** Debug functions
*/
#ifdef DEBUG
static void pd_check(ProcDict *pd)
{
unsigned int i;
Uint num;
if (pd == NULL)
return;
ASSERT(pd->size >= pd->used);
ASSERT(HASH_RANGE(pd) <= MAX_HASH);
for (i = 0, num = 0; i < pd->used; ++i) {
Eterm t = pd->data[i];
if (is_nil(t)) {
continue;
} else if (is_tuple(t)) {
++num;
ASSERT(arityval(*tuple_val(t)) == 2);
continue;
} else if (is_list(t)) {
while (t != NIL) {
++num;
ASSERT(is_tuple(TCAR(t)));
ASSERT(arityval(*(tuple_val(TCAR(t)))) == 2);
t = TCDR(t);
}
continue;
} else {
erl_exit(1,
"Found tag 0x%08x in process dictionary at position %d",
(unsigned long) t, (int) i);
}
}
ASSERT(num == pd->numElements);
ASSERT(pd->splitPosition <= pd->homeSize);
}
#endif /* DEBUG */
#ifdef HARDDEBUG
static int hdebugf(char *format, ...)
{
va_list ap;
erts_fprintf(stderr, "DEBUG: %s:%d :", hdebugf_file, hdebugf_line);
va_start(ap, format);
erts_vfprintf(stderr, format, ap);
va_end(ap);
erts_fprintf(stderr, "\n");
return 0;
}
#endif /* HARDDEBUG */
