1 #include <stdlib.h>
2 #include <string.h>
3
4 typedef unsigned int uint;
5 typedef long long intptr_t;
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 };
22
23 typedef struct Arena Arena;
24 struct Arena
25 {
26 Bucket *btab[MAX2SIZE];
27 };
28 static Arena arena;
29
30 #define datoff ((sizeof(struct Bucket)+7)&~7)
31 #define nil ((void*)0)
32
33 extern void *sbrk(unsigned long);
34
35 void*
malloc(size_t size)36 malloc(size_t size)
37 {
38 intptr_t 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 + 1;
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((intptr_t)bp == -1)
68 return nil;
69
70 next = (intptr_t)bp+size;
71 nbp = (Bucket*)next;
72 arena.btab[pow] = nbp;
73 for(n -= 2; n; n--) {
74 next = (intptr_t)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((intptr_t)bp == -1)
84 return nil;
85 }
86
87 bp->size = pow;
88 bp->magic = MAGIC;
89
90 return bp + 1;
91 }
92
93 void
free(void * ptr)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*)((intptr_t)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*
realloc(void * ptr,size_t n)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*)((intptr_t)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