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