erl_db_hash.c

OTP是开放电信平台的简称

    hval = MAKE_HASH(key);
    HASH(tb, hval, ix);
    b1 = BUCKET(tb, ix);

    while(b1 != 0) {
	if ((b1->hvalue == hval) && EQ(key, GETKEY(tb, b1->dbterm.tpl))) {
	    *ret = am_true;
	    return DB_ERROR_NONE;
	}
	b1 = b1->next;
    }
    *ret = am_false;
    return DB_ERROR_NONE;
}
    
static int db_get_element_hash(Process *p, DbTable *tbl, 
			       Eterm key,
			       int ndex, 
			       Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    HashValue hval;
    int ix;
    HashDbTerm* b1;
    
    hval = MAKE_HASH(key);
    HASH(tb, hval, ix);
    b1 = BUCKET(tb, ix);

    while(b1 != 0) {
	if ((b1->hvalue == hval) && EQ(key, GETKEY(tb, b1->dbterm.tpl))) {
	    Eterm copy;

	    if (ndex > arityval(b1->dbterm.tpl[0]))
		return DB_ERROR_BADITEM;

	    if ((tb->common.status & DB_BAG) || 
		(tb->common.status & DB_DUPLICATE_BAG)) {
		HashDbTerm* b;
		HashDbTerm* b2 = b1->next;
		Eterm elem_list = NIL;

		while((b2 != 0) && (b2->hvalue == hval) &&
		      EQ(key, GETKEY(tb, b2->dbterm.tpl))) {
		    if (ndex > arityval(b2->dbterm.tpl[0]))
			return DB_ERROR_BADITEM;
		    b2 = b2->next;
		}

		b = b1;
		while(b != b2) {
		    Eterm *hp;
		    Uint sz = size_object(b->dbterm.tpl[ndex])+2;
		    
		    hp = HAlloc(p, sz);
		    copy = copy_struct(b->dbterm.tpl[ndex], sz-2, &hp, &MSO(p));
		    elem_list = CONS(hp, copy, elem_list);
		    hp += 2;
		    b = b->next;
		}
		*ret = elem_list;
		return DB_ERROR_NONE;
	    }
	    else {
		COPY_OBJECT(b1->dbterm.tpl[ndex], p, &copy);
		*ret = copy;
		return DB_ERROR_NONE;
	    }
	}
	b1 = b1->next;
    }
    return DB_ERROR_BADKEY;
}

/*
 * Very internal interface, removes elements of arity two from 
 * BAG. Used for the PID meta table
 */
int db_erase_bag_exact2(DbTable *tbl, Eterm key, Eterm value)
{
    DbTableHash *tb = &tbl->hash;
    HashValue hval;
    int ix;
    HashDbTerm** bp;
    HashDbTerm* b;
    int found = 0;

    hval = MAKE_HASH(key);
    HASH(tb, hval, ix);
    bp = &BUCKET(tb, ix);
    b = *bp;

    ASSERT(!(tb->common.status & DB_FIXED));
    ASSERT((tb->common.status & DB_BAG));

    while(b != 0) {
	if ((b->hvalue == hval) && EQ(key, GETKEY(tb, b->dbterm.tpl))) {
	    found = 1;
	    if ((arityval(b->dbterm.tpl[0]) == 2) && 
		EQ(value, b->dbterm.tpl[2])) {
		*bp = b->next;
		free_term(tb, b);
		tb->common.nitems--;
		b = *bp;
		break;
	    }
	} else if (found) {
		break;
	}
	bp = &b->next;
	b = b->next;
    }

    if (found && ((tb->common.nitems / tb->nactive) < CHAIN_LEN))
	shrink(tb);
    return DB_ERROR_NONE;
}
	
