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