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