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