Facebook
From Paltry Sloth, 4 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 206
  1. // COMP1521 19t2 ... Assignment 2: heap management system
  2.  
  3. #include <assert.h>
  4. #include <stdint.h>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8.  
  9. #include "myHeap.h"
  10.  
  11. /** minimum total space for heap */
  12. #define MIN_HEAP 4096
  13. /** minimum amount of space for a free Chunk (includes Header) */
  14. #define MIN_CHUNK 32
  15.  
  16.  
  17. #define ALLOC 0x55555555
  18. #define FREE  0xAAAAAAAA
  19.  
  20. /// Types:
  21.  
  22. typedef unsigned int  uint;
  23. typedef unsigned char byte;
  24.  
  25. typedef uintptr_t     addr; // an address as a numeric type
  26.  
  27. /** The header for a chunk. */
  28. typedef struct header {
  29.         uint status;    /**< the chunk's status -- ALLOC or FREE */
  30.         uint size;      /**< number of bytes, including header */
  31.         byte data[];    /**< the chunk's data -- not interesting to us */
  32. } header;
  33.  
  34. /** The heap's state */
  35. struct heap {
  36.         void  *heapMem;     /**< space allocated for Heap */
  37.         uint   heapSize;    /**< number of bytes in heapMem */
  38.         void **freeList;    /**< array of pointers to free chunks */
  39.         uint   freeElems;   /**< number of elements in freeList[] */
  40.         uint   nFree;       /**< number of free chunks */
  41. };
  42.  
  43.  
  44. /// Variables:
  45.  
  46. /** The heap proper. */
  47. static struct heap Heap;
  48.  
  49.  
  50. /// Functions:
  51.  
  52. static addr heapMaxAddr (void);
  53.  
  54. // function to round up to next multiple if necessary
  55. static int roundup(int numToRoundUp, int multiple);
  56.  
  57. // function returns index of supplied chunk
  58. static int indexOfFreeChunk(header *chunk);
  59.  
  60. // function readjusts pointers after removal from freeList
  61. static void readjustPointers(int indexChunk);
  62.  
  63. /** Initialise the Heap. */
  64. int initHeap (int size)
  65. {
  66.    
  67.        
  68.         /// TODO ///
  69.     if (size < MIN_HEAP) {
  70.         size = MIN_HEAP;
  71.     }
  72.    
  73.     size = roundup(size, 4);
  74.     // heapMem is pointing to a chunk
  75.     Heap.heapMem = malloc(size);
  76.     if (Heap.heapMem == NULL) {
  77.         fprintf(stderr, "malloc failed\n");
  78.         exit(-1);
  79.     }
  80.     // set heapMem to be all zeroes, memset returns pointer to chunk
  81.    
  82.     Heap.heapMem = memset(Heap.heapMem, 0, size);
  83.    
  84.     Heap.heapSize = size;
  85.     // pointer to chunkHeader
  86.     header *chunkHeader = (header *)(Heap.heapMem);
  87.    
  88.     // setting heapMem to be a single free chunk of size;
  89.    
  90.     chunkHeader->size = size;
  91.     chunkHeader->status = FREE;
  92.    
  93.     Heap.freeElems = 1;
  94.     Heap.freeList = malloc(Heap.freeElems * sizeof(void *));
  95.     if (Heap.freeList == NULL) {
  96.         fprintf(stderr, "malloc failed\n");
  97.         exit(-1);
  98.     }
  99.     Heap.freeList[0] = chunkHeader; // check???
  100.     Heap.nFree = 1;
  101.    
  102.    
  103.        
  104.        
  105.    
  106.    
  107.         return 0; // this just keeps the compiler quiet
  108. }
  109.  
  110. /** Release resources associated with the heap. */
  111. void freeHeap (void)
  112. {
  113.         free (Heap.heapMem);
  114.         free (Heap.freeList);
  115. }
  116.  
  117. /** Allocate a chunk of memory large enough to store `size' bytes. */
  118. void *myMalloc (int size)
  119. {
  120.         /// TODO ///
  121.         if (size < 1) {
  122.             return NULL;
  123.     }
  124.     size = roundup(size, 4);
  125.     // round up size to nearest multiple of 4 if necessary
  126.        
  127.     // find the first chunk that fits
  128.     // check if I have found minimum if not return null
  129.     // start up another loop to update minimum chunk
  130.    
  131.     header *minChunk;
  132.     /* for (int i = 0; i < Heap.freeElems; i++) {
  133.         header *currentChunk = (header *) Heap.freeList[i];
  134.        
  135.        
  136.         if (currentChunk->size >= size + sizeof(header)) {
  137.             minChunk = currentChunk;
  138.             break;
  139.         }
  140.     } */
  141.    
  142.     int i = 0;
  143.     int j;
  144.    
  145.    
  146.     while (i < Heap.freeElems) {
  147.         header *currentChunk = (header *) Heap.freeList[i];
  148.        
  149.         if (currentChunk->size >= size + sizeof(header)) {
  150.             minChunk = currentChunk;
  151.             j = i + 1;
  152.             break;
  153.         }
  154.         i++;
  155.     }
  156.        
  157.        
  158.     // didn't find any chunk that fits
  159.    
  160.     if (minChunk == NULL) {
  161.         return NULL;
  162.     }
  163.    
  164.     // finding min available chunk
  165.    
  166.    
  167.     while (j < Heap.freeElems) {
  168.         header *currentChunk = (header *) Heap.freeList[j];
  169.         if ( (currentChunk->size >= size + sizeof(header))
  170.         && (currentChunk->size < minChunk->size) ) {
  171.             minChunk = currentChunk;
  172.         }
  173.         j++;
  174.     }
  175.        
  176.    
  177.     if (minChunk->size >= size + sizeof(header) + MIN_CHUNK) {
  178.        
  179.         // split and make excess a new small free chunk
  180.         // allocating space for "size"
  181.         header *allocatedChunk = minChunk;
  182.         allocatedChunk->status = ALLOC;
  183.        
  184.        
  185.  
  186.         // calculating excessSize
  187.         header * newChunkHeader = (header *)
  188.                             ((addr) allocatedChunk + size + sizeof(header));
  189.        
  190.         uint excessSize = minChunk->size - (size + sizeof(header));
  191.         printf("excessSize = %d\n", excessSize);
  192.         allocatedChunk->size = size + sizeof(header);
  193.         newChunkHeader->size = excessSize;
  194.         newChunkHeader->status = FREE;
  195.        
  196.         // readjusting pointer
  197.        
  198.         Heap.freeList[ indexOfFreeChunk(allocatedChunk) ] = newChunkHeader;
  199.         return ( (void *) ( (addr) allocatedChunk + sizeof(header)) );
  200.        
  201.     } else {
  202.        
  203.         // allocate whole chunk
  204.         minChunk->status = ALLOC;
  205.         // readjust pointers from minChunk onwards
  206.         readjustPointers( indexOfFreeChunk(minChunk) );
  207.         Heap.nFree--;
  208.        
  209.         return ( (void *) ( (addr) minChunk + sizeof(header)) );
  210.     }
  211.            
  212.     return 0; // this just keeps the compiler quiet
  213. }
  214.    
  215.        
  216.        
  217.            
  218.            
  219.    
  220.            
  221.            
  222.            
  223.            
  224.            
  225.            
  226.            
  227.                
  228.            
  229.            
  230.            
  231.            
  232.              
  233.            
  234.            
  235.        
  236.            
  237.        
  238.            
  239.            
  240.            
  241.            
  242.            
  243.  
  244. /** Deallocate a chunk of memory. */
  245. void myFree (void *obj)
  246. {
  247.         /// TODO ///
  248.        
  249.         //
  250.     /* int flag = 0;
  251.     addr iterationChunk = (addr) Heap.heapMem;
  252.     while (iterationChunk < heapMaxAddr ()) {
  253.         header *chunk = (header *) iterationChunk;
  254.         if ( chunk->status == ALLOC
  255.             && (void *) ((addr) chunk + sizeof(header)) == obj) {
  256.             flag = 1;
  257.         }
  258.         iterationChunk += chunk->size;
  259.     }
  260.    
  261.     if (flag == 0) {
  262.         fprintf( stderr, "Attempt to free unallocated chunk\n");
  263.         exit(1);
  264.     }
  265.        
  266.    
  267.     // freeing chunk
  268.     header *freedChunk = (header *) ( (addr) obj - sizeof(header) );
  269.     obj = memset(obj, 0, freedChunk->size - sizeof(header));
  270.     freedChunk->status = FREE;
  271.    
  272.    
  273.    
  274.     // readjust pointers in freeList
  275.    
  276.     // find chunks adjacent to freeChunk and check if they are free
  277.     // if so merge them
  278.    
  279.    
  280.    
  281.     // iterate chunk by chunk
  282.     addr curr = (addr) Heap.heapMem;
  283.         while (curr < heapMaxAddr ()) {
  284.                 header *currChunk = (header *) curr;
  285.                
  286.                 // behindChunk and aheadChunk are check variables
  287.         header *behindChunk = currChunk;
  288.                 header *aheadChunk = currChunk;
  289.                
  290.                 // currChunk is behind freedChunk
  291.                 if ( (header *) ( (addr) currChunk + currChunk->size) == freedChunk ) {
  292.                
  293.                 if (currChunk->status == FREE) {
  294.                
  295.                 // merging
  296.                
  297.                 // adding chunk sizes
  298.                 behindChunk->size = behindChunk->size + freedChunk->size;
  299.                 // removing header of freedChunk
  300.                 freedChunk = memset(freedChunk, 0, sizeof(header));
  301.                 // find pointer which points to currChunk in freeList[]
  302.                 // readjust it to point at currChunk the trailing chunk
  303.                 for (int i = 0; i < Heap.freeElems; i++) {
  304.                     header *chunk = (header *) Heap.freeList[i];
  305.                     if (chunk == currChunk) {
  306.                         Heap.freeList[i] = behindChunk;
  307.                     }
  308.                 }
  309.                
  310.                 }
  311.        
  312.         // currChunk is ahead of freedChunk - there is an aheadChunk
  313.         } else if (currChunk == (header *)
  314.                                 ( (addr) freedChunk + freedChunk->size) ) {
  315.            
  316.            
  317.             if (currChunk->status == FREE) {
  318.                
  319.                 // case where there was a trailing free chunk already added
  320.                 if (behindChunk != currChunk) {
  321.                    
  322.                     behindChunk->size = behindChunk->size + aheadChunk->size;
  323.                     aheadChunk = memset(aheadChunk, 0, sizeof(header));              
  324.                     // adjust pointers from currChunk onwards
  325.                     readjustPointers( indexOfFreeChunk(currChunk) );
  326.                    
  327.                    
  328.                    
  329.                    
  330.                    
  331.                 } else {
  332.                     // adjust current pointer to point at freedChunk
  333.                 }
  334.             }
  335.         }
  336.         curr += currChunk->size;
  337.     } */
  338.                  
  339. }
  340.  
  341. /** Return the first address beyond the range of the heap. */
  342. static addr heapMaxAddr (void)
  343. {
  344.         return (addr) Heap.heapMem + Heap.heapSize;
  345. }
  346.  
  347. /** Convert a pointer to an offset in the heap. */
  348. int heapOffset (void *obj)
  349. {
  350.         addr objAddr = (addr) obj;
  351.         addr heapMin = (addr) Heap.heapMem;
  352.         addr heapMax =        heapMaxAddr ();
  353.         if (obj == NULL || !(heapMin <= objAddr && objAddr < heapMax))
  354.                 return -1;
  355.         else {
  356.                 return (int) (objAddr - heapMin);
  357.     }
  358. }
  359. /** Dump the contents of the heap (for testing/debugging). */
  360. void dumpHeap (void)
  361. {
  362.         int onRow = 0;
  363.  
  364.         // We iterate over the heap, chunk by chunk; we assume that the
  365.         // first chunk is at the first location in the heap, and move along
  366.         // by the size the chunk claims to be.
  367.         addr curr = (addr) Heap.heapMem;
  368.         while (curr < heapMaxAddr ()) {
  369.                 header *chunk = (header *) curr;
  370.  
  371.                 char stat;
  372.                 switch (chunk->status) {
  373.                 case FREE:  stat = 'F'; break;
  374.                 case ALLOC: stat = 'A'; break;
  375.                 default:
  376.                         fprintf (
  377.                                 stderr,
  378.                                 "myHeap: corrupted heap: chunk status %08x\n",
  379.                                 chunk->status
  380.                         );
  381.                         exit (1);
  382.                 }
  383.  
  384.                 printf (
  385.                         "+%05d (%c,%5d)%c",
  386.                         heapOffset ((void *) curr),
  387.                         stat, chunk->size,
  388.                         (++onRow % 5 == 0) ? '\n' : ' '
  389.                 );
  390.  
  391.                 curr += chunk->size;
  392.         }
  393.  
  394.         if (onRow % 5 > 0)
  395.                 printf ("\n");
  396. }
  397.  
  398. static int roundup(int numToRoundUp, int multiple) {
  399.  
  400.     int remainder = numToRoundUp % multiple;
  401.     if (remainder != 0) {
  402.         return numToRoundUp = numToRoundUp + multiple - remainder;
  403.     } else {
  404.         return numToRoundUp;
  405.     }
  406.  
  407. }
  408.  
  409. static int indexOfFreeChunk(header *chunk) {
  410.    
  411.     for (int i = 0; i < Heap.freeElems; i++) {
  412.         header *currChunk = (header *) Heap.freeList[i];
  413.         if (currChunk == chunk) {
  414.             return i;
  415.         }
  416.     }
  417.     return -1;
  418. }
  419.  
  420. static void readjustPointers(int indexChunk) {
  421.    
  422.     while (indexChunk < Heap.freeElems) {
  423.        
  424.         if (indexChunk == Heap.freeElems - 1) {
  425.             Heap.freeList[indexChunk] = NULL;
  426.             break;
  427.         }
  428.         Heap.freeList[indexChunk] = Heap.freeList[indexChunk + 1];  
  429.         indexChunk++;
  430.     }
  431.    
  432. }
  433.