![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / a / usr / bob / korn|
Return to alloc.c CVS log | Up to [MW Coherent from dump] / coherent / a / usr / bob / korn |
1.1 root 1: /*
2: * area-based allocation built on malloc/free
3: */
4:
5: static char *RCSid = "$Header";
6:
7: #include <stddef.h>
8: #include <stdlib.h>
9: #include <setjmp.h>
10: #include "sh.h"
11:
12: #define ICELLS 100 /* number of Cells in small Block */
13:
14: typedef union Cell Cell;
15: typedef struct Block Block;
16:
17: /*
18: * The Cells in a Block are organized as a set of objects.
19: * Each object (pointed to by dp) begins with a size in (dp-1)->size,
20: * followed with "size" data Cells. Free objects are
21: * linked together via dp->next.
22: */
23:
24: union Cell {
25: size_t size;
26: Cell *next;
27: struct {int _;} junk; /* alignment */
28: };
29:
30: struct Block {
31: Block *next; /* list of Blocks in Area */
32: Cell *free; /* object free list */
33: Cell *last; /* &b.cell[size] */
34: Cell cell [1]; /* [size] Cells for allocation */
35: };
36:
37: Block aempty = {&aempty, aempty.cell, aempty.cell};
38:
39: /* create empty Area */
40: Area *
41: ainit(ap)
42: register Area *ap;
43: {
44: ap->free = &aempty;
45: return ap;
46: }
47:
48: /* free all object in Area */
49: void
50: afreeall(ap)
51: register Area *ap;
52: {
53: register Block *bp;
54:
55: if (ap->free == NULL || ap->free == &aempty)
56: return;
57: for (bp = ap->free; ; bp = bp->next) {
58: free((Void*)bp);
59: if (bp->next == ap->free)
60: break;
61: }
62: ap->free = &aempty;
63: }
64:
65: /* allocate object from Area */
66: Void *
67: alloc(size, ap)
68: size_t size;
69: register Area *ap;
70: {
71: int cells, split;
72: register Block *bp;
73: register Cell *dp, *fp, *fpp;
74: #if 0
75: mypr("alloc: size %d area x%x\n", size, ap);
76: #endif
77: if (size <= 0) {
78: aerror(ap, "allocate bad size");
79: return NULL;
80: }
81: cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
82:
83: /* find Cell large enough */
84: for (bp = ap->free; ; bp = bp->next) {
85: for (fpp = NULL, fp = bp->free;
86: fp != bp->last; fpp = fp, fp = fpp->next)
87: if ((fp-1)->size >= cells)
88: goto Found;
89:
90: /* wrapped around Block list, create new Block */
91: if (bp == ap->free) {
92: bp = malloc(offsetof(Block, cell[ICELLS + cells]));
93: if (bp == NULL) {
94: aerror(ap, "cannot allocate");
95: return NULL;
96: }
97: if (ap->free == &aempty)
98: bp->next = bp;
99: else {
100: bp->next = ap->free->next;
101: ap->free->next = bp;
102: }
103: bp->last = bp->cell + ICELLS + cells;
104: fp = bp->free = bp->cell + 1; /* initial free list */
105: (fp-1)->size = ICELLS + cells - 1;
106: fp->next = bp->last;
107: fpp = NULL;
108: break;
109: }
110: }
111: Found:
112: ap->free = bp;
113: dp = fp; /* allocated object */
114: split = (dp-1)->size - cells;
115: if (split < 0)
116: aerror(ap, "allocated object too small");
117: if (--split <= 0) { /* allocate all */
118: fp = fp->next;
119: } else { /* allocate head, free tail */
120: (fp-1)->size = cells;
121: fp += cells + 1;
122: (fp-1)->size = split;
123: fp->next = dp->next;
124: }
125: if (fpp == NULL)
126: bp->free = fp;
127: else
128: fpp->next = fp;
129: return (Void*) dp;
130: }
131:
132: /* change size of object */
133: /* todo: allow expansion */
134: Void *
135: aresize(ptr, size, ap)
136: register Void *ptr;
137: size_t size;
138: register Area *ap;
139: {
140: int cells, split;
141: register Cell *dp = (Cell*)ptr;
142:
143: #if 0
144: mypr("aresize: size %d area x%x ptr x%x\n", size, ap, ptr);
145: #endif
146: if (size <= 0) {
147: aerror(ap, "allocate bad size");
148: return NULL;
149: }
150: cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
151:
152: split = (dp-1)->size - cells;
153: if (split < 0)
154: aerror(ap, "cannot resize larger");
155: if (--split <= 0) /* cannot split */
156: ;
157: else { /* shrink head, free tail */
158: (dp-1)->size = cells;
159: dp += cells + 1;
160: (dp-1)->size = split;
161: afree((Void*)dp, ap);
162: }
163:
164: return (Void*) ptr;
165: }
166:
167: void
168: afree(ptr, ap)
169: Void *ptr;
170: register Area *ap;
171: {
172: register Block *bp;
173: register Cell *fp, *fpp;
174: register Cell *dp = (Cell*)ptr;
175:
176: #if 0
177: mypr("afree: area x%x ptr x%x\n", ap, ptr);
178: #endif
179: /* find Block containing Cell */
180: for (bp = ap->free; ; bp = bp->next) {
181: if (bp->cell <= dp && dp < bp->last)
182: break;
183: if (bp->next == ap->free) {
184: aerror(ap, "freeing with invalid area");
185: return;
186: }
187: }
188:
189: /* find position in free list */
190: for (fpp = NULL, fp = bp->free; fp < dp; fpp = fp, fp = fpp->next)
191: ;
192:
193: if (fp == dp) {
194: aerror(ap, "freeing free object");
195: return;
196: }
197:
198: /* join object with next */
199: if (dp + (dp-1)->size == fp-1) { /* adjacent */
200: (dp-1)->size += (fp-1)->size + 1;
201: dp->next = fp->next;
202: } else /* non-adjacent */
203: dp->next = fp;
204:
205: /* join previous with object */
206: if (fpp == NULL)
207: bp->free = dp;
208: else if (fpp + (fpp-1)->size == dp-1) { /* adjacent */
209: (fpp-1)->size += (dp-1)->size + 1;
210: fpp->next = dp->next;
211: } else /* non-adjacent */
212: fpp->next = dp;
213: }
214:
215:
216: #if TEST_ALLOC
217:
218: Area a;
219:
220: main(argc, argv)
221: int argc;
222: char **argv;
223: {
224: int i;
225: char *p [9];
226:
227: ainit(&a);
228: for (i = 0; i < 9; i++) {
229: p[i] = alloc(124, &a);
230: printf("alloc: %x\n", p[i]);
231: }
232: for (i = 1; i < argc; i++)
233: afree(p[atoi(argv[i])], &a);
234: afreeall(&a);
235: return 0;
236: }
237:
238: void aerror(ap, msg)
239: Area *ap;
240: char *msg;
241: {
242: printf("%r\n", &msg);
243: sleep(1);
244: abort();
245: }
246:
247: #endif
248:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.