1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
int XDirectoryNode::insert(DataObject obj, X_Node **new_node) {
SET_OF_MBR *s1 *s2;
X_Node *follow, *new_son;
int return_value;
// choose a son node to insert obj into
follow = choose_subtree(obj);
// insert obj into subtree
return_value = follow->insert(obj,new_son);
// update MBR of o son node
update_mbr(follow->calc_mbr());
if (return_value == SPLIT) {
// insert mbr of new son node into current node
add_mbr(new_son->calc_mbr());
if (num_of_mbrs()>CAPACITY){ // overflow occurs
if (split(mbrs,s1,s2)==TRUE) {
// topological or overlap-minimal split was successfull
set_mbrs(s1);
*new_node=new X_DirectoryNode(s2);
return SPLIT;
} else { // there is no good split
*newnode = new X_SuperNode();
(*newnode)->set_mbrs(mbrs);
return SUPERNODE;
}
}
// node 'follow' becomes a supernode
} else if (return_value == SUPERNODE) {
remove_son(follow);
insert_son (new_son);
}
return NO_SPLIT;
} |
