copy_string_to_graph.c 18.9 KB
Newer Older
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
1 2 3

#include <stdlib.h>

John van Groningen's avatar
John van Groningen committed
4 5 6
#ifdef _WIN64
# define Int __int64
# define INT_descriptor dINT
7
# define ARCH_64 1
John van Groningen's avatar
John van Groningen committed
8
#else
John van Groningen's avatar
John van Groningen committed
9
# if defined (MACH_O64) || defined (LINUX64)
John van Groningen's avatar
John van Groningen committed
10 11
#  define Int long long
#  define INT_descriptor dINT
12
#  define ARCH_64 1
John van Groningen's avatar
John van Groningen committed
13 14 15
# else
#  define Int int
#  define INT_descriptor INT
16
#  define ARCH_64 0
John van Groningen's avatar
John van Groningen committed
17
# endif
John van Groningen's avatar
John van Groningen committed
18
# if !(defined (LINUX32) || defined (LINUX64))
John van Groningen's avatar
John van Groningen committed
19 20 21
#  define __STRING__ _STRING__
#  define __ARRAY__ _ARRAY__
# endif
John van Groningen's avatar
John van Groningen committed
22 23
#endif

24 25 26 27 28
#if defined (MACH_O64) || defined (PIC)
// Use positions relative to _ARRAY_ for address space layout randomization systems.
#  define USE_DESC_RELATIVE_TO_ARRAY 1
#endif

John van Groningen's avatar
John van Groningen committed
29 30
extern void *INT_descriptor,*CHAR,*BOOL,*REAL,*__STRING__,*__ARRAY__;
extern Int small_integers[],static_characters[];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
31

John van Groningen's avatar
John van Groningen committed
32 33
/*inline*/
static void copy (Int *dest_p,Int *source_p,Int n_words)
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
34
{
John van Groningen's avatar
John van Groningen committed
35
	Int i;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
36 37 38 39 40

	for (i=0; i<n_words; ++i)
		dest_p[i]=source_p[i];
}

