home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixlib36d / src / c / alloc < prev    next >
Text File  |  1994-03-08  |  6KB  |  406 lines
  1. static char sccs_id[] = "@(#) alloc.c 5.0 " __DATE__ " HJR";
  2.  
  3. /* alloc.c (c) Copyright 1990 H.Rogers */
  4.  
  5. /* features multiple free lists hashed on block size */
  6.  
  7. #include <stddef.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. #ifdef M_DEBUG
  12. #include <stdio.h>
  13. #include <signal.h>
  14.  
  15. static int
  16. __m_fail (char *exp, char *file, int line)
  17. {
  18.   fprintf (stderr, "\n\"%s\", line %d: Assertion failed: %s\n", file, line, exp);
  19.   raise (SIGABRT);
  20.   return (0);
  21. }
  22.  
  23. #define assert(x)    (void)((x) ? 0 : __m_fail(#x,__FILE__,__LINE__))
  24.  
  25. #define addr(x)     ((x) ? (*((int *)(x)) | 1) : 0)
  26.  
  27. #define MAGIC        0x4349474d
  28. #endif
  29.  
  30. extern void *sbrk (int);
  31.  
  32. typedef struct _blk
  33.   {
  34. #ifdef M_DEBUG
  35.     int magic;
  36. #endif
  37.     struct _blk *next;
  38.     size_t size;
  39.   }
  40. blk;
  41.  
  42. #ifdef M_DEBUG
  43. #define BLKSIZ        16    /* smallest power of 2 >= sizeof(blk) */
  44. #else
  45. #define BLKSIZ        8
  46. #endif
  47.  
  48. #define blkalign(x)    (((x) + (BLKSIZ<<1) - 1) & (~(BLKSIZ - 1)))
  49.  
  50. #define NFL    8
  51.  
  52. static blk __fl[NFL];
  53. static size_t __flmin[NFL] =
  54. {
  55.   4096 + BLKSIZ,
  56.   1024 + BLKSIZ,
  57.   256 + BLKSIZ,
  58.   64 + BLKSIZ,
  59.   32 + BLKSIZ,
  60.   16 + BLKSIZ,
  61.   8 + BLKSIZ,
  62.   0 + BLKSIZ            /* catchall */
  63. };
  64.  
  65. #define MEMINC        12    /* sbrk() memory block bit alignment */
  66.  
  67. void
  68. __allocinit (void)
  69. {
  70.   register blk *b;
  71.   register int i;
  72.  
  73. #ifdef M_DEBUG
  74.   assert (sizeof (struct _blk) <= BLKSIZ);
  75. #endif
  76.  
  77.   for (i = 0; i < NFL; i++)
  78.     {
  79.       b = __fl + i;
  80.       b->next = b;
  81.       b->size = BLKSIZ;
  82. #ifdef M_DEBUG
  83.       b->magic = MAGIC;
  84. #endif
  85.     }
  86. }
  87.  
  88. static blk *
  89. findblk (register int i, register blk * a)
  90. {
  91.   register blk *b, *p;
  92.  
  93.   p = __fl + i;
  94.   b = p->next;
  95.  
  96. #ifdef M_DEBUG
  97.   assert (addr (p));
  98.   assert (p->magic == MAGIC);
  99. #endif
  100.  
  101.   while (b > p)
  102.     {
  103. #ifdef M_DEBUG
  104.       assert (addr (b));
  105.       assert (b->magic == MAGIC);
  106. #endif
  107.       if (b >= a)
  108.     break;
  109.       p = b;
  110.       b = b->next;
  111.     }
  112.  
  113.   return (p);
  114. }
  115.  
  116. #define addblk(i,n,p) ((n)->next = (p)->next,(p)->next = (n))
  117.  
  118. #define delblk(i,b,p) ((p)->next = (b)->next)
  119.  
  120. static void
  121. concatblk (register blk * a, register blk * p)
  122. {
  123.   register blk *b;
  124.  
  125.   if (!p)
  126.     return;
  127.  
  128.   b = p->next;
  129.  
  130.   while ((char *) a + a->size == (char *) b)
  131.     {
  132.       a->size += b->size;
  133. #ifdef M_DEBUG
  134.       b->magic = 0;
  135. #endif
  136.       b = b->next;
  137.     }
  138.  
  139.   p->next = b;
  140. }
  141.  
  142. static int
  143. flindex (register int size)
  144. {
  145.   register int i;
  146.  
  147.   for (i = 0; size < __flmin[i]; i++);
  148.  
  149.   return (i);
  150. }
  151.  
  152. static blk *
  153. findsize (register int i, register int size, register blk ** p_)
  154. {
  155.   register blk *b, *p;
  156.  
  157.   p = __fl + i;
  158.   b = p->next;
  159.  
  160.   while (b > p)
  161.     {
  162.       if (b->size >= size)
  163.     {
  164.       delblk (i, b, p);
  165.       break;
  166.     }
  167.       p = b;
  168.       b = b->next;
  169.     }
  170.  
  171.   if (p_)
  172.     *p_ = p;
  173.   return (b);
  174. }
  175.  
  176. void *
  177. malloc (register size_t size)
  178. {
  179.   register blk *b;
  180.   register int i;
  181.   blk *p;
  182.  
  183.   if (!size)
  184.     return (0);
  185.  
  186.   size = blkalign (size);
  187.  
  188.   i = flindex (size);
  189.  
  190.   b = findsize (i, size, &p);
  191.  
  192.   if (b <= p)
  193.     {
  194.       register void *m;
  195.       register int _size;
  196.  
  197.       _size = ((size >> MEMINC) + 1) << MEMINC;
  198.       if ((m = sbrk (_size)) == (void *) -1)
  199.     return (0);
  200.  
  201.       if ((char *) p + p->size == (char *) m)
  202.     {
  203.       b = p;
  204.       p = findblk (i, b);
  205.       delblk (i, b, p);
  206.       b->size += _size;
  207.     }
  208.       else
  209.     {
  210.       b = (blk *) m;
  211.       b->size = _size;
  212. #ifdef M_DEBUG
  213.       b->magic = MAGIC;
  214. #endif
  215.     }
  216.     }
  217.  
  218. #ifdef M_DEBUG
  219.   assert (addr (b));
  220.   assert (b->magic == MAGIC);
  221. #endif
  222.  
  223.   if (b->size > (size + __flmin[i]))
  224.     {
  225.       register blk *n;
  226.  
  227.       n = (blk *) ((char *) b + size);
  228.  
  229.       addblk (i, n, p);
  230.  
  231.       n->size = b->size - size;
  232. #ifdef M_DEBUG
  233.       n->magic = MAGIC;
  234. #endif
  235.       b->size = size;
  236.     }
  237.  
  238.   return ((void *) ((char *) b + BLKSIZ));
  239. }
  240.  
  241. void *
  242. realloc (register void *_a, register size_t size)
  243. {
  244.   register blk *a;
  245.   register int i;
  246.   blk *p;
  247.  
  248.   if (!(_a))
  249.     return (malloc (size));
  250.  
  251.   if (!size)
  252.     {
  253.       free (_a);
  254.       return (0);
  255.     }
  256.  
  257.   size = blkalign (size);
  258.  
  259. #ifdef M_DEBUG
  260.   assert (addr (_a));
  261. #endif
  262.  
  263.   a = (blk *) ((char *) _a - BLKSIZ);
  264.  
  265. #ifdef M_DEBUG
  266.   assert (addr (a));
  267.   assert (a->magic == MAGIC);
  268. #endif
  269.  
  270.   i = flindex (a->size);
  271.  
  272.   p = findblk (i, a);
  273.  
  274.   concatblk (a, p);
  275.  
  276.   if (a->size < size)
  277.     {
  278.       if ((char *) p + p->size == (char *) a && p->size + a->size >= size)
  279.     {
  280.       register blk *b;
  281.  
  282. #ifdef M_DEBUG
  283.       assert (addr (p));
  284.       assert (p->magic == MAGIC);
  285. #endif
  286.       b = p;
  287.       p = findblk (i, b);
  288.       delblk (i, b, p);
  289.       b->size += a->size;
  290. #ifdef M_DEBUG
  291.       a->magic = 0;
  292. #endif
  293.       memmove ((char *) b + BLKSIZ, _a, a->size - BLKSIZ);
  294.       _a = (char *) (a = b) + BLKSIZ;
  295.     }
  296.       else
  297.     {
  298.       register void *m;
  299.       register int _size;
  300.  
  301.       _size = ((size >> MEMINC) + 1) << MEMINC;
  302.       if ((m = sbrk (_size)) == (void *) -1)
  303.         return (0);
  304.  
  305.       if ((char *) a + a->size == (char *) m)
  306.         a->size += _size;
  307.       else
  308.         {
  309.           register blk *b;
  310.  
  311.           addblk (i, a, p);
  312.           b = (blk *) m;
  313.           b->size = _size;
  314. #ifdef M_DEBUG
  315.           b->magic = MAGIC;
  316. #endif
  317.           memcpy ((char *) b + BLKSIZ, _a, a->size - BLKSIZ);
  318.           _a = (char *) (a = b) + BLKSIZ;
  319.         }
  320.     }
  321.     }
  322.  
  323.   i = flindex (size);
  324.  
  325.   if (a->size > (size + __flmin[i]))
  326.     {
  327.       register blk *n;
  328.  
  329.       p = findblk (i, a);
  330.  
  331.       n = (blk *) ((char *) a + size);
  332.  
  333.       addblk (i, n, p);
  334.  
  335.       n->size = a->size - size;
  336. #ifdef M_DEBUG
  337.       n->magic = MAGIC;
  338. #endif
  339.       a->size = size;
  340.     }
  341.  
  342.   return (_a);
  343. }
  344.  
  345. void
  346. free (register void *_a)
  347. {
  348.   register blk *a, *p;
  349.   register int i;
  350.  
  351.   if (!_a)
  352.     return;
  353.  
  354. #ifdef M_DEBUG
  355.   assert (addr (_a));
  356. #endif
  357.  
  358.   a = (blk *) ((char *) _a - BLKSIZ);
  359.  
  360. #ifdef M_DEBUG
  361.   assert (addr (a));
  362.   assert (a->magic == MAGIC);
  363. #endif
  364.  
  365.   i = flindex (a->size);
  366.  
  367.   p = findblk (i, a);
  368.  
  369.   concatblk (a, p);
  370.  
  371.   if ((char *) p + p->size == (char *) a)
  372.     {
  373.       p->size += a->size;
  374. #ifdef M_DEBUG
  375.       a->magic = 0;
  376. #endif
  377.     }
  378.   else
  379.     addblk (i, a, p);
  380. }
  381.  
  382. #ifdef M_DEBUG
  383. void
  384. __m_debug (void)        /* dump free lists */
  385. {
  386.   register blk *b;
  387.   register int i;
  388.  
  389.   for (i = 0; i < NFL; i++)
  390.     {
  391.       printf ("\nfl: %d ( >= %d )\n", i, __flmin[i] - BLKSIZ);
  392.       b = __fl + i;
  393.       do
  394.     {
  395.       b = b->next;
  396.       printf ("%7x: next: %7x [%7x] size: %x\n", b, b->next,
  397.           (char *) b + b->size, b->size - BLKSIZ);
  398.       assert (addr (b));
  399.       assert (b->magic == MAGIC);
  400.     }
  401.       while (b->next > b);
  402.     }
  403.   putchar ('\n');
  404. }
  405. #endif
  406.