Subversion Repositories PlanixRsrch.SVN

Rev

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

Rev Author Line No. Line
298 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 
#include <string.h>
329 7u83 28 
#include <stdio.h>
335 7u83 29 
#include <assert.h>
298 7u83 30 
 
31 
#include "mavl.h"
32 
 
300 7u83 33 
 
329 7u83 34 
/*
35 
 * dir == 0 adj_bal_r
36 
 * dir == 1 adj_bal_l
37 
 */
38 
 
39 
static int
40 
adj_bal(struct mavlnode *n, struct mavlnode **parent, int dir, int sdir)
300 7u83 41 
{
329 7u83 42 
	int b;
300 7u83 43 
	if (n->s[dir]->bal == 0) {
44 
		n->bal = sdir;
45 
		n->s[dir]->bal = -sdir;
329 7u83 46 
		mavl_rot(n, parent,dir);
300 7u83 47 
		return 0;
48 
	}
329 7u83 49 
	if (n->s[dir]->bal == sdir) {
300 7u83 50 
		n->bal = 0;
51 
		n->s[dir]->bal = 0;
329 7u83 52 
		mavl_rot(n, parent,dir);
300 7u83 53 
		return 1;
329 7u83 54 
	}
55 
 
56 
        if (n->s[dir]->bal == -sdir) {
57 
 
335 7u83 58 
		b = n->s[dir]->s[1-dir]->bal;
329 7u83 59 
 
60 
		if (b == 0){
61 
			n->s[dir]->bal = 0;
332 7u83 62 
			n->bal=0;
329 7u83 63 
		} else if (b == sdir) {
332 7u83 64 
			n->bal = -sdir;
329 7u83 65 
			n->s[dir]->bal = 0 ;
66 
		} else if (b == -sdir){
67 
			n->s[dir]->bal = sdir;
332 7u83 68 
			n->bal=0;
329 7u83 69 
		} else{
335 7u83 70 
			assert(0*sdir);
329 7u83 71 
		}
72 
 
333 7u83 73 
		n->s[dir]->s[1-dir]->bal = 0;
329 7u83 74 
 
335 7u83 75 
                mavl_drot(n, parent,dir);
76 
		return 1;
329 7u83 77 
        }
78 
 
335 7u83 79 
	assert(0*sdir);
80 
	return 0;
300 7u83 81 
}
82 
 
298 7u83 83 
static int
84 
mavl_del_lo(struct mavl * t, struct mavlnode **parent, void *data)
85 
{
86 
	struct mavlnode *n = *parent;
87 
	/* walk down left */
88 
	if (n->s[0]) {
329 7u83 89 
		int dir=0,sdir;
298 7u83 90 
		int bal = mavl_del_lo(t, &n->s[0], data);
329 7u83 91 
		sdir = dir ? 1:-1;
92 
		n->bal -= bal*sdir;
93 
		if (n->bal == -sdir)
298 7u83 94 
			return 0;
329 7u83 95 
		if (n->bal == -2*sdir){
335 7u83 96 
			return adj_bal(n,parent,1-dir,-sdir);
298 7u83 97 
		}
329 7u83 98 
		return bal;
298 7u83 99 
	}
100 
 
101 
	/* found the lowest element */
102 
	*parent = n->s[1];
103 
	(void) memcpy(data,mavlnode_dataptr(n),t->data_size);
104 
	t->free(n);
105 
	return 1;
106 
}
107 
 
108 
 
316 7u83 109 
int
110 
mavl_del0(struct mavl *t, struct mavlnode **parent, void *data)
298 7u83 111 
{
112 
	struct mavlnode *n = *parent;
113 
	int rc;
114 
	int bal;
325 7u83 115 
	int dir,sdir;
116 
 
298 7u83 117 
	rc = t->cmp(data, mavlnode_dataptr(n));
118 
 
119 
	if (rc == 0) {
120 
		if (!n->s[0] && !n->s[1]) {
121 
			*parent = NULL;
122 
			mavlnode_destroy(t, n);
123 
			return 1;
124 
		}
125 
 
126 
		if (n->s[0] && !n->s[1]) {
127 
			*parent = n->s[0];
128 
			mavlnode_destroy(t, n);
129 
			return 1;
130 
		}
131 
 
132 
		if (!n->s[0] && n->s[1]) {
425 7u83 133 
			*parent = n->s[1];
298 7u83 134 
			mavlnode_destroy(t, n);
135 
			return 1;
136 
		}
316 7u83 137 
 
325 7u83 138 
		/* node has two children */
316 7u83 139 
		if (t->del) {
140 
			t->del(mavlnode_dataptr(n));
141 
		}
142 
		t->count--;
143 
		bal = mavl_del_lo(t,&n->s[1], mavlnode_dataptr(n));
329 7u83 144 
		dir = 1;
316 7u83 145 
 
338 7u83 146 
	} else {
147 
		dir = rc < 0 ? 0 : 1;
298 7u83 148 
 
453 7u83 149 
 
150 
		if (!n->s[dir])
151 
			return MAVL_E_NOTFOUND;
152 
 
338 7u83 153 
		bal = mavl_del0(t, &n->s[dir], data);
453 7u83 154 
 
155 
		if (bal == MAVL_E_NOTFOUND)
156 
			return bal;
338 7u83 157 
	}
158 
 
329 7u83 159 
	sdir = dir ? 1:-1;
160 
	n->bal -= bal*sdir;
161 
	if (n->bal == -sdir)
325 7u83 162 
		return 0;
329 7u83 163 
	if (n->bal == -2*sdir){
335 7u83 164 
		return adj_bal(n,parent,1-dir,-sdir);
329 7u83 165 
	}
166 
	return bal;
298 7u83 167 
}
168 
 
169 
 
316 7u83 170 
void
171 
*mavl_del(struct mavl *t, const void *data)
298 7u83 172 
{
173 
	void *d;
174 
	int rc;
335 7u83 175 
 
298 7u83 176 
	if (!t->root)
177 
		return NULL;
178 
 
179 
	d = (void*)data;
316 7u83 180 
	rc = mavl_del0(t, &t->root, d);
298 7u83 181 
 
182 
	if (rc == 2)
183 
		return NULL;
184 
	return (void*)data;
185 
}
186