memtree.c

地球模拟器

        This soup allocator does not however require 
        the entire array to be initialized, and the
        array could equally well be obtained with
        malloc() instead of calloc() provided this
        routine was changed to clear the following
        fields:
        
                 FreeMem[0].p, FreeMem[0].s,
          FreeMem[1].l, FreeMem[1].r, FreeMem[1].p.  */

void MemInit () {

#ifdef ERROR

   if (MaxFreeBlocks < 2)
     FEError (-601,EXIT,WRITE,
              "Tierra MemInit() error: memory node array too small");

   if (SoupSize <= 0)
     FEError (-601,EXIT,WRITE,
              "Tierra MemInit() error: invalid soup size");

#endif

   FreeMem[0].l = -(MaxFreeBlocks-2);  /* -ve index of untouched */
   FreeMem[0].r = 1;                   /* Initial root for tree  */
   FreeMem[1].s = SoupSize;            /* Initial root holds all */

   return;

}


/*  ________________________________________________________
   |                                                        | 
   |  Function IsFree -- Enquire whether soup addr is free  |
   |________________________________________________________|

   Call is:  y = IsFree (x)

   where:    x = signed fullword integer containing soup addr
             y = small integer (8 bits) which is set to 0 (if 
                 given soup addr is occupied) or 1 (if free)     

   Also:     FreeMem  = addr of the memory node array
             SoupSize = size of soup in instr slots

   This version of IsFree() was written for the new soup 
   allocator; CJS, Santa Fe, July 1992.                   */ 


I8s IsFree (x)   I32s x;  {

Pmf   a,         /* Addr of memory node array */
      c;         /* Addr of current memory node */

#ifdef ERROR
   if (x<0 || x>=SoupSize)
     FEError (-601,EXIT,WRITE,
              "Tierra IsFree() error: addr %ld not in soup",x);
#endif

   a = FreeMem;              /* Addr of node array */
   c = a + a->r;             /* Addr of the tree root */

   while (c != a)            /* Until I fall from tree */
     if (c->p > x)           /* If this node exceeds x */
       c = a + c->l;         /* Step down to left son */
     else
       if ((c->p + c->s) > x)   /* If node contains x */
         return (1);            /* Yield 1 (addr free) */
       else
         c = a + c->r;       /* Step down to right son */

   return (0);               /* Yield 0 (addr occupied) */

}

/*  _____________________________________________________
   |                                                     | 
   |  Function MemAlloc -- Allocate an area of the soup  | 
   |_____________________________________________________|

   Call is:  p = MemAlloc (size,pref,tol) 

   where:    size, pref, tol and p are all signed fullword 
             integers

   and:      size = required amount of soup in instr slots 
                    (0 < size <= SoupSize)

             pref = preferred soup addr (0 <= pref < SoupSize),
                    or pref < 0 if the caller has no preference

             tol  = acceptable tolerance (0 <= tol < SoupSize),
                    or irrel if pref < 0

             p    = allocated soup addr (normally),
                    or -1 if there is no unoccupied  area
                          of adequate size,
                    or -2 if an area of adequate size exists,
                          but not within the given tolerance

   Also:     FreeMem        = addr of memory node array  :  May be changed
             MaxFreeBlocks  = size of memory node array  :  as side effect 
             FreeMemCurrent = sum of unoccupied space    :  of call

             SoupSize = size of soup in instr slots      :  Not changed


   ----------------  Summary of MemAlloc()  ----------------

   1.   If the largest unoccupied area of soup has inadequate
        size, supply a dummy soup addr of -1, without allocat-
        ing any soup at all.  Otherwise proceed as follows.

   2.   If pref < 0, ignore given tolerance, and allocate 
        required soup using `Better Fit', which is sure to
        succeed (see below).  Otherwise proceed as follows.
   
   3.   Identify the winning unoccupied area.

        If the preferred addr lies within an unoccupied area 
        of adequate size, the winning area is the one contain-
        ing the preferred addr; otherwise it is the area of
        adequate size that possesses the minimum separation
        from the preferred addr. (The `separation' is measur-
        ed from `pref' to the beginning of the area, if pref
        precedes the area; or from the end of the area to
        `pref', if the area precedes pref.) If two adequate 
        areas possess equal separation, the one on the left
        prevails.

   4a.  If the winning unoccupied area does not contain the
        preferred addr, identify the nearer edge of the area,
        and measure the absolute difference between this edge
        and the preferred addr.  If this distance exceeds the
        given tolerance, supply a dummy soup addr of -2, with-
        out allocating any soup at all.  Otherwise allocate
        the required soup from the nearer edge.

   4b.  If the winning area contains the preferred addr,
        identify the nearer edge of the area (or define the
        left edge as the nearer if `pref' lies at the centre
        of the winning area), and measure the absolute dis-
        tance between this edge and the preferred addr.  If
        the distance does not exceed size+tol, allocate the
        required soup from this nearer edge; otherwise al-
        locate it at the preferred addr exactly (i.e. beg-
        inning at `pref' and extending to the right).

   Notes:

   1.   `Better Fit' is an allocation policy which selects
        a winning node by descending from the root, always 
        choosing the better-fitting son, until it encount-
        ers a node which possess no sons of adequate size 
        (or no sons at all). The winning area of the soup 
        is the one described by the winning node. 

        In this implementation of Better Fit:

           if both sons are adequate, and have the  
           same size, the one on the left prevails;

           if the size of the winning area exceeds 
           the required size, allocation is made 
           from its left edge.

   2.   `Leftmost Fit' from the tree (which is equivalent 
        to `First Fit' from the corresponding list) can be
        realized by supplying a preferred address of zero
        and the most generous allowable tolerance.        */


