tree.c

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