1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 /*
5 * jvn 0.99 by Radical Eye Software.
6 *
7 * All good ideas here were originated by Gosper or Bell or others, I'm
8 * sure, and all bad ones by yours truly.
9 *
10 * The main reason I wrote this program was to attempt to push out the
11 * evaluation of metacatacryst as far as I could. So this program
12 * really does very little other than compute life as far into the
13 * future as possible, using as little memory as possible (and reusing
14 * it if necessary). No UI, few options.
15 */
16 #include "ghashbase.h"
17 #include "util.h"
18 #include <stdlib.h>
19 #include <string.h>
20 using namespace std ;
21 /*
22 * Power of two hash sizes work fine.
23 */
24 #ifdef PRIMEMOD
25 #define HASHMOD(a) ((a)%hashprime)
nexthashsize(g_uintptr_t i)26 static g_uintptr_t nexthashsize(g_uintptr_t i) {
27 g_uintptr_t j ;
28 i |= 1 ;
29 for (;; i+=2) {
30 for (j=3; j*j<=i; j+=2)
31 if (i % j == 0)
32 break ;
33 if (j*j > i)
34 return i ;
35 }
36 }
37 #else
38 #define HASHMOD(a) ((a)&(hashmask))
nexthashsize(g_uintptr_t i)39 static g_uintptr_t nexthashsize(g_uintptr_t i) {
40 while ((i & (i - 1)))
41 i += (i & (1 + ~i)) ; // i & - i is more idiomatic but generates warning
42 return i ;
43 }
44 #endif
45 /*
46 * We do now support garbage collection, but there are some routines we
47 * call frequently to help us.
48 */
49 #ifdef PRIMEMOD
50 #define ghnode_hash(a,b,c,d) (65537*(g_uintptr_t)(d)+257*(g_uintptr_t)(c)+17*(g_uintptr_t)(b)+5*(g_uintptr_t)(a))
51 #else
ghnode_hash(void * a,void * b,void * c,void * d)52 g_uintptr_t ghnode_hash(void *a, void *b, void *c, void *d) {
53 g_uintptr_t r = (65537*(g_uintptr_t)(d)+257*(g_uintptr_t)(c)+17*(g_uintptr_t)(b)+5*(g_uintptr_t)(a)) ;
54 r += (r >> 11) ;
55 return r ;
56 }
57 #endif
58 #define ghleaf_hash(a,b,c,d) (65537*(d)+257*(c)+17*(b)+5*(a))
59 /*
60 * Resize the hash. The max load factor defined here does not actually
61 * yield the maximum load factor the hash will see, because when we
62 * do the last resize before exhausting memory, we may find we are
63 * not permitted (while keeping total memory consumption below the
64 * limit) to do the resize, so the actual max load factor may be
65 * somewhat higher. Conversely, because we double the hash size
66 * each time, the actual final max load factor may be less than this.
67 * Additional code can be added to manage this, but after some
68 * experimentation, it has been found that the impact is tiny, so
69 * we are keeping the code simple. Nonetheless, this factor can be
70 * tweaked in the case where you absolutely want as many nodes as
71 * possible in memory, and are willing to use a large load factor to
72 * permit this; with the move-to-front heuristic, the code actually
73 * handles a large load factor fairly well.
74 */
75 double ghashbase::maxloadfactor = 0.7 ;
resize()76 void ghashbase::resize() {
77 #ifndef NOGCBEFORERESIZE
78 if (okaytogc) {
79 do_gc(0) ;
80 }
81 #endif
82 g_uintptr_t i, nhashprime = nexthashsize(2 * hashprime) ;
83 ghnode *p, **nhashtab ;
84 if (hashprime > (totalthings >> 2)) {
85 if (alloced > maxmem ||
86 nhashprime * sizeof(ghnode *) > (maxmem - alloced)) {
87 hashlimit = G_MAX ;
88 return ;
89 }
90 }
91 if (verbose) {
92 sprintf(statusline, "Resizing hash to %" PRIuPTR "...", nhashprime) ;
93 lifestatus(statusline) ;
94 }
95 nhashtab = (ghnode **)calloc(nhashprime, sizeof(ghnode *)) ;
96 if (nhashtab == 0) {
97 lifewarning("Out of memory; running in a somewhat slower mode; "
98 "try reducing the hash memory limit after restarting.") ;
99 hashlimit = G_MAX ;
100 return ;
101 }
102 alloced += sizeof(ghnode *) * (nhashprime - hashprime) ;
103 g_uintptr_t ohashprime = hashprime ;
104 hashprime = nhashprime ;
105 #ifndef PRIMEMOD
106 hashmask = hashprime - 1 ;
107 #endif
108 for (i=0; i<ohashprime; i++) {
109 for (p=hashtab[i]; p;) {
110 ghnode *np = p->next ;
111 g_uintptr_t h ;
112 if (is_ghnode(p)) {
113 h = ghnode_hash(p->nw, p->ne, p->sw, p->se) ;
114 } else {
115 ghleaf *l = (ghleaf *)p ;
116 h = ghleaf_hash(l->nw, l->ne, l->sw, l->se) ;
117 }
118 h = HASHMOD(h) ;
119 p->next = nhashtab[h] ;
120 nhashtab[h] = p ;
121 p = np ;
122 }
123 }
124 free(hashtab) ;
125 hashtab = nhashtab ;
126 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
127 if (verbose) {
128 strcpy(statusline+strlen(statusline), " done.") ;
129 lifestatus(statusline) ;
130 }
131 }
132 /*
133 * These next two routines are (nearly) our only hash table access
134 * routines; we simply look up the passed in information. If we
135 * find it in the hash table, we return it; otherwise, we build a
136 * new ghnode and store it in the hash table, and return that.
137 */
find_ghnode(ghnode * nw,ghnode * ne,ghnode * sw,ghnode * se)138 ghnode *ghashbase::find_ghnode(ghnode *nw, ghnode *ne, ghnode *sw, ghnode *se) {
139 ghnode *p ;
140 g_uintptr_t h = ghnode_hash(nw,ne,sw,se) ;
141 ghnode *pred = 0 ;
142 h = HASHMOD(h) ;
143 for (p=hashtab[h]; p; p = p->next) { /* make sure to compare nw *first* */
144 if (nw == p->nw && ne == p->ne && sw == p->sw && se == p->se) {
145 if (pred) { /* move this one to the front */
146 pred->next = p->next ;
147 p->next = hashtab[h] ;
148 hashtab[h] = p ;
149 }
150 return save(p) ;
151 }
152 pred = p ;
153 }
154 p = newghnode() ;
155 p->nw = nw ;
156 p->ne = ne ;
157 p->sw = sw ;
158 p->se = se ;
159 p->res = 0 ;
160 p->next = hashtab[h] ;
161 hashtab[h] = p ;
162 hashpop++ ;
163 save(p) ;
164 if (hashpop > hashlimit)
165 resize() ;
166 return p ;
167 }
find_ghleaf(state nw,state ne,state sw,state se)168 ghleaf *ghashbase::find_ghleaf(state nw, state ne, state sw, state se) {
169 ghleaf *p ;
170 ghleaf *pred = 0 ;
171 g_uintptr_t h = ghleaf_hash(nw, ne, sw, se) ;
172 h = HASHMOD(h) ;
173 for (p=(ghleaf *)hashtab[h]; p; p = (ghleaf *)p->next) {
174 if (nw == p->nw && ne == p->ne && sw == p->sw && se == p->se &&
175 !is_ghnode(p)) {
176 if (pred) {
177 pred->next = p->next ;
178 p->next = hashtab[h] ;
179 hashtab[h] = (ghnode *)p ;
180 }
181 return (ghleaf *)save((ghnode *)p) ;
182 }
183 pred = p ;
184 }
185 p = newghleaf() ;
186 p->nw = nw ;
187 p->ne = ne ;
188 p->sw = sw ;
189 p->se = se ;
190 p->leafpop = bigint((short)((nw != 0) + (ne != 0) + (sw != 0) + (se != 0))) ;
191 p->isghnode = 0 ;
192 p->next = hashtab[h] ;
193 hashtab[h] = (ghnode *)p ;
194 hashpop++ ;
195 save((ghnode *)p) ;
196 if (hashpop > hashlimit)
197 resize() ;
198 return p ;
199 }
200 /*
201 * The following routine does the same, but first it checks to see if
202 * the cached result is any good. If it is, it directly returns that.
203 * Otherwise, it figures out whether to call the ghleaf routine or the
204 * non-ghleaf routine by whether two ghnodes down is a ghleaf ghnode or not.
205 * (We'll understand why this is a bit later.) All the sp stuff is
206 * stack pointer and garbage collection stuff.
207 */
getres(ghnode * n,int depth)208 ghnode *ghashbase::getres(ghnode *n, int depth) {
209 if (n->res)
210 return n->res ;
211 ghnode *res = 0 ;
212 /**
213 * This routine be the only place we assign to res. We use
214 * the fact that the poll routine is *sticky* to allow us to
215 * manage unwinding the stack without munging our data
216 * structures. Note that there may be many find_ghnodes
217 * and getres called before we finally actually exit from
218 * here, because the stack is deep and we don't want to
219 * put checks throughout the code. Instead we need two
220 * calls here, one to prevent us going deeper, and another
221 * to prevent us from destroying the cache field.
222 */
223 if (poller->poll() || softinterrupt) return zeroghnode(depth-1) ;
224 int sp = gsp ;
225 if (running_hperf.fastinc(depth, ngens < depth))
226 running_hperf.report(inc_hperf, verbose) ;
227 depth-- ;
228 if (ngens >= depth) {
229 if (is_ghnode(n->nw)) {
230 res = dorecurs(n->nw, n->ne, n->sw, n->se, depth) ;
231 } else {
232 res = (ghnode *)dorecurs_ghleaf((ghleaf *)n->nw, (ghleaf *)n->ne,
233 (ghleaf *)n->sw, (ghleaf *)n->se) ;
234 }
235 } else {
236 if (is_ghnode(n->nw)) {
237 res = dorecurs_half(n->nw, n->ne, n->sw, n->se, depth) ;
238 } else {
239 lifefatal("! can't happen") ;
240 }
241 }
242 pop(sp) ;
243 if (softinterrupt || poller->isInterrupted()) // don't assign this to the cache field!
244 res = zeroghnode(depth) ;
245 else {
246 if (ngens < depth && halvesdone < 1000)
247 halvesdone++ ;
248 n->res = res ;
249 }
250 return res ;
251 }
252 #ifdef USEPREFETCH
setupprefetch(ghsetup_t & su,ghnode * nw,ghnode * ne,ghnode * sw,ghnode * se)253 void ghashbase::setupprefetch(ghsetup_t &su, ghnode *nw, ghnode *ne, ghnode *sw, ghnode *se) {
254 su.h = ghnode_hash(nw,ne,sw,se) ;
255 su.nw = nw ;
256 su.ne = ne ;
257 su.sw = sw ;
258 su.se = se ;
259 su.prefetch(hashtab + HASHMOD(su.h)) ;
260 }
find_ghnode(ghsetup_t & su)261 ghnode *ghashbase::find_ghnode(ghsetup_t &su) {
262 ghnode *p ;
263 ghnode *pred = 0 ;
264 g_uintptr_t h = HASHMOD(su.h) ;
265 for (p=hashtab[h]; p; p = p->next) { /* make sure to compare nw *first* */
266 if (su.nw == p->nw && su.ne == p->ne && su.sw == p->sw && su.se == p->se) {
267 if (pred) { /* move this one to the front */
268 pred->next = p->next ;
269 p->next = hashtab[h] ;
270 hashtab[h] = p ;
271 }
272 return save(p) ;
273 }
274 pred = p ;
275 }
276 p = newghnode() ;
277 p->nw = su.nw ;
278 p->ne = su.ne ;
279 p->sw = su.sw ;
280 p->se = su.se ;
281 p->res = 0 ;
282 p->next = hashtab[h] ;
283 hashtab[h] = p ;
284 hashpop++ ;
285 save(p) ;
286 if (hashpop > hashlimit)
287 resize() ;
288 return p ;
289 }
dorecurs(ghnode * n,ghnode * ne,ghnode * t,ghnode * e,int depth)290 ghnode *ghashbase::dorecurs(ghnode *n, ghnode *ne, ghnode *t, ghnode *e, int depth) {
291 int sp = gsp ;
292 ghsetup_t su[5] ;
293 setupprefetch(su[2], n->se, ne->sw, t->ne, e->nw) ;
294 setupprefetch(su[0], n->ne, ne->nw, n->se, ne->sw) ;
295 setupprefetch(su[1], ne->sw, ne->se, e->nw, e->ne) ;
296 setupprefetch(su[3], n->sw, n->se, t->nw, t->ne) ;
297 setupprefetch(su[4], t->ne, e->nw, t->se, e->sw) ;
298 ghnode
299 *t00 = getres(n, depth),
300 *t01 = getres(find_ghnode(su[0]), depth),
301 *t02 = getres(ne, depth),
302 *t12 = getres(find_ghnode(su[1]), depth),
303 *t11 = getres(find_ghnode(su[2]), depth),
304 *t10 = getres(find_ghnode(su[3]), depth),
305 *t20 = getres(t, depth),
306 *t21 = getres(find_ghnode(su[4]), depth),
307 *t22 = getres(e, depth) ;
308 setupprefetch(su[0], t11, t12, t21, t22) ;
309 setupprefetch(su[1], t10, t11, t20, t21) ;
310 setupprefetch(su[2], t00, t01, t10, t11) ;
311 setupprefetch(su[3], t01, t02, t11, t12) ;
312 ghnode
313 *t44 = getres(find_ghnode(su[0]), depth),
314 *t43 = getres(find_ghnode(su[1]), depth),
315 *t33 = getres(find_ghnode(su[2]), depth),
316 *t34 = getres(find_ghnode(su[3]), depth) ;
317 n = find_ghnode(t33, t34, t43, t44) ;
318 pop(sp) ;
319 return save(n) ;
320 }
321 #else
322 /*
323 * So let's say the cached way failed. How do we do it the slow way?
324 * Recursively, of course. For an n-square (composed of the four
325 * n/2-squares passed in, compute the n/2-square that is n/4
326 * generations ahead.
327 *
328 * This routine works exactly the same as the ghleafres() routine, only
329 * instead of working on an 8-square, we're working on an n-square,
330 * returning an n/2-square, and we build that n/2-square by first building
331 * 9 n/4-squares, use those to calculate 4 more n/4-squares, and
332 * then put these together into a new n/2-square. Simple, eh?
333 */
dorecurs(ghnode * n,ghnode * ne,ghnode * t,ghnode * e,int depth)334 ghnode *ghashbase::dorecurs(ghnode *n, ghnode *ne, ghnode *t,
335 ghnode *e, int depth) {
336 int sp = gsp ;
337 ghnode
338 *t11 = getres(find_ghnode(n->se, ne->sw, t->ne, e->nw), depth),
339 *t00 = getres(n, depth),
340 *t01 = getres(find_ghnode(n->ne, ne->nw, n->se, ne->sw), depth),
341 *t02 = getres(ne, depth),
342 *t12 = getres(find_ghnode(ne->sw, ne->se, e->nw, e->ne), depth),
343 *t10 = getres(find_ghnode(n->sw, n->se, t->nw, t->ne), depth),
344 *t20 = getres(t, depth),
345 *t21 = getres(find_ghnode(t->ne, e->nw, t->se, e->sw), depth),
346 *t22 = getres(e, depth),
347 *t44 = getres(find_ghnode(t11, t12, t21, t22), depth),
348 *t43 = getres(find_ghnode(t10, t11, t20, t21), depth),
349 *t33 = getres(find_ghnode(t00, t01, t10, t11), depth),
350 *t34 = getres(find_ghnode(t01, t02, t11, t12), depth) ;
351 n = find_ghnode(t33, t34, t43, t44) ;
352 pop(sp) ;
353 return save(n) ;
354 }
355 #endif
356 /*
357 * Same as above, but we only do one step instead of 2.
358 */
dorecurs_half(ghnode * n,ghnode * ne,ghnode * t,ghnode * e,int depth)359 ghnode *ghashbase::dorecurs_half(ghnode *n, ghnode *ne, ghnode *t,
360 ghnode *e, int depth) {
361 int sp = gsp ;
362 if (depth > 1) {
363 ghnode
364 *t00 = find_ghnode(n->nw->se, n->ne->sw, n->sw->ne, n->se->nw),
365 *t01 = find_ghnode(n->ne->se, ne->nw->sw, n->se->ne, ne->sw->nw),
366 *t02 = find_ghnode(ne->nw->se, ne->ne->sw, ne->sw->ne, ne->se->nw),
367 *t10 = find_ghnode(n->sw->se, n->se->sw, t->nw->ne, t->ne->nw),
368 *t11 = find_ghnode(n->se->se, ne->sw->sw, t->ne->ne, e->nw->nw),
369 *t12 = find_ghnode(ne->sw->se, ne->se->sw, e->nw->ne, e->ne->nw),
370 *t20 = find_ghnode(t->nw->se, t->ne->sw, t->sw->ne, t->se->nw),
371 *t21 = find_ghnode(t->ne->se, e->nw->sw, t->se->ne, e->sw->nw),
372 *t22 = find_ghnode(e->nw->se, e->ne->sw, e->sw->ne, e->se->nw) ;
373 n = find_ghnode(getres(find_ghnode(t00, t01, t10, t11), depth),
374 getres(find_ghnode(t01, t02, t11, t12), depth),
375 getres(find_ghnode(t10, t11, t20, t21), depth),
376 getres(find_ghnode(t11, t12, t21, t22), depth)) ;
377 } else {
378 ghnode
379 *t00 = getres(n, depth),
380 *t01 = getres(find_ghnode(n->ne, ne->nw, n->se, ne->sw), depth),
381 *t10 = getres(find_ghnode(n->sw, n->se, t->nw, t->ne), depth),
382 *t11 = getres(find_ghnode(n->se, ne->sw, t->ne, e->nw), depth),
383 *t02 = getres(ne, depth),
384 *t12 = getres(find_ghnode(ne->sw, ne->se, e->nw, e->ne), depth),
385 *t20 = getres(t, depth),
386 *t21 = getres(find_ghnode(t->ne, e->nw, t->se, e->sw), depth),
387 *t22 = getres(e, depth) ;
388 n = find_ghnode((ghnode *)find_ghleaf(((ghleaf *)t00)->se,
389 ((ghleaf *)t01)->sw,
390 ((ghleaf *)t10)->ne,
391 ((ghleaf *)t11)->nw),
392 (ghnode *)find_ghleaf(((ghleaf *)t01)->se,
393 ((ghleaf *)t02)->sw,
394 ((ghleaf *)t11)->ne,
395 ((ghleaf *)t12)->nw),
396 (ghnode *)find_ghleaf(((ghleaf *)t10)->se,
397 ((ghleaf *)t11)->sw,
398 ((ghleaf *)t20)->ne,
399 ((ghleaf *)t21)->nw),
400 (ghnode *)find_ghleaf(((ghleaf *)t11)->se,
401 ((ghleaf *)t12)->sw,
402 ((ghleaf *)t21)->ne,
403 ((ghleaf *)t22)->nw)) ;
404 }
405 pop(sp) ;
406 return save(n) ;
407 }
408 /*
409 * If the ghnode is a 16-ghnode, then the constituents are leaves, so we
410 * need a very similar but still somewhat different subroutine. Since
411 * we do not (yet) garbage collect leaves, we don't need all that
412 * save/pop mumbo-jumbo.
413 */
dorecurs_ghleaf(ghleaf * nw,ghleaf * ne,ghleaf * sw,ghleaf * se)414 ghleaf *ghashbase::dorecurs_ghleaf(ghleaf *nw, ghleaf *ne, ghleaf *sw,
415 ghleaf *se) {
416 return find_ghleaf(
417 slowcalc(nw->nw, nw->ne, ne->nw,
418 nw->sw, nw->se, ne->sw,
419 sw->nw, sw->ne, se->nw),
420 slowcalc(nw->ne, ne->nw, ne->ne,
421 nw->se, ne->sw, ne->se,
422 sw->ne, se->nw, se->ne),
423 slowcalc(nw->sw, nw->se, ne->sw,
424 sw->nw, sw->ne, se->nw,
425 sw->sw, sw->se, se->sw),
426 slowcalc(nw->se, ne->sw, ne->se,
427 sw->ne, se->nw, se->ne,
428 sw->se, se->sw, se->se)) ;
429 }
430 /*
431 * We keep free ghnodes in a linked list for allocation, and we allocate
432 * them 1000 at a time.
433 */
newghnode()434 ghnode *ghashbase::newghnode() {
435 ghnode *r ;
436 if (freeghnodes == 0) {
437 int i ;
438 freeghnodes = (ghnode *)calloc(1001, sizeof(ghnode)) ;
439 if (freeghnodes == 0)
440 lifefatal("Out of memory; try reducing the hash memory limit.") ;
441 alloced += 1001 * sizeof(ghnode) ;
442 freeghnodes->next = ghnodeblocks ;
443 ghnodeblocks = freeghnodes++ ;
444 for (i=0; i<999; i++) {
445 freeghnodes[1].next = freeghnodes ;
446 freeghnodes++ ;
447 }
448 totalthings += 1000 ;
449 }
450 if (freeghnodes->next == 0 && alloced + 1000 * sizeof(ghnode) > maxmem &&
451 okaytogc) {
452 do_gc(0) ;
453 }
454 r = freeghnodes ;
455 freeghnodes = freeghnodes->next ;
456 return r ;
457 }
458 /*
459 * Leaves are the same.
460 */
newghleaf()461 ghleaf *ghashbase::newghleaf() {
462 ghleaf *r = (ghleaf *)newghnode() ;
463 new(&(r->leafpop))bigint ;
464 return r ;
465 }
466 /*
467 * Sometimes we want the new ghnode or ghleaf to be automatically cleared
468 * for us.
469 */
newclearedghnode()470 ghnode *ghashbase::newclearedghnode() {
471 return (ghnode *)memset(newghnode(), 0, sizeof(ghnode)) ;
472 }
newclearedghleaf()473 ghleaf *ghashbase::newclearedghleaf() {
474 ghleaf *r = (ghleaf *)newclearedghnode() ;
475 new(&(r->leafpop))bigint ;
476 return r ;
477 }
ghashbase()478 ghashbase::ghashbase() {
479 hashprime = nexthashsize(1000) ;
480 #ifndef PRIMEMOD
481 hashmask = hashprime - 1 ;
482 #endif
483 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
484 hashpop = 0 ;
485 hashtab = (ghnode **)calloc(hashprime, sizeof(ghnode *)) ;
486 if (hashtab == 0)
487 lifefatal("Out of memory (1).") ;
488 alloced = hashprime * sizeof(ghnode *) ;
489 ngens = 0 ;
490 stacksize = 0 ;
491 halvesdone = 0 ;
492 nzeros = 0 ;
493 stack = 0 ;
494 gsp = 0 ;
495 maxmem = 256 * 1024 * 1024 ;
496 freeghnodes = 0 ;
497 okaytogc = 0 ;
498 totalthings = 0 ;
499 ghnodeblocks = 0 ;
500 zeroghnodea = 0 ;
501 /*
502 * We initialize our universe to be a 16-square. We are in drawing
503 * mode at this point.
504 */
505 root = (ghnode *)newclearedghnode() ;
506 population = 0 ;
507 generation = 0 ;
508 increment = 1 ;
509 setincrement = 1 ;
510 nonpow2 = 1 ;
511 pow2step = 1 ;
512 llsize = 0 ;
513 depth = 1 ;
514 hashed = 0 ;
515 popValid = 0 ;
516 needPop = 0 ;
517 inGC = 0 ;
518 cacheinvalid = 0 ;
519 gccount = 0 ;
520 gcstep = 0 ;
521 running_hperf.clear() ;
522 inc_hperf = running_hperf ;
523 step_hperf = running_hperf ;
524 softinterrupt = 0 ;
525 }
526 /**
527 * Destructor frees memory.
528 */
~ghashbase()529 ghashbase::~ghashbase() {
530 free(hashtab) ;
531 while (ghnodeblocks) {
532 ghnode *r = ghnodeblocks ;
533 ghnodeblocks = ghnodeblocks->next ;
534 free(r) ;
535 }
536 if (zeroghnodea)
537 free(zeroghnodea) ;
538 if (stack)
539 free(stack) ;
540 if (llsize) {
541 delete [] llxb ;
542 delete [] llyb ;
543 }
544 }
545 /**
546 * Set increment.
547 */
setIncrement(bigint inc)548 void ghashbase::setIncrement(bigint inc) {
549 if (inc < increment)
550 softinterrupt = 1 ;
551 increment = inc ;
552 }
553 /**
554 * Do a step.
555 */
step()556 void ghashbase::step() {
557 poller->bailIfCalculating() ;
558 // we use while here because the increment may be changed while we are
559 // doing the hashtable sweep; if that happens, we may need to sweep
560 // again.
561 while (1) {
562 int cleareddownto = 1000000000 ;
563 softinterrupt = 0 ;
564 while (increment != setincrement) {
565 bigint pendingincrement = increment ;
566 int newpow2 = 0 ;
567 bigint t = pendingincrement ;
568 while (t > 0 && t.even()) {
569 newpow2++ ;
570 t.div2() ;
571 }
572 nonpow2 = t.low31() ;
573 if (t != nonpow2)
574 lifefatal("bad increment") ;
575 int downto = newpow2 ;
576 if (ngens < newpow2)
577 downto = ngens ;
578 if (newpow2 != ngens && cleareddownto > downto) {
579 new_ngens(newpow2) ;
580 cleareddownto = downto ;
581 } else {
582 ngens = newpow2 ;
583 }
584 setincrement = pendingincrement ;
585 pow2step = 1 ;
586 while (newpow2--)
587 pow2step += pow2step ;
588 }
589 gcstep = 0 ;
590 running_hperf.genval = generation.todouble() ;
591 for (int i=0; i<nonpow2; i++) {
592 ghnode *newroot = runpattern() ;
593 if (newroot == 0 || softinterrupt || poller->isInterrupted()) // we *were* interrupted
594 break ;
595 popValid = 0 ;
596 root = newroot ;
597 depth = ghnode_depth(root) ;
598 }
599 running_hperf.reportStep(step_hperf, inc_hperf, generation.todouble(), verbose) ;
600 if (poller->isInterrupted() || !softinterrupt)
601 break ;
602 }
603 }
setcurrentstate(void * n)604 void ghashbase::setcurrentstate(void *n) {
605 if (root != (ghnode *)n) {
606 root = (ghnode *)n ;
607 depth = ghnode_depth(root) ;
608 popValid = 0 ;
609 }
610 }
611 /*
612 * Set the max memory
613 */
setMaxMemory(int newmemlimit)614 void ghashbase::setMaxMemory(int newmemlimit) {
615 if (newmemlimit < 10)
616 newmemlimit = 10 ;
617 #ifndef GOLLY64BIT
618 else if (newmemlimit > 4000)
619 newmemlimit = 4000 ;
620 #endif
621 g_uintptr_t newlimit = ((g_uintptr_t)newmemlimit) << 20 ;
622 if (alloced > newlimit) {
623 lifewarning("Sorry, more memory currently used than allowed.") ;
624 return ;
625 }
626 maxmem = newlimit ;
627 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
628 }
629 /**
630 * Clear everything.
631 */
clearall()632 void ghashbase::clearall() {
633 lifefatal("clearall not implemented yet") ;
634 }
635 /*
636 * This routine expands our universe by a factor of two, maintaining
637 * centering. We use four new ghnodes, and *reuse* the root so this cannot
638 * be called after we've started hashing.
639 */
pushroot_1()640 void ghashbase::pushroot_1() {
641 ghnode *t ;
642 t = newclearedghnode() ;
643 t->se = root->nw ;
644 root->nw = t ;
645 t = newclearedghnode() ;
646 t->sw = root->ne ;
647 root->ne = t ;
648 t = newclearedghnode() ;
649 t->ne = root->sw ;
650 root->sw = t ;
651 t = newclearedghnode() ;
652 t->nw = root->se ;
653 root->se = t ;
654 depth++ ;
655 }
656 /*
657 * Return the depth of this ghnode (2 is 8x8).
658 */
ghnode_depth(ghnode * n)659 int ghashbase::ghnode_depth(ghnode *n) {
660 int depth = 0 ;
661 while (is_ghnode(n)) {
662 depth++ ;
663 n = n->nw ;
664 }
665 return depth ;
666 }
667 /*
668 * This routine returns the canonical clear space ghnode at a particular
669 * depth.
670 */
zeroghnode(int depth)671 ghnode *ghashbase::zeroghnode(int depth) {
672 while (depth >= nzeros) {
673 int nnzeros = 2 * nzeros + 10 ;
674 zeroghnodea = (ghnode **)realloc(zeroghnodea,
675 nnzeros * sizeof(ghnode *)) ;
676 if (zeroghnodea == 0)
677 lifefatal("Out of memory (2).") ;
678 alloced += (nnzeros - nzeros) * sizeof(ghnode *) ;
679 while (nzeros < nnzeros)
680 zeroghnodea[nzeros++] = 0 ;
681 }
682 if (zeroghnodea[depth] == 0) {
683 if (depth == 0) {
684 zeroghnodea[depth] = (ghnode *)find_ghleaf(0, 0, 0, 0) ;
685 } else {
686 ghnode *z = zeroghnode(depth-1) ;
687 zeroghnodea[depth] = find_ghnode(z, z, z, z) ;
688 }
689 }
690 return zeroghnodea[depth] ;
691 }
692 /*
693 * Same, but with hashed ghnodes.
694 */
pushroot(ghnode * n)695 ghnode *ghashbase::pushroot(ghnode *n) {
696 int depth = ghnode_depth(n) ;
697 zeroghnode(depth+1) ; // ensure zeros are deep enough
698 ghnode *z = zeroghnode(depth-1) ;
699 return find_ghnode(find_ghnode(z, z, z, n->nw),
700 find_ghnode(z, z, n->ne, z),
701 find_ghnode(z, n->sw, z, z),
702 find_ghnode(n->se, z, z, z)) ;
703 }
704 /*
705 * Here is our recursive routine to set a bit in our universe. We
706 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
707 * but really not all that complicated. We allocate new ghnodes and
708 * leaves on our way down.
709 *
710 * Note that at this point our universe lives outside the hash table
711 * and has not been canonicalized, and that many of the pointers in
712 * the ghnodes can be null. We'll patch this up in due course.
713 */
gsetbit(ghnode * n,int x,int y,int newstate,int depth)714 ghnode *ghashbase::gsetbit(ghnode *n, int x, int y, int newstate, int depth) {
715 if (depth == 0) {
716 ghleaf *l = (ghleaf *)n ;
717 if (hashed) {
718 state nw = l->nw ;
719 state sw = l->sw ;
720 state ne = l->ne ;
721 state se = l->se ;
722 if (x < 0)
723 if (y < 0)
724 sw = (state)newstate ;
725 else
726 nw = (state)newstate ;
727 else
728 if (y < 0)
729 se = (state)newstate ;
730 else
731 ne = (state)newstate ;
732 return save((ghnode *)find_ghleaf(nw, ne, sw, se)) ;
733 }
734 if (x < 0)
735 if (y < 0)
736 l->sw = (state)newstate ;
737 else
738 l->nw = (state)newstate ;
739 else
740 if (y < 0)
741 l->se = (state)newstate ;
742 else
743 l->ne = (state)newstate ;
744 return (ghnode *)l ;
745 } else {
746 unsigned int w = 0, wh = 0 ;
747 if (depth > 31) {
748 if (depth == 32)
749 wh = 0x80000000 ;
750 w = 0 ;
751 } else {
752 w = 1 << depth ;
753 wh = 1 << (depth - 1) ;
754 }
755 depth-- ;
756 ghnode **nptr ;
757 if (depth+1 == this->depth || depth < 31) {
758 if (x < 0) {
759 if (y < 0)
760 nptr = &(n->sw) ;
761 else
762 nptr = &(n->nw) ;
763 } else {
764 if (y < 0)
765 nptr = &(n->se) ;
766 else
767 nptr = &(n->ne) ;
768 }
769 } else {
770 if (x >= 0) {
771 if (y >= 0)
772 nptr = &(n->sw) ;
773 else
774 nptr = &(n->nw) ;
775 } else {
776 if (y >= 0)
777 nptr = &(n->se) ;
778 else
779 nptr = &(n->ne) ;
780 }
781 }
782 if (*nptr == 0) {
783 if (depth == 0)
784 *nptr = (ghnode *)newclearedghleaf() ;
785 else
786 *nptr = newclearedghnode() ;
787 }
788 ghnode *s = gsetbit(*nptr, (x & (w - 1)) - wh,
789 (y & (w - 1)) - wh, newstate, depth) ;
790 if (hashed) {
791 ghnode *nw = (nptr == &(n->nw) ? s : n->nw) ;
792 ghnode *sw = (nptr == &(n->sw) ? s : n->sw) ;
793 ghnode *ne = (nptr == &(n->ne) ? s : n->ne) ;
794 ghnode *se = (nptr == &(n->se) ? s : n->se) ;
795 if (x < 0) {
796 if (y < 0)
797 sw = s ;
798 else
799 nw = s ;
800 } else {
801 if (y < 0)
802 se = s ;
803 else
804 ne = s ;
805 }
806 n = save(find_ghnode(nw, ne, sw, se)) ;
807 } else {
808 *nptr = s ;
809 }
810 return n ;
811 }
812 }
813 /*
814 * Here is our recursive routine to get a bit in our universe. We
815 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
816 * but really not all that complicated.
817 */
getbit(ghnode * n,int x,int y,int depth)818 int ghashbase::getbit(ghnode *n, int x, int y, int depth) {
819 struct ghnode tnode ;
820 while (depth >= 32) {
821 tnode.nw = n->nw->se ;
822 tnode.ne = n->ne->sw ;
823 tnode.sw = n->sw->ne ;
824 tnode.se = n->se->nw ;
825 n = &tnode ;
826 depth-- ;
827 }
828 if (depth == 0) {
829 ghleaf *l = (ghleaf *)n ;
830 if (x < 0)
831 if (y < 0)
832 return l->sw ;
833 else
834 return l->nw ;
835 else
836 if (y < 0)
837 return l->se ;
838 else
839 return l->ne ;
840 } else {
841 unsigned int w = 0, wh = 0 ;
842 if (depth >= 32) {
843 if (depth == 32)
844 wh = 0x80000000 ;
845 } else {
846 w = 1 << depth ;
847 wh = 1 << (depth - 1) ;
848 }
849 ghnode *nptr ;
850 depth-- ;
851 if (x < 0) {
852 if (y < 0)
853 nptr = n->sw ;
854 else
855 nptr = n->nw ;
856 } else {
857 if (y < 0)
858 nptr = n->se ;
859 else
860 nptr = n->ne ;
861 }
862 if (nptr == 0 || nptr == zeroghnode(depth))
863 return 0 ;
864 return getbit(nptr, (x & (w - 1)) - wh, (y & (w - 1)) - wh,
865 depth) ;
866 }
867 }
868 /*
869 * Here is our recursive routine to get the next bit in our universe. We
870 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
871 * but really not all that complicated.
872 */
nextbit(ghnode * n,int x,int y,int depth,int & v)873 int ghashbase::nextbit(ghnode *n, int x, int y, int depth, int &v) {
874 if (n == 0 || n == zeroghnode(depth))
875 return -1 ;
876 if (depth == 0) {
877 ghleaf *l = (ghleaf *)n ;
878 if (y < 0) {
879 if (x < 0 && l->sw) {
880 v = l->sw ;
881 return 0 ;
882 }
883 if (l->se) {
884 v = l->se ;
885 return -x ;
886 }
887 } else {
888 if (x < 0 && l->nw) {
889 v = l->nw ;
890 return 0 ;
891 }
892 if (l->ne) {
893 v = l->ne ;
894 return -x ;
895 }
896 }
897 return -1 ; // none found
898 } else {
899 unsigned int w = 1 << depth ;
900 unsigned int wh = w >> 1 ;
901 ghnode *lft, *rght ;
902 depth-- ;
903 if (y < 0) {
904 lft = n->sw ;
905 rght = n->se ;
906 } else {
907 lft = n->nw ;
908 rght = n->ne ;
909 }
910 int r = 0 ;
911 if (x < 0) {
912 int t = nextbit(lft, (x & (w-1)) - wh,
913 (y & (w - 1)) - wh, depth, v) ;
914 if (t >= 0)
915 return t ;
916 r = -x ;
917 x = 0 ;
918 }
919 int t = nextbit(rght, (x & (w-1)) - wh,
920 (y & (w - 1)) - wh, depth, v) ;
921 if (t >= 0)
922 return r + t ;
923 return -1 ;
924 }
925 }
926 /*
927 * Our nonrecurse top-level bit setting routine simply expands the
928 * universe as necessary to encompass the passed-in coordinates, and
929 * then invokes the recursive setbit. Right now it works hashed or
930 * unhashed (but it's faster when unhashed). We also turn on the inGC
931 * flag to inhibit popcount.
932 */
setcell(int x,int y,int newstate)933 int ghashbase::setcell(int x, int y, int newstate) {
934 if (newstate < 0 || newstate >= maxCellStates)
935 return -1 ;
936 if (hashed) {
937 clearstack() ;
938 save(root) ;
939 okaytogc = 1 ;
940 }
941 inGC = 1 ;
942 y = - y ;
943 int sx = x ;
944 int sy = y ;
945 if (depth <= 31) {
946 sx >>= depth ;
947 sy >>= depth ;
948 } else {
949 sx >>= 31 ;
950 sy >>= 31 ;
951 }
952 while (sx > 0 || sx < -1 || sy > 0 || sy < -1) {
953 if (hashed) {
954 root = save(pushroot(root)) ;
955 depth++ ;
956 } else {
957 pushroot_1() ;
958 }
959 sx >>= 1 ;
960 sy >>= 1 ;
961 }
962 root = gsetbit(root, x, y, newstate, depth) ;
963 if (hashed) {
964 okaytogc = 0 ;
965 }
966 return 0 ;
967 }
968 /*
969 * Our nonrecurse top-level bit getting routine.
970 */
getcell(int x,int y)971 int ghashbase::getcell(int x, int y) {
972 y = - y ;
973 int sx = x ;
974 int sy = y ;
975 if (depth <= 31) {
976 sx >>= depth ;
977 sy >>= depth ;
978 } else {
979 sx >>= 31 ;
980 sy >>= 31 ;
981 }
982 if (sx > 0 || sx < -1 || sy > 0 || sy < -1)
983 return 0 ;
984 return getbit(root, x, y, depth) ;
985 }
986 /*
987 * A recursive bit getting routine, but this one returns the
988 * number of pixels to the right to the next set cell in the
989 * current universe, or -1 if none set to the right, or if
990 * the next set pixel is out of range.
991 */
nextcell(int x,int y,int & v)992 int ghashbase::nextcell(int x, int y, int &v) {
993 y = - y ;
994 int sx = x ;
995 int sy = y ;
996 if (depth <= 31) {
997 sx >>= depth ;
998 sy >>= depth ;
999 } else {
1000 sx >>= 31 ;
1001 sy >>= 31 ;
1002 }
1003 while (sx > 0 || sx < -1 || sy > 0 || sy < -1) {
1004 if (hashed) {
1005 root = save(pushroot(root)) ;
1006 depth++ ;
1007 } else {
1008 pushroot_1() ;
1009 }
1010 sx >>= 1 ;
1011 sy >>= 1 ;
1012 }
1013 if (depth > 30) {
1014 struct ghnode tghnode = *root ;
1015 int mdepth = depth ;
1016 while (mdepth > 30) {
1017 tghnode.nw = tghnode.nw->se ;
1018 tghnode.ne = tghnode.ne->sw ;
1019 tghnode.sw = tghnode.sw->ne ;
1020 tghnode.se = tghnode.se->nw ;
1021 mdepth-- ;
1022 }
1023 return nextbit(&tghnode, x, y, mdepth, v) ;
1024 }
1025 return nextbit(root, x, y, depth, v) ;
1026 }
1027 /*
1028 * Canonicalize a universe by filling in the null pointers and then
1029 * invoking find_ghnode on each ghnode. Drops the original universe on
1030 * the floor [big deal, it's probably small anyway].
1031 */
hashpattern(ghnode * root,int depth)1032 ghnode *ghashbase::hashpattern(ghnode *root, int depth) {
1033 ghnode *r ;
1034 if (root == 0) {
1035 r = zeroghnode(depth) ;
1036 } else if (depth == 0) {
1037 ghleaf *n = (ghleaf *)root ;
1038 r = (ghnode *)find_ghleaf(n->nw, n->ne, n->sw, n->se) ;
1039 n->next = freeghnodes ;
1040 freeghnodes = root ;
1041 } else {
1042 depth-- ;
1043 r = find_ghnode(hashpattern(root->nw, depth),
1044 hashpattern(root->ne, depth),
1045 hashpattern(root->sw, depth),
1046 hashpattern(root->se, depth)) ;
1047 root->next = freeghnodes ;
1048 freeghnodes = root ;
1049 }
1050 return r ;
1051 }
endofpattern()1052 void ghashbase::endofpattern() {
1053 poller->bailIfCalculating() ;
1054 if (!hashed) {
1055 root = hashpattern(root, depth) ;
1056 zeroghnode(depth) ;
1057 hashed = 1 ;
1058 }
1059 popValid = 0 ;
1060 needPop = 0 ;
1061 inGC = 0 ;
1062 }
ensure_hashed()1063 void ghashbase::ensure_hashed() {
1064 if (!hashed)
1065 endofpattern() ;
1066 }
1067 /*
1068 * Pop off any levels we don't need.
1069 */
popzeros(ghnode * n)1070 ghnode *ghashbase::popzeros(ghnode *n) {
1071 int depth = ghnode_depth(n) ;
1072 while (depth > 1) {
1073 ghnode *z = zeroghnode(depth-2) ;
1074 if (n->nw->nw == z && n->nw->ne == z && n->nw->sw == z &&
1075 n->ne->nw == z && n->ne->ne == z && n->ne->se == z &&
1076 n->sw->nw == z && n->sw->sw == z && n->sw->se == z &&
1077 n->se->ne == z && n->se->sw == z && n->se->se == z) {
1078 depth-- ;
1079 n = find_ghnode(n->nw->se, n->ne->sw, n->sw->ne, n->se->nw) ;
1080 } else {
1081 break ;
1082 }
1083 }
1084 return n ;
1085 }
1086 /*
1087 * A lot of the routines from here on down traverse the universe, hanging
1088 * information off the ghnodes. The way they generally do so is by using
1089 * (or abusing) the cache (res) field, and the least significant bit of
1090 * the hash next field (as a visited bit).
1091 */
1092 #define marked(n) (1 & (g_uintptr_t)(n)->next)
1093 #define mark(n) ((n)->next = (ghnode *)(1 | (g_uintptr_t)(n)->next))
1094 #define clearmark(n) ((n)->next = (ghnode *)(~1 & (g_uintptr_t)(n)->next))
1095 #define clearmarkbit(p) ((ghnode *)(~1 & (g_uintptr_t)(p)))
1096 /*
1097 * Sometimes we want to use *res* instead of next to mark. You cannot
1098 * do this to leaves, though.
1099 */
1100 #define marked2(n) (3 & (g_uintptr_t)(n)->res)
1101 #define mark2(n) ((n)->res = (ghnode *)(1 | (g_uintptr_t)(n)->res))
1102 #define mark2v(n, v) ((n)->res = (ghnode *)(v | (g_uintptr_t)(n)->res))
1103 #define clearmark2(n) ((n)->res = (ghnode *)(~3 & (g_uintptr_t)(n)->res))
unhash_ghnode(ghnode * n)1104 void ghashbase::unhash_ghnode(ghnode *n) {
1105 ghnode *p ;
1106 g_uintptr_t h = ghnode_hash(n->nw,n->ne,n->sw,n->se) ;
1107 ghnode *pred = 0 ;
1108 h = HASHMOD(h) ;
1109 for (p=hashtab[h]; (!is_ghnode(p) || !marked2(p)) && p; p = p->next) {
1110 if (p == n) {
1111 if (pred)
1112 pred->next = p->next ;
1113 else
1114 hashtab[h] = p->next ;
1115 return ;
1116 }
1117 pred = p ;
1118 }
1119 lifefatal("Didn't find ghnode to unhash") ;
1120 }
unhash_ghnode2(ghnode * n)1121 void ghashbase::unhash_ghnode2(ghnode *n) {
1122 ghnode *p ;
1123 g_uintptr_t h = ghnode_hash(n->nw,n->ne,n->sw,n->se) ;
1124 ghnode *pred = 0 ;
1125 h = HASHMOD(h) ;
1126 for (p=hashtab[h]; p; p = p->next) {
1127 if (p == n) {
1128 if (pred)
1129 pred->next = p->next ;
1130 else
1131 hashtab[h] = p->next ;
1132 return ;
1133 }
1134 pred = p ;
1135 }
1136 lifefatal("Didn't find ghnode to unhash") ;
1137 }
rehash_ghnode(ghnode * n)1138 void ghashbase::rehash_ghnode(ghnode *n) {
1139 g_uintptr_t h = ghnode_hash(n->nw,n->ne,n->sw,n->se) ;
1140 h = HASHMOD(h) ;
1141 n->next = hashtab[h] ;
1142 hashtab[h] = n ;
1143 }
1144 /*
1145 * This recursive routine calculates the population by hanging the
1146 * population on marked ghnodes.
1147 */
calcpop(ghnode * root,int depth)1148 const bigint &ghashbase::calcpop(ghnode *root, int depth) {
1149 if (root == zeroghnode(depth))
1150 return bigint::zero ;
1151 if (depth == 0)
1152 return ((ghleaf *)root)->leafpop ;
1153 if (marked2(root))
1154 return *(bigint*)&(root->next) ;
1155 depth-- ;
1156 if (root->next == 0)
1157 mark2v(root, 3) ;
1158 else {
1159 unhash_ghnode(root) ;
1160 mark2(root) ;
1161 }
1162 /**
1163 * We use the memory in root->next as a value bigint. But we want to
1164 * make sure the copy constructor doesn't "clean up" something that
1165 * doesn't exist. So we clear it to zero here.
1166 */
1167 new(&(root->next))bigint(
1168 calcpop(root->nw, depth), calcpop(root->ne, depth),
1169 calcpop(root->sw, depth), calcpop(root->se, depth)) ;
1170 return *(bigint *)&(root->next) ;
1171 }
1172 /*
1173 * Call this after doing something that unhashes ghnodes in order to
1174 * use the next field as a temp pointer.
1175 */
aftercalcpop2(ghnode * root,int depth)1176 void ghashbase::aftercalcpop2(ghnode *root, int depth) {
1177 if (depth == 0 || root == zeroghnode(depth))
1178 return ;
1179 int v = marked2(root) ;
1180 if (v) {
1181 clearmark2(root) ;
1182 depth-- ;
1183 if (depth > 0) {
1184 aftercalcpop2(root->nw, depth) ;
1185 aftercalcpop2(root->ne, depth) ;
1186 aftercalcpop2(root->sw, depth) ;
1187 aftercalcpop2(root->se, depth) ;
1188 }
1189 ((bigint *)&(root->next))->~bigint() ;
1190 if (v == 3)
1191 root->next = 0 ;
1192 else
1193 rehash_ghnode(root) ;
1194 }
1195 }
1196 /*
1197 * Call this after doing something that unhashes ghnodes in order to
1198 * use the next field as a temp pointer.
1199 */
afterwritemc(ghnode * root,int depth)1200 void ghashbase::afterwritemc(ghnode *root, int depth) {
1201 if (root == zeroghnode(depth))
1202 return ;
1203 if (depth == 0) {
1204 root->nw = 0 ; // all these bigints are guaranteed to be small
1205 return ;
1206 }
1207 if (marked2(root)) {
1208 clearmark2(root) ;
1209 depth-- ;
1210 afterwritemc(root->nw, depth) ;
1211 afterwritemc(root->ne, depth) ;
1212 afterwritemc(root->sw, depth) ;
1213 afterwritemc(root->se, depth) ;
1214 rehash_ghnode(root) ;
1215 }
1216 }
1217 /*
1218 * This top level routine calculates the population of a universe.
1219 */
calcPopulation()1220 void ghashbase::calcPopulation() {
1221 int depth ;
1222 ensure_hashed() ;
1223 depth = ghnode_depth(root) ;
1224 population = calcpop(root, depth) ;
1225 aftercalcpop2(root, depth) ;
1226 }
1227 /*
1228 * Is the universe empty?
1229 */
isEmpty()1230 int ghashbase::isEmpty() {
1231 ensure_hashed() ;
1232 return root == zeroghnode(depth) ;
1233 }
1234 /*
1235 * This routine marks a ghnode as needed to be saved.
1236 */
save(ghnode * n)1237 ghnode *ghashbase::save(ghnode *n) {
1238 if (gsp >= stacksize) {
1239 int nstacksize = stacksize * 2 + 100 ;
1240 alloced += sizeof(ghnode *)*(nstacksize-stacksize) ;
1241 stack = (ghnode **)realloc(stack, nstacksize * sizeof(ghnode *)) ;
1242 if (stack == 0)
1243 lifefatal("Out of memory (3).") ;
1244 stacksize = nstacksize ;
1245 }
1246 stack[gsp++] = n ;
1247 return n ;
1248 }
1249 /*
1250 * This routine pops the stack back to a previous depth.
1251 */
pop(int n)1252 void ghashbase::pop(int n) {
1253 gsp = n ;
1254 }
1255 /*
1256 * This routine clears the stack altogether.
1257 */
clearstack()1258 void ghashbase::clearstack() {
1259 gsp = 0 ;
1260 }
1261 /*
1262 * Do a gc. Walk down from all ghnodes reachable on the stack, saveing
1263 * them by setting the odd bit on the next link. Then, walk the hash,
1264 * eliminating the res from everything that's not saveed, and moving
1265 * the ghnodes from the hash to the freelist as appropriate. Finally,
1266 * walk the hash again, clearing the low order bits in the next pointers.
1267 */
gc_mark(ghnode * root,int invalidate)1268 void ghashbase::gc_mark(ghnode *root, int invalidate) {
1269 if (!marked(root)) {
1270 mark(root) ;
1271 if (is_ghnode(root)) {
1272 gc_mark(root->nw, invalidate) ;
1273 gc_mark(root->ne, invalidate) ;
1274 gc_mark(root->sw, invalidate) ;
1275 gc_mark(root->se, invalidate) ;
1276 if (root->res) {
1277 if (invalidate)
1278 root->res = 0 ;
1279 else
1280 gc_mark(root->res, invalidate) ;
1281 }
1282 }
1283 }
1284 }
1285 /**
1286 * If the invalidate flag is set, we want to kill *all* cache entries
1287 * and recalculate all leaves.
1288 */
do_gc(int invalidate)1289 void ghashbase::do_gc(int invalidate) {
1290 int i ;
1291 g_uintptr_t freed_ghnodes=0 ;
1292 ghnode *p, *pp ;
1293 inGC = 1 ;
1294 gccount++ ;
1295 gcstep++ ;
1296 if (verbose) {
1297 if (gcstep > 1)
1298 sprintf(statusline, "GC #%d(%d)", gccount, gcstep) ;
1299 else
1300 sprintf(statusline, "GC #%d", gccount) ;
1301 lifestatus(statusline) ;
1302 }
1303 for (i=nzeros-1; i>=0; i--)
1304 if (zeroghnodea[i] != 0)
1305 break ;
1306 if (i >= 0)
1307 gc_mark(zeroghnodea[i], 0) ; // never invalidate zeroghnode
1308 if (root != 0)
1309 gc_mark(root, invalidate) ; // pick up the root
1310 for (i=0; i<gsp; i++) {
1311 poller->poll() ;
1312 gc_mark((ghnode *)stack[i], invalidate) ;
1313 }
1314 for (i=0; i<timeline.framecount; i++)
1315 gc_mark((ghnode *)timeline.frames[i], invalidate) ;
1316 hashpop = 0 ;
1317 memset(hashtab, 0, sizeof(ghnode *) * hashprime) ;
1318 freeghnodes = 0 ;
1319 for (p=ghnodeblocks; p; p=p->next) {
1320 poller->poll() ;
1321 for (pp=p+1, i=1; i<1001; i++, pp++) {
1322 if (marked(pp)) {
1323 g_uintptr_t h = 0 ;
1324 if (pp->nw) { /* yes, it's a ghnode */
1325 h = HASHMOD(ghnode_hash(pp->nw, pp->ne, pp->sw, pp->se)) ;
1326 } else {
1327 ghleaf *lp = (ghleaf *)pp ;
1328 h = HASHMOD(ghleaf_hash(lp->nw, lp->ne, lp->sw, lp->se)) ;
1329 }
1330 pp->next = hashtab[h] ;
1331 hashtab[h] = pp ;
1332 hashpop++ ;
1333 } else {
1334 pp->next = freeghnodes ;
1335 freeghnodes = pp ;
1336 freed_ghnodes++ ;
1337 }
1338 }
1339 }
1340 inGC = 0 ;
1341 if (verbose) {
1342 double perc = (double)freed_ghnodes / (double)totalthings * 100.0 ;
1343 sprintf(statusline+strlen(statusline), " freed %g percent (%" PRIuPTR ").",
1344 perc, freed_ghnodes) ;
1345 lifestatus(statusline) ;
1346 }
1347 if (needPop) {
1348 calcPopulation() ;
1349 popValid = 1 ;
1350 needPop = 0 ;
1351 poller->updatePop() ;
1352 }
1353 }
1354 /*
1355 * Clear the cache bits down to the appropriate level, marking the
1356 * ghnodes we've handled.
1357 */
clearcache(ghnode * n,int depth,int clearto)1358 void ghashbase::clearcache(ghnode *n, int depth, int clearto) {
1359 if (!marked(n)) {
1360 mark(n) ;
1361 if (depth > 1) {
1362 depth-- ;
1363 poller->poll() ;
1364 clearcache(n->nw, depth, clearto) ;
1365 clearcache(n->ne, depth, clearto) ;
1366 clearcache(n->sw, depth, clearto) ;
1367 clearcache(n->se, depth, clearto) ;
1368 if (n->res)
1369 clearcache(n->res, depth, clearto) ;
1370 }
1371 if (depth >= clearto)
1372 n->res = 0 ;
1373 }
1374 }
1375 /*
1376 * Mark the nodes we need to clear the result from.
1377 */
clearcache_p1(ghnode * n,int depth,int clearto)1378 void ghashbase::clearcache_p1(ghnode *n, int depth, int clearto) {
1379 if (depth < clearto || marked(n))
1380 return ;
1381 mark(n) ;
1382 if (depth > clearto) {
1383 depth-- ;
1384 poller->poll() ;
1385 clearcache_p1(n->nw, depth, clearto) ;
1386 clearcache_p1(n->ne, depth, clearto) ;
1387 clearcache_p1(n->sw, depth, clearto) ;
1388 clearcache_p1(n->se, depth, clearto) ;
1389 if (n->res)
1390 clearcache_p1(n->res, depth, clearto) ;
1391 }
1392 }
1393 /*
1394 * Unmark the nodes and clear the cached result.
1395 */
clearcache_p2(ghnode * n,int depth,int clearto)1396 void ghashbase::clearcache_p2(ghnode *n, int depth, int clearto) {
1397 if (depth < clearto || !marked(n))
1398 return ;
1399 clearmark(n) ;
1400 if (depth > clearto) {
1401 depth-- ;
1402 poller->poll() ;
1403 clearcache_p2(n->nw, depth, clearto) ;
1404 clearcache_p2(n->ne, depth, clearto) ;
1405 clearcache_p2(n->sw, depth, clearto) ;
1406 clearcache_p2(n->se, depth, clearto) ;
1407 if (n->res)
1408 clearcache_p2(n->res, depth, clearto) ;
1409 }
1410 if (n->res)
1411 n->res = 0 ;
1412 }
1413 /*
1414 * Clear the entire cache of everything, and recalculate all leaves.
1415 * This can be very expensive.
1416 */
clearcache()1417 void ghashbase::clearcache() {
1418 cacheinvalid = 1 ;
1419 }
1420 /*
1421 * Change the ngens value. Requires us to walk the hash, clearing
1422 * the cache fields of any ghnodes that do not have the appropriate
1423 * values.
1424 */
new_ngens(int newval)1425 void ghashbase::new_ngens(int newval) {
1426 g_uintptr_t i ;
1427 ghnode *p, *pp ;
1428 int clearto = ngens ;
1429 if (newval > ngens && halvesdone == 0) {
1430 ngens = newval ;
1431 return ;
1432 }
1433 #ifndef NOGCBEFOREINC
1434 do_gc(0) ;
1435 #endif
1436 if (verbose) {
1437 strcpy(statusline, "Changing increment...") ;
1438 lifestatus(statusline) ;
1439 }
1440 if (newval < clearto)
1441 clearto = newval ;
1442 clearto++ ; /* clear this depth and above */
1443 if (clearto < 1)
1444 clearto = 1 ;
1445 ngens = newval ;
1446 inGC = 1 ;
1447 for (i=0; i<hashprime; i++)
1448 for (p=hashtab[i]; p; p=clearmarkbit(p->next))
1449 if (is_ghnode(p) && !marked(p))
1450 clearcache(p, ghnode_depth(p), clearto) ;
1451 for (p=ghnodeblocks; p; p=p->next) {
1452 poller->poll() ;
1453 for (pp=p+1, i=1; i<1001; i++, pp++)
1454 clearmark(pp) ;
1455 }
1456 halvesdone = 0 ;
1457 inGC = 0 ;
1458 if (needPop) {
1459 calcPopulation() ;
1460 popValid = 1 ;
1461 needPop = 0 ;
1462 poller->updatePop() ;
1463 }
1464 if (verbose) {
1465 strcpy(statusline+strlen(statusline), " done.") ;
1466 lifestatus(statusline) ;
1467 }
1468 }
1469 /*
1470 * Return log2.
1471 */
log2(unsigned int n)1472 int ghashbase::log2(unsigned int n) {
1473 int r = 0 ;
1474 while ((n & 1) == 0) {
1475 n >>= 1 ;
1476 r++ ;
1477 }
1478 if (n != 1) {
1479 lifefatal("Expected power of two!") ;
1480 }
1481 return r ;
1482 }
1483 static bigint negone = -1 ;
getPopulation()1484 const bigint &ghashbase::getPopulation() {
1485 // note: if called during gc, then we cannot call calcPopulation
1486 // since that will mess up the gc.
1487 if (!popValid) {
1488 if (inGC) {
1489 needPop = 1 ;
1490 return negone ;
1491 } else if (poller->isCalculating()) {
1492 // AKT: avoid calling poller->bailIfCalculating
1493 return negone ;
1494 } else {
1495 calcPopulation() ;
1496 popValid = 1 ;
1497 needPop = 0 ;
1498 }
1499 }
1500 return population ;
1501 }
1502 /*
1503 * Finally, we get to run the pattern. We first ensure that all
1504 * clearspace ghnodes and the input pattern is never garbage
1505 * collected; we turn on garbage collection, and then we invoke our
1506 * magic top-level routine passing in clearspace borders that are
1507 * guaranteed large enough.
1508 */
runpattern()1509 ghnode *ghashbase::runpattern() {
1510 ghnode *n = root ;
1511 save(root) ; // do this in case we interrupt generation
1512 ensure_hashed() ;
1513 okaytogc = 1 ;
1514 if (cacheinvalid) {
1515 do_gc(1) ; // invalidate the entire cache and recalc leaves
1516 cacheinvalid = 0 ;
1517 }
1518 int depth = ghnode_depth(n) ;
1519 ghnode *n2 ;
1520 n = pushroot(n) ;
1521 depth++ ;
1522 n = pushroot(n) ;
1523 depth++ ;
1524 while (ngens + 2 > depth) {
1525 n = pushroot(n) ;
1526 depth++ ;
1527 }
1528 save(zeroghnode(nzeros-1)) ;
1529 save(n) ;
1530 n2 = getres(n, depth) ;
1531 okaytogc = 0 ;
1532 clearstack() ;
1533 if (halvesdone == 1 && n->res != 0) {
1534 n->res = 0 ;
1535 halvesdone = 0 ;
1536 }
1537 if (poller->isInterrupted() || softinterrupt)
1538 return 0 ; // indicate it was interrupted
1539 n = popzeros(n2) ;
1540 generation += pow2step ;
1541 return n ;
1542 }
readmacrocell(char * line)1543 const char *ghashbase::readmacrocell(char *line) {
1544 int n=0 ;
1545 g_uintptr_t i=1, nw=0, ne=0, sw=0, se=0, indlen=0 ;
1546 int r, d ;
1547 ghnode **ind = 0 ;
1548 root = 0 ;
1549 while (getline(line, 10000)) {
1550 if (i >= indlen) {
1551 g_uintptr_t nlen = i + indlen + 10 ;
1552 ind = (ghnode **)realloc(ind, sizeof(ghnode*) * nlen) ;
1553 if (ind == 0)
1554 lifefatal("Out of memory (4).") ;
1555 while (indlen < nlen)
1556 ind[indlen++] = 0 ;
1557 }
1558 if (line[0] == '#') {
1559 char *p, *pp ;
1560 const char *err ;
1561 switch (line[1]) {
1562 case 'R':
1563 p = line + 2 ;
1564 while (*p && *p <= ' ') p++ ;
1565 pp = p ;
1566 while (*pp > ' ') pp++ ;
1567 *pp = 0 ;
1568 err = setrule(p);
1569 if (err) return err;
1570 break ;
1571
1572 case 'G':
1573 p = line + 2 ;
1574 while (*p && *p <= ' ') p++ ;
1575 pp = p ;
1576 while (*pp >= '0' && *pp <= '9') pp++ ;
1577 *pp = 0 ;
1578 generation = bigint(p) ;
1579 break ;
1580 // either:
1581 // #FRAMES count base inc
1582 // or
1583 // #FRAME index node
1584 case 'F':
1585 if (strncmp(line, "#FRAMES ", 8) == 0) {
1586 p = line + 8 ;
1587 while (*p && *p <= ' ')
1588 p++ ;
1589 long cnt = atol(p) ;
1590 if (cnt < 0 || cnt > MAX_FRAME_COUNT)
1591 return "Bad FRAMES line" ;
1592 destroytimeline() ;
1593 while ('0' <= *p && *p <= '9')
1594 p++ ;
1595 while (*p && *p <= ' ')
1596 p++ ;
1597 pp = p ;
1598 while ((*pp >= '0' && *pp <= '9') || *pp == ',') pp++ ;
1599 if (*pp == 0)
1600 return "Bad FRAMES line" ;
1601 *pp = 0 ;
1602 timeline.start = bigint(p) ;
1603 timeline.end = timeline.start ;
1604 timeline.next = timeline.end ;
1605 p = pp + 1 ;
1606 while (*p && *p <= ' ')
1607 p++ ;
1608 pp = p ;
1609 while (*pp > ' ')
1610 pp++ ;
1611 *pp = 0 ;
1612 if (strchr(p, '^')) {
1613 int tbase=0, texpo=0 ;
1614 if (sscanf(p, "%d^%d", &tbase, &texpo) != 2 ||
1615 tbase < 2 || texpo < 0)
1616 return "Bad FRAMES line" ;
1617 timeline.base = tbase ;
1618 timeline.expo = texpo ;
1619 timeline.inc = 1 ;
1620 while (texpo--)
1621 timeline.inc.mul_smallint(tbase) ;
1622 } else {
1623 timeline.inc = bigint(p) ;
1624 // if it's a power of two, we're good
1625 int texpo = timeline.inc.lowbitset() ;
1626 int tbase = 2 ;
1627 bigint test = 1 ;
1628 for (int i=0; i<texpo; i++)
1629 test += test ;
1630 if (test != timeline.inc)
1631 return "Bad increment (missing ^) in FRAMES" ;
1632 timeline.base = tbase ;
1633 timeline.expo = texpo ;
1634 }
1635 } else if (strncmp(line, "#FRAME ", 7) == 0) {
1636 int frameind = 0 ;
1637 g_uintptr_t nodeind = 0 ;
1638 n = sscanf(line+7, "%d %" PRIuPTR, &frameind, &nodeind) ;
1639 if (n != 2 || frameind > MAX_FRAME_COUNT || frameind < 0 ||
1640 nodeind > i || timeline.framecount != frameind)
1641 return "Bad FRAME line" ;
1642 timeline.frames.push_back(ind[nodeind]) ;
1643 timeline.framecount++ ;
1644 timeline.end = timeline.next ;
1645 timeline.next += timeline.inc ;
1646 }
1647 break ;
1648 }
1649 } else {
1650 n = sscanf(line, "%d %" PRIuPTR " %" PRIuPTR " %" PRIuPTR " %" PRIuPTR " %d", &d, &nw, &ne, &sw, &se, &r) ;
1651 if (n < 0) // blank line; permit
1652 continue ;
1653 if (n == 0) {
1654 // conversion error in first argument; we allow only if the only
1655 // content on the line is whitespace.
1656 char *ws = line ;
1657 while (*ws && *ws <= ' ')
1658 ws++ ;
1659 if (*ws > 0)
1660 return "Parse error in macrocell format." ;
1661 continue ;
1662 }
1663 if (n < 5)
1664 // best not to use lifefatal here because user won't see any
1665 // error message when reading clipboard data starting with "[..."
1666 return "Parse error in readmacrocell." ;
1667 if (d < 1)
1668 return "Oops; bad depth in readmacrocell." ;
1669 if (d == 1) {
1670 if (nw >= (g_uintptr_t)maxCellStates || ne >= (g_uintptr_t)maxCellStates ||
1671 sw >= (g_uintptr_t)maxCellStates || se >= (g_uintptr_t)maxCellStates)
1672 return "Cell state values too high for this algorithm." ;
1673 root = ind[i++] = (ghnode *)find_ghleaf((state)nw, (state)ne,
1674 (state)sw, (state)se) ;
1675 depth = d - 1 ;
1676 } else {
1677 ind[0] = zeroghnode(d-2) ; /* allow zeros to work right */
1678 if (nw >= i || ind[nw] == 0 || ne >= i || ind[ne] == 0 ||
1679 sw >= i || ind[sw] == 0 || se >= i || ind[se] == 0) {
1680 return "Node out of range in readmacrocell." ;
1681 }
1682 clearstack() ;
1683 root = ind[i++] = find_ghnode(ind[nw], ind[ne], ind[sw], ind[se]) ;
1684 depth = d - 1 ;
1685 }
1686 }
1687 }
1688 if (ind)
1689 free(ind) ;
1690 if (root == 0) {
1691 // allow empty macrocell pattern; note that endofpattern()
1692 // will be called soon so don't set hashed here
1693 // return "Invalid macrocell file: no ghnodes." ;
1694 return 0 ;
1695 }
1696 hashed = 1 ;
1697 return 0 ;
1698 }
setrule(const char *)1699 const char *ghashbase::setrule(const char *) {
1700 poller->bailIfCalculating() ;
1701 clearcache() ;
1702 return 0 ;
1703 }
1704 /**
1705 * Write out the native macrocell format. This is the one we use when
1706 * we're not interactive and displaying a progress dialog.
1707 */
writecell(std::ostream & os,ghnode * root,int depth)1708 g_uintptr_t ghashbase::writecell(std::ostream &os, ghnode *root, int depth) {
1709 g_uintptr_t thiscell = 0 ;
1710 if (root == zeroghnode(depth))
1711 return 0 ;
1712 if (depth == 0) {
1713 if (root->nw != 0)
1714 return (g_uintptr_t)(root->nw) ;
1715 } else {
1716 if (marked2(root))
1717 return (g_uintptr_t)(root->next) ;
1718 unhash_ghnode2(root) ;
1719 mark2(root) ;
1720 }
1721 thiscell = ++cellcounter ;
1722 if (depth == 0) {
1723 ghleaf *n = (ghleaf *)root ;
1724 root->nw = (ghnode *)thiscell ;
1725 os << 1 << ' ' << int(n->nw) << ' ' << int(n->ne)
1726 << ' ' << int(n->sw) << ' ' << int(n->se) << '\n' ;
1727 } else {
1728 g_uintptr_t nw = writecell(os, root->nw, depth-1) ;
1729 g_uintptr_t ne = writecell(os, root->ne, depth-1) ;
1730 g_uintptr_t sw = writecell(os, root->sw, depth-1) ;
1731 g_uintptr_t se = writecell(os, root->se, depth-1) ;
1732 root->next = (ghnode *)thiscell ;
1733 os << depth+1 << ' ' << nw << ' ' << ne
1734 << ' ' << sw << ' ' << se << '\n' ;
1735 }
1736 return thiscell ;
1737 }
1738 /**
1739 * This new two-pass method works by doing a prepass that numbers the
1740 * ghnodes and counts the number of ghnodes that should be sent, so we can
1741 * display an accurate progress dialog.
1742 */
writecell_2p1(ghnode * root,int depth)1743 g_uintptr_t ghashbase::writecell_2p1(ghnode *root, int depth) {
1744 g_uintptr_t thiscell = 0 ;
1745 if (root == zeroghnode(depth))
1746 return 0 ;
1747 if (depth == 0) {
1748 if (root->nw != 0)
1749 return (g_uintptr_t)(root->nw) ;
1750 } else {
1751 if (marked2(root))
1752 return (g_uintptr_t)(root->next) ;
1753 unhash_ghnode2(root) ;
1754 mark2(root) ;
1755 }
1756 if (depth == 0) {
1757 thiscell = ++cellcounter ;
1758 // note: we *must* not abort this prescan
1759 if ((cellcounter & 4095) == 0)
1760 lifeabortprogress(0, "Scanning tree") ;
1761 root->nw = (ghnode *)thiscell ;
1762 } else {
1763 writecell_2p1(root->nw, depth-1) ;
1764 writecell_2p1(root->ne, depth-1) ;
1765 writecell_2p1(root->sw, depth-1) ;
1766 writecell_2p1(root->se, depth-1) ;
1767 thiscell = ++cellcounter ;
1768 // note: we *must* not abort this prescan
1769 if ((cellcounter & 4095) == 0)
1770 lifeabortprogress(0, "Scanning tree") ;
1771 root->next = (ghnode *)thiscell ;
1772 }
1773 return thiscell ;
1774 }
1775 /**
1776 * This one writes the cells, but assuming they've already been
1777 * numbered, and displaying a progress dialog.
1778 */
1779 static char progressmsg[80] ;
writecell_2p2(std::ostream & os,ghnode * root,int depth)1780 g_uintptr_t ghashbase::writecell_2p2(std::ostream &os, ghnode *root, int depth) {
1781 g_uintptr_t thiscell = 0 ;
1782 if (root == zeroghnode(depth))
1783 return 0 ;
1784 if (depth == 0) {
1785 if (cellcounter + 1 != (g_uintptr_t)(root->nw))
1786 return (g_uintptr_t)(root->nw) ;
1787 thiscell = ++cellcounter ;
1788 if ((cellcounter & 4095) == 0) {
1789 std::streampos siz = os.tellp() ;
1790 sprintf(progressmsg, "File size: %.2f MB", double(siz) / 1048576.0) ;
1791 lifeabortprogress(thiscell/(double)writecells, progressmsg) ;
1792 }
1793 ghleaf *n = (ghleaf *)root ;
1794 root->nw = (ghnode *)thiscell ;
1795 os << 1 << ' ' << int(n->nw) << ' ' << int(n->ne)
1796 << ' ' << int(n->sw) << ' ' << int(n->se) << '\n';
1797 } else {
1798 if (cellcounter + 1 > (g_uintptr_t)(root->next) || isaborted())
1799 return (g_uintptr_t)(root->next) ;
1800 g_uintptr_t nw = writecell_2p2(os, root->nw, depth-1) ;
1801 g_uintptr_t ne = writecell_2p2(os, root->ne, depth-1) ;
1802 g_uintptr_t sw = writecell_2p2(os, root->sw, depth-1) ;
1803 g_uintptr_t se = writecell_2p2(os, root->se, depth-1) ;
1804 if (!isaborted() &&
1805 cellcounter + 1 != (g_uintptr_t)(root->next)) { // this should never happen
1806 lifefatal("Internal in writecell_2p2") ;
1807 return (g_uintptr_t)(root->next) ;
1808 }
1809 thiscell = ++cellcounter ;
1810 if ((cellcounter & 4095) == 0) {
1811 std::streampos siz = os.tellp() ;
1812 sprintf(progressmsg, "File size: %.2f MB", double(siz) / 1048576.0) ;
1813 lifeabortprogress(thiscell/(double)writecells, progressmsg) ;
1814 }
1815 root->next = (ghnode *)thiscell ;
1816 os << depth+1 << ' ' << nw << ' ' << ne
1817 << ' ' << sw << ' ' << se << '\n' ;
1818 }
1819 return thiscell ;
1820 }
1821 #define STRINGIFY(arg) STR2(arg)
1822 #define STR2(arg) #arg
writeNativeFormat(std::ostream & os,char * comments)1823 const char *ghashbase::writeNativeFormat(std::ostream &os, char *comments) {
1824 int depth = ghnode_depth(root) ;
1825 os << "[M2] (golly " STRINGIFY(VERSION) ")\n" ;
1826
1827 // AKT: always write out explicit rule
1828 os << "#R " << getrule() << '\n' ;
1829
1830 if (generation > bigint::zero) {
1831 // write non-zero gen count
1832 os << "#G " << generation.tostring('\0') << '\n' ;
1833 }
1834
1835 if (comments) {
1836 // write given comment line(s), but we can't just do "os << comments" because the
1837 // lines might not start with #C (eg. if they came from the end of a .rle file),
1838 // so we must ensure that each comment line in the .mc file starts with #C
1839 char *p = comments;
1840 while (*p != '\0') {
1841 char *line = p;
1842 // note that readcomments() in readpattern.cpp ensures each line ends with \n
1843 while (*p != '\n') p++;
1844 if (line[0] != '#' || line[1] != 'C') {
1845 os << "#C ";
1846 }
1847 if (line != p) {
1848 *p = '\0';
1849 os << line;
1850 *p = '\n';
1851 }
1852 os << '\n';
1853 p++;
1854 }
1855 }
1856
1857 inGC = 1 ;
1858 /* this is the old way:
1859 cellcounter = 0 ;
1860 writecell(os, root, depth) ;
1861 */
1862 /* this is the new two-pass way */
1863 cellcounter = 0 ;
1864 vector<int> depths(timeline.framecount) ;
1865 int framestosave = timeline.framecount ;
1866 if (timeline.savetimeline == 0)
1867 framestosave = 0 ;
1868 if (framestosave) {
1869 for (int i=0; i<timeline.framecount; i++) {
1870 ghnode *frame = (ghnode*)timeline.frames[i] ;
1871 depths[i] = ghnode_depth(frame) ;
1872 }
1873 for (int i=0; i<timeline.framecount; i++) {
1874 ghnode *frame = (ghnode*)timeline.frames[i] ;
1875 writecell_2p1(frame, depths[i]) ;
1876 }
1877 }
1878 writecell_2p1(root, depth) ;
1879 writecells = cellcounter ;
1880 cellcounter = 0 ;
1881 if (framestosave) {
1882 os << "#FRAMES"
1883 << ' ' << timeline.framecount
1884 << ' ' << timeline.start.tostring()
1885 << ' ' << timeline.base << '^' << timeline.expo << '\n' ;
1886 for (int i=0; i<timeline.framecount; i++) {
1887 ghnode *frame = (ghnode*)timeline.frames[i] ;
1888 writecell_2p2(os, frame, depths[i]) ;
1889 os << "#FRAME " << i << ' ' << (g_uintptr_t)frame->next << '\n' ;
1890 }
1891 }
1892 writecell_2p2(os, root, depth) ;
1893 /* end new two-pass way */
1894 if (framestosave) {
1895 for (int i=0; i<timeline.framecount; i++) {
1896 ghnode *frame = (ghnode*)timeline.frames[i] ;
1897 afterwritemc(frame, depths[i]) ;
1898 }
1899 }
1900 afterwritemc(root, depth) ;
1901 inGC = 0 ;
1902 return 0 ;
1903 }
1904 char ghashbase::statusline[120] ;
doInitializeAlgoInfo(staticAlgoInfo & ai)1905 void ghashbase::doInitializeAlgoInfo(staticAlgoInfo &ai) {
1906 ai.setDefaultBaseStep(8) ;
1907 ai.setDefaultMaxMem(500) ; // MB
1908 }
1909