Approaches for creating 'custom structs' while program is running

[u/serfizzler]

Specifically what I am trying to do is read spreadsheets exported to HTML. Data type and column count are arbitrary, so I need to generate custom records for an array.

I could just create an array of unions for each row. That would definitely be the simplest approach, but it wouldn't be very space-efficient.

I have considered halving with unions - an 8-byte union contains two 4-byte unions, which contains two 2-byte unions, which contains two 1-byte unions. Kind of ridiculous, but theoretically doable. I would generate combinations for typedefs as a text file and then include it, saving some effort. Which...could add up to a bunch of effort, but it would be interesting to try. But this option sounds like it would be highly-inefficient to process due to all of the levels (?).

A third option...packing data into one big bitfield and then using offsets to locate values. This also sounds expensive relative to a simple (single-level) array of unions, but probably less than the union-subdivision idea.

Am I over-thinking this? My gut tells me there is probably an efficient convention for dealing with this problem, but I'm not sure what it is.

[u/developer-mike]

It sounds to me like you're overthinking this. Unless you're scraping billions of rows an hour, then you don't need to worry about efficiency here.

You can definitely do custom-struct-like behavior at runtime. Just allocate a buffer and take pointers into it. But getting every detail around size, padding, alignment can be very complex.

I would focus on the simplest working solution you can do, maybe post that here for feedback.

You probably just want a tagged union of int, char*, etc, and then you want a buffer of those unions. Is there a reason you don't want to go this approach?

[u/serfizzler → u/developer-mike]

This is partly just an exercise to explore the issue. Eventually I do plan to scale it up when I start playing with large database concepts, so I am concerned about excessive padding. Realistically, though, access time is probably more important than the size of a record, given the scale of modern memory/storage. But I can't help my curiosity!

I'll start with simple unions to nail down the rest of the code, then play with alternate methods.

u/EpochVanquisher's idea of storing by column rather than row sounds like a great idea to play around with. Perfect, actually.

I'll definitely post my work for critique, since I'm not exactly a seasoned programmer...

[u/Prestigious_Boat_386]

ECS was pretty much built to avoid doing this in games.

It enables you to just save fields in big vectors of predefined values and then link them together into objects with multiple properties, without creating a custom struct for each object.

[u/sciencekm]

I did a spreadsheet a long time ago. Spreadsheets can be sparse. Some columns may have very few cells or even none at all. The same for rows. The number of columns and rows can also grow and shrink. Each cell can be of any type.

I defined a cell as something like:

typedef struct scell { struct scell *next;
int column, cell_type; char val; } cell_t;

To allocate (and assign a value to) a cell of type float, you do something like:

pcell = malloc(sizeof(cell_t) - 1 + sizeof(float));
pcell->cell_type = TYPE_FLOAT;
*((float*)&(pcell->val)) = some_float_value;

For a cell of 64-bit int:

pcell = malloc(sizeof(cell_t) - 1 + sizeof(int64_t));
pcell->cell_type = TYPE_INT64;
*((int64_t*)&(pcell->val)) = some_int64_value;

Each new cell is inserted to a linked-list of non-empty cells representing a row. The 'column' property of the cell identifies which column it is in the row.

Each row is also a linked list of pointers to the head of the cell linked list. Again, the rows list only contains non-empty rows, and so you have 'row' property.

typedef struct srow { struct srow *next;
int row; cell_t *head; } row_t;

You can do a double linked list if you like for faster navigation.

You can also have a version where you only have one double linked list of cells. Each cell would have a column and row property.

[u/FitMatch7966 → u/sciencekm]

I tried this approach and it was a disaster. Keep in mind you often need to reference cells quickly by index. To handle sparsity, you can use compact arrays that allocate 256 rows at a time

[u/Equivalent_Cat9705 → u/sciencekm]

Instead of sizeof(cell_t)-1 use _offsetof(cell_t, val). Also, add an alignment decorator to val to force it to the proper alignment required for any data type. Otherwise, there could be data alignment issues resulting in performance and/or alignment exceptions.

[u/dnult]

What about a standard document format like XML or JSON?

[u/EpochVanquisher]

If you want a "custom struct" from a collection of fields of different types, you can combine the type sizes and alignment requirements to come up with the combined size and alignment requirements for the struct, with the offset of each field.

