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 /* Based on https://github.com/ntrrgc/right-window */
1018 void find_nearest_neighbor(coordinates_t *ref, coordinates_t *dst, direction_t dir, node_select_t *sel)
1019 {
1020         xcb_rectangle_t rect = get_rectangle(ref->monitor, ref->desktop, ref->node);
1021         uint32_t md = UINT32_MAX, mr = UINT32_MAX;
1022
1023         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1024                 desktop_t *d = m->desk;
1025                 for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1026                         coordinates_t loc = {m, d, f};
1027                         xcb_rectangle_t r = get_rectangle(m, d, f);
1028                         if (f == ref->node ||
1029                             f->client == NULL ||
1030                             f->hidden ||
1031                             is_descendant(f, ref->node) ||
1032                             !node_matches(&loc, ref, sel) ||
1033                             !on_dir_side(rect, r, dir)) {
1034                                 continue;
1035                         }
1036                         uint32_t fd = boundary_distance(rect, r, dir);
1037                         uint32_t fr = history_rank(f);
1038                         if (fd < md || (fd == md && fr < mr)) {
1039                                 md = fd;
1040                                 mr = fr;
1041                                 *dst = loc;
1042                         }
1043                 }
1044         }
1045 }
1046
1047 unsigned int node_area(desktop_t *d, node_t *n)
1048 {
1049         if (n == NULL) {
1050                 return 0;
1051         }
1052         return area(get_rectangle(NULL, d, n));
1053 }
1054
1055 int tiled_count(node_t *n, bool include_receptacles)
1056 {
1057         if (n == NULL) {
1058                 return 0;
1059         }
1060         int cnt = 0;
1061         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1062                 if (!f->hidden && ((include_receptacles && f->client == NULL) ||
1063                                    (f->client != NULL && IS_TILED(f->client)))) {
1064                         cnt++;
1065                 }
1066         }
1067         return cnt;
1068 }
1069
1070 void find_by_area(area_peak_t ap, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1071 {
1072         unsigned int p_area;
1073         if (ap == AREA_BIGGEST) {
1074                 p_area = 0;
1075         } else {
1076                 p_area = UINT_MAX;
1077         }
1078
1079         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1080                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1081                         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1082                                 coordinates_t loc = {m, d, f};
1083                                 if (f->client == NULL || f->vacant || !node_matches(&loc, ref, sel)) {
1084                                         continue;
1085                                 }
1086                                 unsigned int f_area = node_area(d, f);
1087                                 if ((ap == AREA_BIGGEST && f_area > p_area) || (ap == AREA_SMALLEST && f_area < p_area)) {
1088                                         *dst = loc;
1089                                         p_area = f_area;
1090                                 }
1091                         }
1092                 }
1093         }
1094 }
1095
1096 void rotate_tree(node_t *n, int deg)
1097 {
1098         rotate_tree_rec(n, deg);
1099         rebuild_constraints(n);
1100 }
1101
1102 void rotate_tree_rec(node_t *n, int deg)
1103 {
1104         if (n == NULL || is_leaf(n) || deg == 0) {
1105                 return;
1106         }
1107
1108         node_t *tmp;
1109
1110         if ((deg == 90 && n->split_type == TYPE_HORIZONTAL) ||
1111             (deg == 270 && n->split_type == TYPE_VERTICAL) ||
1112             deg == 180) {
1113                 tmp = n->first_child;
1114                 n->first_child = n->second_child;
1115                 n->second_child = tmp;
1116                 n->split_ratio = 1.0 - n->split_ratio;
1117         }
1118
1119         if (deg != 180) {
1120                 if (n->split_type == TYPE_HORIZONTAL) {
1121                         n->split_type = TYPE_VERTICAL;
1122                 } else if (n->split_type == TYPE_VERTICAL) {
1123                         n->split_type = TYPE_HORIZONTAL;
1124                 }
1125         }
1126
1127         rotate_tree_rec(n->first_child, deg);
1128         rotate_tree_rec(n->second_child, deg);
1129 }
1130
1131 void flip_tree(node_t *n, flip_t flp)
1132 {
1133         if (n == NULL || is_leaf(n)) {
1134                 return;
1135         }
1136
1137         node_t *tmp;
1138
1139         if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL) ||
1140             (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
1141                 tmp = n->first_child;
1142                 n->first_child = n->second_child;
1143                 n->second_child = tmp;
1144                 n->split_ratio = 1.0 - n->split_ratio;
1145         }
1146
1147         flip_tree(n->first_child, flp);
1148         flip_tree(n->second_child, flp);
1149 }
1150
1151 void equalize_tree(node_t *n)
1152 {
1153         if (n == NULL || n->vacant) {
1154                 return;
1155         } else {
1156                 n->split_ratio = split_ratio;
1157                 equalize_tree(n->first_child);
1158                 equalize_tree(n->second_child);
1159         }
1160 }
1161
1162 int balance_tree(node_t *n)
1163 {
1164         if (n == NULL || n->vacant) {
1165                 return 0;
1166         } else if (is_leaf(n)) {
1167                 return 1;
1168         } else {
1169                 int b1 = balance_tree(n->first_child);
1170                 int b2 = balance_tree(n->second_child);
1171                 int b = b1 + b2;
1172                 if (b1 > 0 && b2 > 0) {
1173                         n->split_ratio = (double) b1 / b;
1174                 }
1175                 return b;
1176         }
1177 }
1178
1179 /* Adjust the split ratios so that they keep their position
1180  * despite the potential alteration of their rectangle. */
1181 void adjust_ratios(node_t *n, xcb_rectangle_t rect)
1182 {
1183         if (n == NULL) {
1184                 return;
1185         }
1186
1187         double ratio;
1188
1189         if (n->split_type == TYPE_VERTICAL) {
1190                 double position = (double) n->rectangle.x + n->split_ratio * (double) n->rectangle.width;
1191                 ratio = (position - (double) rect.x) / (double) rect.width;
1192         } else {
1193                 double position = (double) n->rectangle.y + n->split_ratio * (double) n->rectangle.height;
1194                 ratio = (position - (double) rect.y) / (double) rect.height;
1195         }
1196
1197         ratio = MAX(0.0, ratio);
1198         ratio = MIN(1.0, ratio);
1199         n->split_ratio = ratio;
1200
1201         xcb_rectangle_t first_rect;
1202         xcb_rectangle_t second_rect;
1203         unsigned int fence;
1204
1205         if (n->split_type == TYPE_VERTICAL) {
1206                 fence = rect.width * n->split_ratio;
1207                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
1208                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
1209         } else {
1210                 fence = rect.height * n->split_ratio;
1211                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
1212                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
1213         }
1214
1215         adjust_ratios(n->first_child, first_rect);
1216         adjust_ratios(n->second_child, second_rect);
1217 }
1218
1219 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
1220 {
1221         if (d == NULL || n == NULL) {
1222                 return;
1223         }
1224
1225         node_t *p = n->parent;
1226
1227         if (p == NULL) {
1228                 d->root = NULL;
1229                 d->focus = NULL;
1230         } else {
1231                 if (d->focus == p || is_descendant(d->focus, n)) {
1232                         d->focus = NULL;
1233                 }
1234
1235                 history_remove(d, p, false);
1236                 cancel_presel(m, d, p);
1237                 if (p->sticky) {
1238                         m->sticky_count--;
1239                 }
1240
1241                 node_t *b = brother_tree(n);
1242                 node_t *g = p->parent;
1243
1244                 b->parent = g;
1245
1246                 if (g != NULL) {
1247                         if (is_first_child(p)) {
1248                                 g->first_child = b;
1249                         } else {
1250                                 g->second_child = b;
1251                         }
1252                 } else {
1253                         d->root = b;
1254                 }
1255
1256                 if (!n->vacant && removal_adjustment) {
1257                         if (automatic_scheme == SCHEME_LONGEST_SIDE || g == NULL) {
1258                                 if (p != NULL) {
1259                                         if (p->rectangle.width > p->rectangle.height) {
1260                                                 b->split_type = TYPE_VERTICAL;
1261                                         } else {
1262                                                 b->split_type = TYPE_HORIZONTAL;
1263                                         }
1264                                 }
1265                         } else if (automatic_scheme == SCHEME_ALTERNATE) {
1266                                 if (g->split_type == TYPE_HORIZONTAL) {
1267                                         b->split_type = TYPE_VERTICAL;
1268                                 } else {
1269                                         b->split_type = TYPE_HORIZONTAL;
1270                                 }
1271                         }
1272                 }
1273
1274                 free(p);
1275                 n->parent = NULL;
1276
1277                 propagate_flags_upward(m, d, b);
1278         }
1279 }
1280
1281 void close_node(node_t *n)
1282 {
1283         if (n == NULL) {
1284                 return;
1285         } else if (n->client != NULL) {
1286                 if (n->client->icccm_props.delete_window) {
1287                         send_client_message(n->id, ewmh->WM_PROTOCOLS, WM_DELETE_WINDOW);
1288                 } else {
1289                         xcb_kill_client(dpy, n->id);
1290                 }
1291         } else {
1292                 close_node(n->first_child);
1293                 close_node(n->second_child);
1294         }
1295 }
1296
1297 void kill_node(monitor_t *m, desktop_t *d, node_t *n)
1298 {
1299         if (n == NULL) {
1300                 return;
1301         }
1302
1303         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1304                 if (f->client != NULL) {
1305                         xcb_kill_client(dpy, f->id);
1306                 }
1307         }
1308
1309         remove_node(m, d, n);
1310 }
1311
1312 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
1313 {
1314         if (n == NULL) {
1315                 return;
1316         }
1317
1318         unlink_node(m, d, n);
1319         history_remove(d, n, true);
1320         remove_stack_node(n);
1321         cancel_presel_in(m, d, n);
1322         if (m->sticky_count > 0) {
1323                 m->sticky_count -= sticky_count(n);
1324         }
1325         clients_count -= clients_count_in(n);
1326         if (is_descendant(grabbed_node, n)) {
1327                 grabbed_node = NULL;
1328         }
1329         free_node(n);
1330
1331         if (single_monocle && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1332                 set_layout(m, d, LAYOUT_MONOCLE, false);
1333         }
1334
1335         ewmh_update_client_list(false);
1336         ewmh_update_client_list(true);
1337
1338         if (mon != NULL && d->focus == NULL) {
1339                 if (d == mon->desk) {
1340                         focus_node(m, d, NULL);
1341                 } else {
1342                         activate_node(m, d, NULL);
1343                 }
1344         }
1345 }
1346
1347 void free_node(node_t *n)
1348 {
1349         if (n == NULL) {
1350                 return;
1351         }
1352         node_t *first_child = n->first_child;
1353         node_t *second_child = n->second_child;
1354         free(n->client);
1355         free(n);
1356         free_node(first_child);
1357         free_node(second_child);
1358 }
1359
1360 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2, bool follow)
1361 {
1362         if (n1 == NULL || n2 == NULL || n1 == n2 || is_descendant(n1, n2) || is_descendant(n2, n1) ||
1363             (d1 != d2 && ((m1->sticky_count > 0 && sticky_count(n1) > 0) ||
1364                           (m2->sticky_count > 0 && sticky_count(n2) > 0)))) {
1365                 return false;
1366         }
1367
1368         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);
1369
1370         node_t *pn1 = n1->parent;
1371         node_t *pn2 = n2->parent;
1372         bool n1_first_child = is_first_child(n1);
1373         bool n2_first_child = is_first_child(n2);
1374         bool n1_held_focus = is_descendant(d1->focus, n1);
1375         bool n2_held_focus = is_descendant(d2->focus, n2);
1376         node_t *last_d1_focus = d1->focus;
1377         node_t *last_d2_focus = d2->focus;
1378
1379         if (pn1 != NULL) {
1380                 if (n1_first_child) {
1381                         pn1->first_child = n2;
1382                 } else {
1383                         pn1->second_child = n2;
1384                 }
1385         }
1386
1387         if (pn2 != NULL) {
1388                 if (n2_first_child) {
1389                         pn2->first_child = n1;
1390                 } else {
1391                         pn2->second_child = n1;
1392                 }
1393         }
1394
1395         n1->parent = pn2;
1396         n2->parent = pn1;
1397
1398         propagate_flags_upward(m2, d2, n1);
1399         propagate_flags_upward(m1, d1, n2);
1400
1401         if (d1 != d2) {
1402                 if (d1->root == n1) {
1403                         d1->root = n2;
1404                 }
1405
1406                 if (d2->root == n2) {
1407                         d2->root = n1;
1408                 }
1409
1410                 if (n1_held_focus) {
1411                         d1->focus = n2_held_focus ? last_d2_focus : n2;
1412                 }
1413
1414                 if (n2_held_focus) {
1415                         d2->focus = n1_held_focus ? last_d1_focus : n1;
1416                 }
1417
1418                 if (m1 != m2) {
1419                         adapt_geometry(&m2->rectangle, &m1->rectangle, n2);
1420                         adapt_geometry(&m1->rectangle, &m2->rectangle, n1);
1421                 }
1422
1423                 ewmh_set_wm_desktop(n1, d2);
1424                 ewmh_set_wm_desktop(n2, d1);
1425
1426                 history_remove(d1, n1, true);
1427                 history_remove(d2, n2, true);
1428
1429                 bool d1_was_focused = (d1 == mon->desk);
1430                 bool d2_was_focused = (d2 == mon->desk);
1431
1432                 if (m1->desk != d1 && m2->desk == d2) {
1433                         show_node(d2, n1);
1434                         if (!follow || !d2_was_focused || !n2_held_focus) {
1435                                 hide_node(d2, n2);
1436                         }
1437                 } else if (m1->desk == d1 && m2->desk != d2) {
1438                         if (!follow || !d1_was_focused || !n1_held_focus) {
1439                                 hide_node(d1, n1);
1440                         }
1441                         show_node(d1, n2);
1442                 }
1443
1444                 if (single_monocle) {
1445                         layout_t l1 = tiled_count(d1->root, true) <= 1 ? LAYOUT_MONOCLE : d1->user_layout;
1446                         layout_t l2 = tiled_count(d2->root, true) <= 1 ? LAYOUT_MONOCLE : d2->user_layout;
1447                         set_layout(m1, d1, l1, false);
1448                         set_layout(m2, d2, l2, false);
1449                 }
1450
1451                 if (n1_held_focus) {
1452                         if (d1_was_focused) {
1453                                 if (follow) {
1454                                         focus_node(m2, d2, last_d1_focus);
1455                                 } else {
1456                                         focus_node(m1, d1, d1->focus);
1457                                 }
1458                         } else {
1459                                 activate_node(m1, d1, d1->focus);
1460                         }
1461                 } else {
1462                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1463                 }
1464
1465                 if (n2_held_focus) {
1466                         if (d2_was_focused) {
1467                                 if (follow) {
1468                                         focus_node(m1, d1, last_d2_focus);
1469                                 } else {
1470                                         focus_node(m2, d2, d2->focus);
1471                                 }
1472                         } else {
1473                                 activate_node(m2, d2, d2->focus);
1474                         }
1475                 } else {
1476                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1477                 }
1478         } else {
1479                 draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1480                 draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1481         }
1482
1483         arrange(m1, d1);
1484
1485         if (d1 != d2) {
1486                 arrange(m2, d2);
1487         }
1488
1489         return true;
1490 }
1491
1492 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd, bool follow)
1493 {
1494         if (ns == NULL || ns == nd || is_child(ns, nd) || is_descendant(nd, ns)) {
1495                 return false;
1496         }
1497
1498         if (sticky_still && ms->sticky_count > 0 && sticky_count(ns) > 0 && dd != md->desk) {
1499                 return false;
1500         }
1501
1502         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);
1503
1504         bool held_focus = is_descendant(ds->focus, ns);
1505         /* avoid ending up with a dangling pointer (because of unlink_node) */
1506         node_t *last_ds_focus = is_child(ns, ds->focus) ? NULL : ds->focus;
1507         bool ds_was_focused = (ds == mon->desk);
1508
1509         if (held_focus && ds_was_focused) {
1510                 clear_input_focus();
1511         }
1512
1513         unlink_node(ms, ds, ns);
1514         insert_node(md, dd, ns, nd);
1515
1516         if (md != ms) {
1517                 if (ns->client == NULL || monitor_from_client(ns->client) != md) {
1518                         adapt_geometry(&ms->rectangle, &md->rectangle, ns);
1519                 }
1520         }
1521
1522         if (ds != dd) {
1523                 ewmh_set_wm_desktop(ns, dd);
1524                 if (sticky_still) {
1525                         if (ds == ms->desk && dd != md->desk) {
1526                                 hide_node(ds, ns);
1527                         } else if (ds != ms->desk && dd == md->desk) {
1528                                 show_node(dd, ns);
1529                         }
1530                 }
1531         }
1532
1533         history_remove(ds, ns, true);
1534         stack(dd, ns, false);
1535
1536         if (ds == dd) {
1537                 if (held_focus) {
1538                         if (ds_was_focused) {
1539                                 focus_node(ms, ds, last_ds_focus);
1540                         } else {
1541                                 activate_node(ms, ds, last_ds_focus);
1542                         }
1543                 } else {
1544                         draw_border(ns, is_descendant(ns, ds->focus), (ms == mon));
1545                 }
1546         } else {
1547                 if (single_monocle) {
1548                         if (ds->layout != LAYOUT_MONOCLE && tiled_count(ds->root, true) <= 1) {
1549                                 set_layout(ms, ds, LAYOUT_MONOCLE, false);
1550                         }
1551                         if (dd->layout == LAYOUT_MONOCLE && tiled_count(dd->root, true) > 1) {
1552                                 set_layout(md, dd, dd->user_layout, false);
1553                         }
1554                 }
1555                 if (held_focus) {
1556                         if (follow) {
1557                                 if (ds_was_focused) {
1558                                         focus_node(md, dd, last_ds_focus);
1559                                 }
1560                                 activate_node(ms, ds, ds->focus);
1561                         } else {
1562                                 if (ds_was_focused) {
1563                                         focus_node(ms, ds, ds->focus);
1564                                 } else {
1565                                         activate_node(ms, ds, ds->focus);
1566                                 }
1567                         }
1568                 }
1569                 if (!held_focus || !follow || !ds_was_focused) {
1570                         if (dd->focus == ns) {
1571                                 if (dd == mon->desk) {
1572                                         focus_node(md, dd, held_focus ? last_ds_focus : ns);
1573                                 } else {
1574                                         activate_node(md, dd, held_focus ? last_ds_focus : ns);
1575                                 }
1576                         } else {
1577                                 draw_border(ns, is_descendant(ns, dd->focus), (md == mon));
1578                         }
1579                 }
1580         }
1581
1582         arrange(ms, ds);
1583
1584         if (ds != dd) {
1585                 arrange(md, dd);
1586         }
1587
1588         return true;
1589 }
1590
1591 bool find_closest_node(coordinates_t *ref, coordinates_t *dst, cycle_dir_t dir, node_select_t *sel)
1592 {
1593         monitor_t *m = ref->monitor;
1594         desktop_t *d = ref->desktop;
1595         node_t *n = ref->node;
1596         n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1597
1598 #define HANDLE_BOUNDARIES(m, d, n)  \
1599         while (n == NULL) { \
1600                 d = (dir == CYCLE_PREV ? d->prev : d->next); \
1601                 if (d == NULL) { \
1602                         m = (dir == CYCLE_PREV ? m->prev : m->next); \
1603                         if (m == NULL) { \
1604                                 m = (dir == CYCLE_PREV ? mon_tail : mon_head); \
1605                         } \
1606                         d = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head); \
1607                 } \
1608                 n = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root)); \
1609                 if (ref->node == NULL && d == ref->desktop) { \
1610                         break; \
1611                 } \
1612         }
1613         HANDLE_BOUNDARIES(m, d, n);
1614
1615         while (n != ref->node) {
1616                 coordinates_t loc = {m, d, n};
1617                 if (n->client != NULL && !n->hidden && node_matches(&loc, ref, sel)) {
1618                         *dst = loc;
1619                         return true;
1620                 }
1621                 n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1622                 HANDLE_BOUNDARIES(m, d, n);
1623         }
1624 #undef HANDLE_BOUNDARIES
1625         return false;
1626 }
1627
1628 void circulate_leaves(monitor_t *m, desktop_t *d, node_t *n, circulate_dir_t dir)
1629 {
1630         if (tiled_count(n, false) < 2) {
1631                 return;
1632         }
1633         node_t *p = d->focus->parent;
1634         bool focus_first_child = is_first_child(d->focus);
1635         if (dir == CIRCULATE_FORWARD) {
1636                 node_t *e = second_extrema(n);
1637                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1638                         e = prev_leaf(e, n);
1639                 }
1640                 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)) {
1641                         swap_nodes(m, d, f, m, d, s, false);
1642                 }
1643         } else {
1644                 node_t *e = first_extrema(n);
1645                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1646                         e = next_leaf(e, n);
1647                 }
1648                 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)) {
1649                         swap_nodes(m, d, f, m, d, s, false);
1650                 }
1651         }
1652         if (p != NULL) {
1653                 node_t *f = focus_first_child ? p->first_child : p->second_child;
1654                 if (is_leaf(f)) {
1655                         if (d == mon->desk) {
1656                                 focus_node(m, d, f);
1657                         } else {
1658                                 activate_node(m, d, f);
1659                         }
1660                 }
1661         }
1662 }
1663
1664 void set_vacant(monitor_t *m, desktop_t *d, node_t *n, bool value)
1665 {
1666         if (n->vacant == value) {
1667                 return;
1668         }
1669
1670         propagate_vacant_downward(m, d, n, value);
1671         propagate_vacant_upward(m, d, n);
1672 }
1673
1674 void set_vacant_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1675 {
1676         if (n->vacant == value) {
1677                 return;
1678         }
1679
1680         n->vacant = value;
1681
1682         if (value) {
1683                 cancel_presel(m, d, n);
1684         }
1685 }
1686
1687 void propagate_vacant_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1688 {
1689         if (n == NULL) {
1690                 return;
1691         }
1692
1693         set_vacant_local(m, d, n, value);
1694
1695         propagate_vacant_downward(m, d, n->first_child, value);
1696         propagate_vacant_downward(m, d, n->second_child, value);
1697 }
1698
1699 void propagate_vacant_upward(monitor_t *m, desktop_t *d, node_t *n)
1700 {
1701         if (n == NULL) {
1702                 return;
1703         }
1704
1705         node_t *p = n->parent;
1706
1707         if (p != NULL) {
1708                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1709         }
1710
1711         propagate_vacant_upward(m, d, p);
1712 }
1713
1714 bool set_layer(monitor_t *m, desktop_t *d, node_t *n, stack_layer_t l)
1715 {
1716         if (n == NULL || n->client == NULL || n->client->layer == l) {
1717                 return false;
1718         }
1719
1720         n->client->last_layer = n->client->layer;
1721         n->client->layer = l;
1722
1723         if (l == LAYER_ABOVE) {
1724                 n->client->wm_flags |= WM_FLAG_ABOVE;
1725                 n->client->wm_flags &= ~WM_FLAG_BELOW;
1726         } else if (l == LAYER_BELOW) {
1727                 n->client->wm_flags |= WM_FLAG_BELOW;
1728                 n->client->wm_flags &= ~WM_FLAG_ABOVE;
1729         } else {
1730                 n->client->wm_flags &= ~(WM_FLAG_ABOVE | WM_FLAG_BELOW);
1731         }
1732
1733         ewmh_wm_state_update(n);
1734
1735         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));
1736
1737         if (d->focus == n) {
1738                 neutralize_occluding_windows(m, d, n);
1739         }
1740
1741         stack(d, n, (d->focus == n));
1742
1743         return true;
1744 }
1745
1746 bool set_state(monitor_t *m, desktop_t *d, node_t *n, client_state_t s)
1747 {
1748         if (n == NULL || n->client == NULL || n->client->state == s) {
1749                 return false;
1750         }
1751
1752         client_t *c = n->client;
1753
1754         bool was_tiled = IS_TILED(c);
1755
1756         c->last_state = c->state;
1757         c->state = s;
1758
1759         switch (c->last_state) {
1760                 case STATE_TILED:
1761                 case STATE_PSEUDO_TILED:
1762                         break;
1763                 case STATE_FLOATING:
1764                         set_floating(m, d, n, false);
1765                         break;
1766                 case STATE_FULLSCREEN:
1767                         set_fullscreen(m, d, n, false);
1768                         break;
1769         }
1770
1771         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));
1772
1773         switch (c->state) {
1774                 case STATE_TILED:
1775                 case STATE_PSEUDO_TILED:
1776                         break;
1777                 case STATE_FLOATING:
1778                         set_floating(m, d, n, true);
1779                         break;
1780                 case STATE_FULLSCREEN:
1781                         set_fullscreen(m, d, n, true);
1782                         break;
1783         }
1784
1785         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));
1786
1787         if (n == m->desk->focus) {
1788                 put_status(SBSC_MASK_REPORT);
1789         }
1790
1791         if (single_monocle && was_tiled != IS_TILED(c)) {
1792                 if (was_tiled && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1793                         set_layout(m, d, LAYOUT_MONOCLE, false);
1794                 } else if (!was_tiled && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
1795                         set_layout(m, d, d->user_layout, false);
1796                 }
1797         }
1798
1799         return true;
1800 }
1801
1802 void set_floating(monitor_t *m, desktop_t *d, node_t *n, bool value)
1803 {
1804         if (n == NULL) {
1805                 return;
1806         }
1807
1808         cancel_presel(m, d, n);
1809         set_vacant(m, d, n, value);
1810
1811         if (!value && d->focus == n) {
1812                 neutralize_occluding_windows(m, d, n);
1813         }
1814
1815         stack(d, n, (d->focus == n));
1816 }
1817
1818 void set_fullscreen(monitor_t *m, desktop_t *d, node_t *n, bool value)
1819 {
1820         if (n == NULL) {
1821                 return;
1822         }
1823
1824         client_t *c = n->client;
1825
1826         cancel_presel(m, d, n);
1827         set_vacant(m, d, n, value);
1828
1829         if (value) {
1830                 c->wm_flags |= WM_FLAG_FULLSCREEN;
1831         } else {
1832                 c->wm_flags &= ~WM_FLAG_FULLSCREEN;
1833                 if (d->focus == n) {
1834                         neutralize_occluding_windows(m, d, n);
1835                 }
1836         }
1837
1838         ewmh_wm_state_update(n);
1839         stack(d, n, (d->focus == n));
1840 }
1841
1842 void neutralize_occluding_windows(monitor_t *m, desktop_t *d, node_t *n)
1843 {
1844         bool changed = false;
1845         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1846                 for (node_t *a = first_extrema(d->root); a != NULL; a = next_leaf(a, d->root)) {
1847                         if (a != f && a->client != NULL && f->client != NULL &&
1848                             IS_FULLSCREEN(a->client) && stack_cmp(f->client, a->client) < 0) {
1849                                 set_state(m, d, a, a->client->last_state);
1850                                 changed = true;
1851                         }
1852                 }
1853         }
1854         if (changed) {
1855                 arrange(m, d);
1856         }
1857 }
1858
1859 void rebuild_constraints(node_t *n)
1860 {
1861         if (n == NULL || is_leaf(n)) {
1862                 return;
1863         } else {
1864                 rebuild_constraints(n->first_child);
1865                 rebuild_constraints(n->second_child);
1866                 update_constraints(n);
1867         }
1868 }
1869
1870 void update_constraints(node_t *n)
1871 {
1872         if (n == NULL || is_leaf(n)) {
1873                 return;
1874         }
1875         if (n->split_type == TYPE_VERTICAL) {
1876                 n->constraints.min_width = n->first_child->constraints.min_width + n->second_child->constraints.min_width;
1877                 n->constraints.min_height = MAX(n->first_child->constraints.min_height, n->second_child->constraints.min_height);
1878         } else {
1879                 n->constraints.min_width = MAX(n->first_child->constraints.min_width, n->second_child->constraints.min_width);
1880                 n->constraints.min_height = n->first_child->constraints.min_height + n->second_child->constraints.min_height;
1881         }
1882 }
1883
1884 void propagate_flags_upward(monitor_t *m, desktop_t *d, node_t *n)
1885 {
1886         if (n == NULL) {
1887                 return;
1888         }
1889
1890         node_t *p = n->parent;
1891
1892         if (p != NULL) {
1893                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1894                 set_hidden_local(m, d, p, (p->first_child->hidden && p->second_child->hidden));
1895                 update_constraints(p);
1896         }
1897
1898         propagate_flags_upward(m, d, p);
1899 }
1900
1901 void set_hidden(monitor_t *m, desktop_t *d, node_t *n, bool value)
1902 {
1903         if (n == NULL || n->hidden == value) {
1904                 return;
1905         }
1906
1907         bool held_focus = is_descendant(d->focus, n);
1908
1909         propagate_hidden_downward(m, d, n, value);
1910         propagate_hidden_upward(m, d, n);
1911
1912         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));
1913
1914         if (held_focus || d->focus == NULL) {
1915                 if (d->focus != NULL) {
1916                         d->focus = NULL;
1917                         draw_border(n, false, (mon == m));
1918                 }
1919                 if (d == mon->desk) {
1920                         focus_node(m, d, d->focus);
1921                 } else {
1922                         activate_node(m, d, d->focus);
1923                 }
1924         }
1925 }
1926
1927 void set_hidden_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1928 {
1929         if (n->hidden == value) {
1930                 return;
1931         }
1932
1933         n->hidden = value;
1934
1935         if (n->client != NULL) {
1936                 if (n->client->shown) {
1937                         window_set_visibility(n->id, !value);
1938                 }
1939
1940                 if (IS_TILED(n->client)) {
1941                         set_vacant(m, d, n, value);
1942                 }
1943
1944                 if (value) {
1945                         n->client->wm_flags |= WM_FLAG_HIDDEN;
1946                 } else {
1947                         n->client->wm_flags &= ~WM_FLAG_HIDDEN;
1948                 }
1949
1950                 ewmh_wm_state_update(n);
1951         }
1952 }
1953
1954 void propagate_hidden_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1955 {
1956         if (n == NULL) {
1957                 return;
1958         }
1959
1960         set_hidden_local(m, d, n, value);
1961
1962         propagate_hidden_downward(m, d, n->first_child, value);
1963         propagate_hidden_downward(m, d, n->second_child, value);
1964 }
1965
1966 void propagate_hidden_upward(monitor_t *m, desktop_t *d, node_t *n)
1967 {
1968         if (n == NULL) {
1969                 return;
1970         }
1971
1972         node_t *p = n->parent;
1973
1974         if (p != NULL) {
1975                 set_hidden_local(m, d, p, p->first_child->hidden && p->second_child->hidden);
1976         }
1977
1978         propagate_hidden_upward(m, d, p);
1979 }
1980
1981 void set_sticky(monitor_t *m, desktop_t *d, node_t *n, bool value)
1982 {
1983         if (n == NULL || n->sticky == value) {
1984                 return;
1985         }
1986
1987         if (d != m->desk) {
1988                 transfer_node(m, d, n, m, m->desk, m->desk->focus, false);
1989         }
1990
1991         n->sticky = value;
1992
1993         if (value) {
1994                 m->sticky_count++;
1995         } else {
1996                 m->sticky_count--;
1997         }
1998
1999         if (n->client != NULL) {
2000                 if (value) {
2001                         n->client->wm_flags |= WM_FLAG_STICKY;
2002                 } else {
2003                         n->client->wm_flags &= ~WM_FLAG_STICKY;
2004                 }
2005                 ewmh_wm_state_update(n);
2006         }
2007
2008         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));
2009
2010         if (n == m->desk->focus) {
2011                 put_status(SBSC_MASK_REPORT);
2012         }
2013 }
2014
2015 void set_private(monitor_t *m, desktop_t *d, node_t *n, bool value)
2016 {
2017         if (n == NULL || n->private == value) {
2018                 return;
2019         }
2020
2021         n->private = value;
2022
2023         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));
2024
2025         if (n == m->desk->focus) {
2026                 put_status(SBSC_MASK_REPORT);
2027         }
2028 }
2029
2030 void set_locked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2031 {
2032         if (n == NULL || n->locked == value) {
2033                 return;
2034         }
2035
2036         n->locked = value;
2037
2038         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));
2039
2040         if (n == m->desk->focus) {
2041                 put_status(SBSC_MASK_REPORT);
2042         }
2043 }
2044
2045 void set_marked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2046 {
2047         if (n == NULL || n->marked == value) {
2048                 return;
2049         }
2050
2051         n->marked = value;
2052
2053         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));
2054
2055         if (n == m->desk->focus) {
2056                 put_status(SBSC_MASK_REPORT);
2057         }
2058 }
2059
2060 void set_urgent(monitor_t *m, desktop_t *d, node_t *n, bool value)
2061 {
2062         if (value && mon->desk->focus == n) {
2063                 return;
2064         }
2065
2066         n->client->urgent = value;
2067
2068         if (value) {
2069                 n->client->wm_flags |= WM_FLAG_DEMANDS_ATTENTION;
2070         } else {
2071                 n->client->wm_flags &= ~WM_FLAG_DEMANDS_ATTENTION;
2072         }
2073
2074         ewmh_wm_state_update(n);
2075
2076         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));
2077         put_status(SBSC_MASK_REPORT);
2078 }
2079
2080 xcb_rectangle_t get_rectangle(monitor_t *m, desktop_t *d, node_t *n)
2081 {
2082         if (n == NULL) {
2083                 return m->rectangle;
2084         }
2085         client_t *c = n->client;
2086         if (c != NULL) {
2087                 if (IS_FLOATING(c)) {
2088                         return c->floating_rectangle;
2089                 } else {
2090                         return c->tiled_rectangle;
2091                 }
2092         } else {
2093                 int wg = (d == NULL ? 0 : (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap));
2094                 xcb_rectangle_t rect = n->rectangle;
2095                 rect.width -= wg;
2096                 rect.height -= wg;
2097                 return rect;
2098         }
2099 }
2100
2101 void listen_enter_notify(node_t *n, bool enable)
2102 {
2103         uint32_t mask = CLIENT_EVENT_MASK | (enable ? XCB_EVENT_MASK_ENTER_WINDOW : 0);
2104         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
2105                 if (f->client == NULL) {
2106                         continue;
2107                 }
2108                 xcb_change_window_attributes(dpy, f->id, XCB_CW_EVENT_MASK, &mask);
2109                 if (f->presel != NULL) {
2110                         xcb_change_window_attributes(dpy, f->presel->feedback, XCB_CW_EVENT_MASK, &mask);
2111                 }
2112         }
2113 }
2114
2115 void regenerate_ids_in(node_t *n)
2116 {
2117         if (n == NULL || n->client != NULL) {
2118                 return;
2119         }
2120         n->id = xcb_generate_id(dpy);
2121         regenerate_ids_in(n->first_child);
2122         regenerate_ids_in(n->second_child);
2123 }
2124
2125 #define DEF_FLAG_COUNT(flag) \
2126         unsigned int flag##_count(node_t *n) \
2127         { \
2128                 if (n == NULL) { \
2129                         return 0; \
2130                 } else { \
2131                         return ((n->flag ? 1 : 0) + \
2132                                 flag##_count(n->first_child) + \
2133                                 flag##_count(n->second_child)); \
2134                 } \
2135         }
2136         DEF_FLAG_COUNT(sticky)
2137         DEF_FLAG_COUNT(private)
2138         DEF_FLAG_COUNT(locked)
2139 #undef DEF_FLAG_COUNT