1 /*******************************************************************************************
2
3 Copyright (C) 2004,2005,2006,2007,2008 (Nuno A. Fonseca) <nuno.fonseca@gmail.com>
4
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either
8 version 2 of the License, or (at your option) any later
9 version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
20
21 Last rev: $Id: range_list.c,v 1.1 2008-03-26 23:05:22 nunofonseca Exp $
22 **************************************************************************/
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include "range_list.h"
28
29 /*****************************************************************************/
30
31
32
33 void set_num_bit(unsigned int number,char* storage,STATUS status);
34 BOOLEAN is_num_bit(unsigned int number,char *storage,STATUS status);
35
36 static void set_quadrant(RL_Node* node,short quadrant,QUADRANT_STATUS status);
37 static QUADRANT_STATUS quadrant_status(RL_Node* node,short quadrant);
38
39 static void quadrant_interval(RL_Tree *tree,short quadrant,NUM interval,NUM *quad_interval);
40 static NUM get_quadrant_node(RL_Tree* tree,NUM node,short quadrant,NUM interval);
41 static unsigned int tree_size(RL_Tree *tree,NUM node,NUM);
42
43 int get_location(RL_Tree* tree,NUM node,short quadrant,NUM interval);
44
45 long set_in(NUM number,NUM node, NUM node_num, NUM interval,NUM max,RL_Tree* tree,STATUS status);
46 long compact_node(RL_Tree*,NUM node,NUM next_node,NUM node_interval,NUM next_node_interval,NUM next_node_num,short quadrant,NUM max);
47
48 BOOLEAN in_tree(NUM number,RL_Tree *tree,NUM node,NUM node_num,NUM interval);
49 void display_tree(RL_Tree *tree);
50 void idisplay_tree(RL_Tree *tree,NUM node,NUM node_num,NUM interval,NUM max);
51 static void display_leaf(RL_Tree* tree,NUM node,NUM node_num,NUM max);
52
53 NUM new_node(RL_Tree* tree,NUM node_father,short quadrant,NUM node_num,NUM quad_min,NUM quad_max,STATUS);
54 static void root_intervals(RL_Tree* tree);
55
56 NUM next_min(RL_Tree *tree,NUM node,NUM node_num,NUM interval,NUM max,NUM min);
57 NUM tree_minus(RL_Tree *r1,RL_Tree *r2,NUM node1,NUM node2,NUM node_num,NUM interval,NUM max);
58
59 RL_Tree* minus_rl(RL_Tree* range1,RL_Tree* range2);
60 void shift_right(RL_Tree *tree,const NUM idx,const long nnodes);
61 void shift_left(RL_Tree *tree,const NUM idx, const long nnodes);
62 void intersect_leafs(char *storage1,char *storage2);
63
64 static void print_nodes(RL_Tree* tree);
65
66 //
67 RL_Buffer* buffer=NULL;
68 unsigned int active_bits[16]={
69 1,
70 3,
71 7,
72 15,
73 31,
74 63,
75 127,
76 255,
77 511,
78 1023,
79 2047,
80 4095,
81 8191,
82 16383,
83 32767,
84 65535
85 };
86
87
88 /*****************************************************************************/
89 /*
90 *
91 *
92 */
new_rl(NUM max_size)93 RL_Tree* new_rl(NUM max_size) {
94
95 RL_Tree *new;
96 RL_Node *buf_ptr;
97 short q;
98 NUM qi,tmp;
99
100 if ( max_size <2 )
101 max_size=2;
102
103 new=(RL_Tree*)malloc(sizeof(RL_Tree));
104 if(new==NULL)
105 return NULL;
106
107 new->range_max=max_size;
108 root_intervals(new);
109
110 // alloc a block for the nodes
111 new->root=(RL_Node*)calloc(1,NODE_SIZE);
112 new->size=1;
113 new->mem_alloc=NODE_SIZE; // memory allocated
114
115 // reset buffer
116 buf_ptr=new->root;//tree_buffer();
117 ALL_OUT(&buf_ptr[0]); // Initialize all numbers as being out of the range/interval
118 buf_ptr[0].i_node.num_subnodes=1;
119 new->root=buf_ptr;// pointer to the buffer
120
121 buf_ptr->i_node.num_subnodes=1;
122 quadrant_interval(new,1,max_size,&qi);
123 tmp=qi+1;
124 for(q=2;q<=BRANCH_FACTOR;++q) {
125 if ( max_size < qi*(q-1)+1 ) // 16 32 48 64 - 32
126 set_quadrant(new->root,q,R_IGNORE);
127 tmp+=qi; // max_size=16 16+1
128 }
129
130 return new;
131 }
132 /*
133 *
134 *
135 */
copy_rl(RL_Tree * tree)136 RL_Tree* copy_rl(RL_Tree *tree) {
137
138 RL_Tree *new;
139 RL_Node *buf_ptr;
140
141 new=(RL_Tree*)malloc(sizeof(RL_Tree));
142 buf_ptr=(RL_Node*)calloc(tree->size,NODE_SIZE);
143 if( new==NULL ) {
144 printf("new==NULL");
145 return NULL;
146 }
147 if( buf_ptr==NULL ) {
148 printf("buf_ptr==NULL---%lu",tree->size);
149 return NULL;
150 }
151 memcpy(new,tree,sizeof(RL_Tree));
152 memcpy(buf_ptr,&tree->root[0],tree->size*NODE_SIZE);
153 new->root=buf_ptr;
154 new->mem_alloc=tree->size*NODE_SIZE;
155 return new;
156 }
157 /*
158 *
159 *
160 */
free_rl(RL_Tree * range)161 void free_rl(RL_Tree* range) {
162
163 // free nodes block
164 if(range->mem_alloc!=0)
165 free(range->root);
166 //
167 free(range);
168 }
169 /*
170
171 */
set_in_rl(RL_Tree * tree,NUM number,STATUS status)172 RL_Tree* set_in_rl(RL_Tree* tree,NUM number,STATUS status) {
173
174 /* */
175 if ( number >0 && number <=tree->range_max)
176 set_in(number,ROOT(tree),1,ROOT_INTERVAL(tree),tree->range_max,tree,status);
177 #ifdef DEBUG
178 printf("Setting: %d size=%d\n",number,tree->size);
179 #endif
180 /*if (status==IN && !in_rl(tree,number)) {
181 fprintf(stderr,"Error adding %lu to tree: size=%lu max=%lu\n",number,tree->size,tree->range_max);
182 display_tree(tree);
183 exit(1);
184 }*/
185 return tree;
186 }
187 /*
188 * Mark all examples in range IN/OUT
189 */
rl_all(RL_Tree * tree,STATUS status)190 void rl_all(RL_Tree* tree,STATUS status) {
191 int i;
192
193 for(i=1;i<=BRANCH_FACTOR;++i)
194 if (quadrant_status(NODE(tree,ROOT(tree)),i)!=R_IGNORE) {
195 if(status==IN)
196 set_quadrant(NODE(tree,ROOT(tree)),i,R_TOTALLY_IN_INTERVAL);
197 else
198 set_quadrant(NODE(tree,ROOT(tree)),i,R_NOT_IN_INTERVAL);
199 }
200 tree->size=1;
201 }
202 /*
203 *
204 *
205 */
in_rl(RL_Tree * tree,NUM number)206 BOOLEAN in_rl(RL_Tree* tree,NUM number) {
207 if ( number <1 && number >tree->range_max)
208 return FALSE;
209 return in_tree(number,tree,ROOT(tree),1,ROOT_INTERVAL(tree));
210 }
211 /*
212 *
213 *
214 */
freeze_rl(RL_Tree * range)215 BOOLEAN freeze_rl(RL_Tree* range) {
216
217 // reduce memory usage if possible
218 NUM s=range->size*NODE_SIZE;
219 if ( s < range->mem_alloc) {
220 range->root=(RL_Node*)realloc(range->root,s);
221 range->mem_alloc=s;
222 }
223 return TRUE;
224 }
225 /*
226 * Returns range1 without the numbers in range2
227 * Constraint:range1->max==range2->max
228 */
minus_rl(RL_Tree * range1,RL_Tree * range2)229 RL_Tree* minus_rl(RL_Tree* range1,RL_Tree* range2) {
230 if (range1->range_max!=range1->range_max)
231 return NULL;
232 //!!!!tree_minus(range1,range2,ROOT(range1),ROOT(range2),1,ROOT_INTERVAL(range1),range1->range_max);
233 return range1;
234 }
235
236 /*
237 * Returns next number in tree bigger than min
238 */
rl_next_in_bigger(RL_Tree * tree,NUM min)239 NUM rl_next_in_bigger(RL_Tree *tree,NUM min) {
240 if ( tree==NULL ) {
241 fprintf(stdout,"!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!%lu\n",min);
242 }
243 return next_min(tree,ROOT(tree),1,ROOT_INTERVAL(tree),tree->range_max,min+1);
244 }
245 /* ******************************************************************************
246 Private Functions
247 ****************************************************************************** */
print_nodes(RL_Tree * tree)248 static void print_nodes(RL_Tree* tree) {
249 RL_Node* nodes=tree->root;
250 int j;
251
252 for(j=0;j<tree->size;++j)
253 printf("[%d]=%lu\n",j,(unsigned long int)nodes[j].leaf);
254
255 }
256 // treeXquadrantXinterval->quadrant_minXquadrant_max
quadrant_interval(RL_Tree * tree,short quadrant,NUM interval,NUM * quad_interval)257 static void quadrant_interval(RL_Tree *tree,short quadrant,NUM interval,NUM *quad_interval) {
258
259 if ( IS_ROOT(tree,interval) ) {
260 *quad_interval=tree->root_i;
261 } else {
262 *quad_interval=NEXT_INTERVAL(interval);
263 }
264 }
265
266 // numberXtreeXinterval->quadrantXquadrant_minXquadrant_max
number_quadrant(NUM number,RL_Tree * tree,NUM node_interval,NUM node_num,short * quadrant,NUM * quad_min,NUM * quad_max)267 static void number_quadrant(NUM number,RL_Tree *tree,NUM node_interval,NUM node_num,short *quadrant,NUM *quad_min,NUM *quad_max) {
268 NUM tmp=node_num-1,quad_interval;
269 int i;
270 quadrant_interval(tree,1,node_interval,&quad_interval);
271 i=(number-node_num)/quad_interval+1;
272 tmp=node_num-1+quad_interval*i;
273 *quad_max=tmp;
274 *quadrant=i;
275 *quad_min=tmp-quad_interval+1;
276 //printf("number=%lu node num=%lu quad_interval=%lu-------> quadrant=%d quad_max=%lu\n",number,node_num,quad_interval,i,tmp);
277 }
278
279 /*
280 * returns the index to the quadrant "quadrant" node
281 */
get_quadrant_node(RL_Tree * tree,NUM node,short quadrant,NUM interval)282 static NUM get_quadrant_node(RL_Tree* tree,NUM node,short quadrant,NUM interval) {
283 int d=get_location(tree,node,quadrant,interval);
284 return node+d;
285 }
286 /* src s
287 * src= 1 2 3 4 5 6 _ _
288 * offset= 2
289 * nbytes=6
290 * >>>src= 1 2 1 2 3 4 5 6
291 * src s
292 */
shift_right(RL_Tree * tree,const NUM idx,const long nnodes)293 void shift_right(RL_Tree *tree,const NUM idx,const long nnodes){
294 long n=idx+nnodes;
295 RL_Node *s=tree->root;
296
297 if (nnodes<=0) return;
298 //print_nodes(tree);
299 while(n>=idx) {
300 s[n+1].leaf=s[n].leaf;
301 --n;
302 }
303 //print_nodes(tree);
304 //printf(">>----------------\n");
305 }
306
shift_left(RL_Tree * tree,const NUM idx,const long nnodes)307 void shift_left(RL_Tree *tree,const NUM idx, const long nnodes){
308 long n=idx;
309 RL_Node *s=tree->root;
310
311 //printf("sfit left: idx=%u nnodes=%u max=%u\n",idx,nnodes,tree->size);
312 if ( nnodes<=0 ) // last element
313 return;
314
315 // print_nodes(tree);
316 while(n<idx+nnodes) {
317 s[n].leaf=s[n+1].leaf;
318 ++n;;
319 }
320 // print_nodes(tree);
321 //printf("<<----------------\n");
322 }
323
324 /*
325 *
326 *
327 */
new_node(RL_Tree * tree,NUM node_father,short quadrant,NUM father_interval,NUM quad_min,NUM quad_max,STATUS status)328 NUM new_node(RL_Tree* tree,NUM node_father,short quadrant,NUM father_interval,NUM quad_min,NUM quad_max,STATUS status) {
329 //RL_Node *new,*root_node=tree->root;
330 NUM new_interval=+NEXT_INTERVAL(father_interval);
331 NUM times;
332 NUM new;
333 RL_Node* ptr;
334 new=get_quadrant_node(tree,node_father,quadrant,father_interval);
335
336 if ( tree->mem_alloc!=0 ) {
337 // increase array size and shift elements right
338 if ( REALLOC_MEM(tree) ) {
339 //printf("new node:resizing memory: current %lu -> new %lu [%lu]\n",tree->mem_alloc,MEM_SIZE(tree),tree->size);
340 ptr=(RL_Node*)realloc(tree->root,MEM_SIZE(tree));
341 if ( ptr==NULL ) {
342 fprintf(stderr,"Fatal error:range_list: Unable to allocate memory");
343 exit(1);
344 }
345 tree->root=ptr;
346 tree->mem_alloc=MEM_SIZE(tree);
347 }
348 // SHIFT elements at the right and including the current node one position
349 times=tree->size-1-new;
350 shift_right(tree,new,times);
351 // SHIFT_NODES((void*)new,times*NODE_SIZE);
352 }
353 // update father reference
354 set_quadrant(NODE(tree,node_father),quadrant,R_PARCIALLY_IN_INTERVAL);
355 // initialize node
356 if ( status==IN) {
357 ALL_OUT(NODE(tree,new)); // clear all bits
358 if ( !IS_LEAF(new_interval) ) {
359 short q;
360 RL_Node* node_ptr=NODE(tree,new);
361 node_ptr->i_node.num_subnodes=1;
362 for(q=2;q<=BRANCH_FACTOR;++q)
363 if ( MIN(quad_max,tree->range_max) < quad_min+NEXT_INTERVAL(new_interval)*(q-1) ) //QUADRANT_MAX_VALUE(
364 set_quadrant(NODE(tree,new),q,R_IGNORE);
365 }
366 } else {
367 // status ==out
368 //SET_LEAF_IN(tree->range_max,NODE(tree,new),quad_min);
369 tree->root[new].leaf=ON_BITS(MIN(16,tree->range_max-quad_min+1));
370 if ( !IS_LEAF(new_interval) ) {
371 short q;
372 RL_Node* node_ptr=NODE(tree,new);
373 node_ptr->i_node.num_subnodes=1;
374 node_ptr->i_node.quadrant_1=node_ptr->i_node.quadrant_2=node_ptr->i_node.quadrant_3=node_ptr->i_node.quadrant_4=R_TOTALLY_IN_INTERVAL;
375 for(q=2;q<=BRANCH_FACTOR;++q)
376 if ( MIN(quad_max,tree->range_max) < quad_min+NEXT_INTERVAL(new_interval)*(q-1) ) //QUADRANT_MAX_VALUE(
377 set_quadrant(NODE(tree,new),q,R_IGNORE);
378 }
379 }
380 // update tree size
381 tree->size++;
382 return new;
383 }
384
385 /*
386 * returns the offset
387 *
388 */
get_location(RL_Tree * tree,NUM node,short quadrant,NUM node_interval)389 int get_location(RL_Tree* tree,NUM node,short quadrant,NUM node_interval) {
390 int i,c=1,tmp;
391 NUM next_node;
392 NUM next_interval;
393
394 if (quadrant==1 || IS_LEAF(node_interval)) return 1;
395
396 //
397 if ( LAST_LEVEL_INODE(node_interval) ) {
398 // 1 node = current
399 for(i=1;i<quadrant;++i) {
400 if ( quadrant_status(NODE(tree,node),i)==R_PARCIALLY_IN_INTERVAL )
401 ++c;
402 }
403 return c;
404 }
405
406 //
407 // internal range list nodes
408 quadrant_interval(tree,quadrant,node_interval,&next_interval);
409 i=1;
410 next_node=node+1;
411 while(i!=quadrant && i<=BRANCH_FACTOR) {
412 if ( quadrant_status(NODE(tree,node),i)==R_PARCIALLY_IN_INTERVAL ) {
413 tmp=tree_size(tree,next_node,next_interval);
414 next_node+=tmp;
415 c+=tmp;
416 }
417 ++i;
418 }
419
420 return c;
421 }
422 /*
423 * Returns the number of nodes created/deleted.
424 *
425 * number: number to insert from the interval
426 * node: index of current node
427 * node_num: number corresponding to the beginning o the interval represented by node
428 * interval: size of the interval represented in the current node
429 */
set_in(NUM number,NUM node,NUM node_num,NUM node_interval,NUM max,RL_Tree * tree,STATUS status)430 long set_in(NUM number,NUM node, NUM node_num, NUM node_interval,NUM max,RL_Tree* tree,STATUS status) {
431 NUM next_node;
432 long ret_val=tree->size,compacted;
433 NUM interval=node_interval;
434 NUM quad_min,quad_max;
435 short quadrant;
436 NUM size;
437 /* */
438 if ( IS_LEAF(interval) ) {
439 // current node is a leaf
440 set_num_bit(number-node_num,(char*)NODE(tree,node),status);
441 return 0;
442 }
443 //
444 number_quadrant(number,tree,node_interval,node_num,&quadrant,&quad_min,&quad_max);
445 interval=quad_max-quad_min+1;
446 // select next node
447 switch(status) {
448 case IN:
449 // move pointer to next node
450 if ( quadrant_status(NODE(tree,node),quadrant)==R_NOT_IN_INTERVAL ) {
451 // new node
452 //display_tree(tree);
453 next_node=new_node(tree,node,quadrant,node_interval,quad_min,quad_max,status);
454 }else if ( quadrant_status(NODE(tree,node),quadrant)==R_TOTALLY_IN_INTERVAL )
455 return 0;
456 else
457 next_node=get_quadrant_node(tree,node,quadrant,node_interval);
458 break;
459 case OUT:
460 if ( quadrant_status(NODE(tree,node),quadrant)==R_TOTALLY_IN_INTERVAL ) {
461 // new node
462 next_node=new_node(tree,node,quadrant,node_interval,quad_min,quad_max,status);
463 } else if ( quadrant_status(NODE(tree,node),quadrant)==R_NOT_IN_INTERVAL )
464 return 0;
465 else
466 next_node=get_quadrant_node(tree,node,quadrant,node_interval);
467 break;
468 default:
469 printf("set_in: invalid number status %d\n",status);
470 exit(1);
471 }
472 // insert in tree
473 set_in(number,next_node,quad_min,interval,quad_max,tree,status);
474 ret_val=tree->size-ret_val; // number of nodes added/removed
475 // compact tree: only if we didn't create new nodes
476 //compacted=compact_node(tree,node,next_node,node_interval,interval,quad_min,quadrant,MIN(quad_max,tree->range_max));
477 compacted=0;
478 if ( compacted==-1 ) {
479 //NUM times=tree->size-1-next_node; // -1 because array position 0
480 shift_left(tree,next_node,1);
481 // update tree size
482 tree->size+=compacted;
483 ret_val+=compacted;
484 //ret_val=0;//compacted;
485 }
486 // update subnodes number
487 if ( tree->root[node].i_node.num_subnodes ==255 )
488 size=tree_size(tree,node,interval);
489 else
490 size=ret_val+tree->root[node].i_node.num_subnodes; // new subnodes value
491
492 if ( size > 254 )
493 tree->root[node].i_node.num_subnodes=255;
494 else
495 tree->root[node].i_node.num_subnodes=size;
496
497 // if (size <0 ) exit(1);
498 return ret_val;
499 }
500 /*
501 * Check if can change quadrant color of node. If it changes, the node is deleted and all nodes at right in the array are shifted one position.
502 *
503 */
compact_node(RL_Tree * tree,NUM node,NUM next_node,NUM node_interval,NUM next_node_interval,NUM next_node_num,short quadrant,NUM max)504 long compact_node(RL_Tree *tree,NUM node,NUM next_node,NUM node_interval,NUM next_node_interval,NUM next_node_num,short quadrant,NUM max){
505 unsigned int j;
506
507 RL_Node* node_ptr=NODE(tree,next_node); // next node pointer
508
509 // Try to compact a leaf
510 if ( IS_LEAF(next_node_interval) ) {
511 #ifdef DEBUG
512 fprintf(stderr,"compact_node: interval node\n");
513 #endif
514 // ALL IN
515 if ( LEAF_ALL_IN(node_ptr->leaf) ) {
516 set_quadrant(NODE(tree,node),quadrant,R_TOTALLY_IN_INTERVAL);
517 return -1;
518 }
519 // ALL IN: part II
520 // The last node does not need to be all in
521 if ( max-next_node_num+1 <= LEAF_SIZE ) {
522 j=ON_BITS(max-next_node_num+1); //153,154,155,156,157,.,.,.,[158 -> valor do max=200 devia ser 158
523 if ( node_ptr->leaf==j ) {
524 set_quadrant(NODE(tree,node),quadrant,R_TOTALLY_IN_INTERVAL);
525 return -1;
526 }
527 }
528 // ALL OUT
529 if ( LEAF_ALL_OUT(node_ptr->leaf) ) {
530 set_quadrant(NODE(tree,node),quadrant,R_NOT_IN_INTERVAL);
531 #ifdef DEBUG
532 printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>compacted leaf1\n");
533 #endif
534 return -1;
535 }
536 } else {
537 #ifdef DEBUG
538 fprintf(stderr,"compact_node:range node\n");
539 #endif
540 // INODE - range list node
541 if ( node_ptr->i_node.num_subnodes>1 ) // unable to compact
542 return 0;
543 // ALL IN
544 for(j=1;j<=BRANCH_FACTOR;++j)
545 if ( quadrant_status(NODE(tree,next_node),j)!=R_IGNORE && quadrant_status(NODE(tree,next_node),j)!=R_TOTALLY_IN_INTERVAL )
546 break;
547
548 if (j>BRANCH_FACTOR) {
549 set_quadrant(NODE(tree,node),quadrant,R_TOTALLY_IN_INTERVAL);
550 return -1;
551 }
552 // ALL OUT
553 for(j=1;j<=BRANCH_FACTOR;++j)
554 if ( quadrant_status(NODE(tree,next_node),j)!=R_IGNORE && quadrant_status(NODE(tree,next_node),j)!=R_NOT_IN_INTERVAL )
555 break;
556
557 if (j>BRANCH_FACTOR) {
558 set_quadrant(NODE(tree,node),quadrant,R_NOT_IN_INTERVAL);
559 return -1;
560 }
561 }
562 return 0;
563 }
564
565 /*
566 * interval: interval associated to the node
567 */
tree_size(RL_Tree * tree,NUM node,NUM interval)568 static unsigned int tree_size(RL_Tree *tree,NUM node,NUM interval) {
569 unsigned int c=1,tmp;
570 int i=1;
571 short status;
572 NUM next_interval;
573 NUM next_node;
574 RL_Node* node_ptr=NODE(tree,node);
575
576 if ( IS_LEAF(interval)) return 1;
577
578 if ( node_ptr->i_node.num_subnodes==255) {
579 // compute the size of all subtrees
580 next_interval=NEXT_INTERVAL(interval);
581 for(i=1;i<=BRANCH_FACTOR;++i) {
582 status=quadrant_status(NODE(tree,node),i);
583 switch(status) {
584 case R_PARCIALLY_IN_INTERVAL:
585 next_node=node+c; //
586 tmp=tree_size(tree,next_node,next_interval);
587 c+=tmp;
588 // default:
589 }
590 }
591 }
592 else c=node_ptr->i_node.num_subnodes;
593 return c;
594 }
595 /*
596 * number >=1 && number <=16
597 */
set_num_bit(unsigned int number,char * storage,STATUS status)598 void set_num_bit(unsigned int number,char *storage,STATUS status) {
599 if ( number >= 8 ) {
600 storage++;
601 number=number-8; // =-8
602 }
603 if ( status==IN )
604 BITMAP_insert(*storage,number);
605 else
606 BITMAP_delete(*storage,number);
607 }
608 /*
609 */
is_num_bit(unsigned int number,char * storage,STATUS status)610 BOOLEAN is_num_bit(unsigned int number,char *storage,STATUS status) {
611 if ( number >= 8 ) {
612 storage++;
613 number=number-8; // =-8
614 }
615 if ( status==IN )
616 return BITMAP_member(*storage,number);
617 else
618 return !BITMAP_member(*storage,number);
619 }
620 /*
621 *
622 */
set_quadrant(RL_Node * node,short quadrant,QUADRANT_STATUS status)623 static void set_quadrant(RL_Node *node,short quadrant,QUADRANT_STATUS status){
624
625 switch(quadrant){
626 case 1:
627 node->i_node.quadrant_1=status;
628 break;
629 case 2:
630 node->i_node.quadrant_2=status;
631 break;
632 case 3:
633 node->i_node.quadrant_3=status;
634 break;
635 case 4:
636 node->i_node.quadrant_4=status;
637 break;
638 default:
639 fprintf(stderr,"ERROR: set_quadrant: invalid quadrant %d(%d)\n",quadrant,status);
640 }
641 }
642 /*
643 *
644 */
quadrant_status(RL_Node * node,short quadrant)645 static QUADRANT_STATUS quadrant_status(RL_Node *node,short quadrant){
646
647 switch(quadrant){
648 case 1:
649 return node->i_node.quadrant_1;
650 case 2:
651 return node->i_node.quadrant_2;
652 case 3:
653 return node->i_node.quadrant_3;
654 case 4:
655 return node->i_node.quadrant_4;
656 default:
657 fprintf(stderr,"ERROR: quadrant_status: invalid quadrant(%d)\n",quadrant);
658 }
659 return 0;
660 }
661 /*
662 *
663 *
664 */
in_leaf(NUM number,RL_Tree * tree,NUM node,NUM node_num,NUM max)665 static BOOLEAN in_leaf(NUM number,RL_Tree *tree,NUM node,NUM node_num,NUM max) {
666
667 if(is_num_bit(number-node_num,(char*)NODE(tree,node),IN))
668 return TRUE;
669 return FALSE;
670 }
671
672 /*
673 *
674 *
675 */
in_tree(NUM number,RL_Tree * tree,NUM node,NUM node_num,NUM node_interval)676 BOOLEAN in_tree(NUM number,RL_Tree *tree,NUM node,NUM node_num,NUM node_interval) {
677 NUM next_node;
678 short quadrant;
679 NUM interval=node_interval;
680 NUM max=MIN(node_num+interval,tree->range_max);
681 NUM quad_min,quad_max;
682
683 /* */
684 if ( IS_LEAF(interval))
685 // current node is a leaf
686 return in_leaf(number,tree,node,node_num,max);
687
688 number_quadrant(number,tree,node_interval,node_num,&quadrant,&quad_min,&quad_max);
689 interval=quad_max-quad_min+1;
690 node_num=quad_min;
691
692 if ( quadrant_status(NODE(tree,node),quadrant)==R_PARCIALLY_IN_INTERVAL ) {
693 next_node=get_quadrant_node(tree,node,quadrant,node_interval);
694 return in_tree(number,tree,next_node,node_num,interval);
695 }
696 if ( quadrant_status(NODE(tree,node),quadrant)==R_TOTALLY_IN_INTERVAL )
697 return TRUE;
698
699 return FALSE;
700 }
701
702
703 /* ************************************************************************************************* */
704 /* I/O */
705 /* ************************************************************************************************* */
706
707 /*
708 *
709 */
display_leaf(RL_Tree * tree,NUM node,NUM node_num,NUM max)710 static void display_leaf(RL_Tree *tree,NUM node,NUM node_num,NUM max) {
711 int i;
712 printf("|");
713 //for(i=0;i<LEAF_SIZE && node_num+i<=max;++i)
714 for(i=0;i<LEAF_SIZE ;++i)
715 if(is_num_bit(i,(char*)NODE(tree,node),IN))
716 printf(",%lu",node_num+i);
717 else
718 printf(",.");
719 printf("|");
720 }
721 /*
722 *
723 */
display_tree(RL_Tree * tree)724 void display_tree(RL_Tree *tree) {
725
726 // root node
727 NUM init,max;
728 NUM next_node;
729 int i;
730 short status;
731
732 NUM qi,tmp=0;
733 next_node=0;//tree->root;
734
735 printf("Size:%lu -[1,%lu]\n",tree->size,tree->range_max);
736 qi=ROOT_INTERVAL(tree)/BRANCH_FACTOR;
737 //quadrant_interval(tree,1,tree->range_max,&qi);
738 for(i=1;i<=BRANCH_FACTOR;++i) {
739 tmp+=qi;
740 //
741 init=tmp-qi+1;
742 max=tmp;
743 status=quadrant_status(NODE(tree,0),i);
744 switch(status) {
745 case R_PARCIALLY_IN_INTERVAL:
746 next_node=get_quadrant_node(tree,ROOT(tree),i,qi*BRANCH_FACTOR);
747 idisplay_tree(tree,next_node,init,qi,max);
748 break;
749 case R_TOTALLY_IN_INTERVAL:
750 printf(",[%lu-%lu]",init,MIN(max,tree->range_max));
751 break;
752 case R_IGNORE:
753 break;
754 default:
755 /* not in */
756 printf(",]%lu-%lu[",init,MIN(max,tree->range_max));
757 }
758 }
759 printf("\n");
760 }
761 /*
762 *
763 *
764 */
idisplay_tree(RL_Tree * tree,NUM node,NUM node_num,NUM interval,NUM max)765 void idisplay_tree(RL_Tree *tree,NUM node,NUM node_num,NUM interval,NUM max) {
766 NUM next_node;
767 short quadrant;
768 NUM interval2;
769 NUM node_num2;
770 NUM quadrant_max;
771 short status;
772
773 if ( IS_LEAF(interval) )
774 return display_leaf(tree,node,node_num,MIN(max,tree->range_max));
775
776 interval2=NEXT_INTERVAL(interval);
777 //
778 for(quadrant=1;quadrant<=BRANCH_FACTOR;++quadrant){
779 node_num2=node_num+(quadrant-1)*interval2;
780 quadrant_max=QUADRANT_MAX_VALUE(node_num,quadrant,interval2,max);
781 status=quadrant_status(NODE(tree,node),quadrant);
782 switch(status) {
783 case R_PARCIALLY_IN_INTERVAL:
784 next_node=get_quadrant_node(tree,node,quadrant,interval);
785 if ( IS_LEAF(interval2) )
786 display_leaf(tree,next_node,node_num2,MIN(quadrant_max,tree->range_max));
787 else
788 idisplay_tree(tree,next_node,node_num2,interval2,quadrant_max);
789 break;
790 case R_TOTALLY_IN_INTERVAL:
791 printf(",[%lu-%lu]",node_num2,MIN(node_num2+interval2-1,max));
792 break;
793 case R_IGNORE:
794 break;
795 default:
796 printf(",]%lu-%lu[",node_num2,MIN(tree->range_max,node_num2+interval2-1));
797 }
798 }
799 }
800
801
802 /* *************************************************************************************************** */
next_in_leaf(RL_Tree * tree,NUM node,NUM node_num,NUM max,NUM min)803 static NUM next_in_leaf(RL_Tree *tree,NUM node,NUM node_num,NUM max,NUM min) {
804 NUM number;
805 number=node_num;
806 if ( number<min) number=min;
807 //fprintf(stderr,"next_in_leaf:[%lu,%lu]:min=%lu-->number=%lu\n",node_num,max,min,number);
808 for (;number<=max;++number)
809 if(is_num_bit(number-node_num,(char*)NODE(tree,node),IN)) {
810 //fprintf(stdout,"next_in_leaf:[%lu,%lu]:min=%lu>>>>number=%lu\n",node_num,max,min,number);
811 return number;
812 }
813 //fprintf(stderr,"!next_in_leaf:[%lu,%lu]:min=%lu-->number=%lu\n",node_num,max,min,number);
814 return 0;
815 }
816
817 /*
818 * Find next element bigger than min
819 *
820 */
next_min(RL_Tree * tree,NUM node,NUM node_num,NUM interval,NUM max,NUM min)821 NUM next_min(RL_Tree *tree,NUM node,NUM node_num,NUM interval,NUM max,NUM min) {
822 NUM next_node;
823 short quadrant;
824 NUM interval2;
825 NUM node_num2;
826 NUM quadrant_max;
827 short status;
828
829 if ( min > tree->range_max ) return 0;
830 if ( IS_LEAF(interval) )
831 return next_in_leaf(tree,node,node_num,MIN(max,tree->range_max),min);
832
833 interval2=NEXT_INTERVAL(interval);
834 //
835 for(quadrant=1;quadrant<=BRANCH_FACTOR;++quadrant){
836 NUM found;
837 node_num2=node_num+(quadrant-1)*interval2;
838 quadrant_max=QUADRANT_MAX_VALUE(node_num,quadrant,interval2,max);
839 //------------------------------------------
840 status=quadrant_status(NODE(tree,node),quadrant);
841 switch(status) {
842 case R_PARCIALLY_IN_INTERVAL:
843 next_node=get_quadrant_node(tree,node,quadrant,interval);
844 found=next_min(tree,next_node,node_num2,interval2,quadrant_max,min);
845 if ( found>0) return found;
846 break;
847 case R_TOTALLY_IN_INTERVAL:
848 if (min<=quadrant_max && min>=node_num2)
849 return min;
850 if ( min < node_num2 ) return node_num2;
851 }
852
853 }
854 return 0;
855 }
856
857 /* *******************************************************************************************************/
858 /*
859 *
860 */
intersect_leafs(char * storage1,char * storage2)861 void intersect_leafs(char *storage1,char *storage2) {
862
863 BITMAP_difference(*storage1,*storage1,*storage2);
864 storage1++; storage2++;
865 BITMAP_difference(*storage1,*storage1,*storage2);
866 }
867 /*
868 * Removes the elements in tree1 that are in tree2
869 *
870 */
871 /*NUM tree_minus(RL_Tree *tree1,RL_Tree *tree2,NUM node1,NUM node2,NUM node_num,NUM interval,NUM max) {
872 NUM next_node1,next_node2;
873 short quadrant;
874 NUM interval2;
875 NUM node_num2;
876 NUM quadrant_max;
877 short status1,status2;
878
879
880 if ( IS_LEAF(interval) ) //
881 return intersect_leafs((char*)NODE(tree1,node1),(char*)NODE(tree2,node2));
882
883 interval2=NEXT_INTERVAL(interval);
884 //
885 for(quadrant=1;quadrant<=BRANCH_FACTOR;++quadrant){
886 node_num2=node_num+(quadrant-1)*interval2;
887 quadrant_max=QUADRANT_MAX_VALUE(node_num,quadrant,interval2,max);
888 //------------------------------------------
889 status1=quadrant_status(NODE(tree1,node1),quadrant);
890 status2=quadrant_status(NODE(tree2,node2),quadrant);
891 if (status2==R_IGNORE || status2==R_NOT_IN_INTERVAL) {
892 // do nothing
893 } else if ( status2==R_TOTALLY_IN_INTERVAL && (status1==R_IGNORE || status1==R_NOT_IN_INTERVAL )) {
894 // do nothing
895 } else if ( status2==R_TOTALLY_IN_INTERVAL && status1==R_TOTALLY_IN_INTERVAL ) {
896 // delete entire quadrant subtree in tree1
897 } else if ( status2==R_PARTIALLY_IN_INTERVAL && status1==R_PARTIALLY_IN_INTERVAL){
898 // call same function
899 next_node1=get_quadrant_node(tree1,node1,quadrant,interval);
900 next_node2=get_quadrant_node(tree1,node2,quadrant,interval);
901 tree_minus(tree1,tree2,next_node1,next_node2,node_num2,interval2,quadrant_max);
902 } else if ( status2==R_PARTIALLY_IN_INTERVAL && status1==R_TOTALLY_IN_INTERVAL) {
903 // foreach element of tree2, remove it in tree1
904
905 } else {
906 // this should never happen!!!!
907 }
908 switch(status) {
909 case R_PARCIALLY_IN_INTERVAL:
910 next_node=get_quadrant_node(tree,node,quadrant,interval);
911 found=next_min(tree,next_node,node_num2,interval2,quadrant_max,min);
912 if ( found>0) return found;
913 break;
914 case R_TOTALLY_IN_INTERVAL:
915 if (min<=quadrant_max && min>=node_num2)
916 return min;
917 if ( min < node_num2 ) return node_num2;
918 }
919
920 }
921 return 0;
922 }*/
923 /* *************************************************************************************************** */
924 // root level
norm_tree_size(NUM interval)925 static NUM norm_tree_size(NUM interval){
926 NUM tmp;
927 NUM j=BRANCH_FACTOR;;
928
929 if ( interval<= LEAF_SIZE*BRANCH_FACTOR) return LEAF_SIZE;
930 while(1) {
931 tmp=LEAF_SIZE*j;
932 if ( tmp * BRANCH_FACTOR >= interval )break;
933 j*=BRANCH_FACTOR;;
934 }
935 return tmp;
936 }
937 //
root_intervals(RL_Tree * tree)938 static void root_intervals(RL_Tree* tree) {
939 NUM first_i;
940
941 first_i=norm_tree_size(tree->range_max);
942 //k=tree->range_max/first_i+1; // number of large intervals
943
944 tree->root_i=first_i;
945
946 if ( tree->root_i*BRANCH_FACTOR < tree->range_max ) {
947 tree->root_i=tree->root_i*BRANCH_FACTOR;
948 //printf("%lu---->>%lu\n",tree->range_max,tree->root_i);
949 }
950 }
951
952
953