Charm++: Charm Source Code Documentation

00001 
00002 #include "converse.h"
00003 #include "mem-arena.h"
00004 
00005 #if USE_BTREE
00006 
00007 /* ======================================================================
00008  * New (b-tree-based implementation)
00009  * ====================================================================== */
00010 
00011 
00012 /* return value for a b-tree insert */
00013 typedef struct _insert_ret_val {
00014   slotblock sb;
00015   btreenode *btn;
00016 } insert_ret_val;
00017 
00018 /*****************************************************************
00019  * Find and return the number of the bin (list) to which the number
00020  * nslots belongs.  The range of each bin is 2^(b-1)+1 to 2^b, where b
00021  * is the bin number.
00022  *****************************************************************/
00023 
00024 static int find_list_bin(CmiInt8 nslots) {
00025   int list_bin     = 32;
00026   CmiInt8 comp_num = 0x100000000LL;
00027   int inc          = 16;
00028 
00029   while (1) {
00030     if ((nslots > (comp_num >> 1)) && (nslots <= comp_num)) {
00031       /* found it */
00032       return list_bin;
00033     } else if (nslots < comp_num) {
00034       /* look left  */
00035       list_bin -= inc;
00036       comp_num  = comp_num >> inc;
00037       if ((inc = inc >> 1) == 0) {
00038     inc = 1;
00039       }
00040     } else {
00041       /* look right */
00042       list_bin += inc;
00043       comp_num  = comp_num << inc;
00044       if ((inc = inc >> 1) == 0) {
00045     inc = 1;
00046       }
00047     }
00048   }
00049 
00050 }
00051 
00052 /*****************************************************************
00053  * Creates and inserts a new dllnode into list_array (part of the
00054  * slotset ss) that both points to and is pointed to by the slotblock
00055  * sb.  This function also returns a pointer to that new dllnode.
00056  *****************************************************************/
00057 
00058 static dllnode *list_insert(slotset *ss, slotblock *sb) {
00059 
00060   /* find the list bin to put the new dllnode in  */
00061   int list_bin = find_list_bin(sb->nslots);
00062 
00063   /* allocate memory for the new node */
00064   dllnode *new_dlln = (dllnode *)(malloc(sizeof(dllnode)));
00065 
00066   /* insert the dllnode */
00067   new_dlln->previous = NULL;
00068   new_dlln->next     = ss->list_array[list_bin];
00069   new_dlln->sb       = sb;
00070   if (ss->list_array[list_bin] != NULL) {
00071     ss->list_array[list_bin]->previous = new_dlln;
00072   }
00073   ss->list_array[list_bin] = new_dlln;
00074 
00075   return new_dlln;
00076 
00077 }
00078 
00079 /*****************************************************************
00080  * Deletes the dllnode from list_array (part of the slotset ss) that
00081  * is pointed to by the slotblock sb.
00082  *****************************************************************/
00083 
00084 static void list_delete(slotset *ss, slotblock *sb) {
00085 
00086   /* remove the node from the list */
00087   if (sb->listblock->next != NULL) {
00088     sb->listblock->next->previous = sb->listblock->previous;
00089   }
00090   if (sb->listblock->previous != NULL) {
00091     sb->listblock->previous->next = sb->listblock->next;
00092   } else {  /* first element in the list */
00093     ss->list_array[find_list_bin(sb->nslots)] = sb->listblock->next;
00094   }
00095 
00096   /* free the memory from the node */
00097   free(sb->listblock);
00098 
00099 }
00100 
00101 /*****************************************************************
00102  * Moves the dllnode dlln to the correct bin (list) of slotset ss
00103  * based on the number of slots in the slotblock to which dlln points.
00104  * It is assumed that the slotblock pointed to by dlln has already been
00105  * updated with the new number of slots.  The integer old_nslots
00106  * contains the number of slots that used to be in the slotblock.
00107  *****************************************************************/
00108 
00109 static void list_move(slotset *ss, dllnode *dlln, CmiInt8 old_nslots) {
00110 
00111   /* determine the bin the slotblock used to be in */
00112   int old_bin = find_list_bin(old_nslots);
00113 
00114   /* determine the bin the slotblock is in now */
00115   int new_bin = find_list_bin(dlln->sb->nslots);
00116 
00117   /* if the old bin and new bin are different, move the slotblock */
00118   if (new_bin != old_bin) {
00119 
00120     /* remove from old bin */
00121     if (dlln->previous == NULL) {  /* dlln is the 1st element in the list */
00122       if (dlln->next != NULL) {
00123     dlln->next->previous = NULL;
00124       }
00125       ss->list_array[old_bin] = dlln->next;
00126     } else {
00127       if (dlln->next != NULL) {
00128     dlln->next->previous = dlln->previous;
00129       }
00130       dlln->previous->next = dlln->next;
00131     }
00132 
00133     /* insert at the beginning of the new bin */
00134     dlln->next     = ss->list_array[new_bin];
00135     dlln->previous = NULL;
00136     if (dlln->next != NULL) {
00137       dlln->next->previous = dlln;
00138     }
00139     ss->list_array[new_bin] = dlln;
00140   }
00141 
00142 }
00143 
00144 /*****************************************************************
00145  * Creates a new b-tree node
00146  *****************************************************************/
00147 
00148 static btreenode *create_btree_node(void) {
00149   int i;
00150   btreenode *btn = (btreenode *)malloc(sizeof(btreenode));
00151   btn->num_blocks = 0;
00152   for (i = 0; i < TREE_NODE_SIZE; i++) {
00153     btn->blocks[i].listblock = NULL;
00154   }
00155   for (i = 0; i < TREE_NODE_SIZE + 1; i++) {
00156     btn->child[i] = NULL;
00157   }
00158   return btn;
00159 }
00160 
00161 /*****************************************************************
00162  * Find the slotblock in the b-tree that contains startslot.  Returns
00163  * NULL if such a block cannot be found.
00164  *****************************************************************/
00165 
00166 static slotblock *find_btree_slotblock(btreenode *node, CmiInt8 startslot) {
00167 
00168   /* check if this node exists */
00169   if ((node == NULL) || (startslot < 0) || (node->num_blocks == 0)) {
00170     return NULL;
00171   } else {
00172 
00173     /*** Binary search on this node ***/
00174     /* initialize */
00175     int index = node->num_blocks >> 1;
00176     int inc   = (index >> 1) + (node->num_blocks & 0x1);
00177     CmiInt8 endslot;
00178 
00179     /* loop until a node is found */
00180     while (1) {
00181 
00182       /* if startslot is in current slotblock, this is the slotblock */
00183       endslot = node->blocks[index].startslot + node->blocks[index].nslots - 1;
00184       if ((startslot >= node->blocks[index].startslot) &&
00185       (startslot <= endslot)) {
00186     return &(node->blocks[index]);
00187       }
00188 
00189       /* else, if startslot is less */
00190       else if (startslot < node->blocks[index].startslot) {
00191 
00192     /* if this is slotblock 0, take the left child */
00193     if (index == 0) {
00194       return find_btree_slotblock(node->child[index], startslot);
00195     }
00196 
00197     /* else check endslot of the slotblock to the left */
00198     else {
00199 
00200       /* if startslot > endslot-of-slotblock-to-the-left, take the
00201          left child */
00202       endslot = node->blocks[index-1].startslot + 
00203         node->blocks[index-1].nslots - 1;
00204       if (startslot > endslot) {
00205         return find_btree_slotblock(node->child[index], startslot);
00206       }
00207 
00208       /* else continue to search this node to the left */
00209       else {
00210         index -= inc;
00211         if ((inc = inc >> 1) == 0) {
00212           inc = 1;
00213         }
00214       }
00215     }
00216       }
00217 
00218       /* else, startslot must be greater */
00219       else {
00220 
00221     /* if this is the last slotblock, take the right child */
00222     if (index == node->num_blocks - 1) {
00223       return find_btree_slotblock(node->child[index+1], startslot);
00224     }
00225 
00226     /* else check startslot of the slotblock to the right */
00227     else {
00228 
00229       /* if startslot < startslot-of-slotblock-to-the-right, then
00230          take the right child */
00231       if (startslot < node->blocks[index+1].startslot) {
00232         return find_btree_slotblock(node->child[index+1], startslot);
00233       }
00234 
00235       /* else continue to search this node to the right */
00236       else {
00237         index += inc;
00238         if ((inc = inc >> 1) == 0) {
00239           inc = 1;
00240         }
00241       }
00242     }
00243       }
00244       
00245     }
00246 
00247   }
00248 
00249 }
00250 
00251 /*****************************************************************
00252  * Insert a slotblock into the b-tree starting at startslot and going
00253  * for nslots slots
00254  *****************************************************************/
00255 
00256 static insert_ret_val btree_insert_int(slotset *ss, btreenode *node, 
00257                        CmiInt8 startslot, CmiInt8 nslots) {
00258 
00259   insert_ret_val irv;
00260 
00261   /*** binary search for the place to insert ***/
00262 
00263   /* initialize */
00264   int index = node->num_blocks >> 1;
00265   int inc   = (index >> 1) + (node->num_blocks & 0x1);
00266 
00267   /* loop until an insertion happens */
00268   while (1) {
00269     if (startslot < node->blocks[index].startslot) {  /* look to the left */
00270       if ((index == 0) || 
00271       (startslot > node->blocks[index-1].startslot)) {
00272     if (node->child[index] != NULL) {             /* take left child */
00273       irv = btree_insert_int(ss, node->child[index], startslot, nslots);
00274       if (irv.btn == NULL) {
00275         return irv;
00276       } else {                                    /* merge return value */
00277         int i, j;                                 /*   insert on left   */
00278         for (i = node->num_blocks; i > index; i--) {
00279           node->blocks[i].startslot     = node->blocks[i-1].startslot;
00280           node->blocks[i].nslots        = node->blocks[i-1].nslots;
00281           node->blocks[i].listblock     = node->blocks[i-1].listblock;
00282           node->blocks[i].listblock->sb = &(node->blocks[i]);
00283           node->child[i+1]              = node->child[i];
00284         }
00285         node->blocks[index].startslot     = irv.sb.startslot;
00286         node->blocks[index].nslots        = irv.sb.nslots;
00287         node->blocks[index].listblock     = irv.sb.listblock;
00288         node->blocks[index].listblock->sb = &(node->blocks[index]);
00289         node->child[index+1]              = irv.btn;
00290         node->num_blocks++;
00291         if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
00292           btreenode *new_node = create_btree_node();
00293           for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
00294         j = i - (TREE_NODE_MID + 1);
00295         new_node->blocks[j].startslot     = node->blocks[i].startslot;
00296         new_node->blocks[j].nslots        = node->blocks[i].nslots;
00297         new_node->blocks[j].listblock     = node->blocks[i].listblock;
00298         new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
00299           }
00300           for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
00301         new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
00302           }
00303           node->num_blocks     = TREE_NODE_MID;
00304           new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
00305 
00306           irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
00307           irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
00308           irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
00309           irv.btn          = new_node;
00310           return irv;
00311         } else {
00312           irv.btn = NULL;
00313           return irv;
00314         }
00315       }
00316     } else {                                      /* insert to the left */
00317       int i, j;
00318       for (i = node->num_blocks; i > index; i--) {
00319         node->blocks[i].startslot     = node->blocks[i-1].startslot;
00320         node->blocks[i].nslots        = node->blocks[i-1].nslots;
00321         node->blocks[i].listblock     = node->blocks[i-1].listblock;
00322         node->blocks[i].listblock->sb = &(node->blocks[i]);
00323       }
00324       node->blocks[index].startslot = startslot;
00325       node->blocks[index].nslots    = nslots;
00326       node->blocks[index].listblock = list_insert(ss, &(node->blocks[index]));
00327       node->num_blocks++;
00328       if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
00329         btreenode *new_node = create_btree_node();
00330         for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
00331           j = i - (TREE_NODE_MID + 1);
00332           new_node->blocks[j].startslot     = node->blocks[i].startslot;
00333           new_node->blocks[j].nslots        = node->blocks[i].nslots;
00334           new_node->blocks[j].listblock     = node->blocks[i].listblock;
00335           new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
00336         }
00337         node->num_blocks     = TREE_NODE_MID;
00338         new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
00339 
00340         irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
00341         irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
00342         irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
00343         irv.btn          = new_node;
00344         return irv;
00345       } else {
00346         irv.btn = NULL;
00347         return irv;
00348       }
00349     }
00350       } else {                                        /* search to the left */
00351     index -= inc;
00352     if ((inc = inc >> 1) == 0) {
00353       inc = 1;
00354     }
00355       }
00356 
00357     } else {                                          /* look to the right */
00358 
00359       if ((index == node->num_blocks - 1) || 
00360       (startslot < node->blocks[index+1].startslot)) {
00361     if (node->child[index+1] != NULL) {           /* take right child */
00362       irv = btree_insert_int(ss, node->child[index+1], startslot, nslots);
00363       if (irv.btn == NULL) {
00364         return irv;
00365       } else {                                    /* merge return value */
00366         int i, j;                                 /*   insert on right  */
00367         for (i = node->num_blocks; i > index + 1; i--) {
00368           node->blocks[i].startslot     = node->blocks[i-1].startslot;
00369           node->blocks[i].nslots        = node->blocks[i-1].nslots;
00370           node->blocks[i].listblock     = node->blocks[i-1].listblock;
00371           node->blocks[i].listblock->sb = &(node->blocks[i]);
00372           node->child[i+1]              = node->child[i];
00373         }
00374         node->blocks[index+1].startslot     = irv.sb.startslot;
00375         node->blocks[index+1].nslots        = irv.sb.nslots;
00376         node->blocks[index+1].listblock     = irv.sb.listblock;
00377         node->blocks[index+1].listblock->sb = &(node->blocks[index+1]);
00378         node->child[index+2]                = irv.btn;
00379         node->num_blocks++;
00380         if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
00381           btreenode *new_node = create_btree_node();
00382           for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
00383         j = i - (TREE_NODE_MID + 1);
00384         new_node->blocks[j].startslot     = node->blocks[i].startslot;
00385         new_node->blocks[j].nslots        = node->blocks[i].nslots;
00386         new_node->blocks[j].listblock     = node->blocks[i].listblock;
00387         new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
00388           }
00389           for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
00390         new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
00391           }
00392           node->num_blocks     = TREE_NODE_MID;
00393           new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
00394 
00395           irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
00396           irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
00397           irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
00398           irv.btn          = new_node;
00399           return irv;
00400         } else {
00401           irv.btn = NULL;
00402           return irv;
00403         }
00404       }
00405     } else {                                      /* insert to the right */
00406       int i, j;
00407       for (i = node->num_blocks; i > index + 1; i--) {
00408         node->blocks[i].startslot     = node->blocks[i-1].startslot;
00409         node->blocks[i].nslots        = node->blocks[i-1].nslots;
00410         node->blocks[i].listblock     = node->blocks[i-1].listblock;
00411         node->blocks[i].listblock->sb = &(node->blocks[i]);
00412       }
00413       node->blocks[index+1].startslot = startslot;
00414       node->blocks[index+1].nslots    = nslots;
00415       node->blocks[index+1].listblock = list_insert(ss, &(node->blocks[index+1]));
00416       node->num_blocks++;
00417       if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
00418         btreenode *new_node = create_btree_node();
00419         for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
00420           j = i - (TREE_NODE_MID + 1);
00421           new_node->blocks[j].startslot     = node->blocks[i].startslot;
00422           new_node->blocks[j].nslots        = node->blocks[i].nslots;
00423           new_node->blocks[j].listblock     = node->blocks[i].listblock;
00424           new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
00425         }
00426         node->num_blocks = TREE_NODE_MID;
00427         new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
00428 
00429         irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
00430         irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
00431         irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
00432         irv.btn          = new_node;
00433         return irv;
00434       } else {
00435         irv.btn = NULL;
00436         return irv;
00437       }
00438     }
00439       } else {                                        /* search to the right */
00440     index += inc;
00441     if ((inc = inc >> 1) == 0) {
00442       inc = 1;
00443     }
00444       }
00445     }
00446   }
00447 
00448 }
00449 
00450 static btreenode *btree_insert(slotset *ss, btreenode *node, 
00451                    CmiInt8 startslot, CmiInt8 nslots) {
00452 
00453   /* check the b-tree root: if it's empty, insert the element in the
00454      first position */
00455   if (node->num_blocks == 0) {
00456 
00457     node->num_blocks          = 1;
00458     node->blocks[0].startslot = startslot;
00459     node->blocks[0].nslots    = nslots;
00460     node->blocks[0].listblock = list_insert(ss, &(node->blocks[0]));
00461 
00462   } else {
00463 
00464     /* insert into the b-tree */
00465     insert_ret_val irv = btree_insert_int(ss, node, startslot, nslots);
00466 
00467     /* if something was returned, we need a new root */
00468     if (irv.btn != NULL) {
00469       btreenode *new_root  = create_btree_node();
00470       new_root->num_blocks = 1;
00471       new_root->blocks[0].startslot     = irv.sb.startslot;
00472       new_root->blocks[0].nslots        = irv.sb.nslots;
00473       new_root->blocks[0].listblock     = irv.sb.listblock;
00474       new_root->blocks[0].listblock->sb = &(new_root->blocks[0]);
00475       new_root->child[0] = node;
00476       new_root->child[1] = irv.btn;
00477       node = new_root;
00478     }
00479 
00480   }
00481 
00482   return node;
00483 
00484 }
00485 
00486 /*****************************************************************
00487  * Delete the slotblock from the b-tree starting at startslot
00488  *****************************************************************/
00489 
00490 static void btree_delete_int(slotset *ss, btreenode *node, 
00491                  CmiInt8 startslot, slotblock *sb) {
00492 
00493   int index, inc;
00494   int i;
00495 
00496   /* If sb is not NULL, we're sending sb down the tree to a leaf to be
00497      swapped with the next larger startslot so it can be deleted from
00498      a leaf node (deletions from non-leaf nodes are not allowed
00499      here).  At this point, the next larger startslot will always be
00500      found by taking the leftmost child.  */
00501   if (sb != NULL) {
00502 
00503     if (node->child[0] != NULL) {
00504       btree_delete_int(ss, node->child[0], startslot, sb);
00505       index = 0;
00506 
00507     } else {
00508 
00509       /* we're now at a leaf node, so the slotblock can be deleted
00510 
00511          first, copy slotblock 0 to the block passed down (sb) and
00512          delete the list array node  */
00513       list_delete(ss, sb);
00514       sb->startslot     = node->blocks[0].startslot;
00515       sb->nslots        = node->blocks[0].nslots;
00516       sb->listblock     = node->blocks[0].listblock;
00517       sb->listblock->sb = sb;
00518 
00519       /* delete the slotblock */
00520       for (i = 0; i < (node->num_blocks - 1); i++) {
00521     node->blocks[i].startslot     = node->blocks[i+1].startslot;
00522     node->blocks[i].nslots        = node->blocks[i+1].nslots;
00523     node->blocks[i].listblock     = node->blocks[i+1].listblock;
00524     node->blocks[i].listblock->sb = &(node->blocks[i]);
00525       }
00526       node->num_blocks--;
00527 
00528       return;
00529 
00530     }
00531 
00532   } else {
00533 
00534     /*** Binary search for the slotblock to delete ***/
00535 
00536     /* initialize */
00537     index = node->num_blocks >> 1;
00538     inc = (index >> 1) + (node->num_blocks & 0x1);
00539 
00540     /* loop until the slotblock with startslot is found */
00541     while (1) {
00542 
00543       if (startslot == node->blocks[index].startslot) {   /* found it */
00544     if (node->child[index+1] != NULL) {               /* not a leaf */
00545       btree_delete_int(ss, node->child[index+1], 
00546                startslot, &(node->blocks[index]));
00547       break;
00548     } else {                                          /* is a leaf */
00549       int i;
00550       /* delete the slotblock */
00551       list_delete(ss, &(node->blocks[index]));
00552       for (i = index; i < (node->num_blocks - 1); i++) {
00553         node->blocks[i].startslot     = node->blocks[i+1].startslot;
00554         node->blocks[i].nslots        = node->blocks[i+1].nslots;
00555         node->blocks[i].listblock     = node->blocks[i+1].listblock;
00556         node->blocks[i].listblock->sb = &(node->blocks[i]);
00557       }
00558       node->num_blocks--;
00559       return;
00560     }
00561       } else {
00562     if (startslot < node->blocks[index].startslot) {  /* look left */
00563       if ((index == 0) ||                             /* take left child */
00564           (startslot > node->blocks[index-1].startslot)) {
00565         btree_delete_int(ss, node->child[index], startslot, sb);
00566         break;
00567       } else {                                        /* search left */
00568         index -= inc;
00569         if ((inc = inc >> 1) == 0) {
00570           inc = 1;
00571         }
00572       }
00573     } else {                                          /* look right */
00574       if ((index == node->num_blocks - 1) ||          /* take right child */
00575           (startslot < node->blocks[index+1].startslot)) {
00576         btree_delete_int(ss, node->child[index+1], startslot, sb);
00577         break;
00578       } else {                                        /* search right */
00579         index += inc;
00580         if ((inc = inc >> 1) == 0) {
00581           inc = 1;
00582         }
00583       }
00584     }
00585       }
00586 
00587     }
00588 
00589   }
00590 
00591   {   /* BLOCK
00592      At this point, the desired slotblock has been removed, and we're
00593      going back up the tree.  We must check for deficient nodes that
00594      require the rotating or combining of elements to maintain a
00595      balanced b-tree. */
00596   int i;
00597   int def_child = -1;
00598 
00599   /* check if one of the child nodes is deficient  */
00600   if (node->child[index]->num_blocks < TREE_NODE_MID) {
00601     def_child = index;
00602   } else if (node->child[index+1]->num_blocks < TREE_NODE_MID) {
00603     def_child = index + 1;
00604   }
00605 
00606   if (def_child >= 0) {
00607 
00608     /* if there is a left sibling and it has enough elements, rotate */
00609     /* to the right */
00610     if ((def_child != 0) && (node->child[def_child-1] != NULL) && 
00611     (node->child[def_child-1]->num_blocks > TREE_NODE_MID)) {
00612 
00613       /* move all elements in deficient child to the right */
00614       for (i = node->child[def_child]->num_blocks; i > 0; i--) {
00615     node->child[def_child]->blocks[i].startslot = 
00616       node->child[def_child]->blocks[i-1].startslot;
00617     node->child[def_child]->blocks[i].nslots = 
00618       node->child[def_child]->blocks[i-1].nslots;
00619     node->child[def_child]->blocks[i].listblock = 
00620       node->child[def_child]->blocks[i-1].listblock;
00621     node->child[def_child]->blocks[i].listblock->sb = 
00622       &(node->child[def_child]->blocks[i]);
00623       }
00624       for (i = node->child[def_child]->num_blocks + 1; i > 0; i--) {
00625     node->child[def_child]->child[i] = 
00626       node->child[def_child]->child[i-1];
00627       }
00628 
00629       /* move parent element to the deficient child */
00630       node->child[def_child]->blocks[0].startslot = 
00631     node->blocks[def_child-1].startslot;
00632       node->child[def_child]->blocks[0].nslots = 
00633     node->blocks[def_child-1].nslots;
00634       node->child[def_child]->blocks[0].listblock = 
00635     node->blocks[def_child-1].listblock;
00636       node->child[def_child]->blocks[0].listblock->sb = 
00637     &(node->child[def_child]->blocks[0]);
00638       node->child[def_child]->num_blocks++;
00639 
00640       /* move the right-most child of the parent's left child to the
00641          left-most child of the formerly deficient child  */
00642       i = node->child[def_child-1]->num_blocks;
00643       node->child[def_child]->child[0] = 
00644     node->child[def_child-1]->child[i];
00645 
00646       /* move largest element from left child up to the parent */
00647       i--;
00648       node->blocks[def_child-1].startslot = 
00649     node->child[def_child-1]->blocks[i].startslot;
00650       node->blocks[def_child-1].nslots = 
00651     node->child[def_child-1]->blocks[i].nslots;
00652       node->blocks[def_child-1].listblock = 
00653     node->child[def_child-1]->blocks[i].listblock;
00654       node->blocks[def_child-1].listblock->sb = 
00655     &(node->blocks[def_child-1]);
00656       node->child[def_child-1]->num_blocks--;
00657 
00658     }
00659 
00660     /* otherwise, if there is a right sibling and it has enough */
00661     /* elements, rotate to the left */
00662     else if (((def_child + 1) <= node->num_blocks) && 
00663          (node->child[def_child+1] != NULL) && 
00664          (node->child[def_child+1]->num_blocks > TREE_NODE_MID)) {
00665 
00666       /* move parent element to the deficient child */
00667       i = node->child[def_child]->num_blocks;
00668       node->child[def_child]->blocks[i].startslot = 
00669     node->blocks[def_child].startslot;
00670       node->child[def_child]->blocks[i].nslots = 
00671     node->blocks[def_child].nslots;
00672       node->child[def_child]->blocks[i].listblock = 
00673     node->blocks[def_child].listblock;
00674       node->child[def_child]->blocks[i].listblock->sb = 
00675     &(node->child[def_child]->blocks[i]);
00676       node->child[def_child]->num_blocks++;
00677 
00678       /* move the left-most child of the parent's right child to the
00679          right-most child of the formerly deficient child  */
00680       i++;
00681       node->child[def_child]->child[i] = 
00682     node->child[def_child+1]->child[0];
00683 
00684       /* move smallest element from right child up to the parent */
00685       node->blocks[def_child].startslot = 
00686     node->child[def_child+1]->blocks[0].startslot;
00687       node->blocks[def_child].nslots = 
00688     node->child[def_child+1]->blocks[0].nslots;
00689       node->blocks[def_child].listblock = 
00690     node->child[def_child+1]->blocks[0].listblock;
00691       node->blocks[def_child].listblock->sb = 
00692     &(node->blocks[def_child]);
00693       node->child[def_child+1]->num_blocks--;
00694 
00695       /* move all elements in the parent's right child to the left  */
00696       for (i = 0; i < node->child[def_child+1]->num_blocks; i++) {
00697     node->child[def_child+1]->blocks[i].startslot = 
00698       node->child[def_child+1]->blocks[i+1].startslot;
00699     node->child[def_child+1]->blocks[i].nslots = 
00700       node->child[def_child+1]->blocks[i+1].nslots;
00701     node->child[def_child+1]->blocks[i].listblock = 
00702       node->child[def_child+1]->blocks[i+1].listblock;
00703     node->child[def_child+1]->blocks[i].listblock->sb = 
00704       &(node->child[def_child+1]->blocks[i]);
00705       }
00706       for (i = 0; i < node->child[def_child+1]->num_blocks + 1; i++) {
00707     node->child[def_child+1]->child[i] = 
00708       node->child[def_child+1]->child[i+1];
00709       }
00710     }    /* BLOCK */
00711     }
00712 
00713     /* otherwise, merge the deficient node, parent, and the parent's
00714        other child (one of the deficient node's siblings) by dropping
00715        the parent down to the level of the children */
00716     else {
00717 
00718       /* move the parent element into the left child node */
00719       i = node->child[index]->num_blocks;
00720       node->child[index]->blocks[i].startslot = 
00721     node->blocks[index].startslot;
00722       node->child[index]->blocks[i].nslots = 
00723     node->blocks[index].nslots;
00724       node->child[index]->blocks[i].listblock = 
00725     node->blocks[index].listblock;
00726       node->child[index]->blocks[i].listblock->sb = 
00727     &(node->child[index]->blocks[i]);
00728       node->child[index]->num_blocks++;
00729 
00730       {   /* BLOCK */
00731       /* move the elements and children of the right child node to the */
00732       /* left child node */
00733       int num_left  = node->child[index]->num_blocks;
00734       int num_right = node->child[index+1]->num_blocks;
00735       int left_pos;
00736       int right_pos = 0;
00737       for (left_pos = num_left; left_pos < num_left + num_right; left_pos++) {
00738     node->child[index]->blocks[left_pos].startslot = 
00739       node->child[index+1]->blocks[right_pos].startslot;
00740     node->child[index]->blocks[left_pos].nslots = 
00741       node->child[index+1]->blocks[right_pos].nslots;
00742     node->child[index]->blocks[left_pos].listblock = 
00743       node->child[index+1]->blocks[right_pos].listblock;
00744     node->child[index]->blocks[left_pos].listblock->sb = 
00745       &(node->child[index]->blocks[left_pos]);
00746     right_pos++;
00747       }
00748       right_pos = 0;
00749       for (left_pos = num_left; left_pos < num_left + num_right + 1; left_pos++) {
00750     node->child[index]->child[left_pos] = 
00751       node->child[index+1]->child[right_pos];
00752     right_pos++;
00753       }
00754       node->child[index]->num_blocks = num_left + num_right;
00755 
00756       /* delete the right child node */
00757       free(node->child[index+1]);
00758       node->child[index+1] = NULL;
00759 
00760       /* update the parent node */
00761       node->num_blocks--;
00762       for (i = index; i < node->num_blocks; i++) {
00763     node->blocks[i].startslot     = node->blocks[i+1].startslot;
00764     node->blocks[i].nslots        = node->blocks[i+1].nslots;
00765     node->blocks[i].listblock     = node->blocks[i+1].listblock;
00766     node->blocks[i].listblock->sb = &(node->blocks[i]);
00767     node->child[i+1]              = node->child[i+2];
00768       }
00769       }  /* BLOCK */
00770     }
00771 
00772   }
00773 
00774 }
00775 
00776 static btreenode *btree_delete(slotset *ss, btreenode *node, CmiInt8 startslot) {
00777 
00778   /* delete element from the b-tree */
00779   btree_delete_int(ss, node, startslot, NULL);
00780 
00781   /* if the root node is empty (from a combine operation on the tree),
00782      the left-most child of the root becomes the new root, unless the
00783      left-most child is NULL, in which case we leave the root node
00784      empty but not NULL */
00785   if (node->num_blocks == 0) {
00786     if (node->child[0] != NULL) {
00787       btreenode *new_root = node->child[0];
00788       free(node);
00789       node = new_root;
00790     }
00791   }
00792 
00793   return node;
00794 
00795 }
00796 
00797 /*****************************************************************
00798  * Creates a new slotset with nslots entries, starting with all empty
00799  * slots.  The slot numbers are [startslot, startslot + nslots - 1].
00800  *****************************************************************/
00801 
00802 slotset *new_slotset(CmiInt8 startslot, CmiInt8 nslots) {
00803   int i;
00804   int list_bin;
00805 
00806   /* CmiPrintf("*** New Isomalloc ***\n"); */
00807 
00808   /* allocate memory for the slotset */
00809   slotset *ss = (slotset *)(malloc(sizeof(slotset)));
00810 
00811   /* allocate memory for the b-tree */
00812   ss->btree_root = create_btree_node();
00813 
00814   /* initialize the b-tree */
00815   ss->btree_root->num_blocks          = 1;
00816   ss->btree_root->blocks[0].startslot = startslot;
00817   ss->btree_root->blocks[0].nslots    = nslots;
00818 
00819   /* initialize the list array */
00820   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
00821     ss->list_array[i] = NULL;
00822   }
00823   list_bin = find_list_bin(nslots);
00824   ss->list_array[list_bin] = (dllnode *)(malloc(sizeof(dllnode)));
00825   ss->list_array[list_bin]->previous = NULL;
00826   ss->list_array[list_bin]->next = NULL;
00827   ss->list_array[list_bin]->sb = &(ss->btree_root->blocks[0]);
00828 
00829   ss->btree_root->blocks[0].listblock = ss->list_array[list_bin];
00830 
00831   return ss;
00832 
00833 }
00834 
00835 /*****************************************************************
00836  * Finds a slotblock containing at least nslots memory slots and
00837  * returns the startslot of that slotblock; returns -1 if no such
00838  * slotblock exists.
00839  *****************************************************************/
00840 
00841 CmiInt8 get_slots(slotset *ss, CmiInt8 nslots) {
00842 
00843   /* calculate the smallest bin (list) to look in first */
00844   int start_list = find_list_bin(nslots);
00845 
00846   /* search for a slotblock with enough slots */
00847   int i;
00848   dllnode *dlln;
00849   for (i = start_list; i < LIST_ARRAY_SIZE; i++) {
00850     dlln = ss->list_array[i];
00851     while (dlln != NULL) {
00852       if (dlln->sb->nslots >= nslots) {
00853     return dlln->sb->startslot;
00854       }
00855       dlln = dlln->next;
00856     }
00857   }
00858 
00859   /* return -1 if no such slotblock exists */
00860   return (-1);
00861 
00862 }
00863 
00864 /*****************************************************************
00865  * Grab a slotblock with the specified range of blocks (nslots blocks
00866  * starting at sslot).  This is different from get_slots because
00867  * grab_slots specifies the slots to be grabbed and actually grabs
00868  * them (removes them from the set of free slots).  get_slots only
00869  * finds a set of free slots.
00870  *****************************************************************/
00871 
00872 void grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
00873 
00874   CmiInt8 endslot;
00875   slotblock *sb = find_btree_slotblock(ss->btree_root, sslot);
00876 
00877   if (sb == NULL) {
00878     CmiAbort("requested a non-existent slotblock\n");
00879   } else {
00880     
00881     if (sb->startslot == sslot) {
00882 
00883       /* range is exact range of slotblock - delete block from tree */
00884       if (sb->nslots == nslots) {
00885     ss->btree_root = btree_delete(ss, ss->btree_root, sslot);
00886       }
00887 
00888       /* range is at beginning of slotblock - update block range */
00889       else {
00890     CmiInt8 old_nslots = sb->nslots;
00891     sb->startslot     += nslots;
00892     sb->nslots        -= nslots;
00893     list_move(ss, sb->listblock, old_nslots);
00894       }
00895 
00896     } else {
00897 
00898       /* range is at end of slotblock - update block range */
00899       endslot = sb->startslot + sb->nslots - 1;
00900       if (endslot == (sslot + nslots - 1)) {
00901     CmiInt8 old_nslots = sb->nslots;
00902     sb->nslots        -= nslots;
00903     list_move(ss, sb->listblock, old_nslots);
00904       }
00905 
00906       /* range is in middle of slotblock - update block range with the */
00907       /* new lower range and insert a block with the new upper range */
00908       else {
00909     CmiInt8 old_nslots = sb->nslots;
00910     sb->nslots         = sslot - sb->startslot;
00911     list_move(ss, sb->listblock, old_nslots);
00912     ss->btree_root = btree_insert(ss, ss->btree_root, sslot + nslots, 
00913                       endslot - (sslot + nslots) + 1);
00914       }
00915 
00916     }
00917 
00918   }
00919 
00920 }
00921 
00922 /*****************************************************************
00923  * Frees nslots memory slots starting at sslot by either adding them
00924  * to one of the slotblocks that exists (if the slot ranges are
00925  * contiguous) or by creating a new slotblock
00926  *****************************************************************/
00927 
00928 void free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
00929 
00930   slotblock *sb_low  = find_btree_slotblock(ss->btree_root, sslot - 1);
00931   slotblock *sb_high = find_btree_slotblock(ss->btree_root, sslot + nslots);
00932 
00933   if (sb_low == NULL) {
00934     if (sb_high == NULL) {
00935 
00936       /* there is no adjacent slotblock, so create a new one and */
00937       /* insert it in the b-tree */
00938       ss->btree_root = btree_insert(ss, ss->btree_root, sslot, nslots);
00939 
00940     } else {
00941 
00942       /* there is an adjacent slotblock to the right, so update its range */
00943       CmiInt8 old_nslots = sb_high->nslots;
00944       sb_high->startslot = sslot;
00945       sb_high->nslots   += nslots;
00946       list_move(ss, sb_high->listblock, old_nslots);
00947 
00948     }
00949   } else {
00950     if (sb_high == NULL) {
00951 
00952       /* there is an adjacent slotblock to the left, so update its range */
00953       CmiInt8 old_nslots  = sb_low->nslots;
00954       sb_low->nslots     += nslots;
00955       list_move(ss, sb_low->listblock, old_nslots);
00956 
00957     } else {
00958 
00959       /* there are adjacent slotblocks on both sides (i.e., the
00960          slots to be freed exactly span the gap between 2 slotblocks),
00961          so update the range of the lower slotblock and delete the
00962          upper one */
00963       CmiInt8 old_nslots = sb_low->nslots;
00964       sb_low->nslots     = sb_low->nslots + nslots + sb_high->nslots;
00965       list_move(ss, sb_low->listblock, old_nslots);
00966       ss->btree_root = btree_delete(ss, ss->btree_root, sb_high->startslot);
00967 
00968     }
00969   }
00970 
00971 }
00972 
00973 /*****************************************************************
00974  * Recursively free the allocated memory of the b-tree
00975  *****************************************************************/
00976 
00977 static void delete_btree(btreenode *node) {
00978   int i;
00979   for (i = 0; i <= node->num_blocks; i++) {
00980     if (node->child[i] != NULL) {
00981       delete_btree(node->child[i]);
00982       free(node->child[i]);
00983     } else {
00984       return;
00985     }
00986   }
00987 }
00988 
00989 /*****************************************************************
00990  * Free the allocated memory of the list array
00991  *****************************************************************/
00992 
00993 static void delete_list_array(slotset *ss) {
00994   int i;
00995   dllnode *dlln;
00996   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
00997     dlln = ss->list_array[i];
00998     if (dlln != NULL) {
00999       while (dlln->next != NULL) {
01000     dlln = dlln->next;
01001       }
01002       while (dlln->previous != NULL) {
01003     dlln = dlln->previous;
01004     free(dlln->next);
01005       }
01006       free(dlln);
01007     }
01008   }
01009 }
01010 
01011 /*****************************************************************
01012  * Free the allocated memory of the slotset
01013  *****************************************************************/
01014 
01015 static void delete_slotset(slotset *ss) {
01016   delete_btree(ss->btree_root);
01017   delete_list_array(ss);
01018   free(ss->btree_root);
01019   free(ss);
01020 }
01021 
01022 /*****************************************************************
01023  * Print the contents of the b-tree on the screen in a top-down
01024  * fashion, starting with the root and progressing to the sub-trees
01025  *****************************************************************/
01026 
01027 /* prints the elements in a single b-tree node */
01028 static void print_btree_node(btreenode *node, int node_num) {
01029   int i;
01030   CmiPrintf("Node %2d: ", node_num);
01031   for (i = 0; i < node->num_blocks; i++) {
01032     CmiPrintf("%d:[%lld,%lld] ", i, node->blocks[i].startslot, node->blocks[i].nslots);
01033   }
01034   CmiPrintf("\n");
01035 }
01036 
01037 /* returns 1 if there's another level to print; 0 if not */
01038 static int print_btree_level(btreenode *node, int level, int current_level, int node_num) {
01039   int i, another_level;
01040   for (i = 0; i <= node->num_blocks; i++) {
01041     if (current_level == level) {
01042       print_btree_node(node, node_num);
01043       if (node->child[0] == NULL) {
01044     return 0;
01045       } else {
01046     return 1;
01047       }
01048     } else {
01049       another_level = print_btree_level(node->child[i], level, 
01050                     current_level + 1, i);
01051     }
01052   }
01053   return another_level;
01054 }
01055 
01056 static void print_btree_top_down(btreenode *node) {
01057   int level = 0;
01058   int another_level;
01059   do {
01060     CmiPrintf("B-tree Level %d\n", level);
01061     CmiPrintf("---------------\n");
01062     another_level = print_btree_level(node, level, 0, 0);
01063     level++;
01064     CmiPrintf("\n\n");
01065   } while (another_level);
01066 }
01067 
01068 /*****************************************************************
01069  * Print the contents of the list arry on the screen
01070  *****************************************************************/
01071 
01072 static void print_list_array(slotset *ss) {
01073   int i;
01074   dllnode *dlln;
01075   CmiPrintf("List Array\n");
01076   CmiPrintf("----------\n");
01077   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
01078     CmiPrintf("List %2d: ", i);
01079     dlln = ss->list_array[i];
01080     while (dlln != NULL) {
01081       if (dlln->previous != NULL) {
01082     CmiPrintf("<->");
01083       } else {
01084     CmiPrintf(" ->");
01085       }
01086       CmiPrintf("[%lld,%lld]", dlln->sb->startslot, dlln->sb->nslots);
01087       dlln = dlln->next;
01088     }
01089     CmiPrintf("\n");
01090   }
01091 }
01092 
01093 #if ISOMALLOC_DEBUG
01094 static void print_slots(slotset *ss) {
01095   print_btree_top_down(ss->btree_root);
01096   print_list_array(ss);
01097 }
01098 #else
01099 #  define print_slots(ss) /*empty*/
01100 #endif
01101 
01102 
01103 #else
01104 
01105 /************************************************************************
01106      array-based memory allocator
01107 ************************************************************************/
01108 
01109 /*
01110  * creates a new slotset of nslots entries, starting with all
01111  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
01112  */
01113 
01114 slotset *
01115 new_slotset(CmiInt8 startslot, CmiInt8 nslots)
01116 {
01117   /* CmiPrintf("*** Old isomalloc ***\n"); */
01118   int i;
01119   slotset *ss = (slotset*) malloc(sizeof(slotset));
01120   _MEMCHECK(ss);
01121   ss->maxbuf = 16;
01122   ss->buf = (slotblock *) malloc(sizeof(slotblock)*ss->maxbuf);
01123   _MEMCHECK(ss->buf);
01124   ss->emptyslots = nslots;
01125   ss->buf[0].startslot = startslot;
01126   ss->buf[0].nslots = nslots;
01127   for (i=1; i<ss->maxbuf; i++)
01128     ss->buf[i].nslots = 0;
01129   return ss;
01130 }
01131 
01132 /*
01133  * returns new block of empty slots. if it cannot find any, returns (-1).
01134  */
01135 
01136 CmiInt8
01137 get_slots(slotset *ss, CmiInt8 nslots)
01138 {
01139   /* CmiPrintf("old get: nslots=%lld\n", nslots); */
01140   int i;
01141   if(ss->emptyslots < nslots)
01142     return (-1);
01143   for(i=0;i<(ss->maxbuf);i++)
01144     if(ss->buf[i].nslots >= nslots)
01145       return ss->buf[i].startslot;
01146   return (-1);
01147 }
01148 
01149 /* just adds a slotblock to an empty position in the given slotset. */
01150 
01151 void
01152 add_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
01153 {
01154   int pos;
01155   int emptypos = -1;
01156   if (nslots == 0)
01157     return;
01158   for (pos=0; pos < (ss->maxbuf); pos++) {
01159     if (ss->buf[pos].nslots == 0) {
01160       emptypos = pos;
01161       break; /* found empty slotblock */
01162     }
01163   }
01164   if (emptypos == (-1)) /*no empty slotblock found */
01165   {
01166     int i;
01167     int newsize = ss->maxbuf*2;
01168     slotblock *newbuf = (slotblock *) malloc(sizeof(slotblock)*newsize);
01169     _MEMCHECK(newbuf);
01170     for (i=0; i<(ss->maxbuf); i++)
01171       newbuf[i] = ss->buf[i];
01172     for (i=ss->maxbuf; i<newsize; i++)
01173       newbuf[i].nslots  = 0;
01174     free(ss->buf);
01175     ss->buf = newbuf;
01176     emptypos = ss->maxbuf;
01177     ss->maxbuf = newsize;
01178   }
01179   ss->buf[emptypos].startslot = sslot;
01180   ss->buf[emptypos].nslots = nslots;
01181   ss->emptyslots += nslots;
01182   return;
01183 }
01184 
01185 /* grab a slotblock with specified range of blocks
01186  * this is different from get_slots, since it pre-specifies the
01187  * slots to be grabbed.
01188  */
01189 void
01190 grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
01191 {
01192   /* CmiPrintf("old grab: sslot=%lld nslots=%lld\n", sslot, nslots); */
01193   CmiInt8 pos, eslot, e;
01194   eslot = sslot + nslots;
01195   for (pos=0; pos < (ss->maxbuf); pos++)
01196   {
01197     if (ss->buf[pos].nslots == 0)
01198       continue;
01199     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
01200     if(sslot >= ss->buf[pos].startslot && eslot <= e)
01201     {
01202       CmiInt8 old_nslots;
01203       old_nslots = ss->buf[pos].nslots;
01204       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
01205       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
01206       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
01207       /* CmiPrintf("grab: sslot=%lld nslots=%lld pos=%lld i=%d\n", sslot, nslots, pos, i); */
01208       return;
01209     }
01210   }
01211   CmiAbort("requested a non-existent slotblock\n");
01212 }
01213 
01214 /*
01215  * Frees slot by adding it to one of the blocks of empty slots.
01216  * this slotblock is one which is contiguous with the slots to be freed.
01217  * if it cannot find such a slotblock, it creates a new slotblock.
01218  * If the buffer fills up, it adds up extra buffer space.
01219  */
01220 void
01221 free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
01222 {
01223   /* CmiPrintf("old free: sslot=%lld nslots=%lld\n", sslot, nslots); */
01224   int pos;
01225   /* eslot is the ending slot of the block to be freed */
01226   CmiInt8 eslot = sslot + nslots;
01227   for (pos=0; pos < (ss->maxbuf); pos++)
01228   {
01229     CmiInt8 e = ss->buf[pos].startslot + ss->buf[pos].nslots;
01230     if (ss->buf[pos].nslots == 0)
01231       continue;
01232     /* e is the ending slot of pos'th slotblock */
01233     if (e == sslot) /* append to the current slotblock */
01234     {
01235             ss->buf[pos].nslots += nslots;
01236             ss->emptyslots += nslots;
01237             /* CmiPrintf("free:append pos=%d\n", pos); */
01238             return;
01239     }
01240     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
01241     {
01242             ss->buf[pos].startslot = sslot;
01243             ss->buf[pos].nslots += nslots;
01244             ss->emptyslots += nslots;
01245             /* CmiPrintf("free:prepend pos=%d\n", pos); */
01246             return;
01247     }
01248   }
01249   /* if we are here, it means we could not find a slotblock that the */
01250   /* block to be freed was combined with. */
01251   /* CmiPrintf("free: pos=%d\n", pos); */
01252   add_slots(ss, sslot, nslots);
01253 }
01254 
01255 
01256 #endif
conv-core/mem-arena.C
