1 #include <stdlib.h> 2 #include <string.h> 3 4 typedef unsigned int uint; 5 6 enum 7 { 8 MAGIC = 0xbada110c, 9 MAX2SIZE = 32, 10 CUTOFF = 12, 11 }; 12 13 typedef struct Bucket Bucket; 14 struct Bucket 15 { 16 int size; 17 int magic; 18 Bucket *next; 19 int pad; 20 char data[1]; 21 }; 22 23 typedef struct Arena Arena; 24 struct Arena 25 { 26 Bucket *btab[MAX2SIZE]; 27 }; 28 static Arena arena; 29 30 #define datoff ((int)((Bucket*)0)->data) 31 #define nil ((void*)0) 32 33 extern void *sbrk(unsigned long); 34 35 void* 36 malloc(size_t size) 37 { 38 uint next; 39 int pow, n; 40 Bucket *bp, *nbp; 41 42 for(pow = 1; pow < MAX2SIZE; pow++) { 43 if(size <= (1<<pow)) 44 goto good; 45 } 46 47 return nil; 48 good: 49 /* Allocate off this list */ 50 bp = arena.btab[pow]; 51 if(bp) { 52 arena.btab[pow] = bp->next; 53 54 if(bp->magic != 0) 55 abort(); 56 57 bp->magic = MAGIC; 58 return bp->data; 59 } 60 size = sizeof(Bucket)+(1<<pow); 61 size += 7; 62 size &= ~7; 63 64 if(pow < CUTOFF) { 65 n = (CUTOFF-pow)+2; 66 bp = sbrk(size*n); 67 if((int)bp < 0) 68 return nil; 69 70 next = (uint)bp+size; 71 nbp = (Bucket*)next; 72 arena.btab[pow] = nbp; 73 for(n -= 2; n; n--) { 74 next = (uint)nbp+size; 75 nbp->next = (Bucket*)next; 76 nbp->size = pow; 77 nbp = nbp->next; 78 } 79 nbp->size = pow; 80 } 81 else { 82 bp = sbrk(size); 83 if((int)bp < 0) 84 return nil; 85 } 86 87 bp->size = pow; 88 bp->magic = MAGIC; 89 90 return bp->data; 91 } 92 93 void 94 free(void *ptr) 95 { 96 Bucket *bp, **l; 97 98 if(ptr == nil) 99 return; 100 101 /* Find the start of the structure */ 102 bp = (Bucket*)((uint)ptr - datoff); 103 104 if(bp->magic != MAGIC) 105 abort(); 106 107 bp->magic = 0; 108 l = &arena.btab[bp->size]; 109 bp->next = *l; 110 *l = bp; 111 } 112 113 void* 114 realloc(void *ptr, size_t n) 115 { 116 void *new; 117 uint osize; 118 Bucket *bp; 119 120 if(ptr == nil) 121 return malloc(n); 122 123 /* Find the start of the structure */ 124 bp = (Bucket*)((uint)ptr - datoff); 125 126 if(bp->magic != MAGIC) 127 abort(); 128 129 /* enough space in this bucket */ 130 osize = 1<<bp->size; 131 if(osize >= n) 132 return ptr; 133 134 new = malloc(n); 135 if(new == nil) 136 return nil; 137 138 memmove(new, ptr, osize); 139 free(ptr); 140 141 return new; 142 } 143