tree.c

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