/*
** NB, this is for the db_erase/2 bif.
*/
int db_erase_hash(Process *p, DbTable *tbl, 
		  Eterm key,
		  Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    HashValue hval;
    int ix;
    HashDbTerm** bp;
    HashDbTerm* b;
    int found = 0;

    hval = MAKE_HASH(key);
    HASH(tb, hval, ix);
    bp = &BUCKET(tb, ix);
    b = *bp;

    while(b != 0) {
	if ((b->hvalue == hval) && EQ(key, GETKEY(tb, b->dbterm.tpl))) {
	    if (tb->common.status & DB_FIXED) {
		/* Pseudo remove */
		FixedDeletion *fixd = (FixedDeletion *) 
		    erts_db_alloc(ERTS_ALC_T_DB_FIX_DEL,
				  (DbTable *) tb,
				  sizeof(FixedDeletion));
		fixd->slot = ix;
		fixd->next = tb->fixdel;
		tb->fixdel = fixd;
		tb->common.nitems--;
		tb->common.kept_items++;
		b->hvalue = INVALID_HASH;
		bp = &b->next;
		b = b->next;
	    } else {
		*bp = b->next;
		free_term(tb, b);
		tb->common.nitems--;
		b = *bp;
	    }
	    found = 1;
	}
	else {
	    if (found)
		break;
	    bp = &b->next;
	    b = b->next;
	}
    }

    if (found && ((tb->common.nitems / tb->nactive) < CHAIN_LEN) &&
	((tb->common.status & DB_FIXED) == 0))
	shrink(tb);

    *ret = am_true;
    return DB_ERROR_NONE;
}    

/*
** This is for the ets:delete_object BIF
*/
static int db_erase_object_hash(Process *p, DbTable *tbl, 
				Eterm object, Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    HashValue hval;
    int ix;
    HashDbTerm** bp;
    HashDbTerm* b;
    int found = 0;
    Eterm key;

    key = GETKEY(tb, tuple_val(object));
    hval = MAKE_HASH(key);
    HASH(tb, hval, ix);
    bp = &BUCKET(tb, ix);
    b = *bp;

    while(b != 0) {
	if ((b->hvalue == hval) && eq(object, make_tuple(b->dbterm.tpl))) {
	    if (tb->common.status & DB_FIXED) {
		/* Pseudo remove */
		FixedDeletion *fixd = (FixedDeletion *) 
		    erts_db_alloc(ERTS_ALC_T_DB_FIX_DEL,
				  (DbTable *) tb,
				  sizeof(FixedDeletion));
		fixd->slot = ix;
		fixd->next = tb->fixdel;
		tb->fixdel = fixd;
		tb->common.nitems--;
		tb->common.kept_items++;
		b->hvalue = INVALID_HASH;
		bp = &b->next;
		b = b->next;
	    } else {
		*bp = b->next;
		free_term(tb, b);
		tb->common.nitems--;
		b = *bp;
	    }
	    found = 1;
	}
	else {
	    if (found)
		break;
	    bp = &b->next;
	    b = b->next;
	}
    }

    if (found && ((tb->common.nitems / tb->nactive) < CHAIN_LEN) &&
	((tb->common.status & DB_FIXED) == 0))
	shrink(tb);

    *ret = am_true;
    return DB_ERROR_NONE;
}    


static int db_slot_hash(Process *p, DbTable *tbl, Eterm slot_term, Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    Sint slot;

    if (is_not_small(slot_term) ||
	((slot = signed_val(slot_term)) < 0) ||
	(slot > tb->nactive))
	return DB_ERROR_BADPARAM;
    
    if (slot == tb->nactive) {
	*ret = am_EOT;
	return DB_ERROR_NONE;
    }

    *ret = put_term_list(p, BUCKET(tb, slot), 0);

    return DB_ERROR_NONE;
}


/*
 * This is just here so I can take care of the return value 
 * that is to be sent during a trap (the BIF_TRAP macros explicitly returns)
 */
static BIF_RETTYPE bif_trap1(Export *bif,
			      Process *p, 
			      Eterm p1) 
{
    BIF_TRAP1(bif, p, p1);
}
    
/*
 * Continue collecting select matches, this may happen either due to a trap
 * or when the user calls ets:select/1
 */
