![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / contrib / icon / rt|
Return to gc.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / icon / rt |
1.1 root 1: #include "../h/rt.h"
2: #include "../h/gc.h"
3: #ifdef VAX
4: #define MAIN
5: #endif VAX
6: #ifdef PORT
7: #define MAIN
8: #endif PORT
9: #ifdef MAIN
10: /*
11: * hneed - insure that at least bytes of space are left in the heap.
12: * The amount of space needed is transmitted to the collector via
13: * the global variable heapneed.
14: */
15:
16: hneed(bytes)
17: unsigned bytes;
18: {
19: heapneed = bytes;
20: if (bytes > maxheap - hpfree)
21: gcollect(0);
22: }
23:
24: /*
25: * sneed - insure that at least chars of space are left in the string
26: * space. The amount of space needed is transmitted to the collector
27: * via the global variable strneed.
28: */
29:
30: sneed(chars)
31: unsigned chars;
32: {
33: strneed = chars;
34: if (chars > estrings - sfree)
35: gcollect(0);
36: }
37:
38: /*
39: * esneed - insure that there is a free co-expression stack. esfree
40: * points to the linked list of free stacks.
41: */
42:
43: esneed()
44: {
45: if (esfree == NULL)
46: gcollect(1);
47: }
48:
49: /*
50: * escollect - collect the expression stack space. This is done after
51: * the marking phase of garbage collection and the stacks that are
52: * reachable have pointers to data blocks, rather than T_ESTACK,
53: * in their type field.
54: */
55:
56: escollect()
57: {
58: register int *ep;
59: register struct b_estack *sp;
60:
61: /*
62: * Reset the type for &main.
63: */
64: BLKLOC(k_main)->estack.type = T_ESTACK;
65:
66: /*
67: * Reset the free list pointer.
68: */
69: esfree = NULL;
70:
71: /*
72: * The co-expression stacks start at stacks and lie contiguously.
73: * ep is pointed at the low word of each stack and sp is pointed
74: * at the b_estack block contained in the space for the stack.
75: * (Note that the last word of the b_estack block is the last word
76: * of the space for the co-expression stack.
77: */
78: for (ep = stacks; ep < estacks; ep += stksize) {
79: sp = (struct b_estack *) (ep + (stksize - sizeof(struct b_estack)/WORDSIZE));
80: if (blktype(sp) == T_ESTACK) {
81: /*
82: * This co-expression was not marked, so it can be collected.
83: * The stacks are linked through the first word of the stack
84: * space with esfree pointing to the last-collected stack.
85: */
86: *ep = (int) esfree;
87: esfree = ep;
88: }
89: else
90: /*
91: * The co-expression was marked, so just reset the type field.
92: */
93: blktype(sp) = T_ESTACK;
94: }
95: }
96:
97: /*
98: * collect - do a garbage collection. esneed indicates if a co-expression
99: * stack is needed.
100: */
101:
102: collect(esneed)
103: int esneed;
104: {
105: register int extra;
106: register char *newend;
107: register struct descrip *dp;
108: char *sptr;
109: extern char *brk();
110:
111: /*
112: * Reset the string qualifier free list pointer.
113: */
114: sqfree = sqlist;
115:
116: /*
117: * Mark the stacks for &main and the current co-expression.
118: */
119: mark(&k_main);
120: mark(¤t);
121: /*
122: * Mark &subject and the cached s2 and s3 strings for map().
123: */
124: mark(&k_subject);
125: mark(&maps2);
126: mark(&maps3);
127: /*
128: * Mark the tended descriptors and the global and static variables.
129: */
130: for (dp = tended; dp < etended; dp++)
131: mark(dp);
132: for (dp = globals; dp < eglobals; dp++)
133: mark(dp);
134: for (dp = statics; dp < estatics; dp++)
135: mark(dp);
136:
137: /*
138: * Collect available co-expression stacks.
139: */
140: escollect();
141: if (esneed && esfree == NULL) {
142: /*
143: * A co-expression stack is needed, but none are available. The
144: * new stack at the end of the stack space and is made available
145: * by pointing esfree at it. *estacks is zeroed to terminate the
146: * (now one element) co-expression free list.
147: */
148: esfree = estacks;
149: *estacks = 0;
150: /*
151: * Move back the end of the expression space by the size of a
152: * stack and indicate stksize words of memory are needed.
153: */
154: estacks += stksize;
155: extra = stksize*WORDSIZE;
156: newend = (char *) sqlist + extra;
157: /*
158: * This next calculation determines if there is space for the new
159: * stack, but it's not clear what all's going on here.
160: */
161: if (newend < (char *)sqlist || newend > (char *)0x7fffffff ||
162: (newend > (char *)esqlist && ((int) brk(newend) == -1)))
163: runerr(305, NULL);
164: }
165: else
166: /*
167: * Another co-expression stack is not needed.
168: */
169: extra = 0;
170:
171: /*
172: * Collect the string space, indicating that it must be moved back
173: * extra bytes.
174: */
175: scollect(extra);
176: /*
177: * sptr is post-gc value for strings. Move back pointers for estrings
178: * and sqlist according to value of extra.
179: */
180: sptr = strings + extra;
181: estrings += extra;
182: sqlist = sqlist + extra;
183: if (sqlist > esqlist)
184: esqlist = sqlist;
185:
186: /*
187: * Calculate a value for extra space. The value is (the larger of
188: * (twice the string space needed) or (the number of words currently
189: * in the string space)) plus the unallocated string space.
190: */
191: extra = (MAX(2*strneed, (estrings-(char *)estacks)/4) -
192: (estrings - extra - sfree) + (GRANSIZE-1)) & ~(GRANSIZE-1);
193:
194: while (extra > 0) {
195: /*
196: * Try to get extra more bytes of storage. If it can't be gotten,
197: * decrease the value by GRANSIZE and try again. If it's gotten,
198: * move back estrings and sqlist.
199: */
200: newend = (char *)sqlist + extra;
201: if (newend >= (char *)sqlist &&
202: (newend <= (char *)esqlist || ((int) brk(newend) != -1))) {
203: estrings += extra;
204: sqlist = (struct descrip **) newend;
205: break;
206: }
207: extra -= GRANSIZE;
208: }
209:
210: /*
211: * Adjust the pointers in the heap. Note that hpbase is the old base
212: * of the heap and estrings will be the post-gc base of the heap.
213: */
214: adjust(hpbase,estrings);
215: /*
216: * Compact the heap.
217: */
218: compact(hpbase);
219: /*
220: * Calculate a value for extra space. The value is (the larger of
221: * (twice the heap space needed) or (the number of words currently
222: * in the heap space)) plus the unallocated heap space.
223: */
224: extra = (MAX(2*heapneed, (maxheap-hpbase)/4) +
225: hpfree - maxheap + (GRANSIZE-1)) & ~(GRANSIZE-1);
226: while (extra > 0) {
227: /*
228: * Try to get extra more bytes of storage. If it can't be gotten,
229: * decrease the value by GRANSIZE and try again. If it's gotten,
230: * move back sqlist.
231: */
232: newend = (char *)sqlist + extra;
233: if (newend >= (char *)sqlist &&
234: (newend <= (char *)esqlist || ((int) brk(newend) != -1))) {
235: sqlist = (struct descrip **) newend;
236: break;
237: }
238: extra -= GRANSIZE;
239: }
240: if (sqlist > esqlist)
241: esqlist = sqlist;
242:
243: if (estrings != hpbase) {
244: /*
245: * estrings is not equal to hpbase and this indicates that the
246: * co-expression and/or string space was expanded and thus
247: * the heap must be moved. There is an assumption here that the
248: * heap always moves up in memory, i.e., the co-expression and
249: * string spaces never shrink. With this assumption in hand,
250: * the heap must be moved before the string space lest the string
251: * space overwrite heap data. The assumption is valid, but beware
252: * if shrinking regions are ever implemented.
253: */
254: mvc((unsigned)(hpfree - hpbase), hpbase, estrings);
255: hpfree += estrings - hpbase;
256: hpbase = estrings;
257: }
258: if (sptr != strings) {
259: /*
260: * sptr is not equal to strings and this indicates that the
261: * co-expression space was expanded and thus the string space
262: * must be moved up in memory.
263: */
264: mvc((unsigned)(sfree - strings), strings, sptr);
265: sfree += sptr - strings;
266: strings = sptr;
267: }
268:
269: /*
270: * Expand the heap.
271: */
272: maxheap = (char *)sqlist;
273: return;
274: }
275: /*
276: * mark - mark each accessible block in the heap and build back-list of
277: * descriptors pointing to that block. (Phase I of garbage collection.)
278: */
279:
280: mark(cdesc)
281: struct descrip *cdesc;
282: {
283: register struct descrip *ndesc;
284: register char *endblock, *block;
285: static int type;
286: static int fdesc;
287:
288: if (QUAL(*cdesc))
289: /*
290: * The descriptor is for a string, so pass the buck to marksq.
291: */
292: marksq(cdesc);
293: else if (isptr(cdesc)) {
294: /*
295: * The descriptor is a pointer to a block or a variable. Point
296: * block at the block referenced by the descriptor.
297: */
298: block = (char *) BLKLOC(*cdesc);
299: if (VAR(*cdesc) && !TVAR(*cdesc))
300: /*
301: * The descriptor is a variable; point block at the start of the
302: * block containing the descriptor that cdesc points to. For
303: * example, descriptors of this sort are created by subscripting
304: * lists.
305: */
306: block = (char *) ((int *) block - OFFSET(*cdesc));
307:
308: if (block >= hpbase && block < hpfree) {
309: /*
310: * The block is the heap (blocks outside the heap are ignored);
311: * get the type of the block.
312: */
313: type = blktype(block);
314: if (type <= MAXTYPE)
315: /*
316: * type is a valid type, indicating that this block hasn't
317: * been marked. Point endblock at the byte past the end
318: * of the block.
319: */
320: endblock = block + getsize(block);
321: /*
322: * Add cdesc to the back-chain for the block and point the
323: * block (via the type field) at cdesc.
324: */
325: BLKLOC(*cdesc) = (union block *) type;
326: blktype(block) = (int) cdesc;
327: if ((type <= MAXTYPE) && ((fdesc = firstd[(int)type]) > 0))
328: /*
329: * The block has not been marked, and it does contain descriptors.
330: * Mark each descriptor.
331: */
332: for (ndesc = (struct descrip *) (block + fdesc);
333: (char *) ndesc < endblock; ndesc++)
334: mark(ndesc);
335: }
336: if (!VAR(*cdesc) && TYPE(*cdesc) == T_ESTACK &&
337: blktype(block) <= MAXTYPE) {
338: /*
339: * cdesc points to a co-expression block that hasn't been marked.
340: * Point the block at cdesc. Sweep the co-expression's stack
341: * and mark the blocks for the activating co-expression and
342: * the co-expression's refresh block.
343: */
344: blktype(block) = (int) cdesc;
345: sweep(((struct b_estack *)block)->boundary);
346: mark(&((struct b_estack *)block)->activator);
347: mark(&((struct b_estack *)block)->freshblk);
348: }
349: }
350: }
351:
352: /*
353: * adjust - adjust pointers into heap, beginning with block oblk and
354: * basing the "new" heap at nblk. (Phase II of garbage collection.)
355: */
356:
357: adjust(oblk,nblk)
358: char *oblk, *nblk;
359: {
360: register struct descrip *nxtptr, *tptr;
361:
362: /*
363: * Loop through to end of allocated heap space moving oblk to each
364: * block in turn, using the size of a block to find the next block.
365: */
366: while (oblk < hpfree) {
367: if ((int) (nxtptr = (struct descrip *) blktype(oblk)) > MAXTYPE) {
368: /*
369: * The type field of oblk is a back-pointer. Work along the chain
370: * of back pointers, changing each block location from oblk
371: * to nblk.
372: */
373: while ((unsigned)nxtptr > MAXTYPE) {
374: tptr = nxtptr;
375: nxtptr = (struct descrip *) BLKLOC(*nxtptr);
376: if (VAR(*tptr) && !TVAR(*tptr))
377: BLKLOC(*tptr) = (union block *) ((int *) nblk + OFFSET(*tptr));
378: else
379: BLKLOC(*tptr) = (union block *) nblk;
380: }
381: blktype(oblk) = (unsigned)nxtptr | MARK;
382: nblk += getsize(oblk);
383: }
384: oblk += getsize(oblk);
385: }
386: }
387:
388: /*
389: * compact - compact good blocks in heap. (Phase III of garbage collection.)
390: */
391:
392: compact(oblk)
393: char *oblk;
394: {
395: register char *nblk;
396: register int size;
397:
398: /*
399: * Start at oblk, which happens to be hpbase.
400: */
401: nblk = oblk;
402: /*
403: * Loop through to end of allocated heap space moving oblk to each
404: * block in turn, using the size of a block to find the next block.
405: * If a block has been marked, it is copied to the location pointed
406: * at by nblk and nblk is pointed past the end of the block, which
407: * is the location to place the next good block at. Good blocks
408: * are un-marked.
409: */
410: while (oblk < hpfree) {
411: size = getsize(oblk);
412: if (blktype(oblk) & MARK) {
413: blktype(oblk) &= ~MARK;
414: if (oblk != nblk)
415: mvc((unsigned)size,oblk,nblk);
416: nblk += size;
417: }
418: oblk += size;
419: }
420: /*
421: * nblk is the location of the next free block, so now that compaction
422: * is complete, point hpfree at that location.
423: */
424: hpfree = nblk;
425: }
426:
427: /*
428: * marksq - mark a string qualifier. Strings outside the string space
429: * are ignored.
430: */
431:
432: marksq(d)
433: struct descrip *d;
434: {
435: extern char *brk();
436:
437: if (STRLOC(*d) >= strings && STRLOC(*d) < estrings) {
438: /*
439: * The string is in the string space, add it to the string qualifier
440: * list. But before adding it, expand the string qualifier list
441: * if necessary.
442: */
443: if (sqfree >= esqlist) {
444: esqlist += SQLINC;
445: if ((int) brk(esqlist) == -1)
446: runerr(303, NULL);
447: }
448: *sqfree++ = d;
449: }
450: }
451:
452: /*
453: * scollect - collect the string space. sqlist is a list of pointers to
454: * descriptors for all the reachable strings in the string space. For
455: * ease of description, it is referred to as if it were composed of
456: * descriptors rather than pointers to them.
457: */
458:
459: scollect(extra)
460: int extra;
461: {
462: register char *s, *d;
463: register struct descrip **p;
464: char *e;
465: extern int sqcmp();
466:
467: if (sqfree <= sqlist) {
468: /*
469: * There are no accessible strings, thus there are none to collect
470: * and the whole string space is free.
471: */
472: sfree = strings;
473: return;
474: }
475: /*
476: * Sort the sqlist in ascending order of string locations.
477: */
478: qsort(sqlist, sqfree-sqlist, sizeof(struct descrip *), sqcmp);
479: /*
480: * The string qualifiers are now ordered by starting location.
481: * The algorithm used is described in detail in one of the references
482: * cited in the "tour", but briefly...
483: *
484: * The string region can be thought of as being made up of clumps,
485: * where a clump is a contiguous area of strings that are referenced.
486: * For example, imagine sqlist looks like:
487: *
488: * [2,400]
489: * [3,400]
490: * [10,400]
491: * [12,415]
492: * [4,420]
493: * [3,430]
494: * [1,430]
495: *
496: * There are three clumps: The first starts at location 400 and extends
497: * to 409. The second starts at 415 and extends to 426. The third
498: * starts at 430 and extends to 432. Note that there are gaps, i.e.
499: * garbage, at 410-414 and 427-429.
500: *
501: * After collection, sqlist will look like:
502: *
503: * [2,400]
504: * [3,400]
505: * [10,400]
506: * [12,410]
507: * [4,415]
508: * [3,422]
509: * [1,422]
510: *
511: * Note how the gaps have been closed by moving the strings downward
512: * in memory.
513: *
514: * The method used is to look at each qualifier in sqlist in turn
515: * and determine which ones lie in clumps and the extent of each
516: * clump. The qualifiers referencing strings in each clump are
517: * relocated and then the clump is moved down (compacted).
518: *
519: * d points to the next free location to compact into. s is the
520: * start of the current clump and e is the end.
521: */
522: d = strings;
523: s = e = STRLOC(**sqlist);
524: /*
525: * Loop through qualifiers for accessible strings.
526: */
527: for (p = sqlist; p < sqfree; p++) {
528: if (STRLOC(**p) > e) {
529: /*
530: * p is a qualifier for a string in the next clump; the last
531: * clump is moved and s and e are set for the next clump.
532: */
533: while (s < e)
534: *d++ = *s++;
535: s = e = STRLOC(**p);
536: }
537: if (STRLOC(**p)+STRLEN(**p) > e)
538: /*
539: * p is a qualifier for a string in this clump, extend the clump.
540: */
541: e = STRLOC(**p) + STRLEN(**p);
542: /*
543: * Relocate the string qualifier.
544: */
545: STRLOC(**p) += d - s + extra;
546: }
547: /*
548: * Move the last clump.
549: */
550: while (s < e)
551: *d++ = *s++;
552: sfree = d;
553: }
554:
555: /*
556: * sqcmp - compare the location fields of two string qualifiers for qsort.
557: */
558:
559: sqcmp(q1,q2)
560: struct descrip **q1, **q2;
561: {
562: return (STRLOC(**q1) - STRLOC(**q2));
563: }
564:
565: /*
566: * mvc - move n bytes from src to dst.
567: */
568:
569: mvc(n, s, d)
570: unsigned n;
571: register char *s, *d;
572: {
573: register int words;
574: register int *srcw, *dstw;
575: int bytes;
576:
577: words = n / sizeof(int);
578: bytes = n % sizeof(int);
579:
580: srcw = (int *)s;
581: dstw = (int *)d;
582:
583: if (d < s) {
584: /*
585: * The move is from higher memory to lower memory. (It so happens
586: * that leftover bytes are not moved.)
587: */
588: while (--words >= 0)
589: *(dstw)++ = *(srcw)++;
590: while (--bytes >= 0)
591: *d++ = *s++;
592: }
593: else if (d > s) {
594: /*
595: * The move is from lower memory to higher memory.
596: */
597: s += n;
598: d += n;
599: while (--bytes >= 0)
600: *--d = *--s;
601: srcw = (int *)s;
602: dstw = (int *)d;
603: while (--words >= 0)
604: *--dstw = *--srcw;
605: }
606: }
607:
608: #endif MAIN
609: #ifdef PDP11
610: /*
611: * hneed(bytes) - insure at least 'bytes' space left in heap.
612: */
613:
614: hneed(bytes)
615: unsigned bytes;
616: {
617: heapneed = bytes;
618: if (bytes > maxheap - hpfree)
619: gcollect(0);
620: }
621:
622: /*
623: * sneed(chars) - insure at least 'chars' bytes left in string space.
624: */
625:
626: sneed(chars)
627: unsigned chars;
628: {
629: strneed = chars;
630: if (chars > estrings - sfree)
631: gcollect(0);
632: }
633:
634: /*
635: * esneed() - insure stack space free list is not empty.
636: */
637:
638: esneed()
639: {
640: if (esfree == NULL)
641: gcollect(1);
642: }
643:
644: /*
645: * escollect() - collect the expression stack space after marking.
646: */
647:
648: escollect()
649: {
650: register int *ep;
651: register struct b_estack *sp;
652: register struct descrip *nxtptr, *tptr;
653:
654: BLKLOC(k_main)->estack.type = T_ESTACK; /* must reset */
655:
656: esfree = NULL;
657: for (ep = stacks; ep < estacks; ep += stksize) {
658: sp = ep + (stksize - sizeof(struct b_estack)/2);
659: if (blktype(sp) == T_ESTACK) { /* add to free list */
660: *ep = esfree;
661: esfree = ep;
662: }
663: else /* adjust type field */
664: blktype(sp) = T_ESTACK;
665: }
666: }
667:
668: /*
669: * collect - call the heap garbage collector.
670: */
671:
672: collect(esneed)
673: int esneed;
674: {
675: register int extra;
676: register char *newend;
677: register struct descrip *dp;
678: char *sptr;
679: extern char *brk();
680:
681: sqfree = sqlist; /* initialize string qualifier list */
682:
683: mark(&k_main); /* mark main stack */
684: mark(¤t); /* mark current stack */
685: mark(&k_subject); /* mark tended descriptors */
686: mark(&maps2);
687: mark(&maps3);
688: for (dp = tended; dp < etended; dp++)
689: mark(dp);
690: for (dp = globals; dp < eglobals; dp++)
691: mark(dp);
692: for (dp = statics; dp < estatics; dp++)
693: mark(dp);
694:
695: escollect(); /* collect available expression stacks */
696: if (esneed && esfree == NULL) {
697: esfree = estacks; /* need to make room for another stack */
698: *estacks = 0;
699: estacks += stksize;
700: extra = stksize*sizeof(int); /* string and heap ptrs are chars */
701: newend = sqlist + extra;
702: if (newend < (char *)sqlist || newend > (char *)0177700 ||
703: (newend > (char *)esqlist && brk(newend) == -1))
704: runerr(305, NULL);
705: }
706: else
707: extra = 0;
708:
709: scollect(extra); /* collect string space */
710: sptr = strings + extra; /* remember new location of string space */
711: estrings += extra;
712: (char *)sqlist += extra;
713: if (sqlist > esqlist)
714: esqlist = sqlist;
715:
716: extra = (MAX(2*strneed, (estrings-estacks)/4) -
717: (estrings - extra - sfree) + 63) & ~077;
718: while (extra > 0) { /* need breathing room? */
719: newend = (char *)sqlist + extra;
720: if (newend >= (char *)sqlist && newend <= (char *)0177700 &&
721: (newend <= (char *)esqlist || brk(newend) != -1)) {
722: estrings += extra;
723: sqlist = newend;
724: break;
725: }
726: extra -= 64;
727: }
728: adjust(hpbase,estrings); /* adjust pointers into heap */
729: compact(hpbase); /* compact heap */
730: extra = (MAX(2*heapneed, (maxheap-hpbase)/4) +
731: hpfree - maxheap + 63) & ~077;
732: while (extra > 0) { /* need breathing room? */
733: newend = (char *)sqlist + extra;
734: if (newend >= (char *)sqlist && newend <= (char *)0177700 &&
735: (newend <= (char *)esqlist || brk(newend) != -1)) {
736: sqlist = newend;
737: break;
738: }
739: extra -= 64;
740: }
741: if (sqlist > esqlist)
742: esqlist = sqlist;
743: if (estrings != hpbase) { /* move heap */
744: mvc((unsigned)(hpfree - hpbase), hpbase, estrings);
745: hpfree += estrings - hpbase;
746: hpbase = estrings;
747: }
748: if (sptr != strings) { /* move string space */
749: mvc((unsigned)(sfree - strings), strings, sptr);
750: sfree += sptr - strings;
751: strings = sptr;
752: }
753: maxheap = (char *)sqlist; /* expand heap */
754:
755: return;
756: }
757:
758: /*
759: * mark - mark each accessible block in the heap and build back-list of
760: * descriptors pointing to that block. (Phase I of garbage collection)
761: */
762:
763: mark(cdesc)
764: struct descrip *cdesc; /* current descriptor */
765: {
766: register struct descrip *ndesc;
767: register char *endblock, *block;
768: static char *type;
769: static int fdesc;
770:
771: if (QUAL(*cdesc)) /* if descriptor is a string qualifier, */
772: marksq(cdesc); /* mark it for scollect */
773: else if (isptr(cdesc)) { /* ok, descriptor is a pointer */
774: block = BLKLOC(*cdesc); /* get pointer to top of block */
775: if (VAR(*cdesc) && !TVAR(*cdesc)) /* if variable, need offset */
776: block = (int *)block - OFFSET(*cdesc);
777:
778: if (block >= hpbase && block < hpfree) { /* insure it points to heap */
779: type = blktype(block); /* save type and end of block */
780: if (type <= MAXTYPE)
781: endblock = block + getsize(block);
782: BLKLOC(*cdesc) = type; /* add descriptor to back chain */
783: blktype(block) = cdesc;
784: /* sweep descriptors in block */
785: if ((type <= MAXTYPE) && ((fdesc = firstd[(int)type]) > 0))
786: for (ndesc = block + fdesc; ndesc < endblock; ndesc++)
787: mark(ndesc);
788: }
789: if (!VAR(*cdesc) && TYPE(*cdesc) == T_ESTACK &&
790: (char *)blktype(block) <= MAXTYPE) {
791: blktype(block) = cdesc; /* note block as visited */
792: sweep(((struct b_estack *)block)->boundary);
793: mark(&((struct b_estack *)block)->activator);
794: mark(&((struct b_estack *)block)->freshblk);
795: }
796: }
797: }
798:
799: /*
800: * adjust - adjust pointers into heap, beginning with heapblock 'oblk'.
801: * (Phase II of garbage collection)
802: */
803:
804: adjust(oblk,nblk)
805: char *oblk, *nblk;
806: {
807: register struct descrip *nxtptr, *tptr;
808:
809: while (oblk < hpfree) { /* linear sweep through heap */
810: if ((nxtptr = blktype(oblk)) > MAXTYPE) {
811: while ((unsigned)nxtptr > MAXTYPE) {
812: tptr = nxtptr;
813: nxtptr = BLKLOC(*nxtptr);
814: if (VAR(*tptr) && !TVAR(*tptr))
815: BLKLOC(*tptr) = (int *)nblk + OFFSET(*tptr);
816: else
817: BLKLOC(*tptr) = nblk;
818: }
819: blktype(oblk) = (unsigned)nxtptr | MARK;
820: nblk += getsize(oblk);
821: }
822: oblk += getsize(oblk);
823: }
824: }
825:
826: /*
827: * compact - compact good blocks in heap, beginning with block 'oblk'.
828: * (Phase III of garbage collection)
829: */
830:
831: compact(oblk)
832: char *oblk;
833: {
834: register char *nblk;
835: register int size;
836:
837: nblk = oblk; /* linear sweep through heap */
838: while (oblk < hpfree) {
839: size = getsize(oblk);
840: if (blktype(oblk) & MARK) { /* move good block */
841: blktype(oblk) &= ~MARK; /* turn off mark */
842: if (oblk != nblk)
843: mvc((unsigned)size,oblk,nblk);
844: nblk += size;
845: }
846: oblk += size;
847: }
848: hpfree = nblk; /* reset free space pointer */
849: }
850:
851: /*
852: * marksq - mark a string qualifier. If it points into the
853: * string space, put a pointer to it in the string qualifier
854: * list.
855: */
856:
857: marksq(d)
858: struct descrip *d;
859: {
860: extern char *brk();
861:
862: if (STRLOC(*d) >= strings && STRLOC(*d) < estrings) {
863: if (sqfree >= esqlist) {
864: esqlist += SQLINC;
865: if ((int)brk(esqlist) == -1)
866: runerr(303, NULL);
867: }
868: *sqfree++ = d;
869: }
870: }
871:
872: /*
873: * scollect - collect the string space.
874: * A list of string qualifiers points to all valid strings.
875: */
876:
877: scollect(extra)
878: int extra;
879: {
880: register char *s, *d;
881: register struct descrip **p;
882: char *e;
883: extern int sqcmp();
884:
885: if (sqfree <= sqlist) {
886: sfree = strings;
887: return;
888: }
889: qsort(sqlist, sqfree-sqlist, sizeof(struct descrip *), sqcmp);
890: d = strings;
891: s = e = STRLOC(**sqlist);
892: for (p = sqlist; p < sqfree; p++) {
893: if (STRLOC(**p) > e) { /* outside last clump */
894: while (s < e) /* move the clump */
895: *d++ = *s++;
896: s = e = STRLOC(**p); /* start a new clump */
897: }
898: if (STRLOC(**p)+STRLEN(**p) > e) /* extend the clump */
899: e = STRLOC(**p) + STRLEN(**p);
900: STRLOC(**p) += d - s + extra; /* relocate the string qualifier */
901: }
902: while (s < e) /* move the last clump */
903: *d++ = *s++;
904: sfree = d;
905: }
906:
907: /*
908: * sqcmp - compare the location fields of two string qualifiers for qsort.
909: */
910:
911: sqcmp(q1,q2)
912: struct descrip **q1, **q2;
913: {
914: return (STRLOC(**q1) - STRLOC(**q2));
915: }
916:
917: /*
918: * mvc - move n bytes from src to dst.
919: * src and dst must be at word boundaries.
920: */
921:
922: mvc(n, s, d)
923: unsigned n;
924: register char *s, *d;
925: {
926: register int words;
927: int bytes;
928:
929: words = n / sizeof(int);
930: bytes = n % sizeof(int);
931:
932: if (d < s) { /* move back */
933: while (--words >= 0)
934: *((int *)d)++ = *((int *)s)++;
935: while (--bytes >= 0)
936: *d++ = *s++;
937: }
938: else if (d > s) { /* move forward */
939: s += n;
940: d += n;
941: while (--bytes >= 0)
942: *--d = *--s;
943: while (--words >= 0)
944: *--(int *)d = *--(int *)s;
945: }
946: }
947: #endif PDP11
948:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.