erl_db_hash.c

OTP是开放电信平台的简称

    FixedDeletion *fixd;

    for (i = 0; i < tb->nactive; i++) {
	if ((list = BUCKET(tb,i)) != 0) {
	    fixd = (FixedDeletion *)
		erts_db_alloc(ERTS_ALC_T_DB_FIX_DEL,
			      (DbTable *) tb,
			      sizeof(FixedDeletion));
	    fixd->slot = i;
	    fixd->next = tb->fixdel;
	    tb->fixdel = fixd;
	    while(list != 0) {
		list->hvalue = INVALID_HASH;
		list = list->next;
	    }
	}
    }
    tb->common.kept_items = tb->common.nitems;
    tb->common.nitems = 0;
    return DB_ERROR_NONE;
}

/* Display hash table contents (for dump) */
static void db_print_hash(int to, void *to_arg, int show, DbTable *tbl)
{
    DbTableHash *tb = &tbl->hash;
    int i;
    
    erts_print(to, to_arg, "Buckets: %d \n", tb->nactive);
    
    if (show) {
	for (i = 0; i < tb->nactive; i++) {
	    HashDbTerm* list = BUCKET(tb,i);
	    if (list == NULL)
		continue;
	    erts_print(to, to_arg, "%d: [", i);
	    while(list != 0) {
		if (list->hvalue == INVALID_HASH)
		    erts_print(to, to_arg, "*");
		erts_print(to, to_arg, "%T", make_tuple(list->dbterm.tpl));
		if (list->next != 0)
		    erts_print(to, to_arg, ",");
		list = list->next;
	    }
	    erts_print(to, to_arg, "]\n");
	}
    }
}

/* release all memory occupied by a single table */
static int db_free_table_hash(DbTable *tbl)
{
    DbTableHash *tb = &tbl->hash;
    HashDbTerm*** sp = tb->seg;
    int n = tb->nsegs;

    while (tb->fixdel != NULL) {
	FixedDeletion *fx = tb->fixdel;
	tb->fixdel = fx->next;
	erts_db_free(ERTS_ALC_T_DB_FIX_DEL,
		     (DbTable *) tb,
		     (void *) fx,
		     sizeof(FixedDeletion));
    }
    while(n--) {
	HashDbTerm** bp = *sp;
	if (bp != 0) {
	    int m = SEGSZ;

	    while(m--) {
		HashDbTerm* p = *bp++;

		while(p != 0) {
		    HashDbTerm* nxt = p->next;
		    free_term(tb, p);
		    p = nxt;
		}
	    }
	    erts_db_free(ERTS_ALC_T_DB_SEG,
			 (DbTable *) tb,
			 (void *) *sp,
			 sizeof(HashDbTerm*)*SEGSZ);
	}
	sp++;
    }
    erts_db_free(ERTS_ALC_T_DB_SEG_TAB,
		 (DbTable *) tb,
		 (void *) tb->seg,
		 sizeof(HashDbTerm**)*tb->nsegs);

    ASSERT(erts_smp_atomic_read(&tb->common.memory_size) == sizeof(DbTable));
    return 0;
}

static int db_free_table_continue_hash(DbTable *tbl, int first)
{
    DbTableHash *tb = &tbl->hash;
    HashDbTerm*** sp = tb->seg;
    int n = tb->nsegs;
    int done;

    /*
     * Optimization: tb->p will hold the number of the next
     * bucket to be deleted so that we quickly can skip deleted buckets.
     */
    if (first) {
	tb->p = 0;		/* Initialize. */
    } else {
	/* Skip already deleted buckets. */
	sp += tb->p;
	n -= tb->p;
    }

    done = 0;
    while (tb->fixdel != NULL) {
	FixedDeletion *fx = tb->fixdel;

	tb->fixdel = fx->next;
	erts_db_free(ERTS_ALC_T_DB_FIX_DEL,
		     (DbTable *) tb,
		     (void *) fx,
		     sizeof(FixedDeletion));
	if (++done >= 2*DELETE_RECORD_LIMIT) {
	    return 0;		/* Not done */
	}
    }

    done = done / 2;
    while(n--) {
	HashDbTerm** bp = *sp;
	if (bp != 0) {
	    int m = SEGSZ;

	    while(m--) {
		HashDbTerm* p = *bp++;

		while (p != 0) {
		    HashDbTerm* nxt = p->next;
		    free_term(tb, p);
		    tb->common.nitems--; /* Needed for correct reduction counting */
		    p = nxt;
		}
	    }
	    erts_db_free(ERTS_ALC_T_DB_SEG,
			 (DbTable *) tb,
			 (void *) *sp,
			 sizeof(HashDbTerm*)*SEGSZ);

	    /*
	     * Mark this segment done. (Necessary if the non-interruptible
	     * delete function will be invoked if the process is killed.)
	     */
	    *sp = NULL;

	    /*
	     * If we have done enough work, get out here.
	     */
	    if (++done >= (DELETE_RECORD_LIMIT / CHAIN_LEN / SEGSZ)) {
		tb->p = sp - tb->seg + 1; /* Remember where we stopped. */
		return 0;	/* Not done */
	    }
	}
	sp++;
    }
    erts_db_free(ERTS_ALC_T_DB_SEG_TAB,
		 (DbTable *) tb,
		 (void *) tb->seg,
		 sizeof(HashDbTerm**)*tb->nsegs);

    ASSERT(erts_smp_atomic_read(&tb->common.memory_size) == sizeof(DbTable));
    return 1;			/* Done */
}



