tree.c

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