• Re: AVL tree insertion - programming exercise

    From antispam@antispam@fricas.org (Waldek Hebisch) to comp.lang.c on Sat Oct 31 13:34:06 2026
    From Newsgroup: comp.lang.c

    Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
    antispam@fricas.org (Waldek Hebisch) writes:

    [I am responding to two postings, restoring a sentence that
    was removed by an intermediate poster]

    Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

    On 2026-10-18 10:42, Waldek Hebisch wrote:

    [...]

    I read the above as: "can access part of object that fits in
    allocated space". That is important for structs and unions: you
    clearly do not want to allocate memory for biggest union variant.
    And I think that allocating memory only for used part of a struct
    is pretty common.

    I confess to being rather incredulous of these claims. More
    below.

    Mind to explain that opinion?

    If I define a (C-)'union' type I definitely want to store anything
    possible in those unions, changing the value to another type as
    necessary. - Mind the 'sizeof' of a union is [at least?] the size
    of its largest component. - If I 'malloc' a union I use that size.
    In cases where I want to use just one [smaller] component-type of
    a union I just allocate that specific type not the union-type.

    But maybe you meant something different?

    I meant what I wrote.

    I think your alleged facts are wrong. The vast majority of C
    programs, and the vast majority of C programmers, have no
    interest in doing either of those things. If C code needs to use
    some part of an allocated struct, a whole struct is allocated.
    Evidence for this pattern can be seen in the common idiom for
    calling malloc():

    struct foo *pfoo = malloc( sizeof *pfoo );

    I think that allocating smaller size for C struct is rare,
    but that it happens in real C programs.

    The case for unions is even weaker. First it is unusual for a
    union to have highly disparate sizes for its members; a factor
    of two or four, maybe, but rarely more than that.

    One of big guys in programming (maybe Knuth) wrote something
    like "7% saving would be considered significant in most
    branches of engineering". Factor of 2 disparity easily may
    lead to 25% saving from allocating only actually used memory.

    Furthermore if
    it were important to access only a subset of the smaller members
    then it is simple to create a new union type with only those
    members. At some level it's necessary to do that to know what
    size to give to malloc(). (And if it's only one member that is
    meant to be accessed, then we expect to follow the above common
    idiom for malloc() with a pointer to the member's type.)

    If you do not use pointers to unions, then you need to do something
    else, most probably uses casts. Unions limit possible errors,
    so in this case are much better than casts.

    Of course it is not impossible that there are C programs that
    violate these norms. But they are at best few and far between,
    and anyone who would write such programs runs a greatly increased
    risk of undefined behavior. No sensible developer would do so.

    Main data structure in gcc is tree node. It was a C union with
    variants corresponding to various node types. Each node contained
    pointers to other nodes, and such pointers at C level usually
    were just pointers to union. When allocating nodes gcc allocated
    amount of memory for needed variant and after creation of a node
    variant never changed.

    Maybe that was due to exposure to Pascal, IIUC in his first shot
    at gcc Stalmann used part of (extended) Pascal compiler (later
    had to remove this part due to licence restrictions).

    But this is safer alternative to say using 'void *' and casting
    pointers to right structure type.

    In any case any use of such anti-patterns is so rare that it
    wasn't a factor in deciding how malloc() is supposed to work.

    C type system is too weak to give exact
    type for more complicated data structure. Instead, real program
    give approximate type and depend on holes in type system.

    This idea is nonsense. The C type system is powerful enough to
    express any type that C code can deal with.

    Maybe you should write "any C type that ...", which is tautologically
    true, but free of information content. It is well known that
    C type system can not express object oriented concepts. More
    to the point, C type system can not express parametrized types
    and more general recursive types. As a simple example consider
    function that should reverse order of a linked list. At logical
    level we have pointer to next element and a payload, which can
    be arbitrary. That can be expressed using paramtrized type like

    typedef struct {NODE(T) * next; T payload;} NODE(T);

    except for that the above is not valid C. What we can do is
    to write code like:

    typedef struct gen_lst gen_lst;
    struct gen_lst {gen_lst * next;};

    gen_lst *
    nreverse_gen0(gen_lst * el, gen_lst * prev) {
    while(el) {
    gen_lst * next = el->next;
    el->next = prev;
    prev = el;
    el = next;
    }
    return prev;
    }

    and at points of use cast pointer to actual list type to pointer
    to 'gen_lst'. So a program can work with parametrized types,
    but it depends on hole in type safety, that is using casts
    (and explicit provision of C standard about layout of common
    prefix of two structs).

    So you
    have pointer to union and program is structured so that it only
    accesses valid variant. Allocating memory for whole using may
    waste a lot of memory and does not buy you any real safety:
    accessing wrong variant is likely to lead to troubles regardless
    of amount of memory that you allocated. And in case of
    interesting data structures variant does not change after
    creation (allocation). If you need different variant you simply
    allocate new piece of memory.

    BTW: Pascal 'new' for variant records takes extra argument
    specifying requested variant. Corresponding pointer has type
    'pointer to variant record', but legally can only be used with
    the variant specified in call to 'new'. In C you get equivalent
    effect (with essentially the same conditions) by allocating
    amount of memory needed for specific variant of union, but
    assigning 'malloc' result to pointer to union.

    Here we see the key to understanding the earlier comments: we
    have someone who wants to write code in C but who wants to think
    in Pascal. There is no reason to think the C standard means to
    support the anti-patterns being advocated.
    --
    Waldek Hebisch
    --- Synchronet 3.22a-Linux NewsLink 1.2