tree.c

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