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