/*
** Utility routines. (static)
*/
/*
** For the select functions, analyzes the pattern and determines which
** part of the tree should be searched. Also compiles the match program
*/
static int analyze_pattern(DbTableHash *tb, Eterm pattern, 
			   struct mp_info *mpi)
{
    Eterm *ptpl;
    Eterm lst, tpl, ttpl;
    Eterm *matches,*guards, *bodies;
    Eterm sbuff[30];
    Eterm *buff = sbuff;
    Eterm key = NIL;	       
    HashValue hval = NIL;      
    int num_heads = 0;
    int i;
    
    mpi->lists = mpi->dlists;
    mpi->num_lists = 0;
    mpi->key_given = 1;
    mpi->something_can_match = 0;
    mpi->all_objects = 1;
    mpi->mp = NULL;

    for (lst = pattern; is_list(lst); lst = CDR(list_val(lst)))
	++num_heads;

    if (lst != NIL) {/* proper list... */
	return DB_ERROR_BADPARAM;
    }

    if (num_heads > 10) {
	buff = erts_alloc(ERTS_ALC_T_DB_TMP, sizeof(Eterm) * num_heads * 3);
	mpi->lists = erts_alloc(ERTS_ALC_T_DB_SEL_LIST,
				sizeof(*(mpi->lists)) * num_heads);
	
    }

    matches = buff;
    guards = buff + num_heads;
    bodies = buff + (num_heads * 2);

    i = 0;
    for(lst = pattern; is_list(lst); lst = CDR(list_val(lst))) {
	Eterm body;
	ttpl = CAR(list_val(lst));
	if (!is_tuple(ttpl)) {
	    if (buff != sbuff) { 
		erts_free(ERTS_ALC_T_DB_TMP, buff);
	    }
	    return DB_ERROR_BADPARAM;
	}
	ptpl = tuple_val(ttpl);
	if (ptpl[0] != make_arityval(3U)) {
	    if (buff != sbuff) { 
		erts_free(ERTS_ALC_T_DB_TMP, buff);
	    }
	    return DB_ERROR_BADPARAM;
	}
	matches[i] = tpl = ptpl[1];
	guards[i] = ptpl[2];
	bodies[i] = body = ptpl[3];
	if (!is_list(body) || CDR(list_val(body)) != NIL ||
	    CAR(list_val(body)) != am_DollarUnderscore) {
	    mpi->all_objects = 0;
	}
	++i;
	if (!(mpi->key_given)) {
	    continue;
	}
	if (tpl == am_Underscore || db_is_variable(tpl) != -1) {
	    (mpi->key_given) = 0;
	    (mpi->something_can_match) = 1;
	} else {
	    key = db_getkey(tb->common.keypos, tpl);
	    if (is_value(key)) {
		if (!db_has_variable(key)) {   /* Bound key */
		    int ix;
		    HashDbTerm **tmp;
		    hval = MAKE_HASH(key);
		    HASH(tb, hval, ix);
		    tmp = &BUCKET(tb,ix);
		    if (search_list(tb, key, hval, 
				    BUCKET(tb, ix)) != 0) {
			int j;
			for (j = 0; j < (mpi->num_lists) && 
				 (mpi->lists)[j] != tmp; ++j)
			    ;
			if (j == (mpi->num_lists)) {
			    (mpi->lists)[(mpi->num_lists)++] = tmp;
			}
			mpi->something_can_match = 1;
		    }
		} else {
		    mpi->key_given = 0;
		    mpi->something_can_match = 1;
		}
	    }
	}
    }