John van Groningen's avatar
John van Groningen committed
41
Int *copy_string_to_graph (Int *string_p,void *begin_free_heap,void *end_free_heap,Int **last_heap_pa)
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
42
{
John van Groningen's avatar
John van Groningen committed
43
	Int ***stack_p,***stack_begin,***stack_end,*heap_p,**arg_a,*root_node_p,n_free_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
44 45 46 47 48 49 50 51 52

	string_p+=2;

	stack_end=end_free_heap;
	stack_begin=end_free_heap;
	stack_p=end_free_heap;
		
	heap_p=begin_free_heap;
	
John van Groningen's avatar
John van Groningen committed
53
	n_free_words=(Int*)end_free_heap-(Int*)begin_free_heap;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
54 55 56 57
	arg_a=&root_node_p;

	for (;;){
		for (;;){
John van Groningen's avatar
John van Groningen committed
58
			Int desc;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
59 60 61 62 63
			
			desc=*string_p;
			
			if (--n_free_words<0){
				*last_heap_pa=heap_p+1+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
64
				return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
65 66 67
			}

			if (!(desc & 1)){
John van Groningen's avatar
John van Groningen committed
68
				*string_p=(Int)heap_p;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
69
				*arg_a=heap_p;
70
#ifdef USE_DESC_RELATIVE_TO_ARRAY
71 72
				desc+=(Int)&__ARRAY__;
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
73 74
				*heap_p=desc;
				if (desc & 2){
John van Groningen's avatar
John van Groningen committed
75
					unsigned Int arity;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
76 77 78
					
					arity=((unsigned short *)desc)[-1];
					if (arity==0){
John van Groningen's avatar
John van Groningen committed
79 80
						if (desc==(Int)&INT_descriptor+2){
							Int i;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
81 82
							
							i=string_p[1];
John van Groningen's avatar
John van Groningen committed
83 84
							if ((unsigned Int)i<=(unsigned Int)32){
								Int *a;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
85 86 87 88
								
								a=&small_integers[i<<1];
								++n_free_words;
								*arg_a=a;
John van Groningen's avatar
John van Groningen committed
89
								*string_p=(Int)a;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
90 91 92
							} else {
								if (--n_free_words<0){
									*last_heap_pa=heap_p+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
93
									return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
94 95 96 97 98 99 100
								}
								
								heap_p[1]=i;
								heap_p+=2;
							}
							string_p+=2;
							break;
John van Groningen's avatar
John van Groningen committed
101
						} else if (desc==(Int)&CHAR+2){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
102
							unsigned char c;
John van Groningen's avatar
John van Groningen committed
103
							Int *a;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
104 105
							
							c=(unsigned char)(string_p[1]);
John van Groningen's avatar
John van Groningen committed
106
							a=&static_characters[(Int)c<<1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
107 108
							++n_free_words;
							*arg_a=a;
John van Groningen's avatar
John van Groningen committed
109
							*string_p=(Int)a;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
110 111
							string_p+=2;
							break;
John van Groningen's avatar
John van Groningen committed
112
						} else if (desc==(Int)&BOOL+2
113
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
114 115 116
							|| desc==(Int)&REAL+2
#endif
						){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
117 118
							if (--n_free_words<0){
								*last_heap_pa=heap_p+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
119
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
120 121 122 123 124 125
							}
							
							heap_p[1]=string_p[1];
							string_p+=2;
							heap_p+=2;
							break;
126
#if ! ARCH_64
John van Groningen's avatar
John van Groningen committed
127
						} else if (desc==(Int)&REAL+2){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
128 129 130
							n_free_words-=2;
							if (n_free_words<0){
								*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
131
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
132 133 134 135 136 137 138
							}
							
							heap_p[1]=string_p[1];
							heap_p[2]=string_p[2];
							string_p+=3;
							heap_p+=3;
							break;
John van Groningen's avatar
John van Groningen committed
139 140 141
#endif
						} else if (desc==(Int)&__STRING__+2){
							unsigned Int length,n_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
142 143 144
							
							length=string_p[1];
							string_p+=2;
145
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
146 147
							n_words=(length+7)>>3;
#else
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
148
							n_words=(length+3)>>2;
John van Groningen's avatar
John van Groningen committed
149
#endif							
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
150 151 152
							n_free_words-=n_words+1;
							if (n_free_words<0){
								*last_heap_pa=heap_p+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
153
								return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
154 155 156 157 158 159 160 161 162
							}
													
							heap_p[1]=length;
							heap_p+=2;

							copy (heap_p,string_p,n_words);
							string_p+=n_words;
							heap_p+=n_words;
							break;
John van Groningen's avatar
John van Groningen committed
163 164
						} else if (desc==(Int)&__ARRAY__+2){
							Int array_size,elem_desc;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
165 166 167 168

							n_free_words-=2;
							if (n_free_words<0){
								*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
169
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
170 171 172 173 174
							}
							
							array_size=string_p[1];
							elem_desc=string_p[2];
							string_p+=3;
175 176

#if defined (USE_DESC_RELATIVE_TO_ARRAY)
177 178 179
							if (elem_desc!=0)
								elem_desc+=(Int)&__ARRAY__;
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
180 181 182
							heap_p[1]=array_size;
							heap_p[2]=elem_desc;
							heap_p+=3;
183
							
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
184
							if (elem_desc==0){
John van Groningen's avatar
John van Groningen committed
185
								Int i;
186 187 188 189 190 191

								n_free_words-=array_size;
								if (n_free_words<0){
									*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
									return (Int*)((Int)string_p+1);
								}
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
192 193 194
								
								stack_p-=array_size;
								if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
195
									Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
196 197 198 199 200

									extra_words=stack_begin-stack_p;
									n_free_words-=extra_words;
									if (n_free_words<0){
										*last_heap_pa=heap_p+array_size+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
201
										return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
202 203 204 205 206 207
									}
									stack_begin=stack_p;
								}
								
								i=array_size;
								while (--i>=0)
John van Groningen's avatar
John van Groningen committed
208
									stack_p[i]=(Int**)&heap_p[i];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
209 210 211

								heap_p+=array_size;
								break;
John van Groningen's avatar
John van Groningen committed
212
							} else if (elem_desc==(Int)&INT_descriptor+2
213
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
214 215 216
								|| elem_desc==(Int)&REAL+2
#endif
							){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
217 218 219
								n_free_words-=array_size;
								if (n_free_words<0){
									*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
220
									return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
221 222 223 224 225 226
								}

								copy (heap_p,string_p,array_size);
								string_p+=array_size;
								heap_p+=array_size;
								break;
227
#if ! ARCH_64
John van Groningen's avatar
John van Groningen committed
228
							} else if (elem_desc==(Int)&REAL+2){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
229 230 231 232 233
								array_size<<=1;
							
								n_free_words-=array_size;
								if (n_free_words<0){
									*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
234
									return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
235 236 237 238 239 240
								}
								
								copy (heap_p,string_p,array_size);
								string_p+=array_size;
								heap_p+=array_size;
								break;
John van Groningen's avatar
John van Groningen committed
241 242
#endif
							} else if (elem_desc==(Int)&BOOL+2){
243
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
244 245
								array_size=(array_size+7)>>3;
#else
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
246
								array_size=(array_size+3)>>2;
John van Groningen's avatar
John van Groningen committed
247
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
248 249 250
								n_free_words-=array_size;
								if (n_free_words<0){
									*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
251
									return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
252 253 254 255 256 257 258
								}
								
								copy (heap_p,string_p,array_size);
								string_p+=array_size;
								heap_p+=array_size;
								break;
							} else {
John van Groningen's avatar
John van Groningen committed
259
								Int n_field_pointers,field_size;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
260 261

								n_field_pointers=*(unsigned short *)elem_desc;
John van Groningen's avatar
John van Groningen committed
262
								field_size=((unsigned short *)elem_desc)[-1]-(Int)256;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
263 264 265 266 267 268 269

								if (n_field_pointers==0){
									array_size*=field_size;
									
									n_free_words-=array_size;
									if (n_free_words<0){
										*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
270
										return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
271 272 273 274 275 276 277
									}
																		
									copy (heap_p,string_p,array_size);
									string_p+=array_size;
									heap_p+=array_size;
									break;
								} else if (n_field_pointers==field_size){
John van Groningen's avatar
John van Groningen committed
278
									Int i;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
279 280 281
									
									array_size*=field_size;

282 283 284 285 286 287
									n_free_words-=array_size;
									if (n_free_words<0){
										*last_heap_pa=heap_p+array_size+(stack_end-stack_begin);
										return (Int*)((Int)string_p+1);
									}

Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
288 289
									stack_p-=array_size;
									if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
290
										Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
291 292 293 294 295

										extra_words=stack_begin-stack_p;
										n_free_words-=extra_words;
										if (n_free_words<0){
											*last_heap_pa=heap_p+array_size+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
296
											return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
297 298 299 300 301 302
										}
										stack_begin=stack_p;
									}
									
									i=array_size;
									while (--i>=0)
John van Groningen's avatar
John van Groningen committed
303
										stack_p[i]=(Int**)&heap_p[i];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
304 305 306 307
									
									heap_p+=array_size;
									break;
								} else {
John van Groningen's avatar
John van Groningen committed
308
									Int n_non_field_pointers,i,***pointer_p;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
309 310 311 312 313 314
									
									n_non_field_pointers=field_size-n_field_pointers;
									
									n_free_words-=array_size*field_size;
									if (n_free_words<0){
										*last_heap_pa=heap_p+array_size*field_size+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
315
										return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
316 317 318 319
									}
									
									stack_p-=array_size*n_field_pointers;
									if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
320
										Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
321 322 323 324 325

										extra_words=stack_begin-stack_p;
										n_free_words-=extra_words;
										if (n_free_words<0){
											*last_heap_pa=heap_p+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
326
											return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
327 328 329 330 331 332 333
										}
										stack_begin=stack_p;
									}
									
									pointer_p=stack_p;
									
									for (i=0; i<array_size; ++i){
John van Groningen's avatar
John van Groningen committed
334
										Int n;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
335 336 337
										
										n=n_field_pointers;
										while (--n>=0)
John van Groningen's avatar
John van Groningen committed
338
											pointer_p[n]=(Int**)&heap_p[n];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
339 340 341 342 343 344 345 346 347 348 349 350 351 352
										pointer_p+=n_field_pointers;
										heap_p+=n_field_pointers;
										
										copy (heap_p,string_p,n_non_field_pointers);
										heap_p+=n_non_field_pointers;
										string_p+=n_non_field_pointers;						
									}
									break;
								}
							}
						} else {
#ifdef OLD_DESCRIPTORS
							desc-=10;
#else
353
# if ARCH_64
John van Groningen's avatar
John van Groningen committed
354 355 356 357
							desc-=10;
# else
							desc-=6;
# endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
358 359
#endif
							++n_free_words;
John van Groningen's avatar
John van Groningen committed
360
							*arg_a=(Int*)desc;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
361 362 363 364 365 366 367
							*string_p=desc;
							++string_p;
							break;
						}
					} else if (arity==1){
						if (--n_free_words<0){
							*last_heap_pa=heap_p+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
368
							return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
369
						}
John van Groningen's avatar
John van Groningen committed
370
						arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
371 372 373 374 375 376 377
						++string_p;
						heap_p+=2;
						continue;
					} else if (arity==2){
						n_free_words-=2;
						if (n_free_words<0){
							*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
378
							return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
379 380 381 382 383
						}
						
						if (stack_p<=stack_begin){
							if (--n_free_words<0){
								*last_heap_pa=heap_p+3+(stack_end-1-stack_begin);
John van Groningen's avatar
John van Groningen committed
384
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
385 386 387 388
							}
							--stack_begin;
						}
						
John van Groningen's avatar
John van Groningen committed
389 390
						*--stack_p=(Int**)&heap_p[2];
						arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
391 392 393 394
						++string_p;
						heap_p+=3;
						continue;
					} else if (arity<256){
John van Groningen's avatar
John van Groningen committed
395
						Int n_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
396 397 398 399

						n_free_words-=arity+1;
						if (n_free_words<0){
							*last_heap_pa=heap_p+arity+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
400
							return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
401 402
						}

John van Groningen's avatar
John van Groningen committed
403 404
						arg_a=(Int**)&heap_p[1];
						heap_p[2]=(Int)&heap_p[3];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
405 406 407 408 409 410
						heap_p+=3;

						n_words=arity-1;

						stack_p-=n_words;
						if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
411
							Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
412 413 414 415 416

							extra_words=stack_begin-stack_p;
							n_free_words-=extra_words;
							if (n_free_words<0){
								*last_heap_pa=heap_p+arity-1+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
417
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
418 419 420 421 422
							}
							stack_begin=stack_p;
						}

						--n_words;
John van Groningen's avatar
John van Groningen committed
423
						stack_p[n_words]=(Int**)&heap_p[n_words];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
424
						--n_words;
John van Groningen's avatar
John van Groningen committed
425
						stack_p[n_words]=(Int**)&heap_p[n_words];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
426
						while (--n_words>=0)
John van Groningen's avatar
John van Groningen committed
427
							stack_p[n_words]=(Int**)&heap_p[n_words];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
428 429 430 431 432

						heap_p+=arity-1;
						++string_p;
						continue;
					} else {
John van Groningen's avatar
John van Groningen committed
433
						Int n_pointers;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
434 435 436 437 438 439 440
						
						n_pointers=*(unsigned short*)desc;
						arity-=256;
						
						if (arity==1){
							if (--n_free_words<0){
								*last_heap_pa=heap_p+2+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
441
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
442 443 444 445 446 447 448 449
							}
							
							if (n_pointers==0){						
								heap_p[1]=string_p[1];
								string_p+=2;
								heap_p+=2;
								break;
							} else {
John van Groningen's avatar
John van Groningen committed
450
								arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
451 452 453 454 455 456 457 458
								++string_p;
								heap_p+=2;
								continue;
							}
						} else if (arity==2){
							n_free_words-=2;
							if (n_free_words<0){
								*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
459
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
							}

							if (n_pointers==0){
								heap_p[1]=string_p[1];
								heap_p[2]=string_p[2];
								string_p+=3;
								heap_p+=3;
								break;
							} else {
								if (n_pointers==1){
									heap_p[2]=string_p[1];
									string_p+=2;
								} else {
									if (stack_p<=stack_begin){
										if (--n_free_words<0){
											*last_heap_pa=heap_p+3+1+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
476
											return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
477 478 479 480
										}
										--stack_begin;
									}
									++string_p;
John van Groningen's avatar
John van Groningen committed
481
									*--stack_p=(Int**)&heap_p[2];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
482
								}
John van Groningen's avatar
John van Groningen committed
483
								arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
484 485 486 487 488 489 490
								heap_p+=3;
								continue;							
							}
						} else {
							n_free_words-=arity+1;
							if (n_free_words<0){
								*last_heap_pa=heap_p+arity+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
491
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
492 493
							}
							
John van Groningen's avatar
John van Groningen committed
494
							heap_p[2]=(Int)&heap_p[3];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
495 496 497 498 499 500 501 502 503 504 505
							
							if (n_pointers==0){
								heap_p[1]=string_p[1];
								heap_p+=3;
								string_p+=2;
								--arity;
								copy (heap_p,string_p,arity);
								string_p+=arity;
								heap_p+=arity;
								break;
							} else {
John van Groningen's avatar
John van Groningen committed
506
								Int n_non_pointers;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
507

John van Groningen's avatar
John van Groningen committed
508
								arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
509 510 511 512 513 514
								heap_p+=3;

								n_non_pointers=arity-n_pointers;
								++string_p;

								if (n_non_pointers>0){
John van Groningen's avatar
John van Groningen committed
515
									Int *non_pointers_p;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
516 517 518 519 520 521 522 523 524

									non_pointers_p=&heap_p[n_pointers-1];

									copy (non_pointers_p,string_p,n_non_pointers);
									string_p+=n_non_pointers;
								}
								
								--n_pointers;
								if (n_pointers>0){
John van Groningen's avatar
John van Groningen committed
525
									Int i;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
526 527 528
									
									stack_p-=n_pointers;
									if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
529
										Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
530 531 532 533 534

										extra_words=stack_begin-stack_p;
										n_free_words-=extra_words;
										if (n_free_words<0){
											*last_heap_pa=heap_p+n_pointers+n_non_pointers+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
535
											return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
536 537 538 539 540 541
										}
										stack_begin=stack_p;
									}
									
									i=n_pointers;
									while (--i>=0)
John van Groningen's avatar
John van Groningen committed
542
										stack_p[i]=(Int**)&heap_p[i];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
543 544 545 546 547 548 549
								}
								heap_p+=n_pointers+n_non_pointers;
								continue;
							}
						}
					}
				} else {
John van Groningen's avatar
John van Groningen committed
550
					Int arity;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
551 552 553 554

					arity=((int*)desc)[-1];
					if (arity>1){
						if (arity<256){
John van Groningen's avatar
John van Groningen committed
555
							Int n_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
556 557 558 559
							
							n_free_words-=arity;
							if (n_free_words<0){
								*last_heap_pa=heap_p+arity+1+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
560
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
561 562 563 564 565 566
							}

							n_words=arity-1;

							stack_p-=n_words;
							if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
567
								Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
568 569 570 571 572

								extra_words=stack_begin-stack_p;
								n_free_words-=extra_words;
								if (n_free_words<0){
									*last_heap_pa=heap_p+arity+1+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
573
									return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
574 575 576 577
								}
								stack_begin=stack_p;
							}

John van Groningen's avatar
John van Groningen committed
578
							arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
579 580 581
							heap_p+=2;
							
							--n_words;
John van Groningen's avatar
John van Groningen committed
582
							stack_p[n_words]=(Int**)&heap_p[n_words];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
583
							while (--n_words>=0)
John van Groningen's avatar
John van Groningen committed
584
								stack_p[n_words]=(Int**)&heap_p[n_words];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
585 586 587

							++string_p;
							heap_p+=arity-1;
John van Groningen's avatar
John van Groningen committed
588
							continue;
589
						} else if (arity!=257){
John van Groningen's avatar
John van Groningen committed
590
							Int n_pointers,n_non_pointers,*non_pointers_p;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
591 592 593 594 595 596 597 598
							
							n_non_pointers=arity>>8;
							arity=arity & 255;
							n_pointers=arity - n_non_pointers;

							n_free_words-=arity;
							if (n_free_words<0){
								*last_heap_pa=heap_p+arity+1+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
599
								return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
600 601 602 603 604 605 606 607 608 609 610 611 612
							}

							++string_p;
							++heap_p;
							non_pointers_p=&heap_p[n_pointers];

							copy (non_pointers_p,string_p,n_non_pointers);
							string_p+=n_non_pointers;
							
							if (n_pointers==0){
								heap_p+=arity;
								break;
							} else {
John van Groningen's avatar
John van Groningen committed
613
								arg_a=(Int**)&heap_p[0];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
614 615 616 617 618 619
								++heap_p;
								if (n_pointers>1){
									--n_pointers;
									
									stack_p-=n_pointers;
									if (stack_p<stack_begin){
John van Groningen's avatar
John van Groningen committed
620
										Int extra_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
621 622 623 624 625

										extra_words=stack_begin-stack_p;
										n_free_words-=extra_words;
										if (n_free_words<0){
											*last_heap_pa=heap_p+arity+(stack_end-stack_p);
John van Groningen's avatar
John van Groningen committed
626
											return (Int*)((Int)string_p+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
627 628 629 630 631
										}
										stack_begin=stack_p;
									}
									
									--n_pointers;
John van Groningen's avatar
John van Groningen committed
632
									stack_p[n_pointers]=(Int**)&heap_p[n_pointers];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
633
									while (--n_pointers>=0)
John van Groningen's avatar
John van Groningen committed
634
										stack_p[n_pointers]=(Int**)&heap_p[n_pointers];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
635 636 637 638
								}
								heap_p+=arity-1;
								continue;
							}
639 640 641 642
						} else {
							n_free_words-=2;
							if (n_free_words<0){
								*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
643
								return (Int*)((Int)&string_p[1]+1);
644 645 646 647 648 649
							}

							heap_p[1]=string_p[1];
							string_p+=2;
							heap_p+=3;
							break;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
650 651 652 653 654
						}
					} else {
						n_free_words-=2;
						if (n_free_words<0){
							*last_heap_pa=heap_p+3+(stack_end-stack_begin);
John van Groningen's avatar
John van Groningen committed
655
							return (Int*)((Int)&string_p[1]+1);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
656 657 658 659 660 661 662
						}
					
						++string_p;
						if (arity==0){
							heap_p+=3;
							break;
						} else {
John van Groningen's avatar
John van Groningen committed
663
							arg_a=(Int**)&heap_p[1];
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
664 665 666 667 668 669
							heap_p+=3;
							continue;
						}
					}
				}
			} else {
John van Groningen's avatar
John van Groningen committed
670
				Int *node_p;
671 672 673

#ifdef THREAD
				if (desc & 2){
674
# ifdef USE_DESC_RELATIVE_TO_ARRAY
675 676
					node_p=(Int*)(desc-3)+(Int)&__ARRAY__;
# else
677
					node_p=(Int*)(desc-3);
678
# endif
679 680 681 682 683
					*arg_a=node_p;
					++string_p;
					break;
				}
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
684
				
John van Groningen's avatar
John van Groningen committed
685
				node_p=*(Int**)((Int)string_p+(desc-1));
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
				*arg_a=node_p;
				++string_p;
				break;
			}
		}

		if (stack_p==stack_end)
			break;
		
		arg_a=*stack_p++;
	}
	
	*last_heap_pa=heap_p;
	return root_node_p;
}

