csh and tcsh work

Sources of csh/malloc.c

csh と tcsh のソース

Bill Joy

First published: October, 1978.

Copyright © 1979 Regents of the University of California.

  1. 1
    /* Copyright (c) 1979 Regents of the University of California */
  2. 2
    #ifdef debug
  3. 3
    #define ASSERT(p) if(!(p))botch("p");else
  4. 4
    botch(s)
  5. 5
    char *s;
  6. 6
    {
  7. 7
    	printf("assertion botched: %s\n",s);
  8. 8
    	abort();
  9. 9
    }
  10. 10
    #else
  11. 11
    #define ASSERT(p)
  12. 12
    #endif
  13. 13
  14. 14
    /*	avoid break bug */
  15. 15
    #ifdef pdp11
  16. 16
    #define GRANULE 64
  17. 17
    #else
  18. 18
    #define GRANULE 0
  19. 19
    #endif
  20. 20
    /*	C storage allocator
  21. 21
     *	circular first-fit strategy
  22. 22
     *	works with noncontiguous, but monotonically linked, arena
  23. 23
     *	each block is preceded by a ptr to the (pointer of)
  24. 24
     *	the next following block
  25. 25
     *	blocks are exact number of words long
  26. 26
     *	aligned to the data type requirements of ALIGN
  27. 27
     *	pointers to blocks must have BUSY bit 0
  28. 28
     *	bit in ptr is 1 for busy, 0 for idle
  29. 29
     *	gaps in arena are merely noted as busy blocks
  30. 30
     *	last block of arena (pointed to by alloct) is empty and
  31. 31
     *	has a pointer to first
  32. 32
     *	idle blocks are coalesced during space search
  33. 33
     *
  34. 34
     *	a different implementation may need to redefine
  35. 35
     *	ALIGN, NALIGN, BLOCK, BUSY, INT
  36. 36
     *	where INT is integer type to which a pointer can be cast
  37. 37
    */
  38. 38
    #define INT int
  39. 39
    #define ALIGN int
  40. 40
    #define NALIGN 1
  41. 41
    #define WORD sizeof(union store)
  42. 42
    #define BLOCK 1024	/* a multiple of WORD*/
  43. 43
    #define BUSY 1
  44. 44
    #define NULL 0
  45. 45
    #define testbusy(p) ((INT)(p)&BUSY)
  46. 46
    #define setbusy(p) (union store *)((INT)(p)|BUSY)
  47. 47
    #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
  48. 48
  49. 49
    union store { union store *ptr;
  50. 50
    	      ALIGN dummy[NALIGN];
  51. 51
    	      int calloc;	/*calloc clears an array of integers*/
  52. 52
    };
  53. 53
  54. 54
    static	union store allocs[2];	/*initial arena*/
  55. 55
    static	union store *allocp;	/*search ptr*/
  56. 56
    static	union store *alloct;	/*arena top*/
  57. 57
    static	union store *allocx;	/*for benefit of realloc*/
  58. 58
    char	*sbrk();
  59. 59
  60. 60
    char *
  61. 61
    malloc(nbytes)
  62. 62
    unsigned nbytes;
  63. 63
    {
  64. 64
    	register union store *p, *q;
  65. 65
    	register nw;
  66. 66
    	static temp;	/*coroutines assume no auto*/
  67. 67
  68. 68
    	if(allocs[0].ptr==0) {	/*first time*/
  69. 69
    		allocs[0].ptr = setbusy(&allocs[1]);
  70. 70
    		allocs[1].ptr = setbusy(&allocs[0]);
  71. 71
    		alloct = &allocs[1];
  72. 72
    		allocp = &allocs[0];
  73. 73
    	}
  74. 74
    	nw = (nbytes+WORD+WORD-1)/WORD;
  75. 75
    	ASSERT(allocp>=allocs && allocp<=alloct);
  76. 76
    	ASSERT(allock());
  77. 77
    	for(p=allocp; ; ) {
  78. 78
    		for(temp=0; ; ) {
  79. 79
    			if(!testbusy(p->ptr)) {
  80. 80
    				while(!testbusy((q=p->ptr)->ptr)) {
  81. 81
    					ASSERT(q>p&&q<alloct);
  82. 82
    					p->ptr = q->ptr;
  83. 83
    				}
  84. 84
    				if(q>=p+nw && p+nw>=p)
  85. 85
    					goto found;
  86. 86
    			}
  87. 87
    			q = p;
  88. 88
    			p = clearbusy(p->ptr);
  89. 89
    			if(p>q)
  90. 90
    				ASSERT(p<=alloct);
  91. 91
    			else if(q!=alloct || p!=allocs) {
  92. 92
    				ASSERT(q==alloct&&p==allocs);
  93. 93
    				return(NULL);
  94. 94
    			} else if(++temp>1)
  95. 95
    				break;
  96. 96
    		}
  97. 97
    		temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
  98. 98
    		q = (union store *)sbrk(0);
  99. 99
    		if(q+temp+GRANULE < q) {
  100. 100
    			return(NULL);
  101. 101
    		}
  102. 102
    		q = (union store *)sbrk(temp*WORD);
  103. 103
    		if((INT)q == -1) {
  104. 104
    			return(NULL);
  105. 105
    		}
  106. 106
    		ASSERT(q>alloct);
  107. 107
    		alloct->ptr = q;
  108. 108
    		if(q!=alloct+1)
  109. 109
    			alloct->ptr = setbusy(alloct->ptr);
  110. 110
    		alloct = q->ptr = q+temp-1;
  111. 111
    		alloct->ptr = setbusy(allocs);
  112. 112
    	}
  113. 113
    found:
  114. 114
    	allocp = p + nw;
  115. 115
    	ASSERT(allocp<=alloct);
  116. 116
    	if(q>allocp) {
  117. 117
    		allocx = allocp->ptr;
  118. 118
    		allocp->ptr = p->ptr;
  119. 119
    	}
  120. 120
    	p->ptr = setbusy(allocp);
  121. 121
    	return((char *)(p+1));
  122. 122
    }
  123. 123
  124. 124
    /*	freeing strategy tuned for LIFO allocation
  125. 125
    */
  126. 126
    free(ap)
  127. 127
    register char *ap;
  128. 128
    {
  129. 129
    	register union store *p = (union store *)ap;
  130. 130
  131. 131
    	ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
  132. 132
    	ASSERT(allock());
  133. 133
    	allocp = --p;
  134. 134
    	ASSERT(testbusy(p->ptr));
  135. 135
    	p->ptr = clearbusy(p->ptr);
  136. 136
    	ASSERT(p->ptr > allocp && p->ptr <= alloct);
  137. 137
    }
  138. 138
  139. 139
    /*	realloc(p, nbytes) reallocates a block obtained from malloc()
  140. 140
     *	and freed since last call of malloc()
  141. 141
     *	to have new size nbytes, and old content
  142. 142
     *	returns new location, or 0 on failure
  143. 143
    */
  144. 144
  145. 145
    char *
  146. 146
    realloc(p, nbytes)
  147. 147
    register union store *p;
  148. 148
    unsigned nbytes;
  149. 149
    {
  150. 150
    	register union store *q;
  151. 151
    	union store *s, *t;
  152. 152
    	register unsigned nw;
  153. 153
    	unsigned onw;
  154. 154
  155. 155
    	if(testbusy(p[-1].ptr))
  156. 156
    		free((char *)p);
  157. 157
    	onw = p[-1].ptr - p;
  158. 158
    	q = (union store *)malloc(nbytes);
  159. 159
    	if(q==NULL || q==p)
  160. 160
    		return((char *)q);
  161. 161
    	s = p;
  162. 162
    	t = q;
  163. 163
    	nw = (nbytes+WORD-1)/WORD;
  164. 164
    	if(nw<onw)
  165. 165
    		onw = nw;
  166. 166
    	while(onw--!=0)
  167. 167
    		*t++ = *s++;
  168. 168
    	if(q<p && q+nw>=p)
  169. 169
    		(q+(q+nw-p))->ptr = allocx;
  170. 170
    	return((char *)q);
  171. 171
    }
  172. 172
  173. 173
    #ifdef debug
  174. 174
    allock()
  175. 175
    {
  176. 176
    #ifdef longdebug
  177. 177
    	register union store *p;
  178. 178
    	int x;
  179. 179
    	x = 0;
  180. 180
    	for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
  181. 181
    		if(p==allocp)
  182. 182
    			x++;
  183. 183
    	}
  184. 184
    	ASSERT(p==alloct);
  185. 185
    	return(x==1|p==allocp);
  186. 186
    #else
  187. 187
    	return(1);
  188. 188
    #endif
  189. 189
    }
  190. 190
    #endif

To the top of this page