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