home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / adaptor.zip / adapt.zip / adaptor / src / memory.c < prev    next >
C/C++ Source or Header  |  1993-03-22  |  7KB  |  232 lines
  1. /* $Id: Memory.c,v 1.12 1992/05/05 13:19:05 grosch rel $ */
  2.  
  3. /* $Log: Memory.c,v $
  4.  * Revision 1.12  1992/05/05  13:19:05  grosch
  5.  * added rcsid
  6.  *
  7.  * Revision 1.11  1992/01/31  16:31:44  grosch
  8.  * adaption to ANSI C
  9.  *
  10.  * Revision 1.10  1992/01/30  13:16:06  grosch
  11.  * redesign of interface to operating system
  12.  *
  13.  * Revision 1.9  1992/01/14  15:24:35  grosch
  14.  * introduced automatic initialization
  15.  *
  16.  * Revision 1.8  1991/11/21  14:28:16  grosch
  17.  * new version of RCS on SPARC
  18.  *
  19.  * Revision 1.7  91/01/21  12:13:22  grosch
  20.  * some performance improvements
  21.  * 
  22.  * Revision 1.6  90/12/14  15:55:52  grosch
  23.  * introduced variable MemoryUsed
  24.  * 
  25.  * Revision 1.5  90/09/14  11:20:46  grosch
  26.  * removed superfluous declarations for automatic alignment
  27.  * 
  28.  * Revision 1.4  90/09/04  17:32:10  grosch
  29.  * automatic determination of alignment
  30.  * 
  31.  * Revision 1.3  90/07/04  14:33:58  grosch
  32.  * introduced conditional include
  33.  * 
  34.  * Revision 1.2  89/12/08  20:16:43  grosch
  35.  * added alignment for MIPS processor
  36.  * 
  37.  * Revision 1.1  89/06/06  10:28:54  grosch
  38.  * fixed lint problem at call of Free
  39.  * 
  40.  * Revision 1.0  88/10/04  11:44:41  grosch
  41.  * Initial revision
  42.  * 
  43.  */
  44.  
  45. /* Ich, Doktor Josef Grosch, Informatiker, Sept. 1987 */
  46.  
  47. static char rcsid [] = "$Id: Memory.c,v 1.12 1992/05/05 13:19:05 grosch rel $";
  48.  
  49. # include "ratc.h"
  50. # include "Memory.h"
  51. # include "System.h"
  52. # include "General.h"
  53. # include <stdio.h>
  54.  
  55. # define MinSizeSmallBlock    4
  56. # define MaxSizeSmallBlock    62    /* 64 - 2    */
  57. # define MinSizeLargeBlockLog    6    /* Log2 64    */
  58. # define MaxSizeLargeBlockLog    24    /* Log2 2**24    */
  59. # define PoolSize        10240L
  60. # define cNoMoreSpace        -1
  61. # define NIL            (tBlockPtr) NULL
  62.  
  63. unsigned long MemoryUsed = 0;
  64.  
  65. struct tBlock {
  66.    struct tBlock *    Successor;
  67.    unsigned long    Size;
  68. };
  69. typedef struct tBlock *    tBlockPtr;
  70. typedef cardinal    tSmallBlockRange;
  71. typedef cardinal    tLargeBlockRange;
  72.  
  73. static    tBlockPtr    SmallChain [MaxSizeSmallBlock    + 1] = { 0,
  74.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  75.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  76.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  77.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  78.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  79.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  80.    NIL, NIL,
  81. };
  82. static    tBlockPtr    LargeChain [MaxSizeLargeBlockLog + 1] = { 0,
  83.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  84.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  85.    NIL, NIL, NIL, NIL,
  86. };
  87. static    char *        PoolFreePtr = 0;
  88. static    char *        PoolEndPtr  = 0;
  89.  
  90. char * Alloc (ByteCount)
  91.    register unsigned long ByteCount;
  92.  
  93. /* Returns a pointer to dynamically allocated    */
  94. /* space of size 'ByteCount' bytes.        */
  95.  
  96. {
  97.    ByteCount = (ByteCount + yyMaxAlign - 1) & yyAlignMasks [yyMaxAlign];
  98.  
  99.    if (ByteCount <= MaxSizeSmallBlock) {    /* handle small block */
  100.       if (ByteCount < MinSizeSmallBlock) ByteCount = MinSizeSmallBlock;
  101.       if (SmallChain [ByteCount] != NIL) {    /* obtain block from freelist */
  102.      register tBlockPtr CurrentBlock = SmallChain [ByteCount];
  103.      SmallChain [ByteCount] = CurrentBlock->Successor;
  104.      return (char *) CurrentBlock;
  105.       } else {                    /* obtain block from storage pool */
  106.      register unsigned long FreeBytes;
  107.      register char *    OldFreePtr;
  108.                         /* release old pool */
  109.      if ((FreeBytes = PoolEndPtr - PoolFreePtr) < ByteCount) {
  110.         if (FreeBytes >= MinSizeSmallBlock) Free (FreeBytes, PoolFreePtr);
  111.         PoolFreePtr = Alloc (PoolSize);    /* allocate new pool */
  112.         PoolEndPtr  = PoolFreePtr + PoolSize;
  113.      }
  114.      OldFreePtr = PoolFreePtr;
  115.      PoolFreePtr += ByteCount;
  116.      return OldFreePtr;
  117.       }
  118.    } else {                    /* handle large block */
  119.  
  120.       /* 1. search in LargeChain [Log2 (ByteCount)] using BEST FIT */
  121.  
  122.       register cardinal        ChainNumber    = Log2 (ByteCount);
  123.       register tBlockPtr    CurrentBlock    = LargeChain [ChainNumber];
  124.       register tBlockPtr    PreviousBlock    = (tBlockPtr) & (LargeChain [ChainNumber]);
  125.       register tBlockPtr    BestBlock    = NIL;
  126.       register unsigned long    BestBlockSize    = 1000000000;
  127.       register tBlockPtr    PredecessorBlock;
  128.       register tLargeBlockRange    j        ;
  129.       register unsigned long    CurrentBlockSize;
  130.  
  131.       while (CurrentBlock) {
  132.      CurrentBlockSize = CurrentBlock->Size;
  133.      if (CurrentBlockSize >= ByteCount) {
  134.         if (CurrentBlockSize == ByteCount) { /* exact match */
  135.            PreviousBlock->Successor = CurrentBlock->Successor;
  136.            return (char *) CurrentBlock;
  137.         }
  138.         if (CurrentBlockSize < BestBlockSize) { /* improve approximation */
  139.            BestBlock    = CurrentBlock;
  140.            BestBlockSize    = CurrentBlockSize;
  141.            PredecessorBlock    = PreviousBlock;
  142.         }
  143.      }
  144.      PreviousBlock    = CurrentBlock;
  145.      CurrentBlock    = CurrentBlock->Successor;
  146.       }
  147.  
  148.       if (BestBlock) {
  149.      PredecessorBlock->Successor = BestBlock->Successor;
  150.      if (BestBlockSize - ByteCount >= MinSizeSmallBlock) {
  151.         Free (BestBlockSize - ByteCount, (char *) BestBlock + ByteCount);
  152.      }
  153.      return (char *) BestBlock;
  154.       }
  155.  
  156.       /* 2. search in LargeChain [j], j > Log2 (ByteCount), using FIRST FIT */
  157.  
  158.       for (j = ChainNumber+1; j <= MaxSizeLargeBlockLog; j ++) {
  159.      CurrentBlock = LargeChain [j];
  160.      if (CurrentBlock != NIL) {
  161.         LargeChain [j] = CurrentBlock->Successor;
  162.         if (CurrentBlock->Size - ByteCount >= MinSizeSmallBlock) {
  163.            Free (CurrentBlock->Size - ByteCount, (char *) CurrentBlock + ByteCount);
  164.         }
  165.         return (char *) CurrentBlock;
  166.      }
  167.       }
  168.  
  169.       if (ByteCount < PoolSize) {        /* 3. obtain block from storage pool */
  170.      register unsigned long FreeBytes;
  171.                         /* release old pool */
  172.      if ((FreeBytes = PoolEndPtr - PoolFreePtr) < ByteCount) {
  173.         if (FreeBytes >= MinSizeSmallBlock) Free (FreeBytes, PoolFreePtr);
  174.         PoolFreePtr = Alloc (PoolSize);    /* allocate new pool */
  175.         PoolEndPtr  = PoolFreePtr + PoolSize;
  176.      }
  177.      PoolFreePtr += ByteCount;
  178.      return PoolFreePtr - ByteCount;
  179.       } else {                    /* 4. allocate individual block */
  180.      CurrentBlock = (tBlockPtr) SysAlloc ((long) ByteCount);
  181.      if ((long) CurrentBlock == cNoMoreSpace) {
  182.         return (char *) NULL;
  183.      } else {
  184.         MemoryUsed += ByteCount;
  185.         return (char *) CurrentBlock;
  186.      }
  187.       }
  188.    }
  189. }
  190.  
  191. void Free (ByteCount, a)
  192.    unsigned long    ByteCount;
  193.    char *        a;
  194.  
  195. /* The dynamically allocated space starting at    */
  196. /* address 'a' of size 'ByteCount' bytes is    */
  197. /* released.                    */
  198.  
  199. {
  200.    register tBlockPtr        BlockPtr;
  201.    register tLargeBlockRange    ChainNumber;
  202.  
  203.    ByteCount = (ByteCount + yyMaxAlign - 1) & yyAlignMasks [yyMaxAlign];
  204.  
  205.    BlockPtr = (tBlockPtr) a;
  206.    if (ByteCount <= MaxSizeSmallBlock) {
  207.       if (ByteCount < MinSizeSmallBlock) ByteCount = MinSizeSmallBlock;
  208.       BlockPtr->Successor    = SmallChain [ByteCount];
  209.       SmallChain [ByteCount]    = BlockPtr;
  210.    } else {
  211.       ChainNumber        = Log2 (ByteCount);
  212.       BlockPtr->Successor    = LargeChain [ChainNumber];
  213.       BlockPtr->Size        = ByteCount;
  214.       LargeChain [ChainNumber]    = BlockPtr;
  215.    }
  216. }
  217.  
  218. void InitMemory ()
  219. {
  220.    register int i;
  221.  
  222.    for (i = MinSizeSmallBlock; i <= MaxSizeSmallBlock; i += 2) {
  223.       SmallChain [i] = NIL;
  224.    }
  225.    for (i = MinSizeLargeBlockLog; i <= MaxSizeLargeBlockLog; i ++) {
  226.       LargeChain [i] = NIL;
  227.    }
  228.    MemoryUsed    = 0;
  229.    PoolFreePtr    = 0;
  230.    PoolEndPtr    = 0;
  231. }
  232.