Subversion Repositories PlanixRsrch.SVN

Rev

Rev 309 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
317 7u83 1 
#include <stdio.h>
301 7u83 2 
 
3 
#include "mavl.h"
4 
 
309 7u83 5 
static int
317 7u83 6 
getbal(struct mavlnode *n)
309 7u83 7 
{
317 7u83 8 
	return n==NULL ? 0 : n->bal;
309 7u83 9 
}
301 7u83 10 
 
309 7u83 11 
static int
302 7u83 12 
recalc(struct mavlnode *n){
309 7u83 13 
	int b0,b1;
317 7u83 14 
	b0 = getbal( n->s[0] );
15 
	b1 = getbal( n->s[1] );
309 7u83 16 
	return (b1>b0 ? b1 : b0)+1;
17 
 
317 7u83 18 
/*	n->bal = n->s[ (getbal(n->s[0])->bal > n->s[1]->bal) ? 0 : 1 ]->bal+1;*/
302 7u83 19 
}
20 
 
305 7u83 21 
/*      p                p
22 
 *     /                /
23 
 *    n     ---->      b
24 
 *   / \	      / \
25 
 *      b            n   2
26 
 *     / \     .    / \
27 
 *     1  2            1
317 7u83 28 
 */
305 7u83 29 
 
317 7u83 30 
/*
31 
2
32 
 \
33 
  1
34 
   \
35 
 
36 
*/
37 
 
305 7u83 38 
/*
39 
 * dir = 1 rot left
40 
 * dir = 0 rot right
41 
 */
301 7u83 42 
static struct mavlnode *
317 7u83 43 
rot(struct mavlnode *n, int dir)
301 7u83 44 
{
317 7u83 45 
	struct mavlnode * r;
46 
	r = n->s[dir];
47 
	n->s[dir]=r->s[1-dir];
48 
	r->s[1-dir]=n;
49 
/*	n->bal = recalc(n);*/
50 
/*	r->bal = recalc(r);*/
51 
	n->bal=0;
52 
	r->bal=0;
53 
	return r;
301 7u83 54 
}
55 
 
56 
 
57 
static struct mavlnode *
317 7u83 58 
balance ( struct mavlnode *n) {
301 7u83 59 
	int b,d;
317 7u83 60 
/*	b = n->s[1]->bal - n->s[0]->bal;*/
61 
 
62 
/*	b = getbal(n->s[1]) - getbal( n->s[0] );*/
63 
 
64 
	b = n->bal;
65 
 
301 7u83 66 
	if (b>-2 && b<2)
67 
		return n;
317 7u83 68 
 
69 
	printf("should rotate! %d\n",b);
70 
	return rot(n,1);
71 
 
72 
/*	d = b<0 ? 1:0;
301 7u83 73 
	if (n->s[d]->bal - n->s[1-d]->bal == -d/2)
74 
		n->s[d]=rot(n->s[d],parent,d);
317 7u83 75 
	return rot(n,parent,1-d);*/
76 
 
301 7u83 77 
}
78 
 
305 7u83 79 
static struct mavlnode *
309 7u83 80 
mav_insert0(struct mavl *t, struct mavlnode *root, const void **data)
305 7u83 81 
{
317 7u83 82 
	struct mavlnode * nnn;
83 
 
309 7u83 84 
	int rc,dir;
85 
	if (root==NULL){
86 
		root = mavlnode_create(t, *data);
87 
		if (root==NULL)
305 7u83 88 
			return NULL;
309 7u83 89 
		*data = mavlnode_dataptr(root);
305 7u83 90 
			/*return MAVL_E_NOMEM;*/
91 
		t->count++;
317 7u83 92 
		root->bal=0;
309 7u83 93 
		return root;
305 7u83 94 
	}
95 
 
309 7u83 96 
	rc = t->cmp(*data, mavlnode_dataptr(root));
305 7u83 97 
	if (rc == 0) {
98 
		/* element exists */
309 7u83 99 
		*data = mavlnode_dataptr(root);
305 7u83 100 
		return NULL;
101 
	}
102 
 
103 
	/* rc is > 0  here */
309 7u83 104 
	dir = rc>0 ? 1:0;
317 7u83 105 
/*	root->bal +=dir;*/ /*recalc(root);	*/
309 7u83 106 
	root->s[dir] =  mav_insert0(t, root->s[dir], data);
107 
 
305 7u83 108 
 
317 7u83 109 
       	nnn = balance(root);
110 
	printf("Return %p === %p\n",root,nnn);
111 
	return balance(nnn);
112 
 
113 
/*	return root;		*/
309 7u83 114 
/*	recalc(n);*/
305 7u83 115 
}
116 
 
301 7u83 117 
void *
118 
mav_insert(struct mavl *t, const void *data, int *exists)
119 
{
120 
	const void *d;
121 
	int rc;
122 
 
123 
	d = data;
309 7u83 124 
	t->root = mav_insert0(t, t->root, &d);
301 7u83 125 
 
126 
/*	if (rc >= 3)
127 
		return NULL;
128 
 
129 
	if (exists != NULL) {
130 
		if (rc == 2)
131 
			*exists = 1;
132 
		else
133 
			*exists = 0;
134 
	} */
135 
	return (void *)d;
136 
}
137