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