123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142 |
- #include <stdlib.h>
- #include <string.h>
- typedef unsigned int uint;
- enum
- {
- MAGIC = 0xbada110c,
- MAX2SIZE = 32,
- CUTOFF = 12,
- };
- typedef struct Bucket Bucket;
- struct Bucket
- {
- int size;
- int magic;
- Bucket *next;
- int pad;
- char data[1];
- };
- typedef struct Arena Arena;
- struct Arena
- {
- Bucket *btab[MAX2SIZE];
- };
- static Arena arena;
- #define datoff ((int)((Bucket*)0)->data)
- #define nil ((void*)0)
- extern void *sbrk(unsigned long);
- void*
- malloc(size_t size)
- {
- uint next;
- int pow, n;
- Bucket *bp, *nbp;
- for(pow = 1; pow < MAX2SIZE; pow++) {
- if(size <= (1<<pow))
- goto good;
- }
- return nil;
- good:
- /* Allocate off this list */
- bp = arena.btab[pow];
- if(bp) {
- arena.btab[pow] = bp->next;
- if(bp->magic != 0)
- abort();
- bp->magic = MAGIC;
- return bp->data;
- }
- size = sizeof(Bucket)+(1<<pow);
- size += 7;
- size &= ~7;
- if(pow < CUTOFF) {
- n = (CUTOFF-pow)+2;
- bp = sbrk(size*n);
- if((int)bp < 0)
- return nil;
- next = (uint)bp+size;
- nbp = (Bucket*)next;
- arena.btab[pow] = nbp;
- for(n -= 2; n; n--) {
- next = (uint)nbp+size;
- nbp->next = (Bucket*)next;
- nbp->size = pow;
- nbp = nbp->next;
- }
- nbp->size = pow;
- }
- else {
- bp = sbrk(size);
- if((int)bp < 0)
- return nil;
- }
-
- bp->size = pow;
- bp->magic = MAGIC;
- return bp->data;
- }
- void
- free(void *ptr)
- {
- Bucket *bp, **l;
- if(ptr == nil)
- return;
- /* Find the start of the structure */
- bp = (Bucket*)((uint)ptr - datoff);
- if(bp->magic != MAGIC)
- abort();
- bp->magic = 0;
- l = &arena.btab[bp->size];
- bp->next = *l;
- *l = bp;
- }
- void*
- realloc(void *ptr, size_t n)
- {
- void *new;
- uint osize;
- Bucket *bp;
- if(ptr == nil)
- return malloc(n);
- /* Find the start of the structure */
- bp = (Bucket*)((uint)ptr - datoff);
- if(bp->magic != MAGIC)
- abort();
- /* enough space in this bucket */
- osize = 1<<bp->size;
- if(osize >= n)
- return ptr;
- new = malloc(n);
- if(new == nil)
- return nil;
- memmove(new, ptr, osize);
- free(ptr);
- return new;
- }
|