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