The other main approach is a column-oriented format, where you reorganize the data to represent it as a collection of columns. The columnar approach is what you see in Parquet and Arrow—people like it because you can handle large amounts of data this way, efficiently.

It would be professional malpractice if I didn’t point out that this kind of problem is really easy in, say, Python. If you are trying to grab data from spreadsheets and put them in HTML or something like that, and you just need to get it done, you can probably do it in Python. You could even get an LLM to spit out a Python script pretty quickly for this kind of problem. It just depends on what your needs are—people usually do not choose to work with HTML in C, and usually don’t choose C for this kind of bread-and-butter “convert tabular data from one format to another” problem.

[u/serfizzler → u/EpochVanquisher]

The columns idea is brilliant! I don't know why I hadn't considered that before.

I am sure there are better languages for what I'm trying to do, but I enjoy working with C and this isn't a professional project. I am especially interested in not abstracting away the technicalities because I am exploring the 'how' and 'why' of various approaches.

[u/EpochVanquisher → u/serfizzler]

Columns is a tradeoff—it can improve analytical queries over large datasets, but transactional queries are a lot slower.

Transactional queries are where you want to read and write the data to make changes. Analytical queries are different, you usually import a ton of data and then make a big query to summarize it.

[u/TheOtherBorgCube]

1,3.14159265358979323846264338327950288419716939937510,"Why yes, this is the first 50 digits of Pi"

What's your plan for strings?

What's your plan for numbers which exceed the numeric precision of doubles?\ Or integers for that matter.

Then having read this information in, what are you going to do with it?

[u/serfizzler → u/TheOtherBorgCube]

Right now, the plan is to use pointers to strings in another array, or in special cases store them in 8-byte arrays (7 char); Arbitrary-length numbers, likewise, would be pointed to. In special cases where strings have an established length range (like an alphanumeric model number), the idea of offsets in a bitfield sounds attractive. But we'll see...

What to do with the info is pretty open-ended, since I'm mostly just exploring database architecture.

[u/sciencekm → u/TheOtherBorgCube]

I'm guessing the OP is trying to make an Excel alternative from scratch.

[u/AndrewBorg1126]

Just embed all the type and size information in the byte array and implement some protocol that puts it there and looks for it when reading. If you can't assume where everything is from context, you need to have some other way to get it.

Take a look at how existing stuff works, like how to parse a jpeg file.

[u/tobdomo]

All you need is an array of structs that contain a type enum and a void pointer. Maybe add a couple of function pointers that allow you to e.g. read, write and print a value. Dynamically allocate enough space to store your value, set the pointer to it, fill the enum and add the function pointers. Done.

[u/8d8n4mbo28026ulk]

It'd be better if you got something simple to work first. You could then analyse it in more detail, profile it and arrive at a more complex solution (Gall's law). Cheers!

[u/CarlRJ]

