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 old_length, size_t new_length, unsigned percent) {
 886         size_t w = 0, space, lspace;
 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         if (old_length == (size_t) -1)
 897                 old_length = strlen(str);
 898
 899         /* Determine current width on screen */
 900         p = str;
 901         while (p < str + old_length) {
 902                 char32_t c;
 903
 904                 if (utf8_encoded_to_unichar(p, &c) < 0) {
 905                         p++, w++; /* count invalid chars as 1 */
 906                         continue;
 907                 }
 908
 909                 p = utf8_next_char(p);
 910                 w += unichar_iswide(c) ? 2 : 1;
 911         }
 912
 913         /* Already wider than the target, if so, don't do anything */
 914         if (w >= new_length)
 915                 return strndup(str, old_length);
 916
 917         /* How much spaces shall we add? An how much on the left side? */
 918         space = new_length - w;
 919         lspace = space * percent / 100U;
 920
 921         ret = new(char, space + old_length + 1);
 922         if (!ret)
 923                 return NULL;
 924
 925         for (i = 0; i < lspace; i++)
 926                 ret[i] = ' ';
 927         memcpy(ret + lspace, str, old_length);
 928         for (i = lspace + old_length; i < space + old_length; i++)
 929                 ret[i] = ' ';
 930
 931         ret[space + old_length] = 0;
 932         return ret;
 933 }
 934
 935 int table_print(Table *t, FILE *f) {
 936         size_t n_rows, *minimum_width, *maximum_width, display_columns, *requested_width,
 937                 i, j, table_minimum_width, table_maximum_width, table_requested_width, table_effective_width,
 938                 *width;
 939         _cleanup_free_ size_t *sorted = NULL;
 940         uint64_t *column_weight, weight_sum;
 941         int r;
 942
 943         assert(t);
 944
 945         if (!f)
 946                 f = stdout;
 947
 948         /* Ensure we have no incomplete rows */
 949         assert(t->n_cells % t->n_columns == 0);
 950
 951         n_rows = t->n_cells / t->n_columns;
 952         assert(n_rows > 0); /* at least the header row must be complete */
 953
 954         if (t->sort_map) {
 955                 /* If sorting is requested, let's calculate an index table we use to lookup the actual index to display with. */
 956
 957                 sorted = new(size_t, n_rows);
 958                 if (!sorted)
 959                         return -ENOMEM;
 960
 961                 for (i = 0; i < n_rows; i++)
 962                         sorted[i] = i * t->n_columns;
 963
 964                 qsort_r_safe(sorted, n_rows, sizeof(size_t), table_data_compare, t);
 965         }
 966
 967         if (t->display_map)
 968                 display_columns = t->n_display_map;
 969         else
 970                 display_columns = t->n_columns;
 971
 972         assert(display_columns > 0);
 973
 974         minimum_width = newa(size_t, display_columns);
 975         maximum_width = newa(size_t, display_columns);
 976         requested_width = newa(size_t, display_columns);
 977         width = newa(size_t, display_columns);
 978         column_weight = newa0(uint64_t, display_columns);
 979
 980         for (j = 0; j < display_columns; j++) {
 981                 minimum_width[j] = 1;
 982                 maximum_width[j] = (size_t) -1;
 983                 requested_width[j] = (size_t) -1;
 984         }
 985
 986         /* First pass: determine column sizes */
 987         for (i = t->header ? 0 : 1; i < n_rows; i++) {
 988                 TableData **row;
 989
 990                 /* Note that we don't care about ordering at this time, as we just want to determine column sizes,
 991                  * hence we don't care for sorted[] during the first pass. */
 992                 row = t->data + i * t->n_columns;
 993
 994                 for (j = 0; j < display_columns; j++) {
 995                         TableData *d;
 996                         size_t req;
 997
 998                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
 999
1000                         r = table_data_requested_width(d, &req);
1001                         if (r < 0)
1002                                 return r;
1003
1004                         /* Determine the biggest width that any cell in this column would like to have */
1005                         if (requested_width[j] == (size_t) -1 ||
1006                             requested_width[j] < req)
1007                                 requested_width[j] = req;
1008
1009                         /* Determine the minimum width any cell in this column needs */
1010                         if (minimum_width[j] < d->minimum_width)
1011                                 minimum_width[j] = d->minimum_width;
1012
1013                         /* Determine the maximum width any cell in this column needs */
1014                         if (d->maximum_width != (size_t) -1 &&
1015                             (maximum_width[j] == (size_t) -1 ||
1016                              maximum_width[j] > d->maximum_width))
1017                                 maximum_width[j] = d->maximum_width;
1018
1019                         /* Determine the full columns weight */
1020                         column_weight[j] += d->weight;
1021                 }
1022         }
1023
1024         /* One space between each column */
1025         table_requested_width = table_minimum_width = table_maximum_width = display_columns - 1;
1026
1027         /* Calculate the total weight for all columns, plus the minimum, maximum and requested width for the table. */
1028         weight_sum = 0;
1029         for (j = 0; j < display_columns; j++) {
1030                 weight_sum += column_weight[j];
1031
1032                 table_minimum_width += minimum_width[j];
1033
1034                 if (maximum_width[j] == (size_t) -1)
1035                         table_maximum_width = (size_t) -1;
1036                 else
1037                         table_maximum_width += maximum_width[j];
1038
1039                 table_requested_width += requested_width[j];
1040         }
1041
1042         /* Calculate effective table width */
1043         if (t->width == (size_t) -1)
1044                 table_effective_width = pager_have() ? table_requested_width : MIN(table_requested_width, columns());
1045         else
1046                 table_effective_width = t->width;
1047
1048         if (table_maximum_width != (size_t) -1 && table_effective_width > table_maximum_width)
1049                 table_effective_width = table_maximum_width;
1050
1051         if (table_effective_width < table_minimum_width)
1052                 table_effective_width = table_minimum_width;
1053
1054         if (table_effective_width >= table_requested_width) {
1055                 size_t extra;
1056
1057                 /* We have extra room, let's distribute it among columns according to their weights. We first provide
1058                  * each column with what it asked for and the distribute the rest.  */
1059
1060                 extra = table_effective_width - table_requested_width;
1061
1062                 for (j = 0; j < display_columns; j++) {
1063                         size_t delta;
1064
1065                         if (weight_sum == 0)
1066                                 width[j] = requested_width[j] + extra / (display_columns - j); /* Avoid division by zero */
1067                         else
1068                                 width[j] = requested_width[j] + (extra * column_weight[j]) / weight_sum;
1069
1070                         if (maximum_width[j] != (size_t) -1 && width[j] > maximum_width[j])
1071                                 width[j] = maximum_width[j];
1072
1073                         if (width[j] < minimum_width[j])
1074                                 width[j] = minimum_width[j];
1075
1076                         assert(width[j] >= requested_width[j]);
1077                         delta = width[j] - requested_width[j];
1078
1079                         /* Subtract what we just added from the rest */
1080                         if (extra > delta)
1081                                 extra -= delta;
1082                         else
1083                                 extra = 0;
1084
1085                         assert(weight_sum >= column_weight[j]);
1086                         weight_sum -= column_weight[j];
1087                 }
1088
1089         } else {
1090                 /* We need to compress the table, columns can't get what they asked for. We first provide each column
1091                  * with the minimum they need, and then distribute anything left. */
1092                 bool finalize = false;
1093                 size_t extra;
1094
1095                 extra = table_effective_width - table_minimum_width;
1096
1097                 for (j = 0; j < display_columns; j++)
1098                         width[j] = (size_t) -1;
1099
1100                 for (;;) {
1101                         bool restart = false;
1102
1103                         for (j = 0; j < display_columns; j++) {
1104                                 size_t delta, w;
1105
1106                                 /* Did this column already get something assigned? If so, let's skip to the next */
1107                                 if (width[j] != (size_t) -1)
1108                                         continue;
1109
1110                                 if (weight_sum == 0)
1111                                         w = minimum_width[j] + extra / (display_columns - j); /* avoid division by zero */
1112                                 else
1113                                         w = minimum_width[j] + (extra * column_weight[j]) / weight_sum;
1114
1115                                 if (w >= requested_width[j]) {
1116                                         /* Never give more than requested. If we hit a column like this, there's more
1117                                          * space to allocate to other columns which means we need to restart the
1118                                          * iteration. However, if we hit a column like this, let's assign it the space
1119                                          * it wanted for good early.*/
1120
1121                                         w = requested_width[j];
1122                                         restart = true;
1123
1124                                 } else if (!finalize)
1125                                         continue;
1126
1127                                 width[j] = w;
1128
1129                                 assert(w >= minimum_width[j]);
1130                                 delta = w - minimum_width[j];
1131
1132                                 assert(delta <= extra);
1133                                 extra -= delta;
1134
1135                                 assert(weight_sum >= column_weight[j]);
1136                                 weight_sum -= column_weight[j];
1137
1138                                 if (restart)
1139                                         break;
1140                         }
1141
1142                         if (finalize) {
1143                                 assert(!restart);
1144                                 break;
1145                         }
1146
1147                         if (!restart)
1148                                 finalize = true;
1149                 }
1150         }
1151
1152         /* Second pass: show output */
1153         for (i = t->header ? 0 : 1; i < n_rows; i++) {
1154                 TableData **row;
1155
1156                 if (sorted)
1157                         row = t->data + sorted[i];
1158                 else
1159                         row = t->data + i * t->n_columns;
1160
1161                 for (j = 0; j < display_columns; j++) {
1162                         _cleanup_free_ char *buffer = NULL;
1163                         const char *field;
1164                         TableData *d;
1165                         size_t l;
1166
1167                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
1168
1169                         field = table_data_format(d);
1170                         if (!field)
1171                                 return -ENOMEM;
1172
1173                         l = utf8_console_width(field);
1174                         if (l > width[j]) {
1175                                 /* Field is wider than allocated space. Let's ellipsize */
1176
1177                                 buffer = ellipsize_mem(field, (size_t) -1, width[j], d->ellipsize_percent);
1178                                 if (!buffer)
1179                                         return -ENOMEM;
1180
1181                                 field = buffer;
1182
1183                         } else if (l < width[j]) {
1184                                 /* Field is shorter than allocated space. Let's align with spaces */
1185
1186                                 buffer = align_string_mem(field, (size_t) -1, width[j], d->align_percent);
1187                                 if (!buffer)
1188                                         return -ENOMEM;
1189
1190                                 field = buffer;
1191                         }
1192
1193                         if (j > 0)
1194                                 fputc(' ', f); /* column separator */
1195
1196                         if (d->color)
1197                                 fputs(d->color, f);
1198
1199                         fputs(field, f);
1200
1201                         if (d->color)
1202                                 fputs(ansi_normal(), f);
1203                 }
1204
1205                 fputc('\n', f);
1206         }
1207
1208         return fflush_and_check(f);
1209 }
1210
1211 int table_format(Table *t, char **ret) {
1212         _cleanup_fclose_ FILE *f = NULL;
1213         char *buf = NULL;
1214         size_t sz = 0;
1215         int r;
1216
1217         f = open_memstream(&buf, &sz);
1218         if (!f)
1219                 return -ENOMEM;
1220
1221         (void) __fsetlocking(f, FSETLOCKING_BYCALLER);
1222
1223         r = table_print(t, f);
1224         if (r < 0)
1225                 return r;
1226
1227         f = safe_fclose(f);
1228
1229         *ret = buf;
1230
1231         return 0;
1232 }
1233
1234 size_t table_get_rows(Table *t) {
1235         if (!t)
1236                 return 0;
1237
1238         assert(t->n_columns > 0);
1239         return t->n_cells / t->n_columns;
1240 }
1241
1242 size_t table_get_columns(Table *t) {
1243         if (!t)
1244                 return 0;
1245
1246         assert(t->n_columns > 0);
1247         return t->n_columns;
1248 }