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