Subversion Repositories PlanixRsrch.SVN

Compare Revisions

Ignore whitespace Rev 304 → Rev 305

/trunk/libmavl/mav.c
7,24 → 7,28
n->bal = n->s[ (n->s[0]->bal>n->s[1]->bal) ? 0 : 1 ]->bal+1;
}
 
/* dir = 1 rot left */
/* p p
* / /
* n ----> b
* / \ / \
* b n 2
* / \ . / \
* 1 2 1
*/
 
/*
* dir = 1 rot left
* dir = 0 rot right
*/
static struct mavlnode *
rot(struct mavlnode *n, struct mavlnode **parent, int dir)
{
*parent = n->s[dir];
n->s[dir]=(*parent)->s[1-dir];
n->s[dir]=n;
(*parent)->s[1-dir]==n;
recalc(n);
recalc(*parent);
return *parentl;
 
/* struct mavlnode *tmp;
*parent = n->s[dir];
tmp = n->s[dir]->s[1-dir];
n->s[dir]->s[1-dir]=n;
n->s[dir]=tmp;
return NULL;
*/
return *parent;
}
 
 
40,6 → 44,38
return rot(n,parent,1-d);
}
 
static struct mavlnode *
mav_insert0(struct mavl *t, struct mavlnode **parent, const void **data)
{
int rc;
struct mavlnode *n ;
if (*parent==NULL){
*parent = mavlnode_create(t, *data);
*data = mavlnode_dataptr(*parent);
if (*parent==NULL)
return NULL;
/*return MAVL_E_NOMEM;*/
t->count++;
(*parent)->bal=1;
return *parent;
}
 
rc = t->cmp(*data, mavlnode_dataptr(n));
if (rc == 0) {
/* element exists */
*data = mavlnode_dataptr(n);
return NULL;
}
 
n = *parent;
 
/* rc is > 0 here */
mav_insert0(t, &(n->s[ rc>0 ? 1:0 ]), data);
 
 
 
}
 
void *
mav_insert(struct mavl *t, const void *data, int *exists)
{