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