This repository has been archived by the owner on Jun 23, 2018. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 9
/
bfree.c
172 lines (142 loc) · 4.16 KB
/
bfree.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <stdio.h>
#include <stdlib.h>
#define MAXBYTES (unsigned) 1024
typedef long Align;
union header {
struct {
union header *ptr; /* next block if on the free list */
unsigned size; /* size of this block */
} s;
Align x;
};
typedef union header Header;
static Header base; /* empty list to get started */
static Header *freep = NULL; /*start of free list */
#define ALIGN(p) (sizeof(Align) - ((unsigned)(p) % sizeof(Align))) % sizeof(Align)
void wtbfree(void *, unsigned);
void bfree(void *, unsigned);
void bfree(void *p, unsigned n) {
unsigned align, s, r;
if (n < sizeof(Header)) { /* can't free less than this */
wtbfree(p, n);
return;
}
align = ALIGN(p);
if (align) { /* adjust alignment */
wtbfree(p, align); /* put at the beginning in the wtbfree list */
p = (char *)p + align;
n -= align;
}
s = n / sizeof(Header);
r = n % sizeof(Header);
/* put at the trailing end of the wtbfree list */
if (r) {
wtbfree((char *)p + n + r, r);
}
/* if there is something left to be free */
if (s) {
if (freep == NULL) { /* setup a free list if it is empty */
base.s.ptr = freep = &base;
base.s.size = 0;
}
((Header *)p)->s.size = s;
free((Header *)p + 1);
}
}
struct wtbheader {
struct wtbheader *next;
void *p;
unsigned n;
};
void try_to_free(struct wtbheader *p) {
char *tp;
unsigned align;
unsigned n;
tp = p->p;
align = ALIGN(p->p);
if ((align < p->n) && ((p->n - align) % sizeof(Header) == 0)) {
tp += align;
n = p->n - align;
p->n = align;
((Header *)tp)->s.size = n / sizeof(Header);
free((Header *)tp + 1);
}
}
static struct wtbheader *headptr;
void wtbfree(void *p, unsigned n) {
struct wtbheader *hp, *prevp;
if (headptr == NULL) { /* first use */
if (!(headptr = malloc(sizeof *headptr))) /* can't save fragment, dump it */
return;
headptr->p = p;
headptr->n = n;
headptr->next = NULL;
} else if (p < headptr->p) { /* special case: less than head */
if ((char *)p + n == headptr->p) { /* merge */
headptr->p = p;
headptr->n = n;
try_to_free(headptr);
if (!headptr->n) { /* delete empty node */
void *tp = headptr;
headptr = headptr->next;
free(tp);
}
} else {
struct wtbheader *tp;
if (!(tp = malloc(sizeof *tp))) /* can't save fragment, dump it */
return;
tp->p = p;
tp->n = n;
tp->next = headptr;
headptr = tp;
}
} else {
for (prevp = hp = headptr; hp->next && p > hp->next->p; prevp = hp, hp = hp->next) {
; /* just advance */
}
if ((char *)hp->p + hp->n == p) { /* merge to current */
hp->n += n;
try_to_free(hp);
if (!hp->n) {
if (hp == headptr)
headptr = NULL;
prevp->next = hp->next;
free(hp);
}
} else if (hp->next && (char *)p + n == hp->next->p) { /* merge to next */
hp->next->p = p;
hp->next->n += n;
try_to_free(hp->next);
if (! hp->next->n) { /* delete empty node */
void *tp = hp->next;
hp->next = hp->next->next;
free(tp);
}
} else { /* insert */
struct wtbheader *tp;
if (!(tp = malloc(sizeof *tp))) /* can't save fragment, dump */
return;
tp->p = p;
tp->n = n;
tp->next = hp->next;
hp->next = tp;
}
}
}
int main(void) {
int *p = NULL;
int i = 0;
p = malloc(100 * sizeof *p);
if (NULL == p)
printf("malloc returned NULL");
else {
for (i = 0; i <= 100; i++) {
printf("%08X", p[i]);
if (i % 8 == 7)
printf("\n");
}
printf("\n");
bfree(p, 1 * sizeof *p);
}
return 0;
}