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