Mercurial > hg > Members > innparusu > xv6-rpi
comparison src/usr/umalloc.c @ 0:83c23a36980d
Init
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 26 May 2017 23:11:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:83c23a36980d |
---|---|
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 } |