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 <float.h>
  26 #include <limits.h>
  27 #include "bspwm.h"
  28 #include "desktop.h"
  29 #include "ewmh.h"
  30 #include "history.h"
  31 #include "monitor.h"
  32 #include "query.h"
  33 #include "subscribe.h"
  34 #include "settings.h"
  35 #include "stack.h"
  36 #include "window.h"
  37 #include "tree.h"
  38
  39 void arrange(monitor_t *m, desktop_t *d)
  40 {
  41         if (d->root == NULL)
  42                 return;
  43
  44         layout_t set_layout = d->layout;
  45         if (leaf_monocle && tiled_count(d) == 1) {
  46                 d->layout = LAYOUT_MONOCLE;
  47         }
  48
  49         xcb_rectangle_t rect = m->rectangle;
  50         int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap);
  51         rect.x += m->left_padding + d->left_padding + wg;
  52         rect.y += m->top_padding + d->top_padding + wg;
  53         rect.width -= m->left_padding + d->left_padding + d->right_padding + m->right_padding + wg;
  54         rect.height -= m->top_padding + d->top_padding + d->bottom_padding + m->bottom_padding + wg;
  55         apply_layout(m, d, d->root, rect, rect);
  56
  57         d->layout = set_layout;
  58 }
  59
  60 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
  61 {
  62         if (n == NULL)
  63                 return;
  64
  65         n->rectangle = rect;
  66
  67         if (is_leaf(n)) {
  68
  69                 unsigned int bw;
  70                 if ((borderless_monocle && n->client->state == STATE_TILED && d->layout == LAYOUT_MONOCLE)
  71                     || n->client->state == STATE_FULLSCREEN) {
  72                         bw = 0;
  73                 } else {
  74                         bw = n->client->border_width;
  75                 }
  76
  77                 xcb_rectangle_t r;
  78                 client_state_t s = n->client->state;
  79                 if (s == STATE_TILED || s == STATE_PSEUDO_TILED) {
  80                         int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : d->window_gap);
  81                         /* tiled clients */
  82                         if (s == STATE_TILED) {
  83                                 r = rect;
  84                                 int bleed = wg + 2 * bw;
  85                                 r.width = (bleed < r.width ? r.width - bleed : 1);
  86                                 r.height = (bleed < r.height ? r.height - bleed : 1);
  87                         /* pseudo-tiled clients */
  88                         } else {
  89                                 r = n->client->floating_rectangle;
  90                                 if (center_pseudo_tiled) {
  91                                         r.x = rect.x - bw + (rect.width - wg - r.width) / 2;
  92                                         r.y = rect.y - bw + (rect.height - wg - r.height) / 2;
  93                                 } else {
  94                                         r.x = rect.x;
  95                                         r.y = rect.y;
  96                                 }
  97                         }
  98                         n->client->tiled_rectangle = r;
  99                 /* floating clients */
 100                 } else if (s == STATE_FLOATING) {
 101                         r = n->client->floating_rectangle;
 102                 /* fullscreen clients */
 103                 } else {
 104                         r = m->rectangle;
 105                 }
 106
 107                 window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
 108                 window_border_width(n->client->window, bw);
 109                 window_draw_border(n, d->focus == n, m == mon);
 110
 111                 if (frozen_pointer->action == ACTION_NONE) {
 112                         put_status(SBSC_MASK_WINDOW_GEOMETRY, "window_geometry %s %s 0x%X %ux%u+%i+%i\n", m->name, d->name, n->client->window, r.width, r.height, r.x, r.y);
 113                 }
 114
 115                 if (pointer_follows_focus && mon->desk->focus == n && frozen_pointer->action == ACTION_NONE) {
 116                         center_pointer(r);
 117                 }
 118
 119         } else {
 120                 xcb_rectangle_t first_rect;
 121                 xcb_rectangle_t second_rect;
 122
 123                 if (d->layout == LAYOUT_MONOCLE || n->first_child->vacant || n->second_child->vacant) {
 124                         first_rect = second_rect = rect;
 125                 } else {
 126                         unsigned int fence;
 127                         if (n->split_type == TYPE_VERTICAL) {
 128                                 fence = rect.width * n->split_ratio;
 129                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 130                                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 131                         } else {
 132                                 fence = rect.height * n->split_ratio;
 133                                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 134                                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 135                         }
 136                 }
 137
 138                 apply_layout(m, d, n->first_child, first_rect, root_rect);
 139                 apply_layout(m, d, n->second_child, second_rect, root_rect);
 140         }
 141 }
 142
 143 void insert_node(monitor_t *m, desktop_t *d, node_t *n, node_t *f)
 144 {
 145         if (d == NULL || n == NULL)
 146                 return;
 147
 148         /* n: new leaf node */
 149         /* c: new container node */
 150         /* f: focus or insertion anchor */
 151         /* p: parent of focus */
 152         /* g: grand parent of focus */
 153
 154         if (f == NULL)
 155                 f = d->root;
 156
 157         if (f == NULL) {
 158                 d->root = n;
 159         } else {
 160                 node_t *c = make_node();
 161                 node_t *p = f->parent;
 162                 if ((f->client->private ||
 163                      (p != NULL && p->privacy_level > 0)) &&
 164                     f->split_mode == MODE_AUTOMATIC) {
 165                         node_t *closest = NULL;
 166                         node_t *public = NULL;
 167                         closest_public(d, f, &closest, &public);
 168                         if (public != NULL) {
 169                                 f = public;
 170                                 p = f->parent;
 171                         } else {
 172                                 if (closest != NULL) {
 173                                         f = closest;
 174                                         p = f->parent;
 175                                 }
 176                                 f->split_mode = MODE_MANUAL;
 177                                 xcb_rectangle_t rect = f->client->tiled_rectangle;
 178                                 f->split_dir = (rect.width >= rect.height ? DIR_LEFT : DIR_UP);
 179                                 if (f->client->private) {
 180                                         get_opposite(f->split_dir, &f->split_dir);
 181                                         update_privacy_level(f, false);
 182                                 }
 183                         }
 184                 }
 185                 if (p != NULL && f->split_mode == MODE_AUTOMATIC &&
 186                     (p->first_child->vacant || p->second_child->vacant)) {
 187                         f = p;
 188                         p = f->parent;
 189                 }
 190                 n->parent = c;
 191                 c->birth_rotation = f->birth_rotation;
 192                 switch (f->split_mode) {
 193                         case MODE_AUTOMATIC:
 194                                 if (p == NULL) {
 195                                         if (initial_polarity == FIRST_CHILD) {
 196                                                 c->first_child = n;
 197                                                 c->second_child = f;
 198                                         } else {
 199                                                 c->first_child = f;
 200                                                 c->second_child = n;
 201                                         }
 202                                         if (m->rectangle.width > m->rectangle.height)
 203                                                 c->split_type = TYPE_VERTICAL;
 204                                         else
 205                                                 c->split_type = TYPE_HORIZONTAL;
 206                                         f->parent = c;
 207                                         d->root = c;
 208                                 } else {
 209                                         node_t *g = p->parent;
 210                                         c->parent = g;
 211                                         if (g != NULL) {
 212                                                 if (is_first_child(p))
 213                                                         g->first_child = c;
 214                                                 else
 215                                                         g->second_child = c;
 216                                         } else {
 217                                                 d->root = c;
 218                                         }
 219                                         c->split_type = p->split_type;
 220                                         c->split_ratio = p->split_ratio;
 221                                         p->parent = c;
 222                                         int rot;
 223                                         if (is_first_child(f)) {
 224                                                 c->first_child = n;
 225                                                 c->second_child = p;
 226                                                 rot = 90;
 227                                         } else {
 228                                                 c->first_child = p;
 229                                                 c->second_child = n;
 230                                                 rot = 270;
 231                                         }
 232                                         if (IS_TILED(n->client)) {
 233                                                 rotate_tree(p, rot);
 234                                         }
 235                                         n->birth_rotation = rot;
 236                                 }
 237                                 break;
 238                         case MODE_MANUAL:
 239                                 if (p != NULL) {
 240                                         if (is_first_child(f))
 241                                                 p->first_child = c;
 242                                         else
 243                                                 p->second_child = c;
 244                                 }
 245                                 c->split_ratio = f->split_ratio;
 246                                 c->parent = p;
 247                                 f->parent = c;
 248                                 f->birth_rotation = 0;
 249                                 switch (f->split_dir) {
 250                                         case DIR_LEFT:
 251                                                 c->split_type = TYPE_VERTICAL;
 252                                                 c->first_child = n;
 253                                                 c->second_child = f;
 254                                                 break;
 255                                         case DIR_RIGHT:
 256                                                 c->split_type = TYPE_VERTICAL;
 257                                                 c->first_child = f;
 258                                                 c->second_child = n;
 259                                                 break;
 260                                         case DIR_UP:
 261                                                 c->split_type = TYPE_HORIZONTAL;
 262                                                 c->first_child = n;
 263                                                 c->second_child = f;
 264                                                 break;
 265                                         case DIR_DOWN:
 266                                                 c->split_type = TYPE_HORIZONTAL;
 267                                                 c->first_child = f;
 268                                                 c->second_child = n;
 269                                                 break;
 270                                 }
 271                                 if (d->root == f)
 272                                         d->root = c;
 273                                 f->split_mode = MODE_AUTOMATIC;
 274                                 break;
 275                 }
 276                 if (f->vacant) {
 277                         update_vacant_state(f->parent);
 278                 }
 279                 if (f->client != NULL) {
 280                         if (f->client->private) {
 281                                 update_privacy_level(f, true);
 282                         }
 283                 }
 284         }
 285         if (n->client->private) {
 286                 update_privacy_level(n, true);
 287         }
 288         if (d->focus == NULL) {
 289                 d->focus = n;
 290         }
 291         if (n->client->sticky) {
 292                 m->num_sticky++;
 293         }
 294         put_status(SBSC_MASK_REPORT);
 295 }
 296
 297 void activate_node(monitor_t *m, desktop_t *d, node_t *n)
 298 {
 299         if (n != NULL) {
 300                 if (d->focus != NULL && n != d->focus && stack_cmp(n->client, d->focus->client) < 0) {
 301                         neutralize_obscuring_windows(m, d, n);
 302                 }
 303                 stack(n, true);
 304                 if (d->focus != n) {
 305                         window_draw_border(d->focus, false, m == mon);
 306                         window_draw_border(n, true, m == mon);
 307                 }
 308         }
 309         d->focus = n;
 310         put_status(SBSC_MASK_WINDOW_ACTIVATE, "window_activate %s %s 0x%X\n", m->name, d->name, n->client->window);
 311 }
 312
 313 void focus_node(monitor_t *m, desktop_t *d, node_t *n)
 314 {
 315         if (mon->desk != d || n == NULL)
 316                 clear_input_focus();
 317
 318         if (m->num_sticky > 0 && d != m->desk) {
 319                 node_t *a = first_extrema(m->desk->root);
 320                 sticky_still = false;
 321                 while (a != NULL) {
 322                         node_t *b = next_leaf(a, m->desk->root);
 323                         if (a->client->sticky)
 324                                 transfer_node(m, m->desk, a, m, d, d->focus);
 325                         a = b;
 326                 }
 327                 sticky_still = true;
 328                 if (n == NULL && d->focus != NULL)
 329                         n = d->focus;
 330         }
 331
 332         if (n != NULL) {
 333                 if (n->client->urgent) {
 334                         n->client->urgent = false;
 335                         put_status(SBSC_MASK_REPORT);
 336                 }
 337                 if (d->focus != NULL && n != d->focus && stack_cmp(n->client, d->focus->client) < 0) {
 338                         neutralize_obscuring_windows(m, d, n);
 339                 }
 340         }
 341
 342         if (mon != m) {
 343                 for (desktop_t *cd = mon->desk_head; cd != NULL; cd = cd->next) {
 344                         window_draw_border(cd->focus, true, false);
 345                 }
 346                 for (desktop_t *cd = m->desk_head; cd != NULL; cd = cd->next) {
 347                         if (cd != d) {
 348                                 window_draw_border(cd->focus, true, true);
 349                         }
 350                 }
 351                 if (d->focus == n) {
 352                         window_draw_border(n, true, true);
 353                 }
 354         }
 355
 356         if (d->focus != n) {
 357                 window_draw_border(d->focus, false, true);
 358                 window_draw_border(n, true, true);
 359         }
 360
 361         focus_desktop(m, d);
 362
 363         d->focus = n;
 364
 365         if (n == NULL) {
 366                 history_add(m, d, NULL);
 367                 ewmh_update_active_window();
 368                 return;
 369         } else {
 370                 stack(n, true);
 371         }
 372
 373         put_status(SBSC_MASK_WINDOW_FOCUS, "window_focus %s %s 0x%X\n", m->name, d->name, n->client->window);
 374
 375         history_add(m, d, n);
 376         set_input_focus(n);
 377
 378         if (focus_follows_pointer) {
 379                 xcb_window_t win = XCB_NONE;
 380                 query_pointer(&win, NULL);
 381                 if (win != n->client->window) {
 382                         enable_motion_recorder();
 383                 } else {
 384                         disable_motion_recorder();
 385                 }
 386         }
 387
 388         if (pointer_follows_focus) {
 389                 center_pointer(get_rectangle(m, n->client));
 390         }
 391
 392         ewmh_update_active_window();
 393 }
 394
 395 void update_current(void)
 396 {
 397         focus_node(mon, mon->desk, mon->desk->focus);
 398 }
 399
 400 node_t *make_node(void)
 401 {
 402         node_t *n = malloc(sizeof(node_t));
 403         n->parent = n->first_child = n->second_child = NULL;
 404         n->split_ratio = split_ratio;
 405         n->split_mode = MODE_AUTOMATIC;
 406         n->split_type = TYPE_VERTICAL;
 407         n->split_dir = DIR_RIGHT;
 408         n->birth_rotation = 0;
 409         n->privacy_level = 0;
 410         n->client = NULL;
 411         n->vacant = false;
 412         return n;
 413 }
 414
 415 client_t *make_client(xcb_window_t win, unsigned int border_width)
 416 {
 417         client_t *c = malloc(sizeof(client_t));
 418         c->window = win;
 419         c->state = c->last_state = STATE_TILED;
 420         c->layer = c->last_layer = LAYER_NORMAL;
 421         snprintf(c->class_name, sizeof(c->class_name), "%s", MISSING_VALUE);
 422         snprintf(c->instance_name, sizeof(c->instance_name), "%s", MISSING_VALUE);
 423         c->border_width = border_width;
 424         c->locked = c->sticky = c->urgent = c->private = c->icccm_focus = false;
 425         c->icccm_input = true;
 426         xcb_icccm_get_wm_protocols_reply_t protocols;
 427         if (xcb_icccm_get_wm_protocols_reply(dpy, xcb_icccm_get_wm_protocols(dpy, win, ewmh->WM_PROTOCOLS), &protocols, NULL) == 1) {
 428                 if (has_proto(WM_TAKE_FOCUS, &protocols)) {
 429                         c->icccm_focus = true;
 430                 }
 431                 xcb_icccm_get_wm_protocols_reply_wipe(&protocols);
 432         }
 433         c->num_states = 0;
 434         xcb_ewmh_get_atoms_reply_t wm_state;
 435         if (xcb_ewmh_get_wm_state_reply(ewmh, xcb_ewmh_get_wm_state(ewmh, win), &wm_state, NULL) == 1) {
 436                 for (unsigned int i = 0; i < wm_state.atoms_len && i < MAX_STATE; i++) {
 437                         ewmh_wm_state_add(c, wm_state.atoms[i]);
 438                 }
 439                 xcb_ewmh_get_atoms_reply_wipe(&wm_state);
 440         }
 441         xcb_icccm_wm_hints_t hints;
 442         if (xcb_icccm_get_wm_hints_reply(dpy, xcb_icccm_get_wm_hints(dpy, win), &hints, NULL) == 1
 443             && (hints.flags & XCB_ICCCM_WM_HINT_INPUT)) {
 444                 c->icccm_input = hints.input;
 445         }
 446         return c;
 447 }
 448
 449 bool is_leaf(node_t *n)
 450 {
 451         return (n != NULL && n->first_child == NULL && n->second_child == NULL);
 452 }
 453
 454 bool is_first_child(node_t *n)
 455 {
 456         return (n != NULL && n->parent != NULL && n->parent->first_child == n);
 457 }
 458
 459 bool is_second_child(node_t *n)
 460 {
 461         return (n != NULL && n->parent != NULL && n->parent->second_child == n);
 462 }
 463
 464 void reset_mode(coordinates_t *loc)
 465 {
 466         if (loc->node != NULL) {
 467                 loc->node->split_mode = MODE_AUTOMATIC;
 468                 window_draw_border(loc->node, loc->desktop->focus == loc->node, mon == loc->monitor);
 469         } else if (loc->desktop != NULL) {
 470                 for (node_t *a = first_extrema(loc->desktop->root); a != NULL; a = next_leaf(a, loc->desktop->root)) {
 471                         a->split_mode = MODE_AUTOMATIC;
 472                         window_draw_border(a, loc->desktop->focus == a, mon == loc->monitor);
 473                 }
 474         }
 475 }
 476
 477 node_t *brother_tree(node_t *n)
 478 {
 479         if (n == NULL || n->parent == NULL)
 480                 return NULL;
 481         if (is_first_child(n))
 482                 return n->parent->second_child;
 483         else
 484                 return n->parent->first_child;
 485 }
 486
 487 void closest_public(desktop_t *d, node_t *n, node_t **closest, node_t **public)
 488 {
 489         if (n == NULL)
 490                 return;
 491         node_t *prev = prev_leaf(n, d->root);
 492         node_t *next = next_leaf(n, d->root);
 493         while (prev != NULL || next != NULL) {
 494 #define TESTLOOP(n) \
 495                 if (n != NULL) { \
 496                         if (IS_TILED(n->client)) { \
 497                                 if (n->privacy_level == 0) { \
 498                                         if (n->parent == NULL || n->parent->privacy_level == 0) { \
 499                                                 *public = n; \
 500                                                 return; \
 501                                         } else if (*closest == NULL) { \
 502                                                 *closest = n; \
 503                                         } \
 504                                 } \
 505                         } \
 506                         n = n##_leaf(n, d->root); \
 507                 }
 508                 TESTLOOP(prev)
 509                 TESTLOOP(next)
 510 #undef TESTLOOP
 511         }
 512 }
 513
 514 node_t *first_extrema(node_t *n)
 515 {
 516         if (n == NULL)
 517                 return NULL;
 518         else if (n->first_child == NULL)
 519                 return n;
 520         else
 521                 return first_extrema(n->first_child);
 522 }
 523
 524 node_t *second_extrema(node_t *n)
 525 {
 526         if (n == NULL)
 527                 return NULL;
 528         else if (n->second_child == NULL)
 529                 return n;
 530         else
 531                 return second_extrema(n->second_child);
 532 }
 533
 534 node_t *next_leaf(node_t *n, node_t *r)
 535 {
 536         if (n == NULL)
 537                 return NULL;
 538         node_t *p = n;
 539         while (is_second_child(p) && p != r)
 540                 p = p->parent;
 541         if (p == r)
 542                 return NULL;
 543         return first_extrema(p->parent->second_child);
 544 }
 545
 546 node_t *prev_leaf(node_t *n, node_t *r)
 547 {
 548         if (n == NULL)
 549                 return NULL;
 550         node_t *p = n;
 551         while (is_first_child(p) && p != r)
 552                 p = p->parent;
 553         if (p == r)
 554                 return NULL;
 555         return second_extrema(p->parent->first_child);
 556 }
 557
 558 node_t *next_tiled_leaf(desktop_t *d, node_t *n, node_t *r)
 559 {
 560         node_t *next = next_leaf(n, r);
 561         if (next == NULL || IS_TILED(next->client))
 562                 return next;
 563         else
 564                 return next_tiled_leaf(d, next, r);
 565 }
 566
 567 node_t *prev_tiled_leaf(desktop_t *d, node_t *n, node_t *r)
 568 {
 569         node_t *prev = prev_leaf(n, r);
 570         if (prev == NULL || IS_TILED(prev->client))
 571                 return prev;
 572         else
 573                 return prev_tiled_leaf(d, prev, r);
 574 }
 575
 576 /* Returns true if *b* is adjacent to *a* in the direction *dir* */
 577 bool is_adjacent(node_t *a, node_t *b, direction_t dir)
 578 {
 579         switch (dir) {
 580                 case DIR_RIGHT:
 581                         return (a->rectangle.x + a->rectangle.width) == b->rectangle.x;
 582                         break;
 583                 case DIR_DOWN:
 584                         return (a->rectangle.y + a->rectangle.height) == b->rectangle.y;
 585                         break;
 586                 case DIR_LEFT:
 587                         return (b->rectangle.x + b->rectangle.width) == a->rectangle.x;
 588                         break;
 589                 case DIR_UP:
 590                         return (b->rectangle.y + b->rectangle.height) == a->rectangle.y;
 591                         break;
 592         }
 593         return false;
 594 }
 595
 596 node_t *find_fence(node_t *n, direction_t dir)
 597 {
 598         node_t *p;
 599
 600         if (n == NULL)
 601                 return NULL;
 602
 603         p = n->parent;
 604
 605         while (p != NULL) {
 606                 if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y) ||
 607                     (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x) ||
 608                     (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height)) ||
 609                     (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 610                         return p;
 611                 p = p->parent;
 612         }
 613
 614         return NULL;
 615 }
 616
 617 node_t *nearest_neighbor(monitor_t *m, desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 618 {
 619         if (n == NULL || IS_FULLSCREEN(n->client) ||
 620             (d->layout == LAYOUT_MONOCLE && IS_TILED(n->client)))
 621                 return NULL;
 622
 623         node_t *nearest = NULL;
 624         if (history_aware_focus)
 625                 nearest = nearest_from_history(m, d, n, dir, sel);
 626     if (nearest == NULL) {
 627         if (focus_by_distance) {
 628             nearest = nearest_from_distance(m, d, n, dir, sel);
 629         } else {
 630             nearest = nearest_from_tree(m, d, n, dir, sel);
 631         }
 632     }
 633     return nearest;
 634 }
 635
 636 node_t *nearest_from_tree(monitor_t *m, desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 637 {
 638     if (n == NULL) {
 639         return NULL;
 640     }
 641
 642     node_t *fence = find_fence(n, dir);
 643
 644     if (fence == NULL)
 645         return NULL;
 646
 647     node_t *nearest = NULL;
 648
 649     if (dir == DIR_UP || dir == DIR_LEFT) {
 650         nearest = second_extrema(fence->first_child);
 651     } else if (dir == DIR_DOWN || dir == DIR_RIGHT) {
 652         nearest = first_extrema(fence->second_child);
 653     }
 654
 655         coordinates_t ref = {m, d, n};
 656         coordinates_t loc = {m, d, nearest};
 657
 658         if (node_matches(&loc, &ref, sel)) {
 659                 return nearest;
 660         } else {
 661                 return NULL;
 662         }
 663 }
 664
 665 node_t *nearest_from_history(monitor_t *m, desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 666 {
 667         if (n == NULL || !IS_TILED(n->client)) {
 668                 return NULL;
 669         }
 670
 671         node_t *target = find_fence(n, dir);
 672         if (target == NULL)
 673                 return NULL;
 674         if (dir == DIR_UP || dir == DIR_LEFT)
 675                 target = target->first_child;
 676         else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 677                 target = target->second_child;
 678
 679         node_t *nearest = NULL;
 680         int min_rank = INT_MAX;
 681         coordinates_t ref = {m, d, n};
 682
 683         for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 684                 if (a->vacant || !is_adjacent(n, a, dir) || a == n)
 685                         continue;
 686                 coordinates_t loc = {m, d, a};
 687                 if (!node_matches(&loc, &ref, sel))
 688                         continue;
 689
 690                 int rank = history_rank(d, a);
 691                 if (rank >= 0 && rank < min_rank) {
 692                         nearest = a;
 693                         min_rank = rank;
 694                 }
 695         }
 696
 697         return nearest;
 698 }
 699
 700 node_t *nearest_from_distance(monitor_t *m, desktop_t *d, node_t *n, direction_t dir, client_select_t sel)
 701 {
 702         if (n == NULL)
 703                 return NULL;
 704
 705         node_t *target = NULL;
 706
 707         if (IS_TILED(n->client)) {
 708                 target = find_fence(n, dir);
 709                 if (target == NULL)
 710                         return NULL;
 711                 if (dir == DIR_UP || dir == DIR_LEFT)
 712                         target = target->first_child;
 713                 else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 714                         target = target->second_child;
 715         } else {
 716                 target = d->root;
 717         }
 718
 719         node_t *nearest = NULL;
 720         direction_t dir2;
 721         xcb_point_t pt;
 722         xcb_point_t pt2;
 723         get_side_handle(n->client, dir, &pt);
 724         get_opposite(dir, &dir2);
 725         double ds = DBL_MAX;
 726         coordinates_t ref = {m, d, n};
 727
 728         for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 729                 coordinates_t loc = {m, d, a};
 730                 if (a == n ||
 731                     !node_matches(&loc, &ref, sel) ||
 732                     IS_TILED(a->client) != IS_TILED(n->client) ||
 733                     (IS_TILED(a->client) && !is_adjacent(n, a, dir)))
 734                         continue;
 735
 736                 get_side_handle(a->client, dir2, &pt2);
 737                 double ds2 = distance(pt, pt2);
 738                 if (ds2 < ds) {
 739                         ds = ds2;
 740                         nearest = a;
 741                 }
 742         }
 743
 744         return nearest;
 745 }
 746
 747 void get_opposite(direction_t src, direction_t *dst)
 748 {
 749         switch (src) {
 750                 case DIR_RIGHT:
 751                         *dst = DIR_LEFT;
 752                         break;
 753                 case DIR_DOWN:
 754                         *dst = DIR_UP;
 755                         break;
 756                 case DIR_LEFT:
 757                         *dst = DIR_RIGHT;
 758                         break;
 759                 case DIR_UP:
 760                         *dst = DIR_DOWN;
 761                         break;
 762         }
 763 }
 764
 765 int tiled_area(node_t *n)
 766 {
 767         if (n == NULL)
 768                 return -1;
 769         xcb_rectangle_t rect = n->client->tiled_rectangle;
 770         return rect.width * rect.height;
 771 }
 772
 773 int tiled_count(desktop_t *d)
 774 {
 775         int cnt = 0;
 776         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 777                 if (IS_TILED(f->client)) {
 778                         cnt++;
 779                 }
 780         }
 781         return cnt;
 782 }
 783
 784 node_t *find_biggest(monitor_t *m, desktop_t *d, node_t *n, client_select_t sel)
 785 {
 786         if (d == NULL)
 787                 return NULL;
 788
 789         node_t *r = NULL;
 790         int r_area = tiled_area(r);
 791         coordinates_t ref = {m, d, n};
 792
 793         for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 794                 coordinates_t loc = {m, d, f};
 795                 if (IS_FLOATING(f->client) || !node_matches(&loc, &ref, sel))
 796                         continue;
 797                 int f_area = tiled_area(f);
 798                 if (r == NULL) {
 799                         r = f;
 800                         r_area = f_area;
 801                 } else if (f_area > r_area) {
 802                         r = f;
 803                         r_area = f_area;
 804                 }
 805         }
 806
 807         return r;
 808 }
 809
 810 void rotate_tree(node_t *n, int deg)
 811 {
 812         if (n == NULL || is_leaf(n) || deg == 0)
 813                 return;
 814
 815         node_t *tmp;
 816
 817         if ((deg == 90 && n->split_type == TYPE_HORIZONTAL) ||
 818             (deg == 270 && n->split_type == TYPE_VERTICAL) ||
 819             deg == 180) {
 820                 tmp = n->first_child;
 821                 n->first_child = n->second_child;
 822                 n->second_child = tmp;
 823                 n->split_ratio = 1.0 - n->split_ratio;
 824         }
 825
 826         if (deg != 180) {
 827                 if (n->split_type == TYPE_HORIZONTAL)
 828                         n->split_type = TYPE_VERTICAL;
 829                 else if (n->split_type == TYPE_VERTICAL)
 830                         n->split_type = TYPE_HORIZONTAL;
 831         }
 832
 833         rotate_tree(n->first_child, deg);
 834         rotate_tree(n->second_child, deg);
 835 }
 836
 837 void rotate_brother(node_t *n)
 838 {
 839         rotate_tree(brother_tree(n), n->birth_rotation);
 840 }
 841
 842 void unrotate_tree(node_t *n, int rot)
 843 {
 844         if (rot == 0)
 845                 return;
 846         rotate_tree(n, 360 - rot);
 847 }
 848
 849 void unrotate_brother(node_t *n)
 850 {
 851         unrotate_tree(brother_tree(n), n->birth_rotation);
 852 }
 853
 854 void flip_tree(node_t *n, flip_t flp)
 855 {
 856         if (n == NULL || is_leaf(n))
 857                 return;
 858
 859         node_t *tmp;
 860
 861         if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL) ||
 862             (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
 863                 tmp = n->first_child;
 864                 n->first_child = n->second_child;
 865                 n->second_child = tmp;
 866                 n->split_ratio = 1.0 - n->split_ratio;
 867         }
 868
 869         flip_tree(n->first_child, flp);
 870         flip_tree(n->second_child, flp);
 871 }
 872
 873 void equalize_tree(node_t *n)
 874 {
 875         if (n == NULL || n->vacant) {
 876                 return;
 877         } else {
 878                 n->split_ratio = split_ratio;
 879                 equalize_tree(n->first_child);
 880                 equalize_tree(n->second_child);
 881         }
 882 }
 883
 884 int balance_tree(node_t *n)
 885 {
 886         if (n == NULL || n->vacant) {
 887                 return 0;
 888         } else if (is_leaf(n)) {
 889                 return 1;
 890         } else {
 891                 int b1 = balance_tree(n->first_child);
 892                 int b2 = balance_tree(n->second_child);
 893                 int b = b1 + b2;
 894                 if (b1 > 0 && b2 > 0)
 895                         n->split_ratio = (double) b1 / b;
 896                 return b;
 897         }
 898 }
 899
 900 void unlink_node(monitor_t *m, desktop_t *d, node_t *n)
 901 {
 902         if (d == NULL || n == NULL)
 903                 return;
 904
 905         node_t *p = n->parent;
 906
 907         if (p == NULL) {
 908                 d->root = NULL;
 909                 d->focus = NULL;
 910         } else {
 911                 if (n->client->private)
 912                         update_privacy_level(n, false);
 913
 914                 node_t *b;
 915                 node_t *g = p->parent;
 916
 917                 if (is_first_child(n)) {
 918                         b = p->second_child;
 919                         if (!n->vacant)
 920                                 unrotate_tree(b, n->birth_rotation);
 921                 } else {
 922                         b = p->first_child;
 923                         if (!n->vacant)
 924                                 unrotate_tree(b, n->birth_rotation);
 925                 }
 926
 927                 b->parent = g;
 928
 929                 if (g != NULL) {
 930                         if (is_first_child(p))
 931                                 g->first_child = b;
 932                         else
 933                                 g->second_child = b;
 934                 } else {
 935                         d->root = b;
 936                 }
 937
 938                 b->birth_rotation = p->birth_rotation;
 939                 n->parent = NULL;
 940                 free(p);
 941                 update_vacant_state(b->parent);
 942
 943                 if (n == d->focus) {
 944                         d->focus = history_get_node(d, n);
 945                         // fallback to the first extrema (`n` is not reachable)
 946                         if (d->focus == NULL)
 947                                 d->focus = first_extrema(d->root);
 948                 }
 949         }
 950         if (n->client->sticky)
 951                 m->num_sticky--;
 952         put_status(SBSC_MASK_REPORT);
 953 }
 954
 955 void remove_node(monitor_t *m, desktop_t *d, node_t *n)
 956 {
 957         if (n == NULL)
 958                 return;
 959
 960         bool focused = (n == mon->desk->focus);
 961
 962         unlink_node(m, d, n);
 963         history_remove(d, n);
 964         remove_stack_node(n);
 965         free(n->client);
 966         free(n);
 967
 968         num_clients--;
 969         ewmh_update_client_list();
 970
 971         if (focused)
 972                 update_current();
 973 }
 974
 975 void destroy_tree(node_t *n)
 976 {
 977         if (n == NULL)
 978                 return;
 979         node_t *first_tree = n->first_child;
 980         node_t *second_tree = n->second_child;
 981         if (n->client != NULL) {
 982                 free(n->client);
 983                 num_clients--;
 984         }
 985         free(n);
 986         destroy_tree(first_tree);
 987         destroy_tree(second_tree);
 988 }
 989
 990 bool swap_nodes(monitor_t *m1, desktop_t *d1, node_t *n1, monitor_t *m2, desktop_t *d2, node_t *n2)
 991 {
 992         if (n1 == NULL || n2 == NULL || n1 == n2
 993             || (d1 != d2 && (n1->client->sticky || n2->client->sticky))) {
 994                 return false;
 995         }
 996
 997         put_status(SBSC_MASK_WINDOW_SWAP, "window_swap %s %s 0x%X %s %s 0x%X\n", m1->name, d1->name, n1->client->window, m2->name, d2->name, n2->client->window);
 998
 999         node_t *pn1 = n1->parent;
1000         node_t *pn2 = n2->parent;
1001         bool n1_first_child = is_first_child(n1);
1002         bool n2_first_child = is_first_child(n2);
1003         int br1 = n1->birth_rotation;
1004         int br2 = n2->birth_rotation;
1005         int pl1 = n1->privacy_level;
1006         int pl2 = n2->privacy_level;
1007
1008         if (pn1 != NULL) {
1009                 if (n1_first_child)
1010                         pn1->first_child = n2;
1011                 else
1012                         pn1->second_child = n2;
1013         }
1014
1015         if (pn2 != NULL) {
1016                 if (n2_first_child)
1017                         pn2->first_child = n1;
1018                 else
1019                         pn2->second_child = n1;
1020         }
1021
1022         n1->parent = pn2;
1023         n2->parent = pn1;
1024         n1->birth_rotation = br2;
1025         n2->birth_rotation = br1;
1026         n1->privacy_level = pl2;
1027         n2->privacy_level = pl1;
1028
1029         if (n1->vacant != n2->vacant) {
1030                 update_vacant_state(n1->parent);
1031                 update_vacant_state(n2->parent);
1032         }
1033
1034         if (n1->client->private != n2->client->private) {
1035                 n1->client->private = !n1->client->private;
1036                 n2->client->private = !n2->client->private;
1037         }
1038
1039         if (d1 != d2) {
1040                 if (d1->root == n1)
1041                         d1->root = n2;
1042                 if (d1->focus == n1)
1043                         d1->focus = n2;
1044                 if (d2->root == n2)
1045                         d2->root = n1;
1046                 if (d2->focus == n2)
1047                         d2->focus = n1;
1048
1049                 if (m1 != m2) {
1050                         translate_client(m2, m1, n2->client);
1051                         translate_client(m1, m2, n1->client);
1052                 }
1053
1054                 ewmh_set_wm_desktop(n1, d2);
1055                 ewmh_set_wm_desktop(n2, d1);
1056                 history_swap_nodes(m1, d1, n1, m2, d2, n2);
1057
1058                 if (m1->desk != d1 && m2->desk == d2) {
1059                         window_show(n1->client->window);
1060                         window_hide(n2->client->window);
1061                 } else if (m1->desk == d1 && m2->desk != d2) {
1062                         window_hide(n1->client->window);
1063                         window_show(n2->client->window);
1064                 }
1065
1066                 update_input_focus();
1067         }
1068
1069         return true;
1070 }
1071
1072 bool transfer_node(monitor_t *ms, desktop_t *ds, node_t *ns, monitor_t *md, desktop_t *dd, node_t *nd)
1073 {
1074         if (ns == NULL || ns == nd || (sticky_still && ns->client->sticky)) {
1075                 return false;
1076         }
1077
1078         put_status(SBSC_MASK_WINDOW_TRANSFER, "window_transfer %s %s 0x%X %s %s 0x%X\n", ms->name, ds->name, ns->client->window, md->name, dd->name, nd!=NULL?nd->client->window:0);
1079
1080         bool focused = (ns == mon->desk->focus);
1081         bool active = (ns == ds->focus);
1082
1083         if (focused) {
1084                 clear_input_focus();
1085         }
1086
1087         unlink_node(ms, ds, ns);
1088         insert_node(md, dd, ns, nd);
1089
1090         if (md != ms) {
1091                 translate_client(ms, md, ns->client);
1092         }
1093
1094         if (ds != dd) {
1095                 ewmh_set_wm_desktop(ns, dd);
1096                 if (!ns->client->sticky) {
1097                         if (ds == ms->desk && dd != md->desk) {
1098                                 window_hide(ns->client->window);
1099                         } else if (ds != ms->desk && dd == md->desk) {
1100                                 window_show(ns->client->window);
1101                         }
1102                 }
1103         }
1104
1105         history_transfer_node(md, dd, ns);
1106         stack(ns, false);
1107
1108         if (ds == dd) {
1109                 if (focused) {
1110                         focus_node(md, dd, ns);
1111                 } else if (active) {
1112                         activate_node(md, dd, ns);
1113                 }
1114         } else {
1115                 if (focused) {
1116                         update_current();
1117                 } else if (ns == mon->desk->focus) {
1118                         update_input_focus();
1119                 }
1120         }
1121
1122         arrange(ms, ds);
1123
1124         if (ds != dd) {
1125                 arrange(md, dd);
1126         }
1127
1128         return true;
1129 }
1130
1131 node_t *closest_node(monitor_t *m, desktop_t *d, node_t *n, cycle_dir_t dir, client_select_t sel)
1132 {
1133         if (n == NULL)
1134                 return NULL;
1135
1136         node_t *f = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
1137         if (f == NULL)
1138                 f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
1139
1140         coordinates_t ref = {m, d, n};
1141         while (f != n) {
1142                 coordinates_t loc = {m, d, f};
1143                 if (node_matches(&loc, &ref, sel))
1144                         return f;
1145                 f = (dir == CYCLE_PREV ? prev_leaf(f, d->root) : next_leaf(f, d->root));
1146                 if (f == NULL)
1147                         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
1148         }
1149         return NULL;
1150 }
1151
1152 void circulate_leaves(monitor_t *m, desktop_t *d, circulate_dir_t dir)
1153 {
1154         if (d == NULL || d->root == NULL || d->focus == NULL || is_leaf(d->root))
1155                 return;
1156         node_t *p = d->focus->parent;
1157         bool focus_first_child = is_first_child(d->focus);
1158         if (dir == CIRCULATE_FORWARD)
1159                 for (node_t *s = second_extrema(d->root), *f = prev_tiled_leaf(d, s, d->root); f != NULL; s = prev_tiled_leaf(d, f, d->root), f = prev_tiled_leaf(d, s, d->root))
1160                         swap_nodes(m, d, f, m, d, s);
1161         else
1162                 for (node_t *f = first_extrema(d->root), *s = next_tiled_leaf(d, f, d->root); s != NULL; f = next_tiled_leaf(d, s, d->root), s = next_tiled_leaf(d, f, d->root))
1163                         swap_nodes(m, d, f, m, d, s);
1164         if (focus_first_child)
1165                 focus_node(m, d, p->first_child);
1166         else
1167                 focus_node(m, d, p->second_child);
1168 }
1169
1170 void update_vacant_state(node_t *n)
1171 {
1172         if (n == NULL)
1173                 return;
1174
1175         /* n is not a leaf */
1176         node_t *p = n;
1177
1178         while (p != NULL) {
1179                 p->vacant = (p->first_child->vacant && p->second_child->vacant);
1180                 p = p->parent;
1181         }
1182 }
1183
1184 void update_privacy_level(node_t *n, bool value)
1185 {
1186         int v = (value ? 1 : -1);
1187         for (node_t *p = n; p != NULL; p = p->parent)
1188                 p->privacy_level += v;
1189 }