home *** CD-ROM | disk | FTP | other *** search
/ High Voltage Shareware / high1.zip / high1 / DIR24 / BASH_112.ZIP / BASH-112.TAR / bash-1.12 / malloc.c < prev    next >
C/C++ Source or Header  |  1993-10-09  |  10KB  |  378 lines
  1. /* Package of programs to manage the near heap.  Implemented because of
  2.    the juvinile beharior of the Borland reallocation procedure.  Attempts
  3.    to ensure that links have not been corrupted, and exits with an error
  4.    message and bad status if they have.  All aborts are made through the
  5.    common routine
  6.             bombOut().
  7.    This enables the user to trap the stack at the point of the exit by
  8.    use of the debugger.
  9. */
  10. #include <os2.h>
  11. #include "stddef.h"
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. unsigned     _mallocAllocBlocks;
  16.  
  17. static char            *noInit="Message control structure not initialized\n";
  18. static char            *badStructure="Message control structures corrupted\n";
  19. static char            *cantCommit="Can't commit memory\n";
  20. static char            *noAlloc = "Can't allocate mem\n";
  21. static int            controlSize;
  22. static int            noInitFlag = 1;
  23. struct memControl{
  24.     struct memControl    *next;
  25.     unsigned            count;
  26.     ULONG                checkValue;
  27.     struct _sysMemST    *sysControl;
  28.     };
  29. typedef struct memControl        userMemST;
  30. typedef struct _sysMemST{
  31.     ULONG        signature;
  32.     userMemST    *freeChain;
  33.     ULONG        allocated;        /* size of block as received from
  34.                                    system call */
  35.     ULONG        noCommitSize;
  36.     PVOID        firstByte;
  37.     PVOID        noCommitMem;
  38.     } sysMemST;
  39. #define CHECK_VALUE    0xA6A6A6A6
  40. #define NUM_ALLOC_BLKS 1000
  41. #define COMMIT_SIZE 8192
  42. #define FULL_BLOCK(i, size) i&(size-1)? (i&(~(size-1)))+size: i
  43.  
  44. static sysMemST                    sysControlBlock;
  45. static userMemST                *currentFreeList;
  46. static struct memControl        *predecessor,        /* used when finding list*/
  47.                                 *prePredecessor;    /* position */
  48.  
  49. static int            abut(struct memControl *, struct memControl*);
  50. static void            addList(struct memControl*);
  51. void                bombOut(char *);
  52. static struct memControl    *combine(struct memControl *);
  53. void                free(void *);
  54. static int            initMem(sysMemST *);
  55. static void            listPosition(struct memControl *);
  56. static struct memControl    *splitBlock(unsigned);
  57.  
  58.  
  59. /* ******************************** ABUT ******************************* */
  60. /* determine if two blocks are contiguous */
  61. static int        abut(blk1, blk2)
  62. struct memControl        *blk1,
  63.                         *blk2;
  64.  
  65. {unsigned        holeSize;
  66. void            *raw1,
  67.                 *raw2;
  68.  
  69. if(blk1==NULL || blk2==NULL)
  70.     return 0;
  71. holeSize = (char *)blk2 - (char *)blk1 - (blk1->count+controlSize);
  72. if(holeSize >0)
  73.     return 0;
  74. if(holeSize == 0)
  75.     return 1;
  76. bombOut(badStructure);
  77. }
  78.  
  79. /* ****************************** ADD_LIST ***************************** */
  80. /* add a block to the free list.  Predecessor must be defined */
  81. static void            addList(block)
  82. struct memControl        *block;
  83. {
  84. if(predecessor == NULL)
  85.     {block->next = block->sysControl->freeChain;
  86.     block->sysControl->freeChain = block;
  87.     currentFreeList = block;
  88.     return;
  89.     }
  90. block->next = predecessor->next;
  91. predecessor->next = block;
  92. return;
  93. }
  94.  
  95. /* ****************************** BOMB_OUT ***************************** */
  96. void        bombOut(mssg)
  97. char        *mssg;
  98.  
  99. {printf(mssg);
  100. exit(1);
  101. }
  102.  
  103. /* ****************************** CALLOC ******************************* */
  104. void            *calloc(num, size)
  105. size_t            num,
  106.                 size;
  107. {void        *blk;
  108.  
  109. blk = malloc(num*size);
  110. if(!blk)
  111.     return NULL;
  112. memset(blk, 0, num*size);
  113. return blk;
  114. }
  115.  
  116. /* ****************************** COMBINE ****************************** */
  117. /* combine input block with its successor block if they are contiguous.
  118.    Returns pointer to combined block if successful, else pointer to
  119.    successor block
  120. */
  121.  
  122. static struct memControl        *combine(block)
  123. struct memControl        *block;
  124.  
  125. {
  126. if(block == NULL)
  127.     return currentFreeList;
  128. if(abut(block, block->next))
  129.     {block->count += (block->next->count + controlSize);
  130.     block->next = block->next->next;
  131.     return block;
  132.     }
  133. return block->next;
  134. }
  135.  
  136. /* ******************************* FREE ******************************** */
  137. void            free(inData)
  138. void            *inData;
  139. {struct memControl        *memBlock;
  140.  
  141. if(!inData)
  142.     return;
  143. if(noInitFlag)
  144.     bombOut(noInit);
  145. memBlock = (struct memControl *)((char *)inData - controlSize);
  146. currentFreeList = memBlock->sysControl->freeChain;
  147. listPosition(memBlock);
  148. addList(memBlock);
  149. combine(combine(predecessor));
  150. return;
  151. }
  152.  
  153. /* ***************************** INIT_MEM ****************************** */
  154. static int            initMem(sysMemST *sysControlBlock)
  155. {struct memControl    *trueStart;
  156. unsigned        i,
  157.                 length;
  158. void            *pBaseAddress;
  159.  
  160. i = _mallocAllocBlocks? _mallocAllocBlocks: NUM_ALLOC_BLKS;
  161. length = 4096*i;
  162. if(DosAllocMem(&pBaseAddress, length, PAG_READ|PAG_WRITE))
  163.     return 1;
  164. sysControlBlock->allocated = length;
  165. sysControlBlock->signature = CHECK_VALUE;
  166. sysControlBlock->noCommitMem = pBaseAddress;
  167. sysControlBlock->noCommitSize = length;
  168. sysControlBlock->freeChain = NULL;
  169. sysControlBlock->firstByte = pBaseAddress;
  170. controlSize = sizeof(struct memControl);
  171. if(controlSize & 3)
  172.     controlSize = (controlSize & 0xfffc) + 4;
  173. noInitFlag = 0;
  174. return 0;
  175. }
  176.  
  177. /* *************************** LIST_POSITION *************************** */
  178. /* Find the block immediately proceeding the input block.  Sets the static
  179.    variables predecessor and prePredecessor
  180. */
  181.  
  182. static void        listPosition(block)
  183. struct memControl        *block;
  184.  
  185. {struct memControl        *work;
  186.  
  187. predecessor = NULL;
  188. prePredecessor = NULL;
  189. for(work = block->sysControl->freeChain;    work != NULL;    work=work->next)
  190.     {if(work > block)
  191.         break;
  192.     prePredecessor = predecessor;
  193.     predecessor = work;
  194.     }
  195. return;
  196.  
  197. }
  198.  
  199. /* ****************************** MALLOC ******************************* */
  200. void            *malloc(num)
  201. size_t        num;
  202.  
  203. {struct memControl        *work;
  204. int                    doAbut,
  205.                     i,
  206.                     toCommit,
  207.                     useCommited;
  208. char                *pd,
  209.                     *dataBlock;
  210. sysMemST            *sysControl;
  211. ULONG                result;
  212.  
  213. if(!num)
  214.     return NULL;
  215. sysControl = &sysControlBlock;
  216. if(noInitFlag)
  217.     initMem(sysControl);
  218. num = FULL_BLOCK(num, 4);
  219. prePredecessor = NULL;
  220. predecessor = NULL;
  221. for(work = sysControl->freeChain;    work != NULL;    work = work->next)
  222.     {if(work->count > num)
  223.         {(void)splitBlock(num);
  224.         dataBlock = (char *)work + controlSize;
  225.         return dataBlock;
  226.         }
  227.     prePredecessor = predecessor;
  228.     predecessor = work;
  229.     }
  230. if(predecessor)
  231.     doAbut = (predecessor->count+predecessor+controlSize) == sysControl->noCommitMem;
  232. else
  233.     doAbut = 0;
  234. useCommited = doAbut?    predecessor->count:    0;
  235. if(useCommited+sysControl->noCommitSize < num)
  236.     return NULL;
  237. toCommit = num-useCommited;
  238. toCommit = FULL_BLOCK(toCommit, COMMIT_SIZE);
  239. if((result = DosSetMem(sysControl->noCommitMem, toCommit, 
  240.                 PAG_COMMIT|PAG_READ|PAG_WRITE)))
  241.     bombOut(cantCommit);
  242. work = (userMemST *) sysControl->noCommitMem;
  243. work->checkValue = CHECK_VALUE;
  244. work->next = NULL;
  245. work->count = toCommit-controlSize;
  246. work->sysControl = sysControl;
  247. if(predecessor)
  248.     predecessor->next = work;
  249. else
  250.     sysControl->freeChain = work;
  251. sysControl->noCommitSize -= toCommit;
  252. sysControl->noCommitMem += toCommit;
  253. currentFreeList = work->sysControl->freeChain;
  254. if(doAbut)
  255.     work = combine(predecessor);
  256. return malloc(num);
  257. }
  258.  
  259. /* *************************** REALLOC ***************************** */
  260.  
  261. void            *realloc(inputData,num)
  262. void            *inputData;
  263. size_t            num;
  264.  
  265. {struct memControl    *newBlock,
  266.                     *oldPredecessor,
  267.                     *SP,
  268.                     *testBlock;
  269. sysMemST            *sysControl;
  270. char            *pd,
  271.                 *ps;
  272. unsigned        availP,
  273.                 availS,
  274.                 i,
  275.                 toMove;
  276. void            *newData;
  277.  
  278. sysControl = &sysControlBlock;
  279. if(noInitFlag)
  280.     bombOut(noInit);
  281. SP = (struct memControl *)((char *)inputData - controlSize);
  282. if(SP->checkValue != CHECK_VALUE)
  283.     {bombOut(badStructure);
  284.     exit(1);
  285.     }
  286. currentFreeList = SP->sysControl->freeChain;
  287. toMove = SP->count;
  288. listPosition(SP);
  289. if(toMove > num)        /* New block will fit inside the old one */
  290.     {addList(SP);
  291.     (void)combine(SP);
  292.     splitBlock(num);
  293.     return inputData;
  294.     }
  295. availP = 0;
  296. availS = 0;
  297. if(abut(predecessor, SP))
  298.     availP = predecessor->count + controlSize;
  299. if(predecessor != NULL)
  300.     testBlock = predecessor->next;
  301. else
  302.     testBlock = sysControl->freeChain;
  303. if(abut(SP, testBlock))
  304.     availS = testBlock->count + controlSize;
  305. if(availP+availS+SP->count >= num)        /* append old block to an adjacent one */
  306.     {addList(SP);
  307.     newBlock = combine(predecessor);
  308.     (void)combine(newBlock);
  309.     if(newBlock == predecessor)
  310.         predecessor = prePredecessor;
  311.     (void)splitBlock(num);
  312.     pd = (char *)SP + controlSize + toMove;
  313.     if(newBlock != SP)
  314.         {for(i=0, ps=(char *)SP+controlSize, pd=(char *)newBlock+controlSize;
  315.           i < toMove;    ++i)
  316.             *pd++ = *ps++;
  317.         }
  318.     for(i=toMove;    i<newBlock->count;    ++i)
  319.         *pd++ = 0;
  320.     return (char *)newBlock + controlSize;
  321.     }
  322. newData = malloc(num);
  323. if(newData == NULL)
  324.     return NULL;
  325. free(inputData);
  326. pd = newData;
  327. ps = inputData;
  328. if(pd < ps)
  329.     {for(i=0;    i<toMove;    ++i)
  330.         *pd++ = *ps++;
  331.     }
  332. else
  333.     {pd += toMove;
  334.     ps += toMove;
  335.     for(i=0; i<toMove;    ++i)
  336.         *(--pd) = *(--ps);
  337.     }
  338. return newData;
  339.  
  340. }
  341.  
  342. /* **************************** SPLIT_BLOCK *************************** */
  343. /* allocate bytes from the block which follows predecessor */
  344.  
  345. static struct memControl        *splitBlock(numBytes)
  346. unsigned                numBytes;
  347.  
  348. {struct memControl        *block,
  349.                         **link,
  350.                         *newBlock;
  351. sysMemST                *sysControl;
  352. unsigned                bytesLeft;
  353.  
  354. sysControl = &sysControlBlock;
  355. if(predecessor == NULL)
  356.     {block = sysControl->freeChain;
  357.     link = &sysControl->freeChain;
  358.     }
  359. else
  360.     {block = predecessor->next;
  361.     link = &predecessor->next;
  362.     }
  363. if(block->count <= (numBytes+controlSize))
  364.     {*link = block->next;        /* no room for an extra control structure, so
  365.                                    can't split block */
  366.     return block;
  367.     }
  368. bytesLeft = block->count - controlSize - numBytes;
  369. newBlock = (struct memControl *)((char *)block + numBytes + controlSize);
  370. newBlock->next = block->next;
  371. newBlock->count = bytesLeft;
  372. newBlock->checkValue = CHECK_VALUE;
  373. newBlock->sysControl = block->sysControl;
  374. *link = newBlock;
  375. block->count = numBytes;
  376. return block;
  377. }
  378.