Subversion Repositories PlanixRsrch.SVN

Rev

Rev 309 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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