I32s MemAlloc (size,pref,tol)  I32s size,pref,tol;  {

Pmf   a,         /* Addr of memory node array */
      c,         /* Addr of current memory node */
      e;         /* Addr of new memory node */

I32s  Hp b,      /* Addr of parental `ptr' to c */
      Hp pa,     /* Addr of `ptr' to best node */

      best,      /* Distance to nearest node */

      oc,        /* Offset of node `c' in array */
      oe,        /* Offset of node `e' in array */
      opa,       /* Offset of `pa' in node array */

      x,         /* Beg soup addr of selected node */
      y,         /* The soup addr that is allocated */
      z;         /* End soup addr of selected node */

#ifdef ERROR

   if (size<=0 || size>SoupSize)
     FEError (-601,EXIT,WRITE,
              "Tierra MemAlloc error: invalid size %ld",size);
   if (pref >= SoupSize)
     FEError (-601,EXIT,WRITE,
              "Tierra MemAlloc error: invalid preference %ld",pref);
   if (pref>=0 && (tol<0 || tol>=SoupSize))
     FEError (-601,EXIT,WRITE,
              "Tierra MemAlloc error: invalid tolerance %ld",tol);

#endif

   a = FreeMem;              /* Addr of node array */
   c = a + a->r;             /* Addr of the tree root */

   if (c->s < size)          /* If biggest area is too small */
     return (-1);            /* Yield -1 (cannot supply soup) */ 

   if (pref < 0)             /* If caller has no preference */
     goto better;            /* Handle below (by better fit) */
     
   /* Arrive here if soup is to be allocated using  
      given preference and tolerance. At this point:

        a = addr of memory array
        c = addr of the root node

        size,pref,tol are as supplied by caller

      Search for the preferred addr until I reach
      a node whose son is too short.              */

   b = &a->r;                /* Addr of my parental `ptr' */
   best = LONG_MAX;          /* Best so far is pretty bad */

   do {                      /* Execute this at least once */
     
     if (c->p > pref) {          /* If this soup addr > pref */
       if (c->p-pref <= best) {  /* And it is nearest so far */
         pa = b;                 /* Remember the parental ptr */
         best = c->p - pref;     /* Remember closest contact */
       }
       b = &c->l;                /* Step down to the left */
     } else {
       if (pref-(c->p+c->s-1) <= best) {
         pa = b;
         best = pref - (c->p + c->s - 1); /* May set best < 0 */
       }
       b = &c->r;
     }

     c = a + *b;             /* Addr of the descendant node */

   } while (best > 0 && c->s >= size);


   /* Arrive here after finding the nearest unoccupied area
      of adequate size. See if it is near enough to his pre- 
      ference.  At this point:

        a = addr of the memory array
        pa = addr of `ptr' to best node
        best = distance separating best area from
               preferred addr, or <= 0 if preferred
               addr lies within an unoccupied area
               of adequate size

        size,pref,tol are as supplied by caller      */
      
   c = a + *pa;              /* Addr of winning node */

   x = c -> p;               /* x = beginning soup addr */
   z = x + c->s;             /* z = ending addr for node */

   if (best > 0) {           /* If pref addr is not available */

     if (best > tol)         /* If distance exceeds tolerance */
       return (-2);          /* Yield -2 (cannot satisfy him) */ 

     if (x > pref)           /* If best is to right of pref */
       goto leftedge;        /* Allocate from left-hand edge */
     else                    /* Or if the best is to the left */
       goto rightedge;       /* Allocate from right-hand edge */

   }

   /* Arrive here if the preferred addr lies within an
      unoccupied area of the soup. Allocate from the nearer
      edge -- if this will place the area within the speci-
      fied tolerance.  At this point:

        a = addr of the memory array
        c = the addr of the best node
        pa = addr of `ptr' to best node

        x = beg soup addr of best node
        z = end soup addr of best node

        size,pref,tol are as supplied by caller      */

   if (pref-x <= z-(pref+size-1))  /* If left edge is nearer */

     if (pref-x <= tol)          /* And if it is near enough */
       goto leftedge;            /* Allocate from left edge */
     else
       ;

   else                          /* If right edge nearer ... */

     if (z-(pref+size-1) <= tol)
       goto rightedge;
     else
       ;

   /* Arrive here if both edges of the area containing 
      the preferred addr are too far from the preferred 
      addr.  Split the area into three, and allocate at
      the preferred addr exactly.  At this point:  

        a = addr of the memory array
        c = the addr of the best node
        pa = addr of `ptr' to best node

        x = beg soup addr of best node
        z = end soup addr of best node

        size,pref,tol are as supplied by caller      

      See note in `memnode' on relocation of ptrs.  */

   oc = c - a;                   /* Convert ptrs to offsets */
   opa = pa - (I32s Hp)a;

   oe = memnode();               /* Acquire new memory node */
   
   if (oe == 0)                  /* If insufficient memory */
     goto bust;                  /* Handle situation below */

   a = FreeMem;                  /* Addr of (new) node array */

   c = a + oc;                   /* Reset my  node ptrs */
   pa = (I32s Hp)a + opa;       

   e = a + oe;                   /* Addr of new memory node */

   e->p = pref + size;           /* Addr of right-hand scrap */
   e->s = z - e->p;              /* Size of right-hand scrap */

   c->s = pref - x;              /* Size of left-hand scrap */

   /* Demote the larger scrap and then insert the
      smaller scrap at the correct place below it.

        a = addr of the memory array
        c = addr of node for LH scrap
        e = addr of node for RH scrap           

        pa = addr of `ptr' to LH scrap

        size,pref are as supplied by caller    */

   if (c->s >= e->s) {               /* If LHS is bigger */

     demote (pa,c);                  /* Demote LH scrap */

     pa = &c->r;                     /* Find home for RHS */     
     while ((a + * pa)->s > e->s)
       pa = &(a + * pa)->l;

     e->l = 0;                       /* Insert RH scrap */
     e->r = *pa;     
     *pa = e - a;

   } else {                          /* If RHS bigger ... */

     e->l = c->l;                    /* Ptrs for demote */
     e->r = c->r;     

     demote (pa,e);                  /* Demote RH scrap */

     pa = &e->l;                     /* Find home for LHS */     
     while ((a + * pa)->s > c->s)
       pa = &(a + * pa)->r;

     c->l = *pa;                     /* Insert LH scrap */
     c->r = 0;
     *pa = c - a;

   }

   y = pref;                     /* Allocate at this addr */
   goto foot;                    /* And handle rest below */


   /* Come here if no preference is given. Allocate 
      some soup using Better Fit.  (This is sure to 
      succeed, since I already checked the size of 
      the root.)  At this point:

        a = addr of the memory array
        c = the addr of the root node 

        size is as supplied by caller            */

better:
   pa = &a->r;                   /* Addr of `ptr' to the root */