16 #include "uct/internal.h"
17 #include "uct/prior.h"
21 /* Allocate one node in the fast_alloc mode. The returned node
22 * is _not_ initialized. Returns NULL if not enough memory.
23 * This function may be called by multiple threads in parallel. */
24 static struct tree_node
*
25 tree_fast_alloc_node(struct tree
*t
)
27 assert(t
->nodes
!= NULL
);
28 struct tree_node
*n
= NULL
;
29 unsigned long old_size
=__sync_fetch_and_add(&t
->nodes_size
, sizeof(*n
));
31 /* The test below works even if max_tree_size is not a
32 * multiple of the node size because tree_init() allocates
33 * space for an extra node. */
34 if (old_size
< t
->max_tree_size
)
35 n
= (struct tree_node
*)(t
->nodes
+ old_size
);
39 /* Allocate and initialize a node. Returns NULL (fast_alloc mode)
40 * or exits the main program if not enough memory.
41 * This function may be called by multiple threads in parallel. */
42 static struct tree_node
*
43 tree_init_node(struct tree
*t
, coord_t coord
, int depth
)
47 n
= tree_fast_alloc_node(t
);
49 memset(n
, 0, sizeof(*n
));
51 n
= calloc(1, sizeof(*n
));
53 fprintf(stderr
, "tree_init_node(): OUT OF MEMORY\n");
56 __sync_fetch_and_add(&t
->nodes_size
, sizeof(*n
));
60 volatile static long c
= 1000000;
61 n
->hash
= __sync_fetch_and_add(&c
, 1);
62 if (depth
> t
->max_depth
)
67 /* Create a tree structure. Pre-allocate all nodes if max_tree_size is > 0. */
69 tree_init(struct board
*board
, enum stone color
, unsigned long max_tree_size
)
71 struct tree
*t
= calloc(1, sizeof(*t
));
73 t
->max_tree_size
= max_tree_size
;
74 if (max_tree_size
!= 0) {
75 /* Allocate one extra node, max_tree_size may not be multiple of node size. */
76 t
->nodes
= malloc(max_tree_size
+ sizeof(struct tree_node
));
77 /* The nodes buffer doesn't need initialization. This is currently
78 * done by tree_init_node to spread the load. Doing a memset for the
79 * entire buffer here would be too slow for large trees (>10 GB). */
81 fprintf(stderr
, "tree_init(): OUT OF MEMORY\n");
85 /* The root PASS move is only virtual, we never play it. */
86 t
->root
= tree_init_node(t
, pass
, 0);
87 t
->root_symmetry
= board
->symmetry
;
88 t
->root_color
= stone_other(color
); // to research black moves, root will be white
93 /* This function may be called by multiple threads in parallel on the
94 * same tree, but not on node n. n may be detached from the tree but
95 * must have been created in this tree originally.
96 * It returns the remaining size of the tree after n has been freed. */
98 tree_done_node(struct tree
*t
, struct tree_node
*n
)
100 struct tree_node
*ni
= n
->children
;
102 struct tree_node
*nj
= ni
->sibling
;
103 tree_done_node(t
, ni
);
107 unsigned long old_size
= __sync_fetch_and_sub(&t
->nodes_size
, sizeof(*n
));
108 return old_size
- sizeof(*n
);
116 /* Worker thread for tree_done_node_detached(). Only for fast_alloc=false. */
118 tree_done_node_worker(void *ctx_
)
120 struct subtree_ctx
*ctx
= ctx_
;
121 char *str
= coord2str(ctx
->n
->coord
, ctx
->t
->board
);
123 unsigned long tree_size
= tree_done_node(ctx
->t
, ctx
->n
);
127 fprintf(stderr
, "done freeing node at %s, tree size %lu\n", str
, tree_size
);
133 /* Asynchronously free the subtree of nodes rooted at n. If the tree becomes
134 * empty free the tree also. Only for fast_alloc=false. */
136 tree_done_node_detached(struct tree
*t
, struct tree_node
*n
)
138 if (n
->u
.playouts
< 1000) { // no thread for small tree
139 if (!tree_done_node(t
, n
))
144 pthread_attr_init(&attr
);
145 pthread_attr_setdetachstate(&attr
, PTHREAD_CREATE_DETACHED
);
148 struct subtree_ctx
*ctx
= malloc(sizeof(struct subtree_ctx
));
150 fprintf(stderr
, "tree_done_node_detached(): OUT OF MEMORY\n");
155 pthread_create(&thread
, &attr
, tree_done_node_worker
, ctx
);
156 pthread_attr_destroy(&attr
);
160 tree_done(struct tree
*t
)
162 if (t
->chchvals
) free(t
->chchvals
);
163 if (t
->chvals
) free(t
->chvals
);
167 } else if (!tree_done_node(t
, t
->root
)) {
169 /* A tree_done_node_worker might still be running on this tree but
170 * it will free the tree later. It is also freeing nodes faster than
171 * we will create new ones. */
177 tree_node_dump(struct tree
*tree
, struct tree_node
*node
, int l
, int thres
)
179 for (int i
= 0; i
< l
; i
++) fputc(' ', stderr
);
181 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
183 /* We use 1 as parity, since for all nodes we want to know the
184 * win probability of _us_, not the node color. */
185 fprintf(stderr
, "[%s] %f %% %d [prior %f %% %d amaf %f %% %d]; hints %x; %d children <%"PRIhash
">\n",
186 coord2sstr(node
->coord
, tree
->board
),
187 tree_node_get_value(tree
, 1, node
->u
.value
), node
->u
.playouts
,
188 tree_node_get_value(tree
, 1, node
->prior
.value
), node
->prior
.playouts
,
189 tree_node_get_value(tree
, 1, node
->amaf
.value
), node
->amaf
.playouts
,
190 node
->hints
, children
, node
->hash
);
192 /* Print nodes sorted by #playouts. */
194 struct tree_node
*nbox
[1000]; int nboxl
= 0;
195 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
196 if (ni
->u
.playouts
> thres
)
201 for (int i
= 0; i
< nboxl
; i
++)
202 if (nbox
[i
] && (best
< 0 || nbox
[i
]->u
.playouts
> nbox
[best
]->u
.playouts
))
206 tree_node_dump(tree
, nbox
[best
], l
+ 1, /* node->u.value < 0.1 ? 0 : */ thres
);
212 tree_dump_chval(struct tree
*tree
, struct move_stats
*v
)
214 for (int y
= board_size(tree
->board
) - 2; y
> 1; y
--) {
215 for (int x
= 1; x
< board_size(tree
->board
) - 1; x
++) {
216 coord_t c
= coord_xy(tree
->board
, x
, y
);
217 fprintf(stderr
, "%.2f%%%05d ", v
[c
].value
, v
[c
].playouts
);
219 fprintf(stderr
, "\n");
224 tree_dump(struct tree
*tree
, int thres
)
226 if (thres
&& tree
->root
->u
.playouts
/ thres
> 100) {
227 /* Be a bit sensible about this; the opening book can create
228 * huge dumps at first. */
229 thres
= tree
->root
->u
.playouts
/ 100 * (thres
< 1000 ? 1 : thres
/ 1000);
231 fprintf(stderr
, "(UCT tree; root %s; extra komi %f)\n",
232 stone2str(tree
->root_color
), tree
->extra_komi
);
233 tree_node_dump(tree
, tree
->root
, 0, thres
);
235 if (DEBUGL(3) && tree
->chvals
) {
236 fprintf(stderr
, "children stats:\n");
237 tree_dump_chval(tree
, tree
->chvals
);
238 fprintf(stderr
, "grandchildren stats:\n");
239 tree_dump_chval(tree
, tree
->chchvals
);
245 tree_book_name(struct board
*b
)
247 static char buf
[256];
248 if (b
->handicap
> 0) {
249 sprintf(buf
, "uctbook-%d-%02.01f-h%d.pachitree", b
->size
- 2, b
->komi
, b
->handicap
);
251 sprintf(buf
, "uctbook-%d-%02.01f.pachitree", b
->size
- 2, b
->komi
);
257 tree_node_save(FILE *f
, struct tree_node
*node
, int thres
)
259 bool save_children
= node
->u
.playouts
>= thres
;
262 node
->is_expanded
= 0;
265 fwrite(((void *) node
) + offsetof(struct tree_node
, depth
),
266 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
270 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
271 tree_node_save(f
, ni
, thres
);
274 node
->is_expanded
= 1;
281 tree_save(struct tree
*tree
, struct board
*b
, int thres
)
283 char *filename
= tree_book_name(b
);
284 FILE *f
= fopen(filename
, "wb");
289 tree_node_save(f
, tree
->root
, thres
);
296 tree_node_load(FILE *f
, struct tree_node
*node
, int *num
)
300 fread(((void *) node
) + offsetof(struct tree_node
, depth
),
301 sizeof(struct tree_node
) - offsetof(struct tree_node
, depth
),
304 /* Keep values in sane scale, otherwise we start overflowing. */
305 #define MAX_PLAYOUTS 10000000
306 if (node
->u
.playouts
> MAX_PLAYOUTS
) {
307 node
->u
.playouts
= MAX_PLAYOUTS
;
309 if (node
->amaf
.playouts
> MAX_PLAYOUTS
) {
310 node
->amaf
.playouts
= MAX_PLAYOUTS
;
312 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
313 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
315 struct tree_node
*ni
= NULL
, *ni_prev
= NULL
;
317 ni_prev
= ni
; ni
= calloc(1, sizeof(*ni
));
321 ni_prev
->sibling
= ni
;
323 tree_node_load(f
, ni
, num
);
328 tree_load(struct tree
*tree
, struct board
*b
)
330 char *filename
= tree_book_name(b
);
331 FILE *f
= fopen(filename
, "rb");
335 fprintf(stderr
, "Loading opening book %s...\n", filename
);
339 tree_node_load(f
, tree
->root
, &num
);
340 fprintf(stderr
, "Loaded %d nodes.\n", num
);
346 static struct tree_node
*
347 tree_node_copy(struct tree_node
*node
)
349 struct tree_node
*n2
= malloc(sizeof(*n2
));
353 struct tree_node
*ni
= node
->children
;
354 struct tree_node
*ni2
= tree_node_copy(ni
);
355 n2
->children
= ni2
; ni2
->parent
= n2
;
356 while ((ni
= ni
->sibling
)) {
357 ni2
->sibling
= tree_node_copy(ni
);
358 ni2
= ni2
->sibling
; ni2
->parent
= n2
;
364 tree_copy(struct tree
*tree
)
366 assert(!tree
->nodes
);
367 struct tree
*t2
= malloc(sizeof(*t2
));
369 t2
->root
= tree_node_copy(tree
->root
);
373 /* Copy the subtree rooted at node, discarding nodes with less
374 * than min_playouts or more than max_playouts, until dest is
375 * full or we have copied all the subtree. Only for fast_alloc.
376 * The code is destructive on src, and the order of nodes is changed.
377 * Returns the copy of node in the destination tree, or NULL
378 * if we could not copy it. */
379 static struct tree_node
*
380 tree_prune(struct tree
*dest
, struct tree
*src
, struct tree_node
*node
,
381 int min_playouts
, int max_playouts
)
383 assert(dest
->nodes
&& node
);
384 if (node
->u
.playouts
< min_playouts
|| dest
->nodes_size
>= dest
->max_tree_size
)
386 struct tree_node
*n2
;
387 if (node
->u
.playouts
> max_playouts
) {
388 /* Node already copied but we must recurse on the children.
389 * Here node->parent is the node copy. */
391 assert(n2
&& n2
->hash
== node
->hash
);
393 n2
= tree_fast_alloc_node(dest
);
396 if (n2
->depth
> dest
->max_depth
)
397 dest
->max_depth
= n2
->depth
;
399 n2
->is_expanded
= false;
400 // Misuse the parent field to remember the copy for future passses:
403 struct tree_node
*ni
= node
->children
;
405 struct tree_node
*ni2
= tree_prune(dest
, src
, ni
, min_playouts
, max_playouts
);
406 if (ni2
&& ni2
->u
.playouts
<= max_playouts
) {
407 ni2
->sibling
= n2
->children
;
409 n2
->is_expanded
= true;
417 /* Free all the tree, keeping only the subtree rooted at node.
418 * Prune the subtree if necessary to fit in max_size bytes.
419 * Returns the moved node. Only for fast_alloc. */
420 static struct tree_node
*
421 tree_garbage_collect(struct tree
*tree
, unsigned long max_size
, struct tree_node
*node
)
423 assert(tree
->nodes
&& !node
->parent
&& !node
->sibling
);
424 struct tree
*temp_tree
= tree_init(tree
->board
, tree
->root_color
, max_size
);
425 struct tree_node
*temp_node
;
426 /* Copy the best (most played) nodes first. */
427 int min_playouts
= node
->u
.playouts
;
428 int max_playouts
= min_playouts
;
430 temp_node
= tree_prune(temp_tree
, tree
, node
, min_playouts
, max_playouts
);
431 max_playouts
= min_playouts
- 1;
433 } while (max_playouts
>= 0 && temp_tree
->nodes_size
< temp_tree
->max_tree_size
);
436 fprintf(stderr
, "tree pruned, max_size %lu, pruned size %lu, min_playouts %d\n",
437 max_size
, temp_tree
->nodes_size
, max_playouts
+1);
439 /* Now copy back to original tree. */
440 tree
->nodes_size
= 0;
443 struct tree_node
*new_node
= tree_prune(tree
, temp_tree
, temp_node
, 0, temp_node
->u
.playouts
);
444 tree_done(temp_tree
);
450 tree_node_merge(struct tree_node
*dest
, struct tree_node
*src
)
452 /* Do not merge nodes that weren't touched at all. */
453 assert(dest
->pamaf
.playouts
== src
->pamaf
.playouts
);
454 assert(dest
->pu
.playouts
== src
->pu
.playouts
);
455 if (src
->amaf
.playouts
- src
->pamaf
.playouts
== 0
456 && src
->u
.playouts
- src
->pu
.playouts
== 0) {
460 dest
->hints
|= src
->hints
;
462 /* Merge the children, both are coord-sorted lists. */
463 struct tree_node
*di
= dest
->children
, **dref
= &dest
->children
;
464 struct tree_node
*si
= src
->children
, **sref
= &src
->children
;
466 if (di
->coord
!= si
->coord
) {
467 /* src has some extra items or misses di */
468 struct tree_node
*si2
= si
->sibling
;
469 while (si2
&& di
->coord
!= si2
->coord
) {
473 goto next_di
; /* src misses di, move on */
474 /* chain the extra [si,si2) items before di */
476 while (si
->sibling
!= si2
) {
485 /* Matching nodes - recurse... */
486 tree_node_merge(di
, si
);
487 /* ...and move on. */
488 sref
= &si
->sibling
; si
= si
->sibling
;
490 dref
= &di
->sibling
; di
= di
->sibling
;
493 /* Some outstanding nodes are left on src side, rechain
503 /* Priors should be constant. */
504 assert(dest
->prior
.playouts
== src
->prior
.playouts
&& dest
->prior
.value
== src
->prior
.value
);
506 stats_merge(&dest
->amaf
, &src
->amaf
);
507 stats_merge(&dest
->u
, &src
->u
);
510 /* Merge two trees built upon the same board. Note that the operation is
511 * destructive on src. */
513 tree_merge(struct tree
*dest
, struct tree
*src
)
515 /* Not suitable for fast_alloc which reorders children. */
516 assert(!dest
->nodes
);
518 if (src
->max_depth
> dest
->max_depth
)
519 dest
->max_depth
= src
->max_depth
;
520 tree_node_merge(dest
->root
, src
->root
);
525 tree_node_normalize(struct tree_node
*node
, int factor
)
527 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
528 tree_node_normalize(ni
, factor
);
530 #define normalize(s1, s2, t) node->s2.t = node->s1.t + (node->s2.t - node->s1.t) / factor;
531 normalize(pamaf
, amaf
, playouts
);
532 memcpy(&node
->pamaf
, &node
->amaf
, sizeof(node
->amaf
));
534 normalize(pu
, u
, playouts
);
535 memcpy(&node
->pu
, &node
->u
, sizeof(node
->u
));
539 /* Normalize a tree, dividing the amaf and u values by given
540 * factor; otherwise, simulations run in independent threads
541 * two trees built upon the same board. To correctly handle
542 * results taken from previous simulation run, they are backed
545 tree_normalize(struct tree
*tree
, int factor
)
547 tree_node_normalize(tree
->root
, factor
);
551 /* Tree symmetry: When possible, we will localize the tree to a single part
552 * of the board in tree_expand_node() and possibly flip along symmetry axes
553 * to another part of the board in tree_promote_at(). We follow b->symmetry
554 * guidelines here. */
557 /* This function must be thread safe, given that board b is only modified by the calling thread. */
559 tree_expand_node(struct tree
*t
, struct tree_node
*node
, struct board
*b
, enum stone color
, struct uct
*u
, int parity
)
561 /* Get a Common Fate Graph distance map from parent node. */
562 int distances
[board_size2(b
)];
563 if (!is_pass(b
->last_move
.coord
) && !is_resign(b
->last_move
.coord
)) {
564 cfg_distances(b
, node
->coord
, distances
, TREE_NODE_D_MAX
);
566 // Pass or resign - everything is too far.
567 foreach_point(b
) { distances
[c
] = TREE_NODE_D_MAX
+ 1; } foreach_point_end
;
570 /* Get a map of prior values to initialize the new nodes with. */
571 struct prior_map map
= {
574 .parity
= tree_parity(t
, parity
),
575 .distances
= distances
,
577 // Include pass in the prior map.
578 struct move_stats map_prior
[board_size2(b
) + 1]; map
.prior
= &map_prior
[1];
579 bool map_consider
[board_size2(b
) + 1]; map
.consider
= &map_consider
[1];
580 memset(map_prior
, 0, sizeof(map_prior
));
581 memset(map_consider
, 0, sizeof(map_consider
));
582 struct move pm
= { .color
= color
};
583 map
.consider
[pass
] = true;
585 if (board_at(b
, c
) != S_NONE
)
588 if (!board_is_valid_move(b
, &pm
))
590 map
.consider
[c
] = true;
592 uct_prior(u
, node
, &map
);
594 /* Now, create the nodes. */
595 struct tree_node
*ni
= tree_init_node(t
, pass
, node
->depth
+ 1);
596 /* In fast_alloc mode we might temporarily run out of nodes but
597 * this should be rare if MIN_FREE_MEM_PERCENT is set correctly. */
599 node
->is_expanded
= false;
602 struct tree_node
*first_child
= ni
;
604 ni
->prior
= map
.prior
[pass
]; ni
->d
= TREE_NODE_D_MAX
+ 1;
606 /* The loop considers only the symmetry playground. */
608 fprintf(stderr
, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
609 coord2sstr(node
->coord
, b
),
610 b
->symmetry
.x1
, b
->symmetry
.y1
,
611 b
->symmetry
.x2
, b
->symmetry
.y2
,
612 b
->symmetry
.type
, b
->symmetry
.d
);
614 for (int i
= b
->symmetry
.x1
; i
<= b
->symmetry
.x2
; i
++) {
615 for (int j
= b
->symmetry
.y1
; j
<= b
->symmetry
.y2
; j
++) {
617 int x
= b
->symmetry
.type
== SYM_DIAG_DOWN
? board_size(b
) - 1 - i
: i
;
620 fprintf(stderr
, "drop %d,%d\n", i
, j
);
625 coord_t c
= coord_xy_otf(i
, j
, t
->board
);
626 if (!map
.consider
[c
]) // Filter out invalid moves
628 assert(c
!= node
->coord
); // I have spotted "C3 C3" in some sequence...
630 struct tree_node
*nj
= tree_init_node(t
, c
, node
->depth
+ 1);
632 node
->is_expanded
= false;
635 nj
->parent
= node
; ni
->sibling
= nj
; ni
= nj
;
637 ni
->prior
= map
.prior
[c
];
638 ni
->d
= distances
[c
];
641 node
->children
= first_child
; // must be done at the end to avoid race
646 flip_coord(struct board
*b
, coord_t c
,
647 bool flip_horiz
, bool flip_vert
, int flip_diag
)
649 int x
= coord_x(c
, b
), y
= coord_y(c
, b
);
651 int z
= x
; x
= y
; y
= z
;
654 x
= board_size(b
) - 1 - x
;
657 y
= board_size(b
) - 1 - y
;
659 return coord_xy_otf(x
, y
, b
);
663 tree_fix_node_symmetry(struct board
*b
, struct tree_node
*node
,
664 bool flip_horiz
, bool flip_vert
, int flip_diag
)
666 if (!is_pass(node
->coord
))
667 node
->coord
= flip_coord(b
, node
->coord
, flip_horiz
, flip_vert
, flip_diag
);
669 for (struct tree_node
*ni
= node
->children
; ni
; ni
= ni
->sibling
)
670 tree_fix_node_symmetry(b
, ni
, flip_horiz
, flip_vert
, flip_diag
);
674 tree_fix_symmetry(struct tree
*tree
, struct board
*b
, coord_t c
)
679 struct board_symmetry
*s
= &tree
->root_symmetry
;
680 int cx
= coord_x(c
, b
), cy
= coord_y(c
, b
);
682 /* playground X->h->v->d normalization
688 bool flip_horiz
= cx
< s
->x1
|| cx
> s
->x2
;
689 bool flip_vert
= cy
< s
->y1
|| cy
> s
->y2
;
693 bool dir
= (s
->type
== SYM_DIAG_DOWN
);
694 int x
= dir
^ flip_horiz
^ flip_vert
? board_size(b
) - 1 - cx
: cx
;
695 if (flip_vert
? x
< cy
: x
> cy
) {
701 fprintf(stderr
, "%s [%d,%d -> %d,%d;%d,%d] will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
703 cx
, cy
, s
->x1
, s
->y1
, s
->x2
, s
->y2
,
704 flip_horiz
, flip_vert
, flip_diag
,
705 coord2sstr(flip_coord(b
, c
, flip_horiz
, flip_vert
, flip_diag
), b
),
706 s
->type
, s
->d
, b
->symmetry
.type
, b
->symmetry
.d
);
708 if (flip_horiz
|| flip_vert
|| flip_diag
)
709 tree_fix_node_symmetry(b
, tree
->root
, flip_horiz
, flip_vert
, flip_diag
);
714 tree_unlink_node(struct tree_node
*node
)
716 struct tree_node
*ni
= node
->parent
;
717 if (ni
->children
== node
) {
718 ni
->children
= node
->sibling
;
721 while (ni
->sibling
!= node
)
723 ni
->sibling
= node
->sibling
;
725 node
->sibling
= NULL
;
729 /* Promotes the given node as the root of the tree. In the fast_alloc
730 * mode, the node may be moved and some of its subtree may be pruned. */
732 tree_promote_node(struct tree
*tree
, struct tree_node
**node
)
734 assert((*node
)->parent
== tree
->root
);
735 tree_unlink_node(*node
);
737 /* Freeing the rest of the tree can take several seconds on large
738 * trees, so we must do it asynchronously: */
739 tree_done_node_detached(tree
, tree
->root
);
741 unsigned long min_free_size
= (MIN_FREE_MEM_PERCENT
* tree
->max_tree_size
) / 100;
742 if (tree
->nodes_size
>= tree
->max_tree_size
- min_free_size
)
743 *node
= tree_garbage_collect(tree
, min_free_size
, *node
);
744 /* If we still have enough free memory, we will free everything later. */
747 tree
->root_color
= stone_other(tree
->root_color
);
748 board_symmetry_update(tree
->board
, &tree
->root_symmetry
, (*node
)->coord
);
749 /* If the tree deepest node was under node, or if we called tree_garbage_collect,
750 * tree->max_depth is correct. Otherwise we could traverse the tree
751 * to recompute max_depth but it's not worth it: it's just for debugging
752 * and soon the tree will grow and max_depth will become correct again. */
753 if (tree
->chchvals
) { free(tree
->chchvals
); tree
->chchvals
= NULL
; }
754 if (tree
->chvals
) { free(tree
->chvals
); tree
->chvals
= NULL
; }
758 tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
)
760 tree_fix_symmetry(tree
, b
, c
);
762 for (struct tree_node
*ni
= tree
->root
->children
; ni
; ni
= ni
->sibling
) {
763 if (ni
->coord
== c
) {
764 tree_promote_node(tree
, &ni
);