memtree.c

地球模拟器

     x = c->p;                  /* Expand node to the left */

   }

   else                         /* Or if invalid overlap */
     goto overlap;              /* Handle situation below */


   /* Arrive here after combining the deallocated piece
      with one or two neighbours, to see if the combined
      node requires promotion.  At this point:

        a = addr of the node array
        c = addr of the combined node

        pa = addr of `ptr' to combined node
        pas = the size of the paternal node

        x = addr of piece being deallocated
        z = endad of piece being deallocated         

        addr,size are as supplied by caller          */

weigh:
   c->p = x;                    /* Combined addr and size */
   c->s = z-x;

   *pa = c - a;                 /* Hang correctly in tree */

   if (c->s > pas)              /* If size exceeds father */
     promote (&a->r,c);         /* Promote combined node */


   /* All successful paths join here.  Keep `almond'
      informed, and return to my caller. On arrival:

        addr,size are as supplied by caller          */

foot:
   FreeMemCurrent += size;      /* Maintain all the books */

#ifdef ALCOMM                   /* Keep `almond' informed */
   if (MIsDFEnabled(TrtOrgLifeEvent))
     TRepDeath (addr,size);
#endif

   return;                      /* And return exhausted */


   /* Come here if I discover invalid overlap after
      starting to insert a node describing the piece
      being deallocated. Promote the overlapping node
      (or the first neighbour, if that is higher) to
      the position occupied by the scratch node, and
      then demote it (again) if necessary. I do not 
      guarantee that the tree will have the same
      shape as before, but I do guarantee that 
      it will be valid.  On arrival:   

        a = the addr of the node array
        c = addr of 1st neighbour, or addr
            of overlapping node, whichever 
            is higher in the tree

        pa = addr of `ptr' to scratch node        */

recover:
   c->l = scratch.l;            /* Tree ptrs from scratch */
   c->r = scratch.r;

   demote (pa,c);               /* Demote or reattach */


   /* Join here if I discover invalid overlap before
      making any alterations to the tree. Report the
      problem and terminate the entire program.   */

overlap:   
   FEError (-602,EXIT,WRITE,
            "Tierra MemDealloc error: corrupted soup addrs");

   /* Come here if a new memory node is required but there
      is insufficient system memory available.  Remove the 
      scratch node from the tree, report the problem verb-
      ally, and terminate the entire program. At this pt:

        pa = addr of `ptr' to scratch node              */

bust:
   delete (pa,&scratch);        /* Delete the scratch node */  

   FEError (-602,EXIT,WRITE,
            "Tierra MemDealloc error: insuf system memory avail");

} 


/*  __________________________________________________
   |                                                  | 
   |  Function delete -- Delete a node from the tree  |
   |__________________________________________________|

   Private function for MemAlloc() and MemDealloc()

   Call is:  delete (pa,victim)

   where:    pa = addr of parental `ptr' to victim
             victim = addr of the node to be deleted

   Also:     FreeMem = addr of memory node array   

   Notes:    1.  On entry, the victim need not be
                 connected to its paternal node.

             2.  The function deletes the node from
                 the tree but it does not chain it
                 into the recycle list. This is the
                 responsibility of the caller.    */


static void delete (pa,victim)  I32s Hp pa; Pmf victim;  {

Pmf   a;         /* Addr of the memory node array */

I32s  lb,rb;     /* `Ptrs' for left and right branch */

   a = FreeMem;              /* Addr of node array */
   lb = victim->l;           /* Index of the left son */ 
   rb = victim->r;           /* Index of the right son */

   while (lb!=0 && rb!=0)    /* While both subtrees exist */
     if ((a+lb)->s >= (a+rb)->s) {  /* If left node longer */
       *pa = lb;                    /* Attach to my father */  
       pa = &(a+lb)->r;             /* Father falls to right */
       lb = *pa;                    /* Remaining left subtree */
     } else {
       *pa = rb;
       pa = &(a+rb)->l;
       rb = *pa;
     }

   *pa = lb + rb;            /* Attach surviving subtree [sic] */
   return;

}        