John van Groningen's avatar
John van Groningen committed
702
void remove_forwarding_pointers_from_string (Int *string_p,Int *end_forwarding_pointers)
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
703 704 705 706
{
	string_p+=2;

	while (string_p<end_forwarding_pointers){
John van Groningen's avatar
John van Groningen committed
707
		Int forwarding_pointer;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
708 709 710
			
		forwarding_pointer=*string_p;
		if (!(forwarding_pointer & 1)){
John van Groningen's avatar
John van Groningen committed
711
			Int desc;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
712
			
John van Groningen's avatar
John van Groningen committed
713
			desc=*(Int*)forwarding_pointer;
714
#ifdef USE_DESC_RELATIVE_TO_ARRAY
715 716
			*string_p=desc-(Int)&__ARRAY__;
#else
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
717
			*string_p=desc;
718
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
719
			if (desc & 2){
John van Groningen's avatar
John van Groningen committed
720
				unsigned Int arity;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
721 722 723
				
				arity=((unsigned short *)desc)[-1];
				if (arity==0){
John van Groningen's avatar
John van Groningen committed
724
					if (desc==(Int)&INT_descriptor+2 || desc==(Int)&CHAR+2 || desc==(Int)&BOOL+2
725
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
726 727 728
						|| desc==(Int)&REAL+2
#endif
					){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
729
						string_p+=2;
730
#if ! ARCH_64
John van Groningen's avatar
John van Groningen committed
731
					} else if (desc==(Int)&REAL+2){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
732
						string_p+=3;
John van Groningen's avatar
John van Groningen committed
733 734 735
#endif
					} else if (desc==(Int)&__STRING__+2){
						unsigned Int length,n_words;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
736 737 738
							
						length=string_p[1];
						string_p+=2;
739
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
740 741
						n_words=(length+7)>>3;
#else
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
742
						n_words=(length+3)>>2;
John van Groningen's avatar
John van Groningen committed
743
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
744
						string_p+=n_words;
John van Groningen's avatar
John van Groningen committed
745 746
					} else if (desc==(Int)&__ARRAY__+2){
						Int array_size,elem_desc;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
747 748 749 750

						array_size=string_p[1];
						elem_desc=string_p[2];
						string_p+=3;
751

Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
752
						if (elem_desc==0){
John van Groningen's avatar
John van Groningen committed
753
						} else if (elem_desc==(Int)&INT_descriptor+2
754
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
755 756 757
							|| elem_desc==(Int)&REAL+2
#endif
						){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
758
							string_p+=array_size;
759
#if ! ARCH_64
John van Groningen's avatar
John van Groningen committed
760
						} else if (elem_desc==(Int)&REAL+2){
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
761 762
							array_size<<=1;
							string_p+=array_size;
John van Groningen's avatar
John van Groningen committed
763 764
#endif
						} else if (elem_desc==(Int)&BOOL+2){
765
#if ARCH_64
John van Groningen's avatar
John van Groningen committed
766 767
							array_size=(array_size+7)>>3;
#else
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
768
							array_size=(array_size+3)>>2;
John van Groningen's avatar
John van Groningen committed
769
#endif
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
770 771
							string_p+=array_size;
						} else {
John van Groningen's avatar
John van Groningen committed
772
							Int n_field_pointers,n_non_field_pointers,field_size;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
773 774

							n_field_pointers=*(unsigned short *)elem_desc;
John van Groningen's avatar
John van Groningen committed
775
							field_size=((unsigned short *)elem_desc)[-1]-(Int)256;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
776 777 778 779 780 781 782 783 784 785
							n_non_field_pointers=field_size-n_field_pointers;
						
							string_p+=n_non_field_pointers*array_size;
						}
					} else {
						++string_p;
					}
				} else {
					++string_p;
					if (arity>=256){
John van Groningen's avatar
John van Groningen committed
786
						Int n_pointers,n_non_pointers;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
787 788 789 790 791 792 793 794

						n_pointers=*(unsigned short*)desc;
						arity-=256;
						n_non_pointers=arity-n_pointers;
						string_p+=n_non_pointers;
					}
				}
			} else {
John van Groningen's avatar
John van Groningen committed
795
				Int arity;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
796 797 798 799

				arity=((int*)desc)[-1];
				++string_p;
				if (arity>=256){
John van Groningen's avatar
John van Groningen committed
800
					Int n_non_pointers;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
801 802 803 804 805 806 807 808 809 810
					
					n_non_pointers=arity>>8;
					string_p+=n_non_pointers;
				}
			}
		} else {
			++string_p;
		}
	}
}