tree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4 #include <xcb/xcb.h>
   5 #include <xcb/xcb_event.h>
   6 #include "settings.h"
   7 #include "helpers.h"
   8 #include "utils.h"
   9 #include "types.h"
  10 #include "bspwm.h"
  11 #include "tree.h"
  12
  13 bool is_leaf(node_t *n)
  14 {
  15     return (n != NULL && n->first_child == NULL && n->second_child == NULL);
  16 }
  17
  18 bool is_first_child(node_t *n)
  19 {
  20     return (n != NULL && n->parent != NULL && n->parent->first_child == n);
  21 }
  22
  23 bool is_second_child(node_t *n)
  24 {
  25     return (n != NULL && n->parent != NULL && n->parent->second_child == n);
  26 }
  27
  28
  29 void change_split_ratio(node_t *n, value_change_t chg) {
  30     n->split_ratio = pow(n->split_ratio, (chg == CHANGE_INCREASE ? INC_EXP : DEC_EXP));
  31 }
  32
  33 node_t *first_extrema(node_t *n)
  34 {
  35     if (n == NULL)
  36         return NULL;
  37     else if (n->first_child == NULL)
  38         return n;
  39     else
  40         return first_extrema(n->first_child);
  41 }
  42
  43 node_t *second_extrema(node_t *n)
  44 {
  45     if (n == NULL)
  46         return NULL;
  47     else if (n->second_child == NULL)
  48         return n;
  49     else
  50         return second_extrema(n->second_child);
  51 }
  52
  53 node_t *next_leaf(node_t *n)
  54 {
  55     if (n == NULL)
  56         return NULL;
  57     node_t *p = n;
  58     while (is_second_child(p))
  59         p = p->parent;
  60     if (p->parent == NULL)
  61         return NULL;
  62     return first_extrema(p->parent->second_child);
  63 }
  64
  65 node_t *prev_leaf(node_t *n)
  66 {
  67     if (n == NULL)
  68         return NULL;
  69     node_t *p = n;
  70     while (is_first_child(p))
  71         p = p->parent;
  72     if (p->parent == NULL)
  73         return NULL;
  74     return second_extrema(p->parent->first_child);
  75 }
  76
  77 node_t *find_fence(node_t *n, direction_t dir)
  78 {
  79     node_t *p;
  80
  81     if (n == NULL)
  82         return NULL;
  83
  84     p = n->parent;
  85
  86     while (p != NULL) {
  87         if ((dir == DIR_UP && p->split_type == TYPE_HORIZONTAL && p->rectangle.y < n->rectangle.y)
  88                 || (dir == DIR_LEFT && p->split_type == TYPE_VERTICAL && p->rectangle.x < n->rectangle.x)
  89                 || (dir == DIR_DOWN && p->split_type == TYPE_HORIZONTAL && (p->rectangle.y + p->rectangle.height) > (n->rectangle.y + n->rectangle.height))
  90                 || (dir == DIR_RIGHT && p->split_type == TYPE_VERTICAL && (p->rectangle.x + p->rectangle.width) > (n->rectangle.x + n->rectangle.width)))
  91             return p;
  92         p = p->parent;
  93     }
  94
  95     return NULL;
  96 }
  97
  98 node_t *find_neighbor(node_t *n, direction_t dir)
  99 {
 100     node_t *fence = find_fence(n, dir);
 101
 102     if (fence == NULL)
 103         return NULL;
 104
 105     if (dir == DIR_UP || dir == DIR_LEFT)
 106         return second_extrema(fence->first_child);
 107     else if (dir == DIR_DOWN || dir == DIR_RIGHT)
 108         return first_extrema(fence->second_child);
 109
 110     return NULL;
 111 }
 112
 113 void move_fence(node_t *n, direction_t dir, fence_move_t mov)
 114 {
 115     node_t *fence = find_fence(n, dir);
 116
 117     if (fence == NULL)
 118         return;
 119
 120     if ((mov == MOVE_PUSH && (dir == DIR_RIGHT || dir == DIR_DOWN))
 121             || (mov == MOVE_PULL && (dir == DIR_LEFT || dir == DIR_UP)))
 122         change_split_ratio(fence, CHANGE_INCREASE);
 123     else
 124         change_split_ratio(fence, CHANGE_DECREASE);
 125 }
 126
 127
 128 void rotate_tree(node_t *n, rotate_t rot)
 129 {
 130     if (n == NULL || is_leaf(n))
 131         return;
 132
 133     node_t *tmp;
 134
 135     if ((rot == ROTATE_CLOCK_WISE && n->split_type == TYPE_HORIZONTAL)
 136             || (rot == ROTATE_COUNTER_CW && n->split_type == TYPE_VERTICAL)
 137             || rot == ROTATE_FULL_CYCLE) {
 138         tmp = n->first_child;
 139         n->first_child = n->second_child;
 140         n->second_child = tmp;
 141         n->split_ratio = 1.0 - n->split_ratio;
 142     }
 143
 144     if (rot != ROTATE_FULL_CYCLE) {
 145         if (n->split_type == TYPE_HORIZONTAL)
 146             n->split_type = TYPE_VERTICAL;
 147         else if (n->split_type == TYPE_VERTICAL)
 148             n->split_type = TYPE_HORIZONTAL;
 149     }
 150
 151     rotate_tree(n->first_child, rot);
 152     rotate_tree(n->second_child, rot);
 153 }
 154
 155 void dump_tree(node_t *n, char *rsp, int depth)
 156 {
 157     if (n == NULL)
 158         return;
 159
 160     for (int i = 0; i < depth; i++)
 161         sprintf(rsp, "%s", "  ");
 162
 163     if (n->client == NULL)
 164         sprintf(rsp, "%s %.2f\n", (n->split_type == TYPE_HORIZONTAL ? "H" : "V"), n->split_ratio);
 165     else
 166         sprintf(rsp, "%X\n", n->client->window);
 167
 168     dump_tree(n->first_child, rsp, depth + 1);
 169     dump_tree(n->second_child, rsp, depth + 1);
 170 }
 171
 172 void update_root_dimensions(void)
 173 {
 174     xcb_rectangle_t root_rect = {
 175         left_padding + window_gap,
 176         top_padding + window_gap,
 177         screen_width - (left_padding + right_padding + window_gap),
 178         screen_height - (top_padding + bottom_padding + window_gap)
 179     };
 180     desktop_t *d = desk_head;
 181     while (d != NULL) {
 182         d->root->rectangle = root_rect;
 183         d = d->next;
 184     }
 185 }
 186
 187 void apply_layout(desktop_t *d, node_t *n)
 188 {
 189     if (n == NULL)
 190         return;
 191     if (is_leaf(n) && !n->client->floating && !n->client->fullscreen) {
 192         uint32_t values[4];
 193         xcb_rectangle_t rect;
 194         if (d->layout == LAYOUT_TILED)
 195             rect = n->rectangle;
 196         else if (d->layout == LAYOUT_MONOCLE)
 197             rect = d->root->rectangle;
 198         values[0] = rect.x;
 199         values[1] = rect.y;
 200         values[2] = rect.width - window_gap;
 201         values[3] = rect.height - window_gap;
 202         xcb_configure_window(dpy, n->client->window, MOVE_RESIZE_MASK, values);
 203     } else {
 204         xcb_rectangle_t rect = n->rectangle;
 205         if (n->first_child->vacant || n->second_child->vacant) {
 206             n->first_child->rectangle = n->second_child->rectangle = rect;
 207         } else {
 208             unsigned int fence;
 209             if (n->split_type == TYPE_VERTICAL) {
 210                 fence = rect.width * n->split_ratio;
 211                 n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 212                 n->second_child->rectangle = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 213
 214             } else if (n->split_type == TYPE_HORIZONTAL) {
 215                 fence = rect.height * n->split_ratio;
 216                 n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 217                 n->second_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 218             }
 219         }
 220         apply_layout(d, n->first_child);
 221         apply_layout(d, n->second_child);
 222     }
 223 }
 224
 225 void insert_node(desktop_t *d, node_t *n)
 226 {
 227     if (d == NULL || n == NULL)
 228         return;
 229
 230     node_t *focus = d->focus;
 231
 232     if (focus == NULL) {
 233         d->root = n;
 234     } else {
 235         node_t *dad = make_node();
 236         node_t *fopar = focus->parent;
 237         n->parent = dad;
 238         switch (split_mode) {
 239             case MODE_AUTOMATIC:
 240                 if (fopar == NULL) {
 241                     dad->first_child = n;
 242                     dad->second_child = focus;
 243                     dad->split_type = TYPE_VERTICAL;
 244                     focus->parent = dad;
 245                     d->root = dad;
 246                 } else {
 247                     node_t *grandpa = fopar->parent;
 248                     dad->parent = grandpa;
 249                     if (grandpa != NULL) {
 250                         if (is_first_child(fopar))
 251                             grandpa->first_child = dad;
 252                         else
 253                             grandpa->second_child = dad;
 254                     } else {
 255                         d->root = dad;
 256                     }
 257                     dad->split_type = fopar->split_type;
 258                     dad->split_ratio = fopar->split_ratio;
 259                     fopar->parent = dad;
 260                     if (is_first_child(focus)) {
 261                         dad->first_child = n;
 262                         dad->second_child = fopar;
 263                         rotate_tree(fopar, ROTATE_CLOCK_WISE);
 264                     } else {
 265                         dad->first_child = fopar;
 266                         dad->second_child = n;
 267                         rotate_tree(fopar, ROTATE_COUNTER_CW);
 268                     }
 269                 }
 270                 break;
 271             case MODE_MANUAL:
 272                 focus->parent = dad;
 273                 switch (split_dir) {
 274                     case DIR_LEFT:
 275                         dad->split_type = TYPE_VERTICAL;
 276                         dad->first_child = n;
 277                         dad->second_child = focus;
 278                         break;
 279                     case DIR_RIGHT:
 280                         dad->split_type = TYPE_VERTICAL;
 281                         dad->first_child = focus;
 282                         dad->second_child = n;
 283                         break;
 284                     case DIR_UP:
 285                         dad->split_type = TYPE_HORIZONTAL;
 286                         dad->first_child = n;
 287                         dad->second_child = focus;
 288                         break;
 289                     case DIR_DOWN:
 290                         dad->split_type = TYPE_HORIZONTAL;
 291                         dad->first_child = focus;
 292                         dad->second_child = n;
 293                         break;
 294                 }
 295                 if (d->root == focus)
 296                     d->root = dad;
 297                 split_mode = MODE_AUTOMATIC;
 298                 break;
 299         }
 300     }
 301 }
 302
 303 void focus_node(desktop_t *d, node_t *n)
 304 {
 305     if (d == NULL || n == NULL || d->focus == n)
 306         return;
 307
 308     draw_triple_border(d->focus, normal_border_color_pxl);
 309     draw_triple_border(n, active_border_color_pxl);
 310
 311     xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 312 }
 313
 314 void remove_node(desktop_t *d, node_t *n)
 315 {
 316     if (d == NULL || n == NULL)
 317         return;
 318
 319     node_t *p = n->parent;
 320
 321     if (p == NULL) {
 322         d->root = NULL;
 323         d->focus = NULL;
 324         d->last_focus = NULL;
 325     } else {
 326         node_t *b;
 327         node_t *g = p->parent;
 328         if (is_first_child(n))
 329             b = p->second_child;
 330         else
 331             b = p->first_child;
 332         b->parent = g;
 333         if (g != NULL) {
 334             if (is_first_child(p))
 335                 g->first_child = b;
 336             else
 337                 g->second_child = b;
 338         } else {
 339             d->root = b;
 340         }
 341         free(p);
 342     }
 343
 344     /* free(n->client); */
 345     /* free(n); */
 346 }
 347
 348 void transfer_node(desktop_t *ds, desktop_t *dd, node_t *n)
 349 {
 350     if (ds == NULL || dd == NULL || n == NULL)
 351         return;
 352     remove_node(ds, n);
 353     insert_node(dd, n);
 354 }
 355
 356 void update_vacant_state(node_t *n)
 357 {
 358     if (n == NULL)
 359         return;
 360     if (!is_leaf(n))
 361         n->vacant = (n->first_child->vacant && n->second_child->vacant);
 362     update_vacant_state(n->parent);
 363 }
 364
 365 void select_desktop(desktop_t *d)
 366 {
 367     if (d == NULL)
 368         return;
 369 }