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