* ========== Copyright Header Begin ==========================================
* OpenSPARC T2 Processor File: b_ary.c
* Copyright (C) 1995-2007 Sun Microsystems, Inc. All Rights Reserved
* 4150 Network Circle, Santa Clara, California 95054, U.S.A.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; version 2 of the License.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
* For the avoidance of doubt, and except that if any non-GPL license
* choice is available it will apply instead, Sun elects to use only
* the General Public License version 2 (GPLv2) at this time for any
* software where a choice of GPL license versions is made
* available with the language indicating that GPLv2 or any later version
* may be used, or where a choice of which version of the GPL is applied is
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.com if you need additional information or
* ========== Copyright Header End ============================================
/*--------------------------------------------
---------------------------------------------*/
b_tree_node_ptr
b_create()
head
= (b_tree_node_ptr
)malloc(sizeof(struct b_tree_node
));
for(i
= 0; i
< B_TREE_MAX
+2; i
++)head
->child
[i
] = 0;
for(i
= 0; i
< B_TREE_MAX
+1; i
++)head
->data
[i
] = 0;
/*--------------------------------------------
---------------------------------------------*/
void b_copy(b_tree_node_ptr p
, int pLo
, int pHi
,
b_tree_node_ptr q
, int qLo
, int qHi
)
if(((pHi
- pLo
) == (qHi
-qLo
)) && (qLo
<= qHi
)){
for(i
= qLo
; i
<= qHi
; i
++){
q
->data
[i
] = p
->data
[i
-qLo
+pLo
];
q
->child
[i
] = p
->child
[i
-qLo
+pLo
];
for(i
= qHi
; i
>= qLo
; i
--){
q
->data
[i
] = p
->data
[ i
-qHi
+pHi
];
q
->child
[i
] = p
->child
[i
-qHi
+pHi
];
/*--------------------------------------------
search for key k in node at node array
---------------------------------------------*/
int b_scanNode(b_tree_node_ptr node
, KeyType key
, int* low
)
middle
= (*low
+ high
+ 1) / 2;
if(key
< node
->data
[middle
]->key
)high
= middle
- 1;
return (*low
) && (node
->data
[*low
]->key
== key
);
/*--------------------------------------------
insert atom a and pointer rp into data
and child arrays of node at node.
---------------------------------------------*/
void b_addData(b_tree_atom_ptr atom
,
b_tree_atom_ptr
* promoted
)
b_tree_node_ptr temp_ptr
;
if((*node
)->size
< B_TREE_MAX
){//node is not yet full, just insert
if(index
< (*node
)->size
)b_copy(*node
, index
+1, (*node
)->size
, *node
, index
+2, (*node
)->size
+1);
(*node
)->data
[index
+1] = atom
;
(*node
)->child
[index
+1] = *rp
;
else{//no room for atom, must split node at node
*rp
= b_create();//(b_tree_node_ptr)malloc(sizeof(struct b_tree_node));
(*rp
)->size
= B_TREE_ORDER
;
(*node
)->size
= B_TREE_ORDER
;
(*rp
)->parent
= (*node
)->parent
;
if(index
<= B_TREE_ORDER
){
b_copy(*node
, B_TREE_ORDER
+1, B_TREE_MAX
, *rp
, 1, B_TREE_ORDER
);
if(index
== B_TREE_ORDER
){
(*rp
)->child
[0] = temp_ptr
;
else {//put half at arrays in the right side.
*promoted
= (*node
)->data
[B_TREE_ORDER
];
(*rp
)->child
[0] = (*node
)->child
[B_TREE_ORDER
];
b_copy(*node
, index
+1, B_TREE_ORDER
-1, *node
, index
+2, B_TREE_ORDER
);
(*node
)->data
[index
+1] = atom
;
(*node
)->child
[index
+1] = temp_ptr
;
(*rp
)->child
[0] = (*node
)->child
[B_TREE_ORDER
+1];
*promoted
= (*node
)->data
[B_TREE_ORDER
+1];
b_copy(*node
, B_TREE_ORDER
+2, index
, *rp
, 1, index
-B_TREE_ORDER
-1);
(*rp
)->data
[index
-B_TREE_ORDER
] = atom
;
(*rp
)->child
[index
-B_TREE_ORDER
] = temp_ptr
;
b_copy(*node
, index
+1, B_TREE_MAX
, *rp
, index
-B_TREE_ORDER
+1, B_TREE_ORDER
);
/*--------------------------------------------
---------------------------------------------*/
void b_recursiveInsert(b_tree_node_ptr
* node
,
b_tree_atom_ptr
* promoted
,
if(!b_scanNode(*node
, (*atom
)->key
, &index
)){
if((*node
)->child
[index
] == 0){//we're at a leaf.
b_addData(*atom
, index
, node
, rp
, promoted
);
b_recursiveInsert(&((*node
)->child
[index
]), promoted
, rp
, atom
);
if(*rp
){//update the parent node info.
for(index
= 0; index
<= B_TREE_ORDER
;index
++){
if((*node
)->child
[index
])(*node
)->child
[index
]->parent
= *node
;
if((*rp
)->child
[index
])(*rp
)->child
[index
]->parent
= *rp
;
b_scanNode(*node
, (*promoted
)->key
, &index
);
b_addData(*promoted
, index
, node
, rp
, promoted
);
if(*rp
){//update the parent node info.
for(index
= 0; index
<= B_TREE_ORDER
;index
++){
if((*node
)->child
[index
])(*node
)->child
[index
]->parent
= *node
;
if((*rp
)->child
[index
])(*rp
)->child
[index
]->parent
= *rp
;
/*--------------------------------------------
---------------------------------------------*/
void b_insert(b_tree_node_ptr
* root
,
b_tree_node_ptr rp
, temp
;
b_tree_atom_ptr promoted
;
b_recursiveInsert(root
, &promoted
, &rp
, atom
);
if(rp
){//Root was split, build new root
(*root
)->child
[0] = temp
;
(*root
)->data
[1] = promoted
;
/*--------------------------------------------
search for key and return the pointer of data.
---------------------------------------------*/
b_tree_atom_ptr
b_Find(b_tree_node_ptr
* p
,
while(!b_scanNode(*p
, *key
, &index
)){
if((*p
)->child
[index
] == 0)return 0;
else p
= &((*p
)->child
[index
]);
return (*p
)->data
[index
];
/*--------------------------------------------
updated data at the target key.
---------------------------------------------*/
int b_update(b_tree_atom_ptr
* atom
,
if(t_ptr
== (b_tree_atom_ptr
)b_Find(p
, &(*atom
)->key
)){
//t_ptr->data = (*atom)->data;
/*--------------------------------------------
recursive search for the target key
---------------------------------------------*/
int b_rmFind(b_tree_node_ptr
* p
,
if(!b_scanNode(*p
, (*atom
)->key
, &index
)){
if((*p
)->child
[index
] == 0)return 0;
b_rmFind(&((*p
)->child
[index
]), parent
, atom
);
/*--------------------------------------------
---------------------------------------------*/
void b_destory(b_tree_node_ptr
* root
)
for(idx
= 0; idx
< (*root
)->size
+ 1; idx
++){
if((*root
)->child
[idx
])b_destory(&((*root
)->child
[idx
]));
for(idx
= 0; idx
< (*root
)->size
; idx
++)free((*root
)->data
[idx
]);
/*--------------------------------------------
---------------------------------------------*/
int b_delete(b_tree_node_ptr
* root
,
b_tree_node_ptr
*parent
, *q
, *p
, temp_ptr
;
//find the elment with key to be deleted.
while(!b_scanNode(*p
, key
, &index
)){
if((*p
)->child
[index
]== 0)return 0;
p
= &((*p
)->child
[index
]);
free((*p
)->data
[index
]);//free the target node.
p
= &((*p
)->child
[index
]);//right subtree
p
= &((*p
)->child
[index
]);
//replace the deleted node with the leftmost element
(*parent
)->data
[index
] = (*p
)->data
[1];
if((*p
)->size
> B_TREE_ORDER
|| *parent
== 0){
if(*parent
== 0 && (*parent
)->size
== 1){//b-tree is empty.
b_copy(*p
, index
+1, (*p
)->size
, *p
, index
, (*p
)->size
-1);
if((*p
)->size
== 0)free(*p
);//node is empty
else if( (pidx
&& ((*parent
)->child
[pidx
-1]->size
> B_TREE_ORDER
)) ||
((*parent
)->size
> pidx
&& ((*parent
)->child
[pidx
+1]->size
> B_TREE_ORDER
)) || (!pidx
&& ((*parent
)->child
[pidx
+1]->size
> B_TREE_ORDER
)) ){
if(pidx
&& ((*parent
)->child
[pidx
-1]->size
> B_TREE_ORDER
)){
//removew an element from the left sibling.
q
= &((*parent
)->child
[pidx
-1]);
b_copy(*p
, 1, index
-1, *p
, 2, index
);
(*p
)->child
[1] = (*p
)->child
[0];
(*p
)->data
[1] = (*parent
)->data
[pidx
];
(*p
)->child
[0] = (*q
)->child
[(*q
)->size
];
if((*p
)->child
[0])(*p
)->child
[0]->parent
= *p
;
//replace the parent element with element borrowed from the rhn.
(*parent
)->data
[pidx
] = (*q
)->data
[(*q
)->size
];
//remove an element from the right sibling.
q
= &((*parent
)->child
[pidx
]);
b_copy(*p
, index
+1, (*p
)->size
, *p
, index
, (*p
)->size
-1);
(*p
)->data
[(*p
)->size
] = (*parent
)->data
[pidx
];
(*p
)->child
[(*p
)->size
] = (*q
)->child
[0];
if((*p
)->child
[(*p
)->size
])(*p
)->child
[(*p
)->size
]->parent
= *p
;
(*parent
)->data
[pidx
] = (*q
)->data
[1];
(*q
)->child
[0] = (*q
)->child
[1];
b_copy(*q
, 2, (*q
)->size
, *q
, 1, (*q
)->size
-1);
else{//merge the right and left node.
if(pidx
== 0 || (*parent
)->size
> pidx
){//merge the right sibling
q
= &((*parent
)->child
[pidx
]);
//shift the deleted node to right.
b_copy(*p
, index
+1, (*p
)->size
, *p
, index
, (*p
)->size
-1);
(*p
)->data
[(*p
)->size
] = (*parent
)->data
[pidx
];
//copy the right node to the left node.
(*p
)->child
[(*p
)->size
] = (*parent
)->child
[0];
if((*p
)->child
[(*p
)->size
])(*p
)->child
[(*p
)->size
]->parent
= *p
;
for(i
= (*p
)->size
+1; i
<= (*p
)->size
+(*q
)->size
;i
++){
(*p
)->data
[i
] = (*q
)->data
[j
];
(*p
)->child
[i
] = (*q
)->child
[j
++];
if((*p
)->child
[i
])(*p
)->child
[i
]->parent
= *p
;
(*p
)->size
+= (*q
)->size
;
else{//merged the left sibling
q
= &((*parent
)->child
[pidx
-1]);//get the left sibling
//shift the deleted node to right
b_copy(*p
, index
+1, (*p
)->size
, *p
, (*q
)->size
+index
+1, (*p
)->size
+(*q
)->size
);
b_copy(*p
, 1, index
-1, *p
, (*q
)->size
+2, (*q
)->size
+index
);
(*p
)->child
[(*q
)->size
+1] = (*p
)->child
[0];
(*p
)->data
[(*q
)->size
+1] = (*parent
)->data
[pidx
];
//copy the right node to the left node.
b_copy(*q
, 1, (*q
)->size
, *p
, 1, (*q
)->size
);
(*p
)->child
[0] = (*q
)->child
[0];
for(i
= 0; i
<= (*q
)->size
;i
++)if((*p
)->child
[0])(*p
)->child
[0]->parent
= *p
;
(*p
)->size
+= (*q
)->size
;
(*parent
)->child
[pidx
-1] = *p
;
if((*parent
)->size
> B_TREE_ORDER
){
//shift one node to left.
b_copy(*parent
, pidx
+1, (*parent
)->size
, *parent
, pidx
, (*parent
)->size
-1);
//immediate parent less than order.
parent
= &((*p
)->parent
);
if((*parent
== 0) && ((*p
)->size
== 1)){
//find the next parent index
for(pidx
= 0; pidx
< (*parent
)->size
;pidx
++)
if((*parent
)->data
[pidx
+1]->key
> (*p
)->data
[index
]->key
)break;