ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/ambient.c
Revision: 2.50
Committed: Thu Jun 5 19:29:34 2003 UTC (20 years, 10 months ago) by schorsch
Content type: text/plain
Branch: MAIN
Changes since 2.49: +3 -7 lines
Log Message:
Macros for setting binary file mode. Replacing MSDOS by _WIN32.

File Contents

# User Rev Content
1 greg 1.1 #ifndef lint
2 schorsch 2.50 static const char RCSid[] = "$Id: ambient.c,v 2.49 2003/05/15 05:13:35 greg Exp $";
3 greg 1.1 #endif
4     /*
5     * ambient.c - routines dealing with ambient (inter-reflected) component.
6 greg 2.47 *
7     * Declarations of external symbols in ambient.h
8     */
9    
10 greg 2.48 #include "copyright.h"
11 greg 1.1
12 schorsch 2.50 #include "platform.h"
13 greg 1.1 #include "ray.h"
14 greg 1.8 #include "otypes.h"
15 greg 1.14 #include "ambient.h"
16 greg 1.1 #include "random.h"
17    
18 greg 2.32 #ifndef OCTSCALE
19 greg 2.29 #define OCTSCALE 1.0 /* ceil((valid rad.)/(cube size)) */
20 greg 2.32 #endif
21 greg 1.1
22 greg 2.27 extern char *shm_boundary; /* memory sharing boundary */
23 greg 2.26
24 greg 2.12 #define MAXASET 511 /* maximum number of elements in ambient set */
25     OBJECT ambset[MAXASET+1]={0}; /* ambient include/exclude set */
26 greg 1.1
27 greg 2.12 double maxarad; /* maximum ambient radius */
28     double minarad; /* minimum ambient radius */
29 greg 1.1
30 greg 2.12 static AMBTREE atrunk; /* our ambient trunk node */
31 greg 1.1
32     static FILE *ambfp = NULL; /* ambient file pointer */
33 greg 2.16 static int nunflshed = 0; /* number of unflushed ambient values */
34 greg 1.1
35 greg 2.26 #ifndef SORT_THRESH
36 greg 2.49 #ifdef SMLMEM
37     #define SORT_THRESH ((3L<<20)/sizeof(AMBVAL))
38     #else
39 greg 2.27 #define SORT_THRESH ((9L<<20)/sizeof(AMBVAL))
40 greg 2.26 #endif
41     #endif
42     #ifndef SORT_INTVL
43 greg 2.41 #define SORT_INTVL (SORT_THRESH<<1)
44 greg 2.26 #endif
45 greg 2.28 #ifndef MAX_SORT_INTVL
46 greg 2.41 #define MAX_SORT_INTVL (SORT_INTVL<<6)
47 greg 2.28 #endif
48 greg 2.26
49 gregl 2.43 static double avsum = 0.; /* computed ambient value sum (log) */
50     static unsigned int navsum = 0; /* number of values in avsum */
51 greg 2.35 static unsigned int nambvals = 0; /* total number of indirect values */
52     static unsigned int nambshare = 0; /* number of values from file */
53 greg 2.27 static unsigned long ambclock = 0; /* ambient access clock */
54     static unsigned long lastsort = 0; /* time of last value sort */
55 greg 2.26 static long sortintvl = SORT_INTVL; /* time until next sort */
56 greg 2.47 static FILE *ambinp = NULL; /* auxiliary file for input */
57     static long lastpos = -1; /* last flush position */
58 greg 2.26
59     #define MAXACLOCK (1L<<30) /* clock turnover value */
60 greg 2.27 /*
61     * Track access times unless we are sharing ambient values
62     * through memory on a multiprocessor, when we want to avoid
63 greg 2.35 * claiming our own memory (copy on write). Go ahead anyway
64     * if more than two thirds of our values are unshared.
65 gregl 2.43 * Compile with -Dtracktime=0 to turn this code off.
66 greg 2.27 */
67 gregl 2.43 #ifndef tracktime
68 greg 2.35 #define tracktime (shm_boundary == NULL || nambvals > 3*nambshare)
69 gregl 2.43 #endif
70 greg 2.26
71 greg 2.12 #define AMBFLUSH (BUFSIZ/AMBVALSIZ)
72 greg 2.6
73 greg 2.47 #define newambval() (AMBVAL *)malloc(sizeof(AMBVAL))
74     #define freeav(av) free((void *)av);
75 greg 1.1
76 greg 2.47 static void initambfile(), avsave(), avinsert(), sortambvals(), unloadatree();
77     static int avlmemi();
78 greg 2.20 static AMBVAL *avstore();
79 greg 2.19 #ifdef F_SETLKW
80 greg 2.47 static void aflock();
81 greg 2.19 #endif
82 greg 1.1
83 greg 2.7
84 greg 2.47 void
85 greg 2.3 setambres(ar) /* set ambient resolution */
86     int ar;
87     {
88 greg 2.21 ambres = ar < 0 ? 0 : ar; /* may be done already */
89 greg 2.3 /* set min & max radii */
90     if (ar <= 0) {
91 greg 2.25 minarad = 0;
92 greg 2.3 maxarad = thescene.cusize / 2.0;
93     } else {
94     minarad = thescene.cusize / ar;
95 greg 2.30 maxarad = 64 * minarad; /* heuristic */
96 greg 2.3 if (maxarad > thescene.cusize / 2.0)
97     maxarad = thescene.cusize / 2.0;
98     }
99 greg 2.25 if (minarad <= FTINY)
100     minarad = 10*FTINY;
101     if (maxarad <= minarad)
102     maxarad = 64 * minarad;
103 greg 2.3 }
104    
105    
106 greg 2.47 void
107 greg 2.21 setambacc(newa) /* set ambient accuracy */
108 greg 2.20 double newa;
109     {
110 greg 2.33 double ambdiff;
111 greg 2.20
112 greg 2.33 if (newa < 0.0)
113     newa = 0.0;
114     ambdiff = fabs(newa - ambacc);
115     if (ambdiff >= .01 && (ambacc = newa) > FTINY && nambvals > 0)
116     sortambvals(1); /* rebuild tree */
117 greg 2.20 }
118    
119    
120 greg 2.47 void
121     setambient() /* initialize calculation */
122 greg 1.1 {
123 gwlarson 2.46 int readonly = 0;
124 greg 2.37 long pos, flen;
125 greg 2.12 AMBVAL amb;
126 greg 2.47 /* make sure we're fresh */
127     ambdone();
128 greg 2.3 /* init ambient limits */
129     setambres(ambres);
130 greg 2.21 setambacc(ambacc);
131 greg 2.47 if (ambfile == NULL || !ambfile[0])
132 greg 2.19 return;
133 greg 2.20 if (ambacc <= FTINY) {
134 greg 2.21 sprintf(errmsg, "zero ambient accuracy so \"%s\" not opened",
135 greg 2.47 ambfile);
136 greg 2.20 error(WARNING, errmsg);
137     return;
138     }
139 greg 2.3 /* open ambient file */
140 greg 2.47 if ((ambfp = fopen(ambfile, "r+")) == NULL)
141     readonly = (ambfp = fopen(ambfile, "r")) != NULL;
142 gwlarson 2.46 if (ambfp != NULL) {
143     initambfile(0); /* file exists */
144 greg 2.37 pos = ftell(ambfp);
145 greg 2.19 while (readambval(&amb, ambfp))
146 greg 2.21 avinsert(avstore(&amb));
147 gwlarson 2.46 nambshare = nambvals; /* share loaded values */
148     if (readonly) {
149     sprintf(errmsg,
150     "loaded %u values from read-only ambient file",
151     nambvals);
152     error(WARNING, errmsg);
153     fclose(ambfp); /* close file so no writes */
154     ambfp = NULL;
155     return; /* avoid ambsync() */
156     }
157     /* align file pointer */
158 greg 2.37 pos += (long)nambvals*AMBVALSIZ;
159 greg 2.47 flen = lseek(fileno(ambfp), (off_t)0L, 2);
160 greg 2.37 if (flen != pos) {
161 greg 2.42 sprintf(errmsg,
162 greg 2.37 "ignoring last %ld values in ambient file (corrupted)",
163     (flen - pos)/AMBVALSIZ);
164 greg 2.42 error(WARNING, errmsg);
165 greg 2.37 fseek(ambfp, pos, 0);
166 greg 2.47 ftruncate(fileno(ambfp), (off_t)pos);
167 greg 2.37 }
168 greg 2.47 } else if ((ambfp = fopen(ambfile, "w+")) != NULL) {
169 gwlarson 2.46 initambfile(1); /* else create new file */
170     } else {
171 greg 2.47 sprintf(errmsg, "cannot open ambient file \"%s\"", ambfile);
172 greg 2.19 error(SYSTEM, errmsg);
173 greg 2.16 }
174 greg 2.19 nunflshed++; /* lie */
175     ambsync();
176 greg 1.8 }
177    
178    
179 greg 2.47 void
180     ambdone() /* close ambient file and free memory */
181     {
182     if (ambfp != NULL) { /* close ambient file */
183     ambsync();
184     fclose(ambfp);
185     ambfp = NULL;
186     if (ambinp != NULL) {
187     fclose(ambinp);
188     ambinp = NULL;
189     }
190     lastpos = -1;
191     }
192     /* free ambient tree */
193     unloadatree(&atrunk, free);
194     /* reset state variables */
195     avsum = 0.;
196     navsum = 0;
197     nambvals = 0;
198     nambshare = 0;
199     ambclock = 0;
200     lastsort = 0;
201     sortintvl = SORT_INTVL;
202     }
203    
204    
205     void
206 greg 1.8 ambnotify(obj) /* record new modifier */
207 greg 2.12 OBJECT obj;
208 greg 1.8 {
209 greg 1.11 static int hitlimit = 0;
210 greg 2.47 register OBJREC *o;
211 greg 1.8 register char **amblp;
212    
213 greg 2.47 if (obj == OVOID) { /* starting over */
214     ambset[0] = 0;
215     hitlimit = 0;
216     return;
217     }
218     o = objptr(obj);
219 greg 1.11 if (hitlimit || !ismodifier(o->otype))
220 greg 1.8 return;
221     for (amblp = amblist; *amblp != NULL; amblp++)
222     if (!strcmp(o->oname, *amblp)) {
223 greg 1.11 if (ambset[0] >= MAXASET) {
224     error(WARNING, "too many modifiers in ambient list");
225     hitlimit++;
226     return; /* should this be fatal? */
227     }
228 greg 1.8 insertelem(ambset, obj);
229     return;
230 greg 1.1 }
231     }
232    
233    
234 greg 2.47 void
235 greg 2.34 ambient(acol, r, nrm) /* compute ambient component for ray */
236 greg 1.1 COLOR acol;
237     register RAY *r;
238 greg 2.34 FVECT nrm;
239 greg 1.1 {
240     static int rdepth = 0; /* ambient recursion */
241 gregl 2.43 double d, l;
242 greg 1.1
243     if (ambdiv <= 0) /* no ambient calculation */
244     goto dumbamb;
245     /* check number of bounces */
246 greg 1.16 if (rdepth >= ambounce)
247 greg 1.1 goto dumbamb;
248     /* check ambient list */
249     if (ambincl != -1 && r->ro != NULL &&
250     ambincl != inset(ambset, r->ro->omod))
251     goto dumbamb;
252    
253     if (ambacc <= FTINY) { /* no ambient storage */
254 greg 1.16 rdepth++;
255     d = doambient(acol, r, r->rweight, NULL, NULL);
256     rdepth--;
257 greg 2.32 if (d <= FTINY)
258 greg 1.1 goto dumbamb;
259 greg 1.16 return;
260 greg 1.1 }
261 greg 2.40
262     if (tracktime) /* sort to minimize thrashing */
263     sortambvals(0);
264 greg 1.1 /* get ambient value */
265     setcolor(acol, 0.0, 0.0, 0.0);
266 greg 2.34 d = sumambient(acol, r, nrm, rdepth,
267 greg 1.16 &atrunk, thescene.cuorg, thescene.cusize);
268 greg 2.32 if (d > FTINY) {
269 greg 1.16 scalecolor(acol, 1.0/d);
270 greg 2.32 return;
271 greg 1.16 }
272 greg 2.33 rdepth++; /* need to cache new value */
273 greg 2.34 d = makeambient(acol, r, nrm, rdepth-1);
274 greg 2.32 rdepth--;
275 greg 1.16 if (d > FTINY)
276     return;
277 greg 1.1 dumbamb: /* return global value */
278     copycolor(acol, ambval);
279 gregl 2.43 if (ambvwt <= 0 | navsum == 0)
280 greg 2.32 return;
281 gregl 2.43 l = bright(ambval); /* average in computations */
282     if (l > FTINY) {
283     d = (log(l)*(double)ambvwt + avsum) /
284     (double)(ambvwt + navsum);
285     d = exp(d) / l;
286     scalecolor(acol, d); /* apply color of ambval */
287     } else {
288     d = exp( avsum / (double)navsum );
289     setcolor(acol, d, d, d); /* neutral color */
290     }
291 greg 1.1 }
292    
293    
294     double
295 greg 2.34 sumambient(acol, r, rn, al, at, c0, s) /* get interpolated ambient value */
296 greg 1.1 COLOR acol;
297     register RAY *r;
298 greg 2.34 FVECT rn;
299 greg 1.16 int al;
300 greg 2.12 AMBTREE *at;
301 greg 1.1 FVECT c0;
302 greg 2.12 double s;
303 greg 1.1 {
304 greg 2.12 double d, e1, e2, wt, wsum;
305 greg 1.1 COLOR ct;
306     FVECT ck0;
307     int i;
308     register int j;
309 greg 2.12 register AMBVAL *av;
310 greg 2.29
311     wsum = 0.0;
312 greg 1.7 /* do this node */
313 greg 1.1 for (av = at->alist; av != NULL; av = av->next) {
314 greg 2.47 double rn_dot = -2.0;
315 greg 2.26 if (tracktime)
316 greg 2.40 av->latick = ambclock;
317 greg 1.1 /*
318 greg 1.16 * Ambient level test.
319 greg 1.1 */
320 greg 2.23 if (av->lvl > al) /* list sorted, so this works */
321     break;
322     if (av->weight < r->rweight-FTINY)
323 greg 1.1 continue;
324     /*
325     * Ambient radius test.
326     */
327 greg 2.29 d = av->pos[0] - r->rop[0];
328     e1 = d * d;
329     d = av->pos[1] - r->rop[1];
330     e1 += d * d;
331     d = av->pos[2] - r->rop[2];
332     e1 += d * d;
333 greg 1.1 e1 /= av->rad * av->rad;
334     if (e1 > ambacc*ambacc*1.21)
335     continue;
336     /*
337 greg 2.47 * Direction test using closest normal.
338 greg 1.1 */
339 greg 2.47 d = DOT(av->dir, r->ron);
340     if (rn != r->ron) {
341     rn_dot = DOT(av->dir, rn);
342     if (rn_dot > 1.0-FTINY)
343     rn_dot = 1.0-FTINY;
344     if (rn_dot >= d-FTINY) {
345     d = rn_dot;
346     rn_dot = -2.0;
347     }
348     }
349     e2 = (1.0 - d) * r->rweight;
350 greg 1.1 if (e2 < 0.0) e2 = 0.0;
351     if (e1 + e2 > ambacc*ambacc*1.21)
352     continue;
353     /*
354     * Ray behind test.
355     */
356     d = 0.0;
357     for (j = 0; j < 3; j++)
358     d += (r->rop[j] - av->pos[j]) *
359     (av->dir[j] + r->ron[j]);
360 greg 1.18 if (d*0.5 < -minarad*ambacc-.001)
361 greg 1.1 continue;
362     /*
363     * Jittering final test reduces image artifacts.
364     */
365 greg 2.47 e1 = sqrt(e1);
366     e2 = sqrt(e2);
367     wt = e1 + e2;
368 greg 2.31 if (wt > ambacc*(.9+.2*urand(9015+samplendx)))
369 greg 1.1 continue;
370 greg 2.47 /*
371     * Recompute directional error using perturbed normal
372     */
373     if (rn_dot > 0.0) {
374     e2 = sqrt((1.0 - rn_dot)*r->rweight);
375     wt = e1 + e2;
376     }
377 greg 1.1 if (wt <= 1e-3)
378     wt = 1e3;
379     else
380     wt = 1.0 / wt;
381     wsum += wt;
382 greg 2.34 extambient(ct, av, r->rop, rn);
383 greg 1.1 scalecolor(ct, wt);
384     addcolor(acol, ct);
385 greg 1.7 }
386     if (at->kid == NULL)
387     return(wsum);
388     /* do children */
389     s *= 0.5;
390     for (i = 0; i < 8; i++) {
391     for (j = 0; j < 3; j++) {
392     ck0[j] = c0[j];
393     if (1<<j & i)
394     ck0[j] += s;
395     if (r->rop[j] < ck0[j] - OCTSCALE*s)
396     break;
397     if (r->rop[j] > ck0[j] + (1.0+OCTSCALE)*s)
398     break;
399     }
400     if (j == 3)
401 greg 2.34 wsum += sumambient(acol, r, rn, al, at->kid+i, ck0, s);
402 greg 1.1 }
403     return(wsum);
404     }
405    
406    
407     double
408 greg 2.34 makeambient(acol, r, rn, al) /* make a new ambient value */
409 greg 1.1 COLOR acol;
410     register RAY *r;
411 greg 2.34 FVECT rn;
412 greg 1.16 int al;
413 greg 1.1 {
414 greg 2.12 AMBVAL amb;
415 greg 1.14 FVECT gp, gd;
416 greg 1.16 /* compute weight */
417     amb.weight = pow(AVGREFL, (double)al);
418 greg 2.33 if (r->rweight < 0.1*amb.weight) /* heuristic */
419 greg 1.16 amb.weight = r->rweight;
420     /* compute ambient */
421     amb.rad = doambient(acol, r, amb.weight, gp, gd);
422 greg 2.33 if (amb.rad <= FTINY)
423 greg 1.1 return(0.0);
424     /* store it */
425     VCOPY(amb.pos, r->rop);
426     VCOPY(amb.dir, r->ron);
427 greg 1.16 amb.lvl = al;
428 greg 1.1 copycolor(amb.val, acol);
429 greg 1.14 VCOPY(amb.gpos, gp);
430     VCOPY(amb.gdir, gd);
431 greg 1.1 /* insert into tree */
432 greg 2.7 avsave(&amb); /* and save to file */
433 greg 2.34 if (rn != r->ron)
434     extambient(acol, &amb, r->rop, rn); /* texture */
435 greg 1.1 return(amb.rad);
436 greg 1.15 }
437    
438    
439 greg 2.47 void
440 greg 1.15 extambient(cr, ap, pv, nv) /* extrapolate value at pv, nv */
441     COLOR cr;
442 greg 2.12 register AMBVAL *ap;
443 greg 1.15 FVECT pv, nv;
444     {
445 gwlarson 2.45 FVECT v1;
446 greg 1.15 register int i;
447 greg 2.12 double d;
448 greg 1.15
449     d = 1.0; /* zeroeth order */
450     /* gradient due to translation */
451     for (i = 0; i < 3; i++)
452     d += ap->gpos[i]*(pv[i]-ap->pos[i]);
453     /* gradient due to rotation */
454 gwlarson 2.45 VCROSS(v1, ap->dir, nv);
455     d += DOT(ap->gdir, v1);
456 greg 1.15 if (d <= 0.0) {
457     setcolor(cr, 0.0, 0.0, 0.0);
458     return;
459     }
460     copycolor(cr, ap->val);
461     scalecolor(cr, d);
462 greg 1.1 }
463    
464    
465 greg 2.47 static void
466 greg 2.9 initambfile(creat) /* initialize ambient file */
467     int creat;
468     {
469 greg 2.47 extern char *progname, *octname;
470     static char *mybuf = NULL;
471 greg 2.9
472 greg 2.19 #ifdef F_SETLKW
473     aflock(creat ? F_WRLCK : F_RDLCK);
474     #endif
475 schorsch 2.50 SET_FILE_BINARY(ambfp);
476 greg 2.47 if (mybuf == NULL)
477     mybuf = (char *)bmalloc(BUFSIZ+8);
478     setbuf(ambfp, mybuf);
479 greg 2.9 if (creat) { /* new file */
480 greg 2.24 newheader("RADIANCE", ambfp);
481 greg 2.41 fprintf(ambfp, "%s -av %g %g %g -aw %d -ab %d -aa %g ",
482 greg 2.9 progname, colval(ambval,RED),
483     colval(ambval,GRN), colval(ambval,BLU),
484 greg 2.41 ambvwt, ambounce, ambacc);
485 greg 2.47 fprintf(ambfp, "-ad %d -as %d -ar %d ",
486     ambdiv, ambssamp, ambres);
487     if (octname != NULL)
488     printargs(1, &octname, ambfp);
489     else
490     fputc('\n', ambfp);
491 greg 2.9 fprintf(ambfp, "SOFTWARE= %s\n", VersionID);
492 greg 2.47 fputnow(ambfp);
493 greg 2.9 fputformat(AMBFMT, ambfp);
494     putc('\n', ambfp);
495     putambmagic(ambfp);
496 greg 2.17 } else if (checkheader(ambfp, AMBFMT, NULL) < 0 || !hasambmagic(ambfp))
497     error(USER, "bad ambient file");
498 greg 2.9 }
499    
500    
501 greg 2.47 static void
502 greg 2.7 avsave(av) /* insert and save an ambient value */
503 greg 2.12 AMBVAL *av;
504 greg 1.1 {
505 greg 2.21 avinsert(avstore(av));
506 greg 1.1 if (ambfp == NULL)
507     return;
508 greg 2.5 if (writambval(av, ambfp) < 0)
509 greg 1.1 goto writerr;
510 greg 2.16 if (++nunflshed >= AMBFLUSH)
511 greg 2.7 if (ambsync() == EOF)
512 greg 1.1 goto writerr;
513     return;
514     writerr:
515 greg 2.47 error(SYSTEM, "error writing to ambient file");
516 greg 1.1 }
517    
518    
519 greg 2.20 static AMBVAL *
520     avstore(aval) /* allocate memory and store aval */
521     register AMBVAL *aval;
522     {
523     register AMBVAL *av;
524 gregl 2.43 double d;
525 greg 2.20
526     if ((av = newambval()) == NULL)
527     error(SYSTEM, "out of memory in avstore");
528     copystruct(av, aval);
529 greg 2.26 av->latick = ambclock;
530     av->next = NULL;
531     nambvals++;
532 gregl 2.43 d = bright(av->val);
533     if (d > FTINY) { /* add to log sum for averaging */
534     avsum += log(d);
535     navsum++;
536     }
537 greg 2.20 return(av);
538     }
539    
540    
541 greg 2.26 #define ATALLOCSZ 512 /* #/8 trees to allocate at once */
542    
543     static AMBTREE *atfreelist = NULL; /* free ambient tree structures */
544    
545    
546 greg 2.47 static AMBTREE *
547 greg 2.26 newambtree() /* allocate 8 ambient tree structs */
548     {
549     register AMBTREE *atp, *upperlim;
550    
551     if (atfreelist == NULL) { /* get more nodes */
552 greg 2.47 atfreelist = (AMBTREE *)malloc(ATALLOCSZ*8*sizeof(AMBTREE));
553 greg 2.26 if (atfreelist == NULL)
554     return(NULL);
555     /* link new free list */
556     upperlim = atfreelist + 8*(ATALLOCSZ-1);
557     for (atp = atfreelist; atp < upperlim; atp += 8)
558     atp->kid = atp + 8;
559     atp->kid = NULL;
560     }
561     atp = atfreelist;
562     atfreelist = atp->kid;
563     bzero((char *)atp, 8*sizeof(AMBTREE));
564     return(atp);
565     }
566    
567    
568 greg 2.47 static void
569 greg 2.26 freeambtree(atp) /* free 8 ambient tree structs */
570     AMBTREE *atp;
571     {
572     atp->kid = atfreelist;
573     atfreelist = atp;
574     }
575    
576    
577 greg 2.47 static void
578 greg 2.21 avinsert(av) /* insert ambient value in our tree */
579 greg 2.20 register AMBVAL *av;
580 greg 1.1 {
581 greg 2.21 register AMBTREE *at;
582 greg 2.23 register AMBVAL *ap;
583     AMBVAL avh;
584 greg 1.1 FVECT ck0;
585 greg 2.21 double s;
586 greg 1.1 int branch;
587     register int i;
588    
589 greg 2.20 if (av->rad <= FTINY)
590     error(CONSISTENCY, "zero ambient radius in avinsert");
591 greg 2.21 at = &atrunk;
592     VCOPY(ck0, thescene.cuorg);
593     s = thescene.cusize;
594 greg 1.1 while (s*(OCTSCALE/2) > av->rad*ambacc) {
595     if (at->kid == NULL)
596     if ((at->kid = newambtree()) == NULL)
597 greg 2.20 error(SYSTEM, "out of memory in avinsert");
598 greg 1.1 s *= 0.5;
599     branch = 0;
600     for (i = 0; i < 3; i++)
601     if (av->pos[i] > ck0[i] + s) {
602     ck0[i] += s;
603     branch |= 1 << i;
604     }
605     at = at->kid + branch;
606     }
607 greg 2.23 avh.next = at->alist; /* order by increasing level */
608     for (ap = &avh; ap->next != NULL; ap = ap->next)
609     if (ap->next->lvl >= av->lvl)
610     break;
611     av->next = ap->next;
612     ap->next = av;
613     at->alist = avh.next;
614 greg 2.7 }
615    
616    
617 greg 2.47 static void
618 greg 2.26 unloadatree(at, f) /* unload an ambient value tree */
619 greg 2.20 register AMBTREE *at;
620 greg 2.47 void (*f)();
621 greg 2.20 {
622     register AMBVAL *av;
623     register int i;
624     /* transfer values at this node */
625     for (av = at->alist; av != NULL; av = at->alist) {
626     at->alist = av->next;
627 greg 2.26 (*f)(av);
628 greg 2.20 }
629 greg 2.21 if (at->kid == NULL)
630     return;
631 greg 2.20 for (i = 0; i < 8; i++) /* transfer and free children */
632 greg 2.26 unloadatree(at->kid+i, f);
633 greg 2.20 freeambtree(at->kid);
634 greg 2.26 at->kid = NULL;
635     }
636    
637    
638 greg 2.39 static struct avl {
639     AMBVAL *p;
640     unsigned long t;
641     } *avlist1; /* ambient value list with ticks */
642     static AMBVAL **avlist2; /* memory positions for sorting */
643 greg 2.26 static int i_avlist; /* index for lists */
644    
645    
646 greg 2.47 static int
647 greg 2.26 av2list(av)
648 greg 2.39 register AMBVAL *av;
649 greg 2.26 {
650 greg 2.27 #ifdef DEBUG
651 greg 2.26 if (i_avlist >= nambvals)
652     error(CONSISTENCY, "too many ambient values in av2list1");
653 greg 2.27 #endif
654 greg 2.39 avlist1[i_avlist].p = avlist2[i_avlist] = av;
655     avlist1[i_avlist++].t = av->latick;
656 greg 2.26 }
657    
658    
659     static int
660 greg 2.39 alatcmp(av1, av2) /* compare ambient values for MRA */
661     struct avl *av1, *av2;
662 greg 2.26 {
663 greg 2.39 register long lc = av2->t - av1->t;
664 greg 2.38 return(lc<0 ? -1 : lc>0 ? 1 : 0);
665 greg 2.26 }
666    
667    
668 greg 2.47 /* GW NOTE 2002/10/3:
669     * I used to compare AMBVAL pointers, but found that this was the
670     * cause of a serious consistency error with gcc, since the optimizer
671     * uses some dangerous trick in pointer subtraction that
672     * assumes pointers differ by exact struct size increments.
673     */
674 greg 2.26 static int
675     aposcmp(avp1, avp2) /* compare ambient value positions */
676 greg 2.47 const void *avp1, *avp2;
677 greg 2.26 {
678 greg 2.47 register long diff = *(char * const *)avp1 - *(char * const *)avp2;
679     if (diff < 0)
680     return(-1);
681     return(diff > 0);
682 greg 2.26 }
683    
684 greg 2.39 #if 1
685 greg 2.27 static int
686     avlmemi(avaddr) /* find list position from address */
687     AMBVAL *avaddr;
688     {
689     register AMBVAL **avlpp;
690    
691     avlpp = (AMBVAL **)bsearch((char *)&avaddr, (char *)avlist2,
692     nambvals, sizeof(AMBVAL *), aposcmp);
693     if (avlpp == NULL)
694     error(CONSISTENCY, "address not found in avlmemi");
695     return(avlpp - avlist2);
696     }
697     #else
698     #define avlmemi(avaddr) ((AMBVAL **)bsearch((char *)&avaddr,(char *)avlist2, \
699     nambvals,sizeof(AMBVAL *),aposcmp) - avlist2)
700     #endif
701    
702    
703 greg 2.47 static void
704 greg 2.26 sortambvals(always) /* resort ambient values */
705     int always;
706     {
707     AMBTREE oldatrunk;
708     AMBVAL tav, *tap, *pnext;
709     register int i, j;
710 greg 2.28 /* see if it's time yet */
711 greg 2.40 if (!always && (ambclock++ < lastsort+sortintvl ||
712 greg 2.28 nambvals < SORT_THRESH))
713     return;
714 greg 2.26 /*
715     * The idea here is to minimize memory thrashing
716     * in VM systems by improving reference locality.
717     * We do this by periodically sorting our stored ambient
718     * values in memory in order of most recently to least
719     * recently accessed. This ordering was chosen so that new
720     * ambient values (which tend to be less important) go into
721     * higher memory with the infrequently accessed values.
722     * Since we expect our values to need sorting less
723     * frequently as the process continues, we double our
724     * waiting interval after each call.
725     * This routine is also called by setambacc() with
726     * the "always" parameter set to 1 so that the ambient
727     * tree will be rebuilt with the new accuracy parameter.
728     */
729 greg 2.27 if (tracktime) { /* allocate pointer arrays to sort */
730 greg 2.26 avlist2 = (AMBVAL **)malloc(nambvals*sizeof(AMBVAL *));
731 greg 2.39 avlist1 = (struct avl *)malloc(nambvals*sizeof(struct avl));
732     } else {
733     avlist2 = NULL;
734     avlist1 = NULL;
735     }
736     if (avlist1 == NULL) { /* no time tracking -- rebuild tree? */
737     if (avlist2 != NULL)
738 greg 2.47 free((void *)avlist2);
739 greg 2.27 if (always) { /* rebuild without sorting */
740     copystruct(&oldatrunk, &atrunk);
741     atrunk.alist = NULL;
742     atrunk.kid = NULL;
743     unloadatree(&oldatrunk, avinsert);
744     }
745 greg 2.26 } else { /* sort memory by last access time */
746     /*
747     * Sorting memory is tricky because it isn't contiguous.
748     * We have to sort an array of pointers by MRA and also
749     * by memory position. We then copy values in "loops"
750     * to minimize memory hits. Nevertheless, we will visit
751 greg 2.27 * everyone at least twice, and this is an expensive process
752 greg 2.26 * when we're thrashing, which is when we need to do it.
753     */
754 greg 2.27 #ifdef DEBUG
755 greg 2.29 sprintf(errmsg, "sorting %u ambient values at ambclock=%lu...",
756     nambvals, ambclock);
757 greg 2.27 eputs(errmsg);
758     #endif
759     i_avlist = 0;
760     unloadatree(&atrunk, av2list); /* empty current tree */
761     #ifdef DEBUG
762     if (i_avlist < nambvals)
763     error(CONSISTENCY, "missing ambient values in sortambvals");
764     #endif
765 greg 2.39 qsort((char *)avlist1, nambvals, sizeof(struct avl), alatcmp);
766 greg 2.26 qsort((char *)avlist2, nambvals, sizeof(AMBVAL *), aposcmp);
767     for (i = 0; i < nambvals; i++) {
768 greg 2.39 if (avlist1[i].p == NULL)
769 greg 2.26 continue;
770     tap = avlist2[i];
771     copystruct(&tav, tap);
772 greg 2.39 for (j = i; (pnext = avlist1[j].p) != tap;
773 greg 2.27 j = avlmemi(pnext)) {
774 greg 2.26 copystruct(avlist2[j], pnext);
775     avinsert(avlist2[j]);
776 greg 2.39 avlist1[j].p = NULL;
777 greg 2.26 }
778     copystruct(avlist2[j], &tav);
779     avinsert(avlist2[j]);
780 greg 2.39 avlist1[j].p = NULL;
781 greg 2.26 }
782 greg 2.47 free((void *)avlist1);
783     free((void *)avlist2);
784 greg 2.28 /* compute new sort interval */
785     sortintvl = ambclock - lastsort;
786 greg 2.32 if (sortintvl >= MAX_SORT_INTVL/2)
787 greg 2.28 sortintvl = MAX_SORT_INTVL;
788     else
789 greg 2.26 sortintvl <<= 1; /* wait twice as long next */
790 greg 2.27 #ifdef DEBUG
791     eputs("done\n");
792     #endif
793 greg 2.26 }
794     if (ambclock >= MAXACLOCK)
795     ambclock = MAXACLOCK/2;
796     lastsort = ambclock;
797 greg 2.20 }
798    
799    
800 greg 2.18 #ifdef F_SETLKW
801 greg 2.10
802 greg 2.47 static void
803 greg 2.19 aflock(typ) /* lock/unlock ambient file */
804     int typ;
805     {
806     static struct flock fls; /* static so initialized to zeroes */
807    
808     fls.l_type = typ;
809     if (fcntl(fileno(ambfp), F_SETLKW, &fls) < 0)
810     error(SYSTEM, "cannot (un)lock ambient file");
811     }
812    
813    
814 greg 2.16 int
815 greg 2.7 ambsync() /* synchronize ambient file */
816     {
817 greg 2.15 long flen;
818 greg 2.12 AMBVAL avs;
819 greg 2.7 register int n;
820 greg 2.16
821     if (nunflshed == 0)
822     return(0);
823 greg 2.19 if (lastpos < 0) /* initializing (locked in initambfile) */
824     goto syncend;
825 greg 2.7 /* gain exclusive access */
826 greg 2.19 aflock(F_WRLCK);
827 greg 2.7 /* see if file has grown */
828 greg 2.47 if ((flen = lseek(fileno(ambfp), (off_t)0L, 2)) < 0)
829 greg 2.21 goto seekerr;
830 greg 2.15 if (n = flen - lastpos) { /* file has grown */
831 greg 2.17 if (ambinp == NULL) { /* use duplicate filedes */
832     ambinp = fdopen(dup(fileno(ambfp)), "r");
833 greg 2.14 if (ambinp == NULL)
834 greg 2.17 error(SYSTEM, "fdopen failed in ambsync");
835 greg 2.14 }
836 greg 2.15 if (fseek(ambinp, lastpos, 0) < 0)
837 greg 2.21 goto seekerr;
838 greg 2.15 while (n >= AMBVALSIZ) { /* load contributed values */
839 greg 2.37 if (!readambval(&avs, ambinp)) {
840     sprintf(errmsg,
841 greg 2.47 "ambient file \"%s\" corrupted near character %ld",
842     ambfile, flen - n);
843 greg 2.37 error(WARNING, errmsg);
844     break;
845     }
846 greg 2.21 avinsert(avstore(&avs));
847 greg 2.15 n -= AMBVALSIZ;
848     }
849 greg 2.22 /*** seek always as safety measure
850     if (n) ***/ /* alignment */
851 greg 2.47 if (lseek(fileno(ambfp), (off_t)(flen-n), 0) < 0)
852 greg 2.21 goto seekerr;
853 greg 2.7 }
854 greg 2.21 #ifdef DEBUG
855     if (ambfp->_ptr - ambfp->_base != nunflshed*AMBVALSIZ) {
856     sprintf(errmsg, "ambient file buffer at %d rather than %d",
857     ambfp->_ptr - ambfp->_base,
858     nunflshed*AMBVALSIZ);
859     error(CONSISTENCY, errmsg);
860     }
861     #endif
862 greg 2.15 syncend:
863 greg 2.7 n = fflush(ambfp); /* calls write() at last */
864 greg 2.47 if ((lastpos = lseek(fileno(ambfp), (off_t)0L, 1)) < 0)
865 greg 2.21 goto seekerr;
866 greg 2.19 aflock(F_UNLCK); /* release file */
867 greg 2.16 nunflshed = 0;
868 greg 2.7 return(n);
869 greg 2.21 seekerr:
870     error(SYSTEM, "seek failed in ambsync");
871 greg 2.18 }
872    
873     #else
874    
875     int
876     ambsync() /* flush ambient file */
877     {
878     if (nunflshed == 0)
879     return(0);
880     nunflshed = 0;
881     return(fflush(ambfp));
882 greg 1.1 }
883 greg 2.10
884     #endif