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