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