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_SPIRAL) {
1258                                 if (is_first_child(n)) {
1259                                         rotate_tree(b, 270);
1260                                 } else {
1261                                         rotate_tree(b, 90);
1262                                 }
1263                         } else if (automatic_scheme == SCHEME_LONGEST_SIDE || g == NULL) {
1264                                 if (p != NULL) {
1265                                         if (p->rectangle.width > p->rectangle.height) {
1266                                                 b->split_type = TYPE_VERTICAL;
1267                                         } else {
1268                                                 b->split_type = TYPE_HORIZONTAL;
1269                                         }
1270                                 }
1271                         } else if (automatic_scheme == SCHEME_ALTERNATE) {
1272                                 if (g->split_type == TYPE_HORIZONTAL) {
1273                                         b->split_type = TYPE_VERTICAL;
1274                                 } else {
1275                                         b->split_type = TYPE_HORIZONTAL;
1276                                 }
1277                         }
1278                 }
1279
1280                 free(p);
1281                 n->parent = NULL;
1282
1283                 propagate_flags_upward(m, d, b);
1284         }
1285 }
1286
1287 void close_node(node_t *n)
1288 {
1289         if (n == NULL) {
1290                 return;
1291         } else if (n->client != NULL) {
1292                 if (n->client->icccm_props.delete_window) {
1293                         send_client_message(n->id, ewmh->WM_PROTOCOLS, WM_DELETE_WINDOW);
1294                 } else {
1295                         xcb_kill_client(dpy, n->id);
1296                 }
1297         } else {
1298                 close_node(n->first_child);
1299                 close_node(n->second_child);
1300         }
1301 }
1302
1303 void kill_node(monitor_t *m, desktop_t *d, node_t *n)
1304 {
1305         if (n == NULL) {
1306                 return;
1307         }
1308
1309         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1310                 if (f->client != NULL) {
1311                         xcb_kill_client(dpy, f->id);
1312                 }
1313         }
1314
1315         remove_node(m, d, n);
1316 }
1317
1318 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
1319 {
1320         if (n == NULL) {
1321                 return;
1322         }
1323
1324         unlink_node(m, d, n);
1325         history_remove(d, n, true);
1326         remove_stack_node(n);
1327         cancel_presel_in(m, d, n);
1328         if (m->sticky_count > 0) {
1329                 m->sticky_count -= sticky_count(n);
1330         }
1331         clients_count -= clients_count_in(n);
1332         if (is_descendant(grabbed_node, n)) {
1333                 grabbed_node = NULL;
1334         }
1335         free_node(n);
1336
1337         if (single_monocle && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1338                 set_layout(m, d, LAYOUT_MONOCLE, false);
1339         }
1340
1341         ewmh_update_client_list(false);
1342         ewmh_update_client_list(true);
1343
1344         if (mon != NULL && d->focus == NULL) {
1345                 if (d == mon->desk) {
1346                         focus_node(m, d, NULL);
1347                 } else {
1348                         activate_node(m, d, NULL);
1349                 }
1350         }
1351 }
1352
1353 void free_node(node_t *n)
1354 {
1355         if (n == NULL) {
1356                 return;
1357         }
1358         node_t *first_child = n->first_child;
1359         node_t *second_child = n->second_child;
1360         free(n->client);
1361         free(n);
1362         free_node(first_child);
1363         free_node(second_child);
1364 }
1365
1366 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2, bool follow)
1367 {
1368         if (n1 == NULL || n2 == NULL || n1 == n2 || is_descendant(n1, n2) || is_descendant(n2, n1) ||
1369             (d1 != d2 && ((m1->sticky_count > 0 && sticky_count(n1) > 0) ||
1370                           (m2->sticky_count > 0 && sticky_count(n2) > 0)))) {
1371                 return false;
1372         }
1373
1374         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);
1375
1376         node_t *pn1 = n1->parent;
1377         node_t *pn2 = n2->parent;
1378         bool n1_first_child = is_first_child(n1);
1379         bool n2_first_child = is_first_child(n2);
1380         bool n1_held_focus = is_descendant(d1->focus, n1);
1381         bool n2_held_focus = is_descendant(d2->focus, n2);
1382         node_t *last_d1_focus = d1->focus;
1383         node_t *last_d2_focus = d2->focus;
1384
1385         if (pn1 != NULL) {
1386                 if (n1_first_child) {
1387                         pn1->first_child = n2;
1388                 } else {
1389                         pn1->second_child = n2;
1390                 }
1391         }
1392
1393         if (pn2 != NULL) {
1394                 if (n2_first_child) {
1395                         pn2->first_child = n1;
1396                 } else {
1397                         pn2->second_child = n1;
1398                 }
1399         }
1400
1401         n1->parent = pn2;
1402         n2->parent = pn1;
1403
1404         propagate_flags_upward(m2, d2, n1);
1405         propagate_flags_upward(m1, d1, n2);
1406
1407         if (d1 != d2) {
1408                 if (d1->root == n1) {
1409                         d1->root = n2;
1410                 }
1411
1412                 if (d2->root == n2) {
1413                         d2->root = n1;
1414                 }
1415
1416                 if (n1_held_focus) {
1417                         d1->focus = n2_held_focus ? last_d2_focus : n2;
1418                 }
1419
1420                 if (n2_held_focus) {
1421                         d2->focus = n1_held_focus ? last_d1_focus : n1;
1422                 }
1423
1424                 if (m1 != m2) {
1425                         adapt_geometry(&m2->rectangle, &m1->rectangle, n2);
1426                         adapt_geometry(&m1->rectangle, &m2->rectangle, n1);
1427                 }
1428
1429                 ewmh_set_wm_desktop(n1, d2);
1430                 ewmh_set_wm_desktop(n2, d1);
1431
1432                 history_remove(d1, n1, true);
1433                 history_remove(d2, n2, true);
1434
1435                 bool d1_was_focused = (d1 == mon->desk);
1436                 bool d2_was_focused = (d2 == mon->desk);
1437
1438                 if (m1->desk != d1 && m2->desk == d2) {
1439                         show_node(d2, n1);
1440                         if (!follow || !d2_was_focused || !n2_held_focus) {
1441                                 hide_node(d2, n2);
1442                         }
1443                 } else if (m1->desk == d1 && m2->desk != d2) {
1444                         if (!follow || !d1_was_focused || !n1_held_focus) {
1445                                 hide_node(d1, n1);
1446                         }
1447                         show_node(d1, n2);
1448                 }
1449
1450                 if (single_monocle) {
1451                         layout_t l1 = tiled_count(d1->root, true) <= 1 ? LAYOUT_MONOCLE : d1->user_layout;
1452                         layout_t l2 = tiled_count(d2->root, true) <= 1 ? LAYOUT_MONOCLE : d2->user_layout;
1453                         set_layout(m1, d1, l1, false);
1454                         set_layout(m2, d2, l2, false);
1455                 }
1456
1457                 if (n1_held_focus) {
1458                         if (d1_was_focused) {
1459                                 if (follow) {
1460                                         focus_node(m2, d2, last_d1_focus);
1461                                 } else {
1462                                         focus_node(m1, d1, d1->focus);
1463                                 }
1464                         } else {
1465                                 activate_node(m1, d1, d1->focus);
1466                         }
1467                 } else {
1468                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1469                 }
1470
1471                 if (n2_held_focus) {
1472                         if (d2_was_focused) {
1473                                 if (follow) {
1474                                         focus_node(m1, d1, last_d2_focus);
1475                                 } else {
1476                                         focus_node(m2, d2, d2->focus);
1477                                 }
1478                         } else {
1479                                 activate_node(m2, d2, d2->focus);
1480                         }
1481                 } else {
1482                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1483                 }
1484         } else {
1485                 draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1486                 draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1487         }
1488
1489         arrange(m1, d1);
1490
1491         if (d1 != d2) {
1492                 arrange(m2, d2);
1493         }
1494
1495         return true;
1496 }
1497
1498 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd, bool follow)
1499 {
1500         if (ns == NULL || ns == nd || is_child(ns, nd) || is_descendant(nd, ns)) {
1501                 return false;
1502         }
1503
1504         if (sticky_still && ms->sticky_count > 0 && sticky_count(ns) > 0 && dd != md->desk) {
1505                 return false;
1506         }
1507
1508         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);
1509
1510         bool held_focus = is_descendant(ds->focus, ns);
1511         /* avoid ending up with a dangling pointer (because of unlink_node) */
1512         node_t *last_ds_focus = is_child(ns, ds->focus) ? NULL : ds->focus;
1513         bool ds_was_focused = (ds == mon->desk);
1514
1515         if (held_focus && ds_was_focused) {
1516                 clear_input_focus();
1517         }
1518
1519         unlink_node(ms, ds, ns);
1520         insert_node(md, dd, ns, nd);
1521
1522         if (md != ms) {
1523                 if (ns->client == NULL || monitor_from_client(ns->client) != md) {
1524                         adapt_geometry(&ms->rectangle, &md->rectangle, ns);
1525                 }
1526         }
1527
1528         if (ds != dd) {
1529                 ewmh_set_wm_desktop(ns, dd);
1530                 if (sticky_still) {
1531                         if (ds == ms->desk && dd != md->desk) {
1532                                 hide_node(ds, ns);
1533                         } else if (ds != ms->desk && dd == md->desk) {
1534                                 show_node(dd, ns);
1535                         }
1536                 }
1537         }
1538
1539         history_remove(ds, ns, true);
1540         stack(dd, ns, false);
1541
1542         if (ds == dd) {
1543                 if (held_focus) {
1544                         if (ds_was_focused) {
1545                                 focus_node(ms, ds, last_ds_focus);
1546                         } else {
1547                                 activate_node(ms, ds, last_ds_focus);
1548                         }
1549                 } else {
1550                         draw_border(ns, is_descendant(ns, ds->focus), (ms == mon));
1551                 }
1552         } else {
1553                 if (single_monocle) {
1554                         if (ds->layout != LAYOUT_MONOCLE && tiled_count(ds->root, true) <= 1) {
1555                                 set_layout(ms, ds, LAYOUT_MONOCLE, false);
1556                         }
1557                         if (dd->layout == LAYOUT_MONOCLE && tiled_count(dd->root, true) > 1) {
1558                                 set_layout(md, dd, dd->user_layout, false);
1559                         }
1560                 }
1561                 if (held_focus) {
1562                         if (follow) {
1563                                 if (ds_was_focused) {
1564                                         focus_node(md, dd, last_ds_focus);
1565                                 }
1566                                 activate_node(ms, ds, ds->focus);
1567                         } else {
1568                                 if (ds_was_focused) {
1569                                         focus_node(ms, ds, ds->focus);
1570                                 } else {
1571                                         activate_node(ms, ds, ds->focus);
1572                                 }
1573                         }
1574                 }
1575                 if (!held_focus || !follow || !ds_was_focused) {
1576                         if (dd->focus == ns) {
1577                                 if (dd == mon->desk) {
1578                                         focus_node(md, dd, held_focus ? last_ds_focus : ns);
1579                                 } else {
1580                                         activate_node(md, dd, held_focus ? last_ds_focus : ns);
1581                                 }
1582                         } else {
1583                                 draw_border(ns, is_descendant(ns, dd->focus), (md == mon));
1584                         }
1585                 }
1586         }
1587
1588         arrange(ms, ds);
1589
1590         if (ds != dd) {
1591                 arrange(md, dd);
1592         }
1593
1594         return true;
1595 }
1596
1597 bool find_closest_node(coordinates_t *ref, coordinates_t *dst, cycle_dir_t dir, node_select_t *sel)
1598 {
1599         monitor_t *m = ref->monitor;
1600         desktop_t *d = ref->desktop;
1601         node_t *n = ref->node;
1602         n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1603
1604 #define HANDLE_BOUNDARIES(m, d, n)  \
1605         while (n == NULL) { \
1606                 d = (dir == CYCLE_PREV ? d->prev : d->next); \
1607                 if (d == NULL) { \
1608                         m = (dir == CYCLE_PREV ? m->prev : m->next); \
1609                         if (m == NULL) { \
1610                                 m = (dir == CYCLE_PREV ? mon_tail : mon_head); \
1611                         } \
1612                         d = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head); \
1613                 } \
1614                 n = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root)); \
1615                 if (ref->node == NULL && d == ref->desktop) { \
1616                         break; \
1617                 } \
1618         }
1619         HANDLE_BOUNDARIES(m, d, n);
1620
1621         while (n != ref->node) {
1622                 coordinates_t loc = {m, d, n};
1623                 if (n->client != NULL && !n->hidden && node_matches(&loc, ref, sel)) {
1624                         *dst = loc;
1625                         return true;
1626                 }
1627                 n = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1628                 HANDLE_BOUNDARIES(m, d, n);
1629         }
1630 #undef HANDLE_BOUNDARIES
1631         return false;
1632 }
1633
1634 void circulate_leaves(monitor_t *m, desktop_t *d, node_t *n, circulate_dir_t dir)
1635 {
1636         if (tiled_count(n, false) < 2) {
1637                 return;
1638         }
1639         node_t *p = d->focus->parent;
1640         bool focus_first_child = is_first_child(d->focus);
1641         if (dir == CIRCULATE_FORWARD) {
1642                 node_t *e = second_extrema(n);
1643                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1644                         e = prev_leaf(e, n);
1645                 }
1646                 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)) {
1647                         swap_nodes(m, d, f, m, d, s, false);
1648                 }
1649         } else {
1650                 node_t *e = first_extrema(n);
1651                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1652                         e = next_leaf(e, n);
1653                 }
1654                 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)) {
1655                         swap_nodes(m, d, f, m, d, s, false);
1656                 }
1657         }
1658         if (p != NULL) {
1659                 node_t *f = focus_first_child ? p->first_child : p->second_child;
1660                 if (is_leaf(f)) {
1661                         if (d == mon->desk) {
1662                                 focus_node(m, d, f);
1663                         } else {
1664                                 activate_node(m, d, f);
1665                         }
1666                 }
1667         }
1668 }
1669
1670 void set_vacant(monitor_t *m, desktop_t *d, node_t *n, bool value)
1671 {
1672         if (n->vacant == value) {
1673                 return;
1674         }
1675
1676         propagate_vacant_downward(m, d, n, value);
1677         propagate_vacant_upward(m, d, n);
1678 }
1679
1680 void set_vacant_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1681 {
1682         if (n->vacant == value) {
1683                 return;
1684         }
1685
1686         n->vacant = value;
1687
1688         if (value) {
1689                 cancel_presel(m, d, n);
1690         }
1691 }
1692
1693 void propagate_vacant_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1694 {
1695         if (n == NULL) {
1696                 return;
1697         }
1698
1699         set_vacant_local(m, d, n, value);
1700
1701         propagate_vacant_downward(m, d, n->first_child, value);
1702         propagate_vacant_downward(m, d, n->second_child, value);
1703 }
1704
1705 void propagate_vacant_upward(monitor_t *m, desktop_t *d, node_t *n)
1706 {
1707         if (n == NULL) {
1708                 return;
1709         }
1710
1711         node_t *p = n->parent;
1712
1713         if (p != NULL) {
1714                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1715         }
1716
1717         propagate_vacant_upward(m, d, p);
1718 }
1719
1720 bool set_layer(monitor_t *m, desktop_t *d, node_t *n, stack_layer_t l)
1721 {
1722         if (n == NULL || n->client == NULL || n->client->layer == l) {
1723                 return false;
1724         }
1725
1726         n->client->last_layer = n->client->layer;
1727         n->client->layer = l;
1728
1729         if (l == LAYER_ABOVE) {
1730                 n->client->wm_flags |= WM_FLAG_ABOVE;
1731                 n->client->wm_flags &= ~WM_FLAG_BELOW;
1732         } else if (l == LAYER_BELOW) {
1733                 n->client->wm_flags |= WM_FLAG_BELOW;
1734                 n->client->wm_flags &= ~WM_FLAG_ABOVE;
1735         } else {
1736                 n->client->wm_flags &= ~(WM_FLAG_ABOVE | WM_FLAG_BELOW);
1737         }
1738
1739         ewmh_wm_state_update(n);
1740
1741         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));
1742
1743         if (d->focus == n) {
1744                 neutralize_occluding_windows(m, d, n);
1745         }
1746
1747         stack(d, n, (d->focus == n));
1748
1749         return true;
1750 }
1751
1752 bool set_state(monitor_t *m, desktop_t *d, node_t *n, client_state_t s)
1753 {
1754         if (n == NULL || n->client == NULL || n->client->state == s) {
1755                 return false;
1756         }
1757
1758         client_t *c = n->client;
1759
1760         bool was_tiled = IS_TILED(c);
1761
1762         c->last_state = c->state;
1763         c->state = s;
1764
1765         switch (c->last_state) {
1766                 case STATE_TILED:
1767                 case STATE_PSEUDO_TILED:
1768                         break;
1769                 case STATE_FLOATING:
1770                         set_floating(m, d, n, false);
1771                         break;
1772                 case STATE_FULLSCREEN:
1773                         set_fullscreen(m, d, n, false);
1774                         break;
1775         }
1776
1777         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));
1778
1779         switch (c->state) {
1780                 case STATE_TILED:
1781                 case STATE_PSEUDO_TILED:
1782                         break;
1783                 case STATE_FLOATING:
1784                         set_floating(m, d, n, true);
1785                         break;
1786                 case STATE_FULLSCREEN:
1787                         set_fullscreen(m, d, n, true);
1788                         break;
1789         }
1790
1791         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));
1792
1793         if (n == m->desk->focus) {
1794                 put_status(SBSC_MASK_REPORT);
1795         }
1796
1797         if (single_monocle && was_tiled != IS_TILED(c)) {
1798                 if (was_tiled && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1799                         set_layout(m, d, LAYOUT_MONOCLE, false);
1800                 } else if (!was_tiled && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
1801                         set_layout(m, d, d->user_layout, false);
1802                 }
1803         }
1804
1805         return true;
1806 }
1807
1808 void set_floating(monitor_t *m, desktop_t *d, node_t *n, bool value)
1809 {
1810         if (n == NULL) {
1811                 return;
1812         }
1813
1814         cancel_presel(m, d, n);
1815         set_vacant(m, d, n, value);
1816
1817         if (!value && d->focus == n) {
1818                 neutralize_occluding_windows(m, d, n);
1819         }
1820
1821         stack(d, n, (d->focus == n));
1822 }
1823
1824 void set_fullscreen(monitor_t *m, desktop_t *d, node_t *n, bool value)
1825 {
1826         if (n == NULL) {
1827                 return;
1828         }
1829
1830         client_t *c = n->client;
1831
1832         cancel_presel(m, d, n);
1833         set_vacant(m, d, n, value);
1834
1835         if (value) {
1836                 c->wm_flags |= WM_FLAG_FULLSCREEN;
1837         } else {
1838                 c->wm_flags &= ~WM_FLAG_FULLSCREEN;
1839                 if (d->focus == n) {
1840                         neutralize_occluding_windows(m, d, n);
1841                 }
1842         }
1843
1844         ewmh_wm_state_update(n);
1845         stack(d, n, (d->focus == n));
1846 }
1847
1848 void neutralize_occluding_windows(monitor_t *m, desktop_t *d, node_t *n)
1849 {
1850         bool changed = false;
1851         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1852                 for (node_t *a = first_extrema(d->root); a != NULL; a = next_leaf(a, d->root)) {
1853                         if (a != f && a->client != NULL && f->client != NULL &&
1854                             IS_FULLSCREEN(a->client) && stack_cmp(f->client, a->client) < 0) {
1855                                 set_state(m, d, a, a->client->last_state);
1856                                 changed = true;
1857                         }
1858                 }
1859         }
1860         if (changed) {
1861                 arrange(m, d);
1862         }
1863 }
1864
1865 void rebuild_constraints(node_t *n)
1866 {
1867         if (n == NULL || is_leaf(n)) {
1868                 return;
1869         } else {
1870                 rebuild_constraints(n->first_child);
1871                 rebuild_constraints(n->second_child);
1872                 update_constraints(n);
1873         }
1874 }
1875
1876 void update_constraints(node_t *n)
1877 {
1878         if (n == NULL || is_leaf(n)) {
1879                 return;
1880         }
1881         if (n->split_type == TYPE_VERTICAL) {
1882                 n->constraints.min_width = n->first_child->constraints.min_width + n->second_child->constraints.min_width;
1883                 n->constraints.min_height = MAX(n->first_child->constraints.min_height, n->second_child->constraints.min_height);
1884         } else {
1885                 n->constraints.min_width = MAX(n->first_child->constraints.min_width, n->second_child->constraints.min_width);
1886                 n->constraints.min_height = n->first_child->constraints.min_height + n->second_child->constraints.min_height;
1887         }
1888 }
1889
1890 void propagate_flags_upward(monitor_t *m, desktop_t *d, node_t *n)
1891 {
1892         if (n == NULL) {
1893                 return;
1894         }
1895
1896         node_t *p = n->parent;
1897
1898         if (p != NULL) {
1899                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1900                 set_hidden_local(m, d, p, (p->first_child->hidden && p->second_child->hidden));
1901                 update_constraints(p);
1902         }
1903
1904         propagate_flags_upward(m, d, p);
1905 }
1906
1907 void set_hidden(monitor_t *m, desktop_t *d, node_t *n, bool value)
1908 {
1909         if (n == NULL || n->hidden == value) {
1910                 return;
1911         }
1912
1913         bool held_focus = is_descendant(d->focus, n);
1914
1915         propagate_hidden_downward(m, d, n, value);
1916         propagate_hidden_upward(m, d, n);
1917
1918         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));
1919
1920         if (held_focus || d->focus == NULL) {
1921                 if (d->focus != NULL) {
1922                         d->focus = NULL;
1923                         draw_border(n, false, (mon == m));
1924                 }
1925                 if (d == mon->desk) {
1926                         focus_node(m, d, d->focus);
1927                 } else {
1928                         activate_node(m, d, d->focus);
1929                 }
1930         }
1931 }
1932
1933 void set_hidden_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1934 {
1935         if (n->hidden == value) {
1936                 return;
1937         }
1938
1939         n->hidden = value;
1940
1941         if (n->client != NULL) {
1942                 if (n->client->shown) {
1943                         window_set_visibility(n->id, !value);
1944                 }
1945
1946                 if (IS_TILED(n->client)) {
1947                         set_vacant(m, d, n, value);
1948                 }
1949
1950                 if (value) {
1951                         n->client->wm_flags |= WM_FLAG_HIDDEN;
1952                 } else {
1953                         n->client->wm_flags &= ~WM_FLAG_HIDDEN;
1954                 }
1955
1956                 ewmh_wm_state_update(n);
1957         }
1958 }
1959
1960 void propagate_hidden_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1961 {
1962         if (n == NULL) {
1963                 return;
1964         }
1965
1966         set_hidden_local(m, d, n, value);
1967
1968         propagate_hidden_downward(m, d, n->first_child, value);
1969         propagate_hidden_downward(m, d, n->second_child, value);
1970 }
1971
1972 void propagate_hidden_upward(monitor_t *m, desktop_t *d, node_t *n)
1973 {
1974         if (n == NULL) {
1975                 return;
1976         }
1977
1978         node_t *p = n->parent;
1979
1980         if (p != NULL) {
1981                 set_hidden_local(m, d, p, p->first_child->hidden && p->second_child->hidden);
1982         }
1983
1984         propagate_hidden_upward(m, d, p);
1985 }
1986
1987 void set_sticky(monitor_t *m, desktop_t *d, node_t *n, bool value)
1988 {
1989         if (n == NULL || n->sticky == value) {
1990                 return;
1991         }
1992
1993         if (d != m->desk) {
1994                 transfer_node(m, d, n, m, m->desk, m->desk->focus, false);
1995         }
1996
1997         n->sticky = value;
1998
1999         if (value) {
2000                 m->sticky_count++;
2001         } else {
2002                 m->sticky_count--;
2003         }
2004
2005         if (n->client != NULL) {
2006                 if (value) {
2007                         n->client->wm_flags |= WM_FLAG_STICKY;
2008                 } else {
2009                         n->client->wm_flags &= ~WM_FLAG_STICKY;
2010                 }
2011                 ewmh_wm_state_update(n);
2012         }
2013
2014         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));
2015
2016         if (n == m->desk->focus) {
2017                 put_status(SBSC_MASK_REPORT);
2018         }
2019 }
2020
2021 void set_private(monitor_t *m, desktop_t *d, node_t *n, bool value)
2022 {
2023         if (n == NULL || n->private == value) {
2024                 return;
2025         }
2026
2027         n->private = value;
2028
2029         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));
2030
2031         if (n == m->desk->focus) {
2032                 put_status(SBSC_MASK_REPORT);
2033         }
2034 }
2035
2036 void set_locked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2037 {
2038         if (n == NULL || n->locked == value) {
2039                 return;
2040         }
2041
2042         n->locked = value;
2043
2044         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));
2045
2046         if (n == m->desk->focus) {
2047                 put_status(SBSC_MASK_REPORT);
2048         }
2049 }
2050
2051 void set_marked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2052 {
2053         if (n == NULL || n->marked == value) {
2054                 return;
2055         }
2056
2057         n->marked = value;
2058
2059         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));
2060
2061         if (n == m->desk->focus) {
2062                 put_status(SBSC_MASK_REPORT);
2063         }
2064 }
2065
2066 void set_urgent(monitor_t *m, desktop_t *d, node_t *n, bool value)
2067 {
2068         if (value && mon->desk->focus == n) {
2069                 return;
2070         }
2071
2072         n->client->urgent = value;
2073
2074         if (value) {
2075                 n->client->wm_flags |= WM_FLAG_DEMANDS_ATTENTION;
2076         } else {
2077                 n->client->wm_flags &= ~WM_FLAG_DEMANDS_ATTENTION;
2078         }
2079
2080         ewmh_wm_state_update(n);
2081
2082         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));
2083         put_status(SBSC_MASK_REPORT);
2084 }
2085
2086 xcb_rectangle_t get_rectangle(monitor_t *m, desktop_t *d, node_t *n)
2087 {
2088         if (n == NULL) {
2089                 return m->rectangle;
2090         }
2091         client_t *c = n->client;
2092         if (c != NULL) {
2093                 if (IS_FLOATING(c)) {
2094                         return c->floating_rectangle;
2095                 } else {
2096                         return c->tiled_rectangle;
2097                 }
2098         } else {
2099                 int wg = (d == NULL ? 0 : (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap));
2100                 xcb_rectangle_t rect = n->rectangle;
2101                 rect.width -= wg;
2102                 rect.height -= wg;
2103                 return rect;
2104         }
2105 }
2106
2107 void listen_enter_notify(node_t *n, bool enable)
2108 {
2109         uint32_t mask = CLIENT_EVENT_MASK | (enable ? XCB_EVENT_MASK_ENTER_WINDOW : 0);
2110         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
2111                 if (f->client == NULL) {
2112                         continue;
2113                 }
2114                 xcb_change_window_attributes(dpy, f->id, XCB_CW_EVENT_MASK, &mask);
2115                 if (f->presel != NULL) {
2116                         xcb_change_window_attributes(dpy, f->presel->feedback, XCB_CW_EVENT_MASK, &mask);
2117                 }
2118         }
2119 }
2120
2121 void regenerate_ids_in(node_t *n)
2122 {
2123         if (n == NULL || n->client != NULL) {
2124                 return;
2125         }
2126         n->id = xcb_generate_id(dpy);
2127         regenerate_ids_in(n->first_child);
2128         regenerate_ids_in(n->second_child);
2129 }
2130
2131 #define DEF_FLAG_COUNT(flag) \
2132         unsigned int flag##_count(node_t *n) \
2133         { \
2134                 if (n == NULL) { \
2135                         return 0; \
2136                 } else { \
2137                         return ((n->flag ? 1 : 0) + \
2138                                 flag##_count(n->first_child) + \
2139                                 flag##_count(n->second_child)); \
2140                 } \
2141         }
2142         DEF_FLAG_COUNT(sticky)
2143         DEF_FLAG_COUNT(private)
2144         DEF_FLAG_COUNT(locked)
2145 #undef DEF_FLAG_COUNT