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