home *** CD-ROM | disk | FTP | other *** search
/ PC Media 4 / PC MEDIA CD04.iso / share / prog / memalloc / memalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-20  |  11.2 KB  |  555 lines
  1. #include <string.h>
  2. #include "memalloc.h"
  3.  
  4. #ifdef __cplusplus
  5. extern "C" {
  6. #endif
  7.  
  8. #define moveleft(d,s,l) memcpy(d,s,l)
  9. #define moveright(d,s,l) memmove(d,s,l)
  10. #define mcbsize 16
  11.  
  12. #ifdef __86__
  13.  
  14. #include <dos.h>
  15. #ifdef __TURBOC__
  16. #include <alloc.h>
  17. #define memadd(p,i) ((mem_ptr)((char huge*)(p)+(i))+mcbsize)
  18. #else /*__TURBOC__*/
  19. #define memadd(p,i) (hugeadd((p),(i))+mcbsize)
  20. #endif /*__TURBOC__*/
  21. #define blkmax 0xff00L /* <= 0xff00 ! */
  22.  
  23. #else /*__86__*/
  24.  
  25. #include <stdlib.h>
  26. #define memadd(p,i) ((p)+(i)+mcbsize)
  27.  
  28. #endif /*__86__*/
  29.  
  30. #define true 1
  31. #define false 0
  32.  
  33. #ifndef __386__
  34. #define bufsizmax 0xfff0 /* max size of memory buffer */
  35. #endif /*__386__*/
  36.  
  37. #define prev(memp) (((memptr)(memp)-1)->m_prev)
  38. #define next(memp) (((memptr)(memp)-1)->m_next)
  39. #define size(memp) (((memptr)(memp)-1)->m_size)
  40. #define datp(memp) (((memptr)(memp)-1)->m_datp)
  41. #ifdef __86__
  42. #define used(memp) (*((unsigned short*)&((memptr)(memp)-1)->m_datp+1))
  43. #else /*__86__*/
  44. #define used(memp) ((unsigned)(((memptr)(memp)-1)->m_datp))
  45. #endif /*__86__*/
  46.  
  47. typedef struct
  48.  {
  49.   mem_ptr m_prev; /* previous memory block */
  50.   mem_ptr m_next; /* next memory block */
  51.   long m_size; /* length of memory block without mcb */
  52.   mem_ptr* m_datp; /* pointer to pointer in user program */
  53.  } memrec; /*16*/
  54. typedef memrec FAR* memptr;
  55.  
  56. static long memfree; /* size of free memory */
  57. static mem_ptr memory; /* memory heap */
  58. static mem_ptr memend; /* end of memory */
  59.  
  60. #ifdef __86__
  61.  
  62. #ifndef __TURBOC__
  63. static mem_ptr hugeadd(mem_ptr p, long i)
  64.  {
  65.   i+=(unsigned short)p;
  66.   *((unsigned short*)&p+1) += (*((unsigned short*)&i+1)<<12)
  67.     + ((unsigned short)i>>4);
  68.   *(unsigned short*)&p = (unsigned short)i&15;
  69.   return(p);
  70.  }
  71. #endif /*__TURBOC__*/
  72.  
  73.  
  74. void hugemoveleft(void FAR* dst, void FAR* src, long len)
  75.  {
  76.   for ( ; len>blkmax; len-=blkmax)
  77.    {
  78.     moveleft((char FAR*)dst,(char FAR*)src,(unsigned)blkmax);
  79.     *((unsigned short*)&dst+1)+=((unsigned short)blkmax>>4);
  80.     *((unsigned short*)&src+1)+=((unsigned short)blkmax>>4);
  81.    }
  82.   moveleft((char FAR*)dst,(char FAR*)src,(unsigned)len);
  83.  }
  84.  
  85.  
  86. void hugemoveright(void FAR* dst, void FAR* src, long len)
  87.  {
  88.   int n;
  89.  
  90.   for (n=0; len>blkmax; len-=blkmax,n++)
  91.    {
  92.     *((unsigned short*)&dst+1)+=((unsigned short)blkmax>>4);
  93.     *((unsigned short*)&src+1)+=((unsigned short)blkmax>>4);
  94.    }
  95.   moveright((char FAR*)dst,(char FAR*)src,(unsigned)len);
  96.   for ( ; n>0; n--)
  97.    {
  98.     *((unsigned short*)&dst+1)-=((unsigned short)blkmax>>4);
  99.     *((unsigned short*)&src+1)-=((unsigned short)blkmax>>4);
  100.     moveright((char FAR*)dst,(char FAR*)src,(unsigned)blkmax);
  101.    }
  102.  }
  103.  
  104. #else /*__86__*/
  105.  
  106. #define hugemoveleft(d,s,l) moveleft(d,s,l)
  107. #define hugemoveright(d,s,l) moveright(d,s,l)
  108.  
  109. #endif /*__86__*/
  110.  
  111.  
  112. /* allocate allmost all of available memory in one block */
  113. void mem_init(long bufsize)
  114.  {
  115.   mem_ptr bufp; /* beginning of memory */
  116.  
  117. #ifdef __386__
  118.  
  119. #ifdef __ZTC__
  120. #if 0
  121.   memfree=_memmax()-16386; //_memmax() is useless
  122.   if (bufsize!=0 && memfree>bufsize)
  123.     memfree=bufsize;
  124.   bufp=malloc(memfree);
  125. #else /*0*/
  126.   int i;
  127.   unsigned len;
  128.   void* p[128];
  129.  
  130.   memfree=0;
  131.   if (bufsize!=0)
  132.    {
  133.     bufp=malloc(bufsize);
  134.     if (bufp!=NULL)
  135.       memfree=bufsize;
  136.    }
  137.  
  138.   if (memfree==0)
  139.    {
  140.     /* allocate all available memory */
  141.     len=1<<(8*sizeof(int)-1);
  142.     i=0;
  143.     do
  144.      {
  145.       p[i]=malloc(len-sizeof(int));
  146.       if (p[i]!=NULL)
  147.        {
  148.     memfree+=len;
  149.     i++;
  150.        }
  151.       else
  152.     len>>=1;
  153.      }
  154.     while (i<sizeof(p)/sizeof(*p) && len>=4096);
  155.  
  156.     /* free all pointers */
  157.     for (i--; i>=0; i--)
  158.       free(p[i]);
  159.  
  160.     memfree-=sizeof(int);
  161.  
  162.     /* allocate one big block */
  163.     for (;;)
  164.      {
  165.       bufp=malloc((unsigned)memfree);
  166.       if (bufp!=NULL)
  167.     break;
  168.       memfree-=1024;
  169.      }
  170.    }
  171. #endif /*0*/
  172. #endif /*__ZTC__*/
  173.  
  174. #else /*__386__*/
  175.  
  176. #ifdef __86__
  177.   memfree=farcoreleft();
  178.   if (bufsize!=0 && memfree>bufsize)
  179.     memfree=bufsize;
  180.   bufp=farmalloc(memfree);
  181. #else /*__86__*/
  182.   memfree=bufsizmax;
  183.   if (bufsize!=0 && memfree>bufsize)
  184.     memfree=bufsize;
  185.   for (;;)
  186.    {
  187.     bufp=malloc((unsigned)memfree);
  188.     if (bufp!=NULL)
  189.       break;
  190.     memfree-=1024;
  191.    }
  192. #endif /*__86__*/
  193.  
  194. #endif /*__386__*/
  195.  
  196.   memory=bufp+mcbsize;
  197.   prev(memory)=NULL;
  198.   next(memory)=NULL;
  199.   size(memory)=memfree-mcbsize;
  200.   datp(memory)=NULL;
  201.   memend=memadd(memory,memfree-mcbsize);
  202.  }
  203.  
  204.  
  205. /* free all memory */
  206. void mem_exit(void)
  207.  {
  208. #ifdef __86__
  209.   farfree(memory-mcbsize);
  210. #else /*__86__*/
  211.   free(memory-mcbsize);
  212. #endif /*__86__*/
  213.  }
  214.  
  215.  
  216. /* exchange used block with free block to the left */
  217. static void NEAR moveblockleft(mem_ptr memp0)
  218.  {
  219.   long size0;
  220.   mem_ptr memp9; /* prev block */
  221.   mem_ptr memp1; /* next block */
  222.  
  223.   memp9=prev(memp0);
  224.   memp1=next(memp0);
  225.   size0=size(memp0);
  226.   datp(memp9)=datp(memp0);
  227.   *datp(memp9)=memp9;
  228.   hugemoveleft(memp9,memp0,size0);
  229.   memp0=memadd(memp9,size0);
  230.   prev(memp0)=memp9;
  231.   next(memp0)=memp1;
  232.   size(memp0)=size(memp9);
  233.   datp(memp0)=NULL;
  234.   next(memp9)=memp0;
  235.   size(memp9)=size0;
  236.   if (memp1!=NULL)
  237.     prev(memp1)=memp0;
  238.  }
  239.  
  240.  
  241. /* exchange used block with free block to the right */
  242. static void NEAR moveblockright(mem_ptr memp0)
  243.  {
  244.   long size0;
  245.   mem_ptr memp1; /* next block */
  246.   mem_ptr memp2;
  247.  
  248.   memp1=next(memp0);
  249.   memp2=next(memp1);
  250.   size0=size(memp0);
  251.   size(memp0)=size(memp1);
  252.   memp1=memadd(memp0,size(memp0));
  253.   hugemoveright(memp1,memp0,size0);
  254.   prev(memp1)=memp0;
  255.   next(memp1)=memp2;
  256.   size(memp1)=size0;
  257.   datp(memp1)=datp(memp0);
  258.   *datp(memp1)=memp1;
  259.   next(memp0)=memp1;
  260.   datp(memp0)=NULL;
  261.   if (memp2!=NULL)
  262.     prev(memp2)=memp1;
  263.  }
  264.  
  265.  
  266. /* combine a block with the free block to the right */
  267. static void NEAR combineblock(mem_ptr memp0)
  268.  {
  269.   mem_ptr memp1; /* next block */
  270.   mem_ptr memp2;
  271.  
  272.   memp1=next(memp0);
  273.   memp2=next(memp1);
  274.   next(memp0)=memp2;
  275.   if (memp2!=NULL)
  276.     prev(memp2)=memp0;
  277.   size(memp0)+=size(memp1)+mcbsize;
  278.   if (used(memp0))
  279.     memfree-=size(memp1)+mcbsize;
  280.  }
  281.  
  282.  
  283. /* split a block */
  284. static void NEAR splitblock(mem_ptr memp0, long len)
  285.  {
  286.   long size0;
  287.   long size1;
  288.   mem_ptr memp1; /* next block */
  289.   mem_ptr memp2;
  290.  
  291.   size0=size(memp0);
  292.   size1=size0-len-mcbsize;
  293.   if (size1<0)
  294.     return;
  295.   memp2=next(memp0);
  296.   memp1=memadd(memp0,len);
  297.   next(memp0)=memp1;
  298.   size(memp0)=len;
  299.   prev(memp1)=memp0;
  300.   next(memp1)=memp2;
  301.   size(memp1)=size1;
  302.   datp(memp1)=NULL;
  303.   if (memp2!=NULL)
  304.     prev(memp2)=memp1;
  305.   if (used(memp0))
  306.     memfree+=size1+mcbsize;
  307.  }
  308.  
  309.  
  310. /* free memory */
  311. void mem_free(mem_ptr* mempp)
  312.  {
  313.   mem_ptr memp;
  314.  
  315.   memp=*mempp;
  316.   if (memp==NULL || datp(memp)!=mempp)
  317.     return;
  318.  
  319.   *mempp=NULL;
  320.   memfree+=size(memp)+mcbsize;
  321.   datp(memp)=NULL;
  322.   if (next(memp)!=NULL && !used(next(memp)))
  323.     combineblock(memp);
  324.   memp=prev(memp);
  325.   if (memp!=NULL && !used(memp))
  326.     combineblock(memp);
  327.  }
  328.  
  329.  
  330. /* allocate memory block */
  331. int mem_alloc(mem_ptr* mempp, long n, long sizen)
  332.  {
  333.   int unused;
  334.   long gap;
  335.   long diff;
  336.   long len;
  337.   long len2;
  338.   mem_ptr memp;
  339.   mem_ptr memp1;
  340.   mem_ptr memp2;
  341.  
  342.   sizen=(n*sizen+3)&~3;
  343.  
  344.   if (sizen==0)
  345.    {
  346.     mem_free(mempp);
  347.     return(true);
  348.    }
  349.  
  350.   memp=*mempp;
  351.   if (memp==NULL || datp(memp)!=mempp) /* new allocation */
  352.    {
  353.     /* search largest free block(, stop if large enough) */
  354.     len=-1;
  355.     memp=NULL;
  356.     for (memp1=memory; memp1!=NULL; memp1=next(memp1))
  357.       if (!used(memp1) && size(memp1)>len)
  358.        {
  359.     memp=memp1;
  360.     len=size(memp1);
  361.        }
  362.     if (memp==NULL) /* no free block */
  363.       return(false);
  364.  
  365.     /* if too large split it so there will be gaps */
  366.     gap=((len-sizen)/2-mcbsize)&~3;
  367.     if (gap>=256)
  368.      {
  369.       splitblock(memp,gap);
  370.       memp=next(memp);
  371.       len=size(memp);
  372.      }
  373.  
  374.     /* allocate this block */
  375.     memfree-=len+mcbsize;
  376.     datp(memp)=mempp;
  377.     *datp(memp)=memp;
  378.    }
  379.  
  380.   if (sizen==size(memp))
  381.     return(true);
  382.   if (sizen>size(memp)+memfree)
  383.     return(false);
  384.  
  385.   /* loop is perform at most twice */
  386.   do
  387.    {
  388.     /* block right is free: add it */
  389.     memp1=next(memp);
  390.     if (memp1!=NULL && !used(memp1))
  391.       combineblock(memp);
  392.     if (sizen<=size(memp))
  393.       break;
  394.  
  395.     /* block left is free and large enough: add it */
  396.     memp1=prev(memp);
  397.     if (memp1!=NULL && !used(memp1)
  398.       && sizen<=size(memp)+size(memp1)+mcbsize)
  399.      {
  400.       moveblockleft(memp);
  401.       memp=memp1;
  402.       combineblock(memp);
  403.       if (sizen<=size(memp))
  404.     break;
  405.      }
  406.  
  407.     /* search largest free block */
  408.     len2=-1;
  409.     memp2=NULL;
  410.     for (memp1=memory; memp1!=NULL; memp1=next(memp1))
  411.       if (!used(memp1) && size(memp1)>len2)
  412.        {
  413.     memp2=memp1;
  414.     len2=size(memp1);
  415.        }
  416.  
  417.     if (len2>=sizen)
  418.      {
  419.       /* if too large split it so the will be gaps */
  420.       gap=((len2-sizen)/2-mcbsize)&~3;
  421.       if (gap>=256)
  422.        {
  423.     splitblock(memp2,gap);
  424.     memp2=next(memp2);
  425.        }
  426.  
  427.       /* move the block to the found free block */
  428.       hugemoveleft(memp2,memp,size(memp));
  429.       datp(memp2)=datp(memp);
  430.       *datp(memp2)=memp2;
  431.       datp(memp)=NULL;
  432.       memfree+=size(memp)-size(memp2);
  433.       if (next(memp)!=NULL && !used(next(memp)))
  434.     combineblock(memp);
  435.       memp=prev(memp);
  436.       if (memp!=NULL && !used(memp))
  437.     combineblock(memp);
  438.       memp=memp2;
  439.       break;
  440.      }
  441.  
  442.     memp1=memp;
  443.     diff=sizen-size(memp);
  444.  
  445.     while (diff>0 && next(memp1)!=NULL)
  446.      {
  447.       memp1=next(memp1);
  448.       if (!used(memp1))
  449.     diff-=size(memp1)+mcbsize;
  450.      }
  451.  
  452.     /* move blocks right from current to the right */
  453.     unused=false;
  454.     while (memp1!=memp)
  455.      {
  456.       memp2=prev(memp1);
  457.       if (used(memp1))
  458.        {
  459.     if (unused)
  460.       moveblockright(memp1);
  461.        }
  462.       else
  463.        {
  464.     if (unused)
  465.       combineblock(memp1);
  466.     unused=true;
  467.        }
  468.       memp1=memp2;
  469.      }
  470.  
  471.     while (diff>0 && prev(memp1)!=NULL)
  472.      {
  473.       memp1=prev(memp1);
  474.       if (!used(memp1))
  475.     diff-=size(memp1)+mcbsize;
  476.      }
  477.  
  478.     /* move blocks left from current to the left */
  479.     unused=false;
  480.     while (memp1!=memp)
  481.      {
  482.       memp2=next(memp1);
  483.       if (used(memp1))
  484.        {
  485.     if (unused)
  486.       moveblockleft(memp1);
  487.        }
  488.       else
  489.        {
  490.     if (unused)
  491.       combineblock(prev(memp1));
  492.     unused=true;
  493.        }
  494.       memp1=memp2;
  495.      }
  496.    }
  497.   while (sizen>size(memp));
  498.  
  499.   splitblock(memp,sizen);
  500.  
  501.   return(true);
  502.  }
  503.  
  504.  
  505. /* return available memory */
  506. long mem_avail(void)
  507.  {
  508.   return(memfree>mcbsize?memfree-mcbsize:0);
  509.  }
  510.  
  511.  
  512. /* check memory control blocks, return 0 if ok */
  513. int mem_check(void)
  514.  {
  515.   mem_ptr memp;
  516.   mem_ptr memp1;
  517.   mem_ptr memp9;
  518.   long memfree1;
  519.   int memi;
  520.  
  521.   memfree1=0;
  522.   memp9=NULL;
  523.   for (memp=memory,memi=0; memp!=NULL; memp=next(memp),memi++)
  524.    {
  525.     if (prev(memp)!=memp9)
  526.       return(1);
  527.     memp1=memadd(memp,size(memp));
  528.     if (next(memp)==NULL)
  529.      {
  530.       if (memp1!=memend)
  531.     return(2);
  532.      }
  533.     else
  534.      {
  535.       if (next(memp)!=memp1)
  536.     return(3);
  537.      }
  538.     if (used(memp))
  539.      {
  540.       if (*datp(memp)!=memp)
  541.     return(4);
  542.      }
  543.     else
  544.       memfree1+=size(memp)+mcbsize;
  545.     memp9=memp;
  546.    }
  547.   if (memfree1!=memfree)
  548.     return(6);
  549.   return(0);
  550.  }
  551.  
  552. #ifdef __cplusplus
  553. }
  554. #endif
  555.