1 /*
2 * Copyright (C) 2016 Jakub Kruszona-Zawadzki, Core Technology Sp. z o.o.
3 *
4 * This file is part of MooseFS.
5 *
6 * MooseFS is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2 (only).
9 *
10 * MooseFS is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with MooseFS; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA
18 * or visit http://www.gnu.org/licenses/gpl-2.0.html
19 */
20
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif
24
25 #include <stdlib.h>
26
27 #include "massert.h"
28 #include "itree.h"
29
30 typedef struct _itnode {
31 uint32_t from,to;
32 uint32_t id;
33 struct _itnode *left,*right;
34 } itnode;
35
itree_free(itnode * n)36 static inline void itree_free(itnode *n) {
37 if (n) {
38 itree_free(n->left);
39 itree_free(n->right);
40 free(n);
41 }
42 }
43
itree_remove(itnode ** p)44 static inline void itree_remove(itnode **p) {
45 itnode *n = *p;
46 itnode *nit,**nptr;
47 uint32_t l,r;
48 if (n->left==NULL) {
49 *p = n->right;
50 free(n);
51 } else if (n->right==NULL) {
52 *p = n->left;
53 free(n);
54 } else {
55 l = r = 0;
56 for (nit=n->left->right ; nit ; nit=nit->right) {
57 l++;
58 }
59 for (nit=n->right->left ; nit ; nit=nit->left) {
60 r++;
61 }
62 if (l==r) {
63 l+=((n->from)^(n->to))&1;
64 }
65 if (r>l) {
66 nptr = &(n->right);
67 while ((nit=*nptr) && nit->left) {
68 nptr = &(nit->left);
69 }
70 *nptr = nit->right;
71 } else {
72 nptr = &(n->left);
73 while ((nit=*nptr) && nit->right) {
74 nptr = &(nit->right);
75 }
76 *nptr = nit->left;
77 }
78 nit->left = n->left;
79 nit->right = n->right;
80 *p = nit;
81 }
82 }
83
84 static inline void itree_delete(itnode **p,uint32_t f,uint32_t t);
85 static inline void itree_add(itnode **p,uint32_t f,uint32_t t,uint32_t id);
86
itree_delete(itnode ** p,uint32_t f,uint32_t t)87 static inline void itree_delete(itnode **p,uint32_t f,uint32_t t) {
88 itnode *n = *p;
89 if (n) {
90 if (t<n->from) {
91 itree_delete(&(n->left),f,t);
92 } else if (f>n->to) {
93 itree_delete(&(n->right),f,t);
94 } else if (f<=n->from && t>=n->to) {
95 if (f<n->from) {
96 itree_delete(&(n->left),f,n->from-1);
97 }
98 if (t>n->to) {
99 itree_delete(&(n->right),n->to+1,t);
100 }
101 itree_remove(p);
102 } else if (f>=n->from && t<=n->to) {
103 if (f==n->from) {
104 n->from = t+1;
105 } else if (t==n->to) {
106 n->to = f-1;
107 } else {
108 if ((t^f)&1) {
109 itree_add(&(n->right),t+1,n->to,n->id);
110 n->to = f-1;
111 } else {
112 itree_add(&(n->left),n->from,f-1,n->id);
113 n->from = t+1;
114 }
115 }
116 } else if (f<n->from) {
117 n->from = t+1;
118 itree_delete(&(n->left),f,t);
119 } else if (t>n->to) {
120 n->to = f-1;
121 itree_delete(&(n->right),f,t);
122 }
123 }
124 }
125
itree_add(itnode ** p,uint32_t f,uint32_t t,uint32_t id)126 static inline void itree_add(itnode **p,uint32_t f,uint32_t t,uint32_t id) {
127 itnode *n = *p;
128 if (n) {
129 if (t<n->from) {
130 itree_add(&(n->left),f,t,id);
131 } else if (f>n->to) {
132 itree_add(&(n->right),f,t,id);
133 } else if (f<=n->from && t>=n->to) {
134 if (f<n->from) {
135 itree_delete(&(n->left),f,n->from-1);
136 }
137 if (t>n->to) {
138 itree_delete(&(n->right),n->to+1,t);
139 }
140 n->from = f;
141 n->to = t;
142 n->id = id;
143 } else if (f>=n->from && t<=n->to) {
144 if (f>n->from) {
145 itree_add(&(n->left),n->from,f-1,n->id);
146 }
147 if (t<n->to) {
148 itree_add(&(n->right),t+1,n->to,n->id);
149 }
150 n->from = f;
151 n->to = t;
152 n->id = id;
153 } else if (f<n->from) {
154 n->from = t+1;
155 itree_add(&(n->left),f,t,id);
156 } else if (t>n->to) {
157 n->to = f-1;
158 itree_add(&(n->right),f,t,id);
159 }
160 } else {
161 *p = n = malloc(sizeof(itnode));
162 passert(n);
163 n->from = f;
164 n->to = t;
165 n->id = id;
166 n->left = NULL;
167 n->right = NULL;
168 }
169 }
170
itree_tolist(itnode * n,itnode ** tail)171 itnode** itree_tolist(itnode *n,itnode **tail) {
172 if (n) {
173 tail = itree_tolist(n->left,tail);
174 n->left = NULL;
175 *tail = n;
176 tail = itree_tolist(n->right,&(n->left));
177 n->right = NULL;
178 }
179 return tail;
180 }
181
itree_simplify(itnode * n)182 void itree_simplify(itnode *n) {
183 itnode *f;
184 while (n && n->left) {
185 if (n->id == n->left->id && n->to+1 == n->left->from) {
186 n->to = n->left->to;
187 f = n->left;
188 n->left = n->left->left;
189 free(f);
190 } else {
191 n = n->left;
192 }
193 }
194 }
195
itree_totree(itnode * l,itnode ** p)196 void itree_totree(itnode *l,itnode **p) {
197 itnode **m,*i;
198 if (l) {
199 i = l;
200 m = &l;
201 while (i && i->left) {
202 m = &((*m)->left);
203 i = i->left->left;
204 }
205 *p = i = *m;
206 (*m) = NULL;
207 itree_totree(i->left,&(i->right));
208 itree_totree(l,&(i->left));
209 } else {
210 *p = NULL;
211 }
212 }
213
214 /* interface */
215
216 /* very simple square-time tree rebalance */
217 /* in the future whole tree should be reimplemented using, RB-tree, AVL or splay */
218
itree_rebalance(void * o)219 void* itree_rebalance(void *o) {
220 itnode *head;
221 itnode *root = (itnode*)o;
222
223 head = NULL;
224 itree_tolist(root,&head);
225 itree_simplify(head);
226 root = NULL;
227 itree_totree(head,&root);
228 return (void*)root;
229 }
230
itree_add_interval(void * o,uint32_t f,uint32_t t,uint32_t id)231 void* itree_add_interval(void *o,uint32_t f,uint32_t t,uint32_t id) {
232 itnode *root = (itnode*)o;
233 if (id==0) {
234 if (t<f) {
235 itree_delete(&root,t,f);
236 } else {
237 itree_delete(&root,f,t);
238 }
239 } else {
240 if (t<f) {
241 itree_add(&root,t,f,id);
242 } else {
243 itree_add(&root,f,t,id);
244 }
245 }
246 return root;
247 }
248
itree_find(void * o,uint32_t v)249 uint32_t itree_find(void *o,uint32_t v) {
250 itnode *n;
251
252 for (n = (itnode*)o ; n ; n = (v<n->from)?n->left:n->right) {
253 if (v>=n->from && v<=n->to) {
254 return n->id;
255 }
256 }
257 return 0;
258
259 }
260
itree_freeall(void * o)261 void itree_freeall(void *o) {
262 itree_free((itnode*)o);
263 }
264
265 /*
266 #include <stdio.h>
267
268 static inline void itree_rshow(itnode *n,uint32_t depth,uint32_t *bits) {
269 uint32_t i,j;
270 if (n) {
271 itree_rshow(n->left,depth+1,bits);
272 if (depth>0) {
273 (*bits)^=(1<<(depth-1));
274 j = (*bits);
275 for (i=0 ; i<depth-1 ; i++) {
276 if (j&1) {
277 printf(" ┃ ");
278 } else {
279 printf(" ");
280 }
281 j>>=1;
282 }
283 if ((*bits)&(1<<(depth-1))) {
284 printf(" ┏━━ ");
285 } else {
286 printf(" ┗━━ ");
287 }
288 }
289 printf("[<%"PRIu32",%"PRIu32">:%"PRIu32"]\n",n->from,n->to,n->id);
290 itree_rshow(n->right,depth+1,bits);
291 } else {
292 if (depth>0) {
293 (*bits)^=(1<<(depth-1));
294 }
295 }
296 }
297
298 void itree_show(void *o) {
299 uint32_t b=0;
300 itree_rshow((itnode*)o,0,&b);
301 }
302 */
303