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 #if 0 /// UNNEEDED by elogind
 377 int table_dup_cell(Table *t, TableCell *cell) {
 378         size_t i;
 379
 380         assert(t);
 381
 382         /* Add the data of the specified cell a second time as a new cell to the end. */
 383
 384         i = TABLE_CELL_TO_INDEX(cell);
 385         if (i >= t->n_cells)
 386                 return -ENXIO;
 387
 388         if (!GREEDY_REALLOC(t->data, t->n_allocated, MAX(t->n_cells + 1, t->n_columns)))
 389                 return -ENOMEM;
 390
 391         t->data[t->n_cells++] = table_data_ref(t->data[i]);
 392         return 0;
 393 }
 394 #endif // 0
 395
 396 static int table_dedup_cell(Table *t, TableCell *cell) {
 397         TableData *nd, *od;
 398         size_t i;
 399
 400         assert(t);
 401
 402         /* Helper call that ensures the specified cell's data object has a ref count of 1, which we can use before
 403          * changing a cell's formatting without effecting every other cell's formatting that shares the same data */
 404
 405         i = TABLE_CELL_TO_INDEX(cell);
 406         if (i >= t->n_cells)
 407                 return -ENXIO;
 408
 409         assert_se(od = t->data[i]);
 410         if (od->n_ref == 1)
 411                 return 0;
 412
 413         assert(od->n_ref > 1);
 414
 415         nd = table_data_new(od->type, od->data, od->minimum_width, od->maximum_width, od->weight, od->align_percent, od->ellipsize_percent);
 416         if (!nd)
 417                 return -ENOMEM;
 418
 419         table_data_unref(od);
 420         t->data[i] = nd;
 421
 422         assert(nd->n_ref == 1);
 423
 424         return 1;
 425 }
 426
 427 static TableData *table_get_data(Table *t, TableCell *cell) {
 428         size_t i;
 429
 430         assert(t);
 431         assert(cell);
 432
 433         /* Get the data object of the specified cell, or NULL if it doesn't exist */
 434
 435         i = TABLE_CELL_TO_INDEX(cell);
 436         if (i >= t->n_cells)
 437                 return NULL;
 438
 439         assert(t->data[i]);
 440         assert(t->data[i]->n_ref > 0);
 441
 442         return t->data[i];
 443 }
 444
 445 #if 0 /// UNNEEDED by elogind
 446 int table_set_minimum_width(Table *t, TableCell *cell, size_t minimum_width) {
 447         int r;
 448
 449         assert(t);
 450         assert(cell);
 451
 452         if (minimum_width == (size_t) -1)
 453                 minimum_width = 1;
 454
 455         r = table_dedup_cell(t, cell);
 456         if (r < 0)
 457                 return r;
 458
 459         table_get_data(t, cell)->minimum_width = minimum_width;
 460         return 0;
 461 }
 462
 463 int table_set_maximum_width(Table *t, TableCell *cell, size_t maximum_width) {
 464         int r;
 465
 466         assert(t);
 467         assert(cell);
 468
 469         r = table_dedup_cell(t, cell);
 470         if (r < 0)
 471                 return r;
 472
 473         table_get_data(t, cell)->maximum_width = maximum_width;
 474         return 0;
 475 }
 476
 477 int table_set_weight(Table *t, TableCell *cell, unsigned weight) {
 478         int r;
 479
 480         assert(t);
 481         assert(cell);
 482
 483         if (weight == (unsigned) -1)
 484                 weight = DEFAULT_WEIGHT;
 485
 486         r = table_dedup_cell(t, cell);
 487         if (r < 0)
 488                 return r;
 489
 490         table_get_data(t, cell)->weight = weight;
 491         return 0;
 492 }
 493 #endif // 0
 494
 495 int table_set_align_percent(Table *t, TableCell *cell, unsigned percent) {
 496         int r;
 497
 498         assert(t);
 499         assert(cell);
 500
 501         if (percent == (unsigned) -1)
 502                 percent = 0;
 503
 504         assert(percent <= 100);
 505
 506         r = table_dedup_cell(t, cell);
 507         if (r < 0)
 508                 return r;
 509
 510         table_get_data(t, cell)->align_percent = percent;
 511         return 0;
 512 }
 513
 514 #if 0 /// UNNEEDED by elogind
 515 int table_set_ellipsize_percent(Table *t, TableCell *cell, unsigned percent) {
 516         int r;
 517
 518         assert(t);
 519         assert(cell);
 520
 521         if (percent == (unsigned) -1)
 522                 percent = 100;
 523
 524         assert(percent <= 100);
 525
 526         r = table_dedup_cell(t, cell);
 527         if (r < 0)
 528                 return r;
 529
 530         table_get_data(t, cell)->ellipsize_percent = percent;
 531         return 0;
 532 }
 533
 534 int table_set_color(Table *t, TableCell *cell, const char *color) {
 535         int r;
 536
 537         assert(t);
 538         assert(cell);
 539
 540         r = table_dedup_cell(t, cell);
 541         if (r < 0)
 542                 return r;
 543
 544         table_get_data(t, cell)->color = empty_to_null(color);
 545         return 0;
 546 }
 547 #endif // 0
 548
 549 int table_add_many_internal(Table *t, TableDataType first_type, ...) {
 550         TableDataType type;
 551         va_list ap;
 552         int r;
 553
 554         assert(t);
 555         assert(first_type >= 0);
 556         assert(first_type < _TABLE_DATA_TYPE_MAX);
 557
 558         type = first_type;
 559
 560         va_start(ap, first_type);
 561         for (;;) {
 562                 const void *data;
 563                 union {
 564                         uint64_t size;
 565                         usec_t usec;
 566                         uint32_t uint32;
 567                         bool b;
 568                 } buffer;
 569
 570                 switch (type) {
 571
 572                 case TABLE_EMPTY:
 573                         data = NULL;
 574                         break;
 575
 576                 case TABLE_STRING:
 577                         data = va_arg(ap, const char *);
 578                         break;
 579
 580                 case TABLE_BOOLEAN:
 581                         buffer.b = va_arg(ap, int);
 582                         data = &buffer.b;
 583                         break;
 584
 585                 case TABLE_TIMESTAMP:
 586                 case TABLE_TIMESPAN:
 587                         buffer.usec = va_arg(ap, usec_t);
 588                         data = &buffer.usec;
 589                         break;
 590
 591                 case TABLE_SIZE:
 592                         buffer.size = va_arg(ap, uint64_t);
 593                         data = &buffer.size;
 594                         break;
 595
 596                 case TABLE_UINT32:
 597                         buffer.uint32 = va_arg(ap, uint32_t);
 598                         data = &buffer.uint32;
 599                         break;
 600
 601                 case _TABLE_DATA_TYPE_MAX:
 602                         /* Used as end marker */
 603                         va_end(ap);
 604                         return 0;
 605
 606                 default:
 607                         assert_not_reached("Uh? Unexpected data type.");
 608                 }
 609
 610                 r = table_add_cell(t, NULL, type, data);
 611                 if (r < 0) {
 612                         va_end(ap);
 613                         return r;
 614                 }
 615
 616                 type = va_arg(ap, TableDataType);
 617         }
 618 }
 619
 620 void table_set_header(Table *t, bool b) {
 621         assert(t);
 622
 623         t->header = b;
 624 }
 625
 626 void table_set_width(Table *t, size_t width) {
 627         assert(t);
 628
 629         t->width = width;
 630 }
 631
 632 int table_set_display(Table *t, size_t first_column, ...) {
 633         size_t allocated, column;
 634         va_list ap;
 635
 636         assert(t);
 637
 638         allocated = t->n_display_map;
 639         column = first_column;
 640
 641         va_start(ap, first_column);
 642         for (;;) {
 643                 assert(column < t->n_columns);
 644
 645                 if (!GREEDY_REALLOC(t->display_map, allocated, MAX(t->n_columns, t->n_display_map+1))) {
 646                         va_end(ap);
 647                         return -ENOMEM;
 648                 }
 649
 650                 t->display_map[t->n_display_map++] = column;
 651
 652                 column = va_arg(ap, size_t);
 653                 if (column == (size_t) -1)
 654                         break;
 655
 656         }
 657         va_end(ap);
 658
 659         return 0;
 660 }
 661
 662 int table_set_sort(Table *t, size_t first_column, ...) {
 663         size_t allocated, column;
 664         va_list ap;
 665
 666         assert(t);
 667
 668         allocated = t->n_sort_map;
 669         column = first_column;
 670
 671         va_start(ap, first_column);
 672         for (;;) {
 673                 assert(column < t->n_columns);
 674
 675                 if (!GREEDY_REALLOC(t->sort_map, allocated, MAX(t->n_columns, t->n_sort_map+1))) {
 676                         va_end(ap);
 677                         return -ENOMEM;
 678                 }
 679
 680                 t->sort_map[t->n_sort_map++] = column;
 681
 682                 column = va_arg(ap, size_t);
 683                 if (column == (size_t) -1)
 684                         break;
 685         }
 686         va_end(ap);
 687
 688         return 0;
 689 }
 690
 691 static int cell_data_compare(TableData *a, size_t index_a, TableData *b, size_t index_b) {
 692         assert(a);
 693         assert(b);
 694
 695         if (a->type == b->type) {
 696
 697                 /* We only define ordering for cells of the same data type. If cells with different data types are
 698                  * compared we follow the order the cells were originally added in */
 699
 700                 switch (a->type) {
 701
 702                 case TABLE_STRING:
 703                         return strcmp(a->string, b->string);
 704
 705                 case TABLE_BOOLEAN:
 706                         if (!a->boolean && b->boolean)
 707                                 return -1;
 708                         if (a->boolean && !b->boolean)
 709                                 return 1;
 710                         return 0;
 711
 712                 case TABLE_TIMESTAMP:
 713                         if (a->timestamp < b->timestamp)
 714                                 return -1;
 715                         if (a->timestamp > b->timestamp)
 716                                 return 1;
 717                         return 0;
 718
 719                 case TABLE_TIMESPAN:
 720                         if (a->timespan < b->timespan)
 721                                 return -1;
 722                         if (a->timespan > b->timespan)
 723                                 return 1;
 724                         return 0;
 725
 726                 case TABLE_SIZE:
 727                         if (a->size < b->size)
 728                                 return -1;
 729                         if (a->size > b->size)
 730                                 return 1;
 731                         return 0;
 732
 733                 case TABLE_UINT32:
 734                         if (a->uint32 < b->uint32)
 735                                 return -1;
 736                         if (a->uint32 > b->uint32)
 737                                 return 1;
 738                         return 0;
 739
 740                 default:
 741                         ;
 742                 }
 743         }
 744
 745         /* Generic fallback using the orginal order in which the cells where added. */
 746         if (index_a < index_b)
 747                 return -1;
 748         if (index_a > index_b)
 749                 return 1;
 750
 751         return 0;
 752 }
 753
 754 static int table_data_compare(const void *x, const void *y, void *userdata) {
 755         const size_t *a = x, *b = y;
 756         Table *t = userdata;
 757         size_t i;
 758         int r;
 759
 760         assert(t);
 761         assert(t->sort_map);
 762
 763         /* Make sure the header stays at the beginning */
 764         if (*a < t->n_columns && *b < t->n_columns)
 765                 return 0;
 766         if (*a < t->n_columns)
 767                 return -1;
 768         if (*b < t->n_columns)
 769                 return 1;
 770
 771         /* Order other lines by the sorting map */
 772         for (i = 0; i < t->n_sort_map; i++) {
 773                 TableData *d, *dd;
 774
 775                 d = t->data[*a + t->sort_map[i]];
 776                 dd = t->data[*b + t->sort_map[i]];
 777
 778                 r = cell_data_compare(d, *a, dd, *b);
 779                 if (r != 0)
 780                         return r;
 781         }
 782
 783         /* Order identical lines by the order there were originally added in */
 784         if (*a < *b)
 785                 return -1;
 786         if (*a > *b)
 787                 return 1;
 788
 789         return 0;
 790 }
 791
 792 static const char *table_data_format(TableData *d) {
 793         assert(d);
 794
 795         if (d->formatted)
 796                 return d->formatted;
 797
 798         switch (d->type) {
 799         case TABLE_EMPTY:
 800                 return "";
 801
 802         case TABLE_STRING:
 803                 return d->string;
 804
 805         case TABLE_BOOLEAN:
 806                 return yes_no(d->boolean);
 807
 808         case TABLE_TIMESTAMP: {
 809                 _cleanup_free_ char *p;
 810
 811                 p = new(char, FORMAT_TIMESTAMP_MAX);
 812                 if (!p)
 813                         return NULL;
 814
 815                 if (!format_timestamp(p, FORMAT_TIMESTAMP_MAX, d->timestamp))
 816                         return "n/a";
 817
 818                 d->formatted = TAKE_PTR(p);
 819                 break;
 820         }
 821
 822         case TABLE_TIMESPAN: {
 823                 _cleanup_free_ char *p;
 824
 825                 p = new(char, FORMAT_TIMESPAN_MAX);
 826                 if (!p)
 827                         return NULL;
 828
 829                 if (!format_timespan(p, FORMAT_TIMESPAN_MAX, d->timestamp, 0))
 830                         return "n/a";
 831
 832                 d->formatted = TAKE_PTR(p);
 833                 break;
 834         }
 835
 836         case TABLE_SIZE: {
 837                 _cleanup_free_ char *p;
 838
 839                 p = new(char, FORMAT_BYTES_MAX);
 840                 if (!p)
 841                         return NULL;
 842
 843                 if (!format_bytes(p, FORMAT_BYTES_MAX, d->size))
 844                         return "n/a";
 845
 846                 d->formatted = TAKE_PTR(p);
 847                 break;
 848         }
 849
 850         case TABLE_UINT32: {
 851                 _cleanup_free_ char *p;
 852
 853                 p = new(char, DECIMAL_STR_WIDTH(d->uint32) + 1);
 854                 if (!p)
 855                         return NULL;
 856
 857                 sprintf(p, "%" PRIu32, d->uint32);
 858                 d->formatted = TAKE_PTR(p);
 859                 break;
 860         }
 861
 862         default:
 863                 assert_not_reached("Unexpected type?");
 864         }
 865
 866         return d->formatted;
 867 }
 868
 869 static int table_data_requested_width(TableData *d, size_t *ret) {
 870         const char *t;
 871         size_t l;
 872
 873         t = table_data_format(d);
 874         if (!t)
 875                 return -ENOMEM;
 876
 877         l = utf8_console_width(t);
 878         if (l == (size_t) -1)
 879                 return -EINVAL;
 880
 881         if (d->maximum_width != (size_t) -1 && l > d->maximum_width)
 882                 l = d->maximum_width;
 883
 884         if (l < d->minimum_width)
 885                 l = d->minimum_width;
 886
 887         *ret = l;
 888         return 0;
 889 }
 890
 891 static char *align_string_mem(const char *str, size_t new_length, unsigned percent) {
 892         size_t w = 0, space, lspace, old_length;
 893         const char *p;
 894         char *ret;
 895         size_t i;
 896
 897         /* As with ellipsize_mem(), 'old_length' is a byte size while 'new_length' is a width in character cells */
 898
 899         assert(str);
 900         assert(percent <= 100);
 901
 902         old_length = strlen(str);
 903
 904         /* Determine current width on screen */
 905         p = str;
 906         while (p < str + old_length) {
 907                 char32_t c;
 908
 909                 if (utf8_encoded_to_unichar(p, &c) < 0) {
 910                         p++, w++; /* count invalid chars as 1 */
 911                         continue;
 912                 }
 913
 914                 p = utf8_next_char(p);
 915                 w += unichar_iswide(c) ? 2 : 1;
 916         }
 917
 918         /* Already wider than the target, if so, don't do anything */
 919         if (w >= new_length)
 920                 return strndup(str, old_length);
 921
 922         /* How much spaces shall we add? An how much on the left side? */
 923         space = new_length - w;
 924         lspace = space * percent / 100U;
 925
 926         ret = new(char, space + old_length + 1);
 927         if (!ret)
 928                 return NULL;
 929
 930         for (i = 0; i < lspace; i++)
 931                 ret[i] = ' ';
 932         memcpy(ret + lspace, str, old_length);
 933         for (i = lspace + old_length; i < space + old_length; i++)
 934                 ret[i] = ' ';
 935
 936         ret[space + old_length] = 0;
 937         return ret;
 938 }
 939
 940 int table_print(Table *t, FILE *f) {
 941         size_t n_rows, *minimum_width, *maximum_width, display_columns, *requested_width,
 942                 i, j, table_minimum_width, table_maximum_width, table_requested_width, table_effective_width,
 943                 *width;
 944         _cleanup_free_ size_t *sorted = NULL;
 945         uint64_t *column_weight, weight_sum;
 946         int r;
 947
 948         assert(t);
 949
 950         if (!f)
 951                 f = stdout;
 952
 953         /* Ensure we have no incomplete rows */
 954         assert(t->n_cells % t->n_columns == 0);
 955
 956         n_rows = t->n_cells / t->n_columns;
 957         assert(n_rows > 0); /* at least the header row must be complete */
 958
 959         if (t->sort_map) {
 960                 /* If sorting is requested, let's calculate an index table we use to lookup the actual index to display with. */
 961
 962                 sorted = new(size_t, n_rows);
 963                 if (!sorted)
 964                         return -ENOMEM;
 965
 966                 for (i = 0; i < n_rows; i++)
 967                         sorted[i] = i * t->n_columns;
 968
 969                 qsort_r_safe(sorted, n_rows, sizeof(size_t), table_data_compare, t);
 970         }
 971
 972         if (t->display_map)
 973                 display_columns = t->n_display_map;
 974         else
 975                 display_columns = t->n_columns;
 976
 977         assert(display_columns > 0);
 978
 979         minimum_width = newa(size_t, display_columns);
 980         maximum_width = newa(size_t, display_columns);
 981         requested_width = newa(size_t, display_columns);
 982         width = newa(size_t, display_columns);
 983         column_weight = newa0(uint64_t, display_columns);
 984
 985         for (j = 0; j < display_columns; j++) {
 986                 minimum_width[j] = 1;
 987                 maximum_width[j] = (size_t) -1;
 988                 requested_width[j] = (size_t) -1;
 989         }
 990
 991         /* First pass: determine column sizes */
 992         for (i = t->header ? 0 : 1; i < n_rows; i++) {
 993                 TableData **row;
 994
 995                 /* Note that we don't care about ordering at this time, as we just want to determine column sizes,
 996                  * hence we don't care for sorted[] during the first pass. */
 997                 row = t->data + i * t->n_columns;
 998
 999                 for (j = 0; j < display_columns; j++) {
1000                         TableData *d;
1001                         size_t req;
1002
1003                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
1004
1005                         r = table_data_requested_width(d, &req);
1006                         if (r < 0)
1007                                 return r;
1008
1009                         /* Determine the biggest width that any cell in this column would like to have */
1010                         if (requested_width[j] == (size_t) -1 ||
1011                             requested_width[j] < req)
1012                                 requested_width[j] = req;
1013
1014                         /* Determine the minimum width any cell in this column needs */
1015                         if (minimum_width[j] < d->minimum_width)
1016                                 minimum_width[j] = d->minimum_width;
1017
1018                         /* Determine the maximum width any cell in this column needs */
1019                         if (d->maximum_width != (size_t) -1 &&
1020                             (maximum_width[j] == (size_t) -1 ||
1021                              maximum_width[j] > d->maximum_width))
1022                                 maximum_width[j] = d->maximum_width;
1023
1024                         /* Determine the full columns weight */
1025                         column_weight[j] += d->weight;
1026                 }
1027         }
1028
1029         /* One space between each column */
1030         table_requested_width = table_minimum_width = table_maximum_width = display_columns - 1;
1031
1032         /* Calculate the total weight for all columns, plus the minimum, maximum and requested width for the table. */
1033         weight_sum = 0;
1034         for (j = 0; j < display_columns; j++) {
1035                 weight_sum += column_weight[j];
1036
1037                 table_minimum_width += minimum_width[j];
1038
1039                 if (maximum_width[j] == (size_t) -1)
1040                         table_maximum_width = (size_t) -1;
1041                 else
1042                         table_maximum_width += maximum_width[j];
1043
1044                 table_requested_width += requested_width[j];
1045         }
1046
1047         /* Calculate effective table width */
1048         if (t->width == (size_t) -1)
1049                 table_effective_width = pager_have() ? table_requested_width : MIN(table_requested_width, columns());
1050         else
1051                 table_effective_width = t->width;
1052
1053         if (table_maximum_width != (size_t) -1 && table_effective_width > table_maximum_width)
1054                 table_effective_width = table_maximum_width;
1055
1056         if (table_effective_width < table_minimum_width)
1057                 table_effective_width = table_minimum_width;
1058
1059         if (table_effective_width >= table_requested_width) {
1060                 size_t extra;
1061
1062                 /* We have extra room, let's distribute it among columns according to their weights. We first provide
1063                  * each column with what it asked for and the distribute the rest.  */
1064
1065                 extra = table_effective_width - table_requested_width;
1066
1067                 for (j = 0; j < display_columns; j++) {
1068                         size_t delta;
1069
1070                         if (weight_sum == 0)
1071                                 width[j] = requested_width[j] + extra / (display_columns - j); /* Avoid division by zero */
1072                         else
1073                                 width[j] = requested_width[j] + (extra * column_weight[j]) / weight_sum;
1074
1075                         if (maximum_width[j] != (size_t) -1 && width[j] > maximum_width[j])
1076                                 width[j] = maximum_width[j];
1077
1078                         if (width[j] < minimum_width[j])
1079                                 width[j] = minimum_width[j];
1080
1081                         assert(width[j] >= requested_width[j]);
1082                         delta = width[j] - requested_width[j];
1083
1084                         /* Subtract what we just added from the rest */
1085                         if (extra > delta)
1086                                 extra -= delta;
1087                         else
1088                                 extra = 0;
1089
1090                         assert(weight_sum >= column_weight[j]);
1091                         weight_sum -= column_weight[j];
1092                 }
1093
1094         } else {
1095                 /* We need to compress the table, columns can't get what they asked for. We first provide each column
1096                  * with the minimum they need, and then distribute anything left. */
1097                 bool finalize = false;
1098                 size_t extra;
1099
1100                 extra = table_effective_width - table_minimum_width;
1101
1102                 for (j = 0; j < display_columns; j++)
1103                         width[j] = (size_t) -1;
1104
1105                 for (;;) {
1106                         bool restart = false;
1107
1108                         for (j = 0; j < display_columns; j++) {
1109                                 size_t delta, w;
1110
1111                                 /* Did this column already get something assigned? If so, let's skip to the next */
1112                                 if (width[j] != (size_t) -1)
1113                                         continue;
1114
1115                                 if (weight_sum == 0)
1116                                         w = minimum_width[j] + extra / (display_columns - j); /* avoid division by zero */
1117                                 else
1118                                         w = minimum_width[j] + (extra * column_weight[j]) / weight_sum;
1119
1120                                 if (w >= requested_width[j]) {
1121                                         /* Never give more than requested. If we hit a column like this, there's more
1122                                          * space to allocate to other columns which means we need to restart the
1123                                          * iteration. However, if we hit a column like this, let's assign it the space
1124                                          * it wanted for good early.*/
1125
1126                                         w = requested_width[j];
1127                                         restart = true;
1128
1129                                 } else if (!finalize)
1130                                         continue;
1131
1132                                 width[j] = w;
1133
1134                                 assert(w >= minimum_width[j]);
1135                                 delta = w - minimum_width[j];
1136
1137                                 assert(delta <= extra);
1138                                 extra -= delta;
1139
1140                                 assert(weight_sum >= column_weight[j]);
1141                                 weight_sum -= column_weight[j];
1142
1143                                 if (restart)
1144                                         break;
1145                         }
1146
1147                         if (finalize) {
1148                                 assert(!restart);
1149                                 break;
1150                         }
1151
1152                         if (!restart)
1153                                 finalize = true;
1154                 }
1155         }
1156
1157         /* Second pass: show output */
1158         for (i = t->header ? 0 : 1; i < n_rows; i++) {
1159                 TableData **row;
1160
1161                 if (sorted)
1162                         row = t->data + sorted[i];
1163                 else
1164                         row = t->data + i * t->n_columns;
1165
1166                 for (j = 0; j < display_columns; j++) {
1167                         _cleanup_free_ char *buffer = NULL;
1168                         const char *field;
1169                         TableData *d;
1170                         size_t l;
1171
1172                         assert_se(d = row[t->display_map ? t->display_map[j] : j]);
1173
1174                         field = table_data_format(d);
1175                         if (!field)
1176                                 return -ENOMEM;
1177
1178                         l = utf8_console_width(field);
1179                         if (l > width[j]) {
1180                                 /* Field is wider than allocated space. Let's ellipsize */
1181
1182                                 buffer = ellipsize(field, width[j], d->ellipsize_percent);
1183                                 if (!buffer)
1184                                         return -ENOMEM;
1185
1186                                 field = buffer;
1187
1188                         } else if (l < width[j]) {
1189                                 /* Field is shorter than allocated space. Let's align with spaces */
1190
1191                                 buffer = align_string_mem(field, width[j], d->align_percent);
1192                                 if (!buffer)
1193                                         return -ENOMEM;
1194
1195                                 field = buffer;
1196                         }
1197
1198                         if (j > 0)
1199                                 fputc(' ', f); /* column separator */
1200
1201                         if (d->color)
1202                                 fputs(d->color, f);
1203
1204                         fputs(field, f);
1205
1206                         if (d->color)
1207                                 fputs(ansi_normal(), f);
1208                 }
1209
1210                 fputc('\n', f);
1211         }
1212
1213         return fflush_and_check(f);
1214 }
1215
1216 int table_format(Table *t, char **ret) {
1217         _cleanup_fclose_ FILE *f = NULL;
1218         char *buf = NULL;
1219         size_t sz = 0;
1220         int r;
1221
1222         f = open_memstream(&buf, &sz);
1223         if (!f)
1224                 return -ENOMEM;
1225
1226         (void) __fsetlocking(f, FSETLOCKING_BYCALLER);
1227
1228         r = table_print(t, f);
1229         if (r < 0)
1230                 return r;
1231
1232         f = safe_fclose(f);
1233
1234         *ret = buf;
1235
1236         return 0;
1237 }
1238
1239 size_t table_get_rows(Table *t) {
1240         if (!t)
1241                 return 0;
1242
1243         assert(t->n_columns > 0);
1244         return t->n_cells / t->n_columns;
1245 }
1246
1247 #if 0 /// UNNEEDED by elogind
1248 size_t table_get_columns(Table *t) {
1249         if (!t)
1250                 return 0;
1251
1252         assert(t->n_columns > 0);
1253         return t->n_columns;
1254 }
1255 #endif // 0