tree.c

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