tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <math.h>
   5 #include <xcb/xcb.h>
   6 #include <xcb/xcb_event.h>
   7 #include "settings.h"
   8 #include "helpers.h"
   9 #include "window.h"
  10 #include "types.h"
  11 #include "bspwm.h"
  12 #include "ewmh.h"
  13 #include "tree.h"
  14
  15 bool is_leaf(node_t *n)
  16 {
  17     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  18 }
  19
  20 bool is_tiled(client_t *c)
  21 {
  22     if (c == NULL)
  23         return false;
  24     return (!c->floating && !c->transient && !c->fullscreen);
  25 }
  26
  27 bool is_floating(client_t *c)
  28 {
  29     if (c == NULL)
  30         return false;
  31     return (c->floating && !c->fullscreen);
  32 }
  33
  34 bool is_first_child(node_t *n)
  35 {
  36     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  37 }
  38
  39 bool is_second_child(node_t *n)
  40 {
  41     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  42 }
  43
  44 void change_split_ratio(node_t *n, value_change_t chg) {
  45     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  46 }
  47
  48 node_t *first_extrema(node_t *n)
  49 {
  50     if (n == NULL)
  51         return NULL;
  52     else if (n->first_child == NULL)
  53         return n;
  54     else
  55         return first_extrema(n->first_child);
  56 }
  57
  58 node_t *second_extrema(node_t *n)
  59 {
  60     if (n == NULL)
  61         return NULL;
  62     else if (n->second_child == NULL)
  63         return n;
  64     else
  65         return second_extrema(n->second_child);
  66 }
  67
  68 node_t *next_leaf(node_t *n)
  69 {
  70     if (n == NULL)
  71         return NULL;
  72     node_t *p = n;
  73     while (is_second_child(p))
  74         p = p->parent;
  75     if (p->parent == NULL)
  76         return NULL;
  77     return first_extrema(p->parent->second_child);
  78 }
  79
  80 node_t *prev_leaf(node_t *n)
  81 {
  82     if (n == NULL)
  83         return NULL;
  84     node_t *p = n;
  85     while (is_first_child(p))
  86         p = p->parent;
  87     if (p->parent == NULL)
  88         return NULL;
  89     return second_extrema(p->parent->first_child);
  90 }
  91
  92 node_t *find_fence(node_t *n, direction_t dir)
  93 {
  94     node_t *p;
  95
  96     if (n == NULL)
  97         return NULL;
  98
  99     p = n->parent;
 100
 101     while (p != NULL) {
 102         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
 103                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
 104                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
 105                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
 106             return p;
 107         p = p->parent;
 108     }
 109
 110     return NULL;
 111 }
 112
 113 node_t *find_neighbor(node_t *n, direction_t dir)
 114 {
 115     node_t *fence = find_fence(n, dir);
 116
 117     if (fence == NULL)
 118         return NULL;
 119
 120     if (dir == DIR_UP || dir == DIR_LEFT)
 121         return second_extrema(fence->first_child);
 122     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 123         return first_extrema(fence->second_child);
 124
 125     return NULL;
 126 }
 127
 128 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 129 {
 130     node_t *fence = find_fence(n, dir);
 131
 132     if (fence == NULL)
 133         return;
 134
 135     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 136             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 137         change_split_ratio(fence, CHANGE_INCREASE);
 138     else
 139         change_split_ratio(fence, CHANGE_DECREASE);
 140 }
 141
 142 void rotate_tree(node_t *n, rotate_t rot)
 143 {
 144     if (n == NULL || is_leaf(n))
 145         return;
 146
 147     node_t *tmp;
 148
 149     if ((rot == ROTATE_CLOCKWISE && n->split_type == TYPE_HORIZONTAL)
 150             || (rot == ROTATE_COUNTER_CLOCKWISE && n->split_type == TYPE_VERTICAL)
 151             || rot == ROTATE_FULL_CYCLE) {
 152         tmp = n->first_child;
 153         n->first_child = n->second_child;
 154         n->second_child = tmp;
 155         n->split_ratio = 1.0 - n->split_ratio;
 156     }
 157
 158     if (rot != ROTATE_FULL_CYCLE) {
 159         if (n->split_type == TYPE_HORIZONTAL)
 160             n->split_type = TYPE_VERTICAL;
 161         else if (n->split_type == TYPE_VERTICAL)
 162             n->split_type = TYPE_HORIZONTAL;
 163     }
 164
 165     rotate_tree(n->first_child, rot);
 166     rotate_tree(n->second_child, rot);
 167 }
 168
 169 void magnetise_tree(node_t *n, corner_t corner)
 170 {
 171     if (n == NULL || is_leaf(n))
 172         return;
 173
 174     PUTS("magnetise tree");
 175
 176     switch (n->split_type) {
 177         case TYPE_HORIZONTAL:
 178             if (corner == TOP_LEFT || corner == TOP_RIGHT)
 179                 change_split_ratio(n, CHANGE_DECREASE);
 180             else
 181                 change_split_ratio(n, CHANGE_INCREASE);
 182             break;
 183         case TYPE_VERTICAL:
 184             if (corner == TOP_LEFT || corner == BOTTOM_LEFT)
 185                 change_split_ratio(n, CHANGE_DECREASE);
 186             else
 187                 change_split_ratio(n, CHANGE_INCREASE);
 188             break;
 189         default:
 190             break;
 191     }
 192
 193     magnetise_tree(n->first_child, corner);
 194     magnetise_tree(n->second_child, corner);
 195 }
 196
 197 void dump_tree(desktop_t *d, node_t *n, char *rsp, int depth)
 198 {
 199     if (n == NULL)
 200         return;
 201
 202     char line[MAXLEN];
 203
 204     for (int i = 0; i < depth; i++)
 205         strncat(rsp, "  ", REMLEN(rsp));
 206
 207     if (is_leaf(n))
 208         snprintf(line, sizeof(line), "%s %X %s%s%s%s%s", n->client->class_name, n->client->window, (n->client->floating ? "f" : "-"), (n->client->transient ? "t" : "-"), (n->client->fullscreen ? "F" : "-"), (n->client->urgent ? "u" : "-"), (n->client->locked ? "l" : "-"));
 209     else
 210         snprintf(line, sizeof(line), "%s %.2f", (n->split_type == TYPE_HORIZONTAL ? "H" : "V"), n->split_ratio);
 211
 212     strncat(rsp, line, REMLEN(rsp));
 213
 214     if (n == d->focus)
 215         strncat(rsp, " *\n", REMLEN(rsp));
 216     else
 217         strncat(rsp, "\n", REMLEN(rsp));
 218
 219     dump_tree(d, n->first_child, rsp, depth + 1);
 220     dump_tree(d, n->second_child, rsp, depth + 1);
 221 }
 222
 223 void refresh_current(void) {
 224     if (desk->focus == NULL)
 225         ewmh_update_active_window();
 226     else
 227         focus_node(desk, desk->focus, true);
 228 }
 229
 230 void list_desktops(char *rsp)
 231 {
 232     desktop_t *d = desk_head;
 233
 234     while (d != NULL) {
 235         strncat(rsp, d->name, REMLEN(rsp));
 236         if (desk == d)
 237             strncat(rsp, " @\n", REMLEN(rsp));
 238         else
 239             strncat(rsp, "\n", REMLEN(rsp));
 240         dump_tree(d, d->root, rsp, 1);
 241         d = d->next;
 242     }
 243 }
 244
 245 void update_root_dimensions(void)
 246 {
 247     root_rect.x = left_padding + window_gap;
 248     root_rect.y = top_padding + window_gap;
 249     root_rect.width = screen_width - (left_padding + right_padding + window_gap);
 250     root_rect.height = screen_height - (top_padding + bottom_padding + window_gap);
 251 }
 252
 253 void apply_layout(desktop_t *d, node_t *n, xcb_rectangle_t rect)
 254 {
 255     if (d == NULL || n == NULL)
 256         return;
 257
 258     n->rectangle = rect;
 259
 260     if (is_leaf(n)) {
 261         if (n->client->fullscreen)
 262             return;
 263
 264         if (is_floating(n->client) && n->client->border_width != border_width) {
 265             int ds = 2 * (border_width - n->client->border_width);
 266             n->client->floating_rectangle.width += ds;
 267             n->client->floating_rectangle.height += ds;
 268         }
 269
 270         if (borderless_monocle && is_tiled(n->client) && d->layout == LAYOUT_MONOCLE)
 271             n->client->border_width = 0;
 272         else
 273             n->client->border_width = border_width;
 274
 275         xcb_rectangle_t r;
 276         if (is_tiled(n->client)) {
 277             if (d->layout == LAYOUT_TILED)
 278                 r = rect;
 279             else if (d->layout == LAYOUT_MONOCLE)
 280                 r = root_rect;
 281             int bleed = window_gap + 2 * n->client->border_width;
 282             r.width = (bleed < r.width ? r.width - bleed : 1);
 283             r.height = (bleed < r.height ? r.height - bleed : 1);
 284             n->client->tiled_rectangle = r;
 285         } else {
 286             r = n->client->floating_rectangle;
 287         }
 288
 289         window_move_resize(n->client->window, r.x, r.y, r.width, r.height);
 290         window_border_width(n->client->window, n->client->border_width);
 291         window_draw_border(n, n == d->focus);
 292
 293         if (d->layout == LAYOUT_MONOCLE && n == d->focus)
 294             window_raise(n->client->window);
 295
 296     } else {
 297         xcb_rectangle_t first_rect;
 298         xcb_rectangle_t second_rect;
 299
 300         if (n->first_child->vacant || n->second_child->vacant) {
 301             first_rect = second_rect = rect;
 302         } else {
 303             unsigned int fence;
 304             if (n->split_type == TYPE_VERTICAL) {
 305                 fence = rect.width * n->split_ratio;
 306                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 307                 second_rect = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 308
 309             } else if (n->split_type == TYPE_HORIZONTAL) {
 310                 fence = rect.height * n->split_ratio;
 311                 first_rect = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 312                 second_rect = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 313             }
 314         }
 315
 316         apply_layout(d, n->first_child, first_rect);
 317         apply_layout(d, n->second_child, second_rect);
 318     }
 319 }
 320
 321 void insert_node(desktop_t *d, node_t *n)
 322 {
 323     if (d == NULL || n == NULL)
 324         return;
 325
 326     PRINTF("insert node %X\n", n->client->window);
 327
 328     node_t *focus = d->focus;
 329
 330     if (focus == NULL) {
 331         d->root = n;
 332     } else {
 333         node_t *dad = make_node();
 334         node_t *fopar = focus->parent;
 335         n->parent = dad;
 336         n->born_as = split_mode;
 337         switch (split_mode) {
 338             case MODE_AUTOMATIC:
 339                 if (fopar == NULL) {
 340                     dad->first_child = n;
 341                     dad->second_child = focus;
 342                     if (focus->rectangle.width > focus->rectangle.height)
 343                         dad->split_type = TYPE_VERTICAL;
 344                     else
 345                         dad->split_type = TYPE_HORIZONTAL;
 346                     focus->parent = dad;
 347                     d->root = dad;
 348                 } else {
 349                     node_t *grandpa = fopar->parent;
 350                     dad->parent = grandpa;
 351                     if (grandpa != NULL) {
 352                         if (is_first_child(fopar))
 353                             grandpa->first_child = dad;
 354                         else
 355                             grandpa->second_child = dad;
 356                     } else {
 357                         d->root = dad;
 358                     }
 359                     dad->split_type = fopar->split_type;
 360                     dad->split_ratio = fopar->split_ratio;
 361                     fopar->parent = dad;
 362                     if (is_first_child(focus)) {
 363                         dad->first_child = n;
 364                         dad->second_child = fopar;
 365                         rotate_tree(fopar, ROTATE_CLOCKWISE);
 366                     } else {
 367                         dad->first_child = fopar;
 368                         dad->second_child = n;
 369                         rotate_tree(fopar, ROTATE_COUNTER_CLOCKWISE);
 370                     }
 371                 }
 372                 break;
 373             case MODE_MANUAL:
 374                 if (fopar != NULL) {
 375                     if (is_first_child(focus))
 376                         fopar->first_child = dad;
 377                     else
 378                         fopar->second_child = dad;
 379                 }
 380                 dad->split_ratio = focus->split_ratio;
 381                 dad->parent = fopar;
 382                 focus->parent = dad;
 383                 switch (split_dir) {
 384                     case DIR_LEFT:
 385                         dad->split_type = TYPE_VERTICAL;
 386                         dad->first_child = n;
 387                         dad->second_child = focus;
 388                         break;
 389                     case DIR_RIGHT:
 390                         dad->split_type = TYPE_VERTICAL;
 391                         dad->first_child = focus;
 392                         dad->second_child = n;
 393                         break;
 394                     case DIR_UP:
 395                         dad->split_type = TYPE_HORIZONTAL;
 396                         dad->first_child = n;
 397                         dad->second_child = focus;
 398                         break;
 399                     case DIR_DOWN:
 400                         dad->split_type = TYPE_HORIZONTAL;
 401                         dad->first_child = focus;
 402                         dad->second_child = n;
 403                         break;
 404                 }
 405                 if (d->root == focus)
 406                     d->root = dad;
 407                 split_mode = MODE_AUTOMATIC;
 408                 break;
 409         }
 410         if (focus->vacant)
 411             update_vacant_state(fopar);
 412     }
 413 }
 414
 415 void focus_node(desktop_t *d, node_t *n, bool is_mapped)
 416 {
 417     if (n == NULL)
 418         return;
 419
 420     PRINTF("focus node %X\n", n->client->window);
 421
 422     split_mode = MODE_AUTOMATIC;
 423     n->client->urgent = false;
 424
 425     if (is_mapped) {
 426         if (d->focus != n) {
 427             window_draw_border(d->focus, false);
 428             window_draw_border(n, true);
 429         }
 430         xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 431     }
 432
 433     if (!is_tiled(n->client) || d->layout == LAYOUT_MONOCLE)
 434         window_raise(n->client->window);
 435     else if (is_tiled(n->client))
 436         window_lower(n->client->window);
 437
 438     if (d->focus != n) {
 439         d->last_focus = d->focus;
 440         d->focus = n;
 441     }
 442
 443     if (d == desk)
 444         ewmh_update_active_window();
 445 }
 446
 447 void update_current(void)
 448 {
 449     if (desk->focus == NULL)
 450         ewmh_update_active_window();
 451     else
 452         focus_node(desk, desk->focus, true);
 453 }
 454
 455 void unlink_node(desktop_t *d, node_t *n)
 456 {
 457     if (d == NULL || n == NULL)
 458         return;
 459
 460     PRINTF("unlink node %X\n", n->client->window);
 461
 462     node_t *p = n->parent;
 463
 464     if (p == NULL) {
 465         d->root = NULL;
 466         d->focus = NULL;
 467         d->last_focus = NULL;
 468     } else {
 469         node_t *b;
 470         node_t *g = p->parent;
 471         bool n_first_child = is_first_child(n);
 472         if (n_first_child) {
 473             b = p->second_child;
 474             if (n->born_as == MODE_AUTOMATIC)
 475                 rotate_tree(b, ROTATE_COUNTER_CLOCKWISE);
 476         } else {
 477             b = p->first_child;
 478             if (n->born_as == MODE_AUTOMATIC)
 479                 rotate_tree(b, ROTATE_CLOCKWISE);
 480         }
 481         b->parent = g;
 482         if (g != NULL) {
 483             if (is_first_child(p))
 484                 g->first_child = b;
 485             else
 486                 g->second_child = b;
 487         } else {
 488             d->root = b;
 489         }
 490
 491         n->parent = NULL;
 492         free(p);
 493
 494         if (n == d->last_focus) {
 495             d->last_focus = NULL;
 496         } else if (n == d->focus) {
 497             if (d->last_focus != NULL)
 498                 d->focus = d->last_focus;
 499             else
 500                 d->focus = (n_first_child ? first_extrema(b) : second_extrema(b));
 501             d->last_focus = NULL;
 502         }
 503
 504         update_vacant_state(b->parent);
 505     }
 506 }
 507
 508 void remove_node(desktop_t *d, node_t *n)
 509 {
 510     if (d == NULL || n == NULL)
 511         return;
 512
 513     PRINTF("remove node %X\n", n->client->window);
 514
 515     unlink_node(d, n);
 516     free(n->client);
 517     free(n);
 518
 519     num_clients--;
 520     ewmh_update_client_list();
 521
 522     if (desk == d)
 523         update_current();
 524 }
 525
 526 void swap_nodes(node_t *n1, node_t *n2)
 527 {
 528     if (n1 == NULL || n2 == NULL || n1 == n2)
 529         return;
 530
 531     PUTS("swap nodes");
 532
 533     /* (n1 and n2 are leaves) */
 534     node_t *pn1 = n1->parent;
 535     node_t *pn2 = n2->parent;
 536     bool n1_first_child = is_first_child(n1);
 537     bool n2_first_child = is_first_child(n2);
 538
 539     if (pn1 != NULL) {
 540         if (n1_first_child)
 541             pn1->first_child = n2;
 542         else
 543             pn1->second_child = n2;
 544     }
 545
 546     if (pn2 != NULL) {
 547         if (n2_first_child)
 548             pn2->first_child = n1;
 549         else
 550             pn2->second_child = n1;
 551     }
 552
 553     n1->parent = pn2;
 554     n2->parent = pn1;
 555
 556     if (n1->vacant != n2->vacant) {
 557         update_vacant_state(n1->parent);
 558         update_vacant_state(n2->parent);
 559     }
 560 }
 561
 562 void transfer_node(desktop_t *ds, desktop_t *dd, node_t *n)
 563 {
 564     if (n == NULL || ds == NULL || dd == NULL || dd == ds)
 565         return;
 566
 567     PRINTF("transfer node %X\n", n->client->window);
 568
 569     unlink_node(ds, n);
 570     insert_node(dd, n);
 571     ewmh_set_wm_desktop(n, dd);
 572
 573     if (ds == desk) {
 574         window_hide(n->client->window);
 575     }
 576
 577     if (dd == desk) {
 578         window_show(n->client->window);
 579         focus_node(dd, n, true);
 580     } else {
 581         focus_node(dd, n, false);
 582     }
 583
 584     if (ds == desk || dd == desk)
 585         update_current();
 586 }
 587
 588 void select_desktop(desktop_t *d)
 589 {
 590     if (d == NULL || d == desk)
 591         return;
 592
 593     PRINTF("select desktop %s\n", d->name);
 594
 595     node_t *n = first_extrema(d->root);
 596
 597     while (n != NULL) {
 598         window_show(n->client->window);
 599         n = next_leaf(n);
 600     }
 601
 602     n = first_extrema(desk->root);
 603
 604     while (n != NULL) {
 605         window_hide(n->client->window);
 606         n = next_leaf(n);
 607     }
 608
 609     last_desk = desk;
 610     desk = d;
 611
 612     update_current();
 613     ewmh_update_current_desktop();
 614 }
 615
 616 void cycle_desktop(cycle_dir_t dir)
 617 {
 618     if (dir == CYCLE_NEXT)
 619         select_desktop((desk->next == NULL ? desk_head : desk->next));
 620     else if (dir == CYCLE_PREV)
 621         select_desktop((desk->prev == NULL ? desk_tail : desk->prev));
 622 }
 623
 624 void cycle_leaf(desktop_t *d, node_t *n, cycle_dir_t dir, skip_client_t skip)
 625 {
 626     if (n == NULL)
 627         return;
 628
 629     PUTS("cycle leaf");
 630
 631     node_t *f = (dir == CYCLE_PREV ? prev_leaf(n) : next_leaf(n));
 632     if (f == NULL)
 633         f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 634
 635     while (f != n) {
 636         bool tiled = is_tiled(f->client);
 637         if (skip == SKIP_NONE || (skip == SKIP_TILED && !tiled) || (skip == SKIP_FLOATING && tiled)
 638                 || (skip == SKIP_CLASS_DIFFER && strcmp(f->client->class_name, n->client->class_name) == 0)
 639                 || (skip == SKIP_CLASS_EQUAL && strcmp(f->client->class_name, n->client->class_name) != 0)) {
 640             focus_node(d, f, true);
 641             return;
 642         }
 643         f = (dir == CYCLE_PREV ? prev_leaf(f) : next_leaf(f));
 644         if (f == NULL)
 645             f = (dir == CYCLE_PREV ? second_extrema(d->root) : first_extrema(d->root));
 646     }
 647 }
 648
 649 void update_vacant_state(node_t *n)
 650 {
 651     if (n == NULL)
 652         return;
 653
 654     PUTS("update vacant state");
 655
 656     /* n is not a leaf */
 657     node_t *p = n;
 658
 659     while (p != NULL) {
 660         p->vacant = (p->first_child->vacant && p->second_child->vacant);
 661         p = p->parent;
 662     }
 663 }
 664
 665 desktop_t *find_desktop(char *name)
 666 {
 667     desktop_t *d = desk_head;
 668     while (d != NULL) {
 669         if (strcmp(d->name, name) == 0)
 670             return d;
 671         d = d->next;
 672     }
 673     return NULL;
 674 }
 675
 676 void add_desktop(char *name)
 677 {
 678     desktop_t *d = make_desktop(name);
 679     desk_tail->next = d;
 680     d->prev = desk_tail;
 681     desk_tail = d;
 682     num_desktops++;
 683     ewmh_update_number_of_desktops();
 684     ewmh_update_desktop_names();
 685 }