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*
malloc(size_t size)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
free(void * ptr)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*
realloc(void * ptr,size_t n)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