home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / EMXLIB8F.ZIP / EMX / LIB / MALLOC / MALLOC.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-02  |  3.2 KB  |  131 lines
  1. /* malloc.c (emx+gcc) -- Copyright (c) 1990-1993 by Eberhard Mattes */
  2.  
  3. #define _MALLOC_C
  4.  
  5. #include <sys/emx.h>
  6. #include <stdlib.h>
  7.  
  8. #define CHUNK_SIZE 65536
  9. #define MAX_SIZE   0x40000000
  10.  
  11. /* to do: take size of last free block into account, if no used block */
  12. /*        follows and if sbrk() must be called.                       */
  13.  
  14. /* Bug: sbrk/brk must not be called by user program to change data    */
  15. /*      segment size (very complicated to fix). malloc returns NULL   */
  16. /*      if it thinks the data segment size has been changed.          */
  17.  
  18. size_t *rover = NULL;
  19. size_t *bottom = NULL;
  20. size_t *top = NULL;
  21.  
  22.  
  23. void *malloc (size_t size)
  24. {
  25.   void *p;
  26.   size_t n;
  27.  
  28.   if (size > MAX_SIZE)
  29.     return (NULL);
  30.   HEAP_LOCK;
  31.   if (rover == NULL)
  32.     {
  33.       n = (size_t)sbrk (0);
  34.       if ((n & 3) != 0)
  35.         sbrk (4 - (n & 3));
  36.       p = sbrk (2 * sizeof (size_t));
  37.       if (p == (void *)(-1) || ((size_t)p & 3) != 0)
  38.         {
  39.           HEAP_UNLOCK;
  40.           return (NULL);
  41.         }
  42.       bottom = rover = p;
  43.       top = bottom+1;
  44.       *bottom = 1;              /* length = 0, free */
  45.       *top = END_OF_HEAP;       /* End of heap      */
  46.     }
  47.   p = _malloc2 (size);
  48.   HEAP_UNLOCK;
  49.   return (p);
  50. }
  51.  
  52.  
  53. /* pass 1: search from rover to end of heap   */
  54. /* pass 2: search from start of heap to rover */
  55. /* pass 3: search from rover to end of heap (after growing heap) */
  56.  
  57. void *_malloc2 (size_t size)
  58. {
  59.   size_t *block, *base;
  60.   void *p;
  61.   size_t len, n;
  62.   int pass;
  63.  
  64.   if (size > MAX_SIZE)          /* Don't call sbrk() with negative argument */
  65.     return (NULL);
  66.   size = (size+3) & ~3;         /* Round to DWORD, bit 0 used as flag */
  67.   pass = 1;
  68. restart:
  69.   block = base = rover;
  70. in_use:
  71.   if (*block & 1)
  72.     goto free_start;
  73. not_free:
  74.   if (pass == 2 && (size_t)block > (size_t)rover)
  75.     {
  76.       block = top;
  77.       goto not_found;
  78.     }
  79.   if (*block == END_OF_HEAP)
  80.     {
  81.       if (block != top)
  82.         return (NULL);
  83.       if (pass >= 2)
  84.         goto not_found;
  85.       ++pass; block = bottom;
  86.       goto in_use;
  87.     }
  88.   block = (size_t *)((char *)block + sizeof (size_t) + *block);
  89.   goto in_use;
  90.  
  91. free_start:
  92.   base = block;
  93.   len = *base & ~3;
  94. free_loop:
  95.   if (len >= size)
  96.     goto found;
  97.   block = (size_t *)((char *)base + sizeof (size_t) + len);
  98.   if (!(*block & 1))
  99.     goto not_free;
  100.   len += sizeof (size_t) + (*block & ~3);
  101.   *base = len | 1;
  102.   goto free_loop;
  103.  
  104. found:
  105.   if (len - size > sizeof (size_t))
  106.     {
  107.       *base = size;             /* even, ie, in use */
  108.       block = (size_t *)((char *)base + sizeof (size_t) + size);
  109.       *block = (len - size - sizeof (size_t)) | 1;
  110.     }
  111.   else
  112.     *base &= ~3;                /* in use! */
  113.   rover = base;
  114.   return ((void *)((char *)base + sizeof (size_t)));
  115.  
  116. not_found:
  117.   n = (size + sizeof (size_t) + 0xfff) & ~0xfff;
  118.   if (n < CHUNK_SIZE)
  119.     n = CHUNK_SIZE;             /* memory is cheap, searching expensive */
  120.   p = sbrk (n);
  121.   if (p == (void *)(-1))
  122.     return (NULL);
  123.   if (p != top+1)
  124.     return (NULL);
  125.   *top = (n - sizeof (size_t)) | 1;
  126.   top = (size_t *)((char *)top + n);
  127.   *top = END_OF_HEAP;
  128.   pass = 3; rover = base;
  129.   goto restart;
  130. }
  131.