home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2000 #5 / Amiga Plus CD - 2000 - No. 5.iso / Tools / Dev / GameboyDev / GBDK / lib / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-29  |  5.2 KB  |  178 lines
  1. /*
  2.   malloc.c
  3.  
  4.   Simple implementation of a malloc library for the GB
  5.  
  6.   Notes:
  7.   * Designed for the Nintendo GB - 8 bitter with little RAM, so efficency and allocation
  8.   speed are important.  recursion or malloc/free pairs are rare.
  9.   * Garbage collection is lazy
  10.   * Singly linked list of 'hunks' - regions of memory
  11.   * Each hunk is preceeded by a header - header describes a singly linked list
  12.   * If the header is corrupted, this system dies - but so does the program so youve got other problems
  13.   * All allocations are on byte boundries
  14.   * See types.h for the definitions of UBYTE, BYTE...
  15.   * Theres a bug in GBDK 2.0b9 - cant handle pointer addition, requiring (UWORD) casting
  16. */
  17. #include <sys/malloc.h>
  18. #include <types.h>
  19. #include <stdio.h>
  20.  
  21. /* First hunk in the linked list */
  22. pmmalloc_hunk malloc_first;
  23.  
  24. /*
  25.   Simple debug message logger.  Logs to stdout (which is, of course, all that a GB has :)
  26. */
  27. void debug( char *fun, char *msg )
  28. {
  29. /*    return; */
  30. /*    printf("%s: %s\n", fun, msg );*/
  31. }
  32.  
  33. /*
  34.   malloc_init
  35.  
  36.   Initialise the malloc system.  
  37.   Only initalises if the magic number on the first hunk is invalid.
  38.   Note that this number is invalidated in crt0.s 
  39.   
  40.   Returns: BYTE, -1 on failure, 0 on success
  41. */
  42. BYTE malloc_init(void)
  43. {
  44.     if (malloc_first->magic!=MALLOC_MAGIC) {
  45.         /* Init by setting up the first hunk */
  46.  
  47.         debug("malloc_init", "Setting up");
  48.         /* malloc_heap_start is set by the linker to point to the start of free memory */
  49.         malloc_first = (pmmalloc_hunk)&malloc_heap_start;
  50.  
  51.         /* Initalise the linked list */
  52.         malloc_first->next = NULL;
  53.         /* Set the size to all of free memory (mem ends at 0xE000), less 200h for the stack */
  54.         malloc_first->size = (UBYTE *)(0xDFFFU - 0x200) - sizeof(mmalloc_hunk) - (UBYTE *)&malloc_heap_start;
  55.         malloc_first->status = MALLOC_FREE;
  56.  
  57.         malloc_first->magic = MALLOC_MAGIC;
  58.         return 0;
  59.     }
  60.     return -1;
  61. }
  62.  
  63. /*
  64.   malloc_gc
  65.  
  66.   Do a grabage collect on the malloc list.  Join any adjacent, free hunks into one
  67.   free hunk.  Called by malloc() when there is no one free block of memory big
  68.   enough.
  69.   Note that malloc_gc is only called when needed to save processor time
  70.   Note:  assumes that hunks ae consecutive
  71. */
  72. void malloc_gc(void)
  73. {
  74.     /* Note: assumes that hunks are consecutive */
  75.  
  76.    
  77.     /* thisHunk is the one that were lookin at */
  78.     /* nextHunk is used when joining hunks */
  79.     pmmalloc_hunk thisHunk, nextHunk;
  80.  
  81.     /* changed is set if at least two hunks are joined */
  82.     /* Note that logically all will be joined on the first pass, but you get that */
  83.     UBYTE changed;
  84.     
  85.     debug("malloc_gc","Running");
  86.  
  87.     do {
  88.     thisHunk = malloc_first;
  89.     changed = 0;
  90.     /* Walk the whole of the linked list */
  91.     while (thisHunk && (thisHunk->magic==MALLOC_MAGIC)) {
  92.         /* Is this hunk free ? */
  93.         if (thisHunk->status == MALLOC_FREE) {
  94.         /* Yes - if the next is as well, join them */
  95.         nextHunk = thisHunk->next;
  96.         /* This catches the case where there are many consecutive free hunks */
  97.         while (nextHunk->status == MALLOC_FREE) {
  98.             /* Must be consecutive */
  99.             changed = 1;
  100.             thisHunk->size+=nextHunk->size+sizeof(mmalloc_hunk);
  101.             nextHunk = nextHunk->next;
  102.             thisHunk->next = nextHunk;
  103.         }
  104.         }
  105.         thisHunk=thisHunk->next;
  106.     }
  107.     /* If thisHunk is not NULL, then the magic number was corrupt */
  108.     if (thisHunk!=NULL)
  109.         debug("malloc_gc", "Corrupted malloc list found.");
  110.     } while (changed);
  111. }
  112.         
  113. /*
  114.   malloc
  115.  
  116.   Attempt to allocate a hunk of at least 'size' bytes from free memory
  117.   Return:  pointer to the base of free memory on success, NULL if no memory
  118.   was available
  119. */
  120. void *malloc( UWORD size )
  121. {
  122.     /* thisHunk: list walker
  123.     */
  124.     pmmalloc_hunk thisHunk, insertBefore;
  125.     pmmalloc_hunk newHunk;
  126.  
  127.     UBYTE firstTry;
  128.  
  129.     /* Init the system if required */
  130.     if (malloc_first->magic != MALLOC_MAGIC)
  131.     malloc_init();
  132.     
  133.     firstTry = 1;    /* Allows gc if no big enough hunk is found */
  134.     
  135.     do {
  136.     thisHunk = malloc_first;
  137.     
  138.     /* Walk the list */
  139.     while (thisHunk&&(thisHunk->magic == MALLOC_MAGIC)) {
  140.         debug("malloc", "Entering hunk" );
  141.         if (thisHunk->status == MALLOC_FREE) {
  142.         debug("malloc", "Found free hunk" );
  143.         
  144.         /* Free, is it big enough? (dont forget the size of the header) */
  145.         if (thisHunk->size >= size+sizeof(mmalloc_hunk)) {
  146.             
  147.             debug("malloc","Found a big enough hunk.");
  148.             
  149.             /* Yes, big enough */
  150.             /* Create a new header at the end of this block */
  151.             /* Note: the header can be of zero length - should add code to combine */
  152.             newHunk = (pmmalloc_hunk)((UBYTE *)thisHunk + size + sizeof(mmalloc_hunk));
  153.             newHunk->next = thisHunk->next;
  154.             /* size is the free space, less that allocated, less the new header */
  155.             newHunk->size = thisHunk->size - sizeof(mmalloc_hunk) - size;
  156.             /* Mark it as free and valid */
  157.             newHunk->status = MALLOC_FREE;
  158.             newHunk->magic = MALLOC_MAGIC;
  159.             
  160.             /* Shrink this hunk, and mark it as used */
  161.             thisHunk->size = size;
  162.             thisHunk->status = MALLOC_USED;
  163.             thisHunk->next = newHunk;
  164.             
  165.             /* Return a pointer to the new region */
  166.             return (void *)((UBYTE *)thisHunk + sizeof(mmalloc_hunk));
  167.         }
  168.         }
  169.         thisHunk = thisHunk->next;
  170.     }
  171.     malloc_gc();
  172.     /* Try again after a garbage collect */
  173.     } while (firstTry--);
  174.  
  175.     /* Couldnt do it */
  176.     return NULL;
  177. }
  178.