/*  ________________________________________________
   |                                                | 
   |  Function demote -- Demote a node in the tree  |
   |________________________________________________|

   Private function for MemAlloc() and MemDealloc()

   Call is:  demote (pa,victim)

   where:    pa = addr of parental `ptr' to victim
             victim = addr of the node to be demoted

   Also:     FreeMem = addr of memory node array   

   Notes:    1.  On entry, the victim need not be
                 connected to its paternal node.

             2.  If the victim is already at the
                 correct level, it is simply con-
                 nected to the given father.      */


static void demote (pa,victim)  I32s Hp pa; Pmf victim;  {

Pmf   a;         /* Addr of the memory node array */

I32s  lb,rb;     /* `Ptrs' for left and right branch */

   a = FreeMem;              /* Addr of the node array */
   lb = victim->l;           /* Index of the left son */ 
   rb = victim->r;           /* Index of the right son */

   while ((a+lb)->s > victim->s || (a+rb)->s > victim->s) 
                                    /* While among big nodes */
     if ((a+lb)->s >= (a+rb)->s) {  /* If left node is longer */
       *pa = lb;                    /* Attach it to my father */  
       pa = &(a+lb)->r;             /* Father falls to right */
       lb = *pa;                    /* Remaining left subtree */
     } else {
       *pa = rb;
       pa = &(a+rb)->l;
       rb = *pa;
     }

   *pa = victim - a;         /* Insert demoted node here */
   victim->l = lb;           /* Set ptrs to both new sons */
   victim->r = rb;
   return;

}        


/*  __________________________________________________
   |                                                  | 
   |  Function promote -- Promote a node in the tree  |
   |__________________________________________________|

   Private function for MemAlloc() and MemDealloc()

   Call is:  promote (adam,riser)

   where:    adam = addr of `ptr' to root of tree
             riser = addr of node to be promoted
                     (must be somewhere in tree)

   Also:     FreeMem = addr of memory node array   

   Note:     On entry, the node to be promoted
             must be properly connected in the 
             tree, and must require promotion.    */


static void promote (pa,riser)  I32s Hp pa; Pmf riser;  {

Pmf   a,         /* Address of the memory node array */
      c;         /* Addr of current node in old tree */ 

I32s  Hp lh,     /* Left hook for root insertion */
      Hp rh,     /* Right hook for root insertion */
      ls,rs;     /* Indices for left,right subtree */


   a = FreeMem;              /* Addr of the node array */
   c = a + *pa;              /* Addr of the tree root */

   /* Perform a passive binary search for the node to be
      promoted until I encounter a node which describes
      an area of soup that is no longer than that des-
      cribed by the node to be promoted.              */

   while (c->s > riser->s) { /* While this size > riser */

     if (c->p < riser->p)    /* Perform a passive search */     
       pa = &c->r;
     else
       pa = &c->l;

     c = a + *pa;            /* Addr of next node down */

   }

   /* Insert the rising node at the root of the remaining
      subtree.                                         */

   *pa = riser - a;          /* Attach riser to new pa */
   lh = &riser->l; ls = *lh; /* Init hooks and save old */
   rh = &riser->r; rs = *rh;

   while (c != riser)        /* Until reach original riser */

     if (c->p < riser->p) {  /* If current node is to left */
       *lh = c - a;          /* Attach node to left hook */
       lh = &c->r;           /* Left hook falls to right */
       c = a + *lh;          /* Addr of next current node */
     } else {
       *rh = c - a;
       rh = &c->l;
       c = a + *rh;
     }

   *lh = ls; *rh = rs;       /* Attach both the subtrees */
   return;

}


