home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 163_01 / heap.c < prev    next >
Text File  |  1988-01-31  |  6KB  |  139 lines
  1. /*
  2. ** Basic scheme:
  3. **
  4. ** The heap grows up from the top of static storage.
  5. ** It is controlled by three pointers, each declared "int *":
  6. **   _heapbase -- first (lowest) byte usable by heap (relative to DS/SS/ES)
  7. **   _heapfree -- address below which no free space exists in heap
  8. **                searches start here
  9. **   _heaptop  -- address of top (dummy) element in heap
  10. **                don't let SP get too close to this!!
  11. **
  12. ** Each heap entry -- allocated or free -- is on a 4-byte boundary & has an
  13. ** int[2] header.  header[0] is the size -- in halfwords -- of the entry.
  14. ** header[1] is the size -- in halfwords -- of the prior entry:  This is used
  15. ** to locate the prior entry for garbage collection.  The high-order bit of
  16. ** header[1] is set if entry is a free space entry, cleared if entry is
  17. ** allocated.
  18. **
  19. ** The maximum legal request is 64K - 4.  Clearly, a request of this size
  20. ** will never actually be granted.
  21. */
  22.  
  23. #define PARANOID
  24.  
  25. malloc(size) int size; {
  26.   int *SP, *ptr, *newblk, *nxtblk, oldsize, intcast;
  27. #asm
  28.        MOV [BP]-2,SP ;retrieve current stack ptr value (into "*SP")
  29. #endasm
  30.   if(_heaptop+100 < _heaptop || _heaptop+100 > SP) abort(ENOMEM);
  31.   if(size == 0) return 0; /* return if was only a check for enough stg */
  32.   size = (((size + 7) & (-4))/2) & 32767; /* get size in halfwords,
  33.                                       plus header & rounded up */
  34.   if(size == 0) {errno = EINVAL; return 0;} /* request too big */
  35.   ptr = _heapfree; /* ptr to first place to look for free space */
  36. #ifdef PARANOID
  37.   if((intcast = _heapfree) & 3) abort(EFAULT);
  38. #endif
  39.   _heapfree = (-1); /* will set this during search */
  40.   while(ptr[0]) { /* top (dummy) block is marked as zero length */
  41. #ifdef PARANOID
  42.     if((intcast = ptr) & 3) abort(EFAULT);
  43.     if(ptr[0] & (-32768)) abort(EFAULT);
  44.     if(ptr[0] & 1) abort(EFAULT);
  45.     if(ptr[1] & 1) abort(EFAULT);
  46. #endif
  47.     if(ptr[1] & (-32768)) { /* if free space */
  48.       if(ptr < _heapfree) _heapfree = ptr; /* update free space ptr */
  49.       if(ptr[0] >= size) { /* if space is big enough */
  50.         if(ptr[0] != size) { /* if space is too big */
  51.           oldsize = ptr[0]; /* extract current size of block */
  52.           newblk = ptr + size; /* address of new block to create */
  53.           nxtblk = ptr + ptr[0]; /* address of next block beyond this one */
  54. #ifdef PARANOID
  55.           if(nxtblk[0] & (-32768)) abort(EFAULT);
  56.           if(nxtblk[0] & 1) abort(EFAULT);
  57.           if(nxtblk[1] & 1) abort(EFAULT);
  58. #endif
  59.           ptr[0] = size; /* set new block size */
  60.           newblk[0] = nxtblk[1] = oldsize - size; /* size of remaining space */
  61.           newblk[1] = size | (-32768); /* size of allocated block + flag */
  62.           }
  63.         ptr[1] &= 32767; /* clear free space flag */
  64.         return &ptr[2]; /* address of 1st usable byte */
  65.         }
  66.       }
  67.     ptr += ptr[0]; /* point at next block */
  68.     }
  69.   /* if we get this far, no free block was found that was large enough */
  70. #ifdef PARANOID
  71.   if(ptr != _heaptop) abort(EFAULT);
  72.   if(_heaptop[0] & (-32768)) abort(EFAULT);
  73.   if(_heaptop[0] & 1) abort(EFAULT);
  74.   if(_heaptop[1] & 1) abort(EFAULT);
  75. #endif
  76.   oldsize = (SP - _heaptop) & 32767; /* available space (halfwords) */
  77.   if(oldsize-size < 500) { /* return if no space */
  78.     _heapfree = _heaptop; /* leave free ptr valid */
  79.     errno = ENOMEM;
  80.     return 0;
  81.     }
  82.   ptr[0] = size; /* set size of new block */
  83.   ptr[1] &= 32767; /* clear free space flag */
  84.   _heapfree = _heaptop = ptr + size; /* new top of heap */
  85.   _heaptop[0] = 0; /* new dummy entry */
  86.   _heaptop[1] = size | (-32768); /* size of entry just allocated */
  87.   return &ptr[2]; /* return address of 1st usable byte */
  88.   }
  89.  
  90. free(ptr) int *ptr; {
  91.   int *ptr1, *ptr2, intcast;
  92.   ptr -= 2; /* get address of header */
  93.   if((intcast = ptr) & 3 || ptr < _heapbase || ptr >= _heaptop ||
  94.       ptr[0] & (1-32768) || ptr[1] & (1-32768)) /* check for bad pointer */
  95.     abort(EINVAL); /* pointer (or heap) is corrupted */
  96.   ptr1 = ptr - ptr[1]; /* get address of prior block */
  97. #ifdef PARANOID
  98.   if(ptr1[0] & (-32768)) abort(EFAULT);
  99.   if(ptr1[0] & 1) abort(EFAULT);
  100.   if(ptr1[1] & 1) abort(EFAULT);
  101. #endif
  102.   if(ptr1[1] & (-32768)) { /* if prior block is free */
  103.     ptr1[0] = ptr[0] + ptr[1]; /* combine sizes (careful of 1st block) */
  104.     ptr2 = ptr1 + ptr1[0]; /* address of following block */
  105. #ifdef PARANOID
  106.     if(ptr2[0] & (-32768)) abort(EFAULT);
  107.     if(ptr2[0] & 1) abort(EFAULT);
  108.     if(ptr2[1] & 1) abort(EFAULT);
  109. #endif
  110.     ptr2[1] = ptr1[0] | (ptr2[1] & (-32768)); /* set back pointer */
  111.     ptr = ptr1; /* new free space entry for following check */
  112.     }
  113.   ptr1 = ptr + ptr[0]; /* get address of next block */
  114. #ifdef PARANOID
  115.   if(ptr1[0] & (-32768)) abort(EFAULT);
  116.   if(ptr1[0] & 1) abort(EFAULT);
  117.   if(ptr1[1] & 1) abort(EFAULT);
  118. #endif
  119.   if(ptr1[1] & (-32768)) { /* if next block is free */
  120.     ptr[0] += ptr1[0]; /* combine sizes */
  121.     ptr1 = ptr + ptr[0]; /* address of new next block */
  122. #ifdef PARANOID
  123.     if(ptr1[0] & (-32768)) abort(EFAULT);
  124.     if(ptr1[0] & 1) abort(EFAULT);
  125.     if(ptr1[1] & 1) abort(EFAULT);
  126. #endif
  127.     ptr1[1] = ptr[0] | (ptr1[1] & (-32768)); /* set back ptr */
  128.     }
  129.   ptr[1] |= (-32768); /* mark the block free */
  130.   if(ptr < _heapfree) _heapfree = ptr; /* set free space search ptr */
  131.   if(!ptr1[0]) { /* if next block is top of heap */
  132. #ifdef PARANOID
  133.     if(ptr1 != _heaptop) abort(EFAULT);
  134. #endif
  135.     ptr[0] = 0; /* move it back to current block */
  136.     _heaptop = ptr; /* remember new top */
  137.     }
  138.   }
  139.