root/umalloc.c
/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- free
- morecore
- malloc
1 #include "types.h"
2 #include "stat.h"
3 #include "user.h"
4 #include "param.h"
5
6 // Memory allocator by Kernighan and Ritchie,
7 // The C programming Language, 2nd ed. Section 8.7.
8
9 typedef long Align;
10
11 union header {
12 struct {
13 union header *ptr;
14 uint size;
15 } s;
16 Align x;
17 };
18
19 typedef union header Header;
20
21 static Header base;
22 static Header *freep;
23
24 void
25 free(void *ap)
26 {
27 Header *bp, *p;
28
29 bp = (Header*)ap - 1;
30 for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
31 if(p >= p->s.ptr && (bp > p || bp < p->s.ptr))
32 break;
33 if(bp + bp->s.size == p->s.ptr){
34 bp->s.size += p->s.ptr->s.size;
35 bp->s.ptr = p->s.ptr->s.ptr;
36 } else
37 bp->s.ptr = p->s.ptr;
38 if(p + p->s.size == bp){
39 p->s.size += bp->s.size;
40 p->s.ptr = bp->s.ptr;
41 } else
42 p->s.ptr = bp;
43 freep = p;
44 }
45
46 static Header*
47 morecore(uint nu)
48 {
49 char *p;
50 Header *hp;
51
52 if(nu < 4096)
53 nu = 4096;
54 p = sbrk(nu * sizeof(Header));
55 if(p == (char*)-1)
56 return 0;
57 hp = (Header*)p;
58 hp->s.size = nu;
59 free((void*)(hp + 1));
60 return freep;
61 }
62
63 void*
64 malloc(uint nbytes)
65 {
66 Header *p, *prevp;
67 uint nunits;
68
69 nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
70 if((prevp = freep) == 0){
71 base.s.ptr = freep = prevp = &base;
72 base.s.size = 0;
73 }
74 for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
75 if(p->s.size >= nunits){
76 if(p->s.size == nunits)
77 prevp->s.ptr = p->s.ptr;
78 else {
79 p->s.size -= nunits;
80 p += p->s.size;
81 p->s.size = nunits;
82 }
83 freep = prevp;
84 return (void*)(p + 1);
85 }
86 if(p == freep)
87 if((p = morecore(nunits)) == 0)
88 return 0;
89 }
90 }