erl_db_tree.c

OTP是开放电信平台的简称

	} else { /* Double LR rotation */
	    p2 = p1->right;
	    b2 = p2->balance;
	    p1->right = p2->left;
	    p2->left = p1;
	    p->left = p2->right;
	    p2->right = p;
	    p->balance = (b2 == -1) ? 1 : 0;
	    p1->balance = (b2 == 1) ? -1 : 0;
	    p2->balance = 0;
	    (*this) = p2;
	}
    }
    return h;
}

static int delsub(TreeDbTerm **this) 
{
    TreeDbTerm **tstack[STACK_NEED];
    int tpos = 0;
    TreeDbTerm *q = (*this);
    TreeDbTerm **r = &(q->left);
    int h;

    /*
     * Walk down the tree to the right and search 
     * for a void right child, pick that child out
     * and return it to be put in the deleted 
     * object's place.
     */
    
    while ((*r)->right != NULL) {
	tstack[tpos++] = r;
	r = &((*r)->right);
    }
    *this = *r;
    *r = (*r)->left;
    (*this)->left = q->left;
    (*this)->right = q->right;
    (*this)->balance = q->balance;
    tstack[0] = &((*this)->left);
    h = 1;
    while (tpos && h) {
	r = tstack[--tpos];
	h = balance_right(r);
    }
    return h;
}

/*
 * Helper for db_slot
 */

static TreeDbTerm *slot_search(Process *p, DbTableTree *tb, Sint slot)
{
    TreeDbTerm *this;
    TreeDbTerm *tmp;

    if (slot == 1) { /* Don't search from where we are if we are 
			looking for the first slot */
	tb->slot_pos = 0;
    }

    if (tb->slot_pos == 0) { /* clear stack if slot positions 
				are not recorded */
	tb->stack_pos = 0;
    }
    if (EMPTY_NODE(tb)) {
	this = tb->root;
	if (this == NULL)
	    return NULL;
	while (this->left != NULL){
	    PUSH_NODE(tb, this);
	    this = this->left;
	}
	PUSH_NODE(tb, this);
	tb->slot_pos = 1;
    }
    this = TOP_NODE(tb);
    while (tb->slot_pos != slot && this != NULL) {
	if (slot > tb->slot_pos) {
	    if (this->right != NULL) {
		this = this->right;
		while (this->left != NULL) {
		    PUSH_NODE(tb, this);
		    this = this->left;
		}
		PUSH_NODE(tb, this);
	    } else {
		for (;;) {
		    tmp = POP_NODE(tb);
		    this = TOP_NODE(tb);
		    if (this == NULL || this->left == tmp)
			break;
		}
	    }		
	    ++(tb->slot_pos);
	} else {
	    if (this->left != NULL) {
		this = this->left;
		while (this->right != NULL) {
		    PUSH_NODE(tb, this);
		    this = this->right;
		}
		PUSH_NODE(tb, this);
	    } else {
		for (;;) {
		    tmp = POP_NODE(tb);
		    this = TOP_NODE(tb);
		    if (this == NULL || this->right == tmp)
			break;
		}
	    }		
	    --(tb->slot_pos);
	}
    }
    return this;
}

/*
 * Find next and previous in sort order
 */

static TreeDbTerm *find_next(DbTableTree *tb, Eterm key)
{
    TreeDbTerm *this;
    TreeDbTerm *tmp;
    Sint c;

    if(( this = TOP_NODE(tb)) != NULL) {
	if (!CMP_EQ(GETKEY(tb, this->dbterm.tpl),key)) {
	    /* Start from the beginning */
	    tb->stack_pos = tb->slot_pos = 0;
	}
    }
    if (EMPTY_NODE(tb)) { /* Have to rebuild the stack */
	if (( this = tb->root ) == NULL)
	    return NULL;
	for (;;) {
	    PUSH_NODE(tb, this);
	    if (( c = cmp(GETKEY(tb, this->dbterm.tpl),key) ) < 0) {
		if (this->right == NULL) /* We are at the previos 
					    and the element does
					    not exist */
		    break;
		else
		    this = this->right;
	    } else if (c > 0) {
		if (this->left == NULL) /* Done */
		    return this;
		else
		    this = this->left;
	    } else
		break;
	}
    }
    /* The next element from this... */
    if (this->right != NULL) {
	this = this->right;
	PUSH_NODE(tb,this);
	while (this->left != NULL) {
	    this = this->left;
	    PUSH_NODE(tb, this);
	}
	if (tb->slot_pos > 0) 
	    ++(tb->slot_pos);
    } else {
	do {
	    tmp = POP_NODE(tb);
	    if (( this = TOP_NODE(tb)) == NULL) {
		tb->slot_pos = 0;
		return NULL;
	    }
	} while (this->right == tmp);
	if (tb->slot_pos > 0) 
	    ++(tb->slot_pos);
    }
    return this;
}

