Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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*
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
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*
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 
}