    /*
     * It would be nice not to compile the match_spec if nothing could match,
     * but then the select calls would not fail like they should on bad 
     * match specs that happen to specify non existent keys etc.
     */
    if ((mpi->mp = db_match_compile(matches, guards, bodies,
				    num_heads, DCOMP_TABLE, NULL)) 
	== NULL) {
	if (buff != sbuff) { 
	    erts_free(ERTS_ALC_T_DB_TMP, buff);
	}
	return DB_ERROR_BADPARAM;
    }
    if (buff != sbuff) { 
	erts_free(ERTS_ALC_T_DB_TMP, buff);
    }
    return DB_ERROR_NONE;
}

static HashDbTerm** alloc_seg(DbTableHash *tb)
{
    HashDbTerm** bp;
    int sz = sizeof(HashDbTerm*)*SEGSZ;

    bp = (HashDbTerm**) erts_db_alloc_fnf(ERTS_ALC_T_DB_SEG,
					  (DbTable *) tb,
					  sz);
    if (!bp)
	return NULL;
    memset(bp, 0, sz);
    return bp;
}


static HashDbTerm* get_term(DbTableHash* tb, HashDbTerm* old, 
			    Eterm obj, HashValue hval) {
    HashDbTerm* p = db_get_term((DbTableCommon *) tb,
				(old != NULL) ? &(old->dbterm) : NULL, 
				((char *) &(old->dbterm)) - ((char *) old),
				obj);
    p->hvalue = hval;
    /*p->next = NULL;*/ /*No Need */
    return p;
}


/*
** Copy terms from ptr1 until ptr2
** works for ptr1 == ptr2 == 0  => []
** or ptr2 == 0
*/
static Eterm put_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2)
{
    int sz = 0;
    HashDbTerm* ptr;
    Eterm list = NIL;
    Eterm copy;
    Eterm *hp;

    ptr = ptr1;
    while(ptr != ptr2) {

	if (ptr->hvalue != INVALID_HASH)
	    sz += ptr->dbterm.size + 2;

	ptr = ptr->next;
    }

    hp = HAlloc(p, sz);

    ptr = ptr1;
    while(ptr != ptr2) {
	if (ptr->hvalue != INVALID_HASH) {
	    copy = copy_shallow(ptr->dbterm.v, ptr->dbterm.size, &hp, &MSO(p));
	    list = CONS(hp, copy, list);
	    hp  += 2;
	}
	ptr = ptr->next;
    }
    return list;
}

static void free_term(DbTableHash *tb, HashDbTerm* p)
{
    db_free_term_data(&(p->dbterm));
    erts_db_free(ERTS_ALC_T_DB_TERM,
		 (DbTable *) tb,
		 (void *) p,
		 SIZ_DBTERM(p)*sizeof(Eterm));
}


static void grow(DbTableHash* tb)
{
    HashDbTerm** bp;
    HashDbTerm** bps;
    HashDbTerm* b;
    int ix;
    int nszm = (tb->szm << 1) | 1;

    /* Ensure that that the slot nactive exists */
    if (tb->nactive >= tb->nslots) {
	/* Time to get a new array */    
	if ((tb->nactive & SZMASK) == 0) {
	    int nxt = tb->nactive >> SZEXP;
	    HashDbTerm** new_segment = alloc_seg(tb);
	    HashDbTerm*** new_seg;

	    if (new_segment == NULL)
		return;

	    if (nxt == tb->nsegs) {
		int i, sz;

		if (tb->nsegs == 1)
		    sz = SEG_LEN;
		else
		    sz = tb->nsegs + SEG_INCREAMENT;
		new_seg = (HashDbTerm***) 
		    erts_db_realloc(ERTS_ALC_T_DB_SEG_TAB,
				    (DbTable *) tb,
				    (void *) tb->seg,
				    sizeof(HashDbTerm**)*tb->nsegs,
				    sizeof(HashDbTerm**)*sz);
		tb->seg = new_seg;
		tb->nsegs = sz;
		for (i = nxt+1; i < sz; i++)
		    tb->seg[i] = 0;
	    }
	    tb->seg[nxt] = new_segment;
	    tb->nslots += SEGSZ;
	}
    }

    ix = tb->p;
    bp = &BUCKET(tb, ix);
    ix += (tb->szm+1);
    bps = &BUCKET(tb, ix);
    b = *bp;

    while (b != 0) {
	ix = b->hvalue & nszm;

	if (ix == tb->p)
	    bp = &b->next;
	else {
	    *bp = b->next;  	    /* unlink */
	    *bps = b;               /* link  *in order due to bags!* */
	    bps = &b->next;
	    b->next = NULL;
	}
	b = *bp;
    }

    tb->nactive++;
    if (tb->p == tb->szm) {
	tb->p = 0;
	tb->szm = nszm;
    }
    else
	tb->p++;
}