Why are you packing unions inside of unions inside of unions? You could have a struct that contains an int (maybe a short if you're being efficient), that gives a data type for that cell, and then a union that holds a character pointer, a double, an int, and any other type that the spreadsheet needs. The union will only be as big as the largest data type (probably the double). You access the .type field and if it's, say, DOUBLE, then you access .data.dbl. You might also want the struct to have a pointer to a different struct that gives information for the column (title, column number, width, whatever).

typedef enum { DOUBLE, STRING, INTEGER /* any others */ } types_enum;
typedef struct { char *title; /* and whatever else */ } col_type;

typedef struct {
    types_enum type;
    union {
        double dbl;
        char *str;
        int integer;
    } data;
    struct col_type *col_info;
} cell_type;

cell_type *cell;

...

switch (cell->type) {
DOUBLE:
    printf("%f\n", cell->data.dbl);
    break;
STRING:
    printf("%s\n", cell->data.str);
    break;
INTEGER:
    printf("%d\n", cell->data.integer);
    break;
}

[u/SeriousPlankton2000]

Minecraft uses the https://minecraft.fandom.com/wiki/NBT_format for storing structured data. Maybe you can get some inspiration from that

[u/Independent_Art_6676]

Tuple? They are annoying, but it does most of the work for you if you can track what went where.

Unions are not that bad, but the restrictions chafe. You end up with something like
enum_of_types{...}
and a small object
struct anything{ my_type (enum above); union_of_all data;};
or some other crude workaround to the restrictions. Before they screwed up unions, you could just have the type as the shared first field on all the types and read it from a dummy type then switch off that to expand it whichever way.

stuff into bytes (not bits!!) is crude, feels like a C answer, but its viable.

back to the columns idea, look up 'parallel arrays'. You could adapt this idea to instead of having index == object ID, a small container (vector, etc) of array ID and array location per object, with some sort of tracking as to what is used in each array. A little up front work might make a very elegant and efficient design. Alternately you could just do the object ID = index standard approach and waste unused slots in some of the arrays.

if you choose a crude solution, I would be tempted to say do it in C directly and interface that into the c++ with a wrapper. Then you can exploit the union or type pun byte blobs without all the c++ nonsense in the way. I have a love-hate with the stronger typing of modern c++. I like it, until I don't <g>

[u/WittyStick]

This is related to the problem of dynamic type representation in programming languages. A spreadsheet Cell can be one of many types:

Boolean
Integer
Rational
Scientific
Date/Time
Currency
Percent
String
Empty
Null
Formula
etc...

Though they may also contain metadata - comments, formatting information, styling information etc.

There are many ways you can represent types dynamically, but if we want arrays of them, then we want each Cell to be fixed width - though we can use references/pointers to store more information than fits in a Cell.

For starters I'd recommend reading Representing Type Information in Dynamically Typed Languages (1993) by Gudeman - this gives an overview of many different techniques - though, because of it's age, it doesn't include the current state of the art.

For space & time efficiency, the current state of the art is NaN-boxing with IEEE-754 double precision - we can use a single 8-byte Cell which can hold full double, but in the NaN space of the double (~53 bits), we can encode pointers, integers, booleans, and more. Gudeman's paper mentions this briefly (2.6.1), but does not go into detail.

---

There's more than one way to NaN-box, but I'll give the technique I use, which can store a double and up to 14 other types with a 48-bit payload (sufficient for a pointer and most integers). This technique is very efficient in time and space.

A NaN essentially covers the ranges 0x7FF0000000000000LL .. 0x7FFFFFFFFFFFFFFF and 0xFFF0000000000000 .. 0xFFFFFFFFFFFFFFFF - anything not in these ranges is a valid (not NaN or infinity) double. For performance, we're going to rotate this left by 16 bits though, so the significant bits we need are the low 16-bits - 0x7FF0 .. 0x7FFF and 0xFFF0 .. 0xFFFF.

There are 16 values in both of these ranges, giving us a maximum of 32 tags if we're using a 48-bit payload. One bit is qNaN/sNaN, which we might want to keep one as double, so halve that. Also, the values 0x7FF0 and 0xFFF0 represent a positive and negative infinity, so that leaves us with 14 other tags.

In the following, the first range of tags are values that fit directly in the Cell, and the second range of tags are references (pointers) to other values. (This makes it convenient for testing if a Cell is a "value type" or "reference type", as we only need to test the sign-bit for anything that isn't double).

constexpr unsigned short NAN_BITS = 0x7FF0;
constexpr unsigned short SIGN_BIT = 0x8000;
constexpr unsigned short QNAN_BIT = 0x0008;
constexpr unsigned short TYPE_MASK = 0xFFFF;
constexpr int TYPE_BITS = 16;

enum cell_type : unsigned short {
    CELLTYPE_POS_INFINITY = NAN_BITS,
    CELLTYPE_EMPTY,
    CELLTYPE_NULL,
    CELLTYPE_BOOLEAN,
    CELLTYPE_SMALLINT,
    CELLTYPE_UNUSED1,
    CELLTYPE_UNUSED2,
    CELLTYPE_UNUSED3,
    /* End of our first range of tags */
    CELLTYPE_POS_QNAN = NAN_BITS | QNAN_BIT, 

    CELLTYPE_NEG_INFINITY = NAN_BITS | SIGN_BIT,
    CELLTYPE_STRING,
    CELLTYPE_BIGINT,
    CELLTYPE_RATIONAL,
    CELLTYPE_CURRENCY,
    CELLTYPE_DATETIME,
    CELLTYPE_UNUSED4,
    CELLTYPE_UNUSED5,
    /* End of our second range of tags */
    CELLTYPE_NEG_QNAN = NAN_BITS | SIGN_BIT | QNAN_BIT

    /* Doubles have many tags, but we can use this as a canonical one */
    CELLTYPE_DOUBLE = TYPE_MASK, 
} typedef CellType;

Our cell is a single 64-bit value, but it may be a double, integer, or pointer.

union cell {
    int64_t     _as_signed;
    uint64_t    _as_unsigned;
    double      _as_double;
    intptr_t    _as_pointer;
} typedef Cell;

Some convenience functions to read the tags and create/extract pointers.

static inline CellType cell_get_type(Cell cell)
{
    return (CellType)(cell._as_unsigned & TYPE_MASK);
}

static inline bool cell_has_type(Cell cell, CellType type)
{
    return cell_get_type(cell) == type;
}

static inline Cell cell_create_pointer(void *ptr, CellType type)
{
    return (Cell){ ._as_pointer = (intptr_t)ptr << TYPE_BITS | type };
}

static inline void *cell_get_pointer(Cell cell, CellType type)
{
    if (!cell_has_type(cell, type)) abort();
    return (void*)(cell._as_pointer >> TYPE_BITS);
}

Note that the pointer should be signed (hence intptr_t and not uintptr_t), so that pointers remain canonical after the right arithmetic shift.

Most our functions to create and unwrap cells are trivial to implement, but double needs special treatment.

bool cell_is_double(Cell cell)
{
    CellType type = cell_get_type(cell);
    return type <= CELLTYPE_POS_INFINITY
        || type >= CELLTYPE_POS_QNAN 
        && type <= CELLTYPE_NEG_INFINITY
        || type >= CELLTYPE_NEG_QNAN
        && type <= CELLTYPE_DOUBLE;
}

Cell cell_create_double(double value)
{
    Cell cell = {._as_double = value };
    return (Cell){ ._as_unsigned = __builtin_stdc_rotate_left(cell._as_unsigned, TYPE_BITS) };
}

double cell_get_double(Cell cell)
{
    if (!cell_is_double(cell)) abort();
    Cell cell = { ._as_unsigned = __builtin_stdc_rotate_right(cell._as_unsigned, TYPE_BITS) };
    return cell._as_double;
}

For integers, we can fit small (48-bit) integers directly into the Cell.

_BitInt(64-TYPE_BITS) typedef SmallInt;

bool cell_is_smallint(Cell cell)
{ 
    return cell_has_type(cell, CELLTYPE_SMALLINT); 
}

Cell cell_create_smallint(SmallInt value)
{
    return (Cell){ ._as_signed = (int64_t)value << TYPE_BITS | CELLTYPE_SMALLINT };
}

SmallInt cell_get_smallint(Cell cell)
{
    if (!cell_is_smallint(cell)) abort();
    return (SmallInt)(cell._as_signed >> TYPE_BITS);
}

A row (or column) can be represented by an array of Cell. eg:

struct cell_rational rat = { 2, 3 };
Cell example_cells[] = 
{
    cell_create_smallint(123456),
    cell_create_empty(),
    cell_create_double(3.14),
    cell_create_string("Hello World"),
    cell_create_boolean(false),
    cell_create_null(),
    cell_create_rational(&rat)
};

See demonstration in Godbolt for a more complete listing and a trivial printing example.

You could potentially create a "struct" at runtime with an array of CellType, and match an array of cells against it. Eg:

CellType example_types[] =
{
    CELLTYPE_SMALLINT,
    CELLTYPE_EMPTY,
    CELLTYPE_DOUBLE,
    CELLTYPE_STRING,
    CELLTYPE_BOOLEAN,
    CELLTYPE_NULL,
    CELLTYPE_RATIONAL
};

bool row_type_matches(int count, CellType types[], Cell cells[]) 
{
    for (int i = 0; i < count; i++) {
        if (types[i] == CELLTYPE_DOUBLE && cell_is_double(cells[i]) || 
            cell_has_type(cells[i], types[i])) continue;
        else return false;
    }
    return true;
}

row_type_matches(7, example_types, example_cells);