Subversion Repositories PlanixRsrch.SVN

Rev

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

Rev Author Line No. Line
2 7u83 1 
/*
2 
 * Copyright 2019, The PLANIX Project
3 
 *
4 
 * Redistribution and use in source and binary forms, with or without
5 
 * modification, are permitted provided that the following conditions are
6 
 * met:
7 
 *
8 
 * 1. Redistributions of source code must retain the above copyright notice,
9 
 * this list of conditions and the following disclaimer.
10 
 *
11 
 * 2. Redistributions in binary form must reproduce the above copyright
12 
 * notice, this list of conditions and the following disclaimer in the
13 
 * documentation and/or other materials provided with the distribution.
14 
 *
15 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16 
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 
 */
27 
 
28 
#include <string.h>
29 
 
30 
#include "mavl.h"
31 
 
40 7u83 32 
void
33 
mavl_rot(struct mavlnode *n, struct mavlnode **parent, int dir)
2 7u83 34 
{
35 
	struct mavlnode *tmp;
40 7u83 36 
	*parent = n->s[dir];
37 
	tmp = n->s[dir]->s[1-dir];
38 
	n->s[dir]->s[1-dir]=n;
39 
	n->s[dir]=tmp;
2 7u83 40 
}
41 
 
40 7u83 42 
void
43 
mavl_drot(struct mavlnode *n, struct mavlnode **parent, int dir)
2 7u83 44 
{
40 7u83 45 
	mavl_rot(n->s[dir],&n->s[dir],1-dir);
46 
	mavl_rot(n,parent,dir);
2 7u83 47 
}
48 
 
304 7u83 49 
struct mavlnode *
2 7u83 50 
mavlnode_create(struct mavl *t, const void *data)
51 
{
52 
	struct mavlnode *n = t->malloc(sizeof(struct mavlnode) + t->data_size);
53 
	if (!n)
54 
		return NULL;
55 
 
40 7u83 56 
	n->s[0] = n->s[1] = NULL;
2 7u83 57 
	n->bal = 0;
58 
 
59 
	(void)memcpy(mavlnode_dataptr(n), data, t->data_size);
60 
 
61 
	return n;
62 
}
63 
 
64 
static int
65 
mavl_insert0(struct mavl *t, struct mavlnode **parent, const void **data)
66 
{
67 
	struct mavlnode *n;
40 7u83 68 
	int rc, bal,b;
69 
	int dir,sdir;
2 7u83 70 
 
13 7u83 71 
	if (*parent==NULL){
72 
		*parent = mavlnode_create(t, *data);
73 
		*data = mavlnode_dataptr(*parent);
74 
		if (*parent==NULL)
75 
			return MAVL_E_NOMEM;
15 7u83 76 
		t->count++;
14 7u83 77 
		return 1;
13 7u83 78 
	}
79 
 
2 7u83 80 
	n = *parent;
81 
	rc = t->cmp(*data, mavlnode_dataptr(n));
82 
 
83 
	if (rc == 0) {
84 
		*data = mavlnode_dataptr(n);
85 
		return 2;
86 
	}
87 
 
40 7u83 88 
	dir = rc>0 ? 1:0;
2 7u83 89 
 
9 7u83 90 
	/* rc is > 0  here */
40 7u83 91 
	bal = mavl_insert0(t, &n->s[dir], data);
2 7u83 92 
 
93 
	if (bal > 1)
94 
		return bal;
95 
 
328 7u83 96 
	sdir = dir ? 1:-1;
40 7u83 97 
	n->bal += bal*sdir;
2 7u83 98 
 
99 
	if (n->bal == 0)
100 
		return 0;
101 
 
40 7u83 102 
	if (n->bal == 2*sdir) {
103 
		if (n->s[dir]->bal == sdir) {
2 7u83 104 
			n->bal = 0;
40 7u83 105 
			n->s[dir]->bal = 0;
106 
			mavl_rot(n, parent,dir);
2 7u83 107 
			return 0;
40 7u83 108 
		}
109 
 
110 
		b = n->s[dir]->s[1-dir]->bal;
111 
		if (b==-sdir){
112 
			n->bal = 0;
113 
			n->s[dir]->bal = sdir;
114 
		}else if (b==sdir){
115 
			n->bal = -sdir;
116 
			n->s[dir]->bal = 0;
117 
		}else{
118 
			n->bal = 0;
119 
			n->s[dir]->bal = 0;
120 
		}
2 7u83 121 
 
40 7u83 122 
		n->s[dir]->s[1-dir]->bal = 0;
123 
		mavl_drot(n, parent,dir);
124 
		return 0;
2 7u83 125 
	}
126 
	return bal;
127 
}
128 
 
9 7u83 129 
void *
2 7u83 130 
mavl_insert(struct mavl *t, const void *data, int *exists)
131 
{
9 7u83 132 
	const void *d;
133 
	int rc;
2 7u83 134 
 
135 
	d = data;
136 
	rc = mavl_insert0(t, &t->root, &d);
137 
 
138 
	if (rc >= 3)
139 
		return NULL;
140 
 
141 
	if (exists != NULL) {
142 
		if (rc == 2)
143 
			*exists = 1;
144 
		else
145 
			*exists = 0;
146 
	}
147 
	return (void *)d;
148 
}
149