tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <ctype.h>
   5 #include <math.h>
   6 #include <float.h>
   7 #include <xcb/xcb.h>
   8 #include <xcb/xcb_event.h>
   9 #include "settings.h"
  10 #include "helpers.h"
  11 #include "window.h"
  12 #include "types.h"
  13 #include "bspwm.h"
  14 #include "ewmh.h"
  15 #include "tree.h"
  16
  17 bool is_leaf(node_t *n)
  18 {
  19     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  20 }
  21
  22 bool is_tiled(client_t *c)
  23 {
  24     if (c == NULL)
  25         return false;
  26     return (!c->floating && !c->transient && !c->fullscreen);
  27 }
  28
  29 bool is_floating(client_t *c)
  30 {
  31     if (c == NULL)
  32         return false;
  33     return (c->floating && !c->fullscreen);
  34 }
  35
  36 bool is_first_child(node_t *n)
  37 {
  38     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  39 }
  40
  41 bool is_second_child(node_t *n)
  42 {
  43     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  44 }
  45
  46 void change_split_ratio(node_t *n, value_change_t chg)
  47 {
  48     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  49 }
  50
  51 node_t *first_extrema(node_t *n)
  52 {
  53     if (n == NULL)
  54         return NULL;
  55     else if (n->first_child == NULL)
  56         return n;
  57     else
  58         return first_extrema(n->first_child);
  59 }
  60
  61 node_t *second_extrema(node_t *n)
  62 {
  63     if (n == NULL)
  64         return NULL;
  65     else if (n->second_child == NULL)
  66         return n;
  67     else
  68         return second_extrema(n->second_child);
  69 }
  70
  71 node_t *next_leaf(node_t *n, node_t *r)
  72 {
  73     if (n == NULL)
  74         return NULL;
  75     node_t *p = n;
  76     while (is_second_child(p) && p != r)
  77         p = p->parent;
  78     if (p == r)
  79         return NULL;
  80     return first_extrema(p->parent->second_child);
  81 }
  82
  83 node_t *prev_leaf(node_t *n, node_t *r)
  84 {
  85     if (n == NULL)
  86         return NULL;
  87     node_t *p = n;
  88     while (is_first_child(p) && p != r)
  89         p = p->parent;
  90     if (p == r)
  91         return NULL;
  92     return second_extrema(p->parent->first_child);
  93 }
  94
  95 node_t *find_fence(node_t *n, direction_t dir)
  96 {
  97     node_t *p;
  98
  99     if (n == NULL)
 100         return NULL;
 101
 102     p = n->parent;
 103
 104     while (p != NULL) {
 105         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
 106                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
 107                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
 108                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 109             return p;
 110         p = p->parent;
 111     }
 112
 113     return NULL;
 114 }
 115
 116 node_t *find_neighbor(node_t *n, direction_t dir)
 117 {
 118     node_t *fence = find_fence(n, dir);
 119
 120     if (fence == NULL)
 121         return NULL;
 122
 123     if (dir == DIR_UP || dir == DIR_LEFT)
 124         return second_extrema(fence->first_child);
 125     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 126         return first_extrema(fence->second_child);
 127
 128     return NULL;
 129 }
 130
 131 void get_opposite(direction_t src, direction_t* dst)
 132 {
 133     switch (src) {
 134         case DIR_RIGHT:
 135             *dst = DIR_LEFT;
 136             break;
 137         case DIR_DOWN:
 138             *dst = DIR_UP;
 139             break;
 140         case DIR_LEFT:
 141             *dst = DIR_RIGHT;
 142             break;
 143         case DIR_UP:
 144             *dst = DIR_DOWN;
 145             break;
 146     }
 147 }
 148
 149 node_t *nearest_neighbor(desktop_t *d, node_t *n, direction_t dir)
 150 {
 151     if (n == NULL)
 152         return NULL;
 153
 154     node_t *target = NULL;
 155     if (is_tiled(n->client)) {
 156         target = find_fence(n, dir);
 157         if (target == NULL)
 158             return NULL;
 159         if (dir == DIR_UP || dir == DIR_LEFT)
 160             target = target->first_child;
 161         else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 162             target = target->second_child;
 163     } else {
 164         target = d->root;
 165     }
 166     node_t *nearest = NULL;
 167     direction_t dir2;
 168     xcb_point_t pt;
 169     xcb_point_t pt2;
 170     get_side_handle(n->client, dir, &pt);
 171     get_opposite(dir, &dir2);
 172     double ds = DBL_MAX;
 173     for (node_t *a = first_extrema(target); a != NULL; a = next_leaf(a, target)) {
 174         if (is_tiled(a->client) != is_tiled(n->client) || a == n)
 175             continue;
 176         get_side_handle(a->client, dir2, &pt2);
 177         double ds2 = distance(pt, pt2);
 178         if (ds2 < ds) {
 179             ds = ds2;
 180             nearest = a;
 181         }
 182     }
 183     return nearest;
 184 }
 185
 186 int tiled_area(node_t *n)
 187 {
 188     if (n == NULL)
 189         return -1;
 190     xcb_rectangle_t rect = n->client->tiled_rectangle;
 191     return rect.width * rect.height;
 192 }
 193
 194 node_t *find_biggest(desktop_t *d)
 195 {
 196     if (d == NULL)
 197         return NULL;
 198
 199     node_t *r = NULL;
 200     int r_area = tiled_area(r);
 201
 202     for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root)) {
 203         int f_area = tiled_area(f);
 204         if (r == NULL) {
 205             r = f;
 206             r_area = f_area;
 207         } else if (f_area > r_area) {
 208             r = f;
 209             r_area = f_area;
 210         }
 211     }
 212
 213     return r;
 214 }
 215
 216 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 217 {
 218     node_t *fence = find_fence(n, dir);
 219
 220     if (fence == NULL)
 221         return;
 222
 223     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 224             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 225         change_split_ratio(fence, CHANGE_INCREASE);
 226     else
 227         change_split_ratio(fence, CHANGE_DECREASE);
 228 }
 229
 230 void rotate_tree(node_t *n, rotate_t rot)
 231 {
 232     if (n == NULL || is_leaf(n) || rot == ROTATE_IDENTITY)
 233         return;
 234
 235     node_t *tmp;
 236
 237     if ((rot == ROTATE_CLOCKWISE && n->split_type == TYPE_HORIZONTAL)
 238             || (rot == ROTATE_COUNTER_CLOCKWISE && n->split_type == TYPE_VERTICAL)
 239             || rot == ROTATE_FULL_CYCLE) {
 240         tmp = n->first_child;
 241         n->first_child = n->second_child;
 242         n->second_child = tmp;
 243         n->split_ratio = 1.0 - n->split_ratio;
 244     }
 245
 246     if (rot != ROTATE_FULL_CYCLE) {
 247         if (n->split_type == TYPE_HORIZONTAL)
 248             n->split_type = TYPE_VERTICAL;
 249         else if (n->split_type == TYPE_VERTICAL)
 250             n->split_type = TYPE_HORIZONTAL;
 251     }
 252
 253     rotate_tree(n->first_child, rot);
 254     rotate_tree(n->second_child, rot);
 255 }
 256
 257 void rotate_brother(node_t *n)
 258 {
 259     if (n == NULL || n->parent == NULL)
 260         return;
 261     if (is_first_child(n))
 262         rotate_tree(n->parent->second_child, n->birth_rotation);
 263     else
 264         rotate_tree(n->parent->first_child, n->birth_rotation);
 265 }
 266
 267 void unrotate_tree(node_t *n, rotate_t rot)
 268 {
 269     switch(rot) {
 270         case ROTATE_CLOCKWISE:
 271             rotate_tree(n, ROTATE_COUNTER_CLOCKWISE);
 272             break;
 273         case ROTATE_COUNTER_CLOCKWISE:
 274             rotate_tree(n, ROTATE_CLOCKWISE);
 275             break;
 276         case ROTATE_IDENTITY:
 277         case ROTATE_FULL_CYCLE:
 278             break;
 279     }
 280 }
 281
 282 void unrotate_brother(node_t *n)
 283 {
 284     if (n == NULL || n->parent == NULL)
 285         return;
 286     if (is_first_child(n))
 287         unrotate_tree(n->parent->second_child, n->birth_rotation);
 288     else
 289         unrotate_tree(n->parent->first_child, n->birth_rotation);
 290 }
 291
 292 void flip_tree(node_t *n, flip_t flp)
 293 {
 294     if (n == NULL || is_leaf(n))
 295         return;
 296
 297     node_t *tmp;
 298
 299     if ((flp == FLIP_HORIZONTAL && n->split_type == TYPE_HORIZONTAL)
 300             || (flp == FLIP_VERTICAL && n->split_type == TYPE_VERTICAL)) {
 301         tmp = n->first_child;
 302         n->first_child = n->second_child;
 303         n->second_child = tmp;
 304         n->split_ratio = 1.0 - n->split_ratio;
 305     }
 306
 307     flip_tree(n->first_child, flp);
 308     flip_tree(n->second_child, flp);
 309 }
 310
 311 void list_history(char *rsp)
 312 {
 313     char line[MAXLEN];
 314     for (monitor_t *m = mon_head; m != NULL; m = m->next)
 315         for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
 316             snprintf(line, sizeof(line), "%s\n", d->name);
 317             strncat(rsp, line, REMLEN(rsp));
 318             for (node_list_t *a = d->history->tail; a != NULL; a = a->prev) {
 319                 snprintf(line, sizeof(line), "  %X\n", a->node->client->window);
 320                 strncat(rsp, line, REMLEN(rsp));
 321             }
 322         }
 323 }
 324
 325 int balance_tree(node_t *n)
 326 {
 327     if (n == NULL || n->vacant) {
 328         return 0;
 329     } else if (is_leaf(n)) {
 330         return 1;
 331     } else {
 332         int b1 = balance_tree(n->first_child);
 333         int b2 = balance_tree(n->second_child);
 334         int b = b1 + b2;
 335         if (b1 > 0 && b2 > 0)
 336             n->split_ratio = (double) b1 / b;
 337         return b;
 338     }
 339 }
 340
 341 void arrange(monitor_t *m, desktop_t *d)
 342 {
 343     if (d->root == NULL)
 344         return;
 345
 346     PRINTF("arrange %s%s%s\n", (num_monitors > 1 ? m->name : ""), (num_monitors > 1 ? " " : ""), d->name);
 347
 348     xcb_rectangle_t rect = m->rectangle;
 349     int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : window_gap);
 350     rect.x += m->left_padding + wg;
 351     rect.y += m->top_padding + wg;
 352     rect.width -= m->left_padding + m->right_padding + wg;
 353     rect.height -= m->top_padding + m->bottom_padding + wg;
 354     apply_layout(m, d, d->root, rect, rect);
 355 }
 356
 357 void apply_layout(monitor_t *m, desktop_t *d, node_t *n, xcb_rectangle_t rect, xcb_rectangle_t root_rect)
 358 {
 359     if (n == NULL)
 360         return;
 361
 362     n->rectangle = rect;
 363
 364     if (is_leaf(n)) {
 365         if (n->client->fullscreen)
 366             return;
 367
 368         if (is_floating(n->client) && n->client->border_width != border_width) {
 369             int ds = 2 * (border_width - n->client->border_width);
 370             n->client->floating_rectangle.width += ds;
 371             n->client->floating_rectangle.height += ds;
 372         }
 373
 374         if (borderless_monocle && is_tiled(n->client) && d->layout == LAYOUT_MONOCLE)
 375             n->client->border_width = 0;
 376         else
 377             n->client->border_width = border_width;
 378
 379         xcb_rectangle_t r;
 380         if (is_tiled(n->client)) {
 381             if (d->layout == LAYOUT_TILED)
 382                 r = rect;
 383             else if (d->layout == LAYOUT_MONOCLE)
 384                 r = root_rect;
 385             int wg = (gapless_monocle && d->layout == LAYOUT_MONOCLE ? 0 : window_gap);
 386             int bleed = wg + 2 * n->client->border_width;
 387             r.width = (bleed < r.width ? r.width - bleed : 1);
 388             r.height = (bleed < r.height ? r.height - bleed : 1);
 389             n->client->tiled_rectangle = r;
 390         } else {
 391             r = n->client->floating_rectangle;
 392         }
 393
 394         window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
 395         window_border_width(n->client->window, n->client->border_width);
 396         window_draw_border(n, n == d->focus, m == mon);
 397
 398     } else {
 399         xcb_rectangle_t first_rect;
 400         xcb_rectangle_t second_rect;
 401
 402         if (n->first_child->vacant || n->second_child->vacant) {
 403             first_rect = second_rect = rect;
 404         } else {
 405             unsigned int fence;
 406             if (n->split_type == TYPE_VERTICAL) {
 407                 fence = rect.width * n->split_ratio;
 408                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 409                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 410
 411             } else if (n->split_type == TYPE_HORIZONTAL) {
 412                 fence = rect.height * n->split_ratio;
 413                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 414                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 415             }
 416         }
 417
 418         apply_layout(m, d, n->first_child, first_rect, root_rect);
 419         apply_layout(m, d, n->second_child, second_rect, root_rect);
 420     }
 421 }
 422
 423 void insert_node(monitor_t *m, desktop_t *d, node_t *n)
 424 {
 425     if (d == NULL || n == NULL)
 426         return;
 427
 428     PRINTF("insert node %X\n", n->client->window);
 429
 430     node_t *focus = d->focus;
 431
 432     if (focus == NULL) {
 433         d->root = n;
 434     } else {
 435         node_t *dad = make_node();
 436         node_t *fopar = focus->parent;
 437         n->parent = dad;
 438         dad->birth_rotation = focus->birth_rotation;
 439         switch (split_mode) {
 440             case MODE_AUTOMATIC:
 441                 if (fopar == NULL) {
 442                     dad->first_child = n;
 443                     dad->second_child = focus;
 444                     if (m->rectangle.width > m->rectangle.height)
 445                         dad->split_type = TYPE_VERTICAL;
 446                     else
 447                         dad->split_type = TYPE_HORIZONTAL;
 448                     focus->parent = dad;
 449                     d->root = dad;
 450                 } else {
 451                     node_t *grandpa = fopar->parent;
 452                     dad->parent = grandpa;
 453                     if (grandpa != NULL) {
 454                         if (is_first_child(fopar))
 455                             grandpa->first_child = dad;
 456                         else
 457                             grandpa->second_child = dad;
 458                     } else {
 459                         d->root = dad;
 460                     }
 461                     dad->split_type = fopar->split_type;
 462                     dad->split_ratio = fopar->split_ratio;
 463                     fopar->parent = dad;
 464                     rotate_t rot;
 465                     if (is_first_child(focus)) {
 466                         dad->first_child = n;
 467                         dad->second_child = fopar;
 468                         rot = ROTATE_CLOCKWISE;
 469                     } else {
 470                         dad->first_child = fopar;
 471                         dad->second_child = n;
 472                         rot = ROTATE_COUNTER_CLOCKWISE;
 473                     }
 474                     rotate_tree(fopar, rot);
 475                     n->birth_rotation = rot;
 476                 }
 477                 break;
 478             case MODE_MANUAL:
 479                 if (fopar != NULL) {
 480                     if (is_first_child(focus))
 481                         fopar->first_child = dad;
 482                     else
 483                         fopar->second_child = dad;
 484                 }
 485                 dad->split_ratio = focus->split_ratio;
 486                 dad->parent = fopar;
 487                 focus->parent = dad;
 488                 focus->birth_rotation = ROTATE_IDENTITY;
 489                 switch (split_dir) {
 490                     case DIR_LEFT:
 491                         dad->split_type = TYPE_VERTICAL;
 492                         dad->first_child = n;
 493                         dad->second_child = focus;
 494                         break;
 495                     case DIR_RIGHT:
 496                         dad->split_type = TYPE_VERTICAL;
 497                         dad->first_child = focus;
 498                         dad->second_child = n;
 499                         break;
 500                     case DIR_UP:
 501                         dad->split_type = TYPE_HORIZONTAL;
 502                         dad->first_child = n;
 503                         dad->second_child = focus;
 504                         break;
 505                     case DIR_DOWN:
 506                         dad->split_type = TYPE_HORIZONTAL;
 507                         dad->first_child = focus;
 508                         dad->second_child = n;
 509                         break;
 510                 }
 511                 if (d->root == focus)
 512                     d->root = dad;
 513                 split_mode = MODE_AUTOMATIC;
 514                 break;
 515         }
 516         if (focus->vacant)
 517             update_vacant_state(fopar);
 518     }
 519     put_status();
 520 }
 521
 522 void pseudo_focus(desktop_t *d, node_t *n)
 523 {
 524     if (d->focus == n)
 525         return;
 526     d->focus = n;
 527     history_add(d->history, n);
 528 }
 529
 530 void focus_node(monitor_t *m, desktop_t *d, node_t *n)
 531 {
 532     if (n == NULL && d->root != NULL)
 533         return;
 534
 535     split_mode = MODE_AUTOMATIC;
 536
 537     if (mon->desk != d)
 538         clear_input_focus();
 539
 540     if (mon != m) {
 541         for (desktop_t *cd = mon->desk_head; cd != NULL; cd = cd->next)
 542             window_draw_border(cd->focus, true, false);
 543         for (desktop_t *cd = m->desk_head; cd != NULL; cd = cd->next)
 544             if (cd != d)
 545                 window_draw_border(cd->focus, true, true);
 546         if (d->focus == n)
 547             window_draw_border(n, true, true);
 548     }
 549
 550     if (d->focus != n) {
 551         window_draw_border(d->focus, false, true);
 552         window_draw_border(n, true, true);
 553     }
 554
 555     select_desktop(m, d);
 556
 557     if (n == NULL) {
 558         ewmh_update_active_window();
 559         return;
 560     }
 561
 562     PRINTF("focus node %X\n", n->client->window);
 563
 564     n->client->urgent = false;
 565
 566     pseudo_focus(d, n);
 567     stack(d, n);
 568
 569     xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 570
 571     if (focus_follows_pointer) {
 572         xcb_window_t win = XCB_NONE;
 573         query_pointer(&win, NULL);
 574         if (win != n->client->window)
 575             enable_motion_recorder();
 576         else
 577             disable_motion_recorder();
 578     }
 579
 580     ewmh_update_active_window();
 581 }
 582
 583 void update_current(void)
 584 {
 585     focus_node(mon, mon->desk, mon->desk->focus);
 586 }
 587
 588 void unlink_node(desktop_t *d, node_t *n)
 589 {
 590     if (d == NULL || n == NULL)
 591         return;
 592
 593     PRINTF("unlink node %X\n", n->client->window);
 594
 595     node_t *p = n->parent;
 596
 597     if (p == NULL) {
 598         d->root = NULL;
 599         d->focus = NULL;
 600     } else {
 601         node_t *b;
 602         node_t *g = p->parent;
 603         if (is_first_child(n)) {
 604             b = p->second_child;
 605             if (!n->vacant)
 606                 unrotate_tree(b, n->birth_rotation);
 607         } else {
 608             b = p->first_child;
 609             if (!n->vacant)
 610                 unrotate_tree(b, n->birth_rotation);
 611         }
 612         b->parent = g;
 613         if (g != NULL) {
 614             if (is_first_child(p))
 615                 g->first_child = b;
 616             else
 617                 g->second_child = b;
 618         } else {
 619             d->root = b;
 620         }
 621
 622         b->birth_rotation = p->birth_rotation;
 623         n->parent = NULL;
 624         free(p);
 625
 626         if (n == d->focus)
 627             d->focus = history_get(d->history, 1);
 628
 629         update_vacant_state(b->parent);
 630     }
 631     history_remove(d->history, n);
 632     put_status();
 633 }
 634
 635 void remove_node(desktop_t *d, node_t *n)
 636 {
 637     if (n == NULL)
 638         return;
 639
 640     PRINTF("remove node %X\n", n->client->window);
 641
 642     unlink_node(d, n);
 643     free(n->client);
 644     free(n);
 645
 646     num_clients--;
 647     ewmh_update_client_list();
 648
 649     if (mon->desk == d)
 650         update_current();
 651 }
 652
 653 void destroy_tree(node_t *n)
 654 {
 655     if (n == NULL)
 656         return;
 657     node_t *first_tree = n->first_child;
 658     node_t *second_tree = n->second_child;
 659     if (n->client != NULL)
 660         free(n->client);
 661     free(n);
 662     destroy_tree(first_tree);
 663     destroy_tree(second_tree);
 664 }
 665
 666 void swap_nodes(node_t *n1, node_t *n2)
 667 {
 668     if (n1 == NULL || n2 == NULL || n1 == n2)
 669         return;
 670
 671     PUTS("swap nodes");
 672
 673     /* (n1 and n2 are leaves) */
 674     node_t *pn1 = n1->parent;
 675     node_t *pn2 = n2->parent;
 676     bool n1_first_child = is_first_child(n1);
 677     bool n2_first_child = is_first_child(n2);
 678     rotate_t br1 = n1->birth_rotation;
 679     rotate_t br2 = n2->birth_rotation;
 680
 681     if (pn1 != NULL) {
 682         if (n1_first_child)
 683             pn1->first_child = n2;
 684         else
 685             pn1->second_child = n2;
 686     }
 687
 688     if (pn2 != NULL) {
 689         if (n2_first_child)
 690             pn2->first_child = n1;
 691         else
 692             pn2->second_child = n1;
 693     }
 694
 695     n1->parent = pn2;
 696     n2->parent = pn1;
 697     n1->birth_rotation = br2;
 698     n2->birth_rotation = br1;
 699
 700     if (n1->vacant != n2->vacant) {
 701         update_vacant_state(n1->parent);
 702         update_vacant_state(n2->parent);
 703     }
 704
 705     /* If we ever need to generalize: */
 706     /* if (d1 != d2) { */
 707     /*     if (d1->root == n1) */
 708     /*         d1->root = n2; */
 709     /*     if (d1->focus == n1) */
 710     /*         d1->focus = n2; */
 711     /*     if (d1->last_focus == n1) */
 712     /*         d1->last_focus = n2; */
 713     /*     if (d2->root == n2) */
 714     /*         d2->root = n1; */
 715     /*     if (d2->focus == n2) */
 716     /*         d2->focus = n1; */
 717     /*     if (d2->last_focus == n2) */
 718     /*         d2->last_focus = n1; */
 719     /* } */
 720 }
 721
 722 void transfer_node(monitor_t *ms, desktop_t *ds, monitor_t *md, desktop_t *dd, node_t *n)
 723 {
 724     if (n == NULL || dd == ds)
 725         return;
 726
 727     PRINTF("transfer node %X\n", n->client->window);
 728
 729     unlink_node(ds, n);
 730     insert_node(md, dd, n);
 731     ewmh_set_wm_desktop(n, dd);
 732
 733     if (ds == ms->desk && dd != md->desk) {
 734         if (n == ds->focus)
 735             clear_input_focus();
 736         window_hide(n->client->window);
 737     }
 738
 739     fit_monitor(md, n->client);
 740
 741     if (n->client->fullscreen)
 742         window_move_resize(n->client->window, md->rectangle.x, md->rectangle.y, md->rectangle.width, md->rectangle.height);
 743
 744     if (ds != ms->desk && dd == md->desk)
 745         window_show(n->client->window);
 746
 747     pseudo_focus(dd, n);
 748
 749     if (md->desk == dd)
 750         stack(dd, n);
 751
 752     arrange(ms, ds);
 753     arrange(md, dd);
 754
 755     if (ds == ms->desk || dd == md->desk)
 756         update_current();
 757 }
 758
 759 void select_monitor(monitor_t *m)
 760 {
 761     if (mon == m)
 762         return;
 763
 764     PRINTF("select monitor %s\n", m->name);
 765
 766     last_mon = mon;
 767     mon = m;
 768
 769     if (pointer_follows_monitor)
 770         center_pointer(m);
 771
 772     ewmh_update_current_desktop();
 773     put_status();
 774 }
 775
 776 void select_desktop(monitor_t *m, desktop_t *d)
 777 {
 778     select_monitor(m);
 779
 780     if (d == mon->desk)
 781         return;
 782
 783     PRINTF("select desktop %s\n", d->name);
 784
 785     if (visible) {
 786         desktop_show(d);
 787         desktop_hide(mon->desk);
 788     }
 789
 790     mon->last_desk = mon->desk;
 791     mon->desk = d;
 792
 793     ewmh_update_current_desktop();
 794     put_status();
 795 }
 796
 797 void cycle_monitor(cycle_dir_t dir)
 798 {
 799     monitor_t *m = NULL;
 800     if (dir == CYCLE_NEXT)
 801         m = (mon->next == NULL ? mon_head : mon->next);
 802     else if (dir == CYCLE_PREV)
 803         m = (mon->prev == NULL ? mon_tail : mon->prev);
 804     focus_node(m, m->desk, m->desk->focus);
 805 }
 806
 807 void cycle_desktop(monitor_t *m, desktop_t *d, cycle_dir_t dir, skip_desktop_t skip)
 808 {
 809     desktop_t *f = (dir == CYCLE_PREV ? d->prev : d->next);
 810     if (f == NULL)
 811         f = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head);
 812
 813     while (f != d) {
 814         if (skip == DESKTOP_SKIP_NONE
 815                 || (skip == DESKTOP_SKIP_FREE && f->root != NULL)
 816                 || (skip == DESKTOP_SKIP_OCCUPIED && f->root == NULL)) {
 817             focus_node(m, f, f->focus);
 818             return;
 819         }
 820         f = (dir == CYCLE_PREV ? f->prev : f->next);
 821         if (f == NULL)
 822             f = (dir == CYCLE_PREV ? m->desk_tail : m->desk_head);
 823     }
 824 }
 825
 826 void cycle_leaf(monitor_t *m, desktop_t *d, node_t *n, cycle_dir_t dir, skip_client_t skip)
 827 {
 828     if (n == NULL)
 829         return;
 830
 831     PUTS("cycle leaf");
 832
 833     node_t *f = (dir == CYCLE_PREV ? prev_leaf(n, d->root) : next_leaf(n, d->root));
 834     if (f == NULL)
 835         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 836
 837     while (f != n) {
 838         bool tiled = is_tiled(f->client);
 839         if (skip == CLIENT_SKIP_NONE || (skip == CLIENT_SKIP_TILED && !tiled) || (skip == CLIENT_SKIP_FLOATING && tiled)
 840                 || (skip == CLIENT_SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 841                 || (skip == CLIENT_SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0)) {
 842             focus_node(m, d, f);
 843             return;
 844         }
 845         f = (dir == CYCLE_PREV ? prev_leaf(f, d->root) : next_leaf(f, d->root));
 846         if (f == NULL)
 847             f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 848     }
 849 }
 850
 851 void nearest_leaf(monitor_t *m, desktop_t *d, node_t *n, nearest_arg_t dir, skip_client_t skip)
 852 {
 853     if (n == NULL)
 854         return;
 855
 856     PUTS("nearest leaf");
 857
 858     node_t *x = NULL;
 859
 860     for (node_t *f = first_extrema(d->root); f != NULL; f = next_leaf(f, d->root))
 861         if (skip == CLIENT_SKIP_NONE || (skip == CLIENT_SKIP_TILED && !is_tiled(f->client)) || (skip == CLIENT_SKIP_FLOATING && is_tiled(f->client))
 862                 || (skip == CLIENT_SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 863                 || (skip == CLIENT_SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0))
 864             if ((dir == NEAREST_OLDER
 865                         && (f->client->uid < n->client->uid)
 866                         && (x == NULL || f->client->uid > x->client->uid))
 867                     || (dir == NEAREST_NEWER
 868                         && (f->client->uid > n->client->uid)
 869                         && (x == NULL || f->client->uid < x->client->uid)))
 870                 x = f;
 871
 872     focus_node(m, d, x);
 873 }
 874
 875 void circulate_leaves(monitor_t *m, desktop_t *d, circulate_dir_t dir)
 876 {
 877     if (d == NULL || d->root == NULL || is_leaf(d->root))
 878         return;
 879     node_t *par = d->focus->parent;
 880     bool focus_first_child = is_first_child(d->focus);
 881     if (dir == CIRCULATE_FORWARD)
 882         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))
 883             swap_nodes(f, s);
 884     else
 885         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))
 886             swap_nodes(f, s);
 887     if (focus_first_child)
 888         focus_node(m, d, par->first_child);
 889     else
 890         focus_node(m, d, par->second_child);
 891 }
 892
 893 void update_vacant_state(node_t *n)
 894 {
 895     if (n == NULL)
 896         return;
 897
 898     PUTS("update vacant state");
 899
 900     /* n is not a leaf */
 901     node_t *p = n;
 902
 903     while (p != NULL) {
 904         p->vacant = (p->first_child->vacant && p->second_child->vacant);
 905         p = p->parent;
 906     }
 907 }
 908
 909 void fit_monitor(monitor_t *m, client_t *c)
 910 {
 911     xcb_rectangle_t crect = c->floating_rectangle;
 912     xcb_rectangle_t mrect = m->rectangle;
 913     while (crect.x < mrect.x)
 914         crect.x += mrect.width;
 915     while (crect.x > (mrect.x + mrect.width - 1))
 916         crect.x -= mrect.width;
 917     while (crect.y < mrect.y)
 918         crect.y += mrect.height;
 919     while (crect.y > (mrect.y + mrect.height - 1))
 920         crect.y -= mrect.height;
 921     c->floating_rectangle = crect;
 922 }
 923
 924 void put_status(void)
 925 {
 926     if (status_fifo == NULL)
 927         return;
 928     if (status_prefix != NULL)
 929         fprintf(status_fifo, "%s", status_prefix);
 930     bool urgent = false;
 931     for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 932         fprintf(status_fifo, "%c%s:", (mon == m ? 'M' : 'm'), m->name);
 933         for (desktop_t *d = m->desk_head; d != NULL; d = d->next, urgent = false) {
 934             for (node_t *n = first_extrema(d->root); n != NULL && !urgent; n = next_leaf(n, d->root))
 935                 urgent |= n->client->urgent;
 936             fprintf(status_fifo, "%c%s:", m->desk == d ? (urgent ? 'U' : 'D') : (d->root == NULL ? 'E' : (urgent ? 'u' : 'd')), d->name);
 937         }
 938     }
 939     if (mon != NULL && mon->desk != NULL)
 940         fprintf(status_fifo, "L%s\n", (mon->desk->layout == LAYOUT_TILED ? "tiled" : "monocle"));
 941     fflush(status_fifo);
 942 }
 943
 944 void list_monitors(list_option_t opt, char *rsp)
 945 {
 946     char line[MAXLEN];
 947     for (monitor_t *m = mon_head; m != NULL; m = m->next) {
 948         snprintf(line, sizeof(line), "%s %ux%u%+i%+i", m->name, m->rectangle.width, m->rectangle.height, m->rectangle.x, m->rectangle.y);
 949         strncat(rsp, line, REMLEN(rsp));
 950         if (m == mon)
 951             strncat(rsp, " #\n", REMLEN(rsp));
 952         else if (m == last_mon)
 953             strncat(rsp, " ~\n", REMLEN(rsp));
 954         else
 955             strncat(rsp, "\n", REMLEN(rsp));
 956         if (opt == LIST_OPTION_VERBOSE)
 957             list_desktops(m, opt, 1, rsp);
 958     }
 959 }
 960
 961 void list_desktops(monitor_t *m, list_option_t opt, unsigned int depth, char *rsp)
 962 {
 963     char line[MAXLEN];
 964     for (desktop_t *d = m->desk_head; d != NULL; d = d->next) {
 965         for (unsigned int i = 0; i < depth; i++)
 966             strncat(rsp, "  ", REMLEN(rsp));
 967         snprintf(line, sizeof(line), "%s %c", d->name, (d->layout == LAYOUT_TILED ? 'T' : 'M'));
 968         strncat(rsp, line, REMLEN(rsp));
 969         if (d == m->desk)
 970             strncat(rsp, " @\n", REMLEN(rsp));
 971         else if (d == m->last_desk)
 972             strncat(rsp, " ~\n", REMLEN(rsp));
 973         else
 974             strncat(rsp, "\n", REMLEN(rsp));
 975         if (opt == LIST_OPTION_VERBOSE)
 976             list(d, d->root, rsp, depth + 1);
 977     }
 978 }
 979
 980 void list(desktop_t *d, node_t *n, char *rsp, unsigned int depth)
 981 {
 982     if (n == NULL)
 983         return;
 984
 985     char line[MAXLEN];
 986
 987     for (unsigned int i = 0; i < depth; i++)
 988         strncat(rsp, "  ", REMLEN(rsp));
 989
 990     if (is_leaf(n)) {
 991         client_t *c = n->client;
 992         snprintf(line, sizeof(line), "%c %s %X %u %u %ux%u%+i%+i %c%c%c%c%c", (n->birth_rotation == ROTATE_CLOCKWISE ? 'a' : (n->birth_rotation == ROTATE_COUNTER_CLOCKWISE ? 'c' : 'm')), c->class_name, c->window, c->uid, c->border_width, c->floating_rectangle.width, c->floating_rectangle.height, c->floating_rectangle.x, c->floating_rectangle.y, (c->floating ? 'f' : '-'), (c->transient ? 't' : '-'), (c->fullscreen ? 'F' : '-'), (c->urgent ? 'u' : '-'), (c->locked ? 'l' : '-'));
 993     } else {
 994         snprintf(line, sizeof(line), "%c %c %.2f", (n->split_type == TYPE_HORIZONTAL ? 'H' : 'V'), (n->birth_rotation == ROTATE_CLOCKWISE ? 'a' : (n->birth_rotation == ROTATE_COUNTER_CLOCKWISE ? 'c' : 'm')), n->split_ratio);
 995     }
 996
 997     strncat(rsp, line, REMLEN(rsp));
 998
 999     if (n == d->focus)
1000         strncat(rsp, " *\n", REMLEN(rsp));
1001     else
1002         strncat(rsp, "\n", REMLEN(rsp));
1003
1004     list(d, n->first_child, rsp, depth + 1);
1005     list(d, n->second_child, rsp, depth + 1);
1006 }
1007
1008 void restore_layout(char *file_path)
1009 {
1010     if (file_path == NULL)
1011         return;
1012
1013     FILE *snapshot = fopen(file_path, "r");
1014     if (snapshot == NULL) {
1015         warn("restore: can't open file\n");
1016         return;
1017     }
1018
1019     PUTS("restore layout");
1020
1021     char line[MAXLEN];
1022     monitor_t *m = NULL;
1023     desktop_t *d = NULL;
1024     node_t *n = NULL;
1025     num_clients = 0;
1026     unsigned int level, last_level = 0, max_uid = 0;
1027     bool aborted = false;
1028
1029     while (!aborted && fgets(line, sizeof(line), snapshot) != NULL) {
1030         unsigned int len = strlen(line);
1031         level = 0;
1032         while (level < strlen(line) && isspace(line[level]))
1033             level++;
1034         if (level == 0) {
1035             if (m == NULL)
1036                 m = mon_head;
1037             else
1038                 m = m->next;
1039             if (len >= 2)
1040                 switch (line[len - 2]) {
1041                     case '#':
1042                         mon = m;
1043                         break;
1044                     case '~':
1045                         last_mon = m;
1046                         break;
1047                 }
1048         } else if (level == 2) {
1049             if (d == NULL)
1050                 d = m->desk_head;
1051             else
1052                 d = d->next;
1053             int i = len - 1;
1054             while (i > 0 && !isupper(line[i]))
1055                 i--;
1056             if (line[i] == 'M')
1057                 d->layout = LAYOUT_MONOCLE;
1058             else if (line[i] == 'T')
1059                 d->layout = LAYOUT_TILED;
1060             if (len >= 2)
1061                 switch (line[len - 2]) {
1062                     case '@':
1063                         m->desk = d;
1064                         break;
1065                     case '~':
1066                         m->last_desk = d;
1067                         break;
1068                 }
1069         } else {
1070             node_t *birth = make_node();
1071             if (level == 4) {
1072                 empty_desktop(d);
1073                 d->root = birth;
1074             } else {
1075                 if (level > last_level) {
1076                     n->first_child = birth;
1077                 } else {
1078                     do {
1079                         n = n->parent;
1080                     } while (n != NULL && n->second_child != NULL);
1081                     if (n == NULL) {
1082                         warn("restore: file is malformed\n");
1083                         aborted = true;
1084                     }
1085                     n->second_child = birth;
1086                 }
1087                 birth->parent = n;
1088             }
1089             n = birth;
1090
1091             char br;
1092             if (isupper(line[level])) {
1093                 char st;
1094                 sscanf(line + level, "%c %c %lf", &st, &br, &n->split_ratio);
1095                 if (st == 'H')
1096                     n->split_type = TYPE_HORIZONTAL;
1097                 else if (st == 'V')
1098                     n->split_type = TYPE_VERTICAL;
1099             } else {
1100                 client_t *c = make_client(XCB_NONE);
1101                 num_clients++;
1102                 char floating, transient, fullscreen, urgent, locked;
1103                 sscanf(line + level, "%c %s %X %u %u %hux%hu%hi%hi %c%c%c%c%c", &br, c->class_name, &c->window, &c->uid, &c->border_width, &c->floating_rectangle.width, &c->floating_rectangle.height, &c->floating_rectangle.x, &c->floating_rectangle.y, &floating, &transient, &fullscreen, &urgent, &locked);
1104                 c->floating = (floating == '-' ? false : true);
1105                 c->transient = (transient == '-' ? false : true);
1106                 c->fullscreen = (fullscreen == '-' ? false : true);
1107                 c->urgent = (urgent == '-' ? false : true);
1108                 c->locked = (locked == '-' ? false : true);
1109                 if (c->uid > max_uid)
1110                     max_uid = c->uid;
1111                 n->client = c;
1112                 if (len >= 2 && line[len - 2] == '*')
1113                     d->focus = n;
1114             }
1115             if (br == 'a')
1116                 n->birth_rotation = ROTATE_CLOCKWISE;
1117             else if (br == 'c')
1118                 n->birth_rotation = ROTATE_COUNTER_CLOCKWISE;
1119             else if (br == 'm')
1120                 n->birth_rotation = ROTATE_IDENTITY;
1121         }
1122         last_level = level;
1123     }
1124
1125     fclose(snapshot);
1126
1127     if (!aborted) {
1128         client_uid = max_uid + 1;
1129         for (monitor_t *m = mon_head; m != NULL; m = m->next)
1130             for (desktop_t *d = m->desk_head; d != NULL; d = d->next)
1131                 for (node_t *n = first_extrema(d->root); n != NULL; n = next_leaf(n, d->root)) {
1132                     uint32_t values[] = {(focus_follows_pointer ? CLIENT_EVENT_MASK_FFP : CLIENT_EVENT_MASK)};
1133                     xcb_change_window_attributes(dpy, n->client->window, XCB_CW_EVENT_MASK, values);
1134                     if (n->client->floating) {
1135                         n->vacant = true;
1136                         update_vacant_state(n->parent);
1137                     }
1138                 }
1139         ewmh_update_current_desktop();
1140     }
1141 }
1142
1143 void restore_history(char *file_path)
1144 {
1145     if (file_path == NULL)
1146         return;
1147
1148     FILE *snapshot = fopen(file_path, "r");
1149     if (snapshot == NULL) {
1150         warn("restore history: can't open file\n");
1151         return;
1152     }
1153
1154     PUTS("restore history");
1155
1156     char line[MAXLEN];
1157     desktop_t *d = NULL;
1158     unsigned int level;
1159
1160     while (fgets(line, sizeof(line), snapshot) != NULL) {
1161         unsigned int i = strlen(line) - 1;
1162         while (i > 0 && isspace(line[i]))
1163             line[i--] = '\0';
1164         level = 0;
1165         while (level < strlen(line) && isspace(line[level]))
1166             level++;
1167         if (level == 0) {
1168             desktop_location_t loc;
1169             if (locate_desktop(line + level, &loc))
1170                 d = loc.desktop;
1171         } else if (d != NULL) {
1172             xcb_window_t win;
1173             if (sscanf(line + level, "%X", &win) == 1) {
1174                 window_location_t loc;
1175                 if (locate_window(win, &loc))
1176                     history_add(d->history, loc.node);
1177             }
1178         }
1179     }
1180
1181     fclose(snapshot);
1182 }