static int db_select_continue_hash(Process *p, 
				   DbTable *tbl, 
				   Eterm continuation, 
				   Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    Sint chain_pos; 
    Sint save_chain_pos;
    Sint chunk_size;
    int all_objects;
    Binary *mp;
    int num_left = 1000;
    HashDbTerm *current_list = 0;
    Eterm match_list;
    Uint32 dummy;
    unsigned sz;
    Eterm *hp;
    Eterm match_res;
    Sint got;
    Eterm *tptr;


#define RET_TO_BIF(Term, State) do { *ret = (Term); return State; } while(0);

    /* Decode continuation. We know it's a tuple but not the arity or anything else */

    tptr = tuple_val(continuation);

    if (arityval(*tptr) != 6)
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    
    if (!is_small(tptr[2]) || !is_small(tptr[3]) || !is_binary(tptr[4]) || 
	!(is_list(tptr[5]) || tptr[5] == NIL) || !is_small(tptr[6]))
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    if ((chain_pos = signed_val(tptr[2])) < 0 || chain_pos > tb->nactive)
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    if ((chunk_size = signed_val(tptr[3])) < 0)
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    if (!(thing_subtag(*binary_val(tptr[4])) == REFC_BINARY_SUBTAG))
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    mp = ((ProcBin *) binary_val(tptr[4]))->val;
    if (!(mp->flags & BIN_FLAG_MATCH_PROG))
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);
    all_objects = mp->flags & BIN_FLAG_ALL_OBJECTS;
    match_list = tptr[5];
    if ((got = signed_val(tptr[6])) < 0)
	RET_TO_BIF(NIL,DB_ERROR_BADPARAM);


    if (chunk_size && got >= chunk_size) {
	/* Already got it in the match_list */
	goto done;
    }

    for(;;) {
	if (chain_pos == tb->nactive) {
	    goto done;
	}

	if ((current_list = BUCKET(tb,chain_pos)) != NULL) {
	    break;
	}
	++chain_pos;
    }
	
    
    for(;;) {
	if (current_list->hvalue != INVALID_HASH && 
	    (match_res = 
	     db_prog_match(p,mp,
			   make_tuple(current_list->dbterm.tpl),
			   0,&dummy),
	     is_value(match_res))) {
	    if (all_objects) {
		hp = HAlloc(p, current_list->dbterm.size + 2);
		match_res = copy_shallow(current_list->dbterm.v,
					 current_list->dbterm.size,
					 &hp,
					 &MSO(p));
	    } else {
		sz = size_object(match_res);
	    
		hp = HAlloc(p, sz + 2);
		match_res = copy_struct(match_res, sz, &hp, &MSO(p));
	    }
            match_list = CONS(hp, match_res, match_list);
	    ++got;
	}
	--num_left;
	save_chain_pos = chain_pos;
	if ((current_list = 
	     next(tb, (Uint*)&chain_pos, current_list)) == 0) {
	    break;
	}
	if (chain_pos != save_chain_pos) { 
	    if (chunk_size && got >= chunk_size) {
		break;
	    }    
	    if (num_left <= 0) {
		goto trap;
	    }
	    
	}
    }
done:
    BUMP_REDS(p, 1000 - num_left);
    if (chunk_size) {
	Eterm continuation;
	Eterm rest = NIL;
	Sint rest_size = 0;

	if (got > chunk_size) { /* Cannot write destructively here, 
				   the list may have 
				   been in user space */
	    rest = NIL;
	    hp = HAlloc(p, (got - chunk_size) * 2); 
	    while (got-- > chunk_size) {
		rest = CONS(hp, CAR(list_val(match_list)), rest);
		hp += 2;
		match_list = CDR(list_val(match_list));
		++rest_size;
	    }
	}
	if (rest != NIL || chain_pos < tb->nactive) {
	    hp = HAlloc(p,3+7);
	    continuation = TUPLE6(hp, tptr[1], make_small(chain_pos), 
				  tptr[3], tptr[4], rest, 
				  make_small(rest_size));
	    hp += 7;
	    RET_TO_BIF(TUPLE2(hp, match_list, continuation),DB_ERROR_NONE);
	} else {
	    if (match_list != NIL) {
		hp = HAlloc(p, 3);
		RET_TO_BIF(TUPLE2(hp, match_list, am_EOT),DB_ERROR_NONE);
	    } else {
		RET_TO_BIF(am_EOT, DB_ERROR_NONE);
	    }
	}
    }
    RET_TO_BIF(match_list,DB_ERROR_NONE);

trap:
    BUMP_ALL_REDS(p);

    hp = HAlloc(p,7);
    continuation = TUPLE6(hp, tptr[1], make_small(chain_pos), tptr[3],
			  tptr[4], match_list, make_small(got));
    RET_TO_BIF(bif_trap1(&ets_select_continue_exp, p, 
			 continuation), 
	       DB_ERROR_NONE);

#undef RET_TO_BIF

}

static int db_select_hash(Process *p, DbTable *tbl, 
			  Eterm pattern, int reverse,
			  Eterm *ret)
{
    return db_select_chunk_hash(p, tbl, pattern, 0, reverse, ret);
}

