src/tree.c

   1 /* Copyright (c) 2012, Bastien Dejean
   2  * All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  * 1. Redistributions of source code must retain the above copyright notice, this
   8  *    list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright notice,
  10  *    this list of conditions and the following disclaimer in the documentation
  11  *    and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  15  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  16  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  17  * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  18  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  19  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  20  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  22  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <stdbool.h>
  28 #include <limits.h>
  29 #include "bspwm.h"
  30 #include "desktop.h"
  31 #include "ewmh.h"
  32 #include "history.h"
  33 #include "monitor.h"
  34 #include "query.h"
  35 #include "geometry.h"
  36 #include "subscribe.h"
  37 #include "settings.h"
  38 #include "pointer.h"
  39 #include "stack.h"
  40 #include "window.h"
  41 #include "tree.h"
  42
  43 void arrange(monitor_t *m, desktop_t *d)
  44 {
  45         if (d->root == NULL) {
  46                 return;
  47         }
  48
  49         xcb_rectangle_t rect = m->rectangle;
  50
  51         rect.x += m->padding.left + d->padding.left;
  52         rect.y += m->padding.top + d->padding.top;
  53         rect.width -= m->padding.left + d->padding.left + d->padding.right + m->padding.right;
  54         rect.height -= m->padding.top + d->padding.top + d->padding.bottom + m->padding.bottom;
  55
  56         if (d->layout == LAYOUT_MONOCLE) {
  57                 rect.x += monocle_padding.left;
  58                 rect.y += monocle_padding.top;
  59                 rect.width -= monocle_padding.left + monocle_padding.right;
  60                 rect.height -= monocle_padding.top + monocle_padding.bottom;
  61         }
  62
  63         if (!gapless_monocle || d->layout != LAYOUT_MONOCLE) {
  64                 rect.x += d->window_gap;
  65                 rect.y += d->window_gap;
  66                 rect.width -= d->window_gap;
  67                 rect.height -= d->window_gap;
  68         }
  69
  70         apply_layout(m, d, d->root, rect, rect);
  71 }
  72
  73 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
  74 {
  75         if (n == NULL) {
  76                 return;
  77         }
  78
  79         n->rectangle = rect;
  80
  81         if (n->presel != NULL) {
  82                 draw_presel_feedback(m, d, n);
  83         }
  84
  85         if (is_leaf(n)) {
  86
  87                 if (n->client == NULL) {
  88                         return;
  89                 }
  90
  91                 unsigned int bw;
  92                 bool the_only_window = !m->prev && !m->next && d->root->client;
  93                 if ((borderless_monocle && d->layout == LAYOUT_MONOCLE && IS_TILED(n->client))
  94                     || (borderless_singleton && the_only_window)
  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 && d->layout == 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 (d->layout == 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, first_rect, root_rect);
 180                 apply_layout(m, d, n->second_child, 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                                         node_t *q = p;
 354                                         while (q != NULL && (q->first_child->vacant || q->second_child->vacant)) {
 355                                                 q = q->parent;
 356                                         }
 357                                         if (q == NULL) {
 358                                                 q = p;
 359                                         }
 360                                         if (q->split_type == TYPE_HORIZONTAL) {
 361                                                 c->split_type = TYPE_VERTICAL;
 362                                         } else {
 363                                                 c->split_type = TYPE_HORIZONTAL;
 364                                         }
 365                                 }
 366                         } else {
 367                                 node_t *g = p->parent;
 368                                 c->parent = g;
 369                                 if (g != NULL) {
 370                                         if (is_first_child(p)) {
 371                                                 g->first_child = c;
 372                                         } else {
 373                                                 g->second_child = c;
 374                                         }
 375                                 } else {
 376                                         d->root = c;
 377                                 }
 378                                 c->split_type = p->split_type;
 379                                 c->split_ratio = p->split_ratio;
 380                                 p->parent = c;
 381                                 int rot;
 382                                 if (is_first_child(f)) {
 383                                         c->first_child = n;
 384                                         c->second_child = p;
 385                                         rot = 90;
 386                                 } else {
 387                                         c->first_child = p;
 388                                         c->second_child = n;
 389                                         rot = 270;
 390                                 }
 391                                 if (!n->vacant) {
 392                                         rotate_tree(p, rot);
 393                                 }
 394                         }
 395                 } else {
 396                         if (p != NULL) {
 397                                 if (is_first_child(f)) {
 398                                         p->first_child = c;
 399                                 } else {
 400                                         p->second_child = c;
 401                                 }
 402                         }
 403                         c->split_ratio = f->presel->split_ratio;
 404                         c->parent = p;
 405                         f->parent = c;
 406                         switch (f->presel->split_dir) {
 407                                 case DIR_WEST:
 408                                         c->split_type = TYPE_VERTICAL;
 409                                         c->first_child = n;
 410                                         c->second_child = f;
 411                                         break;
 412                                 case DIR_EAST:
 413                                         c->split_type = TYPE_VERTICAL;
 414                                         c->first_child = f;
 415                                         c->second_child = n;
 416                                         break;
 417                                 case DIR_NORTH:
 418                                         c->split_type = TYPE_HORIZONTAL;
 419                                         c->first_child = n;
 420                                         c->second_child = f;
 421                                         break;
 422                                 case DIR_SOUTH:
 423                                         c->split_type = TYPE_HORIZONTAL;
 424                                         c->first_child = f;
 425                                         c->second_child = n;
 426                                         break;
 427                         }
 428                         if (d->root == f) {
 429                                 d->root = c;
 430                         }
 431                         cancel_presel(m, d, f);
 432                         set_marked(m, d, n, false);
 433                 }
 434         }
 435
 436         propagate_flags_upward(m, d, n);
 437
 438         if (d->focus == NULL && is_focusable(n)) {
 439                 d->focus = n;
 440         }
 441
 442         return f;
 443 }
 444
 445 void insert_receptacle(monitor_t *m, desktop_t *d, node_t *n)
 446 {
 447         node_t *r = make_node(XCB_NONE);
 448         insert_node(m, d, r, n);
 449
 450         if (single_monocle && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
 451                 set_layout(m, d, d->user_layout, false);
 452         }
 453 }
 454
 455 bool activate_node(monitor_t *m, desktop_t *d, node_t *n)
 456 {
 457         if (n == NULL && d->root != NULL) {
 458                 n = d->focus;
 459                 if (n == NULL) {
 460                         n = history_last_node(d, NULL);
 461                 }
 462                 if (n == NULL) {
 463                         n = first_focusable_leaf(d->root);
 464                 }
 465         }
 466
 467         if (d == mon->desk || (n != NULL && !is_focusable(n))) {
 468                 return false;
 469         }
 470
 471         if (n != NULL) {
 472                 if (d->focus != NULL && n != d->focus) {
 473                         neutralize_occluding_windows(m, d, n);
 474                 }
 475                 stack(d, n, true);
 476                 if (d->focus != n) {
 477                         for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 478                                 if (f->client != NULL && !is_descendant(f, n)) {
 479                                         window_draw_border(f->id, get_border_color(false, (m == mon)));
 480                                 }
 481                         }
 482                 }
 483                 draw_border(n, true, (m == mon));
 484         }
 485
 486         d->focus = n;
 487         history_add(m, d, n, false);
 488
 489         put_status(SBSC_MASK_REPORT);
 490
 491         if (n == NULL) {
 492                 return true;
 493         }
 494
 495         put_status(SBSC_MASK_NODE_ACTIVATE, "node_activate 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 496
 497         return true;
 498 }
 499
 500 void transfer_sticky_nodes(monitor_t *ms, desktop_t *ds, monitor_t *md, desktop_t *dd, node_t *n)
 501 {
 502         if (n == NULL) {
 503                 return;
 504         } else if (n->sticky) {
 505                 sticky_still = false;
 506                 transfer_node(ms, ds, n, md, dd, dd->focus, false);
 507                 sticky_still = true;
 508         } else {
 509                 /* we need references to the children because n might be freed after
 510                  * the first recursive call */
 511                 node_t *first_child = n->first_child;
 512                 node_t *second_child = n->second_child;
 513                 transfer_sticky_nodes(ms, ds, md, dd, first_child);
 514                 transfer_sticky_nodes(ms, ds, md, dd, second_child);
 515         }
 516 }
 517
 518 bool focus_node(monitor_t *m, desktop_t *d, node_t *n)
 519 {
 520         if (m == NULL) {
 521                 m = mon;
 522                 if (m == NULL) {
 523                         m = history_last_monitor(NULL);
 524                 }
 525                 if (m == NULL) {
 526                         m = mon_head;
 527                 }
 528         }
 529
 530         if (m == NULL) {
 531                 return false;
 532         }
 533
 534         if (d == NULL) {
 535                 d = m->desk;
 536                 if (d == NULL) {
 537                         d = history_last_desktop(m, NULL);
 538                 }
 539                 if (d == NULL) {
 540                         d = m->desk_head;
 541                 }
 542         }
 543
 544         if (d == NULL) {
 545                 return false;
 546         }
 547
 548         bool guess = (n == NULL);
 549
 550         if (n == NULL && d->root != NULL) {
 551                 n = d->focus;
 552                 if (n == NULL) {
 553                         n = history_last_node(d, NULL);
 554                 }
 555                 if (n == NULL) {
 556                         n = first_focusable_leaf(d->root);
 557                 }
 558         }
 559
 560         if (n != NULL && !is_focusable(n)) {
 561                 return false;
 562         }
 563
 564         if ((mon != NULL && mon->desk != d) || n == NULL || n->client == NULL) {
 565                 clear_input_focus();
 566         }
 567
 568         if (m->sticky_count > 0 && m->desk != NULL && d != m->desk) {
 569                 if (guess && m->desk->focus != NULL && m->desk->focus->sticky) {
 570                         n = m->desk->focus;
 571                 }
 572
 573                 transfer_sticky_nodes(m, m->desk, m, d, m->desk->root);
 574
 575                 if (n == NULL && d->focus != NULL) {
 576                         n = d->focus;
 577                 }
 578         }
 579
 580         if (d->focus != NULL && n != d->focus) {
 581                 neutralize_occluding_windows(m, d, n);
 582         }
 583
 584         if (n != NULL && n->client != NULL && n->client->urgent) {
 585                 set_urgent(m, d, n, false);
 586         }
 587
 588         if (mon != m) {
 589                 if (mon != NULL) {
 590                         for (desktop_t *e = mon->desk_head; e != NULL; e = e->next) {
 591                                 draw_border(e->focus, true, false);
 592                         }
 593                 }
 594                 for (desktop_t *e = m->desk_head; e != NULL; e = e->next) {
 595                         if (e == d) {
 596                                 continue;
 597                         }
 598                         draw_border(e->focus, true, true);
 599                 }
 600         }
 601
 602         if (d->focus != n) {
 603                 for (node_t *f = first_extrema(d->focus); f != NULL; f = next_leaf(f, d->focus)) {
 604                         if (f->client != NULL && !is_descendant(f, n)) {
 605                                 window_draw_border(f->id, get_border_color(false, true));
 606                         }
 607                 }
 608         }
 609
 610         draw_border(n, true, true);
 611
 612         bool desk_changed = (m != mon || m->desk != d);
 613         bool has_input_focus = false;
 614
 615         if (mon != m) {
 616                 mon = m;
 617
 618                 if (pointer_follows_monitor) {
 619                         center_pointer(m->rectangle);
 620                 }
 621
 622                 put_status(SBSC_MASK_MONITOR_FOCUS, "monitor_focus 0x%08X\n", m->id);
 623         }
 624
 625         if (m->desk != d) {
 626                 show_desktop(d);
 627                 set_input_focus(n);
 628                 has_input_focus = true;
 629                 hide_desktop(m->desk);
 630                 m->desk = d;
 631         }
 632
 633         if (desk_changed) {
 634                 ewmh_update_current_desktop();
 635                 put_status(SBSC_MASK_DESKTOP_FOCUS, "desktop_focus 0x%08X 0x%08X\n", m->id, d->id);
 636         }
 637
 638         d->focus = n;
 639         if (!has_input_focus) {
 640                 set_input_focus(n);
 641         }
 642         ewmh_update_active_window();
 643         history_add(m, d, n, true);
 644
 645         put_status(SBSC_MASK_REPORT);
 646
 647         if (n == NULL) {
 648                 if (focus_follows_pointer) {
 649                         update_motion_recorder();
 650                 }
 651                 return true;
 652         }
 653
 654         put_status(SBSC_MASK_NODE_FOCUS, "node_focus 0x%08X 0x%08X 0x%08X\n", m->id, d->id, n->id);
 655
 656         stack(d, n, true);
 657
 658         if (pointer_follows_focus) {
 659                 center_pointer(get_rectangle(m, d, n));
 660         } else if (focus_follows_pointer) {
 661                 update_motion_recorder();
 662         }
 663
 664         return true;
 665 }
 666
 667 void hide_node(desktop_t *d, node_t *n)
 668 {
 669         if (n == NULL || (!hide_sticky && n->sticky)) {
 670                 return;
 671         } else {
 672                 if (!n->hidden) {
 673                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 674                                 window_hide(n->presel->feedback);
 675                         }
 676                         if (n->client != NULL) {
 677                                 window_hide(n->id);
 678                         }
 679                 }
 680                 if (n->client != NULL) {
 681                         n->client->shown = false;
 682                 }
 683                 hide_node(d, n->first_child);
 684                 hide_node(d, n->second_child);
 685         }
 686 }
 687
 688 void show_node(desktop_t *d, node_t *n)
 689 {
 690         if (n == NULL) {
 691                 return;
 692         } else {
 693                 if (!n->hidden) {
 694                         if (n->client != NULL) {
 695                                 window_show(n->id);
 696                         }
 697                         if (n->presel != NULL && d->layout != LAYOUT_MONOCLE) {
 698                                 window_show(n->presel->feedback);
 699                         }
 700                 }
 701                 if (n->client != NULL) {
 702                         n->client->shown = true;
 703                 }
 704                 show_node(d, n->first_child);
 705                 show_node(d, n->second_child);
 706         }
 707 }
 708
 709 node_t *make_node(uint32_t id)
 710 {
 711         if (id == XCB_NONE) {
 712                 id = xcb_generate_id(dpy);
 713         }
 714         node_t *n = calloc(1, sizeof(node_t));
 715         n->id = id;
 716         n->parent = n->first_child = n->second_child = NULL;
 717         n->vacant = n->hidden = n->sticky = n->private = n->locked = n->marked = false;
 718         n->split_ratio = split_ratio;
 719         n->split_type = TYPE_VERTICAL;
 720         n->constraints = (constraints_t) {MIN_WIDTH, MIN_HEIGHT};
 721         n->presel = NULL;
 722         n->client = NULL;
 723         return n;
 724 }
 725
 726 client_t *make_client(void)
 727 {
 728         client_t *c = calloc(1, sizeof(client_t));
 729         c->state = c->last_state = STATE_TILED;
 730         c->layer = c->last_layer = LAYER_NORMAL;
 731         snprintf(c->class_name, sizeof(c->class_name), "%s", MISSING_VALUE);
 732         snprintf(c->instance_name, sizeof(c->instance_name), "%s", MISSING_VALUE);
 733         c->border_width = border_width;
 734         c->urgent = false;
 735         c->shown = false;
 736         c->wm_flags = 0;
 737         c->icccm_props.input_hint = true;
 738         c->icccm_props.take_focus = false;
 739         c->icccm_props.delete_window = false;
 740         c->size_hints.flags = 0;
 741         return c;
 742 }
 743
 744 void initialize_client(node_t *n)
 745 {
 746         xcb_window_t win = n->id;
 747         client_t *c = n->client;
 748         xcb_icccm_get_wm_protocols_reply_t protos;
 749         if (xcb_icccm_get_wm_protocols_reply(dpy, xcb_icccm_get_wm_protocols(dpy, win, ewmh->WM_PROTOCOLS), &protos, NULL) == 1) {
 750                 for (uint32_t i = 0; i < protos.atoms_len; i++) {
 751                         if (protos.atoms[i] == WM_TAKE_FOCUS) {
 752                                 c->icccm_props.take_focus = true;
 753                         } else if (protos.atoms[i] == WM_DELETE_WINDOW) {
 754                                 c->icccm_props.delete_window = true;
 755                         }
 756                 }
 757                 xcb_icccm_get_wm_protocols_reply_wipe(&protos);
 758         }
 759         xcb_ewmh_get_atoms_reply_t wm_state;
 760         if (xcb_ewmh_get_wm_state_reply(ewmh, xcb_ewmh_get_wm_state(ewmh, win), &wm_state, NULL) == 1) {
 761                 for (unsigned int i = 0; i < wm_state.atoms_len && i < MAX_WM_STATES; i++) {
 762 #define HANDLE_WM_STATE(s) \
 763                         if (wm_state.atoms[i] == ewmh->_NET_WM_STATE_##s) { \
 764                                 c->wm_flags |= WM_FLAG_##s; continue; \
 765                         }
 766                         HANDLE_WM_STATE(MODAL)
 767                         HANDLE_WM_STATE(STICKY)
 768                         HANDLE_WM_STATE(MAXIMIZED_VERT)
 769                         HANDLE_WM_STATE(MAXIMIZED_HORZ)
 770                         HANDLE_WM_STATE(SHADED)
 771                         HANDLE_WM_STATE(SKIP_TASKBAR)
 772                         HANDLE_WM_STATE(SKIP_PAGER)
 773                         HANDLE_WM_STATE(HIDDEN)
 774                         HANDLE_WM_STATE(FULLSCREEN)
 775                         HANDLE_WM_STATE(ABOVE)
 776                         HANDLE_WM_STATE(BELOW)
 777                         HANDLE_WM_STATE(DEMANDS_ATTENTION)
 778 #undef HANDLE_WM_STATE
 779                 }
 780                 xcb_ewmh_get_atoms_reply_wipe(&wm_state);
 781         }
 782         xcb_icccm_wm_hints_t hints;
 783         if (xcb_icccm_get_wm_hints_reply(dpy, xcb_icccm_get_wm_hints(dpy, win), &hints, NULL) == 1
 784                 && (hints.flags & XCB_ICCCM_WM_HINT_INPUT)) {
 785                 c->icccm_props.input_hint = hints.input;
 786         }
 787         xcb_icccm_get_wm_normal_hints_reply(dpy, xcb_icccm_get_wm_normal_hints(dpy, win), &c->size_hints, NULL);
 788 }
 789
 790 bool is_focusable(node_t *n)
 791 {
 792         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 793                 if (f->client != NULL && !f->hidden) {
 794                         return true;
 795                 }
 796         }
 797         return false;
 798 }
 799
 800 bool is_leaf(node_t *n)
 801 {
 802         return (n != NULL && n->first_child == NULL && n->second_child == NULL);
 803 }
 804
 805 bool is_first_child(node_t *n)
 806 {
 807         return (n != NULL && n->parent != NULL && n->parent->first_child == n);
 808 }
 809
 810 bool is_second_child(node_t *n)
 811 {
 812         return (n != NULL && n->parent != NULL && n->parent->second_child == n);
 813 }
 814
 815 unsigned int clients_count_in(node_t *n)
 816 {
 817         if (n == NULL) {
 818                 return 0;
 819         } else {
 820                 return (n->client != NULL ? 1 : 0) +
 821                         clients_count_in(n->first_child) +
 822                         clients_count_in(n->second_child);
 823         }
 824 }
 825
 826 node_t *brother_tree(node_t *n)
 827 {
 828         if (n == NULL || n->parent == NULL) {
 829                 return NULL;
 830         }
 831         if (is_first_child(n)) {
 832                 return n->parent->second_child;
 833         } else {
 834                 return n->parent->first_child;
 835         }
 836 }
 837
 838 node_t *first_extrema(node_t *n)
 839 {
 840         if (n == NULL) {
 841                 return NULL;
 842         } else if (n->first_child == NULL) {
 843                 return n;
 844         } else {
 845                 return first_extrema(n->first_child);
 846         }
 847 }
 848
 849 node_t *second_extrema(node_t *n)
 850 {
 851         if (n == NULL) {
 852                 return NULL;
 853         } else if (n->second_child == NULL) {
 854                 return n;
 855         } else {
 856                 return second_extrema(n->second_child);
 857         }
 858 }
 859
 860 node_t *first_focusable_leaf(node_t *n)
 861 {
 862         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
 863                 if (f->client != NULL && !f->hidden) {
 864                         return f;
 865                 }
 866         }
 867         return NULL;
 868 }
 869
 870 node_t *next_node(node_t *n)
 871 {
 872         if (n == NULL) {
 873                 return NULL;
 874         }
 875
 876         if (n->second_child != NULL) {
 877                 return first_extrema(n->second_child);
 878         } else {
 879                 node_t *p = n;
 880                 while (is_second_child(p)) {
 881                         p = p->parent;
 882                 }
 883                 if (is_first_child(p)) {
 884                         return p->parent;
 885                 } else {
 886                         return NULL;
 887                 }
 888         }
 889 }
 890
 891 node_t *prev_node(node_t *n)
 892 {
 893         if (n == NULL) {
 894                 return NULL;
 895         }
 896
 897         if (n->first_child != NULL) {
 898                 return second_extrema(n->first_child);
 899         } else {
 900                 node_t *p = n;
 901                 while (is_first_child(p)) {
 902                         p = p->parent;
 903                 }
 904                 if (is_second_child(p)) {
 905                         return p->parent;
 906                 } else {
 907                         return NULL;
 908                 }
 909         }
 910 }
 911
 912 node_t *next_leaf(node_t *n, node_t *r)
 913 {
 914         if (n == NULL) {
 915                 return NULL;
 916         }
 917         node_t *p = n;
 918         while (is_second_child(p) && p != r) {
 919                 p = p->parent;
 920         }
 921         if (p == r) {
 922                 return NULL;
 923         }
 924         return first_extrema(p->parent->second_child);
 925 }
 926
 927 node_t *prev_leaf(node_t *n, node_t *r)
 928 {
 929         if (n == NULL) {
 930                 return NULL;
 931         }
 932         node_t *p = n;
 933         while (is_first_child(p) && p != r) {
 934                 p = p->parent;
 935         }
 936         if (p == r) {
 937                 return NULL;
 938         }
 939         return second_extrema(p->parent->first_child);
 940 }
 941
 942 node_t *next_tiled_leaf(node_t *n, node_t *r)
 943 {
 944         node_t *next = next_leaf(n, r);
 945         if (next == NULL || (next->client != NULL && !next->vacant)) {
 946                 return next;
 947         } else {
 948                 return next_tiled_leaf(next, r);
 949         }
 950 }
 951
 952 node_t *prev_tiled_leaf(node_t *n, node_t *r)
 953 {
 954         node_t *prev = prev_leaf(n, r);
 955         if (prev == NULL || (prev->client != NULL && !prev->vacant)) {
 956                 return prev;
 957         } else {
 958                 return prev_tiled_leaf(prev, r);
 959         }
 960 }
 961
 962 /* Returns true if *b* is adjacent to *a* in the direction *dir* */
 963 bool is_adjacent(node_t *a, node_t *b, direction_t dir)
 964 {
 965         switch (dir) {
 966                 case DIR_EAST:
 967                         return (a->rectangle.x + a->rectangle.width) == b->rectangle.x;
 968                         break;
 969                 case DIR_SOUTH:
 970                         return (a->rectangle.y + a->rectangle.height) == b->rectangle.y;
 971                         break;
 972                 case DIR_WEST:
 973                         return (b->rectangle.x + b->rectangle.width) == a->rectangle.x;
 974                         break;
 975                 case DIR_NORTH:
 976                         return (b->rectangle.y + b->rectangle.height) == a->rectangle.y;
 977                         break;
 978         }
 979         return false;
 980 }
 981
 982 node_t *find_fence(node_t *n, direction_t dir)
 983 {
 984         node_t *p;
 985
 986         if (n == NULL) {
 987                 return NULL;
 988         }
 989
 990         p = n->parent;
 991
 992         while (p != NULL) {
 993                 if ((dir == DIR_NORTH && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y) ||
 994                     (dir == DIR_WEST && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x) ||
 995                     (dir == DIR_SOUTH && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height)) ||
 996                     (dir == DIR_EAST && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 997                         return p;
 998                 p = p->parent;
 999         }
1000
1001         return NULL;
1002 }
1003
1004 /* returns *true* if *a* is a child of *b* */
1005 bool is_child(node_t *a, node_t *b)
1006 {
1007         if (a == NULL || b == NULL) {
1008                 return false;
1009         }
1010         return (a->parent != NULL && a->parent == b);
1011 }
1012
1013 /* returns *true* if *a* is a descendant of *b* */
1014 bool is_descendant(node_t *a, node_t *b)
1015 {
1016         if (a == NULL || b == NULL) {
1017                 return false;
1018         }
1019         while (a != b && a != NULL) {
1020                 a = a->parent;
1021         }
1022         return a == b;
1023 }
1024
1025 bool find_by_id(uint32_t id, coordinates_t *loc)
1026 {
1027         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1028                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1029                         node_t *n = find_by_id_in(d->root, id);
1030                         if (n != NULL) {
1031                                 loc->monitor = m;
1032                                 loc->desktop = d;
1033                                 loc->node = n;
1034                                 return true;
1035                         }
1036                 }
1037         }
1038         return false;
1039 }
1040
1041 node_t *find_by_id_in(node_t *r, uint32_t id)
1042 {
1043         if (r == NULL) {
1044                 return NULL;
1045         } else if (r->id == id) {
1046                 return r;
1047         } else {
1048                 node_t *f = find_by_id_in(r->first_child, id);
1049                 if (f != NULL) {
1050                         return f;
1051                 } else {
1052                         return find_by_id_in(r->second_child, id);
1053                 }
1054         }
1055 }
1056
1057 void find_any_node(coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1058 {
1059         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1060                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1061                         if (find_any_node_in(m, d, d->root, ref, dst, sel)) {
1062                                 return;
1063                         }
1064                 }
1065         }
1066 }
1067
1068 bool find_any_node_in(monitor_t *m, desktop_t *d, node_t *n, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1069 {
1070         if (n == NULL) {
1071                 return false;
1072         } else {
1073                 coordinates_t loc = {m, d, n};
1074                 if (node_matches(&loc, ref, sel)) {
1075                         *dst = loc;
1076                         return true;
1077                 } else {
1078                         if (find_any_node_in(m, d, n->first_child, ref, dst, sel)) {
1079                                 return true;
1080                         } else {
1081                                 return find_any_node_in(m, d, n->second_child, ref, dst, sel);
1082                         }
1083                 }
1084         }
1085 }
1086
1087 void find_first_ancestor(coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1088 {
1089         if (ref->node == NULL) {
1090                 return;
1091         }
1092
1093         coordinates_t loc = {ref->monitor, ref->desktop, ref->node};
1094         while ((loc.node = loc.node->parent) != NULL) {
1095                 if (node_matches(&loc, ref, sel)) {
1096                         *dst = loc;
1097                         return;
1098                 }
1099         }
1100 }
1101
1102 /* Based on https://github.com/ntrrgc/right-window */
1103 void find_nearest_neighbor(coordinates_t *ref, coordinates_t *dst, direction_t dir, node_select_t *sel)
1104 {
1105         xcb_rectangle_t rect = get_rectangle(ref->monitor, ref->desktop, ref->node);
1106         uint32_t md = UINT32_MAX, mr = UINT32_MAX;
1107
1108         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1109                 desktop_t *d = m->desk;
1110                 for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1111                         coordinates_t loc = {m, d, f};
1112                         xcb_rectangle_t r = get_rectangle(m, d, f);
1113                         if (f == ref->node ||
1114                             f->client == NULL ||
1115                             f->hidden ||
1116                             is_descendant(f, ref->node) ||
1117                             !node_matches(&loc, ref, sel) ||
1118                             !on_dir_side(rect, r, dir)) {
1119                                 continue;
1120                         }
1121                         uint32_t fd = boundary_distance(rect, r, dir);
1122                         uint32_t fr = history_rank(f);
1123                         if (fd < md || (fd == md && fr < mr)) {
1124                                 md = fd;
1125                                 mr = fr;
1126                                 *dst = loc;
1127                         }
1128                 }
1129         }
1130 }
1131
1132 unsigned int node_area(desktop_t *d, node_t *n)
1133 {
1134         if (n == NULL) {
1135                 return 0;
1136         }
1137         return area(get_rectangle(NULL, d, n));
1138 }
1139
1140 int tiled_count(node_t *n, bool include_receptacles)
1141 {
1142         if (n == NULL) {
1143                 return 0;
1144         }
1145         int cnt = 0;
1146         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1147                 if (!f->hidden && ((include_receptacles && f->client == NULL) ||
1148                                    (f->client != NULL && IS_TILED(f->client)))) {
1149                         cnt++;
1150                 }
1151         }
1152         return cnt;
1153 }
1154
1155 void find_by_area(area_peak_t ap, coordinates_t *ref, coordinates_t *dst, node_select_t *sel)
1156 {
1157         unsigned int p_area;
1158         if (ap == AREA_BIGGEST) {
1159                 p_area = 0;
1160         } else {
1161                 p_area = UINT_MAX;
1162         }
1163
1164         for (monitor_t *m = mon_head; m != NULL; m = m->next) {
1165                 for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
1166                         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
1167                                 coordinates_t loc = {m, d, f};
1168                                 if (f->vacant || !node_matches(&loc, ref, sel)) {
1169                                         continue;
1170                                 }
1171                                 unsigned int f_area = node_area(d, f);
1172                                 if ((ap == AREA_BIGGEST && f_area > p_area) || (ap == AREA_SMALLEST && f_area < p_area)) {
1173                                         *dst = loc;
1174                                         p_area = f_area;
1175                                 }
1176                         }
1177                 }
1178         }
1179 }
1180
1181 void rotate_tree(node_t *n, int deg)
1182 {
1183         rotate_tree_rec(n, deg);
1184         rebuild_constraints_from_leaves(n);
1185         rebuild_constraints_towards_root(n);
1186 }
1187
1188 void rotate_tree_rec(node_t *n, int deg)
1189 {
1190         if (n == NULL || is_leaf(n) || deg == 0) {
1191                 return;
1192         }
1193
1194         node_t *tmp;
1195
1196         if ((deg == 90 && n->split_type == TYPE_HORIZONTAL) ||
1197             (deg == 270 && n->split_type == TYPE_VERTICAL) ||
1198             deg == 180) {
1199                 tmp = n->first_child;
1200                 n->first_child = n->second_child;
1201                 n->second_child = tmp;
1202                 n->split_ratio = 1.0 - n->split_ratio;
1203         }
1204
1205         if (deg != 180) {
1206                 if (n->split_type == TYPE_HORIZONTAL) {
1207                         n->split_type = TYPE_VERTICAL;
1208                 } else if (n->split_type == TYPE_VERTICAL) {
1209                         n->split_type = TYPE_HORIZONTAL;
1210                 }
1211         }
1212
1213         rotate_tree_rec(n->first_child, deg);
1214         rotate_tree_rec(n->second_child, deg);
1215 }
1216
1217 void flip_tree(node_t *n, flip_t flp)
1218 {
1219         if (n == NULL || is_leaf(n)) {
1220                 return;
1221         }
1222
1223         node_t *tmp;
1224
1225         if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL) ||
1226             (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
1227                 tmp = n->first_child;
1228                 n->first_child = n->second_child;
1229                 n->second_child = tmp;
1230                 n->split_ratio = 1.0 - n->split_ratio;
1231         }
1232
1233         flip_tree(n->first_child, flp);
1234         flip_tree(n->second_child, flp);
1235 }
1236
1237 void equalize_tree(node_t *n)
1238 {
1239         if (n == NULL || n->vacant) {
1240                 return;
1241         } else {
1242                 n->split_ratio = split_ratio;
1243                 equalize_tree(n->first_child);
1244                 equalize_tree(n->second_child);
1245         }
1246 }
1247
1248 int balance_tree(node_t *n)
1249 {
1250         if (n == NULL || n->vacant) {
1251                 return 0;
1252         } else if (is_leaf(n)) {
1253                 return 1;
1254         } else {
1255                 int b1 = balance_tree(n->first_child);
1256                 int b2 = balance_tree(n->second_child);
1257                 int b = b1 + b2;
1258                 if (b1 > 0 && b2 > 0) {
1259                         n->split_ratio = (double) b1 / b;
1260                 }
1261                 return b;
1262         }
1263 }
1264
1265 /* Adjust the split ratios so that they keep their position
1266  * despite the potential alteration of their rectangle. */
1267 void adjust_ratios(node_t *n, xcb_rectangle_t rect)
1268 {
1269         if (n == NULL) {
1270                 return;
1271         }
1272
1273         double ratio;
1274
1275         if (n->split_type == TYPE_VERTICAL) {
1276                 double position = (double) n->rectangle.x + n->split_ratio * (double) n->rectangle.width;
1277                 ratio = (position - (double) rect.x) / (double) rect.width;
1278         } else {
1279                 double position = (double) n->rectangle.y + n->split_ratio * (double) n->rectangle.height;
1280                 ratio = (position - (double) rect.y) / (double) rect.height;
1281         }
1282
1283         ratio = MAX(0.0, ratio);
1284         ratio = MIN(1.0, ratio);
1285         n->split_ratio = ratio;
1286
1287         xcb_rectangle_t first_rect;
1288         xcb_rectangle_t second_rect;
1289         unsigned int fence;
1290
1291         if (n->split_type == TYPE_VERTICAL) {
1292                 fence = rect.width * n->split_ratio;
1293                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
1294                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
1295         } else {
1296                 fence = rect.height * n->split_ratio;
1297                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
1298                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
1299         }
1300
1301         adjust_ratios(n->first_child, first_rect);
1302         adjust_ratios(n->second_child, second_rect);
1303 }
1304
1305 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
1306 {
1307         if (d == NULL || n == NULL) {
1308                 return;
1309         }
1310
1311         node_t *p = n->parent;
1312
1313         if (p == NULL) {
1314                 d->root = NULL;
1315                 d->focus = NULL;
1316         } else {
1317                 if (d->focus == p || is_descendant(d->focus, n)) {
1318                         d->focus = NULL;
1319                 }
1320
1321                 history_remove(d, p, false);
1322                 cancel_presel(m, d, p);
1323
1324                 if (p->sticky) {
1325                         m->sticky_count--;
1326                 }
1327
1328                 node_t *b = brother_tree(n);
1329                 node_t *g = p->parent;
1330
1331                 b->parent = g;
1332
1333                 if (g != NULL) {
1334                         if (is_first_child(p)) {
1335                                 g->first_child = b;
1336                         } else {
1337                                 g->second_child = b;
1338                         }
1339                 } else {
1340                         d->root = b;
1341                 }
1342
1343                 if (!n->vacant && removal_adjustment) {
1344                         if (automatic_scheme == SCHEME_SPIRAL) {
1345                                 if (is_first_child(n)) {
1346                                         rotate_tree(b, 270);
1347                                 } else {
1348                                         rotate_tree(b, 90);
1349                                 }
1350                         } else if (automatic_scheme == SCHEME_LONGEST_SIDE || g == NULL) {
1351                                 if (p != NULL) {
1352                                         if (p->rectangle.width > p->rectangle.height) {
1353                                                 b->split_type = TYPE_VERTICAL;
1354                                         } else {
1355                                                 b->split_type = TYPE_HORIZONTAL;
1356                                         }
1357                                 }
1358                         } else if (automatic_scheme == SCHEME_ALTERNATE) {
1359                                 if (g->split_type == TYPE_HORIZONTAL) {
1360                                         b->split_type = TYPE_VERTICAL;
1361                                 } else {
1362                                         b->split_type = TYPE_HORIZONTAL;
1363                                 }
1364                         }
1365                 }
1366
1367                 free(p);
1368                 n->parent = NULL;
1369
1370                 propagate_flags_upward(m, d, b);
1371         }
1372 }
1373
1374 void close_node(node_t *n)
1375 {
1376         if (n == NULL) {
1377                 return;
1378         } else if (n->client != NULL) {
1379                 if (n->client->icccm_props.delete_window) {
1380                         send_client_message(n->id, ewmh->WM_PROTOCOLS, WM_DELETE_WINDOW);
1381                 } else {
1382                         xcb_kill_client(dpy, n->id);
1383                 }
1384         } else {
1385                 close_node(n->first_child);
1386                 close_node(n->second_child);
1387         }
1388 }
1389
1390 void kill_node(monitor_t *m, desktop_t *d, node_t *n)
1391 {
1392         if (n == NULL) {
1393                 return;
1394         }
1395
1396         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1397                 if (f->client != NULL) {
1398                         xcb_kill_client(dpy, f->id);
1399                 }
1400         }
1401
1402         remove_node(m, d, n);
1403 }
1404
1405 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
1406 {
1407         if (n == NULL) {
1408                 return;
1409         }
1410
1411         unlink_node(m, d, n);
1412         history_remove(d, n, true);
1413         remove_stack_node(n);
1414         cancel_presel_in(m, d, n);
1415         if (m->sticky_count > 0 && d == m->desk) {
1416                 m->sticky_count -= sticky_count(n);
1417         }
1418         clients_count -= clients_count_in(n);
1419         if (is_descendant(grabbed_node, n)) {
1420                 grabbed_node = NULL;
1421         }
1422         free_node(n);
1423
1424         if (single_monocle && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1425                 set_layout(m, d, LAYOUT_MONOCLE, false);
1426         }
1427
1428         ewmh_update_client_list(false);
1429         ewmh_update_client_list(true);
1430
1431         if (mon != NULL && d->focus == NULL) {
1432                 if (d == mon->desk) {
1433                         focus_node(m, d, NULL);
1434                 } else {
1435                         activate_node(m, d, NULL);
1436                 }
1437         }
1438 }
1439
1440 void free_node(node_t *n)
1441 {
1442         if (n == NULL) {
1443                 return;
1444         }
1445         node_t *first_child = n->first_child;
1446         node_t *second_child = n->second_child;
1447         free(n->client);
1448         free(n);
1449         free_node(first_child);
1450         free_node(second_child);
1451 }
1452
1453 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2, bool follow)
1454 {
1455         if (n1 == NULL || n2 == NULL || n1 == n2 || is_descendant(n1, n2) || is_descendant(n2, n1) ||
1456             (d1 != d2 && ((m1->sticky_count > 0 && sticky_count(n1) > 0) ||
1457                           (m2->sticky_count > 0 && sticky_count(n2) > 0)))) {
1458                 return false;
1459         }
1460
1461         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);
1462
1463         node_t *pn1 = n1->parent;
1464         node_t *pn2 = n2->parent;
1465         bool n1_first_child = is_first_child(n1);
1466         bool n2_first_child = is_first_child(n2);
1467         bool n1_held_focus = is_descendant(d1->focus, n1);
1468         bool n2_held_focus = is_descendant(d2->focus, n2);
1469         node_t *last_d1_focus = d1->focus;
1470         node_t *last_d2_focus = d2->focus;
1471
1472         if (pn1 != NULL) {
1473                 if (n1_first_child) {
1474                         pn1->first_child = n2;
1475                 } else {
1476                         pn1->second_child = n2;
1477                 }
1478         }
1479
1480         if (pn2 != NULL) {
1481                 if (n2_first_child) {
1482                         pn2->first_child = n1;
1483                 } else {
1484                         pn2->second_child = n1;
1485                 }
1486         }
1487
1488         n1->parent = pn2;
1489         n2->parent = pn1;
1490
1491         propagate_flags_upward(m2, d2, n1);
1492         propagate_flags_upward(m1, d1, n2);
1493
1494         if (d1 != d2) {
1495                 if (d1->root == n1) {
1496                         d1->root = n2;
1497                 }
1498
1499                 if (d2->root == n2) {
1500                         d2->root = n1;
1501                 }
1502
1503                 if (n1_held_focus) {
1504                         d1->focus = n2_held_focus ? last_d2_focus : n2;
1505                 }
1506
1507                 if (n2_held_focus) {
1508                         d2->focus = n1_held_focus ? last_d1_focus : n1;
1509                 }
1510
1511                 if (m1 != m2) {
1512                         adapt_geometry(&m2->rectangle, &m1->rectangle, n2);
1513                         adapt_geometry(&m1->rectangle, &m2->rectangle, n1);
1514                 }
1515
1516                 ewmh_set_wm_desktop(n1, d2);
1517                 ewmh_set_wm_desktop(n2, d1);
1518
1519                 history_remove(d1, n1, true);
1520                 history_remove(d2, n2, true);
1521
1522                 bool d1_was_focused = (d1 == mon->desk);
1523                 bool d2_was_focused = (d2 == mon->desk);
1524
1525                 if (m1->desk != d1 && m2->desk == d2) {
1526                         show_node(d2, n1);
1527                         if (!follow || !d2_was_focused || !n2_held_focus) {
1528                                 hide_node(d2, n2);
1529                         }
1530                 } else if (m1->desk == d1 && m2->desk != d2) {
1531                         if (!follow || !d1_was_focused || !n1_held_focus) {
1532                                 hide_node(d1, n1);
1533                         }
1534                         show_node(d1, n2);
1535                 }
1536
1537                 if (single_monocle) {
1538                         layout_t l1 = tiled_count(d1->root, true) <= 1 ? LAYOUT_MONOCLE : d1->user_layout;
1539                         layout_t l2 = tiled_count(d2->root, true) <= 1 ? LAYOUT_MONOCLE : d2->user_layout;
1540                         set_layout(m1, d1, l1, false);
1541                         set_layout(m2, d2, l2, false);
1542                 }
1543
1544                 if (n1_held_focus) {
1545                         if (d1_was_focused) {
1546                                 if (follow) {
1547                                         focus_node(m2, d2, last_d1_focus);
1548                                 } else {
1549                                         focus_node(m1, d1, d1->focus);
1550                                 }
1551                         } else {
1552                                 activate_node(m1, d1, d1->focus);
1553                         }
1554                 } else {
1555                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1556                 }
1557
1558                 if (n2_held_focus) {
1559                         if (d2_was_focused) {
1560                                 if (follow) {
1561                                         focus_node(m1, d1, last_d2_focus);
1562                                 } else {
1563                                         focus_node(m2, d2, d2->focus);
1564                                 }
1565                         } else {
1566                                 activate_node(m2, d2, d2->focus);
1567                         }
1568                 } else {
1569                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1570                 }
1571         } else {
1572                 if (!n1_held_focus) {
1573                         draw_border(n1, is_descendant(n1, d2->focus), (m2 == mon));
1574                 }
1575                 if (!n2_held_focus) {
1576                         draw_border(n2, is_descendant(n2, d1->focus), (m1 == mon));
1577                 }
1578         }
1579
1580         arrange(m1, d1);
1581
1582         if (d1 != d2) {
1583                 arrange(m2, d2);
1584         } else {
1585                 if (pointer_follows_focus && (n1_held_focus || n2_held_focus)) {
1586                         center_pointer(get_rectangle(m1, d1, d1->focus));
1587                 }
1588         }
1589
1590         return true;
1591 }
1592
1593 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd, bool follow)
1594 {
1595         if (ns == NULL || ns == nd || is_child(ns, nd) || is_descendant(nd, ns)) {
1596                 return false;
1597         }
1598
1599         unsigned int sc = (ms->sticky_count > 0 && ds == ms->desk) ? sticky_count(ns) : 0;
1600         if (sticky_still && sc > 0 && dd != md->desk) {
1601                 return false;
1602         }
1603
1604         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);
1605
1606         bool held_focus = is_descendant(ds->focus, ns);
1607         /* avoid ending up with a dangling pointer (because of unlink_node) */
1608         node_t *last_ds_focus = is_child(ns, ds->focus) ? NULL : ds->focus;
1609         bool ds_was_focused = (ds == mon->desk);
1610
1611         if (held_focus && ds_was_focused) {
1612                 clear_input_focus();
1613         }
1614
1615         unlink_node(ms, ds, ns);
1616         insert_node(md, dd, ns, nd);
1617
1618         if (md != ms) {
1619                 if (ns->client == NULL || monitor_from_client(ns->client) != md) {
1620                         adapt_geometry(&ms->rectangle, &md->rectangle, ns);
1621                 }
1622                 ms->sticky_count -= sc;
1623                 md->sticky_count += sc;
1624         }
1625
1626         if (ds != dd) {
1627                 ewmh_set_wm_desktop(ns, dd);
1628                 if (sticky_still) {
1629                         if (ds == ms->desk && dd != md->desk) {
1630                                 hide_node(ds, ns);
1631                         } else if (ds != ms->desk && dd == md->desk) {
1632                                 show_node(dd, ns);
1633                         }
1634                 }
1635         }
1636
1637         history_remove(ds, ns, true);
1638         stack(dd, ns, false);
1639
1640         if (ds == dd) {
1641                 if (held_focus) {
1642                         if (ds_was_focused) {
1643                                 focus_node(ms, ds, last_ds_focus);
1644                         } else {
1645                                 activate_node(ms, ds, last_ds_focus);
1646                         }
1647                 } else {
1648                         draw_border(ns, is_descendant(ns, ds->focus), (ms == mon));
1649                 }
1650         } else {
1651                 if (single_monocle) {
1652                         if (ds->layout != LAYOUT_MONOCLE && tiled_count(ds->root, true) <= 1) {
1653                                 set_layout(ms, ds, LAYOUT_MONOCLE, false);
1654                         }
1655                         if (dd->layout == LAYOUT_MONOCLE && tiled_count(dd->root, true) > 1) {
1656                                 set_layout(md, dd, dd->user_layout, false);
1657                         }
1658                 }
1659                 if (held_focus) {
1660                         if (follow) {
1661                                 if (ds_was_focused) {
1662                                         focus_node(md, dd, last_ds_focus);
1663                                 }
1664                                 activate_node(ms, ds, ds->focus);
1665                         } else {
1666                                 if (ds_was_focused) {
1667                                         focus_node(ms, ds, ds->focus);
1668                                 } else {
1669                                         activate_node(ms, ds, ds->focus);
1670                                 }
1671                         }
1672                 }
1673                 if (!held_focus || !follow || !ds_was_focused) {
1674                         if (dd->focus == ns) {
1675                                 if (dd == mon->desk) {
1676                                         focus_node(md, dd, held_focus ? last_ds_focus : ns);
1677                                 } else {
1678                                         activate_node(md, dd, held_focus ? last_ds_focus : ns);
1679                                 }
1680                         } else {
1681                                 draw_border(ns, is_descendant(ns, dd->focus), (md == mon));
1682                         }
1683                 }
1684         }
1685
1686         arrange(ms, ds);
1687
1688         if (ds != dd) {
1689                 arrange(md, dd);
1690         }
1691
1692         return true;
1693 }
1694
1695 bool find_closest_node(coordinates_t *ref, coordinates_t *dst, cycle_dir_t dir, node_select_t *sel)
1696 {
1697         monitor_t *m = ref->monitor;
1698         desktop_t *d = ref->desktop;
1699         node_t *n = ref->node;
1700         n = (dir == CYCLE_PREV ? prev_node(n) : next_node(n));
1701
1702 #define HANDLE_BOUNDARIES(m, d, n)  \
1703         while (n == NULL) { \
1704                 d = (dir == CYCLE_PREV ? d->prev : d->next); \
1705                 if (d == NULL) { \
1706                         m = (dir == CYCLE_PREV ? m->prev : m->next); \
1707                         if (m == NULL) { \
1708                                 m = (dir == CYCLE_PREV ? mon_tail : mon_head); \
1709                         } \
1710                         d = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head); \
1711                 } \
1712                 n = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root)); \
1713                 if (ref->node == NULL && d == ref->desktop) { \
1714                         break; \
1715                 } \
1716         }
1717         HANDLE_BOUNDARIES(m, d, n);
1718
1719         while (n != ref->node) {
1720                 coordinates_t loc = {m, d, n};
1721                 if (node_matches(&loc, ref, sel)) {
1722                         *dst = loc;
1723                         return true;
1724                 }
1725                 n = (dir == CYCLE_PREV ? prev_node(n) : next_node(n));
1726                 HANDLE_BOUNDARIES(m, d, n);
1727                 if (ref->node == NULL && d == ref->desktop) {
1728                         break;
1729                 }
1730         }
1731 #undef HANDLE_BOUNDARIES
1732         return false;
1733 }
1734
1735 void circulate_leaves(monitor_t *m, desktop_t *d, node_t *n, circulate_dir_t dir)
1736 {
1737         if (tiled_count(n, false) < 2) {
1738                 return;
1739         }
1740         node_t *p = d->focus->parent;
1741         bool focus_first_child = is_first_child(d->focus);
1742         if (dir == CIRCULATE_FORWARD) {
1743                 node_t *e = second_extrema(n);
1744                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1745                         e = prev_leaf(e, n);
1746                 }
1747                 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)) {
1748                         swap_nodes(m, d, f, m, d, s, false);
1749                 }
1750         } else {
1751                 node_t *e = first_extrema(n);
1752                 while (e != NULL && (e->client == NULL || !IS_TILED(e->client))) {
1753                         e = next_leaf(e, n);
1754                 }
1755                 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)) {
1756                         swap_nodes(m, d, f, m, d, s, false);
1757                 }
1758         }
1759         if (p != NULL) {
1760                 node_t *f = focus_first_child ? p->first_child : p->second_child;
1761                 if (is_leaf(f)) {
1762                         if (d == mon->desk) {
1763                                 focus_node(m, d, f);
1764                         } else {
1765                                 activate_node(m, d, f);
1766                         }
1767                 }
1768         }
1769 }
1770
1771 void set_vacant(monitor_t *m, desktop_t *d, node_t *n, bool value)
1772 {
1773         if (n->vacant == value) {
1774                 return;
1775         }
1776
1777         propagate_vacant_downward(m, d, n, value);
1778         propagate_vacant_upward(m, d, n);
1779 }
1780
1781 void set_vacant_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
1782 {
1783         if (n->vacant == value) {
1784                 return;
1785         }
1786
1787         n->vacant = value;
1788
1789         if (value) {
1790                 cancel_presel(m, d, n);
1791         }
1792 }
1793
1794 void propagate_vacant_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
1795 {
1796         if (n == NULL) {
1797                 return;
1798         }
1799
1800         set_vacant_local(m, d, n, value);
1801
1802         propagate_vacant_downward(m, d, n->first_child, value);
1803         propagate_vacant_downward(m, d, n->second_child, value);
1804 }
1805
1806 void propagate_vacant_upward(monitor_t *m, desktop_t *d, node_t *n)
1807 {
1808         if (n == NULL) {
1809                 return;
1810         }
1811
1812         node_t *p = n->parent;
1813
1814         if (p != NULL) {
1815                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
1816         }
1817
1818         propagate_vacant_upward(m, d, p);
1819 }
1820
1821 bool set_layer(monitor_t *m, desktop_t *d, node_t *n, stack_layer_t l)
1822 {
1823         if (n == NULL || n->client == NULL || n->client->layer == l) {
1824                 return false;
1825         }
1826
1827         n->client->last_layer = n->client->layer;
1828         n->client->layer = l;
1829
1830         if (l == LAYER_ABOVE) {
1831                 n->client->wm_flags |= WM_FLAG_ABOVE;
1832                 n->client->wm_flags &= ~WM_FLAG_BELOW;
1833         } else if (l == LAYER_BELOW) {
1834                 n->client->wm_flags |= WM_FLAG_BELOW;
1835                 n->client->wm_flags &= ~WM_FLAG_ABOVE;
1836         } else {
1837                 n->client->wm_flags &= ~(WM_FLAG_ABOVE | WM_FLAG_BELOW);
1838         }
1839
1840         ewmh_wm_state_update(n);
1841
1842         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));
1843
1844         if (d->focus == n) {
1845                 neutralize_occluding_windows(m, d, n);
1846         }
1847
1848         stack(d, n, (d->focus == n));
1849
1850         return true;
1851 }
1852
1853 bool set_state(monitor_t *m, desktop_t *d, node_t *n, client_state_t s)
1854 {
1855         if (n == NULL || n->client == NULL || n->client->state == s) {
1856                 return false;
1857         }
1858
1859         client_t *c = n->client;
1860
1861         bool was_tiled = IS_TILED(c);
1862
1863         c->last_state = c->state;
1864         c->state = s;
1865
1866         switch (c->last_state) {
1867                 case STATE_TILED:
1868                 case STATE_PSEUDO_TILED:
1869                         break;
1870                 case STATE_FLOATING:
1871                         set_floating(m, d, n, false);
1872                         break;
1873                 case STATE_FULLSCREEN:
1874                         set_fullscreen(m, d, n, false);
1875                         break;
1876         }
1877
1878         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));
1879
1880         switch (c->state) {
1881                 case STATE_TILED:
1882                 case STATE_PSEUDO_TILED:
1883                         break;
1884                 case STATE_FLOATING:
1885                         set_floating(m, d, n, true);
1886                         break;
1887                 case STATE_FULLSCREEN:
1888                         set_fullscreen(m, d, n, true);
1889                         break;
1890         }
1891
1892         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));
1893
1894         if (n == m->desk->focus) {
1895                 put_status(SBSC_MASK_REPORT);
1896         }
1897
1898         if (single_monocle && was_tiled != IS_TILED(c)) {
1899                 if (was_tiled && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
1900                         set_layout(m, d, LAYOUT_MONOCLE, false);
1901                 } else if (!was_tiled && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
1902                         set_layout(m, d, d->user_layout, false);
1903                 }
1904         }
1905
1906         return true;
1907 }
1908
1909 void set_floating(monitor_t *m, desktop_t *d, node_t *n, bool value)
1910 {
1911         if (n == NULL) {
1912                 return;
1913         }
1914
1915         cancel_presel(m, d, n);
1916         if (!n->hidden) {
1917                 set_vacant(m, d, n, value);
1918         }
1919
1920         if (!value && d->focus == n) {
1921                 neutralize_occluding_windows(m, d, n);
1922         }
1923
1924         stack(d, n, (d->focus == n));
1925 }
1926
1927 void set_fullscreen(monitor_t *m, desktop_t *d, node_t *n, bool value)
1928 {
1929         if (n == NULL) {
1930                 return;
1931         }
1932
1933         client_t *c = n->client;
1934
1935         cancel_presel(m, d, n);
1936         if (!n->hidden) {
1937                 set_vacant(m, d, n, value);
1938         }
1939
1940         if (value) {
1941                 c->wm_flags |= WM_FLAG_FULLSCREEN;
1942         } else {
1943                 c->wm_flags &= ~WM_FLAG_FULLSCREEN;
1944                 if (d->focus == n) {
1945                         neutralize_occluding_windows(m, d, n);
1946                 }
1947         }
1948
1949         ewmh_wm_state_update(n);
1950         stack(d, n, (d->focus == n));
1951 }
1952
1953 void neutralize_occluding_windows(monitor_t *m, desktop_t *d, node_t *n)
1954 {
1955         bool changed = false;
1956         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
1957                 for (node_t *a = first_extrema(d->root); a != NULL; a = next_leaf(a, d->root)) {
1958                         if (a != f && a->client != NULL && f->client != NULL &&
1959                             IS_FULLSCREEN(a->client) && stack_cmp(f->client, a->client) < 0) {
1960                                 set_state(m, d, a, a->client->last_state);
1961                                 changed = true;
1962                         }
1963                 }
1964         }
1965         if (changed) {
1966                 arrange(m, d);
1967         }
1968 }
1969
1970 void rebuild_constraints_from_leaves(node_t *n)
1971 {
1972         if (n == NULL || is_leaf(n)) {
1973                 return;
1974         } else {
1975                 rebuild_constraints_from_leaves(n->first_child);
1976                 rebuild_constraints_from_leaves(n->second_child);
1977                 update_constraints(n);
1978         }
1979 }
1980
1981 void rebuild_constraints_towards_root(node_t *n)
1982 {
1983         if (n == NULL) {
1984                 return;
1985         }
1986
1987         node_t *p = n->parent;
1988
1989         if (p != NULL) {
1990                 update_constraints(p);
1991         }
1992
1993         rebuild_constraints_towards_root(p);
1994 }
1995
1996 void update_constraints(node_t *n)
1997 {
1998         if (n == NULL || is_leaf(n)) {
1999                 return;
2000         }
2001         if (n->split_type == TYPE_VERTICAL) {
2002                 n->constraints.min_width = n->first_child->constraints.min_width + n->second_child->constraints.min_width;
2003                 n->constraints.min_height = MAX(n->first_child->constraints.min_height, n->second_child->constraints.min_height);
2004         } else {
2005                 n->constraints.min_width = MAX(n->first_child->constraints.min_width, n->second_child->constraints.min_width);
2006                 n->constraints.min_height = n->first_child->constraints.min_height + n->second_child->constraints.min_height;
2007         }
2008 }
2009
2010 void propagate_flags_upward(monitor_t *m, desktop_t *d, node_t *n)
2011 {
2012         if (n == NULL) {
2013                 return;
2014         }
2015
2016         node_t *p = n->parent;
2017
2018         if (p != NULL) {
2019                 set_vacant_local(m, d, p, (p->first_child->vacant && p->second_child->vacant));
2020                 set_hidden_local(m, d, p, (p->first_child->hidden && p->second_child->hidden));
2021                 update_constraints(p);
2022         }
2023
2024         propagate_flags_upward(m, d, p);
2025 }
2026
2027 void set_hidden(monitor_t *m, desktop_t *d, node_t *n, bool value)
2028 {
2029         if (n == NULL || n->hidden == value) {
2030                 return;
2031         }
2032
2033         bool held_focus = is_descendant(d->focus, n);
2034
2035         propagate_hidden_downward(m, d, n, value);
2036         propagate_hidden_upward(m, d, n);
2037
2038         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));
2039
2040         if (held_focus || d->focus == NULL) {
2041                 if (d->focus != NULL) {
2042                         d->focus = NULL;
2043                         draw_border(n, false, (mon == m));
2044                 }
2045                 if (d == mon->desk) {
2046                         focus_node(m, d, d->focus);
2047                 } else {
2048                         activate_node(m, d, d->focus);
2049                 }
2050         }
2051
2052         if (single_monocle) {
2053                 if (value && d->layout != LAYOUT_MONOCLE && tiled_count(d->root, true) <= 1) {
2054                         set_layout(m, d, LAYOUT_MONOCLE, false);
2055                 } else if (!value && d->layout == LAYOUT_MONOCLE && tiled_count(d->root, true) > 1) {
2056                         set_layout(m, d, d->user_layout, false);
2057                 }
2058         }
2059 }
2060
2061 void set_hidden_local(monitor_t *m, desktop_t *d, node_t *n, bool value)
2062 {
2063         if (n->hidden == value) {
2064                 return;
2065         }
2066
2067         n->hidden = value;
2068
2069         if (n->client != NULL) {
2070                 if (n->client->shown) {
2071                         window_set_visibility(n->id, !value);
2072                 }
2073
2074                 if (IS_TILED(n->client)) {
2075                         set_vacant(m, d, n, value);
2076                 }
2077
2078                 if (value) {
2079                         n->client->wm_flags |= WM_FLAG_HIDDEN;
2080                 } else {
2081                         n->client->wm_flags &= ~WM_FLAG_HIDDEN;
2082                 }
2083
2084                 ewmh_wm_state_update(n);
2085         }
2086 }
2087
2088 void propagate_hidden_downward(monitor_t *m, desktop_t *d, node_t *n, bool value)
2089 {
2090         if (n == NULL) {
2091                 return;
2092         }
2093
2094         set_hidden_local(m, d, n, value);
2095
2096         propagate_hidden_downward(m, d, n->first_child, value);
2097         propagate_hidden_downward(m, d, n->second_child, value);
2098 }
2099
2100 void propagate_hidden_upward(monitor_t *m, desktop_t *d, node_t *n)
2101 {
2102         if (n == NULL) {
2103                 return;
2104         }
2105
2106         node_t *p = n->parent;
2107
2108         if (p != NULL) {
2109                 set_hidden_local(m, d, p, p->first_child->hidden && p->second_child->hidden);
2110         }
2111
2112         propagate_hidden_upward(m, d, p);
2113 }
2114
2115 void set_sticky(monitor_t *m, desktop_t *d, node_t *n, bool value)
2116 {
2117         if (n == NULL || n->sticky == value) {
2118                 return;
2119         }
2120
2121         if (d != m->desk) {
2122                 transfer_node(m, d, n, m, m->desk, m->desk->focus, false);
2123         }
2124
2125         n->sticky = value;
2126
2127         if (value) {
2128                 m->sticky_count++;
2129         } else {
2130                 m->sticky_count--;
2131         }
2132
2133         if (n->client != NULL) {
2134                 if (value) {
2135                         n->client->wm_flags |= WM_FLAG_STICKY;
2136                 } else {
2137                         n->client->wm_flags &= ~WM_FLAG_STICKY;
2138                 }
2139                 ewmh_wm_state_update(n);
2140         }
2141
2142         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));
2143
2144         if (n == m->desk->focus) {
2145                 put_status(SBSC_MASK_REPORT);
2146         }
2147 }
2148
2149 void set_private(monitor_t *m, desktop_t *d, node_t *n, bool value)
2150 {
2151         if (n == NULL || n->private == value) {
2152                 return;
2153         }
2154
2155         n->private = value;
2156
2157         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));
2158
2159         if (n == m->desk->focus) {
2160                 put_status(SBSC_MASK_REPORT);
2161         }
2162 }
2163
2164 void set_locked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2165 {
2166         if (n == NULL || n->locked == value) {
2167                 return;
2168         }
2169
2170         n->locked = value;
2171
2172         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));
2173
2174         if (n == m->desk->focus) {
2175                 put_status(SBSC_MASK_REPORT);
2176         }
2177 }
2178
2179 void set_marked(monitor_t *m, desktop_t *d, node_t *n, bool value)
2180 {
2181         if (n == NULL || n->marked == value) {
2182                 return;
2183         }
2184
2185         n->marked = value;
2186
2187         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));
2188
2189         if (n == m->desk->focus) {
2190                 put_status(SBSC_MASK_REPORT);
2191         }
2192 }
2193
2194 void set_urgent(monitor_t *m, desktop_t *d, node_t *n, bool value)
2195 {
2196         if (value && mon->desk->focus == n) {
2197                 return;
2198         }
2199
2200         n->client->urgent = value;
2201
2202         if (value) {
2203                 n->client->wm_flags |= WM_FLAG_DEMANDS_ATTENTION;
2204         } else {
2205                 n->client->wm_flags &= ~WM_FLAG_DEMANDS_ATTENTION;
2206         }
2207
2208         ewmh_wm_state_update(n);
2209
2210         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));
2211         put_status(SBSC_MASK_REPORT);
2212 }
2213
2214 xcb_rectangle_t get_rectangle(monitor_t *m, desktop_t *d, node_t *n)
2215 {
2216         if (n == NULL) {
2217                 return m->rectangle;
2218         }
2219         client_t *c = n->client;
2220         if (c != NULL) {
2221                 if (IS_FLOATING(c)) {
2222                         return c->floating_rectangle;
2223                 } else {
2224                         return c->tiled_rectangle;
2225                 }
2226         } else {
2227                 int wg = (d == NULL ? 0 : (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap));
2228                 xcb_rectangle_t rect = n->rectangle;
2229                 rect.width -= wg;
2230                 rect.height -= wg;
2231                 return rect;
2232         }
2233 }
2234
2235 void listen_enter_notify(node_t *n, bool enable)
2236 {
2237         uint32_t mask = CLIENT_EVENT_MASK | (enable ? XCB_EVENT_MASK_ENTER_WINDOW : 0);
2238         for (node_t *f = first_extrema(n); f != NULL; f = next_leaf(f, n)) {
2239                 if (f->client == NULL) {
2240                         continue;
2241                 }
2242                 xcb_change_window_attributes(dpy, f->id, XCB_CW_EVENT_MASK, &mask);
2243                 if (f->presel != NULL) {
2244                         xcb_change_window_attributes(dpy, f->presel->feedback, XCB_CW_EVENT_MASK, &mask);
2245                 }
2246         }
2247 }
2248
2249 void regenerate_ids_in(node_t *n)
2250 {
2251         if (n == NULL || n->client != NULL) {
2252                 return;
2253         }
2254         n->id = xcb_generate_id(dpy);
2255         regenerate_ids_in(n->first_child);
2256         regenerate_ids_in(n->second_child);
2257 }
2258
2259 #define DEF_FLAG_COUNT(flag) \
2260         unsigned int flag##_count(node_t *n) \
2261         { \
2262                 if (n == NULL) { \
2263                         return 0; \
2264                 } else { \
2265                         return ((n->flag ? 1 : 0) + \
2266                                 flag##_count(n->first_child) + \
2267                                 flag##_count(n->second_child)); \
2268                 } \
2269         }
2270         DEF_FLAG_COUNT(sticky)
2271         DEF_FLAG_COUNT(private)
2272         DEF_FLAG_COUNT(locked)
2273 #undef DEF_FLAG_COUNT