1 /* $OpenBSD: grid.c,v 1.20 2012/07/10 11:53:01 nicm Exp $ */ 2 3 /* 4 * Copyright (c) 2008 Nicholas Marriott <nicm@users.sourceforge.net> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER 15 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING 16 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <sys/types.h> 20 21 #include <stdlib.h> 22 #include <string.h> 23 24 #include "tmux.h" 25 26 /* 27 * Grid data. This is the basic data structure that represents what is shown on 28 * screen. 29 * 30 * A grid is a grid of cells (struct grid_cell). Lines are not allocated until 31 * cells in that line are written to. The grid is split into history and 32 * viewable data with the history starting at row (line) 0 and extending to 33 * (hsize - 1); from hsize to hsize + (sy - 1) is the viewable data. All 34 * functions in this file work on absolute coordinates, grid-view.c has 35 * functions which work on the screen data. 36 */ 37 38 /* Default grid cell data. */ 39 const struct grid_cell grid_default_cell = { 0, 0, 8, 8, ' ' }; 40 const struct grid_cell grid_marker_cell = { 0, 0, 8, 8, '_' }; 41 42 #define grid_put_cell(gd, px, py, gc) do { \ 43 memcpy(&gd->linedata[py].celldata[px], \ 44 gc, sizeof gd->linedata[py].celldata[px]); \ 45 } while (0) 46 #define grid_put_utf8(gd, px, py, gc) do { \ 47 memcpy(&gd->linedata[py].utf8data[px], \ 48 gc, sizeof gd->linedata[py].utf8data[px]); \ 49 } while (0) 50 51 int grid_check_y(struct grid *, u_int); 52 53 #ifdef DEBUG 54 int 55 grid_check_y(struct grid *gd, u_int py) 56 { 57 if ((py) >= (gd)->hsize + (gd)->sy) 58 log_fatalx("y out of range: %u", py); 59 return (0); 60 } 61 #else 62 int 63 grid_check_y(struct grid *gd, u_int py) 64 { 65 if ((py) >= (gd)->hsize + (gd)->sy) { 66 log_debug("y out of range: %u", py); 67 return (-1); 68 } 69 return (0); 70 } 71 #endif 72 73 /* Create a new grid. */ 74 struct grid * 75 grid_create(u_int sx, u_int sy, u_int hlimit) 76 { 77 struct grid *gd; 78 79 gd = xmalloc(sizeof *gd); 80 gd->sx = sx; 81 gd->sy = sy; 82 83 gd->flags = GRID_HISTORY; 84 85 gd->hsize = 0; 86 gd->hlimit = hlimit; 87 88 gd->linedata = xcalloc(gd->sy, sizeof *gd->linedata); 89 90 return (gd); 91 } 92 93 /* Destroy grid. */ 94 void 95 grid_destroy(struct grid *gd) 96 { 97 struct grid_line *gl; 98 u_int yy; 99 100 for (yy = 0; yy < gd->hsize + gd->sy; yy++) { 101 gl = &gd->linedata[yy]; 102 free(gl->celldata); 103 free(gl->utf8data); 104 } 105 106 free(gd->linedata); 107 108 free(gd); 109 } 110 111 /* Compare grids. */ 112 int 113 grid_compare(struct grid *ga, struct grid *gb) 114 { 115 struct grid_line *gla, *glb; 116 struct grid_cell *gca, *gcb; 117 struct grid_utf8 *gua, *gub; 118 u_int xx, yy; 119 120 if (ga->sx != gb->sx || ga->sy != ga->sy) 121 return (1); 122 123 for (yy = 0; yy < ga->sy; yy++) { 124 gla = &ga->linedata[yy]; 125 glb = &gb->linedata[yy]; 126 if (gla->cellsize != glb->cellsize) 127 return (1); 128 for (xx = 0; xx < ga->sx; xx++) { 129 gca = &gla->celldata[xx]; 130 gcb = &glb->celldata[xx]; 131 if (memcmp(gca, gcb, sizeof (struct grid_cell)) != 0) 132 return (1); 133 if (!(gca->flags & GRID_FLAG_UTF8)) 134 continue; 135 gua = &gla->utf8data[xx]; 136 gub = &glb->utf8data[xx]; 137 if (memcmp(gua, gub, sizeof (struct grid_utf8)) != 0) 138 return (1); 139 } 140 } 141 142 return (0); 143 } 144 145 /* 146 * Collect lines from the history if at the limit. Free the top (oldest) 10% 147 * and shift up. 148 */ 149 void 150 grid_collect_history(struct grid *gd) 151 { 152 u_int yy; 153 154 GRID_DEBUG(gd, ""); 155 156 if (gd->hsize < gd->hlimit) 157 return; 158 159 yy = gd->hlimit / 10; 160 if (yy < 1) 161 yy = 1; 162 163 grid_move_lines(gd, 0, yy, gd->hsize + gd->sy - yy); 164 gd->hsize -= yy; 165 } 166 167 /* 168 * Scroll the entire visible screen, moving one line into the history. Just 169 * allocate a new line at the bottom and move the history size indicator. 170 */ 171 void 172 grid_scroll_history(struct grid *gd) 173 { 174 u_int yy; 175 176 GRID_DEBUG(gd, ""); 177 178 yy = gd->hsize + gd->sy; 179 gd->linedata = xrealloc(gd->linedata, yy + 1, sizeof *gd->linedata); 180 memset(&gd->linedata[yy], 0, sizeof gd->linedata[yy]); 181 182 gd->hsize++; 183 } 184 185 /* Scroll a region up, moving the top line into the history. */ 186 void 187 grid_scroll_history_region(struct grid *gd, u_int upper, u_int lower) 188 { 189 struct grid_line *gl_history, *gl_upper, *gl_lower; 190 u_int yy; 191 192 GRID_DEBUG(gd, "upper=%u, lower=%u", upper, lower); 193 194 /* Create a space for a new line. */ 195 yy = gd->hsize + gd->sy; 196 gd->linedata = xrealloc(gd->linedata, yy + 1, sizeof *gd->linedata); 197 198 /* Move the entire screen down to free a space for this line. */ 199 gl_history = &gd->linedata[gd->hsize]; 200 memmove(gl_history + 1, gl_history, gd->sy * sizeof *gl_history); 201 202 /* Adjust the region and find its start and end. */ 203 upper++; 204 gl_upper = &gd->linedata[upper]; 205 lower++; 206 gl_lower = &gd->linedata[lower]; 207 208 /* Move the line into the history. */ 209 memcpy(gl_history, gl_upper, sizeof *gl_history); 210 211 /* Then move the region up and clear the bottom line. */ 212 memmove(gl_upper, gl_upper + 1, (lower - upper) * sizeof *gl_upper); 213 memset(gl_lower, 0, sizeof *gl_lower); 214 215 /* Move the history offset down over the line. */ 216 gd->hsize++; 217 } 218 219 /* Expand line to fit to cell. */ 220 void 221 grid_expand_line(struct grid *gd, u_int py, u_int sx) 222 { 223 struct grid_line *gl; 224 u_int xx; 225 226 gl = &gd->linedata[py]; 227 if (sx <= gl->cellsize) 228 return; 229 230 gl->celldata = xrealloc(gl->celldata, sx, sizeof *gl->celldata); 231 for (xx = gl->cellsize; xx < sx; xx++) 232 grid_put_cell(gd, xx, py, &grid_default_cell); 233 gl->cellsize = sx; 234 } 235 236 /* Expand line to fit to cell for UTF-8. */ 237 void 238 grid_expand_line_utf8(struct grid *gd, u_int py, u_int sx) 239 { 240 struct grid_line *gl; 241 242 gl = &gd->linedata[py]; 243 if (sx <= gl->utf8size) 244 return; 245 246 gl->utf8data = xrealloc(gl->utf8data, sx, sizeof *gl->utf8data); 247 gl->utf8size = sx; 248 } 249 250 /* Get cell for reading. */ 251 const struct grid_cell * 252 grid_peek_cell(struct grid *gd, u_int px, u_int py) 253 { 254 if (grid_check_y(gd, py) != 0) 255 return (&grid_default_cell); 256 257 if (px >= gd->linedata[py].cellsize) 258 return (&grid_default_cell); 259 return (&gd->linedata[py].celldata[px]); 260 } 261 262 /* Get cell at relative position (for writing). */ 263 struct grid_cell * 264 grid_get_cell(struct grid *gd, u_int px, u_int py) 265 { 266 if (grid_check_y(gd, py) != 0) 267 return (NULL); 268 269 grid_expand_line(gd, py, px + 1); 270 return (&gd->linedata[py].celldata[px]); 271 } 272 273 /* Set cell at relative position. */ 274 void 275 grid_set_cell( 276 struct grid *gd, u_int px, u_int py, const struct grid_cell *gc) 277 { 278 if (grid_check_y(gd, py) != 0) 279 return; 280 281 grid_expand_line(gd, py, px + 1); 282 grid_put_cell(gd, px, py, gc); 283 } 284 285 /* Get UTF-8 for reading. */ 286 const struct grid_utf8 * 287 grid_peek_utf8(struct grid *gd, u_int px, u_int py) 288 { 289 if (grid_check_y(gd, py) != 0) 290 return (NULL); 291 292 if (px >= gd->linedata[py].utf8size) 293 return (NULL); 294 return (&gd->linedata[py].utf8data[px]); 295 } 296 297 /* Get utf8 at relative position (for writing). */ 298 struct grid_utf8 * 299 grid_get_utf8(struct grid *gd, u_int px, u_int py) 300 { 301 if (grid_check_y(gd, py) != 0) 302 return (NULL); 303 304 grid_expand_line_utf8(gd, py, px + 1); 305 return (&gd->linedata[py].utf8data[px]); 306 } 307 308 /* Set utf8 at relative position. */ 309 void 310 grid_set_utf8( 311 struct grid *gd, u_int px, u_int py, const struct grid_utf8 *gc) 312 { 313 if (grid_check_y(gd, py) != 0) 314 return; 315 316 grid_expand_line_utf8(gd, py, px + 1); 317 grid_put_utf8(gd, px, py, gc); 318 } 319 320 /* Clear area. */ 321 void 322 grid_clear(struct grid *gd, u_int px, u_int py, u_int nx, u_int ny) 323 { 324 u_int xx, yy; 325 326 GRID_DEBUG(gd, "px=%u, py=%u, nx=%u, ny=%u", px, py, nx, ny); 327 328 if (nx == 0 || ny == 0) 329 return; 330 331 if (px == 0 && nx == gd->sx) { 332 grid_clear_lines(gd, py, ny); 333 return; 334 } 335 336 if (grid_check_y(gd, py) != 0) 337 return; 338 if (grid_check_y(gd, py + ny - 1) != 0) 339 return; 340 341 for (yy = py; yy < py + ny; yy++) { 342 if (px >= gd->linedata[yy].cellsize) 343 continue; 344 if (px + nx >= gd->linedata[yy].cellsize) { 345 gd->linedata[yy].cellsize = px; 346 continue; 347 } 348 for (xx = px; xx < px + nx; xx++) { 349 if (xx >= gd->linedata[yy].cellsize) 350 break; 351 grid_put_cell(gd, xx, yy, &grid_default_cell); 352 } 353 } 354 } 355 356 /* Clear lines. This just frees and truncates the lines. */ 357 void 358 grid_clear_lines(struct grid *gd, u_int py, u_int ny) 359 { 360 struct grid_line *gl; 361 u_int yy; 362 363 GRID_DEBUG(gd, "py=%u, ny=%u", py, ny); 364 365 if (ny == 0) 366 return; 367 368 if (grid_check_y(gd, py) != 0) 369 return; 370 if (grid_check_y(gd, py + ny - 1) != 0) 371 return; 372 373 for (yy = py; yy < py + ny; yy++) { 374 gl = &gd->linedata[yy]; 375 free(gl->celldata); 376 free(gl->utf8data); 377 memset(gl, 0, sizeof *gl); 378 } 379 } 380 381 /* Move a group of lines. */ 382 void 383 grid_move_lines(struct grid *gd, u_int dy, u_int py, u_int ny) 384 { 385 u_int yy; 386 387 GRID_DEBUG(gd, "dy=%u, py=%u, ny=%u", dy, py, ny); 388 389 if (ny == 0 || py == dy) 390 return; 391 392 if (grid_check_y(gd, py) != 0) 393 return; 394 if (grid_check_y(gd, py + ny - 1) != 0) 395 return; 396 if (grid_check_y(gd, dy) != 0) 397 return; 398 if (grid_check_y(gd, dy + ny - 1) != 0) 399 return; 400 401 /* Free any lines which are being replaced. */ 402 for (yy = dy; yy < dy + ny; yy++) { 403 if (yy >= py && yy < py + ny) 404 continue; 405 grid_clear_lines(gd, yy, 1); 406 } 407 408 memmove( 409 &gd->linedata[dy], &gd->linedata[py], ny * (sizeof *gd->linedata)); 410 411 /* Wipe any lines that have been moved (without freeing them). */ 412 for (yy = py; yy < py + ny; yy++) { 413 if (yy >= dy && yy < dy + ny) 414 continue; 415 memset(&gd->linedata[yy], 0, sizeof gd->linedata[yy]); 416 } 417 } 418 419 /* Move a group of cells. */ 420 void 421 grid_move_cells(struct grid *gd, u_int dx, u_int px, u_int py, u_int nx) 422 { 423 struct grid_line *gl; 424 u_int xx; 425 426 GRID_DEBUG(gd, "dx=%u, px=%u, py=%u, nx=%u", dx, px, py, nx); 427 428 if (nx == 0 || px == dx) 429 return; 430 431 if (grid_check_y(gd, py) != 0) 432 return; 433 gl = &gd->linedata[py]; 434 435 grid_expand_line(gd, py, px + nx); 436 grid_expand_line(gd, py, dx + nx); 437 memmove( 438 &gl->celldata[dx], &gl->celldata[px], nx * sizeof *gl->celldata); 439 440 if (gl->utf8data != NULL) { 441 grid_expand_line_utf8(gd, py, px + nx); 442 grid_expand_line_utf8(gd, py, dx + nx); 443 memmove(&gl->utf8data[dx], 444 &gl->utf8data[px], nx * sizeof *gl->utf8data); 445 } 446 447 /* Wipe any cells that have been moved. */ 448 for (xx = px; xx < px + nx; xx++) { 449 if (xx >= dx && xx < dx + nx) 450 continue; 451 grid_put_cell(gd, xx, py, &grid_default_cell); 452 } 453 } 454 455 /* Convert cells into a string. */ 456 char * 457 grid_string_cells(struct grid *gd, u_int px, u_int py, u_int nx) 458 { 459 const struct grid_cell *gc; 460 const struct grid_utf8 *gu; 461 char *buf; 462 size_t len, off, size; 463 u_int xx; 464 465 GRID_DEBUG(gd, "px=%u, py=%u, nx=%u", px, py, nx); 466 467 len = 128; 468 buf = xmalloc(len); 469 off = 0; 470 471 for (xx = px; xx < px + nx; xx++) { 472 gc = grid_peek_cell(gd, xx, py); 473 if (gc->flags & GRID_FLAG_PADDING) 474 continue; 475 476 if (gc->flags & GRID_FLAG_UTF8) { 477 gu = grid_peek_utf8(gd, xx, py); 478 479 size = grid_utf8_size(gu); 480 while (len < off + size + 1) { 481 buf = xrealloc(buf, 2, len); 482 len *= 2; 483 } 484 485 off += grid_utf8_copy(gu, buf + off, len - off); 486 } else { 487 while (len < off + 2) { 488 buf = xrealloc(buf, 2, len); 489 len *= 2; 490 } 491 492 buf[off++] = gc->data; 493 } 494 } 495 496 while (off > 0 && buf[off - 1] == ' ') 497 off--; 498 buf[off] = '\0'; 499 return (buf); 500 } 501 502 /* 503 * Duplicate a set of lines between two grids. If there aren't enough lines in 504 * either source or destination, the number of lines is limited to the number 505 * available. 506 */ 507 void 508 grid_duplicate_lines( 509 struct grid *dst, u_int dy, struct grid *src, u_int sy, u_int ny) 510 { 511 struct grid_line *dstl, *srcl; 512 u_int yy; 513 514 GRID_DEBUG(src, "dy=%u, sy=%u, ny=%u", dy, sy, ny); 515 516 if (dy + ny > dst->hsize + dst->sy) 517 ny = dst->hsize + dst->sy - dy; 518 if (sy + ny > src->hsize + src->sy) 519 ny = src->hsize + src->sy - sy; 520 grid_clear_lines(dst, dy, ny); 521 522 for (yy = 0; yy < ny; yy++) { 523 srcl = &src->linedata[sy]; 524 dstl = &dst->linedata[dy]; 525 526 memcpy(dstl, srcl, sizeof *dstl); 527 if (srcl->cellsize != 0) { 528 dstl->celldata = xcalloc( 529 srcl->cellsize, sizeof *dstl->celldata); 530 memcpy(dstl->celldata, srcl->celldata, 531 srcl->cellsize * sizeof *dstl->celldata); 532 } 533 if (srcl->utf8size != 0) { 534 dstl->utf8data = xcalloc( 535 srcl->utf8size, sizeof *dstl->utf8data); 536 memcpy(dstl->utf8data, srcl->utf8data, 537 srcl->utf8size * sizeof *dstl->utf8data); 538 } 539 540 sy++; 541 dy++; 542 } 543 } 544