static int db_select_chunk_hash(Process *p, DbTable *tbl, 
				Eterm pattern, Sint chunk_size, 
				int reverse, /* not used */
				Eterm *ret)
{
    DbTableHash *tb = &tbl->hash;
    struct mp_info mpi;
    Uint chain_pos;
    Uint save_chain_pos;
    HashDbTerm *current_list = 0;
    unsigned current_list_pos = 0;
    Eterm match_list;
    Uint32 dummy;
    Eterm match_res;
    unsigned sz;
    Eterm *hp;
    int num_left = 1000;
    Uint got = 0;
    Eterm continuation;
    int errcode;
    Eterm mpb;


#define RET_TO_BIF(Term,RetVal) do {		\
	if (mpi.mp != NULL) {			\
	    erts_match_set_free(mpi.mp);	\
	}					\
	if (mpi.lists != mpi.dlists) {		\
	    erts_free(ERTS_ALC_T_DB_SEL_LIST,	\
		      (void *) mpi.lists);	\
	}					\
	*ret = (Term);				\
	return RetVal;				\
    } while(0)


    if ((errcode = analyze_pattern(tb, pattern, &mpi)) != DB_ERROR_NONE) {
	RET_TO_BIF(NIL,errcode);
    }

    if (!mpi.something_can_match) {
	if (chunk_size) {
	    RET_TO_BIF(am_EOT, DB_ERROR_NONE); /* We're done */
	}  
	RET_TO_BIF(NIL, DB_ERROR_NONE);
	/* can't possibly match anything */
    }

    if (!mpi.key_given) {
    /* Run this code if pattern is variable or GETKEY(pattern)  */
    /* is a variable                                            */
	for(chain_pos = 0; chain_pos < tb->nactive; chain_pos++) {
	    if ((current_list = BUCKET(tb,chain_pos)) != 0)
		break;
	}
	if (current_list == 0) {
	    if (chunk_size) {
		RET_TO_BIF(am_EOT, DB_ERROR_NONE); /* We're done */
	    }  
	    RET_TO_BIF(NIL,DB_ERROR_NONE);
	} 
    } else {
	/* We have at least one */
	chain_pos = tb->nactive;
	current_list = *(mpi.lists[current_list_pos++]); 
    }

    match_list = NIL;

    for(;;) {
	if (current_list->hvalue != INVALID_HASH && 
	    (match_res = 
	     db_prog_match(p,mpi.mp,
			   make_tuple(current_list->dbterm.tpl),
			   0,&dummy),
	     is_value(match_res))) {
	    if (mpi.all_objects) {
		hp = HAlloc(p, current_list->dbterm.size + 2);
		match_res = copy_shallow(current_list->dbterm.v,
					 current_list->dbterm.size,
					 &hp,
					 &MSO(p));
	    } else {
		sz = size_object(match_res);
	    
		hp = HAlloc(p, sz + 2);
		match_res = copy_struct(match_res, sz, &hp, &MSO(p));
	    }
            match_list = CONS(hp, match_res, match_list);
	    ++got;
	}

	/* Update the list variable */
        if (mpi.key_given) {  /* Key is bound */
	    current_list = current_list->next;
	    for (;;) {
		while (current_list != NULL && 
		       current_list->hvalue == INVALID_HASH)
		    current_list = current_list->next;
		if (current_list == NULL) {
		    if (current_list_pos == mpi.num_lists) {
			goto done;
		    } else {
			current_list = *(mpi.lists[current_list_pos++]);
		    }
		} else {
		    break;
		}
	    }
        }
        else { /* Key is variable */
	    --num_left;
	    save_chain_pos = chain_pos;
            if ((current_list = 
		 next(tb, &chain_pos, current_list)) == 0) {
                break;
	    }
	    if (chain_pos != save_chain_pos) {
		if (chunk_size && got >= chunk_size) {
		    break;
		}    
		if (num_left <= 0) {
		    goto trap;
		}
	    }
        }
    }
done:
    BUMP_REDS(p, 1000 - num_left);
    if (chunk_size) {
	Eterm continuation;
	Eterm rest = NIL;
	Sint rest_size = 0;

	if (mpi.all_objects)
	    (mpi.mp)->flags |= BIN_FLAG_ALL_OBJECTS;
	if (got > chunk_size) { /* Split list in return value and 'rest' */
	    Eterm tmp = match_list;
	    rest = match_list;
	    while (got-- > chunk_size + 1) { 
		tmp = CDR(list_val(tmp));
		++rest_size;
	    }
	    ++rest_size;
	    match_list = CDR(list_val(tmp));
	    CDR(list_val(tmp)) = NIL; /* Destructive, the list has never 
					 been in 'user space' */ 
	}
	if (rest != NIL || chain_pos < tb->nactive) { /* Need more calls */
	    hp = HAlloc(p,3+7+PROC_BIN_SIZE);