123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254 |
- #include <limits.h>
- #include <stddef.h>
- #include <stdlib.h>
- #include <string.h>
- #include "malloc.h"
- void *(*__morecore)(long) = __default_morecore_init;
- char *_heapbase;
- union info *_heapinfo;
- static int heapsize;
- int _heapindex;
- int _heaplimit;
- int _fragblocks[BLOCKLOG];
- struct list _fraghead[BLOCKLOG];
- static int initialized;
- static void *
- align(size_t size)
- {
- void *result;
- unsigned int adj;
- result = (*__morecore)(size);
- adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
- if (adj != 0) {
- (*__morecore)(adj = BLOCKSIZE - adj);
- result = (char *) result + adj;
- }
- return result;
- }
- static int
- initialize(void)
- {
- heapsize = HEAP / BLOCKSIZE;
- _heapinfo = align(heapsize * sizeof (union info));
- if (!_heapinfo)
- return 0;
- memset(_heapinfo, 0, heapsize * sizeof (union info));
- _heapinfo[0].free.size = 0;
- _heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
- _heapindex = 0;
- _heapbase = (char *) _heapinfo;
- initialized = 1;
- return 1;
- }
- static void *
- morecore(size_t size)
- {
- void *result;
- union info *newinfo, *oldinfo;
- int newsize;
- result = align(size);
- if (!result)
- return NULL;
-
- if (BLOCK((char *) result + size) > heapsize) {
- newsize = heapsize;
- while (BLOCK((char *) result + size) > newsize)
- newsize *= 2;
- newinfo = align(newsize * sizeof (union info));
- if (!newinfo) {
- (*__morecore)(-size);
- return NULL;
- }
- memset(newinfo, 0, newsize * sizeof (union info));
- memcpy(newinfo, _heapinfo, heapsize * sizeof (union info));
- oldinfo = _heapinfo;
- newinfo[BLOCK(oldinfo)].busy.type = 0;
- newinfo[BLOCK(oldinfo)].busy.info.size
- = BLOCKIFY(heapsize * sizeof (union info));
- _heapinfo = newinfo;
- #if 0
- free(oldinfo);
- #else
- _free_internal (oldinfo);
- #endif
- heapsize = newsize;
- }
- _heaplimit = BLOCK((char *) result + size);
- return result;
- }
- void *
- malloc (size_t size)
- {
- void *result;
- int log, block, blocks, i, lastblocks, start;
- struct list *next;
- if (!initialized && !initialize())
- return NULL;
- #if 1
-
- if (size == 0)
- return NULL;
- #endif
- if (size < sizeof (struct list))
- size = sizeof (struct list);
-
- if (size <= BLOCKSIZE / 2) {
-
- --size;
- for (log = 1; (size >>= 1) != 0; ++log)
- ;
-
- if ((next = _fraghead[log].next) != 0) {
-
- result = next;
- next->prev->next = next->next;
- if (next->next)
- next->next->prev = next->prev;
- block = BLOCK(result);
- if (--_heapinfo[block].busy.info.frag.nfree)
- _heapinfo[block].busy.info.frag.first
- = (unsigned int) ((char *) next->next - (char *) NULL)
- % BLOCKSIZE >> log;
- } else {
-
- result = malloc(BLOCKSIZE);
- if (!result)
- return NULL;
- ++_fragblocks[log];
-
- next = (struct list *) ((char *) result + (1 << log));
- next->next = 0;
- next->prev = &_fraghead[log];
- _fraghead[log].next = next;
- for (i = 2; i < BLOCKSIZE >> log; ++i) {
- next = (struct list *) ((char *) result + (i << log));
- next->next = _fraghead[log].next;
- next->prev = &_fraghead[log];
- next->prev->next = next;
- next->next->prev = next;
- }
-
- block = BLOCK(result);
- _heapinfo[block].busy.type = log;
- _heapinfo[block].busy.info.frag.nfree = i - 1;
- _heapinfo[block].busy.info.frag.first = i - 1;
- }
- } else {
-
- blocks = BLOCKIFY(size);
- start = block = _heapindex;
- while (_heapinfo[block].free.size < blocks) {
- block = _heapinfo[block].free.next;
- if (block == start) {
-
- block = _heapinfo[0].free.prev;
- lastblocks = _heapinfo[block].free.size;
- if (_heaplimit && block + lastblocks == _heaplimit
- && (*__morecore)(0) == ADDRESS(block + lastblocks)
- && morecore((blocks - lastblocks) * BLOCKSIZE)) {
-
- block = _heapinfo[0].free.prev;
- _heapinfo[block].free.size += blocks - lastblocks;
- continue;
- }
- result = morecore(blocks * BLOCKSIZE);
- if (!result)
- return NULL;
- block = BLOCK(result);
- _heapinfo[block].busy.type = 0;
- _heapinfo[block].busy.info.size = blocks;
- return result;
- }
- }
-
- result = ADDRESS(block);
- if (_heapinfo[block].free.size > blocks) {
-
- _heapinfo[block + blocks].free.size
- = _heapinfo[block].free.size - blocks;
- _heapinfo[block + blocks].free.next
- = _heapinfo[block].free.next;
- _heapinfo[block + blocks].free.prev
- = _heapinfo[block].free.prev;
- _heapinfo[_heapinfo[block].free.prev].free.next
- = _heapinfo[_heapinfo[block].free.next].free.prev
- = _heapindex = block + blocks;
- } else {
-
- _heapinfo[_heapinfo[block].free.next].free.prev
- = _heapinfo[block].free.prev;
- _heapinfo[_heapinfo[block].free.prev].free.next
- = _heapindex = _heapinfo[block].free.next;
- }
- _heapinfo[block].busy.type = 0;
- _heapinfo[block].busy.info.size = blocks;
- }
- return result;
- }
|