home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / program / c / ios_src / nmalloc.c < prev    next >
Text File  |  1993-01-31  |  10KB  |  377 lines
  1.  
  2. /* NMALLOC.C            New-malloc        */
  3.  
  4. /* Nach einer Idee von Hans-Jürgen Richstein aus ST-Computer 11/1990 p. 140 ff
  5.     Die Routinen ersetzen jetzt die malloc/free/realloc... vollstaendig!
  6.     Es wird der TOS-Speicher minus 50 KB in TCSMALL reserviert. Der Speicher
  7.     wird dann selbst verwaltet. Dieser Code ist etwa doppelt so schnell wie
  8.     der orginal Turbo-C (2.03) malloc-code in STDLIB.
  9.     NMALLOC muss unmittlebar vor STDLIB gelinkt werden (siehe PRJ-Datei), da
  10.     malloc auch aus der STDLIB von einigen funktionen PC-relativ aufgerufen
  11.     wird.
  12. */
  13. /* keine #include <..> !! */
  14.  
  15. /* size_t ist in mehreren Headerfiles wie folgt definiert:        */
  16. typedef unsigned long    size_t;
  17.  
  18. /*    Das Konstanten-Makro NULL ist in STDDEF.H deklariert:            */
  19. #define NULL        ( ( void * ) 0L )
  20.  
  21. /* init_mem wird von TCSMALL (Startup-code) aufgerufen. */
  22. size_t init_mem(void *start_adress, size_t size);
  23.  
  24. /* Erweiterungen gegen Turbo-C */
  25. size_t total_coreleft(void);
  26. size_t n_of_fragments(void);
  27.  
  28. /* Wie in ext.h definiert:
  29.     ermittelt den größten zur Verfügung stehenden Speicherblock        */
  30. size_t coreleft(void);
  31.  
  32. /* Wie Prototypen in stdlib.h:            */
  33. void free( void *ptr );
  34. void *malloc(size_t size);
  35. void *calloc ( size_t nitems, size_t size );
  36. void *realloc(void *block, size_t newsize);
  37.  
  38. /* Funktionen aus string.h, Gruppe Speichermanipulation    */
  39. void *memset(void *s, int val, size_t len);
  40. void *memcpy(void *dest, const void *src, size_t len);
  41.  
  42.  
  43. /* Jetzt geht's richtig zur Sache.. */
  44.  
  45. #define MEM_BLOCK struct memory_header
  46.  
  47. MEM_BLOCK
  48. {
  49.     MEM_BLOCK *next;
  50.     size_t size;
  51.     char data[];
  52. };
  53.  
  54. typedef struct
  55. {
  56.     size_t size;
  57.     int mark;
  58.     char user_block[];
  59. } LARGE_BLOCK;
  60.  
  61. typedef struct
  62. {
  63.     unsigned int size;
  64.     char user_block[];
  65. } SMALL_BLOCK;
  66.  
  67. static MEM_BLOCK head;
  68.  
  69. static char *start_of_buffer,
  70.                 *end_of_buffer;
  71.  
  72.  
  73. static void* make_user_block(MEM_BLOCK *block, size_t block_size)
  74. {
  75.     if(block_size > 0xFFFF)
  76.     {
  77.         ((LARGE_BLOCK*) block)->size = block_size;
  78.         ((LARGE_BLOCK*) block)->mark = 0;
  79.         return (void*) &(((LARGE_BLOCK*) block)->user_block);
  80.     }
  81.     else
  82.     {
  83.         ((SMALL_BLOCK*) block)->size = (unsigned int)block_size;
  84.         return (void*) &(((SMALL_BLOCK*) block)->user_block);
  85.     }
  86. }
  87.  
  88. static size_t actual_size(size_t desired_size)
  89. {
  90.     size_t size;
  91.     if(desired_size & 1L) desired_size+=3;
  92.     else desired_size+=2;
  93.     size = desired_size + 
  94.         ((desired_size < 0xFFFEL) ? sizeof(SMALL_BLOCK) : sizeof(LARGE_BLOCK));
  95.     if(size < sizeof(MEM_BLOCK)) size = sizeof(MEM_BLOCK);
  96.     return size;
  97. }
  98.  
  99. static void get_block_data(void *block, MEM_BLOCK **block_start,
  100.             size_t *block_size, size_t *size_of_user_data)
  101. {
  102.     if(*((int *) block-1) ==0)
  103.     {
  104.         *block_start = (MEM_BLOCK *)((LARGE_BLOCK*) block-1);
  105.         *block_size = ((LARGE_BLOCK *)*block_start)->size;
  106.         *size_of_user_data = *block_size - sizeof(LARGE_BLOCK);
  107.     }
  108.     else
  109.     {
  110.         *block_start = (MEM_BLOCK *)((SMALL_BLOCK*) block-1);
  111.         *block_size = ((SMALL_BLOCK *)*block_start)->size;
  112.         *size_of_user_data = *block_size - sizeof(SMALL_BLOCK);
  113.     }
  114. }
  115.  
  116. static MEM_BLOCK *find_previous_block(MEM_BLOCK *block)
  117. {
  118.     MEM_BLOCK *previous;
  119.     previous = &head;
  120.     while((previous->next < block) && (previous->next != NULL))
  121.         previous = previous->next;
  122.     return previous;
  123. }
  124.  
  125. static void *shrink_block(void *block, size_t old_size, size_t new_size)
  126. {
  127.     if(old_size - new_size >= sizeof(MEM_BLOCK))
  128.     {
  129.         free(make_user_block((MEM_BLOCK *)((char*)block + new_size),old_size - new_size));
  130.         return make_user_block(block,new_size);
  131.     }
  132.     else
  133.     return make_user_block(block,old_size);
  134. }
  135.  
  136. static void split_block(MEM_BLOCK *block, size_t size_of_first)
  137. {
  138.     MEM_BLOCK *second_block;
  139.     second_block = (MEM_BLOCK*)(((char*)block) + size_of_first);
  140.     second_block->next = block->next;
  141.     second_block->size = block->size - size_of_first;
  142.     block->size = size_of_first;
  143.     block->next = second_block;
  144. }
  145.  
  146. static size_t insert_into_list(MEM_BLOCK *block, size_t size)
  147. {
  148.     MEM_BLOCK *previous, *following;
  149.     previous = find_previous_block(block);
  150.     following = previous->next;
  151.     if(((following != NULL) && ((MEM_BLOCK*)((char*)block + size) > following))
  152.             || (size < sizeof(MEM_BLOCK))
  153.             ||    (block < (MEM_BLOCK*)((char*)previous + previous->size))
  154.             ||    (((char*)block < start_of_buffer) || ((char*)block + size > end_of_buffer)))
  155.     {
  156.         return -1;
  157.     }
  158.     else
  159.     {
  160.         block->size = size;
  161.         if((MEM_BLOCK*)((char*) previous + previous->size) == block)
  162.         {
  163.             previous->size += size;
  164.             block = previous;
  165.         }
  166.         else
  167.         {
  168.             block->size = size;
  169.             block->next = following;
  170.             previous->next = block;
  171.         }
  172.         if((MEM_BLOCK*)((char*)block + block->size) == following)
  173.         {
  174.             block->size += following->size;
  175.             block->next = following->next;
  176.         }
  177.         return 0;
  178.     }
  179. }
  180.  
  181. static void remove_from_list(MEM_BLOCK *block)
  182. {
  183.     MEM_BLOCK *previous;
  184.     previous = find_previous_block(block);
  185.     previous->next = block->next;
  186. }
  187.                 
  188. size_t init_mem(void *start_adress, size_t size)
  189. {
  190.     if((size < sizeof(MEM_BLOCK)) || (start_adress == NULL)) return -1;
  191.     else
  192.     {
  193.         ((MEM_BLOCK *) start_adress)->next = NULL;
  194.         ((MEM_BLOCK *) start_adress)->size = size;
  195.         head.next = (MEM_BLOCK *) start_adress;
  196.         start_of_buffer = (char *) start_adress;
  197.         end_of_buffer = (char *) start_adress + size;
  198.         head.size = 0;
  199.         return 0;
  200.     }
  201. }
  202.  
  203. void *malloc(size_t size)
  204. {
  205.     MEM_BLOCK *current_block, *previous_block;
  206.     void *desired_block;
  207.     size_t allocated_size;
  208.     
  209.     desired_block = NULL;
  210.     if(size >= 0)
  211.     {
  212.         allocated_size = actual_size(size);
  213.         current_block = head.next;
  214.         previous_block = &head;
  215.         while((current_block != NULL) && (current_block->size < allocated_size))
  216.         {
  217.             previous_block=current_block;
  218.             current_block=current_block->next;
  219.         }
  220.         if(current_block != NULL)
  221.         {
  222.             if(current_block->size - allocated_size < sizeof(MEM_BLOCK))
  223.                 allocated_size = current_block->size;
  224.             else split_block(current_block, allocated_size);
  225.             previous_block->next=current_block->next;
  226.             desired_block = make_user_block(current_block,allocated_size);
  227.         }
  228.     }
  229.     return desired_block;
  230. }
  231.  
  232. void *calloc ( size_t nitems, size_t size )
  233. {
  234.     void *block;
  235.     size_t total_size;
  236.     
  237.     total_size = nitems * size;
  238.     block = malloc(total_size);
  239.     if(block != NULL) memset(block,0,total_size);
  240.     return block;
  241. }
  242.  
  243. void *realloc(void *block, size_t newsize)
  244. {
  245.     MEM_BLOCK *returned_block,
  246.                  *previous,
  247.                  *following;
  248.     void *temp_block;
  249.     size_t    current_size,
  250.                 size_of_realloc,
  251.                 size_of_enlarge,
  252.                 data_size;
  253.  
  254.     size_of_realloc = actual_size(newsize);
  255.     if((block != NULL) && (size_of_realloc >= sizeof(MEM_BLOCK)))
  256.     {
  257.         get_block_data(block,&returned_block,¤t_size,&data_size);
  258.         if(size_of_realloc > current_size)
  259.         {
  260.             previous = find_previous_block(returned_block);
  261.             following = previous->next;
  262.             if(((char *) returned_block + current_size == (char*) following)
  263.                 && (current_size + following->size >= size_of_realloc))
  264.             {
  265.                 size_of_enlarge = current_size + following->size;
  266.                 previous->next=following->next;
  267.                 if((current_size < 0xFFFF) && (size_of_realloc > 0xFFFF))
  268.                     memcpy((char*)block + sizeof(LARGE_BLOCK) - sizeof(SMALL_BLOCK),
  269.                                 block, data_size);
  270.                 block =shrink_block(returned_block,size_of_enlarge,size_of_realloc);
  271.             }
  272.             else
  273.             if(((char*) returned_block == (char*) previous + previous->size)
  274.                     && (current_size + previous->size >= size_of_realloc))
  275.             {
  276.                 size_of_enlarge = current_size + previous->size;
  277.                 remove_from_list(previous);
  278.                 temp_block = block;
  279.                 block = make_user_block(previous, size_of_realloc);
  280.                 memcpy(block,temp_block,data_size);
  281.                 shrink_block(previous,size_of_enlarge,size_of_realloc);
  282.             }
  283.             else
  284.             if(((char*) returned_block + current_size == (char*)following)
  285.                     && ((char*) returned_block == (char*)previous + previous->size)
  286.                     && (current_size + previous->size + following->size >= size_of_realloc))
  287.             {
  288.                 size_of_enlarge = current_size + previous->size + following->size;
  289.                 previous->next = following->next;
  290.                 remove_from_list(previous);
  291.                 temp_block = block;
  292.                 block = make_user_block(previous,size_of_realloc);
  293.                 memcpy(block,temp_block,data_size);
  294.                 shrink_block(previous,size_of_enlarge,size_of_realloc);
  295.             }
  296.             else
  297.             {
  298.                 temp_block = block;
  299.                 block = malloc(newsize);
  300.                 if(block != NULL)
  301.                 {
  302.                     memcpy(block,temp_block,data_size);
  303.                     free(temp_block);
  304.                 }
  305.             }
  306.         }
  307.         else
  308.         if(size_of_realloc < current_size)
  309.         {
  310.             if((current_size > 0xFFFF) && (size_of_realloc < 0xFFFF))
  311.             {
  312.                 memcpy( ((LARGE_BLOCK*)returned_block)->user_block,
  313.                             block,data_size);
  314.             }
  315.             shrink_block(returned_block,current_size,size_of_realloc);
  316.         }
  317.         }
  318.     return block;
  319. }
  320.  
  321. void free(void *ptr)
  322. {
  323.     MEM_BLOCK *returned_block;
  324.     size_t size, dummy;
  325.     
  326.     if(ptr != NULL)
  327.     {
  328.         get_block_data(ptr,&returned_block,&size,&dummy);
  329.         insert_into_list(returned_block,size);
  330.     }
  331. }
  332.  
  333. size_t coreleft(void)
  334. {
  335.     MEM_BLOCK *block;
  336.     size_t size_of_largest;
  337.  
  338.     block = head.next;
  339.     size_of_largest=0;
  340.     while(block != NULL)
  341.     {
  342.         if(block->size > size_of_largest)
  343.             size_of_largest = block->size;
  344.         block = block->next;
  345.     }
  346.     return size_of_largest-((size_of_largest < 0xFFFF) ? sizeof(SMALL_BLOCK)
  347.                 : sizeof(LARGE_BLOCK));
  348. }
  349.  
  350. size_t total_coreleft(void)
  351. {
  352.     MEM_BLOCK *block;
  353.     size_t total=0;
  354.     block = head.next;
  355.     while(block != NULL)
  356.     {
  357.         total += block->size -((block->size < 0xFFFF) ? sizeof(SMALL_BLOCK)
  358.                 : sizeof(LARGE_BLOCK));
  359.         block = block->next;
  360.     }
  361.     return total;
  362. }
  363.  
  364. size_t n_of_fragments(void)
  365. {
  366.     MEM_BLOCK *block;
  367.     size_t total=0;
  368.     block = head.next;
  369.     while(block != NULL)
  370.     {
  371.         total ++;
  372.         block = block->next;
  373.     }
  374.     return total;
  375. }
  376.  
  377.