doc: Add serial to list of ci file reserved words
[charm.git] / src / conv-core / mem-arena.c
1
2 #include "converse.h"
3 #include "mem-arena.h"
4
5 #if USE_BTREE
6
7 /* ======================================================================
8  * New (b-tree-based implementation)
9  * ====================================================================== */
10
11
12 /* return value for a b-tree insert */
13 typedef struct _insert_ret_val {
14   slotblock sb;
15   btreenode *btn;
16 } insert_ret_val;
17
18 /*****************************************************************
19  * Find and return the number of the bin (list) to which the number
20  * nslots belongs.  The range of each bin is 2^(b-1)+1 to 2^b, where b
21  * is the bin number.
22  *****************************************************************/
23
24 static int find_list_bin(CmiInt8 nslots) {
25   int list_bin     = 32;
26   CmiInt8 comp_num = 0x100000000LL;
27   int inc          = 16;
28
29   while (1) {
30     if ((nslots > (comp_num >> 1)) && (nslots <= comp_num)) {
31       /* found it */
32       return list_bin;
33     } else if (nslots < comp_num) {
34       /* look left  */
35       list_bin -= inc;
36       comp_num  = comp_num >> inc;
37       if ((inc = inc >> 1) == 0) {
38         inc = 1;
39       }
40     } else {
41       /* look right */
42       list_bin += inc;
43       comp_num  = comp_num << inc;
44       if ((inc = inc >> 1) == 0) {
45         inc = 1;
46       }
47     }
48   }
49
50 }
51
52 /*****************************************************************
53  * Creates and inserts a new dllnode into list_array (part of the
54  * slotset ss) that both points to and is pointed to by the slotblock
55  * sb.  This function also returns a pointer to that new dllnode.
56  *****************************************************************/
57
58 static dllnode *list_insert(slotset *ss, slotblock *sb) {
59
60   /* find the list bin to put the new dllnode in  */
61   int list_bin = find_list_bin(sb->nslots);
62
63   /* allocate memory for the new node */
64   dllnode *new_dlln = (dllnode *)(malloc(sizeof(dllnode)));
65
66   /* insert the dllnode */
67   new_dlln->previous = NULL;
68   new_dlln->next     = ss->list_array[list_bin];
69   new_dlln->sb       = sb;
70   if (ss->list_array[list_bin] != NULL) {
71     ss->list_array[list_bin]->previous = new_dlln;
72   }
73   ss->list_array[list_bin] = new_dlln;
74
75   return new_dlln;
76
77 }
78
79 /*****************************************************************
80  * Deletes the dllnode from list_array (part of the slotset ss) that
81  * is pointed to by the slotblock sb.
82  *****************************************************************/
83
84 static void list_delete(slotset *ss, slotblock *sb) {
85
86   /* remove the node from the list */
87   if (sb->listblock->next != NULL) {
88     sb->listblock->next->previous = sb->listblock->previous;
89   }
90   if (sb->listblock->previous != NULL) {
91     sb->listblock->previous->next = sb->listblock->next;
92   } else {  /* first element in the list */
93     ss->list_array[find_list_bin(sb->nslots)] = sb->listblock->next;
94   }
95
96   /* free the memory from the node */
97   free(sb->listblock);
98
99 }
100
101 /*****************************************************************
102  * Moves the dllnode dlln to the correct bin (list) of slotset ss
103  * based on the number of slots in the slotblock to which dlln points.
104  * It is assumed that the slotblock pointed to by dlln has already been
105  * updated with the new number of slots.  The integer old_nslots
106  * contains the number of slots that used to be in the slotblock.
107  *****************************************************************/
108
109 static void list_move(slotset *ss, dllnode *dlln, CmiInt8 old_nslots) {
110
111   /* determine the bin the slotblock used to be in */
112   int old_bin = find_list_bin(old_nslots);
113
114   /* determine the bin the slotblock is in now */
115   int new_bin = find_list_bin(dlln->sb->nslots);
116
117   /* if the old bin and new bin are different, move the slotblock */
118   if (new_bin != old_bin) {
119
120     /* remove from old bin */
121     if (dlln->previous == NULL) {  /* dlln is the 1st element in the list */
122       if (dlln->next != NULL) {
123         dlln->next->previous = NULL;
124       }
125       ss->list_array[old_bin] = dlln->next;
126     } else {
127       if (dlln->next != NULL) {
128         dlln->next->previous = dlln->previous;
129       }
130       dlln->previous->next = dlln->next;
131     }
132
133     /* insert at the beginning of the new bin */
134     dlln->next     = ss->list_array[new_bin];
135     dlln->previous = NULL;
136     if (dlln->next != NULL) {
137       dlln->next->previous = dlln;
138     }
139     ss->list_array[new_bin] = dlln;
140   }
141
142 }
143
144 /*****************************************************************
145  * Creates a new b-tree node
146  *****************************************************************/
147
148 static btreenode *create_btree_node() {
149   int i;
150   btreenode *btn = (btreenode *)malloc(sizeof(btreenode));
151   btn->num_blocks = 0;
152   for (i = 0; i < TREE_NODE_SIZE; i++) {
153     btn->blocks[i].listblock = NULL;
154   }
155   for (i = 0; i < TREE_NODE_SIZE + 1; i++) {
156     btn->child[i] = NULL;
157   }
158   return btn;
159 }
160
161 /*****************************************************************
162  * Find the slotblock in the b-tree that contains startslot.  Returns
163  * NULL if such a block cannot be found.
164  *****************************************************************/
165
166 static slotblock *find_btree_slotblock(btreenode *node, CmiInt8 startslot) {
167
168   /* check if this node exists */
169   if ((node == NULL) || (startslot < 0) || (node->num_blocks == 0)) {
170     return NULL;
171   } else {
172
173     /*** Binary search on this node ***/
174     /* initialize */
175     int index = node->num_blocks >> 1;
176     int inc   = (index >> 1) + (node->num_blocks & 0x1);
177     CmiInt8 endslot;
178
179     /* loop until a node is found */
180     while (1) {
181
182       /* if startslot is in current slotblock, this is the slotblock */
183       endslot = node->blocks[index].startslot + node->blocks[index].nslots - 1;
184       if ((startslot >= node->blocks[index].startslot) &&
185           (startslot <= endslot)) {
186         return &(node->blocks[index]);
187       }
188
189       /* else, if startslot is less */
190       else if (startslot < node->blocks[index].startslot) {
191
192         /* if this is slotblock 0, take the left child */
193         if (index == 0) {
194           return find_btree_slotblock(node->child[index], startslot);
195         }
196
197         /* else check endslot of the slotblock to the left */
198         else {
199
200           /* if startslot > endslot-of-slotblock-to-the-left, take the
201              left child */
202           endslot = node->blocks[index-1].startslot + 
203             node->blocks[index-1].nslots - 1;
204           if (startslot > endslot) {
205             return find_btree_slotblock(node->child[index], startslot);
206           }
207
208           /* else continue to search this node to the left */
209           else {
210             index -= inc;
211             if ((inc = inc >> 1) == 0) {
212               inc = 1;
213             }
214           }
215         }
216       }
217
218       /* else, startslot must be greater */
219       else {
220
221         /* if this is the last slotblock, take the right child */
222         if (index == node->num_blocks - 1) {
223           return find_btree_slotblock(node->child[index+1], startslot);
224         }
225
226         /* else check startslot of the slotblock to the right */
227         else {
228
229           /* if startslot < startslot-of-slotblock-to-the-right, then
230              take the right child */
231           if (startslot < node->blocks[index+1].startslot) {
232             return find_btree_slotblock(node->child[index+1], startslot);
233           }
234
235           /* else continue to search this node to the right */
236           else {
237             index += inc;
238             if ((inc = inc >> 1) == 0) {
239               inc = 1;
240             }
241           }
242         }
243       }
244       
245     }
246
247   }
248
249 }
250
251 /*****************************************************************
252  * Insert a slotblock into the b-tree starting at startslot and going
253  * for nslots slots
254  *****************************************************************/
255
256 static insert_ret_val btree_insert_int(slotset *ss, btreenode *node, 
257                                        CmiInt8 startslot, CmiInt8 nslots) {
258
259   insert_ret_val irv;
260
261   /*** binary search for the place to insert ***/
262
263   /* initialize */
264   int index = node->num_blocks >> 1;
265   int inc   = (index >> 1) + (node->num_blocks & 0x1);
266
267   /* loop until an insertion happens */
268   while (1) {
269     if (startslot < node->blocks[index].startslot) {  /* look to the left */
270       if ((index == 0) || 
271           (startslot > node->blocks[index-1].startslot)) {
272         if (node->child[index] != NULL) {             /* take left child */
273           irv = btree_insert_int(ss, node->child[index], startslot, nslots);
274           if (irv.btn == NULL) {
275             return irv;
276           } else {                                    /* merge return value */
277             int i, j;                                 /*   insert on left   */
278             for (i = node->num_blocks; i > index; i--) {
279               node->blocks[i].startslot     = node->blocks[i-1].startslot;
280               node->blocks[i].nslots        = node->blocks[i-1].nslots;
281               node->blocks[i].listblock     = node->blocks[i-1].listblock;
282               node->blocks[i].listblock->sb = &(node->blocks[i]);
283               node->child[i+1]              = node->child[i];
284             }
285             node->blocks[index].startslot     = irv.sb.startslot;
286             node->blocks[index].nslots        = irv.sb.nslots;
287             node->blocks[index].listblock     = irv.sb.listblock;
288             node->blocks[index].listblock->sb = &(node->blocks[index]);
289             node->child[index+1]              = irv.btn;
290             node->num_blocks++;
291             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
292               btreenode *new_node = create_btree_node();
293               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
294                 j = i - (TREE_NODE_MID + 1);
295                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
296                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
297                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
298                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
299               }
300               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
301                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
302               }
303               node->num_blocks     = TREE_NODE_MID;
304               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
305
306               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
307               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
308               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
309               irv.btn          = new_node;
310               return irv;
311             } else {
312               irv.btn = NULL;
313               return irv;
314             }
315           }
316         } else {                                      /* insert to the left */
317           int i, j;
318           for (i = node->num_blocks; i > index; i--) {
319             node->blocks[i].startslot     = node->blocks[i-1].startslot;
320             node->blocks[i].nslots        = node->blocks[i-1].nslots;
321             node->blocks[i].listblock     = node->blocks[i-1].listblock;
322             node->blocks[i].listblock->sb = &(node->blocks[i]);
323           }
324           node->blocks[index].startslot = startslot;
325           node->blocks[index].nslots    = nslots;
326           node->blocks[index].listblock = list_insert(ss, &(node->blocks[index]));
327           node->num_blocks++;
328           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
329             btreenode *new_node = create_btree_node();
330             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
331               j = i - (TREE_NODE_MID + 1);
332               new_node->blocks[j].startslot     = node->blocks[i].startslot;
333               new_node->blocks[j].nslots        = node->blocks[i].nslots;
334               new_node->blocks[j].listblock     = node->blocks[i].listblock;
335               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
336             }
337             node->num_blocks     = TREE_NODE_MID;
338             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
339
340             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
341             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
342             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
343             irv.btn          = new_node;
344             return irv;
345           } else {
346             irv.btn = NULL;
347             return irv;
348           }
349         }
350       } else {                                        /* search to the left */
351         index -= inc;
352         if ((inc = inc >> 1) == 0) {
353           inc = 1;
354         }
355       }
356
357     } else {                                          /* look to the right */
358
359       if ((index == node->num_blocks - 1) || 
360           (startslot < node->blocks[index+1].startslot)) {
361         if (node->child[index+1] != NULL) {           /* take right child */
362           irv = btree_insert_int(ss, node->child[index+1], startslot, nslots);
363           if (irv.btn == NULL) {
364             return irv;
365           } else {                                    /* merge return value */
366             int i, j;                                 /*   insert on right  */
367             for (i = node->num_blocks; i > index + 1; i--) {
368               node->blocks[i].startslot     = node->blocks[i-1].startslot;
369               node->blocks[i].nslots        = node->blocks[i-1].nslots;
370               node->blocks[i].listblock     = node->blocks[i-1].listblock;
371               node->blocks[i].listblock->sb = &(node->blocks[i]);
372               node->child[i+1]              = node->child[i];
373             }
374             node->blocks[index+1].startslot     = irv.sb.startslot;
375             node->blocks[index+1].nslots        = irv.sb.nslots;
376             node->blocks[index+1].listblock     = irv.sb.listblock;
377             node->blocks[index+1].listblock->sb = &(node->blocks[index+1]);
378             node->child[index+2]                = irv.btn;
379             node->num_blocks++;
380             if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
381               btreenode *new_node = create_btree_node();
382               for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
383                 j = i - (TREE_NODE_MID + 1);
384                 new_node->blocks[j].startslot     = node->blocks[i].startslot;
385                 new_node->blocks[j].nslots        = node->blocks[i].nslots;
386                 new_node->blocks[j].listblock     = node->blocks[i].listblock;
387                 new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
388               }
389               for (i = TREE_NODE_MID + 1; i <= TREE_NODE_SIZE; i++) {
390                 new_node->child[i-(TREE_NODE_MID+1)] = node->child[i];
391               }
392               node->num_blocks     = TREE_NODE_MID;
393               new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
394
395               irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
396               irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
397               irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
398               irv.btn          = new_node;
399               return irv;
400             } else {
401               irv.btn = NULL;
402               return irv;
403             }
404           }
405         } else {                                      /* insert to the right */
406           int i, j;
407           for (i = node->num_blocks; i > index + 1; i--) {
408             node->blocks[i].startslot     = node->blocks[i-1].startslot;
409             node->blocks[i].nslots        = node->blocks[i-1].nslots;
410             node->blocks[i].listblock     = node->blocks[i-1].listblock;
411             node->blocks[i].listblock->sb = &(node->blocks[i]);
412           }
413           node->blocks[index+1].startslot = startslot;
414           node->blocks[index+1].nslots    = nslots;
415           node->blocks[index+1].listblock = list_insert(ss, &(node->blocks[index+1]));
416           node->num_blocks++;
417           if (node->num_blocks == TREE_NODE_SIZE) {   /* split node */
418             btreenode *new_node = create_btree_node();
419             for (i = TREE_NODE_MID + 1; i < TREE_NODE_SIZE; i++) {
420               j = i - (TREE_NODE_MID + 1);
421               new_node->blocks[j].startslot     = node->blocks[i].startslot;
422               new_node->blocks[j].nslots        = node->blocks[i].nslots;
423               new_node->blocks[j].listblock     = node->blocks[i].listblock;
424               new_node->blocks[j].listblock->sb = &(new_node->blocks[j]);
425             }
426             node->num_blocks = TREE_NODE_MID;
427             new_node->num_blocks = TREE_NODE_SIZE - TREE_NODE_MID - 1;
428
429             irv.sb.startslot = node->blocks[TREE_NODE_MID].startslot;
430             irv.sb.nslots    = node->blocks[TREE_NODE_MID].nslots;
431             irv.sb.listblock = node->blocks[TREE_NODE_MID].listblock;
432             irv.btn          = new_node;
433             return irv;
434           } else {
435             irv.btn = NULL;
436             return irv;
437           }
438         }
439       } else {                                        /* search to the right */
440         index += inc;
441         if ((inc = inc >> 1) == 0) {
442           inc = 1;
443         }
444       }
445     }
446   }
447
448 }
449
450 static btreenode *btree_insert(slotset *ss, btreenode *node, 
451                                CmiInt8 startslot, CmiInt8 nslots) {
452
453   /* check the b-tree root: if it's empty, insert the element in the
454      first position */
455   if (node->num_blocks == 0) {
456
457     node->num_blocks          = 1;
458     node->blocks[0].startslot = startslot;
459     node->blocks[0].nslots    = nslots;
460     node->blocks[0].listblock = list_insert(ss, &(node->blocks[0]));
461
462   } else {
463
464     /* insert into the b-tree */
465     insert_ret_val irv = btree_insert_int(ss, node, startslot, nslots);
466
467     /* if something was returned, we need a new root */
468     if (irv.btn != NULL) {
469       btreenode *new_root  = create_btree_node();
470       new_root->num_blocks = 1;
471       new_root->blocks[0].startslot     = irv.sb.startslot;
472       new_root->blocks[0].nslots        = irv.sb.nslots;
473       new_root->blocks[0].listblock     = irv.sb.listblock;
474       new_root->blocks[0].listblock->sb = &(new_root->blocks[0]);
475       new_root->child[0] = node;
476       new_root->child[1] = irv.btn;
477       node = new_root;
478     }
479
480   }
481
482   return node;
483
484 }
485
486 /*****************************************************************
487  * Delete the slotblock from the b-tree starting at startslot
488  *****************************************************************/
489
490 static void btree_delete_int(slotset *ss, btreenode *node, 
491                              CmiInt8 startslot, slotblock *sb) {
492
493   int index, inc;
494   int i;
495
496   /* If sb is not NULL, we're sending sb down the tree to a leaf to be
497      swapped with the next larger startslot so it can be deleted from
498      a leaf node (deletions from non-leaf nodes are not allowed
499      here).  At this point, the next larger startslot will always be
500      found by taking the leftmost child.  */
501   if (sb != NULL) {
502
503     if (node->child[0] != NULL) {
504       btree_delete_int(ss, node->child[0], startslot, sb);
505       index = 0;
506
507     } else {
508
509       /* we're now at a leaf node, so the slotblock can be deleted
510
511          first, copy slotblock 0 to the block passed down (sb) and
512          delete the list array node  */
513       list_delete(ss, sb);
514       sb->startslot     = node->blocks[0].startslot;
515       sb->nslots        = node->blocks[0].nslots;
516       sb->listblock     = node->blocks[0].listblock;
517       sb->listblock->sb = sb;
518
519       /* delete the slotblock */
520       for (i = 0; i < (node->num_blocks - 1); i++) {
521         node->blocks[i].startslot     = node->blocks[i+1].startslot;
522         node->blocks[i].nslots        = node->blocks[i+1].nslots;
523         node->blocks[i].listblock     = node->blocks[i+1].listblock;
524         node->blocks[i].listblock->sb = &(node->blocks[i]);
525       }
526       node->num_blocks--;
527
528       return;
529
530     }
531
532   } else {
533
534     /*** Binary search for the slotblock to delete ***/
535
536     /* initialize */
537     index = node->num_blocks >> 1;
538     inc = (index >> 1) + (node->num_blocks & 0x1);
539
540     /* loop until the slotblock with startslot is found */
541     while (1) {
542
543       if (startslot == node->blocks[index].startslot) {   /* found it */
544         if (node->child[index+1] != NULL) {               /* not a leaf */
545           btree_delete_int(ss, node->child[index+1], 
546                            startslot, &(node->blocks[index]));
547           break;
548         } else {                                          /* is a leaf */
549           int i;
550           /* delete the slotblock */
551           list_delete(ss, &(node->blocks[index]));
552           for (i = index; i < (node->num_blocks - 1); i++) {
553             node->blocks[i].startslot     = node->blocks[i+1].startslot;
554             node->blocks[i].nslots        = node->blocks[i+1].nslots;
555             node->blocks[i].listblock     = node->blocks[i+1].listblock;
556             node->blocks[i].listblock->sb = &(node->blocks[i]);
557           }
558           node->num_blocks--;
559           return;
560         }
561       } else {
562         if (startslot < node->blocks[index].startslot) {  /* look left */
563           if ((index == 0) ||                             /* take left child */
564               (startslot > node->blocks[index-1].startslot)) {
565             btree_delete_int(ss, node->child[index], startslot, sb);
566             break;
567           } else {                                        /* search left */
568             index -= inc;
569             if ((inc = inc >> 1) == 0) {
570               inc = 1;
571             }
572           }
573         } else {                                          /* look right */
574           if ((index == node->num_blocks - 1) ||          /* take right child */
575               (startslot < node->blocks[index+1].startslot)) {
576             btree_delete_int(ss, node->child[index+1], startslot, sb);
577             break;
578           } else {                                        /* search right */
579             index += inc;
580             if ((inc = inc >> 1) == 0) {
581               inc = 1;
582             }
583           }
584         }
585       }
586
587     }
588
589   }
590
591   {   /* BLOCK
592      At this point, the desired slotblock has been removed, and we're
593      going back up the tree.  We must check for deficient nodes that
594      require the rotating or combining of elements to maintain a
595      balanced b-tree. */
596   int i;
597   int def_child = -1;
598
599   /* check if one of the child nodes is deficient  */
600   if (node->child[index]->num_blocks < TREE_NODE_MID) {
601     def_child = index;
602   } else if (node->child[index+1]->num_blocks < TREE_NODE_MID) {
603     def_child = index + 1;
604   }
605
606   if (def_child >= 0) {
607
608     /* if there is a left sibling and it has enough elements, rotate */
609     /* to the right */
610     if ((def_child != 0) && (node->child[def_child-1] != NULL) && 
611         (node->child[def_child-1]->num_blocks > TREE_NODE_MID)) {
612
613       /* move all elements in deficient child to the right */
614       for (i = node->child[def_child]->num_blocks; i > 0; i--) {
615         node->child[def_child]->blocks[i].startslot = 
616           node->child[def_child]->blocks[i-1].startslot;
617         node->child[def_child]->blocks[i].nslots = 
618           node->child[def_child]->blocks[i-1].nslots;
619         node->child[def_child]->blocks[i].listblock = 
620           node->child[def_child]->blocks[i-1].listblock;
621         node->child[def_child]->blocks[i].listblock->sb = 
622           &(node->child[def_child]->blocks[i]);
623       }
624       for (i = node->child[def_child]->num_blocks + 1; i > 0; i--) {
625         node->child[def_child]->child[i] = 
626           node->child[def_child]->child[i-1];
627       }
628
629       /* move parent element to the deficient child */
630       node->child[def_child]->blocks[0].startslot = 
631         node->blocks[def_child-1].startslot;
632       node->child[def_child]->blocks[0].nslots = 
633         node->blocks[def_child-1].nslots;
634       node->child[def_child]->blocks[0].listblock = 
635         node->blocks[def_child-1].listblock;
636       node->child[def_child]->blocks[0].listblock->sb = 
637         &(node->child[def_child]->blocks[0]);
638       node->child[def_child]->num_blocks++;
639
640       /* move the right-most child of the parent's left child to the
641          left-most child of the formerly deficient child  */
642       i = node->child[def_child-1]->num_blocks;
643       node->child[def_child]->child[0] = 
644         node->child[def_child-1]->child[i];
645
646       /* move largest element from left child up to the parent */
647       i--;
648       node->blocks[def_child-1].startslot = 
649         node->child[def_child-1]->blocks[i].startslot;
650       node->blocks[def_child-1].nslots = 
651         node->child[def_child-1]->blocks[i].nslots;
652       node->blocks[def_child-1].listblock = 
653         node->child[def_child-1]->blocks[i].listblock;
654       node->blocks[def_child-1].listblock->sb = 
655         &(node->blocks[def_child-1]);
656       node->child[def_child-1]->num_blocks--;
657
658     }
659
660     /* otherwise, if there is a right sibling and it has enough */
661     /* elements, rotate to the left */
662     else if (((def_child + 1) <= node->num_blocks) && 
663              (node->child[def_child+1] != NULL) && 
664              (node->child[def_child+1]->num_blocks > TREE_NODE_MID)) {
665
666       /* move parent element to the deficient child */
667       i = node->child[def_child]->num_blocks;
668       node->child[def_child]->blocks[i].startslot = 
669         node->blocks[def_child].startslot;
670       node->child[def_child]->blocks[i].nslots = 
671         node->blocks[def_child].nslots;
672       node->child[def_child]->blocks[i].listblock = 
673         node->blocks[def_child].listblock;
674       node->child[def_child]->blocks[i].listblock->sb = 
675         &(node->child[def_child]->blocks[i]);
676       node->child[def_child]->num_blocks++;
677
678       /* move the left-most child of the parent's right child to the
679          right-most child of the formerly deficient child  */
680       i++;
681       node->child[def_child]->child[i] = 
682         node->child[def_child+1]->child[0];
683
684       /* move smallest element from right child up to the parent */
685       node->blocks[def_child].startslot = 
686         node->child[def_child+1]->blocks[0].startslot;
687       node->blocks[def_child].nslots = 
688         node->child[def_child+1]->blocks[0].nslots;
689       node->blocks[def_child].listblock = 
690         node->child[def_child+1]->blocks[0].listblock;
691       node->blocks[def_child].listblock->sb = 
692         &(node->blocks[def_child]);
693       node->child[def_child+1]->num_blocks--;
694
695       /* move all elements in the parent's right child to the left  */
696       for (i = 0; i < node->child[def_child+1]->num_blocks; i++) {
697         node->child[def_child+1]->blocks[i].startslot = 
698           node->child[def_child+1]->blocks[i+1].startslot;
699         node->child[def_child+1]->blocks[i].nslots = 
700           node->child[def_child+1]->blocks[i+1].nslots;
701         node->child[def_child+1]->blocks[i].listblock = 
702           node->child[def_child+1]->blocks[i+1].listblock;
703         node->child[def_child+1]->blocks[i].listblock->sb = 
704           &(node->child[def_child+1]->blocks[i]);
705       }
706       for (i = 0; i < node->child[def_child+1]->num_blocks + 1; i++) {
707         node->child[def_child+1]->child[i] = 
708           node->child[def_child+1]->child[i+1];
709       }
710     }    /* BLOCK */
711     }
712
713     /* otherwise, merge the deficient node, parent, and the parent's
714        other child (one of the deficient node's siblings) by dropping
715        the parent down to the level of the children */
716     else {
717
718       /* move the parent element into the left child node */
719       i = node->child[index]->num_blocks;
720       node->child[index]->blocks[i].startslot = 
721         node->blocks[index].startslot;
722       node->child[index]->blocks[i].nslots = 
723         node->blocks[index].nslots;
724       node->child[index]->blocks[i].listblock = 
725         node->blocks[index].listblock;
726       node->child[index]->blocks[i].listblock->sb = 
727         &(node->child[index]->blocks[i]);
728       node->child[index]->num_blocks++;
729
730       {   /* BLOCK */
731       /* move the elements and children of the right child node to the */
732       /* left child node */
733       int num_left  = node->child[index]->num_blocks;
734       int num_right = node->child[index+1]->num_blocks;
735       int left_pos;
736       int right_pos = 0;
737       for (left_pos = num_left; left_pos < num_left + num_right; left_pos++) {
738         node->child[index]->blocks[left_pos].startslot = 
739           node->child[index+1]->blocks[right_pos].startslot;
740         node->child[index]->blocks[left_pos].nslots = 
741           node->child[index+1]->blocks[right_pos].nslots;
742         node->child[index]->blocks[left_pos].listblock = 
743           node->child[index+1]->blocks[right_pos].listblock;
744         node->child[index]->blocks[left_pos].listblock->sb = 
745           &(node->child[index]->blocks[left_pos]);
746         right_pos++;
747       }
748       right_pos = 0;
749       for (left_pos = num_left; left_pos < num_left + num_right + 1; left_pos++) {
750         node->child[index]->child[left_pos] = 
751           node->child[index+1]->child[right_pos];
752         right_pos++;
753       }
754       node->child[index]->num_blocks = num_left + num_right;
755
756       /* delete the right child node */
757       free(node->child[index+1]);
758       node->child[index+1] = NULL;
759
760       /* update the parent node */
761       node->num_blocks--;
762       for (i = index; i < node->num_blocks; i++) {
763         node->blocks[i].startslot     = node->blocks[i+1].startslot;
764         node->blocks[i].nslots        = node->blocks[i+1].nslots;
765         node->blocks[i].listblock     = node->blocks[i+1].listblock;
766         node->blocks[i].listblock->sb = &(node->blocks[i]);
767         node->child[i+1]              = node->child[i+2];
768       }
769       }  /* BLOCK */
770     }
771
772   }
773
774 }
775
776 static btreenode *btree_delete(slotset *ss, btreenode *node, CmiInt8 startslot) {
777
778   /* delete element from the b-tree */
779   btree_delete_int(ss, node, startslot, NULL);
780
781   /* if the root node is empty (from a combine operation on the tree),
782      the left-most child of the root becomes the new root, unless the
783      left-most child is NULL, in which case we leave the root node
784      empty but not NULL */
785   if (node->num_blocks == 0) {
786     if (node->child[0] != NULL) {
787       btreenode *new_root = node->child[0];
788       free(node);
789       node = new_root;
790     }
791   }
792
793   return node;
794
795 }
796
797 /*****************************************************************
798  * Creates a new slotset with nslots entries, starting with all empty
799  * slots.  The slot numbers are [startslot, startslot + nslots - 1].
800  *****************************************************************/
801
802 slotset *new_slotset(CmiInt8 startslot, CmiInt8 nslots) {
803   int i;
804   int list_bin;
805
806   /* CmiPrintf("*** New Isomalloc ***\n"); */
807
808   /* allocate memory for the slotset */
809   slotset *ss = (slotset *)(malloc(sizeof(slotset)));
810
811   /* allocate memory for the b-tree */
812   ss->btree_root = create_btree_node();
813
814   /* initialize the b-tree */
815   ss->btree_root->num_blocks          = 1;
816   ss->btree_root->blocks[0].startslot = startslot;
817   ss->btree_root->blocks[0].nslots    = nslots;
818
819   /* initialize the list array */
820   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
821     ss->list_array[i] = NULL;
822   }
823   list_bin = find_list_bin(nslots);
824   ss->list_array[list_bin] = (dllnode *)(malloc(sizeof(dllnode)));
825   ss->list_array[list_bin]->previous = NULL;
826   ss->list_array[list_bin]->next = NULL;
827   ss->list_array[list_bin]->sb = &(ss->btree_root->blocks[0]);
828
829   ss->btree_root->blocks[0].listblock = ss->list_array[list_bin];
830
831   return ss;
832
833 }
834
835 /*****************************************************************
836  * Finds a slotblock containing at least nslots memory slots and
837  * returns the startslot of that slotblock; returns -1 if no such
838  * slotblock exists.
839  *****************************************************************/
840
841 CmiInt8 get_slots(slotset *ss, CmiInt8 nslots) {
842
843   /* calculate the smallest bin (list) to look in first */
844   int start_list = find_list_bin(nslots);
845
846   /* search for a slotblock with enough slots */
847   int i;
848   dllnode *dlln;
849   for (i = start_list; i < LIST_ARRAY_SIZE; i++) {
850     dlln = ss->list_array[i];
851     while (dlln != NULL) {
852       if (dlln->sb->nslots >= nslots) {
853         return dlln->sb->startslot;
854       }
855       dlln = dlln->next;
856     }
857   }
858
859   /* return -1 if no such slotblock exists */
860   return (-1);
861
862 }
863
864 /*****************************************************************
865  * Grab a slotblock with the specified range of blocks (nslots blocks
866  * starting at sslot).  This is different from get_slots because
867  * grab_slots specifies the slots to be grabbed and actually grabs
868  * them (removes them from the set of free slots).  get_slots only
869  * finds a set of free slots.
870  *****************************************************************/
871
872 void grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
873
874   CmiInt8 endslot;
875   slotblock *sb = find_btree_slotblock(ss->btree_root, sslot);
876
877   if (sb == NULL) {
878     CmiAbort("requested a non-existent slotblock\n");
879   } else {
880     
881     if (sb->startslot == sslot) {
882
883       /* range is exact range of slotblock - delete block from tree */
884       if (sb->nslots == nslots) {
885         ss->btree_root = btree_delete(ss, ss->btree_root, sslot);
886       }
887
888       /* range is at beginning of slotblock - update block range */
889       else {
890         CmiInt8 old_nslots = sb->nslots;
891         sb->startslot     += nslots;
892         sb->nslots        -= nslots;
893         list_move(ss, sb->listblock, old_nslots);
894       }
895
896     } else {
897
898       /* range is at end of slotblock - update block range */
899       endslot = sb->startslot + sb->nslots - 1;
900       if (endslot == (sslot + nslots - 1)) {
901         CmiInt8 old_nslots = sb->nslots;
902         sb->nslots        -= nslots;
903         list_move(ss, sb->listblock, old_nslots);
904       }
905
906       /* range is in middle of slotblock - update block range with the */
907       /* new lower range and insert a block with the new upper range */
908       else {
909         CmiInt8 old_nslots = sb->nslots;
910         sb->nslots         = sslot - sb->startslot;
911         list_move(ss, sb->listblock, old_nslots);
912         ss->btree_root = btree_insert(ss, ss->btree_root, sslot + nslots, 
913                                       endslot - (sslot + nslots) + 1);
914       }
915
916     }
917
918   }
919
920 }
921
922 /*****************************************************************
923  * Frees nslots memory slots starting at sslot by either adding them
924  * to one of the slotblocks that exists (if the slot ranges are
925  * contiguous) or by creating a new slotblock
926  *****************************************************************/
927
928 void free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots) {
929
930   slotblock *sb_low  = find_btree_slotblock(ss->btree_root, sslot - 1);
931   slotblock *sb_high = find_btree_slotblock(ss->btree_root, sslot + nslots);
932
933   if (sb_low == NULL) {
934     if (sb_high == NULL) {
935
936       /* there is no adjacent slotblock, so create a new one and */
937       /* insert it in the b-tree */
938       ss->btree_root = btree_insert(ss, ss->btree_root, sslot, nslots);
939
940     } else {
941
942       /* there is an adjacent slotblock to the right, so update its range */
943       CmiInt8 old_nslots = sb_high->nslots;
944       sb_high->startslot = sslot;
945       sb_high->nslots   += nslots;
946       list_move(ss, sb_high->listblock, old_nslots);
947
948     }
949   } else {
950     if (sb_high == NULL) {
951
952       /* there is an adjacent slotblock to the left, so update its range */
953       CmiInt8 old_nslots  = sb_low->nslots;
954       sb_low->nslots     += nslots;
955       list_move(ss, sb_low->listblock, old_nslots);
956
957     } else {
958
959       /* there are adjacent slotblocks on both sides (i.e., the
960          slots to be freed exactly span the gap between 2 slotblocks),
961          so update the range of the lower slotblock and delete the
962          upper one */
963       CmiInt8 old_nslots = sb_low->nslots;
964       sb_low->nslots     = sb_low->nslots + nslots + sb_high->nslots;
965       list_move(ss, sb_low->listblock, old_nslots);
966       ss->btree_root = btree_delete(ss, ss->btree_root, sb_high->startslot);
967
968     }
969   }
970
971 }
972
973 /*****************************************************************
974  * Recursively free the allocated memory of the b-tree
975  *****************************************************************/
976
977 static void delete_btree(btreenode *node) {
978   int i;
979   for (i = 0; i <= node->num_blocks; i++) {
980     if (node->child[i] != NULL) {
981       delete_btree(node->child[i]);
982       free(node->child[i]);
983     } else {
984       return;
985     }
986   }
987 }
988
989 /*****************************************************************
990  * Free the allocated memory of the list array
991  *****************************************************************/
992
993 static void delete_list_array(slotset *ss) {
994   int i;
995   dllnode *dlln;
996   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
997     dlln = ss->list_array[i];
998     if (dlln != NULL) {
999       while (dlln->next != NULL) {
1000         dlln = dlln->next;
1001       }
1002       while (dlln->previous != NULL) {
1003         dlln = dlln->previous;
1004         free(dlln->next);
1005       }
1006       free(dlln);
1007     }
1008   }
1009 }
1010
1011 /*****************************************************************
1012  * Free the allocated memory of the slotset
1013  *****************************************************************/
1014
1015 static void delete_slotset(slotset *ss) {
1016   delete_btree(ss->btree_root);
1017   delete_list_array(ss);
1018   free(ss->btree_root);
1019   free(ss);
1020 }
1021
1022 /*****************************************************************
1023  * Print the contents of the b-tree on the screen in a top-down
1024  * fashion, starting with the root and progressing to the sub-trees
1025  *****************************************************************/
1026
1027 /* prints the elements in a single b-tree node */
1028 static void print_btree_node(btreenode *node, int node_num) {
1029   int i;
1030   CmiPrintf("Node %2d: ", node_num);
1031   for (i = 0; i < node->num_blocks; i++) {
1032     CmiPrintf("%d:[%lld,%lld] ", i, node->blocks[i].startslot, node->blocks[i].nslots);
1033   }
1034   CmiPrintf("\n");
1035 }
1036
1037 /* returns 1 if there's another level to print; 0 if not */
1038 static int print_btree_level(btreenode *node, int level, int current_level, int node_num) {
1039   int i, another_level;
1040   for (i = 0; i <= node->num_blocks; i++) {
1041     if (current_level == level) {
1042       print_btree_node(node, node_num);
1043       if (node->child[0] == NULL) {
1044         return 0;
1045       } else {
1046         return 1;
1047       }
1048     } else {
1049       another_level = print_btree_level(node->child[i], level, 
1050                                         current_level + 1, i);
1051     }
1052   }
1053   return another_level;
1054 }
1055
1056 static void print_btree_top_down(btreenode *node) {
1057   int level = 0;
1058   int another_level;
1059   do {
1060     CmiPrintf("B-tree Level %d\n", level);
1061     CmiPrintf("---------------\n");
1062     another_level = print_btree_level(node, level, 0, 0);
1063     level++;
1064     CmiPrintf("\n\n");
1065   } while (another_level);
1066 }
1067
1068 /*****************************************************************
1069  * Print the contents of the list arry on the screen
1070  *****************************************************************/
1071
1072 static void print_list_array(slotset *ss) {
1073   int i;
1074   dllnode *dlln;
1075   CmiPrintf("List Array\n");
1076   CmiPrintf("----------\n");
1077   for (i = 0; i < LIST_ARRAY_SIZE; i++) {
1078     CmiPrintf("List %2d: ", i);
1079     dlln = ss->list_array[i];
1080     while (dlln != NULL) {
1081       if (dlln->previous != NULL) {
1082         CmiPrintf("<->");
1083       } else {
1084         CmiPrintf(" ->");
1085       }
1086       CmiPrintf("[%lld,%lld]", dlln->sb->startslot, dlln->sb->nslots);
1087       dlln = dlln->next;
1088     }
1089     CmiPrintf("\n");
1090   }
1091 }
1092
1093 #if ISOMALLOC_DEBUG
1094 static void print_slots(slotset *ss) {
1095   print_btree_top_down(ss->btree_root);
1096   print_list_array(ss);
1097 }
1098 #else
1099 #  define print_slots(ss) /*empty*/
1100 #endif
1101
1102
1103 #else
1104
1105 /************************************************************************
1106      array-based memory allocator
1107 ************************************************************************/
1108
1109 /*
1110  * creates a new slotset of nslots entries, starting with all
1111  * empty slots. The slot numbers are [startslot,startslot+nslot-1]
1112  */
1113
1114 slotset *
1115 new_slotset(CmiInt8 startslot, CmiInt8 nslots)
1116 {
1117   /* CmiPrintf("*** Old isomalloc ***\n"); */
1118   int i;
1119   slotset *ss = (slotset*) malloc(sizeof(slotset));
1120   _MEMCHECK(ss);
1121   ss->maxbuf = 16;
1122   ss->buf = (slotblock *) malloc(sizeof(slotblock)*ss->maxbuf);
1123   _MEMCHECK(ss->buf);
1124   ss->emptyslots = nslots;
1125   ss->buf[0].startslot = startslot;
1126   ss->buf[0].nslots = nslots;
1127   for (i=1; i<ss->maxbuf; i++)
1128     ss->buf[i].nslots = 0;
1129   return ss;
1130 }
1131
1132 /*
1133  * returns new block of empty slots. if it cannot find any, returns (-1).
1134  */
1135
1136 CmiInt8
1137 get_slots(slotset *ss, CmiInt8 nslots)
1138 {
1139   /* CmiPrintf("old get: nslots=%lld\n", nslots); */
1140   int i;
1141   if(ss->emptyslots < nslots)
1142     return (-1);
1143   for(i=0;i<(ss->maxbuf);i++)
1144     if(ss->buf[i].nslots >= nslots)
1145       return ss->buf[i].startslot;
1146   return (-1);
1147 }
1148
1149 /* just adds a slotblock to an empty position in the given slotset. */
1150
1151 void
1152 add_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1153 {
1154   int pos;
1155   int emptypos = -1;
1156   if (nslots == 0)
1157     return;
1158   for (pos=0; pos < (ss->maxbuf); pos++) {
1159     if (ss->buf[pos].nslots == 0) {
1160       emptypos = pos;
1161       break; /* found empty slotblock */
1162     }
1163   }
1164   if (emptypos == (-1)) /*no empty slotblock found */
1165   {
1166     int i;
1167     int newsize = ss->maxbuf*2;
1168     slotblock *newbuf = (slotblock *) malloc(sizeof(slotblock)*newsize);
1169     _MEMCHECK(newbuf);
1170     for (i=0; i<(ss->maxbuf); i++)
1171       newbuf[i] = ss->buf[i];
1172     for (i=ss->maxbuf; i<newsize; i++)
1173       newbuf[i].nslots  = 0;
1174     free(ss->buf);
1175     ss->buf = newbuf;
1176     emptypos = ss->maxbuf;
1177     ss->maxbuf = newsize;
1178   }
1179   ss->buf[emptypos].startslot = sslot;
1180   ss->buf[emptypos].nslots = nslots;
1181   ss->emptyslots += nslots;
1182   return;
1183 }
1184
1185 /* grab a slotblock with specified range of blocks
1186  * this is different from get_slots, since it pre-specifies the
1187  * slots to be grabbed.
1188  */
1189 void
1190 grab_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1191 {
1192   /* CmiPrintf("old grab: sslot=%lld nslots=%lld\n", sslot, nslots); */
1193   CmiInt8 pos, eslot, e;
1194   eslot = sslot + nslots;
1195   for (pos=0; pos < (ss->maxbuf); pos++)
1196   {
1197     if (ss->buf[pos].nslots == 0)
1198       continue;
1199     e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1200     if(sslot >= ss->buf[pos].startslot && eslot <= e)
1201     {
1202       CmiInt8 old_nslots;
1203       old_nslots = ss->buf[pos].nslots;
1204       ss->buf[pos].nslots = sslot - ss->buf[pos].startslot;
1205       ss->emptyslots -= (old_nslots - ss->buf[pos].nslots);
1206       add_slots(ss, sslot + nslots, old_nslots - ss->buf[pos].nslots - nslots);
1207       /* CmiPrintf("grab: sslot=%lld nslots=%lld pos=%lld i=%d\n", sslot, nslots, pos, i); */
1208       return;
1209     }
1210   }
1211   CmiAbort("requested a non-existent slotblock\n");
1212 }
1213
1214 /*
1215  * Frees slot by adding it to one of the blocks of empty slots.
1216  * this slotblock is one which is contiguous with the slots to be freed.
1217  * if it cannot find such a slotblock, it creates a new slotblock.
1218  * If the buffer fills up, it adds up extra buffer space.
1219  */
1220 void
1221 free_slots(slotset *ss, CmiInt8 sslot, CmiInt8 nslots)
1222 {
1223   /* CmiPrintf("old free: sslot=%lld nslots=%lld\n", sslot, nslots); */
1224   int pos;
1225   /* eslot is the ending slot of the block to be freed */
1226   CmiInt8 eslot = sslot + nslots;
1227   for (pos=0; pos < (ss->maxbuf); pos++)
1228   {
1229     CmiInt8 e = ss->buf[pos].startslot + ss->buf[pos].nslots;
1230     if (ss->buf[pos].nslots == 0)
1231       continue;
1232     /* e is the ending slot of pos'th slotblock */
1233     if (e == sslot) /* append to the current slotblock */
1234     {
1235             ss->buf[pos].nslots += nslots;
1236             ss->emptyslots += nslots;
1237             /* CmiPrintf("free:append pos=%d\n", pos); */
1238             return;
1239     }
1240     if(eslot == ss->buf[pos].startslot) /* prepend to the current slotblock */
1241     {
1242             ss->buf[pos].startslot = sslot;
1243             ss->buf[pos].nslots += nslots;
1244             ss->emptyslots += nslots;
1245             /* CmiPrintf("free:prepend pos=%d\n", pos); */
1246             return;
1247     }
1248   }
1249   /* if we are here, it means we could not find a slotblock that the */
1250   /* block to be freed was combined with. */
1251   /* CmiPrintf("free: pos=%d\n", pos); */
1252   add_slots(ss, sslot, nslots);
1253 }
1254
1255
1256 #endif