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