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     desktop_t *d = desk_head;
 175     while (d != NULL) {
 176         d->root->rectangle = (xcb_rectangle_t) {left_padding, top_padding, screen_width - (left_padding + right_padding), screen_height - (top_padding + bottom_padding)};
 177         d = d->next;
 178     }
 179 }
 180
 181 void apply_layout(desktop_t *d, node_t *n)
 182 {
 183     if (n == NULL)
 184         return;
 185     if (is_leaf(n)) {
 186         uint32_t values[4];
 187         xcb_rectangle_t rect;
 188         if (desk->layout == LAYOUT_TILED)
 189             rect = n->rectangle;
 190         else if (desk->layout == LAYOUT_MONOCLE)
 191             rect = d->root->rectangle;
 192         values[0] = rect.x;
 193         values[1] = rect.y;
 194         values[2] = rect.width;
 195         values[3] = rect.height;
 196         xcb_configure_window(dpy, n->client->window, MOVE_RESIZE_MASK, values);
 197     } else {
 198         unsigned int fence;
 199         xcb_rectangle_t rect = n->rectangle;
 200         if (n->split_type == TYPE_VERTICAL) {
 201             fence = rect.width * n->split_ratio;
 202             n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, fence, rect.height};
 203             n->second_child->rectangle = (xcb_rectangle_t) {rect.x + fence, rect.y, rect.width - fence, rect.height};
 204
 205         } else if (n->split_type == TYPE_HORIZONTAL) {
 206             fence = rect.height * n->split_ratio;
 207             n->first_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y, rect.width, fence};
 208             n->second_child->rectangle = (xcb_rectangle_t) {rect.x, rect.y + fence, rect.width, rect.height - fence};
 209         }
 210         apply_layout(d, n->first_child);
 211         apply_layout(d, n->second_child);
 212     }
 213 }
 214
 215 void insert_node(desktop_t *d, node_t *n)
 216 {
 217     if (d == NULL || n == NULL)
 218         return;
 219
 220     node_t *focus = d->focus;
 221
 222     if (focus == NULL) {
 223         d->root = n;
 224     } else {
 225         node_t *dad = make_node();
 226         node_t *fopar = focus->parent;
 227         n->parent = dad;
 228         switch (split_mode) {
 229             case MODE_AUTOMATIC:
 230                 if (fopar == NULL) {
 231                     dad->first_child = n;
 232                     dad->second_child = focus;
 233                     dad->split_type = TYPE_VERTICAL;
 234                     focus->parent = dad;
 235                     d->root = dad;
 236                 } else {
 237                     node_t *grandpa = fopar->parent;
 238                     dad->parent = grandpa;
 239                     if (grandpa != NULL) {
 240                         if (is_first_child(fopar))
 241                             grandpa->first_child = dad;
 242                         else
 243                             grandpa->second_child = dad;
 244                     } else {
 245                         d->root = dad;
 246                     }
 247                     dad->split_type = fopar->split_type;
 248                     dad->split_ratio = fopar->split_ratio;
 249                     fopar->parent = dad;
 250                     if (is_first_child(focus)) {
 251                         dad->first_child = n;
 252                         dad->second_child = fopar;
 253                         rotate_tree(fopar, ROTATE_CLOCK_WISE);
 254                     } else {
 255                         dad->first_child = fopar;
 256                         dad->second_child = n;
 257                         rotate_tree(fopar, ROTATE_COUNTER_CW);
 258                     }
 259                 }
 260                 break;
 261             case MODE_MANUAL:
 262                 focus->parent = dad;
 263                 switch (split_dir) {
 264                     case DIR_LEFT:
 265                         dad->split_type = TYPE_VERTICAL;
 266                         dad->first_child = n;
 267                         dad->second_child = focus;
 268                         break;
 269                     case DIR_RIGHT:
 270                         dad->split_type = TYPE_VERTICAL;
 271                         dad->first_child = focus;
 272                         dad->second_child = n;
 273                         break;
 274                     case DIR_UP:
 275                         dad->split_type = TYPE_HORIZONTAL;
 276                         dad->first_child = n;
 277                         dad->second_child = focus;
 278                         break;
 279                     case DIR_DOWN:
 280                         dad->split_type = TYPE_HORIZONTAL;
 281                         dad->first_child = focus;
 282                         dad->second_child = n;
 283                         break;
 284                 }
 285                 if (d->root == focus)
 286                     d->root = dad;
 287                 split_mode = MODE_AUTOMATIC;
 288                 break;
 289         }
 290     }
 291 }
 292
 293 void focus_node(desktop_t *d, node_t *n)
 294 {
 295     if (d == NULL || n == NULL || d->focus == n)
 296         return;
 297
 298     draw_triple_border(d->focus, normal_border_color_pxl);
 299     draw_triple_border(n, active_border_color_pxl);
 300
 301     xcb_set_input_focus(dpy, XCB_INPUT_FOCUS_POINTER_ROOT, n->client->window, XCB_CURRENT_TIME);
 302 }
 303
 304 void select_desktop(desktop_t *d)
 305 {
 306     if (d == NULL)
 307         return;
 308 }
 309
 310 void remove_node(desktop_t *d, node_t *n)
 311 {
 312     if (d == NULL || n == NULL)
 313         return;
 314
 315     node_t *p = n->parent;
 316
 317     if (p == NULL) {
 318         d->root = NULL;
 319         d->focus = NULL;
 320         d->last_focus = NULL;
 321     } else {
 322         node_t *b;
 323         node_t *g = p->parent;
 324         if (is_first_child(n))
 325             b = p->second_child;
 326         else
 327             b = p->first_child;
 328         b->parent = g;
 329         if (g != NULL) {
 330             if (is_first_child(p))
 331                 g->first_child = b;
 332             else
 333                 g->second_child = b;
 334         } else {
 335             d->root = b;
 336         }
 337         free(p);
 338     }
 339
 340     free(n->client);
 341     free(n);
 342 }
 343
 344