src/tree.c

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