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