src/basic/format-table.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2
   3 //#include <stdio_ext.h>
   4
   5 //#include "alloc-util.h"
   6 //#include "fd-util.h"
   7 //#include "fileio.h"
   8 //#include "format-table.h"
   9 //#include "gunicode.h"
  10 //#include "pager.h"
  11 //#include "parse-util.h"
  12 //#include "string-util.h"
  13 //#include "terminal-util.h"
  14 //#include "time-util.h"
  15 //#include "utf8.h"
  16 //#include "util.h"
  17
  18 #define DEFAULT_WEIGHT 100
  19
  20 /*
  21    A few notes on implementation details:
  22
  23  - TableCell is a 'fake' structure, it's just used as data type to pass references to specific cell positions in the
  24    table. It can be easily converted to an index number and back.
  25
  26  - TableData is where the actual data is stored: it encapsulates the data and formatting for a specific cell. It's
  27    'pseudo-immutable' and ref-counted. When a cell's data's formatting is to be changed, we duplicate the object if the
  28    ref-counting is larger than 1. Note that TableData and its ref-counting is mostly not visible to the outside. The
  29    outside only sees Table and TableCell.
  30
  31  - The Table object stores a simple one-dimensional array of references to TableData objects, one row after the
  32    previous one.
  33
  34  - There's no special concept of a "row" or "column" in the table, and no special concept of the "header" row. It's all
  35    derived from the cell index: we know how many cells are to be stored in a row, and can determine the rest from
  36    that. The first row is always the header row. If header display is turned off we simply skip outputting the first
  37    row. Also, when sorting rows we always leave the first row where it is, as the header shouldn't move.
  38
  39  - Note because there's no row and no column object some properties that might be approproate as row/column properties
  40    are exposed as cell properties instead. For example, the "weight" of a column (which is used to determine where to
  41    add/remove space preferable when expanding/compressing tables horizontally) is actually made the "weight" of a
  42    cell. Given that we usually need it per-column though we will calculate the average across every cell of the column
  43    instead.
  44
  45  - To make things easy, when cells are added without any explicit configured formatting, then we'll copy the formatting
  46    from the same cell in the previous cell. This is particularly useful for the "weight" of the cell (see above), as
  47    this means setting the weight of the cells of the header row will nicely propagate to all cells in the other rows.
  48 */
  49
  50 typedef struct TableData {
  51         unsigned n_ref;
  52         TableDataType type;
  53
  54         size_t minimum_width;       /* minimum width for the column */
  55         size_t maximum_width;       /* maximum width for the column */
  56         unsigned weight;            /* the horizontal weight for this column, in case the table is expanded/compressed */
  57         unsigned ellipsize_percent; /* 0 … 100, where to place the ellipsis when compression is needed */
  58         unsigned align_percent;     /* 0 … 100, where to pad with spaces when expanding is needed. 0: left-aligned, 100: right-aligned */
  59
  60         const char *color;          /* ANSI color string to use for this cell. When written to terminal should not move cursor. Will automatically be reset after the cell */
  61         char *formatted;            /* A cached textual representation of the cell data, before ellipsation/alignment */
  62
  63         union {
  64                 uint8_t data[0];    /* data is generic array */
  65                 bool boolean;
  66                 usec_t timestamp;
  67                 usec_t timespan;
  68                 uint64_t size;
  69                 char string[0];
  70                 uint32_t uint32;
  71                 /* … add more here as we start supporting more cell data types … */
  72         };
  73 } TableData;
  74
  75 static size_t TABLE_CELL_TO_INDEX(TableCell *cell) {
  76         unsigned i;
  77
  78         assert(cell);
  79
  80         i = PTR_TO_UINT(cell);
  81         assert(i > 0);
  82
  83         return i-1;
  84 }
  85
  86 static TableCell* TABLE_INDEX_TO_CELL(size_t index) {
  87         assert(index != (size_t) -1);
  88         return UINT_TO_PTR((unsigned) (index + 1));
  89 }
  90
  91 struct Table {
  92         size_t n_columns;
  93         size_t n_cells;
  94
  95         bool header;   /* Whether to show the header row? */
  96         size_t width;  /* If != (size_t) -1 the width to format this table in */
  97
  98         TableData **data;
  99         size_t n_allocated;
 100
 101         size_t *display_map;  /* List of columns to show (by their index). It's fine if columns are listed multiple times or not at all */
 102         size_t n_display_map;
 103
 104         size_t *sort_map;     /* The columns to order rows by, in order of preference. */
 105         size_t n_sort_map;
 106 };
 107
 108 Table *table_new_raw(size_t n_columns) {
 109         _cleanup_(table_unrefp) Table *t = NULL;
 110
 111         assert(n_columns > 0);
 112
 113         t = new(Table, 1);
 114         if (!t)
 115                 return NULL;
 116
 117         *t = (struct Table) {
 118                 .n_columns = n_columns,
 119                 .header = true,
 120                 .width = (size_t) -1,
 121         };
 122
 123         return TAKE_PTR(t);
 124 }
 125
 126 Table *table_new_internal(const char *first_header, ...) {
 127         _cleanup_(table_unrefp) Table *t = NULL;
 128         size_t n_columns = 1;
 129         va_list ap;
 130         int r;
 131
 132         assert(first_header);
 133
 134         va_start(ap, first_header);
 135         for (;;) {
 136                 const char *h;
 137
 138                 h = va_arg(ap, const char*);
 139                 if (!h)
 140                         break;
 141
 142                 n_columns++;
 143         }
 144         va_end(ap);
 145
 146         t = table_new_raw(n_columns);
 147         if (!t)
 148                 return NULL;
 149
 150         r = table_add_cell(t, NULL, TABLE_STRING, first_header);
 151         if (r < 0)
 152                 return NULL;
 153
 154         va_start(ap, first_header);
 155         for (;;) {
 156                 const char *h;
 157
 158                 h = va_arg(ap, const char*);
 159                 if (!h)
 160                         break;
 161
 162                 r = table_add_cell(t, NULL, TABLE_STRING, h);
 163                 if (r < 0) {
 164                         va_end(ap);
 165                         return NULL;
 166                 }
 167         }
 168         va_end(ap);
 169
 170         assert(t->n_columns == t->n_cells);
 171         return TAKE_PTR(t);
 172 }
 173
 174 static TableData *table_data_unref(TableData *d) {
 175         if (!d)
 176                 return NULL;
 177
 178         assert(d->n_ref > 0);
 179         d->n_ref--;
 180
 181         if (d->n_ref > 0)
 182                 return NULL;
 183
 184         free(d->formatted);
 185         return mfree(d);
 186 }
 187
 188 DEFINE_TRIVIAL_CLEANUP_FUNC(TableData*, table_data_unref);
 189
 190 static TableData *table_data_ref(TableData *d) {
 191         if (!d)
 192                 return NULL;
 193
 194         assert(d->n_ref > 0);
 195         d->n_ref++;
 196
 197         return d;
 198 }
 199
 200 Table *table_unref(Table *t) {
 201         size_t i;
 202
 203         if (!t)
 204                 return NULL;
 205
 206         for (i = 0; i < t->n_cells; i++)
 207                 table_data_unref(t->data[i]);
 208
 209         free(t->data);
 210         free(t->display_map);
 211         free(t->sort_map);
 212
 213         return mfree(t);
 214 }
 215
 216 static size_t table_data_size(TableDataType type, const void *data) {
 217
 218         switch (type) {
 219
 220         case TABLE_EMPTY:
 221                 return 0;
 222
 223         case TABLE_STRING:
 224                 return strlen(data) + 1;
 225
 226         case TABLE_BOOLEAN:
 227                 return sizeof(bool);
 228
 229         case TABLE_TIMESTAMP:
 230         case TABLE_TIMESPAN:
 231                 return sizeof(usec_t);
 232
 233         case TABLE_SIZE:
 234                 return sizeof(uint64_t);
 235
 236         case TABLE_UINT32:
 237                 return sizeof(uint32_t);
 238
 239         default:
 240                 assert_not_reached("Uh? Unexpected cell type");
 241         }
 242 }
 243
 244 static bool table_data_matches(
 245                 TableData *d,
 246                 TableDataType type,
 247                 const void *data,
 248                 size_t minimum_width,
 249                 size_t maximum_width,
 250                 unsigned weight,
 251                 unsigned align_percent,
 252                 unsigned ellipsize_percent) {
 253
 254         size_t k, l;
 255         assert(d);
 256
 257         if (d->type != type)
 258                 return false;
 259
 260         if (d->minimum_width != minimum_width)
 261                 return false;
 262
 263         if (d->maximum_width != maximum_width)
 264                 return false;
 265
 266         if (d->weight != weight)
 267                 return false;
 268
 269         if (d->align_percent != align_percent)
 270                 return false;
 271
 272         if (d->ellipsize_percent != ellipsize_percent)
 273                 return false;
 274
 275         k = table_data_size(type, data);
 276         l = table_data_size(d->type, d->data);
 277
 278         if (k != l)
 279                 return false;
 280
 281         return memcmp(data, d->data, l) == 0;
 282 }
 283
 284 static TableData *table_data_new(
 285                 TableDataType type,
 286                 const void *data,
 287                 size_t minimum_width,
 288                 size_t maximum_width,
 289                 unsigned weight,
 290                 unsigned align_percent,
 291                 unsigned ellipsize_percent) {
 292
 293         size_t data_size;
 294         TableData *d;
 295
 296         data_size = table_data_size(type, data);
 297
 298         d = malloc0(offsetof(TableData, data) + data_size);
 299         if (!d)
 300                 return NULL;
 301
 302         d->n_ref = 1;
 303         d->type = type;
 304         d->minimum_width = minimum_width;
 305         d->maximum_width = maximum_width;
 306         d->weight = weight;
 307         d->align_percent = align_percent;
 308         d->ellipsize_percent = ellipsize_percent;
 309         memcpy_safe(d->data, data, data_size);
 310
 311         return d;
 312 }
 313
 314 int table_add_cell_full(
 315                 Table *t,
 316                 TableCell **ret_cell,
 317                 TableDataType type,
 318                 const void *data,
 319                 size_t minimum_width,
 320                 size_t maximum_width,
 321                 unsigned weight,
 322                 unsigned align_percent,
 323                 unsigned ellipsize_percent) {
 324
 325         _cleanup_(table_data_unrefp) TableData *d = NULL;
 326         TableData *p;
 327
 328         assert(t);
 329         assert(type >= 0);
 330         assert(type < _TABLE_DATA_TYPE_MAX);
 331
 332         /* Determine the cell adjacent to the current one, but one row up */
 333         if (t->n_cells >= t->n_columns)
 334                 assert_se(p = t->data[t->n_cells - t->n_columns]);
 335         else
 336                 p = NULL;
 337
 338         /* If formatting parameters are left unspecified, copy from the previous row */
 339         if (minimum_width == (size_t) -1)
 340                 minimum_width = p ? p->minimum_width : 1;
 341
 342         if (weight == (unsigned) -1)
 343                 weight = p ? p->weight : DEFAULT_WEIGHT;
 344
 345         if (align_percent == (unsigned) -1)
 346                 align_percent = p ? p->align_percent : 0;
 347
 348         if (ellipsize_percent == (unsigned) -1)
 349                 ellipsize_percent = p ? p->ellipsize_percent : 100;
 350
 351         assert(align_percent <= 100);
 352         assert(ellipsize_percent <= 100);
 353
 354         /* Small optimization: Pretty often adjacent cells in two subsequent lines have the same data and
 355          * formatting. Let's see if we can reuse the cell data and ref it once more. */
 356
 357         if (p && table_data_matches(p, type, data, minimum_width, maximum_width, weight, align_percent, ellipsize_percent))
 358                 d = table_data_ref(p);
 359         else {
 360                 d = table_data_new(type, data, minimum_width, maximum_width, weight, align_percent, ellipsize_percent);
 361                 if (!d)
 362                         return -ENOMEM;
 363         }
 364
 365         if (!GREEDY_REALLOC(t->data, t->n_allocated, MAX(t->n_cells + 1, t->n_columns)))
 366                 return -ENOMEM;
 367
 368         if (ret_cell)
 369                 *ret_cell = TABLE_INDEX_TO_CELL(t->n_cells);
 370
 371         t->data[t->n_cells++] = TAKE_PTR(d);
 372
 373         return 0;
 374 }
 375
 376 int table_dup_cell(Table *t, TableCell *cell) {
 377         size_t i;
 378
 379         assert(t);
 380
 381         /* Add the data of the specified cell a second time as a new cell to the end. */
 382
 383         i = TABLE_CELL_TO_INDEX(cell);
 384         if (i >= t->n_cells)
 385                 return -ENXIO;
 386
 387         if (!GREEDY_REALLOC(t->data, t->n_allocated, MAX(t->n_cells + 1, t->n_columns)))
 388                 return -ENOMEM;
 389
 390         t->data[t->n_cells++] = table_data_ref(t->data[i]);
 391         return 0;
 392 }
 393
 394 static int table_dedup_cell(Table *t, TableCell *cell) {
 395         TableData *nd, *od;
 396         size_t i;
 397
 398         assert(t);
 399
 400         /* Helper call that ensures the specified cell's data object has a ref count of 1, which we can use before
 401          * changing a cell's formatting without effecting every other cell's formatting that shares the same data */
 402
 403         i = TABLE_CELL_TO_INDEX(cell);
 404         if (i >= t->n_cells)
 405                 return -ENXIO;
 406
 407         assert_se(od = t->data[i]);
 408         if (od->n_ref == 1)
 409                 return 0;
 410
 411         assert(od->n_ref > 1);
 412
 413         nd = table_data_new(od->type, od->data, od->minimum_width, od->maximum_width, od->weight, od->align_percent, od->ellipsize_percent);
 414         if (!nd)
 415                 return -ENOMEM;
 416
 417         table_data_unref(od);
 418         t->data[i] = nd;
 419
 420         assert(nd->n_ref == 1);
 421
 422         return 1;
 423 }
 424
 425 static TableData *table_get_data(Table *t, TableCell *cell) {
 426         size_t i;
 427
 428         assert(t);
 429         assert(cell);
 430
 431         /* Get the data object of the specified cell, or NULL if it doesn't exist */
 432
 433         i = TABLE_CELL_TO_INDEX(cell);
 434         if (i >= t->n_cells)
 435                 return NULL;
 436
 437         assert(t->data[i]);
 438         assert(t->data[i]->n_ref > 0);
 439
 440         return t->data[i];
 441 }
 442
 443 int table_set_minimum_width(Table *t, TableCell *cell, size_t minimum_width) {
 444         int r;
 445
 446         assert(t);
 447         assert(cell);
 448
 449         if (minimum_width == (size_t) -1)
 450                 minimum_width = 1;
 451
 452         r = table_dedup_cell(t, cell);
 453         if (r < 0)
 454                 return r;
 455
 456         table_get_data(t, cell)->minimum_width = minimum_width;
 457         return 0;
 458 }
 459
 460 int table_set_maximum_width(Table *t, TableCell *cell, size_t maximum_width) {
 461         int r;
 462
 463         assert(t);
 464         assert(cell);
 465
 466         r = table_dedup_cell(t, cell);
 467         if (r < 0)
 468                 return r;
 469
 470         table_get_data(t, cell)->maximum_width = maximum_width;
 471         return 0;
 472 }
 473
 474 int table_set_weight(Table *t, TableCell *cell, unsigned weight) {
 475         int r;
 476
 477         assert(t);
 478         assert(cell);
 479
 480         if (weight == (unsigned) -1)
 481                 weight = DEFAULT_WEIGHT;
 482
 483         r = table_dedup_cell(t, cell);
 484         if (r < 0)
 485                 return r;
 486
 487         table_get_data(t, cell)->weight = weight;
 488         return 0;
 489 }
 490
 491 int table_set_align_percent(Table *t, TableCell *cell, unsigned percent) {
 492         int r;
 493
 494         assert(t);
 495         assert(cell);
 496
 497         if (percent == (unsigned) -1)
 498                 percent = 0;
 499
 500         assert(percent <= 100);
 501
 502         r = table_dedup_cell(t, cell);
 503         if (r < 0)
 504                 return r;
 505
 506         table_get_data(t, cell)->align_percent = percent;
 507         return 0;
 508 }
 509
 510 int table_set_ellipsize_percent(Table *t, TableCell *cell, unsigned percent) {
 511         int r;
 512
 513         assert(t);
 514         assert(cell);
 515
 516         if (percent == (unsigned) -1)
 517                 percent = 100;
 518
 519         assert(percent <= 100);
 520
 521         r = table_dedup_cell(t, cell);
 522         if (r < 0)
 523                 return r;
 524
 525         table_get_data(t, cell)->ellipsize_percent = percent;
 526         return 0;
 527 }
 528
 529 int table_set_color(Table *t, TableCell *cell, const char *color) {
 530         int r;
 531
 532         assert(t);
 533         assert(cell);
 534
 535         r = table_dedup_cell(t, cell);
 536         if (r < 0)
 537                 return r;
 538
 539         table_get_data(t, cell)->color = empty_to_null(color);
 540         return 0;
 541 }
 542
 543 int table_add_many_internal(Table *t, TableDataType first_type, ...) {
 544         TableDataType type;
 545         va_list ap;
 546         int r;
 547
 548         assert(t);
 549         assert(first_type >= 0);
 550         assert(first_type < _TABLE_DATA_TYPE_MAX);
 551
 552         type = first_type;
 553
 554         va_start(ap, first_type);
 555         for (;;) {
 556                 const void *data;
 557                 union {
 558                         uint64_t size;
 559                         usec_t usec;
 560                         uint32_t uint32;
 561                         bool b;
 562                 } buffer;
 563
 564                 switch (type) {
 565
 566                 case TABLE_EMPTY:
 567                         data = NULL;
 568                         break;
 569
 570                 case TABLE_STRING:
 571                         data = va_arg(ap, const char *);
 572                         break;
 573
 574                 case TABLE_BOOLEAN:
 575                         buffer.b = !!va_arg(ap, int);
 576                         data = &buffer.b;
 577                         break;
 578
 579                 case TABLE_TIMESTAMP:
 580                 case TABLE_TIMESPAN:
 581                         buffer.usec = va_arg(ap, usec_t);
 582                         data = &buffer.usec;
 583                         break;
 584
 585                 case TABLE_SIZE:
 586                         buffer.size = va_arg(ap, uint64_t);
 587                         data = &buffer.size;
 588                         break;
 589
 590                 case TABLE_UINT32:
 591                         buffer.uint32 = va_arg(ap, uint32_t);
 592                         data = &buffer.uint32;
 593                         break;
 594
 595                 case _TABLE_DATA_TYPE_MAX:
 596                         /* Used as end marker */
 597                         va_end(ap);
 598                         return 0;
 599
 600                 default:
 601                         assert_not_reached("Uh? Unexpected data type.");
 602                 }
 603
 604                 r = table_add_cell(t, NULL, type, data);
 605                 if (r < 0) {
 606                         va_end(ap);
 607                         return r;
 608                 }
 609
 610                 type = va_arg(ap, TableDataType);
 611         }
 612 }
 613
 614 void table_set_header(Table *t, bool b) {
 615         assert(t);
 616
 617         t->header = b;
 618 }
 619
 620 void table_set_width(Table *t, size_t width) {
 621         assert(t);
 622
 623         t->width = width;
 624 }
 625
 626 int table_set_display(Table *t, size_t first_column, ...) {
 627         size_t allocated, column;
 628         va_list ap;
 629
 630         assert(t);
 631
 632         allocated = t->n_display_map;
 633         column = first_column;
 634
 635         va_start(ap, first_column);
 636         for (;;) {
 637                 assert(column < t->n_columns);
 638
 639                 if (!GREEDY_REALLOC(t->display_map, allocated, MAX(t->n_columns, t->n_display_map+1))) {
 640                         va_end(ap);
 641                         return -ENOMEM;
 642                 }
 643
 644                 t->display_map[t->n_display_map++] = column;
 645
 646                 column = va_arg(ap, size_t);
 647                 if (column == (size_t) -1)
 648                         break;
 649
 650         }
 651         va_end(ap);
 652
 653         return 0;
 654 }
 655
 656 int table_set_sort(Table *t, size_t first_column, ...) {
 657         size_t allocated, column;
 658         va_list ap;
 659
 660         assert(t);
 661
 662         allocated = t->n_sort_map;
 663         column = first_column;
 664
 665         va_start(ap, first_column);
 666         for (;;) {
 667                 assert(column < t->n_columns);
 668
 669                 if (!GREEDY_REALLOC(t->sort_map, allocated, MAX(t->n_columns, t->n_sort_map+1))) {
 670                         va_end(ap);
 671                         return -ENOMEM;
 672                 }
 673
 674                 t->sort_map[t->n_sort_map++] = column;
 675
 676                 column = va_arg(ap, size_t);
 677                 if (column == (size_t) -1)
 678                         break;
 679         }
 680         va_end(ap);
 681
 682         return 0;
 683 }
 684
 685 static int cell_data_compare(TableData *a, size_t index_a, TableData *b, size_t index_b) {
 686         assert(a);
 687         assert(b);
 688
 689         if (a->type == b->type) {
 690
 691                 /* We only define ordering for cells of the same data type. If cells with different data types are
 692                  * compared we follow the order the cells were originally added in */
 693
 694                 switch (a->type) {
 695
 696                 case TABLE_STRING:
 697                         return strcmp(a->string, b->string);
 698
 699                 case TABLE_BOOLEAN:
 700                         if (!a->boolean && b->boolean)
 701                                 return -1;
 702                         if (a->boolean && !b->boolean)
 703                                 return 1;
 704                         return 0;
 705
 706                 case TABLE_TIMESTAMP:
 707                         if (a->timestamp < b->timestamp)
 708                                 return -1;
 709                         if (a->timestamp > b->timestamp)
 710                                 return 1;
 711                         return 0;
 712
 713                 case TABLE_TIMESPAN:
 714                         if (a->timespan < b->timespan)
 715                                 return -1;
 716                         if (a->timespan > b->timespan)
 717                                 return 1;
 718                         return 0;
 719
 720                 case TABLE_SIZE:
 721                         if (a->size < b->size)
 722                                 return -1;
 723                         if (a->size > b->size)
 724                                 return 1;
 725                         return 0;
 726
 727                 case TABLE_UINT32:
 728                         if (a->uint32 < b->uint32)
 729                                 return -1;
 730                         if (a->uint32 > b->uint32)
 731                                 return 1;
 732                         return 0;
 733
 734                 default:
 735                         ;
 736                 }
 737         }
 738
 739         /* Generic fallback using the orginal order in which the cells where added. */
 740         if (index_a < index_b)
 741                 return -1;
 742         if (index_a > index_b)
 743                 return 1;
 744
 745         return 0;
 746 }
 747
 748 static int table_data_compare(const void *x, const void *y, void *userdata) {
 749         const size_t *a = x, *b = y;
 750         Table *t = userdata;
 751         size_t i;
 752         int r;
 753
 754         assert(t);
 755         assert(t->sort_map);
 756
 757         /* Make sure the header stays at the beginning */
 758         if (*a < t->n_columns && *b < t->n_columns)
 759                 return 0;
 760         if (*a < t->n_columns)
 761                 return -1;
 762         if (*b < t->n_columns)
 763                 return 1;
 764
 765         /* Order other lines by the sorting map */
 766         for (i = 0; i < t->n_sort_map; i++) {
 767                 TableData *d, *dd;
 768
 769                 d = t->data[*a + t->sort_map[i]];
 770                 dd = t->data[*b + t->sort_map[i]];
 771
 772                 r = cell_data_compare(d, *a, dd, *b);
 773                 if (r != 0)
 774                         return r;
 775         }
 776
 777         /* Order identical lines by the order there were originally added in */
 778         if (*a < *b)
 779                 return -1;
 780         if (*a > *b)
 781                 return 1;
 782
 783         return 0;
 784 }
 785
 786 static const char *table_data_format(TableData *d) {
 787         assert(d);
 788
 789         if (d->formatted)
 790                 return d->formatted;
 791
 792         switch (d->type) {
 793         case TABLE_EMPTY:
 794                 return "";
 795
 796         case TABLE_STRING:
 797                 return d->string;
 798
 799         case TABLE_BOOLEAN:
 800                 return yes_no(d->boolean);
 801
 802         case TABLE_TIMESTAMP: {
 803                 _cleanup_free_ char *p;
 804
 805                 p = new(char, FORMAT_TIMESTAMP_MAX);
 806                 if (!p)
 807                         return NULL;
 808
 809                 if (!format_timestamp(p, FORMAT_TIMESTAMP_MAX, d->timestamp))
 810                         return "n/a";
 811
 812                 d->formatted = TAKE_PTR(p);
 813                 break;
 814         }
 815
 816         case TABLE_TIMESPAN: {
 817                 _cleanup_free_ char *p;
 818
 819                 p = new(char, FORMAT_TIMESPAN_MAX);
 820                 if (!p)
 821                         return NULL;
 822
 823                 if (!format_timespan(p, FORMAT_TIMESPAN_MAX, d->timestamp, 0))
 824                         return "n/a";
 825
 826                 d->formatted = TAKE_PTR(p);
 827                 break;
 828         }
 829
 830         case TABLE_SIZE: {
 831                 _cleanup_free_ char *p;
 832
 833                 p = new(char, FORMAT_BYTES_MAX);
 834                 if (!p)
 835                         return NULL;
 836
 837                 if (!format_bytes(p, FORMAT_BYTES_MAX, d->size))
 838                         return "n/a";
 839
 840                 d->formatted = TAKE_PTR(p);
 841                 break;
 842         }
 843
 844         case TABLE_UINT32: {
 845                 _cleanup_free_ char *p;
 846
 847                 p = new(char, DECIMAL_STR_WIDTH(d->uint32) + 1);
 848                 if (!p)
 849                         return NULL;
 850
 851                 sprintf(p, "%" PRIu32, d->uint32);
 852                 d->formatted = TAKE_PTR(p);
 853                 break;
 854         }
 855
 856         default:
 857                 assert_not_reached("Unexpected type?");
 858         }
 859
 860         return d->formatted;
 861 }
 862
 863 static int table_data_requested_width(TableData *d, size_t *ret) {
 864         const char *t;
 865         size_t l;
 866
 867         t = table_data_format(d);
 868         if (!t)
 869                 return -ENOMEM;
 870
 871         l = utf8_console_width(t);
 872         if (l == (size_t) -1)
 873                 return -EINVAL;
 874
 875         if (d->maximum_width != (size_t) -1 && l > d->maximum_width)
 876                 l = d->maximum_width;
 877
 878         if (l < d->minimum_width)
 879                 l = d->minimum_width;
 880
 881         *ret = l;
 882         return 0;
 883 }
 884
 885 static char *align_string_mem(const char *str, size_t new_length, unsigned percent) {
 886         size_t w = 0, space, lspace, old_length;
 887         const char *p;
 888         char *ret;
 889         size_t i;
 890
 891         /* As with ellipsize_mem(), 'old_length' is a byte size while 'new_length' is a width in character cells */
 892
 893         assert(str);
 894         assert(percent <= 100);
 895
 896         old_length = strlen(str);
 897
 898         /* Determine current width on screen */
 899         p = str;
 900         while (p < str + old_length) {
 901                 char32_t c;
 902
 903                 if (utf8_encoded_to_unichar(p, &c) < 0) {
 904                         p++, w++; /* count invalid chars as 1 */
 905                         continue;
 906                 }
 907
 908                 p = utf8_next_char(p);
 909                 w += unichar_iswide(c) ? 2 : 1;
 910         }
 911
 912         /* Already wider than the target, if so, don't do anything */
 913         if (w >= new_length)
 914                 return strndup(str, old_length);
 915
 916         /* How much spaces shall we add? An how much on the left side? */
 917         space = new_length - w;
 918         lspace = space * percent / 100U;
 919
 920         ret = new(char, space + old_length + 1);
 921         if (!ret)
 922                 return NULL;
 923
 924         for (i = 0; i < lspace; i++)
 925                 ret[i] = ' ';
 926         memcpy(ret + lspace, str, old_length);
 927         for (i = lspace + old_length; i < space + old_length; i++)
 928                 ret[i] = ' ';
 929
 930         ret[space + old_length] = 0;
 931         return ret;
 932 }
 933
 934 int table_print(Table *t, FILE *f) {
 935         size_t n_rows, *minimum_width, *maximum_width, display_columns, *requested_width,
 936                 i, j, table_minimum_width, table_maximum_width, table_requested_width, table_effective_width,
 937                 *width;
 938         _cleanup_free_ size_t *sorted = NULL;
 939         uint64_t *column_weight, weight_sum;
 940         int r;
 941
 942         assert(t);
 943
 944         if (!f)
 945                 f = stdout;
 946
 947         /* Ensure we have no incomplete rows */
 948         assert(t->n_cells % t->n_columns == 0);
 949
 950         n_rows = t->n_cells / t->n_columns;
 951         assert(n_rows > 0); /* at least the header row must be complete */
 952
 953         if (t->sort_map) {
 954                 /* If sorting is requested, let's calculate an index table we use to lookup the actual index to display with. */
 955
 956                 sorted = new(size_t, n_rows);
 957                 if (!sorted)
 958                         return -ENOMEM;
 959
 960                 for (i = 0; i < n_rows; i++)
 961                         sorted[i] = i * t->n_columns;
 962
 963                 qsort_r_safe(sorted, n_rows, sizeof(size_t), table_data_compare, t);
 964         }
 965
 966         if (t->display_map)
 967                 display_columns = t->n_display_map;
 968         else
 969                 display_columns = t->n_columns;
 970
 971         assert(display_columns > 0);
 972
 973         minimum_width = newa(size_t, display_columns);
 974         maximum_width = newa(size_t, display_columns);
 975         requested_width = newa(size_t, display_columns);
 976         width = newa(size_t, display_columns);
 977         column_weight = newa0(uint64_t, display_columns);
 978
 979         for (j = 0; j < display_columns; j++) {
 980                 minimum_width[j] = 1;
 981                 maximum_width[j] = (size_t) -1;
 982                 requested_width[j] = (size_t) -1;
 983         }
 984
 985         /* First pass: determine column sizes */
 986         for (i = t->header ? 0 : 1; i < n_rows; i++) {
 987                 TableData **row;
 988
 989                 /* Note that we don't care about ordering at this time, as we just want to determine column sizes,
 990                  * hence we don't care for sorted[] during the first pass. */
 991                 row = t->data + i * t->n_columns;
 992
 993                 for (j = 0; j < display_columns; j++) {
 994                         TableData *d;
 995                         size_t req;
 996
 997                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
 998
 999                         r = table_data_requested_width(d, &req);
1000                         if (r < 0)
1001                                 return r;
1002
1003                         /* Determine the biggest width that any cell in this column would like to have */
1004                         if (requested_width[j] == (size_t) -1 ||
1005                             requested_width[j] < req)
1006                                 requested_width[j] = req;
1007
1008                         /* Determine the minimum width any cell in this column needs */
1009                         if (minimum_width[j] < d->minimum_width)
1010                                 minimum_width[j] = d->minimum_width;
1011
1012                         /* Determine the maximum width any cell in this column needs */
1013                         if (d->maximum_width != (size_t) -1 &&
1014                             (maximum_width[j] == (size_t) -1 ||
1015                              maximum_width[j] > d->maximum_width))
1016                                 maximum_width[j] = d->maximum_width;
1017
1018                         /* Determine the full columns weight */
1019                         column_weight[j] += d->weight;
1020                 }
1021         }
1022
1023         /* One space between each column */
1024         table_requested_width = table_minimum_width = table_maximum_width = display_columns - 1;
1025
1026         /* Calculate the total weight for all columns, plus the minimum, maximum and requested width for the table. */
1027         weight_sum = 0;
1028         for (j = 0; j < display_columns; j++) {
1029                 weight_sum += column_weight[j];
1030
1031                 table_minimum_width += minimum_width[j];
1032
1033                 if (maximum_width[j] == (size_t) -1)
1034                         table_maximum_width = (size_t) -1;
1035                 else
1036                         table_maximum_width += maximum_width[j];
1037
1038                 table_requested_width += requested_width[j];
1039         }
1040
1041         /* Calculate effective table width */
1042         if (t->width == (size_t) -1)
1043                 table_effective_width = pager_have() ? table_requested_width : MIN(table_requested_width, columns());
1044         else
1045                 table_effective_width = t->width;
1046
1047         if (table_maximum_width != (size_t) -1 && table_effective_width > table_maximum_width)
1048                 table_effective_width = table_maximum_width;
1049
1050         if (table_effective_width < table_minimum_width)
1051                 table_effective_width = table_minimum_width;
1052
1053         if (table_effective_width >= table_requested_width) {
1054                 size_t extra;
1055
1056                 /* We have extra room, let's distribute it among columns according to their weights. We first provide
1057                  * each column with what it asked for and the distribute the rest.  */
1058
1059                 extra = table_effective_width - table_requested_width;
1060
1061                 for (j = 0; j < display_columns; j++) {
1062                         size_t delta;
1063
1064                         if (weight_sum == 0)
1065                                 width[j] = requested_width[j] + extra / (display_columns - j); /* Avoid division by zero */
1066                         else
1067                                 width[j] = requested_width[j] + (extra * column_weight[j]) / weight_sum;
1068
1069                         if (maximum_width[j] != (size_t) -1 && width[j] > maximum_width[j])
1070                                 width[j] = maximum_width[j];
1071
1072                         if (width[j] < minimum_width[j])
1073                                 width[j] = minimum_width[j];
1074
1075                         assert(width[j] >= requested_width[j]);
1076                         delta = width[j] - requested_width[j];
1077
1078                         /* Subtract what we just added from the rest */
1079                         if (extra > delta)
1080                                 extra -= delta;
1081                         else
1082                                 extra = 0;
1083
1084                         assert(weight_sum >= column_weight[j]);
1085                         weight_sum -= column_weight[j];
1086                 }
1087
1088         } else {
1089                 /* We need to compress the table, columns can't get what they asked for. We first provide each column
1090                  * with the minimum they need, and then distribute anything left. */
1091                 bool finalize = false;
1092                 size_t extra;
1093
1094                 extra = table_effective_width - table_minimum_width;
1095
1096                 for (j = 0; j < display_columns; j++)
1097                         width[j] = (size_t) -1;
1098
1099                 for (;;) {
1100                         bool restart = false;
1101
1102                         for (j = 0; j < display_columns; j++) {
1103                                 size_t delta, w;
1104
1105                                 /* Did this column already get something assigned? If so, let's skip to the next */
1106                                 if (width[j] != (size_t) -1)
1107                                         continue;
1108
1109                                 if (weight_sum == 0)
1110                                         w = minimum_width[j] + extra / (display_columns - j); /* avoid division by zero */
1111                                 else
1112                                         w = minimum_width[j] + (extra * column_weight[j]) / weight_sum;
1113
1114                                 if (w >= requested_width[j]) {
1115                                         /* Never give more than requested. If we hit a column like this, there's more
1116                                          * space to allocate to other columns which means we need to restart the
1117                                          * iteration. However, if we hit a column like this, let's assign it the space
1118                                          * it wanted for good early.*/
1119
1120                                         w = requested_width[j];
1121                                         restart = true;
1122
1123                                 } else if (!finalize)
1124                                         continue;
1125
1126                                 width[j] = w;
1127
1128                                 assert(w >= minimum_width[j]);
1129                                 delta = w - minimum_width[j];
1130
1131                                 assert(delta <= extra);
1132                                 extra -= delta;
1133
1134                                 assert(weight_sum >= column_weight[j]);
1135                                 weight_sum -= column_weight[j];
1136
1137                                 if (restart)
1138                                         break;
1139                         }
1140
1141                         if (finalize) {
1142                                 assert(!restart);
1143                                 break;
1144                         }
1145
1146                         if (!restart)
1147                                 finalize = true;
1148                 }
1149         }
1150
1151         /* Second pass: show output */
1152         for (i = t->header ? 0 : 1; i < n_rows; i++) {
1153                 TableData **row;
1154
1155                 if (sorted)
1156                         row = t->data + sorted[i];
1157                 else
1158                         row = t->data + i * t->n_columns;
1159
1160                 for (j = 0; j < display_columns; j++) {
1161                         _cleanup_free_ char *buffer = NULL;
1162                         const char *field;
1163                         TableData *d;
1164                         size_t l;
1165
1166                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
1167
1168                         field = table_data_format(d);
1169                         if (!field)
1170                                 return -ENOMEM;
1171
1172                         l = utf8_console_width(field);
1173                         if (l > width[j]) {
1174                                 /* Field is wider than allocated space. Let's ellipsize */
1175
1176                                 buffer = ellipsize(field, width[j], d->ellipsize_percent);
1177                                 if (!buffer)
1178                                         return -ENOMEM;
1179
1180                                 field = buffer;
1181
1182                         } else if (l < width[j]) {
1183                                 /* Field is shorter than allocated space. Let's align with spaces */
1184
1185                                 buffer = align_string_mem(field, width[j], d->align_percent);
1186                                 if (!buffer)
1187                                         return -ENOMEM;
1188
1189                                 field = buffer;
1190                         }
1191
1192                         if (j > 0)
1193                                 fputc(' ', f); /* column separator */
1194
1195                         if (d->color)
1196                                 fputs(d->color, f);
1197
1198                         fputs(field, f);
1199
1200                         if (d->color)
1201                                 fputs(ansi_normal(), f);
1202                 }
1203
1204                 fputc('\n', f);
1205         }
1206
1207         return fflush_and_check(f);
1208 }
1209
1210 int table_format(Table *t, char **ret) {
1211         _cleanup_fclose_ FILE *f = NULL;
1212         char *buf = NULL;
1213         size_t sz = 0;
1214         int r;
1215
1216         f = open_memstream(&buf, &sz);
1217         if (!f)
1218                 return -ENOMEM;
1219
1220         (void) __fsetlocking(f, FSETLOCKING_BYCALLER);
1221
1222         r = table_print(t, f);
1223         if (r < 0)
1224                 return r;
1225
1226         f = safe_fclose(f);
1227
1228         *ret = buf;
1229
1230         return 0;
1231 }
1232
1233 size_t table_get_rows(Table *t) {
1234         if (!t)
1235                 return 0;
1236
1237         assert(t->n_columns > 0);
1238         return t->n_cells / t->n_columns;
1239 }
1240
1241 size_t table_get_columns(Table *t) {
1242         if (!t)
1243                 return 0;
1244
1245         assert(t->n_columns > 0);
1246         return t->n_columns;
1247 }