src/tree.c

   1 /* Copyright (c) 2012, Bastien Dejean
   2  * All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  * 1. Redistributions of source code must retain the above copyright notice, this
   8  *    list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright notice,
  10  *    this list of conditions and the following disclaimer in the documentation
  11  *    and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  16  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  17  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  20  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <stdbool.h>
  28 #include <limits.h>
  29 #include "bspwm.h"
  30 #include "desktop.h"
  31 #include "ewmh.h"
  32 #include "history.h"
  33 #include "monitor.h"
  34 #include "query.h"
  35 #include "geometry.h"
  36 #include "subscribe.h"
  37 #include "settings.h"
  38 #include "pointer.h"
  39 #include "stack.h"
  40 #include "window.h"
  41 #include "tree.h"
  42
  43 void arrange(monitor_t *m, desktop_t *d)
  44 {
  45         if (d->root == NULL) {
  46                 return;
  47         }
  48
  49         xcb_rectangle_t rect = m->rectangle;
  50
  51         rect.x += m->padding.left + d->padding.left;
  52         rect.y += m->padding.top + d->padding.top;
  53         rect.width -= m->padding.left + d->padding.left + d->padding.right + m->padding.right;
  54         rect.height -= m->padding.top + d->padding.top + d->padding.bottom + m->padding.bottom;
  55
  56         if (d->layout == LAYOUT_MONOCLE) {
  57                 rect.x += monocle_padding.left;
  58                 rect.y += monocle_padding.top;
  59                 rect.width -= monocle_padding.left + monocle_padding.right;
  60                 rect.height -= monocle_padding.top + monocle_padding.bottom;
  61         }
  62
  63         if (!gapless_monocle || d->layout != LAYOUT_MONOCLE) {
  64                 rect.x += d->window_gap;
  65                 rect.y += d->window_gap;
  66                 rect.width -= d->window_gap;
  67                 rect.height -= d->window_gap;
  68         }
  69
  70         apply_layout(m, d, d->root, rect, rect);
  71 }
  72
  73 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
  74 {
  75         if (n == NULL) {
  76                 return;
  77         }
  78
  79         n->rectangle = rect;
  80
  81         if (n->presel != NULL) {
  82                 draw_presel_feedback(m, d, n);
  83         }
  84
  85         if (is_leaf(n)) {
  86
  87                 if (n->client == NULL) {
  88                         return;
  89                 }
  90
  91                 unsigned int bw;
  92                 bool the_only_window = !m->prev && !m->next && d->root->client;
  93                 if ((borderless_monocle && d->layout == LAYOUT_MONOCLE && IS_TILED(n->client))
  94                     || (borderless_singleton && the_only_window)
  95                     || n->client->state == STATE_FULLSCREEN) {
  96                         bw = 0;
  97                 } else {
  98                         bw = n->client->border_width;
  99                 }
 100
 101                 xcb_rectangle_t r;
 102                 xcb_rectangle_t cr = get_window_rectangle(n);
 103                 client_state_t s = n->client->state;
 104                 /* tiled and pseudo-tiled clients */
 105                 if (s == STATE_TILED || s == STATE_PSEUDO_TILED) {
 106                         int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap);
 107                         r = rect;
 108                         int bleed = wg + 2 * bw;
 109                         r.width = (bleed < r.width ? r.width - bleed : 1);
 110                         r.height = (bleed < r.height ? r.height - bleed : 1);
 111                         /* pseudo-tiled clients */
 112                         if (s == STATE_PSEUDO_TILED) {
 113                                 xcb_rectangle_t f = n->client->floating_rectangle;
 114                                 r.width = MIN(r.width, f.width);
 115                                 r.height = MIN(r.height, f.height);
 116                                 if (center_pseudo_tiled) {
 117                                         r.x = rect.x - bw + (rect.width - wg - r.width) / 2;
 118                                         r.y = rect.y - bw + (rect.height - wg - r.height) / 2;
 119                                 }
 120                         }
 121                         n->client->tiled_rectangle = r;
 122                 /* floating clients */
 123                 } else if (s == STATE_FLOATING) {
 124                         r = n->client->floating_rectangle;
 125                 /* fullscreen clients */
 126                 } else {
 127                         r = m->rectangle;
 128                         n->client->tiled_rectangle = r;
 129                 }
 130
 131                 apply_size_hints(n->client, &r.width, &r.height);
 132
 133                 if (!rect_eq(r, cr)) {
 134                         window_move_resize(n->id, r.x, r.y, r.width, r.height);
 135                         if (!grabbing) {
 136                                 put_status(SBSC_MASK_NODE_GEOMETRY, "node_geometry 0x%08X 0x%08X 0x%08X %ux%u+%i+%i\n", m->id, d->id, n->id, r.width, r.height, r.x, r.y);
 137                         }
 138                 }
 139
 140                 window_border_width(n->id, bw);
 141
 142         } else {
 143                 xcb_rectangle_t first_rect;
 144                 xcb_rectangle_t second_rect;
 145
 146                 if (d->layout == LAYOUT_MONOCLE || n->first_child->vacant || n->second_child->vacant) {
 147                         first_rect = second_rect = rect;
 148                 } else {
 149                         unsigned int fence;
 150                         if (n->split_type == TYPE_VERTICAL) {
 151                                 fence = rect.width * n->split_ratio;
 152                                 if ((n->first_child->constraints.min_width + n->second_child->constraints.min_width) <= rect.width) {
 153                                         if (fence < n->first_child->constraints.min_width) {
 154                                                 fence = n->first_child->constraints.min_width;
 155                                                 n->split_ratio = (double) fence / (double) rect.width;
 156                                         } else if (fence > (uint16_t) (rect.width - n->second_child->constraints.min_width)) {
 157                                                 fence = (rect.width - n->second_child->constraints.min_width);
 158                                                 n->split_ratio = (double) fence / (double) rect.width;
 159                                         }
 160                                 }
 161                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 162                                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 163                         } else {
 164                                 fence = rect.height * n->split_ratio;
 165                                 if ((n->first_child->constraints.min_height + n->second_child->constraints.min_height) <= rect.height) {
 166                                         if (fence < n->first_child->constraints.min_height) {
 167                                                 fence = n->first_child->constraints.min_height;
 168                                                 n->split_ratio = (double) fence / (double) rect.height;
 169                                         } else if (fence > (uint16_t) (rect.height - n->second_child->constraints.min_height)) {
 170                                                 fence = (rect.height - n->second_child->constraints.min_height);
 171                                                 n->split_ratio = (double) fence / (double) rect.height;
 172                                         }
 173                                 }
 174                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 175                                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 176                         }
 177                 }
 178
 179                 apply_layout(m, d, n->first_child, first_rect, root_rect);
 180                 apply_layout(m, d, n->second_child, second_rect, root_rect);
 181         }
 182 }
 183
 184 presel_t *make_presel(void)
 185 {
 186         presel_t *p = calloc(1, sizeof(presel_t));
 187         p->split_dir = DIR_EAST;
 188         p->split_ratio = split_ratio;
 189         p->feedback = XCB_NONE;
 190         return p;
 191 }
 192
 193 void set_ratio(node_t *n, double rat)
 194 {
 195         if (n == NULL) {
 196                 return;
 197         }
 198
 199         n->split_ratio = rat;
 200 }
 201
 202 void presel_dir(monitor_t *m, desktop_t *d, node_t *n, direction_t dir)
 203 {
 204         if (n->presel == NULL) {
 205                 n->presel = make_presel();
 206         }
 207
 208         n->presel->split_dir = dir;
 209
 210         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X dir %s\n", m->id, d->id, n->id, SPLIT_DIR_STR(dir));
 211 }
 212
 213 void presel_ratio(monitor_t *m, desktop_t *d, node_t *n, double ratio)
 214 {
 215         if (n->presel == NULL) {
 216                 n->presel = make_presel();
 217         }
 218
 219         n->presel->split_ratio = ratio;
 220
 221         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X ratio %lf\n", m->id, d->id, n->id, ratio);
 222 }
 223
 224 void cancel_presel(monitor_t *m, desktop_t *d, node_t *n)
 225 {
 226         if (n->presel == NULL) {
 227                 return;
 228         }
 229
 230         if (n->presel->feedback != XCB_NONE) {
 231                 xcb_destroy_window(dpy, n->presel->feedback);
 232         }
 233
 234         free(n->presel);
 235         n->presel = NULL;
 236
 237         put_status(SBSC_MASK_NODE_PRESEL, "node_presel 0x%08X 0x%08X 0x%08X cancel\n", m->id, d->id, n->id);
 238 }
 239
 240 void cancel_presel_in(monitor_t *m, desktop_t *d, node_t *n)
 241 {
 242         if (n == NULL) {
 243                 return;
 244         }
 245         cancel_presel(m, d, n);
 246         cancel_presel_in(m, d, n->first_child);
 247         cancel_presel_in(m, d, n->second_child);
 248 }
 249
 250 node_t *find_public(desktop_t *d)
 251 {
 252         unsigned int b_manual_area = 0;
 253         unsigned int b_automatic_area = 0;
 254         node_t *b_manual = NULL;
 255         node_t *b_automatic = NULL;
 256         for (node_t *n = first_extrema(d->root); n != NULL; n = next_leaf(n, d->root)) {
 257                 if (n->vacant) {
 258                         continue;
 259                 }
 260                 unsigned int n_area = node_area(d, n);
 261                 if (n_area > b_manual_area && (n->presel != NULL || !n->private)) {
 262                         b_manual = n;
 263                         b_manual_area = n_area;
 264                 }
 265                 if (n_area > b_automatic_area &&
 266                     n->presel == NULL && !n->private && private_count(n->parent) == 0) {
 267                         b_automatic = n;
 268                         b_automatic_area = n_area;
 269                 }
 270         }
 271         if (b_automatic != NULL) {
 272                 return b_automatic;
 273         } else {
 274                 return b_manual;
 275         }
 276 }
 277
 278 node_t *insert_node(monitor_t *m, desktop_t *d, node_t *n, node_t *f)
 279 {
 280         if (d == NULL || n == NULL) {
 281                 return NULL;
 282         }
 283
 284         /* n: inserted node */
 285         /* c: new internal node */
 286         /* f: focus or insertion anchor */
 287         /* p: parent of focus */
 288         /* g: grand parent of focus */
 289
 290         if (f == NULL) {
 291                 f = d->root;
 292         }
 293
 294         if (f == NULL) {
 295                 d->root = n;
 296         } else if (IS_RECEPTACLE(f) && f->presel == NULL) {
 297                 node_t *p = f->parent;
 298                 if (p != NULL) {
 299                         if (is_first_child(f)) {
 300                                 p->first_child = n;
 301                         } else {
 302                                 p->second_child = n;
 303                         }
 304                 } else {
 305                         d->root = n;
 306                 }
 307                 n->parent = p;
 308                 free(f);
 309                 f = NULL;
 310         } else {
 311                 node_t *c = make_node(XCB_NONE);
 312                 node_t *p = f->parent;
 313                 if (f->presel == NULL && (f->private || private_count(f->parent) > 0)) {
 314                         node_t *k = find_public(d);
 315                         if (k != NULL) {
 316                                 f = k;
 317                                 p = f->parent;
 318                         }
 319                         if (f->presel == NULL && (f->private || private_count(f->parent) > 0)) {
 320                                 xcb_rectangle_t rect = get_rectangle(m, d, f);
 321                                 presel_dir(m, d, f, (rect.width >= rect.height ? DIR_EAST : DIR_SOUTH));
 322                         }
 323                 }
 324                 n->parent = c;
 325                 if (f->presel == NULL) {
 326                         bool single_tiled = f->client != NULL && IS_TILED(f->client) && tiled_count(d->root, true) == 1;
 327                         if (p == NULL || automatic_scheme != SCHEME_SPIRAL || single_tiled) {
 328                                 if (p != NULL) {
 329                                         if (is_first_child(f)) {
 330                                                 p->first_child = c;
 331                                         } else {
 332                                                 p->second_child = c;
 333                                         }
 334                                 } else {
 335                                         d->root = c;
 336                                 }
 337                                 c->parent = p;
 338                                 f->parent = c;
 339                                 if (initial_polarity == FIRST_CHILD) {
 340                                         c->first_child = n;
 341                                         c->second_child = f;
 342                                 } else {
 343                                         c->first_child = f;
 344                                         c->second_child = n;
 345                                 }
 346                                 if (p == NULL || automatic_scheme == SCHEME_LONGEST_SIDE || single_tiled) {
 347                                         if (f->rectangle.width > f->rectangle.height) {
 348                                                 c->split_type = TYPE_VERTICAL;
 349                                         } else {
 350                                                 c->split_type = TYPE_HORIZONTAL;
 351                                         }
 352                                 } else {
 353                                         node_t *q = p;
 354                                         while (q != NULL && (q->first_child->vacant || q->second_child->vacant)) {
 355                                                 q = q->parent;
 356                                         }
 357                                         if (q == NULL) {
 358                                                 q = p;
 359                                         }
 360                                         if (q->split_type == TYPE_HORIZONTAL) {
 361                                                 c->split_type = TYPE_VERTICAL;
 362                                         } else {
 363                                                 c->split_type = TYPE_HORIZONTAL;
 364                                         }
 365                                 }
 366                         } else {
 367                                 node_t *g = p->parent;
 368                                 c->parent = g;
 369                                 if (g != NULL) {
 370                                         if (is_first_child(p)) {
 371                                                 g->first_child = c;
 372                                         } else {
 373                                                 g->second_child = c;
 374                                         }
 375                                 } else {
 376                                         d->root = c;
 377                                 }
 378                                 c->split_type = p->split_type;
 379                                 c->split_ratio = p->split_ratio;
 380                                 p->parent = c;
 381                                 int rot;
 382                                 if (is_first_child(f)) {
 383                                         c->first_child = n;
 384                                         c->second_child = p;
 385                                         rot = 90;
 386                                 } else {
 387                                         c->first_child = p;
 388                                         c->second_child = n;
 389                                         rot = 270;
 390                                 }
 391                                 if (!n->vacant) {
 392                                         rotate_tree(p, rot);
 393                                 }
 394                         }
 395                 } else {
 396                         if (p != NULL) {
 397                                 if (is_first_child(f)) {
 398                                         p->first_child = c;
 399                                 } else {
 400                                         p->second_child = c;
 401                                 }
 402                         }
 403                         c->split_ratio = f->presel->split_ratio;
 404                         c->parent = p;
 405                         f->parent = c;
 406                         switch (f->presel->split_dir) {
 407                                 case DIR_WEST:
 408                                         c->split_type = TYPE_VERTICAL;
 409                                         c->first_child = n;
 410                                         c->second_child = f;
 411                                         break;
 412                                 case DIR_EAST:
 413                                         c->split_type = TYPE_VERTICAL;
 414                                         c->first_child = f;
 415                                         c->second_child = n;
 416                                         break;
 417                                 case DIR_NORTH:
 418                                         c->split_type = TYPE_HORIZONTAL;
 419                                         c->first_child = n;
 420                                         c->second_child = f;
 421                                         break;
 422                                 case DIR_SOUTH:
 423                                         c->split_type = TYPE_HORIZONTAL;
 424                                         c->first_child = f;
 425                                         c->second_child = n;
 426                                         break;
 427                         }
 428                         if (d->root == f) {
 429                                 d->root = c;
 430                         }
 431                         cancel_presel(m, d, f);
 432                         set_marked(m, d, n, false);
 433                 }
 434         }
 435
 436         propagate_flags_upward(m, d, n);
 437
 438         if (d->focus == NULL && is_focusable(n)) {
 439                 d->focus = n;
 440         }
 441
 442         return f;
 443 }
 444
 445 void insert_receptacle(monitor_t *m, desktop_t *d, node_t *n)
 446 {
 447         node_t *r = make_node(XCB_NONE);
 448         insert_node(m, d, r, n);
 449         put_status(SBSC_MASK_NODE_ADD, "node_add 0x%08X 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id, r->id);
 450
 451         if (single_monocle && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
 452                 set_layout(m, d, d->user_layout, false);
 453         }
 454 }
 455
 456 bool activate_node(monitor_t *m, desktop_t *d, node_t *n)
 457 {
 458         if (n == NULL && d->root != NULL) {
 459                 n = d->focus;
 460                 if (n == NULL) {
 461                         n = history_last_node(d, NULL);
 462                 }
 463                 if (n == NULL) {
 464                         n = first_focusable_leaf(d->root);
 465                 }
 466         }
 467
 468         if (d == mon->desk || (n != NULL && !is_focusable(n))) {
 469                 return false;
 470         }
 471
 472         if (n != NULL) {
 473                 if (d->focus != NULL && n != d->focus) {
 474                         neutralize_occluding_windows(m, d, n);
 475                 }
 476                 stack(d, n, true);
 477                 if (d->focus != n) {
 478                         for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 479                                 if (f->client != NULL && !is_descendant(f, n)) {
 480                                         window_draw_border(f->id, get_border_color(false, (m == mon)));
 481                                 }
 482                         }
 483                 }
 484                 draw_border(n, true, (m == mon));
 485         }
 486
 487         d->focus = n;
 488         history_add(m, d, n, false);
 489
 490         put_status(SBSC_MASK_REPORT);
 491
 492         if (n == NULL) {
 493                 return true;
 494         }
 495
 496         put_status(SBSC_MASK_NODE_ACTIVATE, "node_activate 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 497
 498         return true;
 499 }
 500
 501 void transfer_sticky_nodes(monitor_t *ms, desktop_t *ds, monitor_t *md, desktop_t *dd, node_t *n)
 502 {
 503         if (n == NULL) {
 504                 return;
 505         } else if (n->sticky) {
 506                 sticky_still = false;
 507                 transfer_node(ms, ds, n, md, dd, dd->focus, false);
 508                 sticky_still = true;
 509         } else {
 510                 /* we need references to the children because n might be freed after
 511                  * the first recursive call */
 512                 node_t *first_child = n->first_child;
 513                 node_t *second_child = n->second_child;
 514                 transfer_sticky_nodes(ms, ds, md, dd, first_child);
 515                 transfer_sticky_nodes(ms, ds, md, dd, second_child);
 516         }
 517 }
 518
 519 bool focus_node(monitor_t *m, desktop_t *d, node_t *n)
 520 {
 521         if (m == NULL) {
 522                 m = mon;
 523                 if (m == NULL) {
 524                         m = history_last_monitor(NULL);
 525                 }
 526                 if (m == NULL) {
 527                         m = mon_head;
 528                 }
 529         }
 530
 531         if (m == NULL) {
 532                 return false;
 533         }
 534
 535         if (d == NULL) {
 536                 d = m->desk;
 537                 if (d == NULL) {
 538                         d = history_last_desktop(m, NULL);
 539                 }
 540                 if (d == NULL) {
 541                         d = m->desk_head;
 542                 }
 543         }
 544
 545         if (d == NULL) {
 546                 return false;
 547         }
 548
 549         bool guess = (n == NULL);
 550
 551         if (n == NULL && d->root != NULL) {
 552                 n = d->focus;
 553                 if (n == NULL) {
 554                         n = history_last_node(d, NULL);
 555                 }
 556                 if (n == NULL) {
 557                         n = first_focusable_leaf(d->root);
 558                 }
 559         }
 560
 561         if (n != NULL && !is_focusable(n)) {
 562                 return false;
 563         }
 564
 565         if ((mon != NULL && mon->desk != d) || n == NULL || n->client == NULL) {
 566                 clear_input_focus();
 567         }
 568
 569         if (m->sticky_count > 0 && m->desk != NULL && d != m->desk) {
 570                 if (guess && m->desk->focus != NULL && m->desk->focus->sticky) {
 571                         n = m->desk->focus;
 572                 }
 573
 574                 transfer_sticky_nodes(m, m->desk, m, d, m->desk->root);
 575
 576                 if (n == NULL && d->focus != NULL) {
 577                         n = d->focus;
 578                 }
 579         }
 580
 581         if (d->focus != NULL && n != d->focus) {
 582                 neutralize_occluding_windows(m, d, n);
 583         }
 584
 585         if (n != NULL && n->client != NULL && n->client->urgent) {
 586                 set_urgent(m, d, n, false);
 587         }
 588
 589         if (mon != m) {
 590                 if (mon != NULL) {
 591                         for (desktop_t *e = mon->desk_head; e != NULL; e = e->next) {
 592                                 draw_border(e->focus, true, false);
 593                         }
 594                 }
 595                 for (desktop_t *e = m->desk_head; e != NULL; e = e->next) {
 596                         if (e == d) {
 597                                 continue;
 598                         }
 599                         draw_border(e->focus, true, true);
 600                 }
 601         }
 602
 603         if (d->focus != n) {
 604                 for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 605                         if (f->client != NULL && !is_descendant(f, n)) {
 606                                 window_draw_border(f->id, get_border_color(false, true));
 607                         }
 608                 }
 609         }
 610
 611         draw_border(n, true, true);
 612
 613         bool desk_changed = (m != mon || m->desk != d);
 614         bool has_input_focus = false;
 615
 616         if (mon != m) {
 617                 mon = m;
 618
 619                 if (pointer_follows_monitor) {
 620                         center_pointer(m->rectangle);
 621                 }
 622
 623                 put_status(SBSC_MASK_MONITOR_FOCUS, "monitor_focus 0x%08X\n", m->id);
 624         }
 625
 626         if (m->desk != d) {
 627                 show_desktop(d);
 628                 set_input_focus(n);
 629                 has_input_focus = true;
 630                 hide_desktop(m->desk);
 631                 m->desk = d;
 632         }
 633
 634         if (desk_changed) {
 635                 ewmh_update_current_desktop();
 636                 put_status(SBSC_MASK_DESKTOP_FOCUS, "desktop_focus 0x%08X 0x%08X\n", m->id, d->id);
 637         }
 638
 639         d->focus = n;
 640         if (!has_input_focus) {
 641                 set_input_focus(n);
 642         }
 643         ewmh_update_active_window();
 644         history_add(m, d, n, true);
 645
 646         put_status(SBSC_MASK_REPORT);
 647
 648         if (n == NULL) {
 649                 if (focus_follows_pointer) {
 650                         update_motion_recorder();
 651                 }
 652                 return true;
 653         }
 654
 655         put_status(SBSC_MASK_NODE_FOCUS, "node_focus 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 656
 657         stack(d, n, true);
 658
 659         if (pointer_follows_focus) {
 660                 center_pointer(get_rectangle(m, d, n));
 661         } else if (focus_follows_pointer) {
 662                 update_motion_recorder();
 663         }
 664
 665         return true;
 666 }
 667
 668 void hide_node(desktop_t *d, node_t *n)
 669 {
 670         if (n == NULL || (!hide_sticky && n->sticky)) {
 671                 return;
 672         } else {
 673                 if (!n->hidden) {
 674                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 675                                 window_hide(n->presel->feedback);
 676                         }
 677                         if (n->client != NULL) {
 678                                 window_hide(n->id);
 679                         }
 680                 }
 681                 if (n->client != NULL) {
 682                         n->client->shown = false;
 683                 }
 684                 hide_node(d, n->first_child);
 685                 hide_node(d, n->second_child);
 686         }
 687 }
 688
 689 void show_node(desktop_t *d, node_t *n)
 690 {
 691         if (n == NULL) {
 692                 return;
 693         } else {
 694                 if (!n->hidden) {
 695                         if (n->client != NULL) {
 696                                 window_show(n->id);
 697                         }
 698                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 699                                 window_show(n->presel->feedback);
 700                         }
 701                 }
 702                 if (n->client != NULL) {
 703                         n->client->shown = true;
 704                 }
 705                 show_node(d, n->first_child);
 706                 show_node(d, n->second_child);
 707         }
 708 }
 709
 710 node_t *make_node(uint32_t id)
 711 {
 712         if (id == XCB_NONE) {
 713                 id = xcb_generate_id(dpy);
 714         }
 715         node_t *n = calloc(1, sizeof(node_t));
 716         n->id = id;
 717         n->parent = n->first_child = n->second_child = NULL;
 718         n->vacant = n->hidden = n->sticky = n->private = n->locked = n->marked = false;
 719         n->split_ratio = split_ratio;
 720         n->split_type = TYPE_VERTICAL;
 721         n->constraints = (constraints_t) {MIN_WIDTH, MIN_HEIGHT};
 722         n->presel = NULL;
 723         n->client = NULL;
 724         return n;
 725 }
 726
 727 client_t *make_client(void)
 728 {
 729         client_t *c = calloc(1, sizeof(client_t));
 730         c->state = c->last_state = STATE_TILED;
 731         c->layer = c->last_layer = LAYER_NORMAL;
 732         snprintf(c->class_name, sizeof(c->class_name), "%s", MISSING_VALUE);
 733         snprintf(c->instance_name, sizeof(c->instance_name), "%s", MISSING_VALUE);
 734         c->border_width = border_width;
 735         c->urgent = false;
 736         c->shown = false;
 737         c->wm_flags = 0;
 738         c->icccm_props.input_hint = true;
 739         c->icccm_props.take_focus = false;
 740         c->icccm_props.delete_window = false;
 741         c->size_hints.flags = 0;
 742         return c;
 743 }
 744
 745 void initialize_client(node_t *n)
 746 {
 747         xcb_window_t win = n->id;
 748         client_t *c = n->client;
 749         xcb_icccm_get_wm_protocols_reply_t protos;
 750         if (xcb_icccm_get_wm_protocols_reply(dpy, xcb_icccm_get_wm_protocols(dpy, win, ewmh->WM_PROTOCOLS), &protos, NULL) == 1) {
 751                 for (uint32_t i = 0; i < protos.atoms_len; i++) {
 752                         if (protos.atoms[i] == WM_TAKE_FOCUS) {
 753                                 c->icccm_props.take_focus = true;
 754                         } else if (protos.atoms[i] == WM_DELETE_WINDOW) {
 755                                 c->icccm_props.delete_window = true;
 756                         }
 757                 }
 758                 xcb_icccm_get_wm_protocols_reply_wipe(&protos);
 759         }
 760         xcb_ewmh_get_atoms_reply_t wm_state;
 761         if (xcb_ewmh_get_wm_state_reply(ewmh, xcb_ewmh_get_wm_state(ewmh, win), &wm_state, NULL) == 1) {
 762                 for (unsigned int i = 0; i < wm_state.atoms_len && i < MAX_WM_STATES; i++) {
 763 #define HANDLE_WM_STATE(s) \
 764                         if (wm_state.atoms[i] == ewmh->_NET_WM_STATE_##s) { \
 765                                 c->wm_flags |= WM_FLAG_##s; continue; \
 766                         }
 767                         HANDLE_WM_STATE(MODAL)
 768                         HANDLE_WM_STATE(STICKY)
 769                         HANDLE_WM_STATE(MAXIMIZED_VERT)
 770                         HANDLE_WM_STATE(MAXIMIZED_HORZ)
 771                         HANDLE_WM_STATE(SHADED)
 772                         HANDLE_WM_STATE(SKIP_TASKBAR)
 773                         HANDLE_WM_STATE(SKIP_PAGER)
 774                         HANDLE_WM_STATE(HIDDEN)
 775                         HANDLE_WM_STATE(FULLSCREEN)
 776                         HANDLE_WM_STATE(ABOVE)
 777                         HANDLE_WM_STATE(BELOW)
 778                         HANDLE_WM_STATE(DEMANDS_ATTENTION)
 779 #undef HANDLE_WM_STATE
 780                 }
 781                 xcb_ewmh_get_atoms_reply_wipe(&wm_state);
 782         }
 783         xcb_icccm_wm_hints_t hints;
 784         if (xcb_icccm_get_wm_hints_reply(dpy, xcb_icccm_get_wm_hints(dpy, win), &hints, NULL) == 1
 785                 && (hints.flags & XCB_ICCCM_WM_HINT_INPUT)) {
 786                 c->icccm_props.input_hint = hints.input;
 787         }
 788         xcb_icccm_get_wm_normal_hints_reply(dpy, xcb_icccm_get_wm_normal_hints(dpy, win), &c->size_hints, NULL);
 789 }
 790
 791 bool is_focusable(node_t *n)
 792 {
 793         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 794                 if (f->client != NULL && !f->hidden) {
 795                         return true;
 796                 }
 797         }
 798         return false;
 799 }
 800
 801 bool is_leaf(node_t *n)
 802 {
 803         return (n != NULL && n->first_child == NULL && n->second_child == NULL);
 804 }
 805
 806 bool is_first_child(node_t *n)
 807 {
 808         return (n != NULL && n->parent != NULL && n->parent->first_child == n);
 809 }
 810
 811 bool is_second_child(node_t *n)
 812 {
 813         return (n != NULL && n->parent != NULL && n->parent->second_child == n);
 814 }
 815
 816 unsigned int clients_count_in(node_t *n)
 817 {
 818         if (n == NULL) {
 819                 return 0;
 820         } else {
 821                 return (n->client != NULL ? 1 : 0) +
 822                         clients_count_in(n->first_child) +
 823                         clients_count_in(n->second_child);
 824         }
 825 }
 826
 827 node_t *brother_tree(node_t *n)
 828 {
 829         if (n == NULL || n->parent == NULL) {
 830                 return NULL;
 831         }
 832         if (is_first_child(n)) {
 833                 return n->parent->second_child;
 834         } else {
 835                 return n->parent->first_child;
 836         }
 837 }
 838
 839 node_t *first_extrema(node_t *n)
 840 {
 841         if (n == NULL) {
 842                 return NULL;
 843         } else if (n->first_child == NULL) {
 844                 return n;
 845         } else {
 846                 return first_extrema(n->first_child);
 847         }
 848 }
 849
 850 node_t *second_extrema(node_t *n)
 851 {
 852         if (n == NULL) {
 853                 return NULL;
 854         } else if (n->second_child == NULL) {
 855                 return n;
 856         } else {
 857                 return second_extrema(n->second_child);
 858         }
 859 }
 860
 861 node_t *first_focusable_leaf(node_t *n)
 862 {
 863         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 864                 if (f->client != NULL && !f->hidden) {
 865                         return f;
 866                 }
 867         }
 868         return NULL;
 869 }
 870
 871 node_t *next_node(node_t *n)
 872 {
 873         if (n == NULL) {
 874                 return NULL;
 875         }
 876
 877         if (n->second_child != NULL) {
 878                 return first_extrema(n->second_child);
 879         } else {
 880                 node_t *p = n;
 881                 while (is_second_child(p)) {
 882                         p = p->parent;
 883                 }
 884                 if (is_first_child(p)) {
 885                         return p->parent;
 886                 } else {
 887                         return NULL;
 888                 }
 889         }
 890 }
 891
 892 node_t *prev_node(node_t *n)
 893 {
 894         if (n == NULL) {
 895                 return NULL;
 896         }
 897
 898         if (n->first_child != NULL) {
 899                 return second_extrema(n->first_child);
 900         } else {
 901                 node_t *p = n;
 902                 while (is_first_child(p)) {
 903                         p = p->parent;
 904                 }
 905                 if (is_second_child(p)) {
 906                         return p->parent;
 907                 } else {
 908                         return NULL;
 909                 }
 910         }
 911 }
 912
 913 node_t *next_leaf(node_t *n, node_t *r)
 914 {
 915         if (n == NULL) {
 916                 return NULL;
 917         }
 918         node_t *p = n;
 919         while (is_second_child(p) && p != r) {
 920                 p = p->parent;
 921         }
 922         if (p == r) {
 923                 return NULL;
 924         }
 925         return first_extrema(p->parent->second_child);
 926 }
 927
 928 node_t *prev_leaf(node_t *n, node_t *r)
 929 {
 930         if (n == NULL) {
 931                 return NULL;
 932         }
 933         node_t *p = n;
 934         while (is_first_child(p) && p != r) {
 935                 p = p->parent;
 936         }
 937         if (p == r) {
 938                 return NULL;
 939         }
 940         return second_extrema(p->parent->first_child);
 941 }
 942
 943 node_t *next_tiled_leaf(node_t *n, node_t *r)
 944 {
 945         node_t *next = next_leaf(n, r);
 946         if (next == NULL || (next->client != NULL && !next->vacant)) {
 947                 return next;
 948         } else {
 949                 return next_tiled_leaf(next, r);
 950         }
 951 }
 952
 953 node_t *prev_tiled_leaf(node_t *n, node_t *r)
 954 {
 955         node_t *prev = prev_leaf(n, r);
 956         if (prev == NULL || (prev->client != NULL && !prev->vacant)) {
 957                 return prev;
 958         } else {
 959                 return prev_tiled_leaf(prev, r);
 960         }
 961 }
 962
 963 /* Returns true if *b* is adjacent to *a* in the direction *dir* */
 964 bool is_adjacent(node_t *a, node_t *b, direction_t dir)
 965 {
 966         switch (dir) {
 967                 case DIR_EAST:
 968                         return (a->rectangle.x + a->rectangle.width) == b->rectangle.x;
 969                         break;
 970                 case DIR_SOUTH:
 971                         return (a->rectangle.y + a->rectangle.height) == b->rectangle.y;
 972                         break;
 973                 case DIR_WEST:
 974                         return (b->rectangle.x + b->rectangle.width) == a->rectangle.x;
 975                         break;
 976                 case DIR_NORTH:
 977                         return (b->rectangle.y + b->rectangle.height) == a->rectangle.y;
 978                         break;
 979         }
 980         return false;
 981 }
 982
 983 node_t *find_fence(node_t *n, direction_t dir)
 984 {
 985         node_t *p;
 986
 987         if (n == NULL) {
 988                 return NULL;
 989         }
 990
 991         p = n->parent;
 992
 993         while (p != NULL) {
 994                 if ((dir == DIR_NORTH && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y) ||
 995                     (dir == DIR_WEST && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x) ||
 996                     (dir == DIR_SOUTH && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height)) ||
 997                     (dir == DIR_EAST && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 998                         return p;
 999                 p = p->parent;
1000         }
1001
1002         return NULL;
1003 }
1004
1005 /* returns *true* if *a* is a child of *b* */
1006 bool is_child(node_t *a, node_t *b)
1007 {
1008         if (a == NULL || b == NULL) {
1009                 return false;
1010         }
1011         return (a->parent != NULL && a->parent == b);
1012 }
1013
1014 /* returns *true* if *a* is a descendant of *b* */
1015 bool is_descendant(node_t *a, node_t *b)
1016 {
1017         if (a == NULL || b == NULL) {
1018                 return false;
1019         }
1020         while (a != b && a != NULL) {
1021                 a = a->parent;
1022         }
1023         return a == b;
1024 }
1025
1026 bool find_by_id(uint32_t id, coordinates_t *loc)
1027 {
1028         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1029                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1030                         node_t *n = find_by_id_in(d->root, id);
1031                         if (n != NULL) {
1032                                 loc->monitor = m;
1033                                 loc->desktop = d;
1034                                 loc->node = n;
1035                                 return true;
1036                         }
1037                 }
1038         }
1039         return false;
1040 }
1041
1042 node_t *find_by_id_in(node_t *r, uint32_t id)
1043 {
1044         if (r == NULL) {
1045                 return NULL;
1046         } else if (r->id == id) {
1047                 return r;
1048         } else {
1049                 node_t *f = find_by_id_in(r->first_child, id);
1050                 if (f != NULL) {
1051                         return f;
1052                 } else {
1053                         return find_by_id_in(r->second_child, id);
1054                 }
1055         }
1056 }
1057
1058 void find_any_node(coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1059 {
1060         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1061                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1062                         if (find_any_node_in(m, d, d->root, ref, dst, sel)) {
1063                                 return;
1064                         }
1065                 }
1066         }
1067 }
1068
1069 bool find_any_node_in(monitor_t *m, desktop_t *d, node_t *n, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1070 {
1071         if (n == NULL) {
1072                 return false;
1073         } else {
1074                 coordinates_t loc = {m, d, n};
1075                 if (node_matches(&loc, ref, sel)) {
1076                         *dst = loc;
1077                         return true;
1078                 } else {
1079                         if (find_any_node_in(m, d, n->first_child, ref, dst, sel)) {
1080                                 return true;
1081                         } else {
1082                                 return find_any_node_in(m, d, n->second_child, ref, dst, sel);
1083                         }
1084                 }
1085         }
1086 }
1087
1088 void find_first_ancestor(coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1089 {
1090         if (ref->node == NULL) {
1091                 return;
1092         }
1093
1094         coordinates_t loc = {ref->monitor, ref->desktop, ref->node};
1095         while ((loc.node = loc.node->parent) != NULL) {
1096                 if (node_matches(&loc, ref, sel)) {
1097                         *dst = loc;
1098                         return;
1099                 }
1100         }
1101 }
1102
1103 /* Based on https://github.com/ntrrgc/right-window */
1104 void find_nearest_neighbor(coordinates_t *ref, coordinates_t *dst, direction_t dir, node_select_t *sel)
1105 {
1106         xcb_rectangle_t rect = get_rectangle(ref->monitor, ref->desktop, ref->node);
1107         uint32_t md = UINT32_MAX, mr = UINT32_MAX;
1108
1109         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1110                 desktop_t *d = m->desk;
1111                 for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1112                         coordinates_t loc = {m, d, f};
1113                         xcb_rectangle_t r = get_rectangle(m, d, f);
1114                         if (f == ref->node ||
1115                             f->client == NULL ||
1116                             f->hidden ||
1117                             is_descendant(f, ref->node) ||
1118                             !node_matches(&loc, ref, sel) ||
1119                             !on_dir_side(rect, r, dir)) {
1120                                 continue;
1121                         }
1122                         uint32_t fd = boundary_distance(rect, r, dir);
1123                         uint32_t fr = history_rank(f);
1124                         if (fd < md || (fd == md && fr < mr)) {
1125                                 md = fd;
1126                                 mr = fr;
1127                                 *dst = loc;
1128                         }
1129                 }
1130         }
1131 }
1132
1133 unsigned int node_area(desktop_t *d, node_t *n)
1134 {
1135         if (n == NULL) {
1136                 return 0;
1137         }
1138         return area(get_rectangle(NULL, d, n));
1139 }
1140
1141 int tiled_count(node_t *n, bool include_receptacles)
1142 {
1143         if (n == NULL) {
1144                 return 0;
1145         }
1146         int cnt = 0;
1147         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1148                 if (!f->hidden && ((include_receptacles && f->client == NULL) ||
1149                                    (f->client != NULL && IS_TILED(f->client)))) {
1150                         cnt++;
1151                 }
1152         }
1153         return cnt;
1154 }
1155
1156 void find_by_area(area_peak_t ap, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1157 {
1158         unsigned int p_area;
1159         if (ap == AREA_BIGGEST) {
1160                 p_area = 0;
1161         } else {
1162                 p_area = UINT_MAX;
1163         }
1164
1165         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1166                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1167                         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1168                                 coordinates_t loc = {m, d, f};
1169                                 if (f->vacant || !node_matches(&loc, ref, sel)) {
1170                                         continue;
1171                                 }
1172                                 unsigned int f_area = node_area(d, f);
1173                                 if ((ap == AREA_BIGGEST && f_area > p_area) || (ap == AREA_SMALLEST && f_area < p_area)) {
1174                                         *dst = loc;
1175                                         p_area = f_area;
1176                                 }
1177                         }
1178                 }
1179         }
1180 }
1181
1182 void rotate_tree(node_t *n, int deg)
1183 {
1184         rotate_tree_rec(n, deg);
1185         rebuild_constraints_from_leaves(n);
1186         rebuild_constraints_towards_root(n);
1187 }
1188
1189 void rotate_tree_rec(node_t *n, int deg)
1190 {
1191         if (n == NULL || is_leaf(n) || deg == 0) {
1192                 return;
1193         }
1194
1195         node_t *tmp;
1196
1197         if ((deg == 90 && n->split_type == TYPE_HORIZONTAL) ||
1198             (deg == 270 && n->split_type == TYPE_VERTICAL) ||
1199             deg == 180) {
1200                 tmp = n->first_child;
1201                 n->first_child = n->second_child;
1202                 n->second_child = tmp;
1203                 n->split_ratio = 1.0 - n->split_ratio;
1204         }
1205
1206         if (deg != 180) {
1207                 if (n->split_type == TYPE_HORIZONTAL) {
1208                         n->split_type = TYPE_VERTICAL;
1209                 } else if (n->split_type == TYPE_VERTICAL) {
1210                         n->split_type = TYPE_HORIZONTAL;
1211                 }
1212         }
1213
1214         rotate_tree_rec(n->first_child, deg);
1215         rotate_tree_rec(n->second_child, deg);
1216 }
1217
1218 void flip_tree(node_t *n, flip_t flp)
1219 {
1220         if (n == NULL || is_leaf(n)) {
1221                 return;
1222         }
1223
1224         node_t *tmp;
1225
1226         if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL) ||
1227             (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
1228                 tmp = n->first_child;
1229                 n->first_child = n->second_child;
1230                 n->second_child = tmp;
1231                 n->split_ratio = 1.0 - n->split_ratio;
1232         }
1233
1234         flip_tree(n->first_child, flp);
1235         flip_tree(n->second_child, flp);
1236 }
1237
1238 void equalize_tree(node_t *n)
1239 {
1240         if (n == NULL || n->vacant) {
1241                 return;
1242         } else {
1243                 n->split_ratio = split_ratio;
1244                 equalize_tree(n->first_child);
1245                 equalize_tree(n->second_child);
1246         }
1247 }
1248
1249 int balance_tree(node_t *n)
1250 {
1251         if (n == NULL || n->vacant) {
1252                 return 0;
1253         } else if (is_leaf(n)) {
1254                 return 1;
1255         } else {
1256                 int b1 = balance_tree(n->first_child);
1257                 int b2 = balance_tree(n->second_child);
1258                 int b = b1 + b2;
1259                 if (b1 > 0 && b2 > 0) {
1260                         n->split_ratio = (double) b1 / b;
1261                 }
1262                 return b;
1263         }
1264 }
1265
1266 /* Adjust the split ratios so that they keep their position
1267  * despite the potential alteration of their rectangle. */
1268 void adjust_ratios(node_t *n, xcb_rectangle_t rect)
1269 {
1270         if (n == NULL) {
1271                 return;
1272         }
1273
1274         double ratio;
1275
1276         if (n->split_type == TYPE_VERTICAL) {
1277                 double position = (double) n->rectangle.x + n->split_ratio * (double) n->rectangle.width;
1278                 ratio = (position - (double) rect.x) / (double) rect.width;
1279         } else {
1280                 double position = (double) n->rectangle.y + n->split_ratio * (double) n->rectangle.height;
1281                 ratio = (position - (double) rect.y) / (double) rect.height;
1282         }
1283
1284         ratio = MAX(0.0, ratio);
1285         ratio = MIN(1.0, ratio);
1286         n->split_ratio = ratio;
1287
1288         xcb_rectangle_t first_rect;
1289         xcb_rectangle_t second_rect;
1290         unsigned int fence;
1291
1292         if (n->split_type == TYPE_VERTICAL) {
1293                 fence = rect.width * n->split_ratio;
1294                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
1295                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
1296         } else {
1297                 fence = rect.height * n->split_ratio;
1298                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
1299                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
1300         }
1301
1302         adjust_ratios(n->first_child, first_rect);
1303         adjust_ratios(n->second_child, second_rect);
1304 }
1305
1306 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
1307 {
1308         if (d == NULL || n == NULL) {
1309                 return;
1310         }
1311
1312         node_t *p = n->parent;
1313
1314         if (p == NULL) {
1315                 d->root = NULL;
1316                 d->focus = NULL;
1317         } else {
1318                 if (d->focus == p || is_descendant(d->focus, n)) {
1319                         d->focus = NULL;
1320                 }
1321
1322                 history_remove(d, p, false);
1323                 cancel_presel(m, d, p);
1324
1325                 if (p->sticky) {
1326                         m->sticky_count--;
1327                 }
1328
1329                 node_t *b = brother_tree(n);
1330                 node_t *g = p->parent;
1331
1332                 b->parent = g;
1333
1334                 if (g != NULL) {
1335                         if (is_first_child(p)) {
1336                                 g->first_child = b;
1337                         } else {
1338                                 g->second_child = b;
1339                         }
1340                 } else {
1341                         d->root = b;
1342                 }
1343
1344                 if (!n->vacant && removal_adjustment) {
1345                         if (automatic_scheme == SCHEME_SPIRAL) {
1346                                 if (is_first_child(n)) {
1347                                         rotate_tree(b, 270);
1348                                 } else {
1349                                         rotate_tree(b, 90);
1350                                 }
1351                         } else if (automatic_scheme == SCHEME_LONGEST_SIDE || g == NULL) {
1352                                 if (p != NULL) {
1353                                         if (p->rectangle.width > p->rectangle.height) {
1354                                                 b->split_type = TYPE_VERTICAL;
1355                                         } else {
1356                                                 b->split_type = TYPE_HORIZONTAL;
1357                                         }
1358                                 }
1359                         } else if (automatic_scheme == SCHEME_ALTERNATE) {
1360                                 if (g->split_type == TYPE_HORIZONTAL) {
1361                                         b->split_type = TYPE_VERTICAL;
1362                                 } else {
1363                                         b->split_type = TYPE_HORIZONTAL;
1364                                 }
1365                         }
1366                 }
1367
1368                 free(p);
1369                 n->parent = NULL;
1370
1371                 propagate_flags_upward(m, d, b);
1372         }
1373 }
1374
1375 void close_node(node_t *n)
1376 {
1377         if (n == NULL) {
1378                 return;
1379         } else if (n->client != NULL) {
1380                 if (n->client->icccm_props.delete_window) {
1381                         send_client_message(n->id, ewmh->WM_PROTOCOLS, WM_DELETE_WINDOW);
1382                 } else {
1383                         xcb_kill_client(dpy, n->id);
1384                 }
1385         } else {
1386                 close_node(n->first_child);
1387                 close_node(n->second_child);
1388         }
1389 }
1390
1391 void kill_node(monitor_t *m, desktop_t *d, node_t *n)
1392 {
1393         if (n == NULL) {
1394                 return;
1395         }
1396
1397         if (IS_RECEPTACLE(n)) {
1398                 put_status(SBSC_MASK_NODE_REMOVE, "node_remove 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
1399                 remove_node(m, d, n);
1400         } else {
1401                 for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1402                         if (f->client != NULL) {
1403                                 xcb_kill_client(dpy, f->id);
1404                         }
1405                 }
1406         }
1407 }
1408
1409 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
1410 {
1411         if (n == NULL) {
1412                 return;
1413         }
1414
1415         unlink_node(m, d, n);
1416         history_remove(d, n, true);
1417         remove_stack_node(n);
1418         cancel_presel_in(m, d, n);
1419         if (m->sticky_count > 0 && d == m->desk) {
1420                 m->sticky_count -= sticky_count(n);
1421         }
1422         clients_count -= clients_count_in(n);
1423         if (is_descendant(grabbed_node, n)) {
1424                 grabbed_node = NULL;
1425         }
1426         free_node(n);
1427
1428         if (single_monocle && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1429                 set_layout(m, d, LAYOUT_MONOCLE, false);
1430         }
1431
1432         ewmh_update_client_list(false);
1433         ewmh_update_client_list(true);
1434
1435         if (mon != NULL && d->focus == NULL) {
1436                 if (d == mon->desk) {
1437                         focus_node(m, d, NULL);
1438                 } else {
1439                         activate_node(m, d, NULL);
1440                 }
1441         }
1442 }
1443
1444 void free_node(node_t *n)
1445 {
1446         if (n == NULL) {
1447                 return;
1448         }
1449         node_t *first_child = n->first_child;
1450         node_t *second_child = n->second_child;
1451         free(n->client);
1452         free(n);
1453         free_node(first_child);
1454         free_node(second_child);
1455 }
1456
1457 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2, bool follow)
1458 {
1459         if (n1 == NULL || n2 == NULL || n1 == n2 || is_descendant(n1, n2) || is_descendant(n2, n1) ||
1460             (d1 != d2 && ((m1->sticky_count > 0 && sticky_count(n1) > 0) ||
1461                           (m2->sticky_count > 0 && sticky_count(n2) > 0)))) {
1462                 return false;
1463         }
1464
1465         put_status(SBSC_MASK_NODE_SWAP, "node_swap 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X\n", m1->id, d1->id, n1->id, m2->id, d2->id, n2->id);
1466
1467         node_t *pn1 = n1->parent;
1468         node_t *pn2 = n2->parent;
1469         bool n1_first_child = is_first_child(n1);
1470         bool n2_first_child = is_first_child(n2);
1471         bool n1_held_focus = is_descendant(d1->focus, n1);
1472         bool n2_held_focus = is_descendant(d2->focus, n2);
1473         node_t *last_d1_focus = d1->focus;
1474         node_t *last_d2_focus = d2->focus;
1475
1476         if (pn1 != NULL) {
1477                 if (n1_first_child) {
1478                         pn1->first_child = n2;
1479                 } else {
1480                         pn1->second_child = n2;
1481                 }
1482         }
1483
1484         if (pn2 != NULL) {
1485                 if (n2_first_child) {
1486                         pn2->first_child = n1;
1487                 } else {
1488                         pn2->second_child = n1;
1489                 }
1490         }
1491
1492         n1->parent = pn2;
1493         n2->parent = pn1;
1494
1495         propagate_flags_upward(m2, d2, n1);
1496         propagate_flags_upward(m1, d1, n2);
1497
1498         if (d1 != d2) {
1499                 if (d1->root == n1) {
1500                         d1->root = n2;
1501                 }
1502
1503                 if (d2->root == n2) {
1504                         d2->root = n1;
1505                 }
1506
1507                 if (n1_held_focus) {
1508                         d1->focus = n2_held_focus ? last_d2_focus : n2;
1509                 }
1510
1511                 if (n2_held_focus) {
1512                         d2->focus = n1_held_focus ? last_d1_focus : n1;
1513                 }
1514
1515                 if (m1 != m2) {
1516                         adapt_geometry(&m2->rectangle, &m1->rectangle, n2);
1517                         adapt_geometry(&m1->rectangle, &m2->rectangle, n1);
1518                 }
1519
1520                 ewmh_set_wm_desktop(n1, d2);
1521                 ewmh_set_wm_desktop(n2, d1);
1522
1523                 history_remove(d1, n1, true);
1524                 history_remove(d2, n2, true);
1525
1526                 bool d1_was_focused = (d1 == mon->desk);
1527                 bool d2_was_focused = (d2 == mon->desk);
1528
1529                 if (m1->desk != d1 && m2->desk == d2) {
1530                         show_node(d2, n1);
1531                         if (!follow || !d2_was_focused || !n2_held_focus) {
1532                                 hide_node(d2, n2);
1533                         }
1534                 } else if (m1->desk == d1 && m2->desk != d2) {
1535                         if (!follow || !d1_was_focused || !n1_held_focus) {
1536                                 hide_node(d1, n1);
1537                         }
1538                         show_node(d1, n2);
1539                 }
1540
1541                 if (single_monocle) {
1542                         layout_t l1 = tiled_count(d1->root, true) <= 1 ? LAYOUT_MONOCLE : d1->user_layout;
1543                         layout_t l2 = tiled_count(d2->root, true) <= 1 ? LAYOUT_MONOCLE : d2->user_layout;
1544                         set_layout(m1, d1, l1, false);
1545                         set_layout(m2, d2, l2, false);
1546                 }
1547
1548                 if (n1_held_focus) {
1549                         if (d1_was_focused) {
1550                                 if (follow) {
1551                                         focus_node(m2, d2, last_d1_focus);
1552                                 } else {
1553                                         focus_node(m1, d1, d1->focus);
1554                                 }
1555                         } else {
1556                                 activate_node(m1, d1, d1->focus);
1557                         }
1558                 } else {
1559                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1560                 }
1561
1562                 if (n2_held_focus) {
1563                         if (d2_was_focused) {
1564                                 if (follow) {
1565                                         focus_node(m1, d1, last_d2_focus);
1566                                 } else {
1567                                         focus_node(m2, d2, d2->focus);
1568                                 }
1569                         } else {
1570                                 activate_node(m2, d2, d2->focus);
1571                         }
1572                 } else {
1573                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1574                 }
1575         } else {
1576                 if (!n1_held_focus) {
1577                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1578                 }
1579                 if (!n2_held_focus) {
1580                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1581                 }
1582         }
1583
1584         arrange(m1, d1);
1585
1586         if (d1 != d2) {
1587                 arrange(m2, d2);
1588         } else {
1589                 if (pointer_follows_focus && (n1_held_focus || n2_held_focus)) {
1590                         center_pointer(get_rectangle(m1, d1, d1->focus));
1591                 }
1592         }
1593
1594         return true;
1595 }
1596
1597 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd, bool follow)
1598 {
1599         if (ns == NULL || ns == nd || is_child(ns, nd) || is_descendant(nd, ns)) {
1600                 return false;
1601         }
1602
1603         unsigned int sc = (ms->sticky_count > 0 && ds == ms->desk) ? sticky_count(ns) : 0;
1604         if (sticky_still && sc > 0 && dd != md->desk) {
1605                 return false;
1606         }
1607
1608         put_status(SBSC_MASK_NODE_TRANSFER, "node_transfer 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X 0x%08X\n", ms->id, ds->id, ns->id, md->id, dd->id, nd!=NULL?nd->id:0);
1609
1610         bool held_focus = is_descendant(ds->focus, ns);
1611         /* avoid ending up with a dangling pointer (because of unlink_node) */
1612         node_t *last_ds_focus = is_child(ns, ds->focus) ? NULL : ds->focus;
1613         bool ds_was_focused = (ds == mon->desk);
1614
1615         if (held_focus && ds_was_focused) {
1616                 clear_input_focus();
1617         }
1618
1619         unlink_node(ms, ds, ns);
1620         insert_node(md, dd, ns, nd);
1621
1622         if (md != ms) {
1623                 if (ns->client == NULL || monitor_from_client(ns->client) != md) {
1624                         adapt_geometry(&ms->rectangle, &md->rectangle, ns);
1625                 }
1626                 ms->sticky_count -= sc;
1627                 md->sticky_count += sc;
1628         }
1629
1630         if (ds != dd) {
1631                 ewmh_set_wm_desktop(ns, dd);
1632                 if (sticky_still) {
1633                         if (ds == ms->desk && dd != md->desk) {
1634                                 hide_node(ds, ns);
1635                         } else if (ds != ms->desk && dd == md->desk) {
1636                                 show_node(dd, ns);
1637                         }
1638                 }
1639         }
1640
1641         history_remove(ds, ns, true);
1642         stack(dd, ns, false);
1643
1644         if (ds == dd) {
1645                 if (held_focus) {
1646                         if (ds_was_focused) {
1647                                 focus_node(ms, ds, last_ds_focus);
1648                         } else {
1649                                 activate_node(ms, ds, last_ds_focus);
1650                         }
1651                 } else {
1652                         draw_border(ns, is_descendant(ns, ds->focus), (ms == mon));
1653                 }
1654         } else {
1655                 if (single_monocle) {
1656                         if (ds->layout != LAYOUT_MONOCLE && tiled_count(ds->root, true) <= 1) {
1657                                 set_layout(ms, ds, LAYOUT_MONOCLE, false);
1658                         }
1659                         if (dd->layout == LAYOUT_MONOCLE && tiled_count(dd->root, true) > 1) {
1660                                 set_layout(md, dd, dd->user_layout, false);
1661                         }
1662                 }
1663                 if (held_focus) {
1664                         if (follow) {
1665                                 if (ds_was_focused) {
1666                                         focus_node(md, dd, last_ds_focus);
1667                                 }
1668                                 activate_node(ms, ds, ds->focus);
1669                         } else {
1670                                 if (ds_was_focused) {
1671                                         focus_node(ms, ds, ds->focus);
1672                                 } else {
1673                                         activate_node(ms, ds, ds->focus);
1674                                 }
1675                         }
1676                 }
1677                 if (!held_focus || !follow || !ds_was_focused) {
1678                         if (dd->focus == ns) {
1679                                 if (dd == mon->desk) {
1680                                         focus_node(md, dd, held_focus ? last_ds_focus : ns);
1681                                 } else {
1682                                         activate_node(md, dd, held_focus ? last_ds_focus : ns);
1683                                 }
1684                         } else {
1685                                 draw_border(ns, is_descendant(ns, dd->focus), (md == mon));
1686                         }
1687                 }
1688         }
1689
1690         arrange(ms, ds);
1691
1692         if (ds != dd) {
1693                 arrange(md, dd);
1694         }
1695
1696         return true;
1697 }
1698
1699 bool find_closest_node(coordinates_t *ref, coordinates_t *dst, cycle_dir_t dir, node_select_t *sel)
1700 {
1701         monitor_t *m = ref->monitor;
1702         desktop_t *d = ref->desktop;
1703         node_t *n = ref->node;
1704         n = (dir == CYCLE_PREV ? prev_node(n) : next_node(n));
1705
1706 #define HANDLE_BOUNDARIES(m, d, n)  \
1707         while (n == NULL) { \
1708                 d = (dir == CYCLE_PREV ? d->prev : d->next); \
1709                 if (d == NULL) { \
1710                         m = (dir == CYCLE_PREV ? m->prev : m->next); \
1711                         if (m == NULL) { \
1712                                 m = (dir == CYCLE_PREV ? mon_tail : mon_head); \
1713                         } \
1714                         d = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head); \
1715                 } \
1716                 n = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root)); \
1717                 if (ref->node == NULL && d == ref->desktop) { \
1718                         break; \
1719                 } \
1720         }
1721         HANDLE_BOUNDARIES(m, d, n);
1722
1723         while (n != ref->node) {
1724                 coordinates_t loc = {m, d, n};
1725                 if (node_matches(&loc, ref, sel)) {
1726                         *dst = loc;
1727                         return true;
1728                 }
1729                 n = (dir == CYCLE_PREV ? prev_node(n) : next_node(n));
1730                 HANDLE_BOUNDARIES(m, d, n);
1731                 if (ref->node == NULL && d == ref->desktop) {
1732                         break;
1733                 }
1734         }
1735 #undef HANDLE_BOUNDARIES
1736         return false;
1737 }
1738
1739 void circulate_leaves(monitor_t *m, desktop_t *d, node_t *n, circulate_dir_t dir)
1740 {
1741         if (tiled_count(n, false) < 2) {
1742                 return;
1743         }
1744         node_t *p = d->focus->parent;
1745         bool focus_first_child = is_first_child(d->focus);
1746         if (dir == CIRCULATE_FORWARD) {
1747                 node_t *e = second_extrema(n);
1748                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1749                         e = prev_leaf(e, n);
1750                 }
1751                 for (node_t *s = e, *f = prev_tiled_leaf(s, n); f != NULL; s = prev_tiled_leaf(f, n), f = prev_tiled_leaf(s, n)) {
1752                         swap_nodes(m, d, f, m, d, s, false);
1753                 }
1754         } else {
1755                 node_t *e = first_extrema(n);
1756                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1757                         e = next_leaf(e, n);
1758                 }
1759                 for (node_t *f = e, *s = next_tiled_leaf(f, n); s != NULL; f = next_tiled_leaf(s, n), s = next_tiled_leaf(f, n)) {
1760                         swap_nodes(m, d, f, m, d, s, false);
1761                 }
1762         }
1763         if (p != NULL) {
1764                 node_t *f = focus_first_child ? p->first_child : p->second_child;
1765                 if (is_leaf(f)) {
1766                         if (d == mon->desk) {
1767                                 focus_node(m, d, f);
1768                         } else {
1769                                 activate_node(m, d, f);
1770                         }
1771                 }
1772         }
1773 }
1774
1775 void set_vacant(monitor_t *m, desktop_t *d, node_t *n, bool value)
1776 {
1777         if (n->vacant == value) {
1778                 return;
1779         }
1780
1781         propagate_vacant_downward(m, d, n, value);
1782         propagate_vacant_upward(m, d, n);
1783 }
1784
1785 void set_vacant_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1786 {
1787         if (n->vacant == value) {
1788                 return;
1789         }
1790
1791         n->vacant = value;
1792
1793         if (value) {
1794                 cancel_presel(m, d, n);
1795         }
1796 }
1797
1798 void propagate_vacant_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1799 {
1800         if (n == NULL) {
1801                 return;
1802         }
1803
1804         set_vacant_local(m, d, n, value);
1805
1806         propagate_vacant_downward(m, d, n->first_child, value);
1807         propagate_vacant_downward(m, d, n->second_child, value);
1808 }
1809
1810 void propagate_vacant_upward(monitor_t *m, desktop_t *d, node_t *n)
1811 {
1812         if (n == NULL) {
1813                 return;
1814         }
1815
1816         node_t *p = n->parent;
1817
1818         if (p != NULL) {
1819                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1820         }
1821
1822         propagate_vacant_upward(m, d, p);
1823 }
1824
1825 bool set_layer(monitor_t *m, desktop_t *d, node_t *n, stack_layer_t l)
1826 {
1827         if (n == NULL || n->client == NULL || n->client->layer == l) {
1828                 return false;
1829         }
1830
1831         n->client->last_layer = n->client->layer;
1832         n->client->layer = l;
1833
1834         if (l == LAYER_ABOVE) {
1835                 n->client->wm_flags |= WM_FLAG_ABOVE;
1836                 n->client->wm_flags &= ~WM_FLAG_BELOW;
1837         } else if (l == LAYER_BELOW) {
1838                 n->client->wm_flags |= WM_FLAG_BELOW;
1839                 n->client->wm_flags &= ~WM_FLAG_ABOVE;
1840         } else {
1841                 n->client->wm_flags &= ~(WM_FLAG_ABOVE | WM_FLAG_BELOW);
1842         }
1843
1844         ewmh_wm_state_update(n);
1845
1846         put_status(SBSC_MASK_NODE_LAYER, "node_layer 0x%08X 0x%08X 0x%08X %s\n", m->id, d->id, n->id, LAYER_STR(l));
1847
1848         if (d->focus == n) {
1849                 neutralize_occluding_windows(m, d, n);
1850         }
1851
1852         stack(d, n, (d->focus == n));
1853
1854         return true;
1855 }
1856
1857 bool set_state(monitor_t *m, desktop_t *d, node_t *n, client_state_t s)
1858 {
1859         if (n == NULL || n->client == NULL || n->client->state == s) {
1860                 return false;
1861         }
1862
1863         client_t *c = n->client;
1864
1865         bool was_tiled = IS_TILED(c);
1866
1867         c->last_state = c->state;
1868         c->state = s;
1869
1870         switch (c->last_state) {
1871                 case STATE_TILED:
1872                 case STATE_PSEUDO_TILED:
1873                         break;
1874                 case STATE_FLOATING:
1875                         set_floating(m, d, n, false);
1876                         break;
1877                 case STATE_FULLSCREEN:
1878                         set_fullscreen(m, d, n, false);
1879                         break;
1880         }
1881
1882         put_status(SBSC_MASK_NODE_STATE, "node_state 0x%08X 0x%08X 0x%08X %s off\n", m->id, d->id, n->id, STATE_STR(c->last_state));
1883
1884         switch (c->state) {
1885                 case STATE_TILED:
1886                 case STATE_PSEUDO_TILED:
1887                         break;
1888                 case STATE_FLOATING:
1889                         set_floating(m, d, n, true);
1890                         break;
1891                 case STATE_FULLSCREEN:
1892                         set_fullscreen(m, d, n, true);
1893                         break;
1894         }
1895
1896         put_status(SBSC_MASK_NODE_STATE, "node_state 0x%08X 0x%08X 0x%08X %s on\n", m->id, d->id, n->id, STATE_STR(c->state));
1897
1898         if (n == m->desk->focus) {
1899                 put_status(SBSC_MASK_REPORT);
1900         }
1901
1902         if (single_monocle && was_tiled != IS_TILED(c)) {
1903                 if (was_tiled && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1904                         set_layout(m, d, LAYOUT_MONOCLE, false);
1905                 } else if (!was_tiled && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
1906                         set_layout(m, d, d->user_layout, false);
1907                 }
1908         }
1909
1910         return true;
1911 }
1912
1913 void set_floating(monitor_t *m, desktop_t *d, node_t *n, bool value)
1914 {
1915         if (n == NULL) {
1916                 return;
1917         }
1918
1919         cancel_presel(m, d, n);
1920         if (!n->hidden) {
1921                 set_vacant(m, d, n, value);
1922         }
1923
1924         if (!value && d->focus == n) {
1925                 neutralize_occluding_windows(m, d, n);
1926         }
1927
1928         stack(d, n, (d->focus == n));
1929 }
1930
1931 void set_fullscreen(monitor_t *m, desktop_t *d, node_t *n, bool value)
1932 {
1933         if (n == NULL) {
1934                 return;
1935         }
1936
1937         client_t *c = n->client;
1938
1939         cancel_presel(m, d, n);
1940         if (!n->hidden) {
1941                 set_vacant(m, d, n, value);
1942         }
1943
1944         if (value) {
1945                 c->wm_flags |= WM_FLAG_FULLSCREEN;
1946         } else {
1947                 c->wm_flags &= ~WM_FLAG_FULLSCREEN;
1948                 if (d->focus == n) {
1949                         neutralize_occluding_windows(m, d, n);
1950                 }
1951         }
1952
1953         ewmh_wm_state_update(n);
1954         stack(d, n, (d->focus == n));
1955 }
1956
1957 void neutralize_occluding_windows(monitor_t *m, desktop_t *d, node_t *n)
1958 {
1959         bool changed = false;
1960         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1961                 for (node_t *a = first_extrema(d->root); a != NULL; a = next_leaf(a, d->root)) {
1962                         if (a != f && a->client != NULL && f->client != NULL &&
1963                             IS_FULLSCREEN(a->client) && stack_cmp(f->client, a->client) < 0) {
1964                                 set_state(m, d, a, a->client->last_state);
1965                                 changed = true;
1966                         }
1967                 }
1968         }
1969         if (changed) {
1970                 arrange(m, d);
1971         }
1972 }
1973
1974 void rebuild_constraints_from_leaves(node_t *n)
1975 {
1976         if (n == NULL || is_leaf(n)) {
1977                 return;
1978         } else {
1979                 rebuild_constraints_from_leaves(n->first_child);
1980                 rebuild_constraints_from_leaves(n->second_child);
1981                 update_constraints(n);
1982         }
1983 }
1984
1985 void rebuild_constraints_towards_root(node_t *n)
1986 {
1987         if (n == NULL) {
1988                 return;
1989         }
1990
1991         node_t *p = n->parent;
1992
1993         if (p != NULL) {
1994                 update_constraints(p);
1995         }
1996
1997         rebuild_constraints_towards_root(p);
1998 }
1999
2000 void update_constraints(node_t *n)
2001 {
2002         if (n == NULL || is_leaf(n)) {
2003                 return;
2004         }
2005         if (n->split_type == TYPE_VERTICAL) {
2006                 n->constraints.min_width = n->first_child->constraints.min_width + n->second_child->constraints.min_width;
2007                 n->constraints.min_height = MAX(n->first_child->constraints.min_height, n->second_child->constraints.min_height);
2008         } else {
2009                 n->constraints.min_width = MAX(n->first_child->constraints.min_width, n->second_child->constraints.min_width);
2010                 n->constraints.min_height = n->first_child->constraints.min_height + n->second_child->constraints.min_height;
2011         }
2012 }
2013
2014 void propagate_flags_upward(monitor_t *m, desktop_t *d, node_t *n)
2015 {
2016         if (n == NULL) {
2017                 return;
2018         }
2019
2020         node_t *p = n->parent;
2021
2022         if (p != NULL) {
2023                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
2024                 set_hidden_local(m, d, p, (p->first_child->hidden && p->second_child->hidden));
2025                 update_constraints(p);
2026         }
2027
2028         propagate_flags_upward(m, d, p);
2029 }
2030
2031 void set_hidden(monitor_t *m, desktop_t *d, node_t *n, bool value)
2032 {
2033         if (n == NULL || n->hidden == value) {
2034                 return;
2035         }
2036
2037         bool held_focus = is_descendant(d->focus, n);
2038
2039         propagate_hidden_downward(m, d, n, value);
2040         propagate_hidden_upward(m, d, n);
2041
2042         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X hidden %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2043
2044         if (held_focus || d->focus == NULL) {
2045                 if (d->focus != NULL) {
2046                         d->focus = NULL;
2047                         draw_border(n, false, (mon == m));
2048                 }
2049                 if (d == mon->desk) {
2050                         focus_node(m, d, d->focus);
2051                 } else {
2052                         activate_node(m, d, d->focus);
2053                 }
2054         }
2055
2056         if (single_monocle) {
2057                 if (value && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
2058                         set_layout(m, d, LAYOUT_MONOCLE, false);
2059                 } else if (!value && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
2060                         set_layout(m, d, d->user_layout, false);
2061                 }
2062         }
2063 }
2064
2065 void set_hidden_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
2066 {
2067         if (n->hidden == value) {
2068                 return;
2069         }
2070
2071         n->hidden = value;
2072
2073         if (n->client != NULL) {
2074                 if (n->client->shown) {
2075                         window_set_visibility(n->id, !value);
2076                 }
2077
2078                 if (IS_TILED(n->client)) {
2079                         set_vacant(m, d, n, value);
2080                 }
2081
2082                 if (value) {
2083                         n->client->wm_flags |= WM_FLAG_HIDDEN;
2084                 } else {
2085                         n->client->wm_flags &= ~WM_FLAG_HIDDEN;
2086                 }
2087
2088                 ewmh_wm_state_update(n);
2089         }
2090 }
2091
2092 void propagate_hidden_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
2093 {
2094         if (n == NULL) {
2095                 return;
2096         }
2097
2098         set_hidden_local(m, d, n, value);
2099
2100         propagate_hidden_downward(m, d, n->first_child, value);
2101         propagate_hidden_downward(m, d, n->second_child, value);
2102 }
2103
2104 void propagate_hidden_upward(monitor_t *m, desktop_t *d, node_t *n)
2105 {
2106         if (n == NULL) {
2107                 return;
2108         }
2109
2110         node_t *p = n->parent;
2111
2112         if (p != NULL) {
2113                 set_hidden_local(m, d, p, p->first_child->hidden && p->second_child->hidden);
2114         }
2115
2116         propagate_hidden_upward(m, d, p);
2117 }
2118
2119 void set_sticky(monitor_t *m, desktop_t *d, node_t *n, bool value)
2120 {
2121         if (n == NULL || n->sticky == value) {
2122                 return;
2123         }
2124
2125         if (d != m->desk) {
2126                 transfer_node(m, d, n, m, m->desk, m->desk->focus, false);
2127         }
2128
2129         n->sticky = value;
2130
2131         if (value) {
2132                 m->sticky_count++;
2133         } else {
2134                 m->sticky_count--;
2135         }
2136
2137         if (n->client != NULL) {
2138                 if (value) {
2139                         n->client->wm_flags |= WM_FLAG_STICKY;
2140                 } else {
2141                         n->client->wm_flags &= ~WM_FLAG_STICKY;
2142                 }
2143                 ewmh_wm_state_update(n);
2144         }
2145
2146         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X sticky %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2147
2148         if (n == m->desk->focus) {
2149                 put_status(SBSC_MASK_REPORT);
2150         }
2151 }
2152
2153 void set_private(monitor_t *m, desktop_t *d, node_t *n, bool value)
2154 {
2155         if (n == NULL || n->private == value) {
2156                 return;
2157         }
2158
2159         n->private = value;
2160
2161         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X private %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2162
2163         if (n == m->desk->focus) {
2164                 put_status(SBSC_MASK_REPORT);
2165         }
2166 }
2167
2168 void set_locked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2169 {
2170         if (n == NULL || n->locked == value) {
2171                 return;
2172         }
2173
2174         n->locked = value;
2175
2176         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X locked %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2177
2178         if (n == m->desk->focus) {
2179                 put_status(SBSC_MASK_REPORT);
2180         }
2181 }
2182
2183 void set_marked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2184 {
2185         if (n == NULL || n->marked == value) {
2186                 return;
2187         }
2188
2189         n->marked = value;
2190
2191         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X marked %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2192
2193         if (n == m->desk->focus) {
2194                 put_status(SBSC_MASK_REPORT);
2195         }
2196 }
2197
2198 void set_urgent(monitor_t *m, desktop_t *d, node_t *n, bool value)
2199 {
2200         if (value && mon->desk->focus == n) {
2201                 return;
2202         }
2203
2204         n->client->urgent = value;
2205
2206         if (value) {
2207                 n->client->wm_flags |= WM_FLAG_DEMANDS_ATTENTION;
2208         } else {
2209                 n->client->wm_flags &= ~WM_FLAG_DEMANDS_ATTENTION;
2210         }
2211
2212         ewmh_wm_state_update(n);
2213
2214         put_status(SBSC_MASK_NODE_FLAG, "node_flag 0x%08X 0x%08X 0x%08X urgent %s\n", m->id, d->id, n->id, ON_OFF_STR(value));
2215         put_status(SBSC_MASK_REPORT);
2216 }
2217
2218 xcb_rectangle_t get_rectangle(monitor_t *m, desktop_t *d, node_t *n)
2219 {
2220         if (n == NULL) {
2221                 return m->rectangle;
2222         }
2223         client_t *c = n->client;
2224         if (c != NULL) {
2225                 if (IS_FLOATING(c)) {
2226                         return c->floating_rectangle;
2227                 } else {
2228                         return c->tiled_rectangle;
2229                 }
2230         } else {
2231                 int wg = (d == NULL ? 0 : (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap));
2232                 xcb_rectangle_t rect = n->rectangle;
2233                 rect.width -= wg;
2234                 rect.height -= wg;
2235                 return rect;
2236         }
2237 }
2238
2239 void listen_enter_notify(node_t *n, bool enable)
2240 {
2241         uint32_t mask = CLIENT_EVENT_MASK | (enable ? XCB_EVENT_MASK_ENTER_WINDOW : 0);
2242         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
2243                 if (f->client == NULL) {
2244                         continue;
2245                 }
2246                 xcb_change_window_attributes(dpy, f->id, XCB_CW_EVENT_MASK, &mask);
2247                 if (f->presel != NULL) {
2248                         xcb_change_window_attributes(dpy, f->presel->feedback, XCB_CW_EVENT_MASK, &mask);
2249                 }
2250         }
2251 }
2252
2253 void regenerate_ids_in(node_t *n)
2254 {
2255         if (n == NULL || n->client != NULL) {
2256                 return;
2257         }
2258         n->id = xcb_generate_id(dpy);
2259         regenerate_ids_in(n->first_child);
2260         regenerate_ids_in(n->second_child);
2261 }
2262
2263 #define DEF_FLAG_COUNT(flag) \
2264         unsigned int flag##_count(node_t *n) \
2265         { \
2266                 if (n == NULL) { \
2267                         return 0; \
2268                 } else { \
2269                         return ((n->flag ? 1 : 0) + \
2270                                 flag##_count(n->first_child) + \
2271                                 flag##_count(n->second_child)); \
2272                 } \
2273         }
2274         DEF_FLAG_COUNT(sticky)
2275         DEF_FLAG_COUNT(private)
2276         DEF_FLAG_COUNT(locked)
2277 #undef DEF_FLAG_COUNT