static TreeDbTerm *find_prev(DbTableTree *tb, Eterm key)
{
    TreeDbTerm *this;
    TreeDbTerm *tmp;
    Sint c;

    if(( this = TOP_NODE(tb)) != NULL) {
	if (!CMP_EQ(GETKEY(tb, this->dbterm.tpl),key)) {
	    /* Start from the beginning */
	    tb->stack_pos = tb->slot_pos = 0;
	}
    }
    if (EMPTY_NODE(tb)) { /* Have to rebuild the stack */
	if (( this = tb->root ) == NULL)
	    return NULL;
	for (;;) {
	    PUSH_NODE(tb, this);
	    if (( c = cmp(GETKEY(tb, this->dbterm.tpl),key) ) > 0) {
		if (this->left == NULL) /* We are at the next 
					   and the element does
					   not exist */
		    break;
		else
		    this = this->left;
	    } else if (c < 0) {
		if (this->right == NULL) /* Done */
		    return this;
		else
		    this = this->right;
	    } else
		break;
	}
    }
    /* The previous element from this... */
    if (this->left != NULL) {
	this = this->left;
	PUSH_NODE(tb,this);
	while (this->right != NULL) {
	    this = this->right;
	    PUSH_NODE(tb, this);
	}
	if (tb->slot_pos > 0) 
	    --(tb->slot_pos);
    } else {
	do {
	    tmp = POP_NODE(tb);
	    if (( this = TOP_NODE(tb)) == NULL) {
		tb->slot_pos = 0;
		return NULL;
	    }
	} while (this->left == tmp);
	if (tb->slot_pos > 0) 
	    --(tb->slot_pos);
    }
    return this;
}

static TreeDbTerm *find_next_from_pb_key(DbTableTree *tb, Eterm key)
{
    TreeDbTerm *this;
    TreeDbTerm *tmp;
    Sint c;

    /* spool the stack, we have to "re-search" */
    tb->stack_pos = tb->slot_pos = 0;
    if (( this = tb->root ) == NULL)
	return NULL;
    for (;;) {
	PUSH_NODE(tb, this);
	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl)) ) >= 0) {
	    if (this->right == NULL) {
		do {
		    tmp = POP_NODE(tb);
		    if (( this = TOP_NODE(tb)) == NULL) {
			return NULL;
		    }
		} while (this->right == tmp);
		return this;
	    } else
		this = this->right;
	} else /*if (c < 0)*/ {
	    if (this->left == NULL) /* Done */
		return this;
	    else
		this = this->left;
	} 
    }
}

static TreeDbTerm *find_prev_from_pb_key(DbTableTree *tb, Eterm key)
{
    TreeDbTerm *this;
    TreeDbTerm *tmp;
    Sint c;

    /* spool the stack, we have to "re-search" */
    tb->stack_pos = tb->slot_pos = 0;
    if (( this = tb->root ) == NULL)
	return NULL;
    for (;;) {
	PUSH_NODE(tb, this);
	if (( c = cmp_partly_bound(key,GETKEY(tb, this->dbterm.tpl)) ) <= 0) {
	    if (this->left == NULL) {
		do {
		    tmp = POP_NODE(tb);
		    if (( this = TOP_NODE(tb)) == NULL) {
			return NULL;
		    }
		} while (this->left == tmp);
		return this;
	    } else
		this = this->left;
	} else /*if (c < 0)*/ {
	    if (this->right == NULL) /* Done */
		return this;
	    else
		this = this->right;
	} 
    }
}


/*
 * Just lookup a node
 */
static TreeDbTerm *find_node(DbTableTree *tb, Eterm key)
{
    TreeDbTerm *this;
    Sint res;

    if(!EMPTY_NODE(tb) && 
       CMP_EQ(GETKEY(tb, ( this = TOP_NODE(tb) )->dbterm.tpl), key))
	return this;
    this = tb->root;
    while (this != NULL && 
	   ( res = cmp(key, GETKEY(tb, this->dbterm.tpl)) ) != 0) {
	if (res < 0)
	    this = this->left;
	else
	    this = this->right;
    }
    return this;
}

/*
 * Lookup a node and return the address of the node pointer in the tree
 */
static TreeDbTerm **find_node2(DbTableTree *tb, Eterm key)
{
    TreeDbTerm **this;
    Sint res;

    this = &tb->root;
    while ((*this) != NULL && 
	   ( res = cmp(key, GETKEY(tb, (*this)->dbterm.tpl)) ) != 0) {
	if (res < 0)
	    this = &((*this)->left);
	else
	    this = &((*this)->right);
    }
    if (*this == NULL)
	return NULL;
    return this;
}

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

/*
 * Traverse the tree with a callback function, used by db_match_xxx
 */
static void traverse_backwards(DbTableTree *tb,
			       Eterm lastkey,
			       int (*doit)(DbTableTree *,
					   TreeDbTerm *,
					   void *,
					   int),
			       void *context) 
{
    TreeDbTerm *this, *next;

    if (lastkey == NIL) {
	tb->stack_pos = tb->slot_pos = 0;
	if (( this = tb->root ) == NULL) {
	    return;
	}
	while (this != NULL) {
	    PUSH_NODE(tb, this);
	    this = this->right;
	}
	this = TOP_NODE(tb);
	next = find_prev(tb, GETKEY(tb, this->dbterm.tpl));
	if (!((*doit)(tb, this, context, 0)))
	    return;
    } else {
	next = find_prev(tb, lastkey);
    }

    while ((this = next) != NULL) {
	next = find_prev(tb, GETKEY(tb, this->dbterm.tpl));
	if (!((*doit)(tb, this, context, 0)))
	    return;
    }
}

