1 #ifndef __BStreeh 2 #define __BStreeh 3 4 /* routines for managing B-tree data structures */ 5 6 /* Note, if __TREE_RETURN is specified, then our error handling */ 7 /* routines will be CHKERRN and MY_SETERRN, otherwise, they will be */ 8 /* CHKERR and MY_SETERR */ 9 10 #define MAX_KIDS 9 11 #define MAX_KEYS (MAX_KIDS-1) 12 #define MIN_KIDS ((MAX_KIDS+1)/2) 13 #define MIN_KEYS (MIN_KIDS-1) 14 typedef struct __BStree_node { 15 int num_keys; 16 int keys[MAX_KEYS]; 17 char *data_ptr[MAX_KEYS]; 18 struct __BStree_node *child[MAX_KIDS], *parent; 19 } BStree_node; 20 typedef struct __BStree_ptr { 21 BStree_node *ptr; 22 int ind; 23 } BStree_ptr; 24 25 /* used in the special memory management routines */ 26 typedef struct __BSMBlock { 27 int base_size; 28 int num_units; 29 double *top, *bottom; /* bounds of memory for this block */ 30 /* used for free'ing quickly */ 31 struct __BSMBlock *next; /* Pointer to next BSMBlock */ 32 double *free_blocks; 33 int num_allocated; 34 double v; /* Dummy for top */ 35 } BSMBlock; 36 37 typedef struct __BStree { 38 BStree_node *root; 39 int u_data_size; 40 BSMBlock *node_blocks; 41 BSMBlock *user_blocks; 42 } BStree; 43 44 /* ********************** */ 45 /* special memory section */ 46 /* ********************** */ 47 /* on the Intel DELTA, the memory allocation routines *can* be be quite slow */ 48 /* thus, we have an option of using our own memory allocation routines that */ 49 /* were adopted from those in petsc */ 50 #if defined(PARCH_intelnx) 51 #define __SLOW_MALLOC 52 #endif 53 54 #if defined(__SLOW_MALLOC) 55 BSMBlock *BSsbinit(long,int); 56 double *BSsbmalloc(); 57 void BSsbfree(); 58 void BSmem_clean(); 59 #endif 60 61 #if defined(__SLOW_MALLOC) 62 #if defined (__TREE_RETURN) 63 #define MY_MALLOC_USER_DATA(tree,data_ptr) \ 64 { \ 65 if (tree.u_data_size > 0) { \ 66 if ((data_ptr = (char *) BSsbmalloc(&(tree.user_blocks))) == NULL) { \ 67 MY_SETERRCN(MEM_ERROR,"Out of memory allocating user data\n"); \ 68 } \ 69 } \ 70 } 71 #else 72 #define MY_MALLOC_USER_DATA(tree,data_ptr) \ 73 { \ 74 if (tree.u_data_size > 0) { \ 75 if ((data_ptr = (char *) BSsbmalloc(&(tree.user_blocks))) == NULL) { \ 76 MY_SETERRCN(MEM_ERROR,"Out of memory allocating user data\n"); \ 77 } \ 78 } \ 79 } 80 #endif 81 #else 82 #if defined (__TREE_RETURN) 83 #define MY_MALLOC_USER_DATA(tree,data_ptr) \ 84 { \ 85 if (tree.u_data_size > 0) { \ 86 MY_MALLOCN(data_ptr,(char *),tree.u_data_size,1); \ 87 } \ 88 } 89 #else 90 #define MY_MALLOC_USER_DATA(tree,data_ptr) \ 91 { \ 92 if (tree.u_data_size > 0) { \ 93 MY_MALLOCN(data_ptr,(char *),tree.u_data_size,1); \ 94 } \ 95 } 96 #endif 97 #endif 98 99 #if defined(__SLOW_MALLOC) 100 #define MY_FREE_USER_DATA(tree,data_ptr) \ 101 { \ 102 if (data_ptr != NULL) { \ 103 BSsbfree(data_ptr,&(tree.user_blocks)); \ 104 } \ 105 } 106 #else 107 #define MY_FREE_USER_DATA(tree,data_ptr) \ 108 { \ 109 if (data_ptr != NULL) { \ 110 MY_FREEN(data_ptr); \ 111 } \ 112 } 113 #endif 114 115 #if defined(__SLOW_MALLOC) 116 #define MY_FREE_TREE_NODE(tree,inptr) \ 117 { \ 118 int i99; \ 119 for (i99=0;i99<MAX_KEYS;i99++) { \ 120 MY_FREE_USER_DATA(tree,inptr->data_ptr[i99]); \ 121 } \ 122 BSsbfree(inptr,&(tree.node_blocks)); \ 123 } 124 #else 125 #define MY_FREE_TREE_NODE(tree,inptr) \ 126 { \ 127 int i99; \ 128 for (i99=0;i99<MAX_KEYS;i99++) { \ 129 MY_FREE_USER_DATA(tree,inptr->data_ptr[i99]); \ 130 } \ 131 MY_FREEN(inptr); \ 132 } 133 #endif 134 135 #if defined(__SLOW_MALLOC) 136 #if defined (__TREE_RETURN) 137 #define MY_GET_TREE_NODE(tree,inptr) \ 138 { \ 139 int i99; \ 140 if ((inptr = (BStree_node *) BSsbmalloc(&(tree.node_blocks))) == NULL) { \ 141 MY_SETERRCN(MEM_ERROR,"Out of memory allocating node data\n"); \ 142 } \ 143 inptr->num_keys = 0; \ 144 inptr->parent = NULL; \ 145 for (i99=0;i99<MAX_KIDS;i99++) { \ 146 inptr->child[i99] = NULL; \ 147 } \ 148 for (i99=0;i99<MAX_KEYS;i99++) { \ 149 inptr->data_ptr[i99] = NULL; \ 150 } \ 151 } 152 #else 153 #define MY_GET_TREE_NODE(tree,inptr) \ 154 { \ 155 int i99; \ 156 if ((inptr = (BStree_node *) BSsbmalloc(&(tree.node_blocks))) == NULL) { \ 157 MY_SETERRCN(MEM_ERROR,"Out of memory allocating node data\n"); \ 158 } \ 159 inptr->num_keys = 0; \ 160 inptr->parent = NULL; \ 161 for (i99=0;i99<MAX_KIDS;i99++) { \ 162 inptr->child[i99] = NULL; \ 163 } \ 164 for (i99=0;i99<MAX_KEYS;i99++) { \ 165 inptr->data_ptr[i99] = NULL; \ 166 } \ 167 } 168 #endif 169 #else 170 #if defined (__TREE_RETURN) 171 #define MY_GET_TREE_NODE(tree,inptr) \ 172 { \ 173 int i99; \ 174 MY_MALLOCN(inptr,(BStree_node *),sizeof(BStree_node),1); \ 175 inptr->num_keys = 0; \ 176 inptr->parent = NULL; \ 177 for (i99=0;i99<MAX_KIDS;i99++) { \ 178 inptr->child[i99] = NULL; \ 179 } \ 180 for (i99=0;i99<MAX_KEYS;i99++) { \ 181 inptr->data_ptr[i99] = NULL; \ 182 } \ 183 } 184 #else 185 #define MY_GET_TREE_NODE(tree,inptr) \ 186 { \ 187 int i99; \ 188 MY_MALLOCN(inptr,(BStree_node *),sizeof(BStree_node),1); \ 189 inptr->num_keys = 0; \ 190 inptr->parent = NULL; \ 191 for (i99=0;i99<MAX_KIDS;i99++) { \ 192 inptr->child[i99] = NULL; \ 193 } \ 194 for (i99=0;i99<MAX_KEYS;i99++) { \ 195 inptr->data_ptr[i99] = NULL; \ 196 } \ 197 } 198 #endif 199 #endif 200 201 #if defined(__SLOW_MALLOC) 202 #if defined (__TREE_RETURN) 203 #define MY_INIT_TREE(tree,user_data_size) \ 204 { \ 205 tree.root = NULL; \ 206 tree.u_data_size = user_data_size; \ 207 if ((tree.user_blocks = (void *) BSsbinit(tree.u_data_size,MAX_KEYS*128)) \ 208 == NULL) { \ 209 MY_SETERRCN(MEM_ERROR,"Out of memory initing user data\n"); \ 210 } \ 211 if ((tree.node_blocks = (void *) BSsbinit(sizeof(BStree_node),128)) \ 212 == NULL) { \ 213 MY_SETERRCN(MEM_ERROR,"Out of memory initing node data\n"); \ 214 } \ 215 } 216 #else 217 #define MY_INIT_TREE(tree,user_data_size) \ 218 { \ 219 tree.root = NULL; \ 220 tree.u_data_size = user_data_size; \ 221 if ((tree.user_blocks = (void *) BSsbinit(tree.u_data_size,MAX_KEYS*128)) \ 222 == NULL) { \ 223 MY_SETERRC(MEM_ERROR,"Out of memory initing user data\n"); \ 224 } \ 225 if ((tree.node_blocks = (void *) BSsbinit(sizeof(BStree_node),128)) \ 226 == NULL) { \ 227 MY_SETERRC(MEM_ERROR,"Out of memory initing node data\n"); \ 228 } \ 229 } 230 #endif 231 #else 232 #define MY_INIT_TREE(tree,user_data_size) \ 233 { \ 234 tree.root = NULL; \ 235 tree.u_data_size = user_data_size; \ 236 } 237 #endif 238 239 #if defined(__SLOW_MALLOC) 240 #define MY_CLEAN_TREE(tree) \ 241 { \ 242 BSmem_clean(&(tree.user_blocks)); \ 243 BSmem_clean(&(tree.node_blocks)); \ 244 } 245 #else 246 #define MY_CLEAN_TREE(tree) 247 #endif 248 249 /* ***************************** */ 250 /* end of special memory section */ 251 /* ***************************** */ 252 253 254 #define MY_PRINT_NODE(tptr) \ 255 { \ 256 int i99; \ 257 if (tptr == NULL) { \ 258 printf("NULL NODE\n"); \ 259 } else { \ 260 printf("Node has %d keys: ",tptr->num_keys); \ 261 if (tptr->child[0] != NULL) { \ 262 printf(" Child "); \ 263 } else { \ 264 printf(" NoChild "); \ 265 } \ 266 for (i99=0;i99<tptr->num_keys;i99++) { \ 267 printf("%d ",tptr->keys[i99]); \ 268 if (tptr->child[i99+1] != NULL) { \ 269 printf(" Child "); \ 270 } else { \ 271 printf(" NoChild "); \ 272 } \ 273 } \ 274 printf("\n"); \ 275 } \ 276 } 277 278 #define MY_NEXT_IN_TREE(node_ptr) \ 279 { \ 280 BStree_node *curptr99, *prevptr99, *chkptr99; \ 281 int done99, i99; \ 282 curptr99 = node_ptr.ptr->child[node_ptr.ind+1]; \ 283 if (curptr99 == NULL) { \ 284 node_ptr.ind++; \ 285 if (node_ptr.ind == node_ptr.ptr->num_keys) { \ 286 chkptr99 = node_ptr.ptr; \ 287 curptr99 = chkptr99->parent; \ 288 done99 = FALSE; \ 289 while ((curptr99 != NULL) && (! done99)) { \ 290 for (i99=0;i99<curptr99->num_keys+1;i99++) { \ 291 if (curptr99->child[i99] == chkptr99) break; \ 292 } \ 293 if (i99 < curptr99->num_keys) { \ 294 done99 = TRUE; \ 295 } else { \ 296 chkptr99 = curptr99; \ 297 curptr99 = curptr99->parent; \ 298 } \ 299 } \ 300 node_ptr.ptr = curptr99; \ 301 node_ptr.ind = i99; \ 302 } \ 303 } else { \ 304 while (curptr99 != NULL) { \ 305 prevptr99 = curptr99; \ 306 curptr99 = curptr99->child[0]; \ 307 } \ 308 node_ptr.ptr = prevptr99; \ 309 node_ptr.ind = 0; \ 310 } \ 311 } 312 313 #define IS_TREE_PTR_NULL(tree_ptr) ((tree_ptr.ptr == NULL)?1:0) 314 315 #define MY_FIRST_IN_TREE(tree,node_ptr) \ 316 { \ 317 BStree_node *tptr99, *pptr99; \ 318 tptr99 = tree.root; \ 319 pptr99 = tptr99; \ 320 while (tptr99 != NULL) { \ 321 pptr99 = tptr99; \ 322 tptr99 = tptr99->child[0]; \ 323 } \ 324 node_ptr.ptr = pptr99; \ 325 node_ptr.ind = 0; \ 326 } 327 328 #define MY_KEY_LT(key1,key2) (((key1) < (key2))?1:0) 329 #define MY_KEY_EQUAL(key1,key2) (((key1) == (key2))?1:0) 330 331 #define MY_MAKE_PARENT(inchild,inparent) \ 332 { \ 333 if (inchild != NULL) inchild->parent = inparent; \ 334 } 335 336 #define MY_PUT_IN_TREE(tree,inkey,inptr) \ 337 { \ 338 int done99, i99; \ 339 BStree_node *tptr99, *cur_right99, *tright99; \ 340 char *cur_data99, *tdata99; \ 341 int cur_key99, tkey99; \ 342 int temp_keys99[MAX_KEYS+1]; \ 343 BStree_node *temp_kids99[MAX_KEYS+1]; \ 344 char *temp_data99[MAX_KEYS+1]; \ 345 if (tree.root == NULL) { \ 346 MY_GET_TREE_NODE(tree,tree.root); \ 347 tree.root->num_keys = 1; \ 348 tree.root->keys[0] = inkey; \ 349 MY_MALLOC_USER_DATA(tree,tree.root->data_ptr[0]); \ 350 } else { \ 351 done99 = FALSE; \ 352 tptr99 = inptr; \ 353 cur_key99 = inkey; \ 354 cur_right99 = NULL; \ 355 MY_MALLOC_USER_DATA(tree,cur_data99); \ 356 while (! done99) { \ 357 if (tptr99 == NULL) { \ 358 MY_GET_TREE_NODE(tree,tptr99); \ 359 tptr99->num_keys = 1; \ 360 tptr99->keys[0] = cur_key99; \ 361 tptr99->data_ptr[0] = cur_data99; \ 362 tptr99->child[0] = tree.root; \ 363 tree.root->parent = tptr99; \ 364 tptr99->child[1] = cur_right99; \ 365 cur_right99->parent = tptr99; \ 366 tree.root = tptr99; \ 367 done99 = TRUE; \ 368 } else if (tptr99->num_keys < MAX_KEYS) { \ 369 MY_MAKE_PARENT(cur_right99,tptr99); \ 370 tptr99->keys[tptr99->num_keys] = cur_key99; \ 371 tptr99->child[tptr99->num_keys+1] = cur_right99; \ 372 tptr99->data_ptr[tptr99->num_keys] = cur_data99; \ 373 tptr99->num_keys++; \ 374 for (i99=tptr99->num_keys-1;i99>0;i99--) { \ 375 if (MY_KEY_LT(tptr99->keys[i99],tptr99->keys[i99-1])) { \ 376 tkey99 = tptr99->keys[i99]; \ 377 tright99 = tptr99->child[i99+1]; \ 378 tdata99 = tptr99->data_ptr[i99]; \ 379 tptr99->keys[i99] = tptr99->keys[i99-1]; \ 380 tptr99->child[i99+1] = tptr99->child[i99]; \ 381 tptr99->data_ptr[i99] = tptr99->data_ptr[i99-1]; \ 382 tptr99->keys[i99-1] = tkey99; \ 383 tptr99->child[i99] = tright99; \ 384 tptr99->data_ptr[i99-1] = tdata99; \ 385 } else { \ 386 break; \ 387 } \ 388 } \ 389 done99 = TRUE; \ 390 } else { \ 391 for (i99=0;i99<MAX_KEYS;i99++) { \ 392 temp_keys99[i99] = tptr99->keys[i99]; \ 393 temp_data99[i99] = tptr99->data_ptr[i99]; \ 394 temp_kids99[i99] = tptr99->child[i99+1]; \ 395 } \ 396 temp_keys99[MAX_KEYS] = cur_key99; \ 397 temp_data99[MAX_KEYS] = cur_data99; \ 398 temp_kids99[MAX_KEYS] = cur_right99; \ 399 for (i99=MAX_KEYS;i99>0;i99--) { \ 400 if (MY_KEY_LT(temp_keys99[i99],temp_keys99[i99-1])) { \ 401 tkey99 = temp_keys99[i99]; \ 402 tright99 = temp_kids99[i99]; \ 403 tdata99 = temp_data99[i99]; \ 404 temp_keys99[i99] = temp_keys99[i99-1]; \ 405 temp_kids99[i99] = temp_kids99[i99-1]; \ 406 temp_data99[i99] = temp_data99[i99-1]; \ 407 temp_keys99[i99-1] = tkey99; \ 408 temp_kids99[i99-1] = tright99; \ 409 temp_data99[i99-1] = tdata99; \ 410 } else { \ 411 break; \ 412 } \ 413 } \ 414 tptr99->num_keys = MIN_KEYS; \ 415 for (i99=0;i99<MIN_KEYS;i99++) { \ 416 tptr99->keys[i99] = temp_keys99[i99]; \ 417 tptr99->child[i99+1] = temp_kids99[i99]; \ 418 MY_MAKE_PARENT(tptr99->child[i99+1],tptr99); \ 419 tptr99->data_ptr[i99] = temp_data99[i99]; \ 420 } \ 421 for (i99=MIN_KEYS;i99<MAX_KEYS;i99++) { \ 422 tptr99->data_ptr[i99] = NULL; \ 423 } \ 424 MY_GET_TREE_NODE(tree,cur_right99); \ 425 cur_right99->num_keys = MIN_KEYS; \ 426 cur_right99->child[0] = temp_kids99[MIN_KEYS]; \ 427 MY_MAKE_PARENT(cur_right99->child[0],cur_right99); \ 428 for (i99=0;i99<MIN_KEYS;i99++) { \ 429 cur_right99->keys[i99] = temp_keys99[i99+MIN_KEYS+1]; \ 430 cur_right99->child[i99+1] = temp_kids99[i99+MIN_KEYS+1]; \ 431 MY_MAKE_PARENT(cur_right99->child[i99+1],cur_right99); \ 432 cur_right99->data_ptr[i99] = temp_data99[i99+MIN_KEYS+1]; \ 433 } \ 434 cur_key99 = temp_keys99[MIN_KEYS]; \ 435 cur_data99 = temp_data99[MIN_KEYS]; \ 436 tptr99 = tptr99->parent; \ 437 } \ 438 } \ 439 } \ 440 } 441 442 #define MY_SEARCH_TREE(tree,inkey,found,node_ptr) \ 443 { \ 444 BStree_node *tptr99, *pptr99; \ 445 int down99, i99; \ 446 tptr99 = tree.root; \ 447 pptr99 = tptr99; \ 448 found = FALSE; \ 449 while ((tptr99 != NULL) && (! found)) { \ 450 down99 = FALSE; \ 451 pptr99 = tptr99; \ 452 for (i99=0;i99<tptr99->num_keys;i99++) { \ 453 if (MY_KEY_EQUAL(inkey,tptr99->keys[i99])) { \ 454 found = TRUE; \ 455 down99 = TRUE; \ 456 node_ptr.ptr = tptr99; \ 457 node_ptr.ind = i99; \ 458 break; \ 459 } else if (MY_KEY_LT(inkey,tptr99->keys[i99])) { \ 460 down99 = TRUE; \ 461 tptr99 = tptr99->child[i99]; \ 462 break; \ 463 } \ 464 } \ 465 if (! down99) { \ 466 tptr99 = tptr99->child[tptr99->num_keys]; \ 467 } \ 468 } \ 469 if (!found) { \ 470 node_ptr.ptr = pptr99; \ 471 } \ 472 } 473 474 #define MY_INSERT_TREE_NODE(tree,inkey,found,node_ptr,key_count) \ 475 { \ 476 MY_SEARCH_TREE(tree,inkey,found,node_ptr); \ 477 if (!found) { \ 478 key_count++; \ 479 MY_PUT_IN_TREE(tree,inkey,(node_ptr.ptr)); \ 480 MY_SEARCH_TREE(tree,inkey,found,node_ptr); \ 481 found = FALSE; \ 482 } \ 483 } 484 485 #define MY_GET_TREE_DATA(node_ptr) node_ptr.ptr->data_ptr[node_ptr.ind] 486 487 #define MY_GET_TREE_KEY(node_ptr) node_ptr.ptr->keys[node_ptr.ind] 488 489 #define MY_FREE_TREE(tree) \ 490 { \ 491 BStree_node *curptr99, *tptr99; \ 492 int i99, found99; \ 493 curptr99 = tree.root; \ 494 while (curptr99 != NULL) { \ 495 found99 = FALSE; \ 496 for (i99=0;i99<curptr99->num_keys+1;i99++) { \ 497 tptr99 = curptr99->child[i99]; \ 498 if (tptr99 != NULL) { \ 499 curptr99->child[i99] = NULL; \ 500 curptr99 = tptr99; \ 501 found99 = TRUE; \ 502 break; \ 503 } \ 504 } \ 505 if (! found99) { \ 506 tptr99 = curptr99; \ 507 curptr99 = curptr99->parent; \ 508 MY_FREE_TREE_NODE(tree,tptr99); \ 509 } \ 510 } \ 511 MY_CLEAN_TREE(tree); \ 512 } 513 514 #endif 515