/*  ____________________________________________________
   |                                                    | 
   |  Function memnode -- Supply an unused memory node  | 
   |____________________________________________________|

   Private function for MemAlloc() and MemDealloc()

   Call is:  b = memnode ()

   where:    b = index of memory node supplied, or zero 
                 if unable to supply a new memory node

   Also:     FreeMem       = addr of memory node array  :  May be changed
             MaxFreeBlocks = size of memory node array  :  as side effect 

   Summary:  Supply a recycled node if available.  Else
             supply an untouched node if available. Else
             increase the size of the array and supply 
             the first untouched node from the new part
             -- or yield a dummy value of zero if the
             array already occupies LONG_MAX bytes or
             more, or if there is insufficient system
             memory available.

   Note:     Callers of this function must relocate any
             private pointers which address data in the 
             node array, in order to compensate for pos-
             sible reallocation of the array.  This re-
             quires peculiar care, owing to the way in 
             which some C compilers implement ptr arith-
             metic.  Consider for example the following 
             situation:

               a = addr of the old array
               b = addr of the new array
               c = addr of an (old) node

             It is tempting to try and relocate `c' by
             writing:

               c = c + (b - a);      [or c += b - a;]

             However, some compilers assume that `a' and
             `b' refer to nodes in the same instance of
             the node array.  They therefore `know' that
             the value of (b-a) must be a multiple of 16
             (the size of a memory node). As a result (it
             appears) they feel justified in clearing the
             four low-order bits, which yields the wrong
             answer unless (a mod 16) happens to equal
             (b mod 16). 

             To avoid this problem, one is tempted to
             write:

               c = b + (c - a);

             This may in fact work (I have not tried it);
             but in principle parentheses in C do not de-
             termine the order of evaluation, so there is
             no guarantee that it will behave any differ-
             ently from the first method.      

             The safest thing to do seems to be to convert 
             all ptrs to offsets before calling newnode(),
             and then convert them back to ptrs afterwards.
             Suppose for example that u is a ptr to a node,
             and v is a ptr to an object of type V *in* a
             node.  Then the following sequence allocates
             a new node w and relocates the old ptrs if
             necessary:

               ou = u - FreeMem;       Integral offsets 
               ov = v - (V*)FreeMem;

               ow = memnode();         Allocate new node

               if (ow == 0)            If insuf sys mem
                 goto ...;             handle mess below 

               u = FreeMem + ou;       Updated node ptr
               v = (V*)FreeMem + ov;   Internal ptr too
               w = FreeMem + ow;       Addr of new node   */


static I32s memnode () {

Pmf   a;         /* Addr of memory node array */
I32s  b;         /* Index of the winning node */

   a = FreeMem;              /* Addr of the node array */
   b = a->l;                 /* Magic for available nodes */

   if (b > 0) {              /* If recycled nodes exist */
     a->l = (a+b)->l;        /* Remove 1st node from list */
     return (b);             /* Well that was quite easy */
   }

   if (b < 0) {              /* If untouched nodes exist */
     a->l ++;                /* Reduce the untouched part */
     return (MaxFreeBlocks+b);  /* Tricky, but still easy */
   }

   /* Arrive here if the entire node array is in use.
      Double the size of the array and supply the 1st
      node in the (new) second half.               */

   b = MaxFreeBlocks;                /* Existing array size */

   if (b > LONG_MAX/sizeof(MemFr))   /* If expansion impossible */
     return (0);                     /* Supply nothing whatever */

   a = (Pmf) threcalloc ((I8s Hp)a,      /* Enlarge node array */
             (I32u)(2*b*sizeof(MemFr)),  /* Desired array size */
             (I32u)(b*sizeof(MemFr)));   /* Old size of array */
  
   if (a == NULL)                    /* If insuf system memory */
     return (0);                     /* Supply nothing whatever */

   FreeMem = a;              /* Reset the global variables */
   MaxFreeBlocks = 2*b;

   a->l = b - (2*b) + 1;     /* -ve index of untouched part */
   return (b);               /* Supply 1st node in 2nd half */

}