/*
 * Traverse the tree with a callback function, used by db_match_xxx
 */
static void traverse_forward(DbTableTree *tb,
			     Eterm lastkey,
			     int (*doit)(DbTableTree *,
					 TreeDbTerm *,
					 void *,
					 int),
			     void *context) 
{
    TreeDbTerm *this, *next;

    if (lastkey == NIL) {
	tb->stack_pos = tb->slot_pos = 0;
	if (( this = tb->root ) == NULL) {
	    return;
	}
	while (this != NULL) {
	    PUSH_NODE(tb, this);
	    this = this->left;
	}
	this = TOP_NODE(tb);
	next = find_next(tb, GETKEY(tb, this->dbterm.tpl));
	if (!((*doit)(tb, this, context, 1)))
	    return;
    } else {
	next = find_next(tb, lastkey);
    }

    while ((this = next) != NULL) {
	next = find_next(tb, GETKEY(tb, this->dbterm.tpl));
	if (!((*doit)(tb, this, context, 1)))
	    return;
    }
}

/*
 * Returns 0 if not given 1 if given and -1 on no possible match
 * if key is given; *ret is set to point to the object concerned.
 */
static int key_given(DbTableTree *tb, Eterm pattern, TreeDbTerm **ret, 
		     Eterm *partly_bound)
{
    TreeDbTerm *this;
    Eterm key;

    ASSERT(ret != NULL);
    if (pattern == am_Underscore || db_is_variable(pattern) != -1)
	return 0;
    key = db_getkey(tb->common.keypos, pattern);
    if (is_non_value(key))
	return -1;  /* can't possibly match anything */
    if (!db_has_variable(key)) {   /* Bound key */
	if (( this = find_node(tb, key) ) == NULL) {
	    return -1;
	}
	*ret = this; 
	return 1;
    } else if (partly_bound != NULL && key != am_Underscore && 
	       db_is_variable(key) < 0)
	*partly_bound = key;
	
    return 0;
}



static Sint do_cmp_partly_bound(Eterm a, Eterm b, int *done)
{
    Eterm* aa;
    Eterm* bb;
    Eterm a_hdr;
    Eterm b_hdr;
    int i;
    Sint j;

    /* A variable matches anything */
    if (is_atom(a) && (a == am_Underscore || (db_is_variable(a) >= 0))) {
	*done = 1;
	return 0;
    }
    if (a == b)
	return 0;
    
    switch (a & _TAG_PRIMARY_MASK) {
    case TAG_PRIMARY_LIST:
	if (!is_list(b)) {
	    return cmp(a,b);
	}
	aa = list_val(a);
	bb = list_val(b);
	while (1) {
	    if ((j = do_cmp_partly_bound(*aa++, *bb++, done)) != 0 || *done) 
		return j;
	    if (*aa==*bb)
		return 0;
	    if (is_not_list(*aa) || is_not_list(*bb))
		return do_cmp_partly_bound(*aa, *bb, done);
	    aa = list_val(*aa);
	    bb = list_val(*bb);
	}
    case TAG_PRIMARY_BOXED:
	if ((b & _TAG_PRIMARY_MASK) != TAG_PRIMARY_BOXED) {
	    return cmp(a,b);
	}
	a_hdr = ((*boxed_val(a)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
	b_hdr = ((*boxed_val(b)) & _TAG_HEADER_MASK) >> _TAG_PRIMARY_SIZE;
	if (a_hdr != b_hdr) {
	    return cmp(a, b);
	}
	if (a_hdr == (_TAG_HEADER_ARITYVAL >> _TAG_PRIMARY_SIZE)) {
	    aa = tuple_val(a);
	    bb = tuple_val(b);
	    /* compare the arities */
	    i = arityval(*aa);	/* get the arity*/
	    if (i < arityval(*bb)) return(-1);
	    if (i > arityval(*bb)) return(1);
	    while (i--) {
		if ((j = do_cmp_partly_bound(*++aa, *++bb, done)) != 0 
		    || *done) 
		    return j;
	    }
	    return 0;
	}
	/* Drop through */
      default:
	  return cmp(a, b);
    }
}

static Sint cmp_partly_bound(Eterm partly_bound_key, Eterm bound_key) 
{
    int done = 0;
    Sint ret = do_cmp_partly_bound(partly_bound_key, bound_key, &done);
#ifdef HARDDEBUG
    erts_fprintf(stderr,"\ncmp_partly_bound: %T", partly_bound_key);
    if (ret < 0)
	erts_fprintf(stderr," < ");
    else if (ret > 0)
	erts_fprintf(stderr," > ");
    else
	erts_fprintf(stderr," == ");
    erts_fprintf(stderr,"%T\n",bound_key);
#endif
    return ret;
}

/*
** For partly_bound debugging....
**
BIF_RETTYPE ets_testnisse_2(BIF_ALIST_2)
B