/*
** Shrink the hash table
** Remove segments if they are empty
** but do not reallocate the segment index table !!!
*/
static void shrink(DbTableHash* tb)
{
    HashDbTerm** bp;

    if (tb->nactive == SEGSZ)
	return;

    tb->nactive--;
    if (tb->p == 0) {
	tb->szm >>= 1;
	tb->p = tb->szm;
    }
    else
	tb->p--;

    bp = &BUCKET(tb, tb->p);
    while(*bp != 0) bp = &(*bp)->next;

    *bp = BUCKET(tb, tb->nactive);
    BUCKET(tb, tb->nactive) = 0;

    if ((tb->nactive & SZMASK) == SZMASK) {
	int six = (tb->nactive >> SZEXP)+1;

	erts_db_free(ERTS_ALC_T_DB_SEG,
		     (DbTable *) tb,
		     (void *) tb->seg[six],
		     sizeof(HashDbTerm*)*SEGSZ);
	tb->seg[six] = 0;
	tb->nslots -= SEGSZ;
    }
}


/* Search a list of tuples for a matching key */

static HashDbTerm* search_list(DbTableHash* tb, Eterm key, 
			       HashValue hval, HashDbTerm *list)
{
    while (list != 0) {
	if ((list->hvalue == hval) && EQ(key, GETKEY(tb, list->dbterm.tpl)))
	    return list;
	list = list->next;
    }
    return 0;
}


/* This function is called by the next AND the select BIF */
/* It return the next object in a table                   */

static HashDbTerm* next(DbTableHash *tb, Uint *iptr, HashDbTerm *list)
{
    int i;

    list = list->next;
    while (list != NULL && list->hvalue == INVALID_HASH)
	list = list->next;

    if (list != NULL)
	return list;
    i = *iptr + 1;
    while (i < tb->nactive) {
	if ((list = BUCKET(tb,i)) != NULL) {
	    while (list != NULL && list->hvalue == INVALID_HASH)
		list = list->next;
	    if (list != NULL) {
		*iptr = i;
		return list;
	    }
	}
	i++;
    }
    *iptr = i;
    return NULL;
}


static int realloc_counter(DbTableCommon *tb, HashDbTerm** bp, Uint sz, 
			   Eterm new_counter, int counterpos)
{
    HashDbTerm* b = *bp;
    return db_realloc_counter(tb, (void **) bp, &(b->dbterm),
			      ((char *) &(b->dbterm)) - ((char *) b),
			      sz, new_counter, counterpos);
}

int db_delete_all_objects_hash(Process* p, DbTable* tbl)
{
    if (tbl->hash.common.status & DB_FIXED) {
	db_mark_all_deleted_hash(tbl);
    } else {
	db_free_table_hash(tbl);
	db_create_hash(p, tbl);
	tbl->hash.common.nitems = 0;
    }
    return 0;
}

void db_foreach_offheap_hash(DbTable *tbl,
			     void (*func)(ErlOffHeap *, void *),
			     void * arg)
{
    DbTableHash *tb = &tbl->hash;
    HashDbTerm* list;
    int i;

    for (i = 0; i < tb->nactive; i++) {
	list = BUCKET(tb,i);
	while(list != 0) {
	    (*func)(&(list->dbterm.off_heap), arg);
	    list = list->next;
	}
    }
}

#ifdef HARDDEBUG

void db_check_table_hash(DbTable *tbl)
{
    DbTableHash *tb = &tbl->hash;
    HashDbTerm* list;
    int j;
    
    for (j = 0; j < tb->nactive; j++) {
	if ((list = BUCKET(tb,j)) != 0) {
	    while (list != 0) {
		if (!is_tuple(make_tuple(list->dbterm.tpl))) {
		    erl_exit(1, "Bad term in slot %d of ets table", j);
		}
		list = list->next;
	    }
	}
    }
}

#endif