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
|
#include <stdio.h>
#include <string.h>
/* The C Programming Language: 2nd Edition
*
* Exercise 8-6: The standard library function calloc(n, size) returns a
* pointer to `n` objects of size `size`, with the storage initialized to zero.
* Write `calloc`, by calling malloc or by modifying it.
*
* Notes: Replacing the standard library functions here can be problematic if
* you also intend to use the stdlib to output text or use other functions that
* interact with *alloc, morecore, and free.
*
* I prefixed the functions with 'z' so I could hack on them *and* use the
* standard library as needed.
*
* Ideally, one would use a debugger or other tool to show that memory is
* assigned in the free list, and verify the size of the block of memory. We'll
* revisit this when I'm good at debuggers. :)
*/
typedef long Align;
union header {
struct {
union header *ptr;
unsigned size;
} s;
/* unused, just for alignment */
Align x;
} hdr;
typedef union header Header;
static Header base;
static Header *freep = NULL;
static Header *zmorecore(unsigned);
void *zmalloc(unsigned);
void zfree(void *);
void *zmalloc(unsigned nbytes) {
/* TODO: get the size field updated correctly */
Header *p, *prevp;
unsigned nunits;
nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1;
if ((prevp = freep) == NULL) {
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
/* larger than requested units */
if (p->s.size >= nunits) {
if (p->s.size == nunits) {
prevp->s.ptr = p->s.ptr;
} else {
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void *)(p+1);
}
if (p == freep) {
if ((p = zmorecore(nunits)) == NULL) {
return NULL;
}
}
}
}
#define NALLOC 1024
static Header *zmorecore(unsigned nu) {
char *cp, *sbrk(int);
Header *up;
if (nu < NALLOC) {
nu = NALLOC;
}
cp = sbrk(nu * sizeof (Header));
if (cp == (char*) -1) {
return NULL;
}
up = (Header *) cp;
up->s.size = nu;
zfree((void *)(up+1));
return freep;
}
void zfree(void *ap) {
Header *bp, *p;
bp = (Header *)ap - 1;
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) {
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) {
break;
}
}
if (bp + bp->s.size == p->s.ptr) {
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else {
bp->s.ptr = p->s.ptr;
}
if (p + p->s.size == bp) {
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else {
p->s.ptr = bp;
}
freep = p;
}
void * zcalloc(int count, unsigned size) {
char *p;
int i;
p = zmalloc(count * size);
if (p != NULL) {
for (i = 0; i < (count * size); i++) {
p[i] = '\0';
}
return p;
} else {
return (int *)(-1);
}
}
int main(int argc, char *argv[]) {
char *foo = "hello there!";
char *buf = zcalloc(strlen(foo) + 1, sizeof (char));
strncpy(buf, foo, 5);
printf("%s\n", buf);
printf("buf is %d long\n", strlen(buf));
printf("foo is %d long\n", strlen(foo));
printf("the header says buf's max size is %d\n", freep->s.size);
return 0;
}
|
